/*
 * Copyright (C) 2011, 2012 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 "DFGGraph.h"
#include "DFGPhase.h"
#include <wtf/FastBitVector.h>

namespace JSC { namespace DFG {

class CSEPhase : public Phase {
public:
    CSEPhase(Graph& graph)
        : Phase(graph, "common subexpression elimination")
    {
        // Replacements are used to implement local common subexpression elimination.
        m_replacements.resize(m_graph.size());
        
        for (unsigned i = 0; i < m_graph.size(); ++i)
            m_replacements[i] = NoNode;
        
        m_relevantToOSR.resize(m_graph.size());
    }
    
    bool run()
    {
        m_changed = false;
        
        for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
            performBlockCSE(m_graph.m_blocks[block].get());
        
        return m_changed;
    }
    
private:
    
    NodeIndex canonicalize(NodeIndex nodeIndex)
    {
        if (nodeIndex == NoNode)
            return NoNode;
        
        if (m_graph[nodeIndex].op() == ValueToInt32)
            nodeIndex = m_graph[nodeIndex].child1().index();
        
        return nodeIndex;
    }
    NodeIndex canonicalize(Edge nodeUse)
    {
        return canonicalize(nodeUse.indexUnchecked());
    }
    
    unsigned endIndexForPureCSE()
    {
        unsigned result = m_lastSeen[m_graph[m_compileIndex].op()];
        if (result == UINT_MAX)
            result = 0;
        else
            result++;
        ASSERT(result <= m_indexInBlock);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        dataLogF("  limit %u: ", result);
#endif
        return result;
    }
    
    NodeIndex pureCSE(Node& node)
    {
        NodeIndex child1 = canonicalize(node.child1());
        NodeIndex child2 = canonicalize(node.child2());
        NodeIndex child3 = canonicalize(node.child3());
        
        for (unsigned i = endIndexForPureCSE(); i--;) {
            NodeIndex index = m_currentBlock->at(i);
            if (index == child1 || index == child2 || index == child3)
                break;

            Node& otherNode = m_graph[index];
            if (!otherNode.shouldGenerate())
                continue;
            
            if (node.op() != otherNode.op())
                continue;
            
            if (node.arithNodeFlags() != otherNode.arithNodeFlags())
                continue;
            
            NodeIndex otherChild = canonicalize(otherNode.child1());
            if (otherChild == NoNode)
                return index;
            if (otherChild != child1)
                continue;
            
            otherChild = canonicalize(otherNode.child2());
            if (otherChild == NoNode)
                return index;
            if (otherChild != child2)
                continue;
            
            otherChild = canonicalize(otherNode.child3());
            if (otherChild == NoNode)
                return index;
            if (otherChild != child3)
                continue;
            
            return index;
        }
        return NoNode;
    }
    
    NodeIndex constantCSE(Node& node)
    {
        for (unsigned i = endIndexForPureCSE(); i--;) {
            NodeIndex index = m_currentBlock->at(i);
            Node& otherNode = m_graph[index];
            if (otherNode.op() != JSConstant)
                continue;
            
            if (otherNode.constantNumber() != node.constantNumber())
                continue;
            
            return index;
        }
        return NoNode;
    }
    
    NodeIndex weakConstantCSE(Node& node)
    {
        for (unsigned i = endIndexForPureCSE(); i--;) {
            NodeIndex index = m_currentBlock->at(i);
            Node& otherNode = m_graph[index];
            if (otherNode.op() != WeakJSConstant)
                continue;
            
            if (otherNode.weakConstant() != node.weakConstant())
                continue;
            
            return index;
        }
        return NoNode;
    }
    
    NodeIndex getArrayLengthElimination(NodeIndex array)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case GetArrayLength:
                if (node.child1() == array)
                    return index;
                break;
                
            case PutByVal:
                if (!m_graph.byValIsPure(node))
                    return NoNode;
                if (node.arrayMode().mayStoreToHole())
                    return NoNode;
                break;
                
            default:
                if (m_graph.clobbersWorld(index))
                    return NoNode;
            }
        }
        return NoNode;
    }
    
    NodeIndex globalVarLoadElimination(WriteBarrier<Unknown>* registerPointer)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case GetGlobalVar:
                if (node.registerPointer() == registerPointer)
                    return index;
                break;
            case PutGlobalVar:
                if (node.registerPointer() == registerPointer)
                    return node.child1().index();
                break;
            default:
                break;
            }
            if (m_graph.clobbersWorld(index))
                break;
        }
        return NoNode;
    }
    
    NodeIndex scopedVarLoadElimination(NodeIndex registers, unsigned varNumber)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case GetScopedVar: {
                if (node.child1() == registers && node.varNumber() == varNumber)
                    return index;
                break;
            } 
            case PutScopedVar: {
                if (node.child2() == registers && node.varNumber() == varNumber)
                    return node.child3().index();
                break;
            }
            case SetLocal: {
                VariableAccessData* variableAccessData = node.variableAccessData();
                if (variableAccessData->isCaptured()
                    && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
                    return NoNode;
                break;
            }
            default:
                break;
            }
            if (m_graph.clobbersWorld(index))
                break;
        }
        return NoNode;
    }
    
    bool globalVarWatchpointElimination(WriteBarrier<Unknown>* registerPointer)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case GlobalVarWatchpoint:
                if (node.registerPointer() == registerPointer)
                    return true;
                break;
            case PutGlobalVar:
                if (node.registerPointer() == registerPointer)
                    return false;
                break;
            default:
                break;
            }
            if (m_graph.clobbersWorld(index))
                break;
        }
        return false;
    }
    
    NodeIndex globalVarStoreElimination(WriteBarrier<Unknown>* registerPointer)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case PutGlobalVar:
            case PutGlobalVarCheck:
                if (node.registerPointer() == registerPointer)
                    return index;
                break;
                
            case GetGlobalVar:
                if (node.registerPointer() == registerPointer)
                    return NoNode;
                break;
                
            default:
                break;
            }
            if (m_graph.clobbersWorld(index) || node.canExit())
                return NoNode;
        }
        return NoNode;
    }
    
    NodeIndex scopedVarStoreElimination(NodeIndex scope, NodeIndex registers, unsigned varNumber)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case PutScopedVar: {
                if (node.child1() == scope && node.child2() == registers && node.varNumber() == varNumber)
                    return index;
                break;
            }
                
            case GetScopedVar: {
                // Let's be conservative.
                if (node.varNumber() == varNumber)
                    return NoNode;
                break;
            }
                
            case GetLocal: {
                VariableAccessData* variableAccessData = node.variableAccessData();
                if (variableAccessData->isCaptured()
                    && variableAccessData->local() == static_cast<VirtualRegister>(varNumber))
                    return NoNode;
                break;
            }

            default:
                break;
            }
            if (m_graph.clobbersWorld(index) || node.canExit())
                return NoNode;
        }
        return NoNode;
    }
    
    NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            if (index == child1 || index == canonicalize(child2)) 
                break;

            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case GetByVal:
                if (!m_graph.byValIsPure(node))
                    return NoNode;
                if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
                    return index;
                break;
            case PutByVal:
            case PutByValAlias: {
                if (!m_graph.byValIsPure(node))
                    return NoNode;
                if (m_graph.varArgChild(node, 0) == child1 && canonicalize(m_graph.varArgChild(node, 1)) == canonicalize(child2))
                    return m_graph.varArgChild(node, 2).index();
                // 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.
                return NoNode;
            }
            case PutStructure:
            case PutByOffset:
                // GetByVal currently always speculates that it's accessing an
                // array with an integer index, which means that it's impossible
                // for a structure change or a put to property storage to affect
                // the GetByVal.
                break;
            default:
                if (m_graph.clobbersWorld(index))
                    return NoNode;
                break;
            }
        }
        return NoNode;
    }

    bool checkFunctionElimination(JSCell* function, NodeIndex child1)
    {
        for (unsigned i = endIndexForPureCSE(); i--;) {
            NodeIndex index = m_currentBlock->at(i);
            if (index == child1) 
                break;

            Node& node = m_graph[index];
            if (node.op() == CheckFunction && node.child1() == child1 && node.function() == function)
                return true;
        }
        return false;
    }

    bool checkStructureElimination(const StructureSet& structureSet, NodeIndex child1)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            if (index == child1) 
                break;

            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case CheckStructure:
            case ForwardCheckStructure:
                if (node.child1() == child1
                    && structureSet.isSupersetOf(node.structureSet()))
                    return true;
                break;
                
            case StructureTransitionWatchpoint:
            case ForwardStructureTransitionWatchpoint:
                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 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(index))
                    return false;
                break;
            }
        }
        return false;
    }
    
    bool structureTransitionWatchpointElimination(Structure* structure, NodeIndex child1)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            if (index == child1) 
                break;

            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case CheckStructure:
            case ForwardCheckStructure:
                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 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:
            case ForwardStructureTransitionWatchpoint:
                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(index))
                    return false;
                break;
            }
        }
        return false;
    }
    
    NodeIndex putStructureStoreElimination(NodeIndex child1)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            if (index == child1)
                break;
            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case CheckStructure:
            case ForwardCheckStructure:
                return NoNode;
                
            case PhantomPutStructure:
                if (node.child1() == child1) // No need to retrace our steps.
                    return NoNode;
                break;
                
            case PutStructure:
                if (node.child1() == child1)
                    return index;
                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 StrCat:
            case ToPrimitive:
            case NewRegexp:
            case NewArrayBuffer:
            case NewArray:
            case NewObject:
            case CreateThis:
            case AllocatePropertyStorage:
            case ReallocatePropertyStorage:
                return NoNode;
                
            case GetIndexedPropertyStorage:
                if (node.arrayMode().getIndexedPropertyStorageMayTriggerGC())
                    return NoNode;
                break;
                
            default:
                break;
            }
            if (m_graph.clobbersWorld(index) || node.canExit())
                return NoNode;
        }
        return NoNode;
    }
    
    NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            if (index == child1)
                break;

            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case GetByOffset:
                if (node.child1() == child1
                    && m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
                    return index;
                break;
                
            case PutByOffset:
                if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
                    if (node.child1() == child1) // Must be same property storage.
                        return node.child3().index();
                    return NoNode;
                }
                break;
                
            case PutStructure:
                // Changing the structure cannot change the outcome of a property get.
                break;
                
            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 NoNode;
                
            default:
                if (m_graph.clobbersWorld(index))
                    return NoNode;
                break;
            }
        }
        return NoNode;
    }
    
    NodeIndex putByOffsetStoreElimination(unsigned identifierNumber, NodeIndex child1)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            if (index == child1)
                break;

            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case GetByOffset:
                if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber)
                    return NoNode;
                break;
                
            case PutByOffset:
                if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) {
                    if (node.child1() == child1) // Must be same property storage.
                        return index;
                    return NoNode;
                }
                break;
                
            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 NoNode;
                
            default:
                if (m_graph.clobbersWorld(index))
                    return NoNode;
                break;
            }
            if (node.canExit())
                return NoNode;
        }
        return NoNode;
    }
    
    NodeIndex getPropertyStorageLoadElimination(NodeIndex child1)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            if (index == child1) 
                break;

            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case GetButterfly:
                if (node.child1() == child1)
                    return index;
                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 index;
                // 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 NoNode;
                
            case PutByOffset:
            case PutStructure:
                // Changing the structure or putting to the storage cannot
                // change the property storage pointer.
                break;
                
            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 NoNode;
                
            case Arrayify:
            case ArrayifyToStructure:
                // We could check if the arrayification could affect our butterfly.
                // But that seems like it would take Effort.
                return NoNode;
                
            default:
                if (m_graph.clobbersWorld(index))
                    return NoNode;
                break;
            }
        }
        return NoNode;
    }
    
    bool checkArrayElimination(NodeIndex child1, ArrayMode arrayMode)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            if (index == child1) 
                break;

            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case PutByOffset:
            case PutStructure:
                // Changing the structure or putting to the storage cannot
                // change the property storage pointer.
                break;
                
            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(index))
                    return false;
                break;
            }
        }
        return false;
    }

    NodeIndex getIndexedPropertyStorageLoadElimination(NodeIndex child1, ArrayMode arrayMode)
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            if (index == child1) 
                break;

            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case GetIndexedPropertyStorage: {
                if (node.child1() == child1 && node.arrayMode() == arrayMode)
                    return index;
                break;
            }

            case PutByOffset:
            case PutStructure:
                // Changing the structure or putting to the storage cannot
                // change the property storage pointer.
                break;
                
            default:
                if (m_graph.clobbersWorld(index))
                    return NoNode;
                break;
            }
        }
        return NoNode;
    }
    
    NodeIndex getMyScopeLoadElimination()
    {
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case CreateActivation:
                // This may cause us to return a different scope.
                return NoNode;
            case GetMyScope:
                return index;
            default:
                break;
            }
        }
        return NoNode;
    }
    
    NodeIndex getLocalLoadElimination(VirtualRegister local, NodeIndex& relevantLocalOp, bool careAboutClobbering)
    {
        relevantLocalOp = NoNode;
        
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case GetLocal:
                if (node.local() == local) {
                    relevantLocalOp = index;
                    return index;
                }
                break;
                
            case GetLocalUnlinked:
                if (node.unlinkedLocal() == local) {
                    relevantLocalOp = index;
                    return index;
                }
                break;
                
            case SetLocal:
                if (node.local() == local) {
                    relevantLocalOp = index;
                    return node.child1().index();
                }
                break;
                
            case PutScopedVar:
                if (static_cast<VirtualRegister>(node.varNumber()) == local)
                    return NoNode;
                break;
                
            default:
                if (careAboutClobbering && m_graph.clobbersWorld(index))
                    return NoNode;
                break;
            }
        }
        return NoNode;
    }
    
    struct SetLocalStoreEliminationResult {
        SetLocalStoreEliminationResult()
            : mayBeAccessed(false)
            , mayExit(false)
            , mayClobberWorld(false)
        {
        }
        
        bool mayBeAccessed;
        bool mayExit;
        bool mayClobberWorld;
    };
    SetLocalStoreEliminationResult setLocalStoreElimination(
        VirtualRegister local, NodeIndex expectedNodeIndex)
    {
        SetLocalStoreEliminationResult result;
        for (unsigned i = m_indexInBlock; i--;) {
            NodeIndex index = m_currentBlock->at(i);
            Node& node = m_graph[index];
            if (!node.shouldGenerate())
                continue;
            switch (node.op()) {
            case GetLocal:
            case Flush:
                if (node.local() == local)
                    result.mayBeAccessed = true;
                break;
                
            case GetLocalUnlinked:
                if (node.unlinkedLocal() == local)
                    result.mayBeAccessed = true;
                break;
                
            case SetLocal: {
                if (node.local() != local)
                    break;
                if (index != expectedNodeIndex)
                    result.mayBeAccessed = true;
                if (m_graph[index].refCount() > 1)
                    result.mayBeAccessed = true;
                return result;
            }
                
            case GetScopedVar:
                if (static_cast<VirtualRegister>(node.varNumber()) == local)
                    result.mayBeAccessed = true;
                break;
                
            case GetMyScope:
            case SkipTopScope:
                if (m_graph.uncheckedActivationRegisterFor(node.codeOrigin) == local)
                    result.mayBeAccessed = true;
                break;
                
            case CheckArgumentsNotCreated:
            case GetMyArgumentsLength:
            case GetMyArgumentsLengthSafe:
                if (m_graph.uncheckedArgumentsRegisterFor(node.codeOrigin) == local)
                    result.mayBeAccessed = true;
                break;
                
            case GetMyArgumentByVal:
            case GetMyArgumentByValSafe:
                result.mayBeAccessed = true;
                break;
                
            case GetByVal:
                // If this is accessing arguments then it's potentially accessing locals.
                if (m_graph[node.child1()].shouldSpeculateArguments())
                    result.mayBeAccessed = true;
                break;
                
            case CreateArguments:
            case TearOffActivation:
            case TearOffArguments:
                // If an activation is being torn off then it means that captured variables
                // are live. We could be clever here and check if the local qualifies as an
                // argument register. But that seems like it would buy us very little since
                // any kind of tear offs are rare to begin with.
                result.mayBeAccessed = true;
                break;
                
            default:
                break;
            }
            result.mayExit |= node.canExit();
            result.mayClobberWorld |= m_graph.clobbersWorld(index);
        }
        ASSERT_NOT_REACHED();
        // Be safe in release mode.
        result.mayBeAccessed = true;
        return result;
    }
    
    void performSubstitution(Edge& child, bool addRef = true)
    {
        // Check if this operand is actually unused.
        if (!child)
            return;
        
        // Check if there is any replacement.
        NodeIndex replacement = m_replacements[child.index()];
        if (replacement == NoNode)
            return;
        
        child.setIndex(replacement);
        
        // There is definitely a replacement. Assert that the replacement does not
        // have a replacement.
        ASSERT(m_replacements[child.index()] == NoNode);
        
        if (addRef)
            m_graph.ref(child);
    }
    
    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 (m_relevantToOSR.get(edge.index()))
                continue;
            
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
            dataLog("   Eliminating edge @", m_compileIndex, " -> @", edge.index());
#endif
            m_graph.deref(edge);
            node.children.removeEdgeFromBag(i--);
            m_changed = true;
        }
    }
    
    enum PredictionHandlingMode { RequireSamePrediction, AllowPredictionMismatch };
    bool setReplacement(NodeIndex replacement, PredictionHandlingMode predictionHandlingMode = RequireSamePrediction)
    {
        if (replacement == NoNode)
            return false;
        
        // Be safe. Don't try to perform replacements if the predictions don't
        // agree.
        if (predictionHandlingMode == RequireSamePrediction
            && m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
            return false;
        
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        dataLogF("   Replacing @%u -> @%u", m_compileIndex, replacement);
#endif
        
        Node& node = m_graph[m_compileIndex];
        node.setOpAndDefaultFlags(Phantom);
        node.setRefCount(1);
        eliminateIrrelevantPhantomChildren(node);
        
        // At this point we will eliminate all references to this node.
        m_replacements[m_compileIndex] = replacement;
        
        m_changed = true;
        
        return true;
    }
    
    void eliminate()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        dataLogF("   Eliminating @%u", m_compileIndex);
#endif
        
        Node& node = m_graph[m_compileIndex];
        ASSERT(node.refCount() == 1);
        ASSERT(node.mustGenerate());
        node.setOpAndDefaultFlags(Phantom);
        eliminateIrrelevantPhantomChildren(node);
        
        m_changed = true;
    }
    
    void eliminate(NodeIndex nodeIndex, NodeType phantomType = Phantom)
    {
        if (nodeIndex == NoNode)
            return;
        Node& node = m_graph[nodeIndex];
        if (node.refCount() != 1)
            return;
        ASSERT(node.mustGenerate());
        node.setOpAndDefaultFlags(phantomType);
        if (phantomType == Phantom)
            eliminateIrrelevantPhantomChildren(node);
        
        m_changed = true;
    }
    
    void performNodeCSE(Node& node)
    {
        bool shouldGenerate = node.shouldGenerate();

        if (node.flags() & NodeHasVarArgs) {
            for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
                performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate);
        } else {
            performSubstitution(node.children.child1(), shouldGenerate);
            performSubstitution(node.children.child2(), shouldGenerate);
            performSubstitution(node.children.child3(), shouldGenerate);
        }
        
        if (node.op() == SetLocal)
            m_relevantToOSR.set(node.child1().index());
        
        if (!shouldGenerate)
            return;
        
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        dataLogF("   %s @%u: ", Graph::opName(m_graph[m_compileIndex].op()), m_compileIndex);
#endif
        
        // NOTE: there are some nodes that we deliberately don't CSE even though we
        // probably could, like StrCat and ToPrimitive. That's because there is no
        // evidence that doing CSE on these nodes would result in a performance
        // progression. Hence considering these nodes in CSE would just mean that this
        // code does more work with no win. Of course, we may want to reconsider this,
        // since StrCat is trivially CSE-able. It's not trivially doable for
        // ToPrimitive, but we could change that with some speculations if we really
        // needed to.
        
        switch (node.op()) {
        
        case Identity:
            setReplacement(node.child1().index());
            break;
            
        // Handle the pure nodes. These nodes never have any side-effects.
        case BitAnd:
        case BitOr:
        case BitXor:
        case BitRShift:
        case BitLShift:
        case BitURShift:
        case ArithAdd:
        case ArithSub:
        case ArithNegate:
        case ArithMul:
        case ArithMod:
        case ArithDiv:
        case ArithAbs:
        case ArithMin:
        case ArithMax:
        case ArithSqrt:
        case GetCallee:
        case StringCharAt:
        case StringCharCodeAt:
        case Int32ToDouble:
        case IsUndefined:
        case IsBoolean:
        case IsNumber:
        case IsString:
        case IsObject:
        case IsFunction:
        case DoubleAsInt32:
        case LogicalNot:
        case SkipTopScope:
        case SkipScope:
        case GetScopeRegisters:
            setReplacement(pureCSE(node));
            break;
            
        case GetLocal: {
            VariableAccessData* variableAccessData = node.variableAccessData();
            if (!variableAccessData->isCaptured())
                break;
            NodeIndex relevantLocalOp;
            NodeIndex possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp, variableAccessData->isCaptured());
            if (relevantLocalOp == NoNode)
                break;
            if (m_graph[relevantLocalOp].op() != GetLocalUnlinked
                && m_graph[relevantLocalOp].variableAccessData() != variableAccessData)
                break;
            NodeIndex phiIndex = node.child1().index();
            if (!setReplacement(possibleReplacement))
                break;
            // If the GetLocal we replaced used to refer to a SetLocal, then it now
            // should refer to the child of the SetLocal instead.
            if (m_graph[phiIndex].op() == SetLocal) {
                ASSERT(node.child1().index() == phiIndex);
                m_graph.changeEdge(node.children.child1(), m_graph[phiIndex].child1());
            }
            NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(
                variableAccessData->local());
            if (oldTailIndex == m_compileIndex) {
                m_currentBlock->variablesAtTail.operand(variableAccessData->local()) =
                    relevantLocalOp;
                
                // Maintain graph integrity: since we're replacing a GetLocal with a GetLocalUnlinked,
                // make sure that the GetLocalUnlinked is now linked.
                if (m_graph[relevantLocalOp].op() == GetLocalUnlinked) {
                    m_graph[relevantLocalOp].setOp(GetLocal);
                    m_graph[relevantLocalOp].children.child1() = Edge(phiIndex);
                    m_graph.ref(phiIndex);
                }
            }
            m_changed = true;
            break;
        }
            
        case GetLocalUnlinked: {
            NodeIndex relevantLocalOpIgnored;
            setReplacement(getLocalLoadElimination(node.unlinkedLocal(), relevantLocalOpIgnored, true));
            break;
        }
            
        case Flush: {
            VariableAccessData* variableAccessData = node.variableAccessData();
            VirtualRegister local = variableAccessData->local();
            NodeIndex replacementIndex = node.child1().index();
            Node& replacement = m_graph[replacementIndex];
            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 (m_graph.m_fixpointState == FixpointNotConverged) {
                // Need to be conservative at this time; if the SetLocal has any chance of performing
                // any speculations then we cannot do anything.
                if (variableAccessData->isCaptured()) {
                    // Captured SetLocals never speculate and hence never exit.
                } else {
                    if (variableAccessData->shouldUseDoubleFormat())
                        break;
                    SpeculatedType prediction = variableAccessData->argumentAwarePrediction();
                    if (isInt32Speculation(prediction))
                        break;
                    if (isArraySpeculation(prediction))
                        break;
                    if (isBooleanSpeculation(prediction))
                        break;
                }
            } else {
                if (replacement.canExit())
                    break;
            }
            SetLocalStoreEliminationResult result =
                setLocalStoreElimination(local, replacementIndex);
            if (result.mayBeAccessed || result.mayClobberWorld)
                break;
            ASSERT(replacement.op() == SetLocal);
            ASSERT(replacement.refCount() == 1);
            ASSERT(replacement.shouldGenerate());
            // FIXME: Investigate using mayExit as a further optimization.
            node.setOpAndDefaultFlags(Phantom);
            NodeIndex dataNodeIndex = replacement.child1().index();
            ASSERT(m_graph[dataNodeIndex].hasResult());
            m_graph.clearAndDerefChild1(node);
            node.children.child1() = Edge(dataNodeIndex);
            m_graph.ref(dataNodeIndex);
            NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(local);
            if (oldTailIndex == m_compileIndex)
                m_currentBlock->variablesAtTail.operand(local) = replacementIndex;
            m_changed = true;
            break;
        }
            
        case JSConstant:
            // 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), AllowPredictionMismatch);
            break;
            
        case WeakJSConstant:
            // FIXME: have CSE for weak constants against strong constants and vice-versa.
            setReplacement(weakConstantCSE(node));
            break;
            
        case GetArrayLength:
            setReplacement(getArrayLengthElimination(node.child1().index()));
            break;

        case GetMyScope:
            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 ValueAdd:
        case CompareLess:
        case CompareLessEq:
        case CompareGreater:
        case CompareGreaterEq:
        case CompareEq: {
            if (m_graph.isPredictedNumerical(node)) {
                NodeIndex replacementIndex = pureCSE(node);
                if (replacementIndex != NoNode && m_graph.isPredictedNumerical(m_graph[replacementIndex]))
                    setReplacement(replacementIndex);
            }
            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:
            setReplacement(globalVarLoadElimination(node.registerPointer()));
            break;

        case GetScopedVar: {
            setReplacement(scopedVarLoadElimination(node.child1().index(), node.varNumber()));
            break;
        }

        case GlobalVarWatchpoint:
            if (globalVarWatchpointElimination(node.registerPointer()))
                eliminate();
            break;
            
        case PutGlobalVar:
        case PutGlobalVarCheck:
            if (m_graph.m_fixpointState == FixpointNotConverged)
                break;
            eliminate(globalVarStoreElimination(node.registerPointer()));
            break;
            
        case PutScopedVar: {
            if (m_graph.m_fixpointState == FixpointNotConverged)
                break;
            eliminate(scopedVarStoreElimination(node.child1().index(), node.child2().index(), node.varNumber()));
            break;
        }

        case GetByVal:
            if (m_graph.byValIsPure(node))
                setReplacement(getByValLoadElimination(node.child1().index(), node.child2().index()));
            break;
            
        case PutByVal: {
            Edge child1 = m_graph.varArgChild(node, 0);
            Edge child2 = m_graph.varArgChild(node, 1);
            if (node.arrayMode().canCSEStorage()) {
                NodeIndex nodeIndex = getByValLoadElimination(child1.index(), child2.index());
                if (nodeIndex == NoNode)
                    break;
                node.setOp(PutByValAlias);
            }
            break;
        }
            
        case CheckStructure:
        case ForwardCheckStructure:
            if (checkStructureElimination(node.structureSet(), node.child1().index()))
                eliminate();
            break;
            
        case StructureTransitionWatchpoint:
        case ForwardStructureTransitionWatchpoint:
            if (structureTransitionWatchpointElimination(node.structure(), node.child1().index()))
                eliminate();
            break;
            
        case PutStructure:
            if (m_graph.m_fixpointState == FixpointNotConverged)
                break;
            eliminate(putStructureStoreElimination(node.child1().index()), PhantomPutStructure);
            break;

        case CheckFunction:
            if (checkFunctionElimination(node.function(), node.child1().index()))
                eliminate();
            break;
                
        case CheckArray:
            if (checkArrayElimination(node.child1().index(), node.arrayMode()))
                eliminate();
            break;
            
        case GetIndexedPropertyStorage: {
            setReplacement(getIndexedPropertyStorageLoadElimination(node.child1().index(), node.arrayMode()));
            break;
        }

        case GetButterfly:
            setReplacement(getPropertyStorageLoadElimination(node.child1().index()));
            break;

        case GetByOffset:
            setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
            break;
            
        case PutByOffset:
            if (m_graph.m_fixpointState == FixpointNotConverged)
                break;
            eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index()));
            break;
            
        case Phantom:
            // FIXME: we ought to remove Phantom's that have no children.
            
            eliminateIrrelevantPhantomChildren(node);
            break;
            
        default:
            // do nothing.
            break;
        }
        
        m_lastSeen[node.op()] = m_indexInBlock;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        dataLogF("\n");
#endif
    }
    
    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;
        
        // Make all of my Phi nodes relevant to OSR.
        for (unsigned i = 0; i < block->phis.size(); ++i)
            m_relevantToOSR.set(block->phis[i]);
        
        // Make all of my SetLocal nodes relevant to OSR.
        for (unsigned i = 0; i < block->size(); ++i) {
            NodeIndex nodeIndex = block->at(i);
            Node& node = m_graph[nodeIndex];
            switch (node.op()) {
            case SetLocal:
                m_relevantToOSR.set(nodeIndex);
                break;
            default:
                break;
            }
        }

        for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) {
            m_compileIndex = block->at(m_indexInBlock);
            performNodeCSE(m_graph[m_compileIndex]);
        }
    }
    
    BasicBlock* m_currentBlock;
    NodeIndex m_compileIndex;
    unsigned m_indexInBlock;
    Vector<NodeIndex, 16> m_replacements;
    FixedArray<unsigned, LastNodeType> m_lastSeen;
    FastBitVector m_relevantToOSR;
    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>(graph);
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)