webkitgtk-2.16.5HEADwebkitgtk-2.16.5master

1 files changed, 750 insertions, 1282 deletions

diff --git a/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp b/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp
index a4e159e73..699049b2b 100644
--- a/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp
+++ b/Source/JavaScriptCore/dfg/DFGCSEPhase.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2011, 2012, 2013 Apple Inc. All rights reserved.
+ * Copyright (C) 2011-2015 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -28,1421 +28,889 @@
 
 #if ENABLE(DFG_JIT)
 
+#include "DFGAbstractHeap.h"
+#include "DFGBlockMapInlines.h"
+#include "DFGClobberSet.h"
+#include "DFGClobberize.h"
+#include "DFGDominators.h"
 #include "DFGEdgeUsesStructure.h"
 #include "DFGGraph.h"
 #include "DFGPhase.h"
-#include "JSCellInlines.h"
+#include "JSCInlines.h"
 #include <array>
-#include <wtf/FastBitVector.h>
 
 namespace JSC { namespace DFG {
 
-enum CSEMode { NormalCSE, StoreElimination };
+// This file contains two CSE implementations: local and global. LocalCSE typically runs when we're
+// in DFG mode, i.e. we want to compile quickly. LocalCSE contains a lot of optimizations for
+// compile time. GlobalCSE, on the other hand, is fairly straight-forward. It will find more
+// optimization opportunities by virtue of being global.
 
-template<CSEMode cseMode>
-class CSEPhase : public Phase {
+namespace {
+
+const bool verbose = false;
+
+class ImpureDataSlot {
+    WTF_MAKE_NONCOPYABLE(ImpureDataSlot);
+    WTF_MAKE_FAST_ALLOCATED;
 public:
-    CSEPhase(Graph& graph)
-        : Phase(graph, cseMode == NormalCSE ? "common subexpression elimination" : "store elimination")
-    {
-    }
-    
-    bool run()
+    ImpureDataSlot(HeapLocation key, LazyNode value, unsigned hash)
+        : key(key), value(value), hash(hash)
+    { }
+
+    HeapLocation key;
+    LazyNode value;
+    unsigned hash;
+};
+
+struct ImpureDataSlotHash : public DefaultHash<std::unique_ptr<ImpureDataSlot>>::Hash {
+    static unsigned hash(const std::unique_ptr<ImpureDataSlot>& key)
     {
-        ASSERT(m_graph.m_fixpointState != BeforeFixpoint);
-        
-        m_changed = false;
-        
-        m_graph.clearReplacements();
-        
-        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
-            BasicBlock* block = m_graph.block(blockIndex);
-            if (!block)
-                continue;
-            
-            // All Phis need to already be marked as relevant to OSR.
-            if (!ASSERT_DISABLED) {
-                for (unsigned i = 0; i < block->phis.size(); ++i)
-                    ASSERT(block->phis[i]->flags() & NodeRelevantToOSR);
-            }
-            
-            for (unsigned i = block->size(); i--;) {
-                Node* node = block->at(i);
-                
-                switch (node->op()) {
-                case SetLocal:
-                case GetLocal: // FIXME: The GetLocal case is only necessary until we do https://bugs.webkit.org/show_bug.cgi?id=106707.
-                    node->mergeFlags(NodeRelevantToOSR);
-                    break;
-                default:
-                    node->clearFlags(NodeRelevantToOSR);
-                    break;
-                }
-            }
-        }
-        
-        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
-            BasicBlock* block = m_graph.block(blockIndex);
-            if (!block)
-                continue;
-            
-            for (unsigned i = block->size(); i--;) {
-                Node* node = block->at(i);
-                if (!node->containsMovHint())
-                    continue;
-                
-                ASSERT(node->op() != ZombieHint);
-                node->child1()->mergeFlags(NodeRelevantToOSR);
-            }
-        }
-        
-        if (m_graph.m_form == SSA) {
-            Vector<BasicBlock*> depthFirst;
-            m_graph.getBlocksInDepthFirstOrder(depthFirst);
-            for (unsigned i = 0; i < depthFirst.size(); ++i)
-                performBlockCSE(depthFirst[i]);
-        } else {
-            for (unsigned blockIndex = 0; blockIndex < m_graph.numBlocks(); ++blockIndex)
-                performBlockCSE(m_graph.block(blockIndex));
-        }
-        
-        return m_changed;
+        return key->hash;
     }
-    
-private:
-    
-    unsigned endIndexForPureCSE()
+
+    static bool equal(const std::unique_ptr<ImpureDataSlot>& a, const std::unique_ptr<ImpureDataSlot>& b)
     {
-        unsigned result = m_lastSeen[m_currentNode->op()];
-        if (result == UINT_MAX)
-            result = 0;
-        else
-            result++;
-        ASSERT(result <= m_indexInBlock);
-        return result;
+        // The ImpureDataSlot are unique per table per HeapLocation. This lets us compare the key
+        // by just comparing the pointers of the unique ImpureDataSlots.
+        ASSERT(a != b || a->key == b->key);
+        return a == b;
     }
+};
 
-    Node* pureCSE(Node* node)
+struct ImpureDataTranslator {
+    static unsigned hash(const HeapLocation& key)
     {
-        Edge child1 = node->child1();
-        Edge child2 = node->child2();
-        Edge child3 = node->child3();
-        
-        for (unsigned i = endIndexForPureCSE(); i--;) {
-            Node* otherNode = m_currentBlock->at(i);
-            if (otherNode == child1 || otherNode == child2 || otherNode == child3)
-                break;
-
-            if (node->op() != otherNode->op())
-                continue;
-            
-            if (node->hasArithMode()) {
-                if (node->arithMode() != otherNode->arithMode())
-                    continue;
-            }
-            
-            Edge otherChild = otherNode->child1();
-            if (!otherChild)
-                return otherNode;
-            if (otherChild != child1)
-                continue;
-            
-            otherChild = otherNode->child2();
-            if (!otherChild)
-                return otherNode;
-            if (otherChild != child2)
-                continue;
-            
-            otherChild = otherNode->child3();
-            if (!otherChild)
-                return otherNode;
-            if (otherChild != child3)
-                continue;
-            
-            return otherNode;
-        }
-        return 0;
+        return key.hash();
     }
-    
-    Node* int32ToDoubleCSE(Node* node)
+
+    static bool equal(const std::unique_ptr<ImpureDataSlot>& slot, const HeapLocation& key)
     {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* otherNode = m_currentBlock->at(i);
-            if (otherNode == node->child1())
-                return 0;
-            switch (otherNode->op()) {
-            case Int32ToDouble:
-                if (otherNode->child1() == node->child1())
-                    return otherNode;
-                break;
-            default:
-                break;
-            }
-        }
-        return 0;
+        if (!slot)
+            return false;
+        if (HashTraits<std::unique_ptr<ImpureDataSlot>>::isDeletedValue(slot))
+            return false;
+        return slot->key == key;
     }
-    
-    Node* constantCSE(Node* node)
+
+    static void translate(std::unique_ptr<ImpureDataSlot>& slot, const HeapLocation& key, unsigned hashCode)
     {
-        for (unsigned i = endIndexForPureCSE(); i--;) {
-            Node* otherNode = m_currentBlock->at(i);
-            if (otherNode->op() != JSConstant)
-                continue;
-            
-            if (otherNode->constantNumber() != node->constantNumber())
-                continue;
-            
-            return otherNode;
-        }
-        return 0;
+        new (NotNull, std::addressof(slot)) std::unique_ptr<ImpureDataSlot>(new ImpureDataSlot {key, LazyNode(), hashCode});
     }
-    
-    Node* weakConstantCSE(Node* node)
+};
+
+class ImpureMap {
+    WTF_MAKE_FAST_ALLOCATED;
+    WTF_MAKE_NONCOPYABLE(ImpureMap);
+public:
+    ImpureMap() = default;
+
+    ImpureMap(ImpureMap&& other)
     {
-        for (unsigned i = endIndexForPureCSE(); i--;) {
-            Node* otherNode = m_currentBlock->at(i);
-            if (otherNode->op() != WeakJSConstant)
-                continue;
-            
-            if (otherNode->weakConstant() != node->weakConstant())
-                continue;
-            
-            return otherNode;
-        }
-        return 0;
+        m_abstractHeapStackMap.swap(other.m_abstractHeapStackMap);
+        m_fallbackStackMap.swap(other.m_fallbackStackMap);
+        m_heapMap.swap(other.m_heapMap);
+#if !defined(NDEBUG)
+        m_debugImpureData.swap(other.m_debugImpureData);
+#endif
     }
-    
-    Node* constantStoragePointerCSE(Node* node)
+
+    const ImpureDataSlot* add(const HeapLocation& location, const LazyNode& node)
     {
-        for (unsigned i = endIndexForPureCSE(); i--;) {
-            Node* otherNode = m_currentBlock->at(i);
-            if (otherNode->op() != ConstantStoragePointer)
-                continue;
-            
-            if (otherNode->storagePointer() != node->storagePointer())
-                continue;
-            
-            return otherNode;
-        }
-        return 0;
+        const ImpureDataSlot* result = addImpl(location, node);
+
+#if !defined(NDEBUG)
+        auto addResult = m_debugImpureData.add(location, node);
+        ASSERT(!!result == !addResult.isNewEntry);
+#endif
+        return result;
     }
-    
-    Node* getCalleeLoadElimination()
+
+    LazyNode get(const HeapLocation& location) const
     {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case GetCallee:
-                return node;
-            default:
-                break;
-            }
-        }
-        return 0;
+        LazyNode result = getImpl(location);
+#if !defined(NDEBUG)
+        ASSERT(result == m_debugImpureData.get(location));
+#endif
+        return result;
     }
-    
-    Node* getArrayLengthElimination(Node* array)
+
+    void clobber(AbstractHeap heap)
     {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case GetArrayLength:
-                if (node->child1() == array)
-                    return node;
-                break;
-                
-            case PutByValDirect:
-            case PutByVal:
-                if (!m_graph.byValIsPure(node))
-                    return 0;
-                if (node->arrayMode().mayStoreToHole())
-                    return 0;
-                break;
-                
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return 0;
-            }
+        switch (heap.kind()) {
+        case World: {
+            clear();
+            break;
         }
-        return 0;
-    }
-    
-    Node* globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case GetGlobalVar:
-                if (node->registerPointer() == registerPointer)
-                    return node;
-                break;
-            case PutGlobalVar:
-                if (node->registerPointer() == registerPointer)
-                    return node->child1().node();
-                break;
-            default:
-                break;
-            }
-            if (m_graph.clobbersWorld(node))
-                break;
+        case SideState:
+            break;
+        case Stack: {
+            ASSERT(!heap.payload().isTop());
+            ASSERT(heap.payload().value() == heap.payload().value32());
+            m_abstractHeapStackMap.remove(heap.payload().value32());
+            clobber(m_fallbackStackMap, heap);
+            break;
         }
-        return 0;
-    }
-    
-    Node* scopedVarLoadElimination(Node* registers, int varNumber)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case GetClosureVar: {
-                if (node->child1() == registers && node->varNumber() == varNumber)
-                    return node;
-                break;
-            } 
-            case PutClosureVar: {
-                if (node->varNumber() != varNumber)
-                    break;
-                if (node->child2() == registers)
-                    return node->child3().node();
-                return 0;
-            }
-            case SetLocal: {
-                VariableAccessData* variableAccessData = node->variableAccessData();
-                if (variableAccessData->isCaptured()
-                    && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
-                    return 0;
-                break;
-            }
-            default:
-                break;
-            }
-            if (m_graph.clobbersWorld(node))
-                break;
+        default:
+            clobber(m_heapMap, heap);
+            break;
         }
-        return 0;
-    }
-    
-    bool varInjectionWatchpointElimination()
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node->op() == VarInjectionWatchpoint)
-                return true;
-            if (m_graph.clobbersWorld(node))
-                break;
+#if !defined(NDEBUG)
+        m_debugImpureData.removeIf([heap](const HashMap<HeapLocation, LazyNode>::KeyValuePairType& pair) -> bool {
+            return heap.overlaps(pair.key.heap());
+        });
+        ASSERT(m_debugImpureData.size()
+            == (m_heapMap.size()
+                + m_abstractHeapStackMap.size()
+                + m_fallbackStackMap.size()));
+
+        const bool verifyClobber = false;
+        if (verifyClobber) {
+            for (auto& pair : m_debugImpureData)
+                ASSERT(!!get(pair.key));
         }
-        return false;
+#endif
     }
-    
-    Node* globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
+
+    void clear()
     {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case PutGlobalVar:
-                if (node->registerPointer() == registerPointer)
-                    return node;
-                break;
-                
-            case GetGlobalVar:
-                if (node->registerPointer() == registerPointer)
-                    return 0;
-                break;
-                
-            default:
-                break;
-            }
-            if (m_graph.clobbersWorld(node) || node->canExit())
-                return 0;
-        }
-        return 0;
+        m_abstractHeapStackMap.clear();
+        m_fallbackStackMap.clear();
+        m_heapMap.clear();
+#if !defined(NDEBUG)
+        m_debugImpureData.clear();
+#endif
     }
-    
-    Node* scopedVarStoreElimination(Node* scope, Node* registers, int varNumber)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case PutClosureVar: {
-                if (node->varNumber() != varNumber)
-                    break;
-                if (node->child1() == scope && node->child2() == registers)
-                    return node;
-                return 0;
-            }
-                
-            case GetClosureVar: {
-                // Let's be conservative.
-                if (node->varNumber() == varNumber)
-                    return 0;
-                break;
-            }
-                
-            case GetLocal:
-            case SetLocal: {
-                VariableAccessData* variableAccessData = node->variableAccessData();
-                if (variableAccessData->isCaptured()
-                    && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
-                    return 0;
-                break;
-            }
 
-            default:
-                break;
-            }
-            if (m_graph.clobbersWorld(node) || node->canExit())
-                return 0;
+private:
+    typedef HashSet<std::unique_ptr<ImpureDataSlot>, ImpureDataSlotHash> Map;
+
+    const ImpureDataSlot* addImpl(const HeapLocation& location, const LazyNode& node)
+    {
+        switch (location.heap().kind()) {
+        case World:
+        case SideState:
+            RELEASE_ASSERT_NOT_REACHED();
+        case Stack: {
+            AbstractHeap abstractHeap = location.heap();
+            if (abstractHeap.payload().isTop())
+                return add(m_fallbackStackMap, location, node);
+            ASSERT(abstractHeap.payload().value() == abstractHeap.payload().value32());
+            auto addResult = m_abstractHeapStackMap.add(abstractHeap.payload().value32(), nullptr);
+            if (addResult.isNewEntry) {
+                addResult.iterator->value.reset(new ImpureDataSlot {location, node, 0});
+                return nullptr;
+            }
+            if (addResult.iterator->value->key == location)
+                return addResult.iterator->value.get();
+            return add(m_fallbackStackMap, location, node);
         }
-        return 0;
-    }
-    
-    Node* getByValLoadElimination(Node* child1, Node* child2, ArrayMode arrayMode)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1 || node == child2) 
-                break;
-
-            switch (node->op()) {
-            case GetByVal:
-                if (!m_graph.byValIsPure(node))
-                    return 0;
-                if (node->child1() == child1
-                    && node->child2() == child2
-                    && node->arrayMode().type() == arrayMode.type())
-                    return node;
-                break;
-                    
-            case PutByValDirect:
-            case PutByVal:
-            case PutByValAlias: {
-                if (!m_graph.byValIsPure(node))
-                    return 0;
-                // Typed arrays 
-                if (arrayMode.typedArrayType() != NotTypedArray)
-                    return 0;
-                if (m_graph.varArgChild(node, 0) == child1
-                    && m_graph.varArgChild(node, 1) == child2
-                    && node->arrayMode().type() == arrayMode.type())
-                    return m_graph.varArgChild(node, 2).node();
-                // We must assume that the PutByVal will clobber the location we're getting from.
-                // FIXME: We can do better; if we know that the PutByVal is accessing an array of a
-                // different type than the GetByVal, then we know that they won't clobber each other.
-                // ... except of course for typed arrays, where all typed arrays clobber all other
-                // typed arrays!  An Int32Array can alias a Float64Array for example, and so on.
-                return 0;
-            }
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return 0;
-                break;
-            }
+        default:
+            return add(m_heapMap, location, node);
         }
-        return 0;
+        return nullptr;
     }
 
-    bool checkFunctionElimination(JSCell* function, Node* child1)
+    LazyNode getImpl(const HeapLocation& location) const
     {
-        for (unsigned i = endIndexForPureCSE(); i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1) 
-                break;
-
-            if (node->op() == CheckFunction && node->child1() == child1 && node->function() == function)
-                return true;
+        switch (location.heap().kind()) {
+        case World:
+        case SideState:
+            RELEASE_ASSERT_NOT_REACHED();
+        case Stack: {
+            ASSERT(location.heap().payload().value() == location.heap().payload().value32());
+            auto iterator = m_abstractHeapStackMap.find(location.heap().payload().value32());
+            if (iterator != m_abstractHeapStackMap.end()
+                && iterator->value->key == location)
+                return iterator->value->value;
+            return get(m_fallbackStackMap, location);
         }
-        return false;
+        default:
+            return get(m_heapMap, location);
+        }
+        return LazyNode();
     }
-    
-    bool checkExecutableElimination(ExecutableBase* executable, Node* child1)
-    {
-        for (unsigned i = endIndexForPureCSE(); i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1)
-                break;
 
-            if (node->op() == CheckExecutable && node->child1() == child1 && node->executable() == executable)
-                return true;
+    static const ImpureDataSlot* add(Map& map, const HeapLocation& location, const LazyNode& node)
+    {
+        auto result = map.add<ImpureDataTranslator>(location);
+        if (result.isNewEntry) {
+            (*result.iterator)->value = node;
+            return nullptr;
         }
-        return false;
+        return result.iterator->get();
     }
 
-    bool checkStructureElimination(const StructureSet& structureSet, Node* child1)
+    static LazyNode get(const Map& map, const HeapLocation& location)
     {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1) 
-                break;
-
-            switch (node->op()) {
-            case CheckStructure:
-                if (node->child1() == child1
-                    && structureSet.isSupersetOf(node->structureSet()))
-                    return true;
-                break;
-                
-            case StructureTransitionWatchpoint:
-                if (node->child1() == child1
-                    && structureSet.contains(node->structure()))
-                    return true;
-                break;
-                
-            case PutStructure:
-                if (node->child1() == child1
-                    && structureSet.contains(node->structureTransitionData().newStructure))
-                    return true;
-                if (structureSet.contains(node->structureTransitionData().previousStructure))
-                    return false;
-                break;
-                
-            case PutByOffset:
-                // Setting a property cannot change the structure.
-                break;
-                    
-            case PutByValDirect:
-            case PutByVal:
-            case PutByValAlias:
-                if (m_graph.byValIsPure(node)) {
-                    // If PutByVal speculates that it's accessing an array with an
-                    // integer index, then it's impossible for it to cause a structure
-                    // change.
-                    break;
-                }
-                return false;
-                
-            case Arrayify:
-            case ArrayifyToStructure:
-                // We could check if the arrayification could affect our structures.
-                // But that seems like it would take Effort.
-                return false;
-                
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return false;
-                break;
-            }
-        }
-        return false;
+        auto iterator = map.find<ImpureDataTranslator>(location);
+        if (iterator != map.end())
+            return (*iterator)->value;
+        return LazyNode();
     }
-    
-    bool structureTransitionWatchpointElimination(Structure* structure, Node* child1)
+
+    static void clobber(Map& map, AbstractHeap heap)
     {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1) 
-                break;
+        map.removeIf([heap](const std::unique_ptr<ImpureDataSlot>& slot) -> bool {
+            return heap.overlaps(slot->key.heap());
+        });
+    }
 
-            switch (node->op()) {
-            case CheckStructure:
-                if (node->child1() == child1
-                    && node->structureSet().containsOnly(structure))
-                    return true;
-                break;
-                
-            case PutStructure:
-                ASSERT(node->structureTransitionData().previousStructure != structure);
-                break;
-                
-            case PutByOffset:
-                // Setting a property cannot change the structure.
-                break;
-                    
-            case PutByValDirect:
-            case PutByVal:
-            case PutByValAlias:
-                if (m_graph.byValIsPure(node)) {
-                    // If PutByVal speculates that it's accessing an array with an
-                    // integer index, then it's impossible for it to cause a structure
-                    // change.
-                    break;
-                }
-                return false;
-                
-            case StructureTransitionWatchpoint:
-                if (node->structure() == structure && node->child1() == child1)
-                    return true;
-                break;
-                
-            case Arrayify:
-            case ArrayifyToStructure:
-                // We could check if the arrayification could affect our structures.
-                // But that seems like it would take Effort.
-                return false;
-                
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return false;
-                break;
-            }
-        }
-        return false;
+    // The majority of Impure Stack Slotsare unique per value.
+    // This is very useful for fast clobber(), we can just remove the slot addressed by AbstractHeap
+    // in O(1).
+    //
+    // When there are conflict, any additional HeapLocation is added in the fallback map.
+    // This works well because fallbackStackMap remains tiny.
+    //
+    // One cannot assume a unique ImpureData is in m_abstractHeapStackMap. It may have been
+    // a duplicate in the past and now only live in m_fallbackStackMap.
+    //
+    // Obviously, TOP always goes into m_fallbackStackMap since it does not have a unique value.
+    HashMap<int32_t, std::unique_ptr<ImpureDataSlot>, DefaultHash<int32_t>::Hash, WTF::SignedWithZeroKeyHashTraits<int32_t>> m_abstractHeapStackMap;
+    Map m_fallbackStackMap;
+
+    Map m_heapMap;
+
+#if !defined(NDEBUG)
+    HashMap<HeapLocation, LazyNode> m_debugImpureData;
+#endif
+};
+
+class LocalCSEPhase : public Phase {
+public:
+    LocalCSEPhase(Graph& graph)
+        : Phase(graph, "local common subexpression elimination")
+        , m_smallBlock(graph)
+        , m_largeBlock(graph)
+    {
     }
     
-    Node* putStructureStoreElimination(Node* child1)
+    bool run()
     {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1)
-                break;
-            switch (node->op()) {
-            case CheckStructure:
-                return 0;
-                
-            case PhantomPutStructure:
-                if (node->child1() == child1) // No need to retrace our steps.
-                    return 0;
-                break;
-                
-            case PutStructure:
-                if (node->child1() == child1)
-                    return node;
-                break;
-                
-            // PutStructure needs to execute if we GC. Hence this needs to
-            // be careful with respect to nodes that GC.
-            case CreateArguments:
-            case TearOffArguments:
-            case NewFunctionNoCheck:
-            case NewFunction:
-            case NewFunctionExpression:
-            case CreateActivation:
-            case TearOffActivation:
-            case ToPrimitive:
-            case NewRegexp:
-            case NewArrayBuffer:
-            case NewArray:
-            case NewObject:
-            case CreateThis:
-            case AllocatePropertyStorage:
-            case ReallocatePropertyStorage:
-            case TypeOf:
-            case ToString:
-            case NewStringObject:
-            case MakeRope:
-            case NewTypedArray:
-                return 0;
-                
-            // This either exits, causes a GC (lazy string allocation), or clobbers
-            // the world. The chances of it not doing any of those things are so
-            // slim that we might as well not even try to reason about it.
-            case GetByVal:
-                return 0;
-                
-            case GetIndexedPropertyStorage:
-                if (node->arrayMode().getIndexedPropertyStorageMayTriggerGC())
-                    return 0;
-                break;
-                
-            default:
-                break;
-            }
-            if (m_graph.clobbersWorld(node) || node->canExit())
-                return 0;
-            if (edgesUseStructure(m_graph, node))
-                return 0;
+        ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
+        ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == LoadStore);
+        
+        bool changed = false;
+        
+        m_graph.clearReplacements();
+        
+        for (BlockIndex blockIndex = m_graph.numBlocks(); blockIndex--;) {
+            BasicBlock* block = m_graph.block(blockIndex);
+            if (!block)
+                continue;
+            
+            if (block->size() <= SmallMaps::capacity)
+                changed |= m_smallBlock.run(block);
+            else
+                changed |= m_largeBlock.run(block);
         }
-        return 0;
+        
+        return changed;
     }
     
-    Node* getByOffsetLoadElimination(unsigned identifierNumber, Node* child1)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1)
-                break;
-
-            switch (node->op()) {
-            case GetByOffset:
-                if (node->child1() == child1
-                    && m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
-                    return node;
-                break;
-                
-            case PutByOffset:
-                if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {
-                    if (node->child1() == child1) // Must be same property storage.
-                        return node->child3().node();
-                    return 0;
-                }
-                break;
-                    
-            case PutByValDirect:
-            case PutByVal:
-            case PutByValAlias:
-                if (m_graph.byValIsPure(node)) {
-                    // If PutByVal speculates that it's accessing an array with an
-                    // integer index, then it's impossible for it to cause a structure
-                    // change.
-                    break;
-                }
-                return 0;
-                
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return 0;
-                break;
-            }
+private:
+    class SmallMaps {
+    public:
+        // This permits SmallMaps to be used for blocks that have up to 100 nodes. In practice,
+        // fewer than half of the nodes in a block have pure defs, and even fewer have impure defs.
+        // Thus, a capacity limit of 100 probably means that somewhere around ~40 things may end up
+        // in one of these "small" list-based maps. That number still seems largeish, except that
+        // the overhead of HashMaps can be quite high currently: clearing them, or even removing
+        // enough things from them, deletes (or resizes) their backing store eagerly. Hence
+        // HashMaps induce a lot of malloc traffic.
+        static const unsigned capacity = 100;
+    
+        SmallMaps()
+            : m_pureLength(0)
+            , m_impureLength(0)
+        {
         }
-        return 0;
-    }
     
-    Node* putByOffsetStoreElimination(unsigned identifierNumber, Node* child1)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1)
-                break;
-
-            switch (node->op()) {
-            case GetByOffset:
-                if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
-                    return 0;
-                break;
-                
-            case PutByOffset:
-                if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {
-                    if (node->child1() == child1) // Must be same property storage.
-                        return node;
-                    return 0;
-                }
-                break;
-                    
-            case PutByValDirect:
-            case PutByVal:
-            case PutByValAlias:
-            case GetByVal:
-                if (m_graph.byValIsPure(node)) {
-                    // If PutByVal speculates that it's accessing an array with an
-                    // integer index, then it's impossible for it to cause a structure
-                    // change.
-                    break;
-                }
-                return 0;
-                
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return 0;
-                break;
-            }
-            if (node->canExit())
-                return 0;
+        void clear()
+        {
+            m_pureLength = 0;
+            m_impureLength = 0;
         }
-        return 0;
-    }
     
-    Node* getPropertyStorageLoadElimination(Node* child1)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1) 
-                break;
-
-            switch (node->op()) {
-            case GetButterfly:
-                if (node->child1() == child1)
-                    return node;
-                break;
+        void write(AbstractHeap heap)
+        {
+            if (heap.kind() == SideState)
+                return;
 
-            case AllocatePropertyStorage:
-            case ReallocatePropertyStorage:
-                // If we can cheaply prove this is a change to our object's storage, we
-                // can optimize and use its result.
-                if (node->child1() == child1)
-                    return node;
-                // Otherwise, we currently can't prove that this doesn't change our object's
-                // storage, so we conservatively assume that it may change the storage
-                // pointer of any object, including ours.
-                return 0;
-                    
-            case PutByValDirect:
-            case PutByVal:
-            case PutByValAlias:
-                if (m_graph.byValIsPure(node)) {
-                    // If PutByVal speculates that it's accessing an array with an
-                    // integer index, then it's impossible for it to cause a structure
-                    // change.
-                    break;
-                }
-                return 0;
-                
-            case Arrayify:
-            case ArrayifyToStructure:
-                // We could check if the arrayification could affect our butterfly.
-                // But that seems like it would take Effort.
-                return 0;
-                
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return 0;
-                break;
+            for (unsigned i = 0; i < m_impureLength; ++i) {
+                if (heap.overlaps(m_impureMap[i].key.heap()))
+                    m_impureMap[i--] = m_impureMap[--m_impureLength];
             }
         }
-        return 0;
-    }
     
-    bool checkArrayElimination(Node* child1, ArrayMode arrayMode)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1) 
-                break;
-
-            switch (node->op()) {
-            case CheckArray:
-                if (node->child1() == child1 && node->arrayMode() == arrayMode)
-                    return true;
-                break;
-                
-            case Arrayify:
-            case ArrayifyToStructure:
-                // We could check if the arrayification could affect our array.
-                // But that seems like it would take Effort.
-                return false;
-                
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return false;
-                break;
+        Node* addPure(PureValue value, Node* node)
+        {
+            for (unsigned i = m_pureLength; i--;) {
+                if (m_pureMap[i].key == value)
+                    return m_pureMap[i].value;
             }
+        
+            ASSERT(m_pureLength < capacity);
+            m_pureMap[m_pureLength++] = WTF::KeyValuePair<PureValue, Node*>(value, node);
+            return nullptr;
         }
-        return false;
-    }
-
-    Node* getIndexedPropertyStorageLoadElimination(Node* child1, ArrayMode arrayMode)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1) 
-                break;
-
-            switch (node->op()) {
-            case GetIndexedPropertyStorage: {
-                if (node->child1() == child1 && node->arrayMode() == arrayMode)
-                    return node;
-                break;
-            }
-
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return 0;
-                break;
+        
+        LazyNode findReplacement(HeapLocation location)
+        {
+            for (unsigned i = m_impureLength; i--;) {
+                if (m_impureMap[i].key == location)
+                    return m_impureMap[i].value;
             }
+            return nullptr;
         }
-        return 0;
-    }
     
-    Node* getTypedArrayByteOffsetLoadElimination(Node* child1)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1) 
-                break;
-
-            switch (node->op()) {
-            case GetTypedArrayByteOffset: {
-                if (node->child1() == child1)
-                    return node;
-                break;
-            }
+        LazyNode addImpure(HeapLocation location, LazyNode node)
+        {
+            // FIXME: If we are using small maps, we must not def() derived values.
+            // For now the only derived values we def() are constant-based.
+            if (location.index() && !location.index().isNode())
+                return nullptr;
+            if (LazyNode result = findReplacement(location))
+                return result;
+            ASSERT(m_impureLength < capacity);
+            m_impureMap[m_impureLength++] = WTF::KeyValuePair<HeapLocation, LazyNode>(location, node);
+            return nullptr;
+        }
+    
+    private:
+        WTF::KeyValuePair<PureValue, Node*> m_pureMap[capacity];
+        WTF::KeyValuePair<HeapLocation, LazyNode> m_impureMap[capacity];
+        unsigned m_pureLength;
+        unsigned m_impureLength;
+    };
 
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return 0;
-                break;
-            }
+    class LargeMaps {
+    public:
+        LargeMaps()
+        {
         }
-        return 0;
-    }
     
-    Node* getMyScopeLoadElimination()
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case CreateActivation:
-                // This may cause us to return a different scope.
-                return 0;
-            case GetMyScope:
-                return node;
-            default:
-                break;
-            }
+        void clear()
+        {
+            m_pureMap.clear();
+            m_impureMap.clear();
         }
-        return 0;
-    }
     
-    Node* getLocalLoadElimination(VirtualRegister local, Node*& relevantLocalOp, bool careAboutClobbering)
-    {
-        relevantLocalOp = 0;
+        void write(AbstractHeap heap)
+        {
+            m_impureMap.clobber(heap);
+        }
+    
+        Node* addPure(PureValue value, Node* node)
+        {
+            auto result = m_pureMap.add(value, node);
+            if (result.isNewEntry)
+                return nullptr;
+            return result.iterator->value;
+        }
         
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case GetLocal:
-                if (node->local() == local) {
-                    relevantLocalOp = node;
-                    return node;
-                }
-                break;
-                
-            case GetLocalUnlinked:
-                if (node->unlinkedLocal() == local) {
-                    relevantLocalOp = node;
-                    return node;
-                }
-                break;
-                
-            case SetLocal:
-                if (node->local() == local) {
-                    relevantLocalOp = node;
-                    return node->child1().node();
+        LazyNode findReplacement(HeapLocation location)
+        {
+            return m_impureMap.get(location);
+        }
+    
+        LazyNode addImpure(const HeapLocation& location, const LazyNode& node)
+        {
+            if (const ImpureDataSlot* slot = m_impureMap.add(location, node))
+                return slot->value;
+            return LazyNode();
+        }
+
+    private:
+        HashMap<PureValue, Node*> m_pureMap;
+        ImpureMap m_impureMap;
+    };
+
+    template<typename Maps>
+    class BlockCSE {
+    public:
+        BlockCSE(Graph& graph)
+            : m_graph(graph)
+            , m_insertionSet(graph)
+        {
+        }
+    
+        bool run(BasicBlock* block)
+        {
+            m_maps.clear();
+            m_changed = false;
+            m_block = block;
+        
+            for (unsigned nodeIndex = 0; nodeIndex < block->size(); ++nodeIndex) {
+                m_node = block->at(nodeIndex);
+                m_graph.performSubstitution(m_node);
+            
+                if (m_node->op() == Identity) {
+                    m_node->replaceWith(m_node->child1().node());
+                    m_changed = true;
+                } else {
+                    // This rule only makes sense for local CSE, since in SSA form we have already
+                    // factored the bounds check out of the PutByVal. It's kind of gross, but we
+                    // still have reason to believe that PutByValAlias is a good optimization and
+                    // that it's better to do it with a single node rather than separating out the
+                    // CheckInBounds.
+                    if (m_node->op() == PutByVal || m_node->op() == PutByValDirect) {
+                        HeapLocation heap;
+                        
+                        Node* base = m_graph.varArgChild(m_node, 0).node();
+                        Node* index = m_graph.varArgChild(m_node, 1).node();
+                        
+                        ArrayMode mode = m_node->arrayMode();
+                        switch (mode.type()) {
+                        case Array::Int32:
+                            if (!mode.isInBounds())
+                                break;
+                            heap = HeapLocation(
+                                IndexedPropertyLoc, IndexedInt32Properties, base, index);
+                            break;
+                            
+                        case Array::Double:
+                            if (!mode.isInBounds())
+                                break;
+                            heap = HeapLocation(
+                                IndexedPropertyLoc, IndexedDoubleProperties, base, index);
+                            break;
+                            
+                        case Array::Contiguous:
+                            if (!mode.isInBounds())
+                                break;
+                            heap = HeapLocation(
+                                IndexedPropertyLoc, IndexedContiguousProperties, base, index);
+                            break;
+                            
+                        case Array::Int8Array:
+                        case Array::Int16Array:
+                        case Array::Int32Array:
+                        case Array::Uint8Array:
+                        case Array::Uint8ClampedArray:
+                        case Array::Uint16Array:
+                        case Array::Uint32Array:
+                        case Array::Float32Array:
+                        case Array::Float64Array:
+                            if (!mode.isInBounds())
+                                break;
+                            heap = HeapLocation(
+                                IndexedPropertyLoc, TypedArrayProperties, base, index);
+                            break;
+                            
+                        default:
+                            break;
+                        }
+
+                        if (!!heap && m_maps.findReplacement(heap))
+                            m_node->setOp(PutByValAlias);
+                    }
+
+                    clobberize(m_graph, m_node, *this);
                 }
-                break;
-                
-            case GetClosureVar:
-            case PutClosureVar:
-                if (static_cast<VirtualRegister>(node->varNumber()) == local)
-                    return 0;
-                break;
-                
-            default:
-                if (careAboutClobbering && m_graph.clobbersWorld(node))
-                    return 0;
-                break;
             }
+
+            m_insertionSet.execute(block);
+        
+            return m_changed;
         }
-        return 0;
-    }
     
-    struct SetLocalStoreEliminationResult {
-        SetLocalStoreEliminationResult()
-            : mayBeAccessed(false)
-            , mayExit(false)
-            , mayClobberWorld(false)
+        void read(AbstractHeap) { }
+    
+        void write(AbstractHeap heap)
         {
+            m_maps.write(heap);
         }
         
-        bool mayBeAccessed;
-        bool mayExit;
-        bool mayClobberWorld;
-    };
-    SetLocalStoreEliminationResult setLocalStoreElimination(
-        VirtualRegister local, Node* expectedNode)
-    {
-        SetLocalStoreEliminationResult result;
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case GetLocal:
-            case Flush:
-                if (node->local() == local)
-                    result.mayBeAccessed = true;
-                break;
-                
-            case GetLocalUnlinked:
-                if (node->unlinkedLocal() == local)
-                    result.mayBeAccessed = true;
-                break;
-                
-            case SetLocal: {
-                if (node->local() != local)
-                    break;
-                if (node != expectedNode)
-                    result.mayBeAccessed = true;
-                return result;
+        void def(PureValue value)
+        {
+            Node* match = m_maps.addPure(value, m_node);
+            if (!match)
+                return;
+
+            m_node->replaceWith(match);
+            m_changed = true;
+        }
+    
+        void def(const HeapLocation& location, const LazyNode& value)
+        {
+            LazyNode match = m_maps.addImpure(location, value);
+            if (!match)
+                return;
+        
+            if (m_node->op() == GetLocal) {
+                // Usually the CPS rethreading phase does this. But it's OK for us to mess with
+                // locals so long as:
+                // 
+                // - We dethread the graph. Any changes we make may invalidate the assumptions of
+                //   our CPS form, particularly if this GetLocal is linked to the variablesAtTail.
+                //
+                // - We don't introduce a Phantom for the child of the GetLocal. This wouldn't be
+                //   totally wrong but it would pessimize the code. Just because there is a
+                //   GetLocal doesn't mean that the child was live. Simply rerouting the all uses
+                //   of this GetLocal will preserve the live-at-exit information just fine.
+                //
+                // We accomplish the latter by just clearing the child; then the Phantom that we
+                // introduce won't have children and so it will eventually just be deleted.
+            
+                m_node->child1() = Edge();
+                m_graph.dethread();
             }
-                
-            case GetClosureVar:
-            case PutClosureVar:
-                if (static_cast<VirtualRegister>(node->varNumber()) == local)
-                    result.mayBeAccessed = true;
-                break;
-                
-            case GetMyScope:
-            case SkipTopScope:
-                if (node->codeOrigin.inlineCallFrame)
-                    break;
-                if (m_graph.uncheckedActivationRegister() == local)
-                    result.mayBeAccessed = true;
-                break;
-                
-            case CheckArgumentsNotCreated:
-            case GetMyArgumentsLength:
-            case GetMyArgumentsLengthSafe:
-                if (m_graph.uncheckedArgumentsRegisterFor(node->codeOrigin) == local)
-                    result.mayBeAccessed = true;
-                break;
-                
-            case GetMyArgumentByVal:
-            case GetMyArgumentByValSafe:
-                result.mayBeAccessed = true;
-                break;
-                
-            case GetByVal:
-                // If this is accessing arguments then it's potentially accessing locals.
-                if (node->arrayMode().type() == Array::Arguments)
-                    result.mayBeAccessed = true;
-                break;
-                
-            case CreateArguments:
-            case TearOffActivation:
-            case TearOffArguments:
-                // If an activation is being torn off then it means that captured variables
-                // are live. We could be clever here and check if the local qualifies as an
-                // argument register. But that seems like it would buy us very little since
-                // any kind of tear offs are rare to begin with.
-                result.mayBeAccessed = true;
-                break;
-                
-            default:
-                break;
+        
+            if (value.isNode() && value.asNode() == m_node) {
+                match.ensureIsNode(m_insertionSet, m_block, 0)->owner = m_block;
+                ASSERT(match.isNode());
+                m_node->replaceWith(match.asNode());
+                m_changed = true;
             }
-            result.mayExit |= node->canExit();
-            result.mayClobberWorld |= m_graph.clobbersWorld(node);
         }
-        RELEASE_ASSERT_NOT_REACHED();
-        // Be safe in release mode.
-        result.mayBeAccessed = true;
-        return result;
-    }
     
-    void eliminateIrrelevantPhantomChildren(Node* node)
+    private:
+        Graph& m_graph;
+        
+        bool m_changed;
+        Node* m_node;
+        BasicBlock* m_block;
+    
+        Maps m_maps;
+
+        InsertionSet m_insertionSet;
+    };
+
+    BlockCSE<SmallMaps> m_smallBlock;
+    BlockCSE<LargeMaps> m_largeBlock;
+};
+
+class GlobalCSEPhase : public Phase {
+public:
+    GlobalCSEPhase(Graph& graph)
+        : Phase(graph, "global common subexpression elimination")
+        , m_impureDataMap(graph)
+        , m_insertionSet(graph)
     {
-        ASSERT(node->op() == Phantom);
-        for (unsigned i = 0; i < AdjacencyList::Size; ++i) {
-            Edge edge = node->children.child(i);
-            if (!edge)
-                continue;
-            if (edge.useKind() != UntypedUse)
-                continue; // Keep the type check.
-            if (edge->flags() & NodeRelevantToOSR)
-                continue;
-            
-            node->children.removeEdge(i--);
-            m_changed = true;
-        }
     }
     
-    bool setReplacement(Node* replacement)
+    bool run()
     {
-        if (!replacement)
-            return false;
+        ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
+        ASSERT(m_graph.m_form == SSA);
         
-        m_currentNode->convertToPhantom();
-        eliminateIrrelevantPhantomChildren(m_currentNode);
+        m_graph.initializeNodeOwners();
+        m_graph.ensureDominators();
         
-        // At this point we will eliminate all references to this node.
-        m_currentNode->misc.replacement = replacement;
+        m_preOrder = m_graph.blocksInPreOrder();
         
-        m_changed = true;
+        // First figure out what gets clobbered by blocks. Node that this uses the preOrder list
+        // for convenience only.
+        for (unsigned i = m_preOrder.size(); i--;) {
+            m_block = m_preOrder[i];
+            m_impureData = &m_impureDataMap[m_block];
+            for (unsigned nodeIndex = m_block->size(); nodeIndex--;)
+                addWrites(m_graph, m_block->at(nodeIndex), m_impureData->writes);
+        }
         
-        return true;
-    }
-    
-    void eliminate()
-    {
-        ASSERT(m_currentNode->mustGenerate());
-        m_currentNode->convertToPhantom();
-        eliminateIrrelevantPhantomChildren(m_currentNode);
+        // Based on my experience doing this before, what follows might have to be made iterative.
+        // Right now it doesn't have to be iterative because everything is dominator-bsed. But when
+        // validation is enabled, we check if iterating would find new CSE opportunities.
+
+        bool changed = iterate();
         
-        m_changed = true;
-    }
-    
-    void eliminate(Node* node, NodeType phantomType = Phantom)
-    {
-        if (!node)
-            return;
-        ASSERT(node->mustGenerate());
-        node->setOpAndDefaultFlags(phantomType);
-        if (phantomType == Phantom)
-            eliminateIrrelevantPhantomChildren(node);
+        // FIXME: It should be possible to assert that CSE will not find any new opportunities if you
+        // run it a second time. Unfortunately, we cannot assert this right now. Note that if we did
+        // this, we'd have to first reset all of our state.
+        // https://bugs.webkit.org/show_bug.cgi?id=145853
         
-        m_changed = true;
+        return changed;
     }
     
-    void performNodeCSE(Node* node)
+    bool iterate()
     {
-        if (cseMode == NormalCSE)
-            m_graph.performSubstitution(node);
+        if (verbose)
+            dataLog("Performing iteration.\n");
         
-        switch (node->op()) {
+        m_changed = false;
+        m_graph.clearReplacements();
         
-        case Identity:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(node->child1().node());
-            break;
-            
-        // Handle the pure nodes. These nodes never have any side-effects.
-        case BitAnd:
-        case BitOr:
-        case BitXor:
-        case BitRShift:
-        case BitLShift:
-        case BitURShift:
-        case ArithAdd:
-        case ArithSub:
-        case ArithNegate:
-        case ArithMul:
-        case ArithMod:
-        case ArithDiv:
-        case ArithAbs:
-        case ArithMin:
-        case ArithMax:
-        case ArithSqrt:
-        case ArithSin:
-        case ArithCos:
-        case StringCharAt:
-        case StringCharCodeAt:
-        case IsUndefined:
-        case IsBoolean:
-        case IsNumber:
-        case IsString:
-        case IsObject:
-        case IsFunction:
-        case DoubleAsInt32:
-        case LogicalNot:
-        case SkipTopScope:
-        case SkipScope:
-        case GetClosureRegisters:
-        case GetScope:
-        case TypeOf:
-        case CompareEqConstant:
-        case ValueToInt32:
-        case MakeRope:
-        case Int52ToDouble:
-        case Int52ToValue:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(pureCSE(node));
-            break;
-            
-        case Int32ToDouble:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(int32ToDoubleCSE(node));
-            break;
+        for (unsigned i = 0; i < m_preOrder.size(); ++i) {
+            m_block = m_preOrder[i];
+            m_impureData = &m_impureDataMap[m_block];
+            m_writesSoFar.clear();
             
-        case GetCallee:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(getCalleeLoadElimination());
-            break;
+            if (verbose)
+                dataLog("Processing block ", *m_block, ":\n");
 
-        case GetLocal: {
-            if (cseMode == StoreElimination)
-                break;
-            VariableAccessData* variableAccessData = node->variableAccessData();
-            if (!variableAccessData->isCaptured())
-                break;
-            Node* relevantLocalOp;
-            Node* possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp, variableAccessData->isCaptured());
-            if (!relevantLocalOp)
-                break;
-            if (relevantLocalOp->op() != GetLocalUnlinked
-                && relevantLocalOp->variableAccessData() != variableAccessData)
-                break;
-            Node* phi = node->child1().node();
-            if (!setReplacement(possibleReplacement))
-                break;
-            
-            m_graph.dethread();
-            
-            // If we replace a GetLocal with a GetLocalUnlinked, then turn the GetLocalUnlinked
-            // into a GetLocal.
-            if (relevantLocalOp->op() == GetLocalUnlinked)
-                relevantLocalOp->convertToGetLocal(variableAccessData, phi);
-
-            m_changed = true;
-            break;
-        }
-            
-        case GetLocalUnlinked: {
-            if (cseMode == StoreElimination)
-                break;
-            Node* relevantLocalOpIgnored;
-            setReplacement(getLocalLoadElimination(node->unlinkedLocal(), relevantLocalOpIgnored, true));
-            break;
-        }
-            
-        case Flush: {
-            if (m_graph.m_form == SSA) {
-                // FIXME: Enable Flush store elimination in SSA form.
-                // https://bugs.webkit.org/show_bug.cgi?id=125429
-                break;
-            }
-            VariableAccessData* variableAccessData = node->variableAccessData();
-            VirtualRegister local = variableAccessData->local();
-            Node* replacement = node->child1().node();
-            if (replacement->op() != SetLocal)
-                break;
-            ASSERT(replacement->variableAccessData() == variableAccessData);
-            // FIXME: We should be able to remove SetLocals that can exit; we just need
-            // to replace them with appropriate type checks.
-            if (cseMode == NormalCSE) {
-                // Need to be conservative at this time; if the SetLocal has any chance of performing
-                // any speculations then we cannot do anything.
-                FlushFormat format = variableAccessData->flushFormat();
-                ASSERT(format != DeadFlush);
-                if (format != FlushedJSValue)
-                    break;
-            } else {
-                if (replacement->canExit())
-                    break;
+            for (unsigned nodeIndex = 0; nodeIndex < m_block->size(); ++nodeIndex) {
+                m_nodeIndex = nodeIndex;
+                m_node = m_block->at(nodeIndex);
+                if (verbose)
+                    dataLog("  Looking at node ", m_node, ":\n");
+                
+                m_graph.performSubstitution(m_node);
+                
+                if (m_node->op() == Identity) {
+                    m_node->replaceWith(m_node->child1().node());
+                    m_changed = true;
+                } else
+                    clobberize(m_graph, m_node, *this);
             }
-            SetLocalStoreEliminationResult result =
-                setLocalStoreElimination(local, replacement);
-            if (result.mayBeAccessed || result.mayClobberWorld)
-                break;
-            ASSERT(replacement->op() == SetLocal);
-            // FIXME: Investigate using mayExit as a further optimization.
-            node->convertToPhantom();
-            Node* dataNode = replacement->child1().node();
-            ASSERT(dataNode->hasResult());
-            node->child1() = Edge(dataNode);
-            m_graph.dethread();
-            m_changed = true;
-            break;
-        }
-            
-        case JSConstant:
-            if (cseMode == StoreElimination)
-                break;
-            // This is strange, but necessary. Some phases will convert nodes to constants,
-            // which may result in duplicated constants. We use CSE to clean this up.
-            setReplacement(constantCSE(node));
-            break;
-            
-        case WeakJSConstant:
-            if (cseMode == StoreElimination)
-                break;
-            // FIXME: have CSE for weak constants against strong constants and vice-versa.
-            setReplacement(weakConstantCSE(node));
-            break;
-            
-        case ConstantStoragePointer:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(constantStoragePointerCSE(node));
-            break;
-            
-        case GetArrayLength:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(getArrayLengthElimination(node->child1().node()));
-            break;
 
-        case GetMyScope:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(getMyScopeLoadElimination());
-            break;
-            
-        // Handle nodes that are conditionally pure: these are pure, and can
-        // be CSE'd, so long as the prediction is the one we want.
-        case CompareLess:
-        case CompareLessEq:
-        case CompareGreater:
-        case CompareGreaterEq:
-        case CompareEq: {
-            if (cseMode == StoreElimination)
-                break;
-            if (m_graph.isPredictedNumerical(node)) {
-                Node* replacement = pureCSE(node);
-                if (replacement && m_graph.isPredictedNumerical(replacement))
-                    setReplacement(replacement);
-            }
-            break;
-        }
+            m_insertionSet.execute(m_block);
             
-        // Finally handle heap accesses. These are not quite pure, but we can still
-        // optimize them provided that some subtle conditions are met.
-        case GetGlobalVar:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(globalVarLoadElimination(node->registerPointer()));
-            break;
-
-        case GetClosureVar: {
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(scopedVarLoadElimination(node->child1().node(), node->varNumber()));
-            break;
+            m_impureData->didVisit = true;
         }
+        
+        return m_changed;
+    }
 
-        case VarInjectionWatchpoint:
-            if (cseMode == StoreElimination)
-                break;
-            if (varInjectionWatchpointElimination())
-                eliminate();
-            break;
-            
-        case PutGlobalVar:
-            if (cseMode == NormalCSE)
-                break;
-            eliminate(globalVarStoreElimination(node->registerPointer()));
-            break;
-            
-        case PutClosureVar: {
-            if (cseMode == NormalCSE)
-                break;
-            eliminate(scopedVarStoreElimination(node->child1().node(), node->child2().node(), node->varNumber()));
-            break;
+    void read(AbstractHeap) { }
+    
+    void write(AbstractHeap heap)
+    {
+        m_impureData->availableAtTail.clobber(heap);
+        m_writesSoFar.add(heap);
+    }
+    
+    void def(PureValue value)
+    {
+        // With pure values we do not have to worry about the possibility of some control flow path
+        // clobbering the value. So, we just search for all of the like values that have been
+        // computed. We pick one that is in a block that dominates ours. Note that this means that
+        // a PureValue will map to a list of nodes, since there may be many places in the control
+        // flow graph that compute a value but only one of them that dominates us. We may build up
+        // a large list of nodes that compute some value in the case of gnarly control flow. This
+        // is probably OK.
+        
+        auto result = m_pureValues.add(value, Vector<Node*>());
+        if (result.isNewEntry) {
+            result.iterator->value.append(m_node);
+            return;
         }
-
-        case GetByVal:
-            if (cseMode == StoreElimination)
-                break;
-            if (m_graph.byValIsPure(node))
-                setReplacement(getByValLoadElimination(node->child1().node(), node->child2().node(), node->arrayMode()));
-            break;
-                
-        case PutByValDirect:
-        case PutByVal: {
-            if (cseMode == StoreElimination)
-                break;
-            Edge child1 = m_graph.varArgChild(node, 0);
-            Edge child2 = m_graph.varArgChild(node, 1);
-            if (node->arrayMode().canCSEStorage()) {
-                Node* replacement = getByValLoadElimination(child1.node(), child2.node(), node->arrayMode());
-                if (!replacement)
-                    break;
-                node->setOp(PutByValAlias);
+        
+        for (unsigned i = result.iterator->value.size(); i--;) {
+            Node* candidate = result.iterator->value[i];
+            if (m_graph.m_dominators->dominates(candidate->owner, m_block)) {
+                m_node->replaceWith(candidate);
+                m_changed = true;
+                return;
             }
-            break;
         }
-            
-        case CheckStructure:
-            if (cseMode == StoreElimination)
-                break;
-            if (checkStructureElimination(node->structureSet(), node->child1().node()))
-                eliminate();
-            break;
-            
-        case StructureTransitionWatchpoint:
-            if (cseMode == StoreElimination)
-                break;
-            if (structureTransitionWatchpointElimination(node->structure(), node->child1().node()))
-                eliminate();
-            break;
-            
-        case PutStructure:
-            if (cseMode == NormalCSE)
-                break;
-            eliminate(putStructureStoreElimination(node->child1().node()), PhantomPutStructure);
-            break;
-
-        case CheckFunction:
-            if (cseMode == StoreElimination)
-                break;
-            if (checkFunctionElimination(node->function(), node->child1().node()))
-                eliminate();
-            break;
-                
-        case CheckExecutable:
-            if (cseMode == StoreElimination)
-                break;
-            if (checkExecutableElimination(node->executable(), node->child1().node()))
-                eliminate();
-            break;
-                
-        case CheckArray:
-            if (cseMode == StoreElimination)
-                break;
-            if (checkArrayElimination(node->child1().node(), node->arrayMode()))
-                eliminate();
-            break;
-            
-        case GetIndexedPropertyStorage: {
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(getIndexedPropertyStorageLoadElimination(node->child1().node(), node->arrayMode()));
-            break;
+        
+        result.iterator->value.append(m_node);
+    }
+    
+    LazyNode findReplacement(HeapLocation location)
+    {
+        // At this instant, our "availableAtTail" reflects the set of things that are available in
+        // this block so far. We check this map to find block-local CSE opportunities before doing
+        // a global search.
+        LazyNode match = m_impureData->availableAtTail.get(location);
+        if (!!match) {
+            if (verbose)
+                dataLog("      Found local match: ", match, "\n");
+            return match;
         }
-            
-        case GetTypedArrayByteOffset: {
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(getTypedArrayByteOffsetLoadElimination(node->child1().node()));
-            break;
+        
+        // If it's not available at this point in the block, and at some prior point in the block
+        // we have clobbered this heap location, then there is no point in doing a global search.
+        if (m_writesSoFar.overlaps(location.heap())) {
+            if (verbose)
+                dataLog("      Not looking globally because of local clobber: ", m_writesSoFar, "\n");
+            return nullptr;
         }
-
-        case GetButterfly:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(getPropertyStorageLoadElimination(node->child1().node()));
-            break;
-
-        case GetByOffset:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child1().node()));
-            break;
-            
-        case PutByOffset:
-            if (cseMode == NormalCSE)
-                break;
-            eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber, node->child1().node()));
-            break;
-            
-        case Phantom:
-            // FIXME: we ought to remove Phantom's that have no children.
+        
+        // This perfoms a backward search over the control flow graph to find some possible
+        // non-local def() that matches our heap location. Such a match is only valid if there does
+        // not exist any path from that def() to our block that contains a write() that overlaps
+        // our heap. This algorithm looks for both of these things (the matching def and the
+        // overlapping writes) in one backwards DFS pass.
+        //
+        // This starts by looking at the starting block's predecessors, and then it continues along
+        // their predecessors. As soon as this finds a possible def() - one that defines the heap
+        // location we want while dominating our starting block - it assumes that this one must be
+        // the match. It then lets the DFS over predecessors complete, but it doesn't add the
+        // def()'s predecessors; this ensures that any blocks we visit thereafter are on some path
+        // from the def() to us. As soon as the DFG finds a write() that overlaps the location's
+        // heap, it stops, assuming that there is no possible match. Note that the write() case may
+        // trigger before we find a def(), or after. Either way, the write() case causes this
+        // function to immediately return nullptr.
+        //
+        // If the write() is found before we find the def(), then we know that any def() we would
+        // find would have a path to us that trips over the write() and hence becomes invalid. This
+        // is just a direct outcome of us looking for a def() that dominates us. Given a block A
+        // that dominates block B - so that A is the one that would have the def() and B is our
+        // starting block - we know that any other block must either be on the path from A to B, or
+        // it must be on a path from the root to A, but not both. So, if we haven't found A yet but
+        // we already have found a block C that has a write(), then C must be on some path from A
+        // to B, which means that A's def() is invalid for our purposes. Hence, before we find the
+        // def(), stopping on write() is the right thing to do.
+        //
+        // Stopping on write() is also the right thing to do after we find the def(). After we find
+        // the def(), we don't add that block's predecessors to the search worklist. That means
+        // that henceforth the only blocks we will see in the search are blocks on the path from
+        // the def() to us. If any such block has a write() that clobbers our heap then we should
+        // give up.
+        //
+        // Hence this graph search algorithm ends up being deceptively simple: any overlapping
+        // write() causes us to immediately return nullptr, and a matching def() means that we just
+        // record it and neglect to visit its precessors.
+        
+        Vector<BasicBlock*, 8> worklist;
+        Vector<BasicBlock*, 8> seenList;
+        BitVector seen;
+        
+        for (unsigned i = m_block->predecessors.size(); i--;) {
+            BasicBlock* predecessor = m_block->predecessors[i];
+            if (!seen.get(predecessor->index)) {
+                worklist.append(predecessor);
+                seen.set(predecessor->index);
+            }
+        }
+        
+        while (!worklist.isEmpty()) {
+            BasicBlock* block = worklist.takeLast();
+            seenList.append(block);
+            
+            if (verbose)
+                dataLog("      Searching in block ", *block, "\n");
+            ImpureBlockData& data = m_impureDataMap[block];
+            
+            // We require strict domination because this would only see things in our own block if
+            // they came *after* our position in the block. Clearly, while our block dominates
+            // itself, the things in the block after us don't dominate us.
+            if (m_graph.m_dominators->strictlyDominates(block, m_block)) {
+                if (verbose)
+                    dataLog("        It strictly dominates.\n");
+                DFG_ASSERT(m_graph, m_node, data.didVisit);
+                DFG_ASSERT(m_graph, m_node, !match);
+                match = data.availableAtTail.get(location);
+                if (verbose)
+                    dataLog("        Availability: ", match, "\n");
+                if (!!match) {
+                    // Don't examine the predecessors of a match. At this point we just want to
+                    // establish that other blocks on the path from here to there don't clobber
+                    // the location we're interested in.
+                    continue;
+                }
+            }
             
-            eliminateIrrelevantPhantomChildren(node);
-            break;
+            if (verbose)
+                dataLog("        Dealing with write set ", data.writes, "\n");
+            if (data.writes.overlaps(location.heap())) {
+                if (verbose)
+                    dataLog("        Clobbered.\n");
+                return nullptr;
+            }
             
-        default:
-            // do nothing.
-            break;
+            for (unsigned i = block->predecessors.size(); i--;) {
+                BasicBlock* predecessor = block->predecessors[i];
+                if (!seen.get(predecessor->index)) {
+                    worklist.append(predecessor);
+                    seen.set(predecessor->index);
+                }
+            }
         }
         
-        m_lastSeen[node->op()] = m_indexInBlock;
+        if (!match)
+            return nullptr;
+        
+        // Cache the results for next time. We cache them both for this block and for all of our
+        // predecessors, since even though we've already visited our predecessors, our predecessors
+        // probably have successors other than us.
+        // FIXME: Consider caching failed searches as well, when match is null. It's not clear that
+        // the reduction in compile time would warrant the increase in complexity, though.
+        // https://bugs.webkit.org/show_bug.cgi?id=134876
+        for (BasicBlock* block : seenList)
+            m_impureDataMap[block].availableAtTail.add(location, match);
+        m_impureData->availableAtTail.add(location, match);
+        
+        return match;
     }
     
-    void performBlockCSE(BasicBlock* block)
+    void def(HeapLocation location, LazyNode value)
     {
-        if (!block)
-            return;
-        if (!block->isReachable)
-            return;
+        if (verbose)
+            dataLog("    Got heap location def: ", location, " -> ", value, "\n");
         
-        m_currentBlock = block;
-        for (unsigned i = 0; i < LastNodeType; ++i)
-            m_lastSeen[i] = UINT_MAX;
+        LazyNode match = findReplacement(location);
         
-        for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
-            m_currentNode = block->at(m_indexInBlock);
-            performNodeCSE(m_currentNode);
-        }
+        if (verbose)
+            dataLog("      Got match: ", match, "\n");
         
-        if (!ASSERT_DISABLED && cseMode == StoreElimination) {
-            // Nobody should have replacements set.
-            for (unsigned i = 0; i < block->size(); ++i)
-                ASSERT(!block->at(i)->misc.replacement);
+        if (!match) {
+            if (verbose)
+                dataLog("      Adding at-tail mapping: ", location, " -> ", value, "\n");
+            auto result = m_impureData->availableAtTail.add(location, value);
+            ASSERT_UNUSED(result, !result);
+            return;
+        }
+
+        if (value.isNode() && value.asNode() == m_node) {
+            if (!match.isNode()) {
+                // We need to properly record the constant in order to use an existing one if applicable.
+                // This ensures that re-running GCSE will not find new optimizations.
+                match.ensureIsNode(m_insertionSet, m_block, m_nodeIndex)->owner = m_block;
+                auto result = m_pureValues.add(PureValue(match.asNode(), match->constant()), Vector<Node*>());
+                bool replaced = false;
+                if (!result.isNewEntry) {
+                    for (unsigned i = result.iterator->value.size(); i--;) {
+                        Node* candidate = result.iterator->value[i];
+                        if (m_graph.m_dominators->dominates(candidate->owner, m_block)) {
+                            ASSERT(candidate);
+                            match->replaceWith(candidate);
+                            match.setNode(candidate);
+                            replaced = true;
+                            break;
+                        }
+                    }
+                }
+                if (!replaced)
+                    result.iterator->value.append(match.asNode());
+            }
+            ASSERT(match.asNode());
+            m_node->replaceWith(match.asNode());
+            m_changed = true;
         }
     }
     
-    BasicBlock* m_currentBlock;
-    Node* m_currentNode;
-    unsigned m_indexInBlock;
-    std::array<unsigned, LastNodeType> m_lastSeen;
-    bool m_changed; // Only tracks changes that have a substantive effect on other optimizations.
+    struct ImpureBlockData {
+        ImpureBlockData()
+            : didVisit(false)
+        {
+        }
+        
+        ClobberSet writes;
+        ImpureMap availableAtTail;
+        bool didVisit;
+    };
+    
+    Vector<BasicBlock*> m_preOrder;
+
+    PureMultiMap m_pureValues;
+    BlockMap<ImpureBlockData> m_impureDataMap;
+    
+    BasicBlock* m_block;
+    Node* m_node;
+    unsigned m_nodeIndex;
+    ImpureBlockData* m_impureData;
+    ClobberSet m_writesSoFar;
+    InsertionSet m_insertionSet;
+    
+    bool m_changed;
 };
 
-bool performCSE(Graph& graph)
+} // anonymous namespace
+
+bool performLocalCSE(Graph& graph)
 {
-    SamplingRegion samplingRegion("DFG CSE Phase");
-    return runPhase<CSEPhase<NormalCSE>>(graph);
+    return runPhase<LocalCSEPhase>(graph);
 }
 
-bool performStoreElimination(Graph& graph)
+bool performGlobalCSE(Graph& graph)
 {
-    SamplingRegion samplingRegion("DFG Store Elimination Phase");
-    return runPhase<CSEPhase<StoreElimination>>(graph);
+    return runPhase<GlobalCSEPhase>(graph);
 }
 
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
-
-