FTLB3Output should maintain good block order like the LLVM one does
authorfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 26 Jan 2016 08:17:31 +0000 (08:17 +0000)
committerfpizlo@apple.com <fpizlo@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 26 Jan 2016 08:17:31 +0000 (08:17 +0000)
https://bugs.webkit.org/show_bug.cgi?id=152222

Reviewed by Geoffrey Garen.

Source/JavaScriptCore:

This fixes FTLB3Output to emit an ordered B3 IR. This makes inspecting IR *a lot* easier.
It will also be a performance win whenever we use range-based data structures for
liveness.

Also two small other changes:
- Added some more dumping in integer range optimization phase.
- Refined the disassembler's printing of instruction width suffixes so that "jzl" is not
  a thing. It was using "l" as the suffix because jumps take a 32-bit immediate.

* b3/B3Procedure.cpp:
(JSC::B3::Procedure::addBlock):
(JSC::B3::Procedure::setBlockOrderImpl):
(JSC::B3::Procedure::clone):
* b3/B3Procedure.h:
(JSC::B3::Procedure::frontendData):
(JSC::B3::Procedure::setBlockOrder):
* dfg/DFGIntegerRangeOptimizationPhase.cpp:
* disassembler/udis86/udis86_syn-att.c:
(ud_translate_att):
* ftl/FTLB3Output.cpp:
(JSC::FTL::Output::initialize):
(JSC::FTL::Output::newBlock):
(JSC::FTL::Output::applyBlockOrder):
(JSC::FTL::Output::appendTo):
* ftl/FTLB3Output.h:
(JSC::FTL::Output::setFrequency):
(JSC::FTL::Output::insertNewBlocksBefore):
(JSC::FTL::Output::callWithoutSideEffects):
(JSC::FTL::Output::newBlock): Deleted.
* ftl/FTLLowerDFGToLLVM.cpp:
(JSC::FTL::DFG::LowerDFGToLLVM::lower):

Source/WTF:

In the FTL we need to be able to construct a list by inserting elements before other
specific elements. We didn't already have a scalable way to do this, so this adds such a
data structure to WTF. This also has changes to SentinelLinkedList to make it support
these kinds of insertions.

* WTF.xcodeproj/project.pbxproj:
* wtf/OrderMaker.h: Added.
(WTF::OrderMaker::Node::Node):
(WTF::OrderMaker::OrderMaker):
(WTF::OrderMaker::prepend):
(WTF::OrderMaker::append):
(WTF::OrderMaker::insertBefore):
(WTF::OrderMaker::insertAfter):
(WTF::OrderMaker::iterator::iterator):
(WTF::OrderMaker::iterator::operator*):
(WTF::OrderMaker::iterator::operator++):
(WTF::OrderMaker::iterator::operator==):
(WTF::OrderMaker::iterator::operator!=):
(WTF::OrderMaker::begin):
(WTF::OrderMaker::end):
(WTF::OrderMaker::newNode):
* wtf/SentinelLinkedList.h:
(WTF::BasicRawSentinelNode::isOnList):
(WTF::BasicRawSentinelNode<T>::remove):
(WTF::BasicRawSentinelNode<T>::prepend):
(WTF::BasicRawSentinelNode<T>::append):
(WTF::RawNode>::SentinelLinkedList):
(WTF::RawNode>::push):
(WTF::RawNode>::append):
(WTF::RawNode>::remove):
(WTF::RawNode>::prepend):
(WTF::RawNode>::isOnList):

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@195585 268f45cc-cd09-0410-ab3c-d52691b4dbfc

13 files changed:
Source/JavaScriptCore/ChangeLog
Source/JavaScriptCore/b3/B3Procedure.cpp
Source/JavaScriptCore/b3/B3Procedure.h
Source/JavaScriptCore/dfg/DFGIntegerRangeOptimizationPhase.cpp
Source/JavaScriptCore/disassembler/udis86/udis86_syn-att.c
Source/JavaScriptCore/ftl/FTLB3Output.cpp
Source/JavaScriptCore/ftl/FTLB3Output.h
Source/JavaScriptCore/ftl/FTLLowerDFGToLLVM.cpp
Source/WTF/ChangeLog
Source/WTF/WTF.xcodeproj/project.pbxproj
Source/WTF/wtf/CMakeLists.txt
Source/WTF/wtf/OrderMaker.h [new file with mode: 0644]
Source/WTF/wtf/SentinelLinkedList.h

index 91368d8..3e5a725 100644 (file)
@@ -1,3 +1,42 @@
+2016-01-25  Filip Pizlo  <fpizlo@apple.com>
+
+        FTLB3Output should maintain good block order like the LLVM one does
+        https://bugs.webkit.org/show_bug.cgi?id=152222
+
+        Reviewed by Geoffrey Garen.
+
+        This fixes FTLB3Output to emit an ordered B3 IR. This makes inspecting IR *a lot* easier.
+        It will also be a performance win whenever we use range-based data structures for
+        liveness.
+
+        Also two small other changes:
+        - Added some more dumping in integer range optimization phase.
+        - Refined the disassembler's printing of instruction width suffixes so that "jzl" is not
+          a thing. It was using "l" as the suffix because jumps take a 32-bit immediate.
+
+        * b3/B3Procedure.cpp:
+        (JSC::B3::Procedure::addBlock):
+        (JSC::B3::Procedure::setBlockOrderImpl):
+        (JSC::B3::Procedure::clone):
+        * b3/B3Procedure.h:
+        (JSC::B3::Procedure::frontendData):
+        (JSC::B3::Procedure::setBlockOrder):
+        * dfg/DFGIntegerRangeOptimizationPhase.cpp:
+        * disassembler/udis86/udis86_syn-att.c:
+        (ud_translate_att):
+        * ftl/FTLB3Output.cpp:
+        (JSC::FTL::Output::initialize):
+        (JSC::FTL::Output::newBlock):
+        (JSC::FTL::Output::applyBlockOrder):
+        (JSC::FTL::Output::appendTo):
+        * ftl/FTLB3Output.h:
+        (JSC::FTL::Output::setFrequency):
+        (JSC::FTL::Output::insertNewBlocksBefore):
+        (JSC::FTL::Output::callWithoutSideEffects):
+        (JSC::FTL::Output::newBlock): Deleted.
+        * ftl/FTLLowerDFGToLLVM.cpp:
+        (JSC::FTL::DFG::LowerDFGToLLVM::lower):
+
 2016-01-25  Skachkov Oleksandr  <gskachkov@gmail.com>
 
         [ES6] Arrow function syntax. Arrow function specific features. Lexical bind "arguments"
index 4dcc665..b323f40 100644 (file)
@@ -68,6 +68,29 @@ BasicBlock* Procedure::addBlock(double frequency)
     return result;
 }
 
+void Procedure::setBlockOrderImpl(Vector<BasicBlock*>& blocks)
+{
+    IndexSet<BasicBlock> blocksSet;
+    blocksSet.addAll(blocks);
+
+    for (BasicBlock* block : *this) {
+        if (!blocksSet.contains(block))
+            blocks.append(block);
+    }
+
+    // Place blocks into this's block list by first leaking all of the blocks and then readopting
+    // them.
+    for (auto& entry : m_blocks)
+        entry.release();
+
+    m_blocks.resize(blocks.size());
+    for (unsigned i = 0; i < blocks.size(); ++i) {
+        BasicBlock* block = blocks[i];
+        block->m_index = i;
+        m_blocks[i] = std::unique_ptr<BasicBlock>(block);
+    }
+}
+
 Value* Procedure::clone(Value* value)
 {
     std::unique_ptr<Value> clone(value->cloneImpl());
index 4081787..4bf6845 100644 (file)
@@ -78,6 +78,18 @@ public:
     const void* frontendData() const { return m_frontendData; }
 
     JS_EXPORT_PRIVATE BasicBlock* addBlock(double frequency = 1);
+
+    // Changes the order of basic blocks to be as in the supplied vector. The vector does not
+    // need to mention every block in the procedure. Blocks not mentioned will be placed after
+    // these blocks in the same order as they were in originally.
+    template<typename BlockIterable>
+    void setBlockOrder(const BlockIterable& iterable)
+    {
+        Vector<BasicBlock*> blocks;
+        for (BasicBlock* block : iterable)
+            blocks.append(block);
+        setBlockOrderImpl(blocks);
+    }
     
     template<typename ValueType, typename... Arguments>
     ValueType* add(Arguments...);
@@ -278,6 +290,8 @@ public:
 private:
     friend class BlockInsertionSet;
     
+    void setBlockOrderImpl(Vector<BasicBlock*>&);
+
     JS_EXPORT_PRIVATE size_t addValueIndex();
     
     Vector<std::unique_ptr<BasicBlock>> m_blocks;
index c59fde9..7df9004 100644 (file)
@@ -1221,10 +1221,16 @@ public:
                         minValue = std::max(minValue, relationship.minValueOfLeft());
                         maxValue = std::min(maxValue, relationship.maxValueOfLeft());
                     }
+
+                    if (verbose)
+                        dataLog("    minValue = ", minValue, ", maxValue = ", maxValue, "\n");
                     
                     if (sumOverflows<int>(minValue, node->child2()->asInt32()) ||
                         sumOverflows<int>(maxValue, node->child2()->asInt32()))
                         break;
+
+                    if (verbose)
+                        dataLog("    It's in bounds.\n");
                     
                     executeNode(block->at(nodeIndex));
                     node->setArithMode(Arith::Unchecked);
index 4064b27..c9c8488 100644 (file)
@@ -231,7 +231,8 @@ ud_translate_att(struct ud *u)
   }
 
   for (i = 3; i--;) {
-      if (u->operand[i].size > size)
+      if (u->operand[i].size > size
+          && u->operand[i].type != UD_OP_JIMM)
           size = u->operand[i].size;
   }
 
index 9f4997c..1720c2b 100644 (file)
@@ -51,6 +51,23 @@ void Output::initialize(AbstractHeapRepository& heaps)
     m_heaps = &heaps;
 }
 
+LBasicBlock Output::newBlock(const char*)
+{
+    LBasicBlock result = m_proc.addBlock(m_frequency);
+
+    if (!m_nextBlock)
+        m_blockOrder.append(result);
+    else
+        m_blockOrder.insertBefore(m_nextBlock, result);
+
+    return result;
+}
+
+void Output::applyBlockOrder()
+{
+    m_proc.setBlockOrder(m_blockOrder);
+}
+
 LBasicBlock Output::appendTo(LBasicBlock block, LBasicBlock nextBlock)
 {
     appendTo(block);
index add7d35..6a0c103 100644 (file)
@@ -53,6 +53,7 @@
 #include "FTLValueFromBlock.h"
 #include "FTLWeight.h"
 #include "FTLWeightedTarget.h"
+#include <wtf/OrderMaker.h>
 #include <wtf/StringPrintStream.h>
 
 // FIXME: remove this once everything can be generated through B3.
@@ -82,11 +83,7 @@ public:
         m_frequency = value;
     }
 
-    LBasicBlock newBlock(const char* name = "")
-    {
-        UNUSED_PARAM(name);
-        return m_proc.addBlock(m_frequency);
-    }
+    LBasicBlock newBlock(const char* name = "");
 
     LBasicBlock insertNewBlocksBefore(LBasicBlock nextBlock)
     {
@@ -95,6 +92,8 @@ public:
         return lastNextBlock;
     }
 
+    void applyBlockOrder();
+
     LBasicBlock appendTo(LBasicBlock, LBasicBlock nextBlock);
     void appendTo(LBasicBlock);
 
@@ -469,6 +468,8 @@ public:
     double m_frequency { 1 };
 
 private:
+    OrderMaker<LBasicBlock> m_blockOrder;
+    
     template<typename Function, typename... Args>
     LValue callWithoutSideEffects(B3::Type type, Function function, LValue arg1, Args... args)
     {
index 4c4e444..c46406a 100644 (file)
@@ -454,6 +454,9 @@ public:
         // write a B3 phase that so aggressively assumes the lack of orphans that it would crash
         // if any orphans were around. We might even have such phases already.
         m_proc.deleteOrphans();
+
+        // We put the blocks into the B3 procedure in a super weird order. Now we reorder them.
+        m_out.applyBlockOrder();
 #endif // FTL_USES_B3
 
 #if !FTL_USES_B3
index 68c8af5..769cc05 100644 (file)
@@ -1,3 +1,43 @@
+2016-01-25  Filip Pizlo  <fpizlo@apple.com>
+
+        FTLB3Output should maintain good block order like the LLVM one does
+        https://bugs.webkit.org/show_bug.cgi?id=152222
+
+        Reviewed by Geoffrey Garen.
+
+        In the FTL we need to be able to construct a list by inserting elements before other
+        specific elements. We didn't already have a scalable way to do this, so this adds such a
+        data structure to WTF. This also has changes to SentinelLinkedList to make it support
+        these kinds of insertions.
+
+        * WTF.xcodeproj/project.pbxproj:
+        * wtf/OrderMaker.h: Added.
+        (WTF::OrderMaker::Node::Node):
+        (WTF::OrderMaker::OrderMaker):
+        (WTF::OrderMaker::prepend):
+        (WTF::OrderMaker::append):
+        (WTF::OrderMaker::insertBefore):
+        (WTF::OrderMaker::insertAfter):
+        (WTF::OrderMaker::iterator::iterator):
+        (WTF::OrderMaker::iterator::operator*):
+        (WTF::OrderMaker::iterator::operator++):
+        (WTF::OrderMaker::iterator::operator==):
+        (WTF::OrderMaker::iterator::operator!=):
+        (WTF::OrderMaker::begin):
+        (WTF::OrderMaker::end):
+        (WTF::OrderMaker::newNode):
+        * wtf/SentinelLinkedList.h:
+        (WTF::BasicRawSentinelNode::isOnList):
+        (WTF::BasicRawSentinelNode<T>::remove):
+        (WTF::BasicRawSentinelNode<T>::prepend):
+        (WTF::BasicRawSentinelNode<T>::append):
+        (WTF::RawNode>::SentinelLinkedList):
+        (WTF::RawNode>::push):
+        (WTF::RawNode>::append):
+        (WTF::RawNode>::remove):
+        (WTF::RawNode>::prepend):
+        (WTF::RawNode>::isOnList):
+
 2016-01-25  Alex Christensen  <achristensen@webkit.org>
 
         [Win] Copy forwarding headers before building a project
index 6df2118..2b2870a 100644 (file)
@@ -36,6 +36,7 @@
                0F8F2B92172E0103007DBDA5 /* CompilationThread.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F8F2B8F172E00F0007DBDA5 /* CompilationThread.cpp */; };
                0F8F2B9C172F2596007DBDA5 /* ConversionMode.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F8F2B9B172F2594007DBDA5 /* ConversionMode.h */; };
                0F93274B1C17F4B700CF6564 /* Box.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F93274A1C17F4B700CF6564 /* Box.h */; };
+               0F9495841C571CC900413A48 /* OrderMaker.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F9495831C571CC900413A48 /* OrderMaker.h */; };
                0F9D3360165DBA73005AD387 /* FilePrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9D335B165DBA73005AD387 /* FilePrintStream.cpp */; };
                0F9D3361165DBA73005AD387 /* FilePrintStream.h in Headers */ = {isa = PBXBuildFile; fileRef = 0F9D335C165DBA73005AD387 /* FilePrintStream.h */; };
                0F9D3362165DBA73005AD387 /* PrintStream.cpp in Sources */ = {isa = PBXBuildFile; fileRef = 0F9D335D165DBA73005AD387 /* PrintStream.cpp */; };
                0F8F2B90172E00F0007DBDA5 /* CompilationThread.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = CompilationThread.h; sourceTree = "<group>"; };
                0F8F2B9B172F2594007DBDA5 /* ConversionMode.h */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.h; path = ConversionMode.h; sourceTree = "<group>"; };
                0F93274A1C17F4B700CF6564 /* Box.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Box.h; sourceTree = "<group>"; };
+               0F9495831C571CC900413A48 /* OrderMaker.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = OrderMaker.h; sourceTree = "<group>"; };
                0F9D335B165DBA73005AD387 /* FilePrintStream.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = FilePrintStream.cpp; sourceTree = "<group>"; };
                0F9D335C165DBA73005AD387 /* FilePrintStream.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FilePrintStream.h; sourceTree = "<group>"; };
                0F9D335D165DBA73005AD387 /* PrintStream.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = PrintStream.cpp; sourceTree = "<group>"; };
                                A8A472D6151A825B004123FF /* NumberOfCores.h */,
                                7E29C33D15FFD79B00516D61 /* ObjcRuntimeExtras.h */,
                                1AFDE6521953B23D00C48FFA /* Optional.h */,
+                               0F9495831C571CC900413A48 /* OrderMaker.h */,
                                A8A472D7151A825B004123FF /* OSAllocator.h */,
                                A8A472D8151A825B004123FF /* OSAllocatorPosix.cpp */,
                                7CBBA07319BB7FDC00BBF025 /* OSObjectPtr.h */,
                                A8A473EA151A825B004123FF /* MD5.h in Headers */,
                                CD5497AD15857D0300B5BC30 /* MediaTime.h in Headers */,
                                A8A473EB151A825B004123FF /* MessageQueue.h in Headers */,
+                               0F9495841C571CC900413A48 /* OrderMaker.h in Headers */,
                                A8A473ED151A825B004123FF /* MetaAllocator.h in Headers */,
                                A8A473EE151A825B004123FF /* MetaAllocatorHandle.h in Headers */,
                                FE8225311B2A1E5B00BA68FD /* NakedPtr.h in Headers */,
index a0602b8..f0b24c8 100644 (file)
@@ -60,6 +60,7 @@ set(WTF_HEADERS
     NumberOfCores.h
     OSAllocator.h
     OSRandomSource.h
+    OrderMaker.h
     PageAllocation.h
     PageBlock.h
     PageReservation.h
diff --git a/Source/WTF/wtf/OrderMaker.h b/Source/WTF/wtf/OrderMaker.h
new file mode 100644 (file)
index 0000000..12c9de0
--- /dev/null
@@ -0,0 +1,143 @@
+/*
+ * Copyright (C) 2016 Apple Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
+ * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
+ * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef WTF_OrderMaker_h
+#define WTF_OrderMaker_h
+
+#include <wtf/Bag.h>
+#include <wtf/HashMap.h>
+#include <wtf/Noncopyable.h>
+#include <wtf/SentinelLinkedList.h>
+
+namespace WTF {
+
+// This is a collection that is meant to be used for building up lists in a certain order. It's
+// not an efficient data structure for storing lists, but if you need to build a list by doing
+// operations like insertBefore(existingValue, newValue), then this class is a good intermediate
+// helper. Note that the type it operates on must be usable as a HashMap key.
+template<typename T>
+class OrderMaker {
+    WTF_MAKE_NONCOPYABLE(OrderMaker);
+    
+    struct Node : BasicRawSentinelNode<Node> {
+        Node(SentinelTag)
+        {
+        }
+
+        Node()
+        {
+        }
+
+        T payload;
+    };
+    
+public:
+    OrderMaker()
+    {
+    }
+
+    void prepend(T value)
+    {
+        m_list.push(newNode(value));
+    }
+
+    void append(T value)
+    {
+        m_list.append(newNode(value));
+    }
+
+    void insertBefore(T existingValue, T newValue)
+    {
+        Node* node = m_map.get(existingValue);
+        ASSERT(node);
+        node->prepend(newNode(newValue));
+    }
+    
+    void insertAfter(T existingValue, T newValue)
+    {
+        Node* node = m_map.get(existingValue);
+        ASSERT(node);
+        node->append(newNode(newValue));
+    }
+
+    class iterator {
+    public:
+        iterator()
+        {
+        }
+
+        iterator(Node* node)
+            : m_node(node)
+        {
+        }
+
+        const T& operator*()
+        {
+            return m_node->payload;
+        }
+
+        iterator& operator++()
+        {
+            m_node = m_node->next();
+            return *this;
+        }
+
+        bool operator==(const iterator& other) const
+        {
+            return m_node == other.m_node;
+        }
+
+        bool operator!=(const iterator& other) const
+        {
+            return !(*this == other);
+        }
+        
+    private:
+        Node* m_node { nullptr };
+    };
+
+    iterator begin() const { return iterator(const_cast<SentinelLinkedList<Node>&>(m_list).begin()); }
+    iterator end() const { return iterator(const_cast<SentinelLinkedList<Node>&>(m_list).end()); }
+    
+private:
+    Node* newNode(T value)
+    {
+        Node* result = m_nodes.add();
+        result->payload = value;
+        m_map.set(value, result);
+        return result;
+    }
+    
+    HashMap<T, Node*> m_map;
+    Bag<Node> m_nodes; // FIXME: We could just manually free the contents of the linked list.
+    SentinelLinkedList<Node> m_list;
+};
+
+} // namespace WTF
+
+using WTF::OrderMaker;
+
+#endif // WTF_OrderMaker_h
+
index c68ee70..072753f 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011 Apple Inc. All rights reserved.
+ * Copyright (C) 2011, 2016 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -70,6 +70,9 @@ public:
     }
     
     void remove();
+
+    void prepend(BasicRawSentinelNode*);
+    void append(BasicRawSentinelNode*);
     
 private:
     BasicRawSentinelNode* m_next;
@@ -82,8 +85,15 @@ public:
 
     SentinelLinkedList();
 
+    // Pushes to the front of the list. It's totally backwards from what you'd expect.
     void push(T*);
+
+    // Appends to the end of the list.
+    void append(T*);
+    
     static void remove(T*);
+    static void prepend(T* existingNode, T* newNode);
+    static void append(T* existingNode, T* newNode);
     
     bool isOnList(T*);
 
@@ -102,6 +112,18 @@ template <typename T> void BasicRawSentinelNode<T>::remove()
     SentinelLinkedList<T, BasicRawSentinelNode<T>>::remove(static_cast<T*>(this));
 }
 
+template <typename T> void BasicRawSentinelNode<T>::prepend(BasicRawSentinelNode* node)
+{
+    SentinelLinkedList<T, BasicRawSentinelNode<T>>::prepend(
+        static_cast<T*>(this), static_cast<T*>(node));
+}
+
+template <typename T> void BasicRawSentinelNode<T>::append(BasicRawSentinelNode* node)
+{
+    SentinelLinkedList<T, BasicRawSentinelNode<T>>::append(
+        static_cast<T*>(this), static_cast<T*>(node));
+}
+
 template <typename T, typename RawNode> inline SentinelLinkedList<T, RawNode>::SentinelLinkedList()
     : m_headSentinel(Sentinel)
     , m_tailSentinel(Sentinel)
@@ -139,6 +161,22 @@ template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNod
     next->setPrev(node);
 }
 
+template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNode>::append(T* node)
+{
+    ASSERT(node);
+    ASSERT(!node->prev());
+    ASSERT(!node->next());
+    
+    RawNode* prev = m_tailSentinel.prev();
+    RawNode* next = &m_tailSentinel;
+
+    node->setPrev(prev);
+    node->setNext(next);
+
+    prev->setNext(node);
+    next->setPrev(node);
+}
+
 template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNode>::remove(T* node)
 {
     ASSERT(node);
@@ -155,6 +193,44 @@ template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNod
     node->setNext(0);
 }
 
+template <typename T, typename RawNode>
+inline void SentinelLinkedList<T, RawNode>::prepend(T* existingNode, T* newNode)
+{
+    ASSERT(existingNode);
+    ASSERT(!!existingNode->prev());
+    ASSERT(!!existingNode->next());
+    ASSERT(newNode);
+    ASSERT(!newNode->prev());
+    ASSERT(!newNode->next());
+
+    RawNode* prev = existingNode->prev();
+
+    newNode->setNext(existingNode);
+    newNode->setPrev(prev);
+    
+    prev->setNext(newNode);
+    existingNode->setPrev(newNode);
+}
+
+template <typename T, typename RawNode>
+inline void SentinelLinkedList<T, RawNode>::append(T* existingNode, T* newNode)
+{
+    ASSERT(existingNode);
+    ASSERT(!!existingNode->prev());
+    ASSERT(!!existingNode->next());
+    ASSERT(newNode);
+    ASSERT(!newNode->prev());
+    ASSERT(!newNode->next());
+
+    RawNode* next = existingNode->next();
+
+    newNode->setNext(next);
+    newNode->setPrev(existingNode);
+    
+    next->setPrev(newNode);
+    existingNode->setNext(newNode);
+}
+
 template <typename T, typename RawNode> inline bool SentinelLinkedList<T, RawNode>::isOnList(T* node)
 {
     if (!node->isOnList())