DFGCSEPhase.cpp   [plain text]

/*
 * Copyright (C) 2011, 2012, 2013, 2014 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#include "config.h"
#include "DFGCSEPhase.h"

#if ENABLE(DFG_JIT)

#include "DFGAbstractHeap.h"
#include "DFGClobberize.h"
#include "DFGEdgeUsesStructure.h"
#include "DFGGraph.h"
#include "DFGPhase.h"
#include "JSCInlines.h"
#include <array>
#include <wtf/FastBitVector.h>

namespace JSC { namespace DFG {

enum CSEMode { NormalCSE, StoreElimination };

template<CSEMode cseMode>
class CSEPhase : public Phase {
public:
    CSEPhase(Graph& graph)
        : Phase(graph, cseMode == NormalCSE ? "common subexpression elimination" : "store elimination")
    {
    }
    
    bool run()
    {
        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;
    }
    
private:
    
    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;
        }
        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;
            }
        }
        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;
            }
        }
        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;
        }
        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;
        }
        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 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;
        }
        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;
            }

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

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

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

            default:
                if (m_graph.clobbersWorld(node))
                    return 0;
                break;
            }
        }
        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;
            }
        }
        return 0;
    }
    
    Node* getLocalLoadElimination(VirtualRegister local, Node*& relevantLocalOp, bool careAboutClobbering)
    {
        relevantLocalOp = 0;
        
        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;
            }
        }
        return 0;
    }
    
    bool uncapturedSetLocalStoreElimination(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;
                
            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;
    }

    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;
                
            case GetLocalUnlinked:
                if (node->unlinkedLocal() == local)
                    return false;
                break;
                
            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;
            }
        }
        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);
    }
    
    bool invalidationPointElimination()
    {
        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;
    }
    
    void eliminateIrrelevantPhantomChildren(Node* node)
    {
        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;
        
        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();
        }
        
        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;
        
        return true;
    }
    
    void eliminate()
    {
        ASSERT(m_currentNode->mustGenerate());
        m_currentNode->convertToPhantom();
        eliminateIrrelevantPhantomChildren(m_currentNode);
        
        m_changed = true;
    }
    
    void eliminate(Node* node, NodeType phantomType = Phantom)
    {
        if (!node)
            return;
        ASSERT(node->mustGenerate());
        node->setOpAndDefaultFlags(phantomType);
        if (phantomType == Phantom)
            eliminateIrrelevantPhantomChildren(node);
        
        m_changed = true;
    }
    
    void performNodeCSE(Node* node)
    {
        if (cseMode == NormalCSE)
            m_graph.performSubstitution(node);
        
        switch (node->op()) {
        
        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());
            }
            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;
            }
            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);
            }
            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);
            }
            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;
    }
    
    void performBlockCSE(BasicBlock* block)
    {
        if (!block)
            return;
        if (!block->isReachable)
            return;
        
        m_currentBlock = block;
        for (unsigned i = 0; i < LastNodeType; ++i)
            m_lastSeen[i] = UINT_MAX;
        
        for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
            m_currentNode = block->at(m_indexInBlock);
            performNodeCSE(m_currentNode);
        }
        
        if (!ASSERT_DISABLED && cseMode == StoreElimination) {
            // Nobody should have replacements set.
            for (unsigned i = 0; i < block->size(); ++i)
                ASSERT(!block->at(i)->misc.replacement);
        }
    }
    
    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.
};

bool performCSE(Graph& graph)
{
    SamplingRegion samplingRegion("DFG CSE Phase");
    return runPhase<CSEPhase<NormalCSE>>(graph);
}

bool performStoreElimination(Graph& graph)
{
    SamplingRegion samplingRegion("DFG Store Elimination Phase");
    return runPhase<CSEPhase<StoreElimination>>(graph);
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)