JavaScriptCore-7601.1.46.3.tar.gz

[apple/javascriptcore.git] / dfg / DFGCSEPhase.cpp

diff --git a/dfg/DFGCSEPhase.cpp b/dfg/DFGCSEPhase.cpp
index d4e1023d048c99998e342cb6540cd51da61e89a2..a3b8676166d1da3fe188bfd73828dc82c5ab2e5f 100644 (file)
--- a/dfg/DFGCSEPhase.cpp
+++ b/dfg/DFGCSEPhase.cpp
@@ -1,5 +1,5 @@
 /*
 /*

- * Copyright (C) 2011, 2012, 2013, 2014 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
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions


@@ -29,6 +29,8 @@
 #if ENABLE(DFG_JIT)
 
 #include "DFGAbstractHeap.h"
 #if ENABLE(DFG_JIT)
 
 #include "DFGAbstractHeap.h"

+#include "DFGBlockMapInlines.h"
+#include "DFGClobberSet.h"

 #include "DFGClobberize.h"
 #include "DFGEdgeUsesStructure.h"
 #include "DFGGraph.h"
 #include "DFGClobberize.h"
 #include "DFGEdgeUsesStructure.h"
 #include "DFGGraph.h"


@@ -39,21 +41,52 @@
 
 namespace JSC { namespace DFG {
 
 
 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 ClobberFilter {

 public:
 public:

-    CSEPhase(Graph& graph)
-        : Phase(graph, cseMode == NormalCSE ? "common subexpression elimination" : "store elimination")
+    ClobberFilter(AbstractHeap heap)
+        : m_heap(heap)
+    {
+    }
+    
+    bool operator()(const ImpureMap::KeyValuePairType& pair) const
+    {
+        return m_heap.overlaps(pair.key.heap());
+    }
+    
+private:
+    AbstractHeap m_heap;
+};
+
+inline void clobber(ImpureMap& map, AbstractHeap heap)
+{
+    ClobberFilter filter(heap);
+    map.removeIf(filter);
+}
+
+class LocalCSEPhase : public Phase {
+public:
+    LocalCSEPhase(Graph& graph)
+        : Phase(graph, "local common subexpression elimination")
+        , m_smallBlock(graph)
+        , m_largeBlock(graph)

     {
     }
     
     bool run()
     {
     {
     }
     
     bool run()
     {

-        ASSERT(m_graph.m_fixpointState != BeforeFixpoint);
+        ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
+        ASSERT(m_graph.m_form == ThreadedCPS || m_graph.m_form == LoadStore);

         
         

-        m_changed = false;
+        bool changed = false;

         
         m_graph.clearReplacements();
         
         
         m_graph.clearReplacements();
         


@@ -62,1477 +95,621 @@ public:
             if (!block)
                 continue;
             
             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;
-                }
-            }
+            if (block->size() <= SmallMaps::capacity)
+                changed |= m_smallBlock.run(block);
+            else
+                changed |= m_largeBlock.run(block);

         }
         
         }
         

-        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 changed;

     }
     
 private:
     }
     
 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;

     
     

-    unsigned endIndexForPureCSE()
-    {
-        unsigned result = m_lastSeen[m_currentNode->op()];
-        if (result == UINT_MAX)
-            result = 0;
-        else
-            result++;
-        ASSERT(result <= m_indexInBlock);
-        return result;
-    }
-
-    Node* pureCSE(Node* node)
-    {
-        Edge child1 = node->child1().sanitized();
-        Edge child2 = node->child2().sanitized();
-        Edge child3 = node->child3().sanitized();
-        
-        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;
-            
-            Edge otherChild = otherNode->child1().sanitized();
-            if (!otherChild)
-                return otherNode;
-            if (otherChild != child1)
-                continue;
-            
-            otherChild = otherNode->child2().sanitized();
-            if (!otherChild)
-                return otherNode;
-            if (otherChild != child2)
-                continue;
-            
-            otherChild = otherNode->child3().sanitized();
-            if (!otherChild)
-                return otherNode;
-            if (otherChild != child3)
-                continue;
-            
-            return otherNode;
-        }
-        return 0;
-    }
-    
-    Node* constantCSE(Node* node)
-    {
-        for (unsigned i = endIndexForPureCSE(); i--;) {
-            Node* otherNode = m_currentBlock->at(i);
-            if (otherNode->op() != node->op())
-                continue;
-            
-            if (otherNode->constantNumber() != node->constantNumber())
-                continue;
-            
-            return otherNode;
-        }
-        return 0;
-    }
-    
-    Node* weakConstantCSE(Node* node)
-    {
-        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;
-    }
-    
-    Node* constantStoragePointerCSE(Node* 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;
+        SmallMaps()
+            : m_pureLength(0)
+            , m_impureLength(0)
+        {

         }
         }

-        return 0;
-    }

     
     

-    Node* getCalleeLoadElimination()
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case GetCallee:
-                return node;
-            default:
-                break;
-            }
+        void clear()
+        {
+            m_pureLength = 0;
+            m_impureLength = 0;

         }
         }

-        return 0;
-    }

     
     

-    Node* getArrayLengthElimination(Node* array)
-    {
-        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;
+        void write(AbstractHeap heap)
+        {
+            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;
-    }

     
     

-    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;
+        Node* addPure(PureValue value, Node* node)
+        {
+            for (unsigned i = m_pureLength; i--;) {
+                if (m_pureMap[i].key == value)
+                    return m_pureMap[i].value;

             }
             }

-            if (m_graph.clobbersWorld(node))
-                break;
+        
+            ASSERT(m_pureLength < capacity);
+            m_pureMap[m_pureLength++] = WTF::KeyValuePair<PureValue, Node*>(value, node);
+            return nullptr;

         }
         }

-        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;
+        
+        LazyNode findReplacement(HeapLocation location)
+        {
+            for (unsigned i = m_impureLength; i--;) {
+                if (m_impureMap[i].key == location)
+                    return m_impureMap[i].value;

             }
             }

-            if (m_graph.clobbersWorld(node))
-                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;
+            return nullptr;

         }
         }

-        return false;
-    }

     
     

-    Node* globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
-    {
-        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;
+        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;

         }
         }

-        return 0;
-    }

     
     

-    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;
-            }
+    private:
+        WTF::KeyValuePair<PureValue, Node*> m_pureMap[capacity];
+        WTF::KeyValuePair<HeapLocation, LazyNode> m_impureMap[capacity];
+        unsigned m_pureLength;
+        unsigned m_impureLength;
+    };

 
 

-            default:
-                break;
-            }
-            if (m_graph.clobbersWorld(node) || node->canExit())
-                return 0;
+    class LargeMaps {
+    public:
+        LargeMaps()
+        {

         }
         }

-        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;
-            }
+        void clear()
+        {
+            m_pureMap.clear();
+            m_impureMap.clear();

         }
         }

-        return 0;
-    }
-
-    bool checkFunctionElimination(JSCell* function, Node* child1)
-    {
-        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;
+    
+        void write(AbstractHeap heap)
+        {
+            clobber(m_impureMap, heap);

         }
         }

-        return false;
-    }

     
     

-    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;
+        Node* addPure(PureValue value, Node* node)
+        {
+            auto result = m_pureMap.add(value, node);
+            if (result.isNewEntry)
+                return nullptr;
+            return result.iterator->value;

         }
         }

-        return false;
-    }
-
-    bool checkStructureElimination(const StructureSet& structureSet, Node* child1)
-    {
-        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 MultiPutByOffset:
-                if (node->multiPutByOffsetData().writesStructures())
-                    return false;
-                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;
+        
+        LazyNode findReplacement(HeapLocation location)
+        {
+            return m_impureMap.get(location);
+        }
+    
+        LazyNode addImpure(HeapLocation location, LazyNode node)
+        {
+            auto result = m_impureMap.add(location, node);
+            if (result.isNewEntry)
+                return nullptr;
+            return result.iterator->value;
+        }
+
+    private:
+        HashMap<PureValue, Node*> m_pureMap;
+        HashMap<HeapLocation, LazyNode> 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);

                 }
                 }

-                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;
-    }
-    
-    bool structureTransitionWatchpointElimination(Structure* structure, Node* child1)
-    {
-        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
-                    && 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 MultiPutByOffset:
-                if (node->multiPutByOffsetData().writesStructures())
-                    return false;
-                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;
-    }
-    
-    Node* putStructureStoreElimination(Node* child1)
-    {
-        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:
-            case MultiPutByOffset:
-                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;
+            m_insertionSet.execute(block);
+        
+            return m_changed;

         }
         }

-        return 0;
-    }

     
     

-    Node* getByOffsetLoadElimination(unsigned identifierNumber, Node* base)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == base)
-                break;
-
-            switch (node->op()) {
-            case GetByOffset:
-                if (node->child2() == base
-                    && m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber)
-                    return node;
-                break;
-                
-            case MultiGetByOffset:
-                if (node->child1() == base
-                    && node->multiGetByOffsetData().identifierNumber == identifierNumber)
-                    return node;
-                break;
-                
-            case PutByOffset:
-                if (m_graph.m_storageAccessData[node->storageAccessDataIndex()].identifierNumber == identifierNumber) {
-                    if (node->child2() == base) // Must be same property storage.
-                        return node->child3().node();
-                    return 0;
-                }
-                break;
-                
-            case MultiPutByOffset:
-                if (node->multiPutByOffsetData().identifierNumber == identifierNumber) {
-                    if (node->child1() == base)
-                        return node->child2().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;
-            }
-        }
-        return 0;
-    }
+        void read(AbstractHeap) { }

     
     

-    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 MultiPutByOffset:
-                if (node->multiPutByOffsetData().identifierNumber == identifierNumber)
-                    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 write(AbstractHeap heap)
+        {
+            m_maps.write(heap);

         }
         }

-        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 def(PureValue value)
+        {
+            Node* match = m_maps.addPure(value, m_node);
+            if (!match)
+                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;
-                
-            case MultiPutByOffset:
-                if (node->multiPutByOffsetData().reallocatesStorage())
-                    return 0;
-                break;
-                
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return 0;
-                break;
-            }
+            m_node->replaceWith(match);
+            m_changed = true;

         }
         }

-        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;
-            }
-        }
-        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;
+        void def(HeapLocation location, 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();

             }
             }

-
-            default:
-                if (m_graph.clobbersWorld(node))
-                    return 0;
-                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;

             }
         }
             }
         }

-        return 0;
-    }

     
     

-    Node* getTypedArrayByteOffsetLoadElimination(Node* child1)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node == child1) 
-                break;
+    private:
+        Graph& m_graph;
+        
+        bool m_changed;
+        Node* m_node;
+        BasicBlock* m_block;
+    
+        Maps m_maps;

 
 

-            switch (node->op()) {
-            case GetTypedArrayByteOffset: {
-                if (node->child1() == child1)
-                    return node;
-                break;
-            }
+        InsertionSet m_insertionSet;
+    };

 
 

-            default:
-                if (m_graph.clobbersWorld(node))
-                    return 0;
-                break;
-            }
-        }
-        return 0;
-    }
-    
-    Node* getMyScopeLoadElimination()
+    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)

     {
     {

-        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;
-            }
-        }
-        return 0;

     }
     
     }
     

-    Node* getLocalLoadElimination(VirtualRegister local, Node*& relevantLocalOp, bool careAboutClobbering)
+    bool run()

     {
     {

-        relevantLocalOp = 0;
+        ASSERT(m_graph.m_fixpointState == FixpointNotConverged);
+        ASSERT(m_graph.m_form == SSA);

         
         

-        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();
-                }
-                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_graph.initializeNodeOwners();
+        m_graph.m_dominators.computeIfNecessary(m_graph);
+        
+        m_preOrder = m_graph.blocksInPreOrder();
+        
+        // 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 0;
+        
+        // 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();
+        
+        // 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
+        
+        return changed;

     }
     
     }
     

-    bool uncapturedSetLocalStoreElimination(VirtualRegister local, Node* expectedNode)
+    bool iterate()

     {
     {

-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case GetLocal:
-            case Flush:
-                if (node->local() == local)
-                    return false;
-                break;
-                
-            case GetLocalUnlinked:
-                if (node->unlinkedLocal() == local)
-                    return false;
-                break;
-                
-            case SetLocal: {
-                if (node->local() != local)
-                    break;
-                if (node != expectedNode)
-                    return false;
-                return true;
-            }
-                
-            case GetClosureVar:
-            case PutClosureVar:
-                if (static_cast<VirtualRegister>(node->varNumber()) == local)
-                    return false;
-                break;
-                
-            case GetMyScope:
-            case SkipTopScope:
-                if (node->origin.semantic.inlineCallFrame)
-                    break;
-                if (m_graph.uncheckedActivationRegister() == local)
-                    return false;
-                break;
-                
-            case CheckArgumentsNotCreated:
-            case GetMyArgumentsLength:
-            case GetMyArgumentsLengthSafe:
-                if (m_graph.uncheckedArgumentsRegisterFor(node->origin.semantic) == local)
-                    return false;
-                break;
-                
-            case GetMyArgumentByVal:
-            case GetMyArgumentByValSafe:
-                return false;
-                
-            case GetByVal:
-                // If this is accessing arguments then it's potentially accessing locals.
-                if (node->arrayMode().type() == Array::Arguments)
-                    return false;
-                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.
-                return false;
-                
-            default:
-                break;
-            }
-            if (m_graph.clobbersWorld(node))
-                return false;
-        }
-        RELEASE_ASSERT_NOT_REACHED();
-        return false;
-    }
+        if (verbose)
+            dataLog("Performing iteration.\n");
+        
+        m_changed = false;
+        m_graph.clearReplacements();
+        
+        for (unsigned i = 0; i < m_preOrder.size(); ++i) {
+            m_block = m_preOrder[i];
+            m_impureData = &m_impureDataMap[m_block];
+            m_writesSoFar.clear();
+            
+            if (verbose)
+                dataLog("Processing block ", *m_block, ":\n");

 
 

-    bool capturedSetLocalStoreElimination(VirtualRegister local, Node* expectedNode)
-    {
-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            switch (node->op()) {
-            case GetLocal:
-            case Flush:
-                if (node->local() == local)
-                    return false;
-                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");

                 
                 

-            case GetLocalUnlinked:
-                if (node->unlinkedLocal() == local)
-                    return false;
-                break;
+                m_graph.performSubstitution(m_node);

                 
                 

-            case SetLocal: {
-                if (node->local() != local)
-                    break;
-                if (node != expectedNode)
-                    return false;
-                return true;
-            }
-                
-            case Phantom:
-            case Check:
-            case HardPhantom:
-            case MovHint:
-            case JSConstant:
-            case DoubleConstant:
-            case Int52Constant:
-                break;
-                
-            default:
-                return false;
+                if (m_node->op() == Identity) {
+                    m_node->replaceWith(m_node->child1().node());
+                    m_changed = true;
+                } else
+                    clobberize(m_graph, m_node, *this);

             }
             }

+
+            m_insertionSet.execute(m_block);
+            
+            m_impureData->didVisit = true;

         }
         }

-        RELEASE_ASSERT_NOT_REACHED();
-        return false;
-    }
-    
-    bool setLocalStoreElimination(VariableAccessData* variableAccessData, Node* expectedNode)
-    {
-        if (variableAccessData->isCaptured())
-            return capturedSetLocalStoreElimination(variableAccessData->local(), expectedNode);
-        return uncapturedSetLocalStoreElimination(variableAccessData->local(), expectedNode);
+        
+        return m_changed;

     }
     }

+
+    void read(AbstractHeap) { }

     
     

-    bool invalidationPointElimination()
+    void write(AbstractHeap heap)

     {
     {

-        for (unsigned i = m_indexInBlock; i--;) {
-            Node* node = m_currentBlock->at(i);
-            if (node->op() == InvalidationPoint)
-                return true;
-            if (writesOverlap(m_graph, node, Watchpoint_fire))
-                break;
-        }
-        return false;
+        clobber(m_impureData->availableAtTail, heap);
+        m_writesSoFar.add(heap);
+        if (verbose)
+            dataLog("    Clobbered, new tail map: ", mapDump(m_impureData->availableAtTail), "\n");

     }
     
     }
     

-    void eliminateIrrelevantPhantomChildren(Node* node)
+    void def(PureValue value)

     {
     {

-        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)
-    {
-        if (!replacement)
-            return false;
+        // 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.

         
         

-        if (!ASSERT_DISABLED
-            && canonicalResultRepresentation(m_currentNode->result()) != canonicalResultRepresentation(replacement->result())) {
-            startCrashing();
-            dataLog("CSE attempting to replace a node with a mismatched result: ", m_currentNode, " with ", replacement, "\n");
-            dataLog("\n");
-            m_graph.dump();
-            RELEASE_ASSERT_NOT_REACHED();
+        auto result = m_pureValues.add(value, Vector<Node*>());
+        if (result.isNewEntry) {
+            result.iterator->value.append(m_node);
+            return;

         }
         
         }
         

-        m_currentNode->convertToPhantom();
-        eliminateIrrelevantPhantomChildren(m_currentNode);
-        
-        // At this point we will eliminate all references to this node.
-        m_currentNode->misc.replacement = replacement;
-        
-        m_changed = true;
+        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;
+            }
+        }

         
         

-        return true;
+        result.iterator->value.append(m_node);

     }
     
     }
     

-    void eliminate()
+    LazyNode findReplacement(HeapLocation location)

     {
     {

-        ASSERT(m_currentNode->mustGenerate());
-        m_currentNode->convertToPhantom();
-        eliminateIrrelevantPhantomChildren(m_currentNode);
+        // 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;
+        }

         
         

-        m_changed = true;
-    }
-    
-    void eliminate(Node* node, NodeType phantomType = Phantom)
-    {
-        if (!node)
-            return;
-        ASSERT(node->mustGenerate());
-        node->setOpAndDefaultFlags(phantomType);
-        if (phantomType == Phantom)
-            eliminateIrrelevantPhantomChildren(node);
+        // 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;
+        }

         
         

-        m_changed = true;
-    }
-    
-    void performNodeCSE(Node* node)
-    {
-        if (cseMode == NormalCSE)
-            m_graph.performSubstitution(node);
+        // 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.

         
         

-        switch (node->op()) {
+        Vector<BasicBlock*, 8> worklist;
+        Vector<BasicBlock*, 8> seenList;
+        BitVector seen;

         
         

-        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 ArithAbs:
-        case ArithMin:
-        case ArithMax:
-        case ArithSqrt:
-        case ArithFRound:
-        case ArithSin:
-        case ArithCos:
-        case StringCharAt:
-        case StringCharCodeAt:
-        case IsUndefined:
-        case IsBoolean:
-        case IsNumber:
-        case IsString:
-        case IsObject:
-        case IsFunction:
-        case LogicalNot:
-        case SkipTopScope:
-        case SkipScope:
-        case GetClosureRegisters:
-        case GetScope:
-        case TypeOf:
-        case CompareEqConstant:
-        case ValueToInt32:
-        case MakeRope:
-        case DoubleRep:
-        case ValueRep:
-        case Int52Rep:
-        case BooleanToNumber:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(pureCSE(node));
-            break;
-            
-        case ArithAdd:
-        case ArithSub:
-        case ArithNegate:
-        case ArithMul:
-        case ArithDiv:
-        case ArithMod:
-        case UInt32ToNumber:
-        case DoubleAsInt32: {
-            if (cseMode == StoreElimination)
-                break;
-            Node* candidate = pureCSE(node);
-            if (!candidate)
-                break;
-            if (!subsumes(candidate->arithMode(), node->arithMode())) {
-                if (!subsumes(node->arithMode(), candidate->arithMode()))
-                    break;
-                candidate->setArithMode(node->arithMode());
+        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);

             }
             }

-            setReplacement(candidate);
-            break;
-        }
-            
-        case GetCallee:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(getCalleeLoadElimination());
-            break;
-
-        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: {
-            ASSERT(m_graph.m_form != SSA);
-            VariableAccessData* variableAccessData = node->variableAccessData();
-            if (!node->child1()) {
-                // FIXME: It's silly that we punt on flush-eliminating here. We don't really
-                // need child1 to figure out what's going on.
-                // https://bugs.webkit.org/show_bug.cgi?id=130521
-                break;
-            }
-            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;
+        
+        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);
+                if (verbose)
+                    dataLog("        Availability map: ", mapDump(data.availableAtTail), "\n");
+                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;
+                }

             }
             }

-            if (!setLocalStoreElimination(variableAccessData, replacement))
-                break;
-            ASSERT(replacement->op() == SetLocal);
-            node->convertToPhantom();
-            Node* dataNode = replacement->child1().node();
-            ASSERT(dataNode->hasResult());
-            node->child1() = dataNode->defaultEdge();
-            m_graph.dethread();
-            m_changed = true;
-            break;
-        }
-            
-        case JSConstant:
-        case DoubleConstant:
-        case Int52Constant:
-            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);
+            if (verbose)
+                dataLog("        Dealing with write set ", data.writes, "\n");
+            if (data.writes.overlaps(location.heap())) {
+                if (verbose)
+                    dataLog("        Clobbered.\n");
+                return nullptr;

             }
             }

-            break;
-        }
-            
-        // 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;
-        }
-
-        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;
-        }
-
-        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 = block->predecessors.size(); i--;) {
+                BasicBlock* predecessor = block->predecessors[i];
+                if (!seen.get(predecessor->index)) {
+                    worklist.append(predecessor);
+                    seen.set(predecessor->index);
+                }

             }
             }

-            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;
-        }
-            
-        case GetTypedArrayByteOffset: {
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(getTypedArrayByteOffsetLoadElimination(node->child1().node()));
-            break;
-        }
-
-        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->child2().node()));
-            break;
-            
-        case MultiGetByOffset:
-            if (cseMode == StoreElimination)
-                break;
-            setReplacement(getByOffsetLoadElimination(node->multiGetByOffsetData().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 InvalidationPoint:
-            if (invalidationPointElimination())
-                eliminate();
-            break;
-            
-        case Phantom:
-            // FIXME: we ought to remove Phantom's that have no children.
-            // NB. It would be incorrect to do this for HardPhantom. In fact, the whole point
-            // of HardPhantom is that we *don't* do this for HardPhantoms, since they signify
-            // a more strict kind of liveness than the Phantom bytecode liveness.
-            eliminateIrrelevantPhantomChildren(node);
-            break;
-            
-        default:
-            // do nothing.
-            break;

         }
         
         }
         

-        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.isNewEntry);
+            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);
+    SamplingRegion samplingRegion("DFG LocalCSE Phase");
+    return runPhase<LocalCSEPhase>(graph);

 }
 
 }
 

-bool performStoreElimination(Graph& graph)
+bool performGlobalCSE(Graph& graph)

 {
 {

-    SamplingRegion samplingRegion("DFG Store Elimination Phase");
-    return runPhase<CSEPhase<StoreElimination>>(graph);
+    SamplingRegion samplingRegion("DFG GlobalCSE Phase");
+    return runPhase<GlobalCSEPhase>(graph);

 }
 
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)
 }
 
 } } // namespace JSC::DFG
 
 #endif // ENABLE(DFG_JIT)

-
-