DFGPropagator.cpp   [plain text]

/*
 * Copyright (C) 2011 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 "DFGPropagator.h"

#if ENABLE(DFG_JIT)

#include "DFGAbstractState.h"
#include "DFGGraph.h"
#include "DFGScoreBoard.h"
#include <wtf/FixedArray.h>

namespace JSC { namespace DFG {

class Propagator {
public:
    Propagator(Graph& graph, JSGlobalData& globalData, CodeBlock* codeBlock, CodeBlock* profiledBlock)
        : m_graph(graph)
        , m_globalData(globalData)
        , m_codeBlock(codeBlock)
        , m_profiledBlock(profiledBlock)
    {
        // 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;
        
        for (unsigned i = 0; i < LastNodeId; ++i)
            m_lastSeen[i] = NoNode;
    }
    
    void fixpoint()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        m_graph.dump(m_codeBlock);
#endif

        propagateArithNodeFlags();
        propagatePredictions();
        fixup();
        
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("Graph after propagation fixup:\n");
        m_graph.dump(m_codeBlock);
#endif

        localCSE();

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("Graph after CSE:\n");
        m_graph.dump(m_codeBlock);
#endif

        allocateVirtualRegisters();

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("Graph after virtual register allocation:\n");
        m_graph.dump(m_codeBlock);
#endif

        globalCFA();

#if DFG_ENABLE(DEBUG_VERBOSE)
        printf("Graph after propagation:\n");
        m_graph.dump(m_codeBlock);
#endif
    }
    
private:
    bool isNotNegZero(NodeIndex nodeIndex)
    {
        if (!m_graph.isNumberConstant(m_codeBlock, nodeIndex))
            return false;
        double value = m_graph.valueOfNumberConstant(m_codeBlock, nodeIndex);
        return !value && 1.0 / value < 0.0;
    }
    
    bool isNotZero(NodeIndex nodeIndex)
    {
        if (!m_graph.isNumberConstant(m_codeBlock, nodeIndex))
            return false;
        return !!m_graph.valueOfNumberConstant(m_codeBlock, nodeIndex);
    }
    
    void propagateArithNodeFlags(Node& node)
    {
        if (!node.shouldGenerate())
            return;
        
        NodeType op = node.op;
        ArithNodeFlags flags = 0;
        
        if (node.hasArithNodeFlags())
            flags = node.rawArithNodeFlags();
        
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("   %s @%u: %s ", Graph::opName(op), m_compileIndex, arithNodeFlagsAsString(flags));
#endif
        
        flags &= NodeUsedAsMask;
        
        bool changed = false;
        
        switch (op) {
        case ValueToInt32:
        case BitAnd:
        case BitOr:
        case BitXor:
        case BitLShift:
        case BitRShift:
        case BitURShift: {
            // These operations are perfectly happy with truncated integers,
            // so we don't want to propagate anything.
            break;
        }
            
        case ValueToNumber:
        case ValueToDouble:
        case UInt32ToNumber: {
            changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
            break;
        }
            
        case ArithAdd:
        case ValueAdd: {
            if (isNotNegZero(node.child1()) || isNotNegZero(node.child2()))
                flags &= ~NodeNeedsNegZero;
            
            changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
            changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
            break;
        }
            
        case ArithSub: {
            if (isNotZero(node.child1()) || isNotZero(node.child2()))
                flags &= ~NodeNeedsNegZero;
            
            changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
            changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
            break;
        }
            
        case ArithMul:
        case ArithDiv: {
            // As soon as a multiply happens, we can easily end up in the part
            // of the double domain where the point at which you do truncation
            // can change the outcome. So, ArithMul always checks for overflow
            // no matter what, and always forces its inputs to check as well.
            
            flags |= NodeUsedAsNumber | NodeNeedsNegZero;
            changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
            changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
            break;
        }
            
        case ArithMin:
        case ArithMax: {
            flags |= NodeUsedAsNumber;
            changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
            changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
            break;
        }
            
        case ArithAbs: {
            flags &= ~NodeNeedsNegZero;
            changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
            break;
        }
            
        case PutByVal: {
            changed |= m_graph[node.child1()].mergeArithNodeFlags(flags | NodeUsedAsNumber | NodeNeedsNegZero);
            changed |= m_graph[node.child2()].mergeArithNodeFlags(flags | NodeUsedAsNumber);
            changed |= m_graph[node.child3()].mergeArithNodeFlags(flags | NodeUsedAsNumber | NodeNeedsNegZero);
            break;
        }
            
        case GetByVal: {
            changed |= m_graph[node.child1()].mergeArithNodeFlags(flags | NodeUsedAsNumber | NodeNeedsNegZero);
            changed |= m_graph[node.child2()].mergeArithNodeFlags(flags | NodeUsedAsNumber);
            break;
        }
            
        default:
            flags |= NodeUsedAsNumber | NodeNeedsNegZero;
            if (op & NodeHasVarArgs) {
                for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
                    changed |= m_graph[m_graph.m_varArgChildren[childIdx]].mergeArithNodeFlags(flags);
            } else {
                if (node.child1() == NoNode)
                    break;
                changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);
                if (node.child2() == NoNode)
                    break;
                changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);
                if (node.child3() == NoNode)
                    break;
                changed |= m_graph[node.child3()].mergeArithNodeFlags(flags);
            }
            break;
        }

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("%s\n", changed ? "CHANGED" : "");
#endif
        
        m_changed |= changed;
    }
    
    void propagateArithNodeFlagsForward()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("Propagating arithmetic node flags forward [%u]\n", ++m_count);
#endif
        for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
            propagateArithNodeFlags(m_graph[m_compileIndex]);
    }
    
    void propagateArithNodeFlagsBackward()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("Propagating arithmetic node flags backward [%u]\n", ++m_count);
#endif
        for (m_compileIndex = m_graph.size(); m_compileIndex-- > 0;)
            propagateArithNodeFlags(m_graph[m_compileIndex]);
    }
    
    void propagateArithNodeFlags()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        m_count = 0;
#endif
        do {
            m_changed = false;
            
            // Up here we start with a backward pass because we suspect that to be
            // more profitable.
            propagateArithNodeFlagsBackward();
            if (!m_changed)
                break;
            
            m_changed = false;
            propagateArithNodeFlagsForward();
        } while (m_changed);
    }
    
    bool setPrediction(PredictedType prediction)
    {
        ASSERT(m_graph[m_compileIndex].hasResult());
        
        // setPrediction() is used when we know that there is no way that we can change
        // our minds about what the prediction is going to be. There is no semantic
        // difference between setPrediction() and mergePrediction() other than the
        // increased checking to validate this property.
        ASSERT(m_graph[m_compileIndex].prediction() == PredictNone || m_graph[m_compileIndex].prediction() == prediction);
        
        return m_graph[m_compileIndex].predict(prediction);
    }
    
    bool mergePrediction(PredictedType prediction)
    {
        ASSERT(m_graph[m_compileIndex].hasResult());
        
        return m_graph[m_compileIndex].predict(prediction);
    }
    
    void propagateNodePredictions(Node& node)
    {
        if (!node.shouldGenerate())
            return;
        
        NodeType op = node.op;

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("   %s @%u: ", Graph::opName(op), m_compileIndex);
#endif
        
        bool changed = false;
        
        switch (op) {
        case JSConstant:
        case WeakJSConstant: {
            changed |= setPrediction(predictionFromValue(m_graph.valueOfJSConstant(m_codeBlock, m_compileIndex)));
            break;
        }
            
        case GetLocal: {
            PredictedType prediction = node.variableAccessData()->prediction();
            if (prediction)
                changed |= mergePrediction(prediction);
            break;
        }
            
        case SetLocal: {
            changed |= node.variableAccessData()->predict(m_graph[node.child1()].prediction());
            break;
        }
            
        case BitAnd:
        case BitOr:
        case BitXor:
        case BitRShift:
        case BitLShift:
        case BitURShift:
        case ValueToInt32: {
            changed |= setPrediction(PredictInt32);
            break;
        }
            
        case ArrayPop:
        case ArrayPush: {
            if (node.getHeapPrediction())
                changed |= mergePrediction(node.getHeapPrediction());
            break;
        }

        case StringCharCodeAt: {
            changed |= mergePrediction(PredictInt32);
            break;
        }

        case ArithMod: {
            PredictedType left = m_graph[node.child1()].prediction();
            PredictedType right = m_graph[node.child2()].prediction();
            
            if (left && right) {
                if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
                    changed |= mergePrediction(PredictInt32);
                else
                    changed |= mergePrediction(PredictDouble);
            }
            break;
        }
            
        case UInt32ToNumber: {
            if (nodeCanSpeculateInteger(node.arithNodeFlags()))
                changed |= setPrediction(PredictInt32);
            else
                changed |= setPrediction(PredictNumber);
            break;
        }

        case ValueToNumber: {
            PredictedType prediction = m_graph[node.child1()].prediction();
            
            if (prediction) {
                if (!(prediction & PredictDouble) && nodeCanSpeculateInteger(node.arithNodeFlags()))
                    changed |= mergePrediction(PredictInt32);
                else
                    changed |= mergePrediction(PredictNumber);
            }
            
            break;
        }

        case ValueAdd: {
            PredictedType left = m_graph[node.child1()].prediction();
            PredictedType right = m_graph[node.child2()].prediction();
            
            if (left && right) {
                if (isNumberPrediction(left) && isNumberPrediction(right)) {
                    if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
                        changed |= mergePrediction(PredictInt32);
                    else
                        changed |= mergePrediction(PredictDouble);
                } else if (!(left & PredictNumber) || !(right & PredictNumber)) {
                    // left or right is definitely something other than a number.
                    changed |= mergePrediction(PredictString);
                } else
                    changed |= mergePrediction(PredictString | PredictInt32 | PredictDouble);
            }
            break;
        }
            
        case ArithAdd:
        case ArithSub:
        case ArithMul:
        case ArithMin:
        case ArithMax:
        case ArithDiv: {
            PredictedType left = m_graph[node.child1()].prediction();
            PredictedType right = m_graph[node.child2()].prediction();
            
            if (left && right) {
                if (isInt32Prediction(mergePredictions(left, right)) && nodeCanSpeculateInteger(node.arithNodeFlags()))
                    changed |= mergePrediction(PredictInt32);
                else
                    changed |= mergePrediction(PredictDouble);
            }
            break;
        }
            
        case ArithSqrt: {
            changed |= setPrediction(PredictDouble);
            break;
        }
            
        case ArithAbs: {
            PredictedType child = m_graph[node.child1()].prediction();
            if (child) {
                if (nodeCanSpeculateInteger(node.arithNodeFlags()))
                    changed |= mergePrediction(child);
                else
                    changed |= setPrediction(PredictDouble);
            }
            break;
        }
            
        case LogicalNot:
        case CompareLess:
        case CompareLessEq:
        case CompareGreater:
        case CompareGreaterEq:
        case CompareEq:
        case CompareStrictEq:
        case InstanceOf: {
            changed |= setPrediction(PredictBoolean);
            break;
        }
            
        case GetById: {
            if (node.getHeapPrediction())
                changed |= mergePrediction(node.getHeapPrediction());
            else if (m_codeBlock->identifier(node.identifierNumber()) == m_globalData.propertyNames->length) {
                // If there is no prediction from value profiles, check if we might be
                // able to infer the type ourselves.
                bool isArray = isArrayPrediction(m_graph[node.child1()].prediction());
                bool isString = isStringPrediction(m_graph[node.child1()].prediction());
                bool isByteArray = m_graph[node.child1()].shouldSpeculateByteArray();
                bool isInt8Array = m_graph[node.child1()].shouldSpeculateInt8Array();
                bool isInt16Array = m_graph[node.child1()].shouldSpeculateInt16Array();
                bool isInt32Array = m_graph[node.child1()].shouldSpeculateInt32Array();
                bool isUint8Array = m_graph[node.child1()].shouldSpeculateUint8Array();
                bool isUint16Array = m_graph[node.child1()].shouldSpeculateUint16Array();
                bool isUint32Array = m_graph[node.child1()].shouldSpeculateUint32Array();
                bool isFloat32Array = m_graph[node.child1()].shouldSpeculateFloat32Array();
                bool isFloat64Array = m_graph[node.child1()].shouldSpeculateFloat64Array();
                if (isArray || isString || isByteArray || isInt8Array || isInt16Array || isInt32Array || isUint8Array || isUint16Array || isUint32Array || isFloat32Array || isFloat64Array)
                    changed |= mergePrediction(PredictInt32);
            }
            break;
        }
            
        case GetByIdFlush:
            if (node.getHeapPrediction())
                changed |= mergePrediction(node.getHeapPrediction());
            break;
            
        case GetByVal: {
            if (m_graph[node.child1()].shouldSpeculateUint32Array() || m_graph[node.child1()].shouldSpeculateFloat32Array() || m_graph[node.child1()].shouldSpeculateFloat64Array())
                changed |= mergePrediction(PredictDouble);
            else if (node.getHeapPrediction())
                changed |= mergePrediction(node.getHeapPrediction());
            break;
        }
            
        case GetPropertyStorage: 
        case GetIndexedPropertyStorage: {
            changed |= setPrediction(PredictOther);
            break;
        }

        case GetByOffset: {
            if (node.getHeapPrediction())
                changed |= mergePrediction(node.getHeapPrediction());
            break;
        }
            
        case Call:
        case Construct: {
            if (node.getHeapPrediction())
                changed |= mergePrediction(node.getHeapPrediction());
            break;
        }
            
        case ConvertThis: {
            PredictedType prediction = m_graph[node.child1()].prediction();
            if (prediction) {
                if (prediction & ~PredictObjectMask) {
                    prediction &= PredictObjectMask;
                    prediction = mergePredictions(prediction, PredictObjectOther);
                }
                changed |= mergePrediction(prediction);
            }
            break;
        }
            
        case GetGlobalVar: {
            PredictedType prediction = m_graph.getGlobalVarPrediction(node.varNumber());
            if (prediction)
                changed |= mergePrediction(prediction);
            break;
        }
            
        case PutGlobalVar: {
            changed |= m_graph.predictGlobalVar(node.varNumber(), m_graph[node.child1()].prediction());
            break;
        }
            
        case GetScopedVar:
        case Resolve:
        case ResolveBase:
        case ResolveBaseStrictPut:
        case ResolveGlobal: {
            PredictedType prediction = node.getHeapPrediction();
            if (prediction)
                changed |= mergePrediction(prediction);
            break;
        }
            
        case GetScopeChain: {
            changed |= setPrediction(PredictCellOther);
            break;
        }
            
        case GetCallee: {
            changed |= setPrediction(PredictFunction);
            break;
        }
            
        case CreateThis:
        case NewObject: {
            changed |= setPrediction(PredictFinalObject);
            break;
        }
            
        case NewArray:
        case NewArrayBuffer: {
            changed |= setPrediction(PredictArray);
            break;
        }
            
        case NewRegexp: {
            changed |= setPrediction(PredictObjectOther);
            break;
        }
        
        case StringCharAt:
        case StrCat: {
            changed |= setPrediction(PredictString);
            break;
        }
            
        case ToPrimitive: {
            PredictedType child = m_graph[node.child1()].prediction();
            if (child) {
                if (isObjectPrediction(child)) {
                    // I'd love to fold this case into the case below, but I can't, because
                    // removing PredictObjectMask from something that only has an object
                    // prediction and nothing else means we have an ill-formed PredictedType
                    // (strong predict-none). This should be killed once we remove all traces
                    // of static (aka weak) predictions.
                    changed |= mergePrediction(PredictString);
                } else if (child & PredictObjectMask) {
                    // Objects get turned into strings. So if the input has hints of objectness,
                    // the output will have hinsts of stringiness.
                    changed |= mergePrediction(mergePredictions(child & ~PredictObjectMask, PredictString));
                } else
                    changed |= mergePrediction(child);
            }
            break;
        }
            
        case ValueToDouble:
        case GetArrayLength:
        case GetByteArrayLength:
        case GetInt8ArrayLength:
        case GetInt16ArrayLength:
        case GetInt32ArrayLength:
        case GetUint8ArrayLength:
        case GetUint16ArrayLength:
        case GetUint32ArrayLength:
        case GetFloat32ArrayLength:
        case GetFloat64ArrayLength:
        case GetStringLength: {
            // This node should never be visible at this stage of compilation. It is
            // inserted by fixup(), which follows this phase.
            ASSERT_NOT_REACHED();
            break;
        }
        
#ifndef NDEBUG
        // These get ignored because they don't return anything.
        case PutScopedVar:
        case DFG::Jump:
        case Branch:
        case Breakpoint:
        case Return:
        case CheckHasInstance:
        case Phi:
        case Flush:
        case Throw:
        case ThrowReferenceError:
        case ForceOSRExit:
        case SetArgument:
        case PutByVal:
        case PutByValAlias:
        case PutById:
        case PutByIdDirect:
        case CheckStructure:
        case CheckFunction:
        case PutStructure:
        case PutByOffset:
            break;
            
        // These gets ignored because it doesn't do anything.
        case Phantom:
        case InlineStart:
        case Nop:
            break;
#else
        default:
            break;
#endif
        }

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("%s\n", predictionToString(m_graph[m_compileIndex].prediction()));
#endif
        
        m_changed |= changed;
    }
    
    void propagatePredictionsForward()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("Propagating predictions forward [%u]\n", ++m_count);
#endif
        for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
            propagateNodePredictions(m_graph[m_compileIndex]);
    }
    
    void propagatePredictionsBackward()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("Propagating predictions backward [%u]\n", ++m_count);
#endif
        for (m_compileIndex = m_graph.size(); m_compileIndex-- > 0;)
            propagateNodePredictions(m_graph[m_compileIndex]);
    }
    
    void propagatePredictions()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        m_count = 0;
#endif
        do {
            m_changed = false;
            
            // Forward propagation is near-optimal for both topologically-sorted and
            // DFS-sorted code.
            propagatePredictionsForward();
            if (!m_changed)
                break;
            
            // Backward propagation reduces the likelihood that pathological code will
            // cause slowness. Loops (especially nested ones) resemble backward flow.
            // This pass captures two cases: (1) it detects if the forward fixpoint
            // found a sound solution and (2) short-circuits backward flow.
            m_changed = false;
            propagatePredictionsBackward();
        } while (m_changed);
    }
    
    void toDouble(NodeIndex nodeIndex)
    {
        if (m_graph[nodeIndex].op == ValueToNumber) {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
            printf("  @%u -> ValueToDouble", nodeIndex);
#endif
            m_graph[nodeIndex].op = ValueToDouble;
        }
    }
    
    void fixupNode(Node& node)
    {
        if (!node.shouldGenerate())
            return;
        
        NodeType op = node.op;

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("   %s @%u: ", Graph::opName(op), m_compileIndex);
#endif
        
        switch (op) {
        case ValueAdd: {
            if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
                toDouble(node.child1());
                toDouble(node.child2());
                break;
            }
            
            PredictedType left = m_graph[node.child1()].prediction();
            PredictedType right = m_graph[node.child2()].prediction();
            
            if (left && right && isNumberPrediction(left) && isNumberPrediction(right)) {
                if (left & PredictDouble)
                    toDouble(node.child2());
                if (right & PredictDouble)
                    toDouble(node.child1());
            }
            break;
        }
            
        case ArithAdd:
        case ArithSub:
        case ArithMul:
        case ArithMin:
        case ArithMax:
        case ArithMod:
        case ArithDiv: {
            if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
                toDouble(node.child1());
                toDouble(node.child2());
                break;
            }
            
            PredictedType left = m_graph[node.child1()].prediction();
            PredictedType right = m_graph[node.child2()].prediction();
            
            if (left && right) {
                if (left & PredictDouble)
                    toDouble(node.child2());
                if (right & PredictDouble)
                    toDouble(node.child1());
            }
            break;
        }
            
        case ArithAbs: {
            if (!nodeCanSpeculateInteger(node.arithNodeFlags())) {
                toDouble(node.child1());
                break;
            }
            
            PredictedType prediction = m_graph[node.child1()].prediction();
            if (prediction & PredictDouble)
                toDouble(node.child1());
            break;
        }
            
        case ArithSqrt: {
            toDouble(node.child1());
            break;
        }
            
        case GetById: {
            if (!isInt32Prediction(m_graph[m_compileIndex].prediction()))
                break;
            if (m_codeBlock->identifier(node.identifierNumber()) != m_globalData.propertyNames->length)
                break;
            bool isArray = isArrayPrediction(m_graph[node.child1()].prediction());
            bool isString = isStringPrediction(m_graph[node.child1()].prediction());
            bool isByteArray = m_graph[node.child1()].shouldSpeculateByteArray();
            bool isInt8Array = m_graph[node.child1()].shouldSpeculateInt8Array();
            bool isInt16Array = m_graph[node.child1()].shouldSpeculateInt16Array();
            bool isInt32Array = m_graph[node.child1()].shouldSpeculateInt32Array();
            bool isUint8Array = m_graph[node.child1()].shouldSpeculateUint8Array();
            bool isUint16Array = m_graph[node.child1()].shouldSpeculateUint16Array();
            bool isUint32Array = m_graph[node.child1()].shouldSpeculateUint32Array();
            bool isFloat32Array = m_graph[node.child1()].shouldSpeculateFloat32Array();
            bool isFloat64Array = m_graph[node.child1()].shouldSpeculateFloat64Array();
            if (!isArray && !isString && !isByteArray && !isInt8Array && !isInt16Array && !isInt32Array && !isUint8Array && !isUint16Array && !isUint32Array && !isFloat32Array && !isFloat64Array)
                break;
            
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
            printf("  @%u -> %s", m_compileIndex, isArray ? "GetArrayLength" : "GetStringLength");
#endif
            if (isArray)
                node.op = GetArrayLength;
            else if (isString)
                node.op = GetStringLength;
            else if (isByteArray)
                node.op = GetByteArrayLength;
            else if (isInt8Array)
                node.op = GetInt8ArrayLength;
            else if (isInt16Array)
                node.op = GetInt16ArrayLength;
            else if (isInt32Array)
                node.op = GetInt32ArrayLength;
            else if (isUint8Array)
                node.op = GetUint8ArrayLength;
            else if (isUint16Array)
                node.op = GetUint16ArrayLength;
            else if (isUint32Array)
                node.op = GetUint32ArrayLength;
            else if (isFloat32Array)
                node.op = GetFloat32ArrayLength;
            else if (isFloat64Array)
                node.op = GetFloat64ArrayLength;
            else
                ASSERT_NOT_REACHED();
            m_graph.deref(m_compileIndex); // No longer MustGenerate
            break;
        }
        case GetIndexedPropertyStorage: {
            PredictedType basePrediction = m_graph[node.child2()].prediction();
            if (!(basePrediction & PredictInt32) && basePrediction) {
                node.op = Nop;
                m_graph.clearAndDerefChild1(node);
                m_graph.clearAndDerefChild2(node);
                m_graph.clearAndDerefChild3(node);
                node.setRefCount(0);
            }
            break;
        }
        case GetByVal:
        case StringCharAt:
        case StringCharCodeAt: {
            if (node.child3() != NoNode && m_graph[node.child3()].op == Nop)
                node.children.fixed.child3 = NoNode;
            break;
        }
        default:
            break;
        }

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("\n");
#endif
    }
    
    void fixup()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("Performing Fixup\n");
#endif
        for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex)
            fixupNode(m_graph[m_compileIndex]);
    }
    
    NodeIndex canonicalize(NodeIndex nodeIndex)
    {
        if (nodeIndex == NoNode)
            return NoNode;
        
        if (m_graph[nodeIndex].op == ValueToNumber)
            nodeIndex = m_graph[nodeIndex].child1();
        
        if (m_graph[nodeIndex].op == ValueToInt32)
            nodeIndex = m_graph[nodeIndex].child1();
        
        return nodeIndex;
    }
    
    // Computes where the search for a candidate for CSE should start. Don't call
    // this directly; call startIndex() instead as it does logging in debug mode.
    NodeIndex computeStartIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
    {
        const unsigned limit = 300;
        
        NodeIndex start = m_start;
        if (m_compileIndex - start > limit)
            start = m_compileIndex - limit;
        
        ASSERT(start >= m_start);
        
        NodeIndex child = canonicalize(child1);
        if (child == NoNode)
            return start;
        
        if (start < child)
            start = child;
        
        child = canonicalize(child2);
        if (child == NoNode)
            return start;
        
        if (start < child)
            start = child;
        
        child = canonicalize(child3);
        if (child == NoNode)
            return start;
        
        if (start < child)
            start = child;
        
        return start;
    }
    
    NodeIndex startIndexForChildren(NodeIndex child1 = NoNode, NodeIndex child2 = NoNode, NodeIndex child3 = NoNode)
    {
        NodeIndex result = computeStartIndexForChildren(child1, child2, child3);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("  lookback %u: ", result);
#endif
        return result;
    }
    
    NodeIndex startIndex()
    {
        Node& node = m_graph[m_compileIndex];
        return startIndexForChildren(node.child1(), node.child2(), node.child3());
    }
    
    NodeIndex endIndexForPureCSE()
    {
        NodeIndex result = m_lastSeen[m_graph[m_compileIndex].op & NodeIdMask];
        if (result == NoNode)
            result = 0;
        else
            result++;
        ASSERT(result <= m_compileIndex);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("  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());
        
        NodeIndex start = startIndex();
        for (NodeIndex index = endIndexForPureCSE(); index-- > start;) {
            Node& otherNode = m_graph[index];
            if (node.op != otherNode.op)
                continue;
            
            if (node.arithNodeFlagsForCompare() != otherNode.arithNodeFlagsForCompare())
                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;
    }
    
    bool isPredictedNumerical(Node& node)
    {
        PredictedType left = m_graph[node.child1()].prediction();
        PredictedType right = m_graph[node.child2()].prediction();
        return isNumberPrediction(left) && isNumberPrediction(right);
    }
    
    bool logicalNotIsPure(Node& node)
    {
        PredictedType prediction = m_graph[node.child1()].prediction();
        return isBooleanPrediction(prediction) || !prediction;
    }
    
    bool byValIsPure(Node& node)
    {
        PredictedType prediction = m_graph[node.child2()].prediction();
        return (prediction & PredictInt32) || !prediction;
    }
    
    bool clobbersWorld(NodeIndex nodeIndex)
    {
        Node& node = m_graph[nodeIndex];
        if (node.op & NodeClobbersWorld)
            return true;
        if (!(node.op & NodeMightClobber))
            return false;
        switch (node.op) {
        case ValueAdd:
        case CompareLess:
        case CompareLessEq:
        case CompareGreater:
        case CompareGreaterEq:
        case CompareEq:
            return !isPredictedNumerical(node);
        case LogicalNot:
            return !logicalNotIsPure(node);
        case GetByVal:
            return !byValIsPure(node);
        default:
            ASSERT_NOT_REACHED();
            return true; // If by some oddity we hit this case in release build it's safer to have CSE assume the worst.
        }
    }
    
    NodeIndex impureCSE(Node& node)
    {
        NodeIndex child1 = canonicalize(node.child1());
        NodeIndex child2 = canonicalize(node.child2());
        NodeIndex child3 = canonicalize(node.child3());
        
        NodeIndex start = startIndex();
        for (NodeIndex index = m_compileIndex; index-- > start;) {
            Node& otherNode = m_graph[index];
            if (node.op == otherNode.op
                && node.arithNodeFlagsForCompare() == otherNode.arithNodeFlagsForCompare()) {
                NodeIndex otherChild = canonicalize(otherNode.child1());
                if (otherChild == NoNode)
                    return index;
                if (otherChild == child1) {
                    otherChild = canonicalize(otherNode.child2());
                    if (otherChild == NoNode)
                        return index;
                    if (otherChild == child2) {
                        otherChild = canonicalize(otherNode.child3());
                        if (otherChild == NoNode)
                            return index;
                        if (otherChild == child3)
                            return index;
                    }
                }
            }
            if (clobbersWorld(index))
                break;
        }
        return NoNode;
    }
    
    NodeIndex globalVarLoadElimination(unsigned varNumber, JSGlobalObject* globalObject)
    {
        NodeIndex start = startIndexForChildren();
        for (NodeIndex index = m_compileIndex; index-- > start;) {
            Node& node = m_graph[index];
            switch (node.op) {
            case GetGlobalVar:
                if (node.varNumber() == varNumber && m_codeBlock->globalObjectFor(node.codeOrigin) == globalObject)
                    return index;
                break;
            case PutGlobalVar:
                if (node.varNumber() == varNumber && m_codeBlock->globalObjectFor(node.codeOrigin) == globalObject)
                    return node.child1();
                break;
            default:
                break;
            }
            if (clobbersWorld(index))
                break;
        }
        return NoNode;
    }
    
    NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2)
    {
        NodeIndex start = startIndexForChildren(child1, child2);
        for (NodeIndex index = m_compileIndex; index-- > start;) {
            Node& node = m_graph[index];
            switch (node.op) {
            case GetByVal:
                if (!byValIsPure(node))
                    return NoNode;
                if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
                    return index;
                break;
            case PutByVal:
            case PutByValAlias:
                if (!byValIsPure(node))
                    return NoNode;
                if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2))
                    return node.child3();
                // 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;
            case ArrayPush:
                // A push cannot affect previously existing elements in the array.
                break;
            default:
                if (clobbersWorld(index))
                    return NoNode;
                break;
            }
        }
        return NoNode;
    }

    bool checkFunctionElimination(JSFunction* function, NodeIndex child1)
    {
        NodeIndex start = startIndexForChildren(child1);
        for (NodeIndex index = endIndexForPureCSE(); index-- > start;) {
            Node& node = m_graph[index];
            if (node.op == CheckFunction && node.child1() == child1 && node.function() == function)
                return true;
        }
        return false;
    }

    bool checkStructureLoadElimination(const StructureSet& structureSet, NodeIndex child1)
    {
        NodeIndex start = startIndexForChildren(child1);
        for (NodeIndex index = m_compileIndex; index-- > start;) {
            Node& node = m_graph[index];
            switch (node.op) {
            case CheckStructure:
                if (node.child1() == child1
                    && structureSet.isSupersetOf(node.structureSet()))
                    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 (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;
                
            default:
                if (clobbersWorld(index))
                    return false;
                break;
            }
        }
        return false;
    }
    
    NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1)
    {
        NodeIndex start = startIndexForChildren(child1);
        for (NodeIndex index = m_compileIndex; index-- > start;) {
            Node& node = m_graph[index];
            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.child2() == child1)
                        return node.child3();
                    return NoNode;
                }
                break;
                
            case PutStructure:
                // Changing the structure cannot change the outcome of a property get.
                break;
                
            case PutByVal:
            case PutByValAlias:
                if (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 (clobbersWorld(index))
                    return NoNode;
                break;
            }
        }
        return NoNode;
    }
    
    NodeIndex getPropertyStorageLoadElimination(NodeIndex child1)
    {
        NodeIndex start = startIndexForChildren(child1);
        for (NodeIndex index = m_compileIndex; index-- > start;) {
            Node& node = m_graph[index];
            switch (node.op) {
            case GetPropertyStorage:
                if (node.child1() == child1)
                    return index;
                break;
                
            case PutByOffset:
            case PutStructure:
                // Changing the structure or putting to the storage cannot
                // change the property storage pointer.
                break;
                
            case PutByVal:
            case PutByValAlias:
                if (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 (clobbersWorld(index))
                    return NoNode;
                break;
            }
        }
        return NoNode;
    }

    NodeIndex getIndexedPropertyStorageLoadElimination(NodeIndex child1, bool hasIntegerIndexPrediction)
    {
        NodeIndex start = startIndexForChildren(child1);
        for (NodeIndex index = m_compileIndex; index-- > start;) {
            Node& node = m_graph[index];
            switch (node.op) {
            case GetIndexedPropertyStorage: {
                PredictedType basePrediction = m_graph[node.child2()].prediction();
                bool nodeHasIntegerIndexPrediction = !(!(basePrediction & PredictInt32) && basePrediction);
                if (node.child1() == child1 && hasIntegerIndexPrediction == nodeHasIntegerIndexPrediction)
                    return index;
                break;
            }

            case PutByOffset:
            case PutStructure:
                // Changing the structure or putting to the storage cannot
                // change the property storage pointer.
                break;
                
            case PutByValAlias:
                // PutByValAlias can't change the indexed storage pointer
                break;
                
            case PutByVal:
                if (isFixedIndexedStorageObjectPrediction(m_graph[node.child1()].prediction()) && byValIsPure(node))
                    break;
                return NoNode;

            default:
                if (clobbersWorld(index))
                    return NoNode;
                break;
            }
        }
        return NoNode;
    }
    
    NodeIndex getScopeChainLoadElimination(unsigned depth)
    {
        NodeIndex start = startIndexForChildren();
        for (NodeIndex index = endIndexForPureCSE(); index-- > start;) {
            Node& node = m_graph[index];
            if (node.op == GetScopeChain
                && node.scopeChainDepth() == depth)
                return index;
        }
        return NoNode;
    }
    
    void performSubstitution(NodeIndex& child, bool addRef = true)
    {
        // Check if this operand is actually unused.
        if (child == NoNode)
            return;
        
        // Check if there is any replacement.
        NodeIndex replacement = m_replacements[child];
        if (replacement == NoNode)
            return;
        
        child = replacement;
        
        // There is definitely a replacement. Assert that the replacement does not
        // have a replacement.
        ASSERT(m_replacements[child] == NoNode);
        
        if (addRef)
            m_graph[child].ref();
    }
    
    void setReplacement(NodeIndex replacement)
    {
        if (replacement == NoNode)
            return;
        
        // Be safe. Don't try to perform replacements if the predictions don't
        // agree.
        if (m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction())
            return;
        
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("   Replacing @%u -> @%u", m_compileIndex, replacement);
#endif
        
        Node& node = m_graph[m_compileIndex];
        node.op = Phantom;
        node.setRefCount(1);
        
        // At this point we will eliminate all references to this node.
        m_replacements[m_compileIndex] = replacement;
    }
    
    void eliminate()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("   Eliminating @%u", m_compileIndex);
#endif
        
        Node& node = m_graph[m_compileIndex];
        ASSERT(node.refCount() == 1);
        ASSERT(node.mustGenerate());
        node.op = Phantom;
    }
    
    void performNodeCSE(Node& node)
    {
        bool shouldGenerate = node.shouldGenerate();

        if (node.op & NodeHasVarArgs) {
            for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
                performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate);
        } else {
            performSubstitution(node.children.fixed.child1, shouldGenerate);
            performSubstitution(node.children.fixed.child2, shouldGenerate);
            performSubstitution(node.children.fixed.child3, shouldGenerate);
        }
        
        if (!shouldGenerate)
            return;
        
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("   %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) {
        
        // 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 ArithMul:
        case ArithMod:
        case ArithDiv:
        case ArithAbs:
        case ArithMin:
        case ArithMax:
        case ArithSqrt:
        case GetByteArrayLength:
        case GetInt8ArrayLength:
        case GetInt16ArrayLength:
        case GetInt32ArrayLength:
        case GetUint8ArrayLength:
        case GetUint16ArrayLength:
        case GetUint32ArrayLength:
        case GetFloat32ArrayLength:
        case GetFloat64ArrayLength:
        case GetCallee:
        case GetStringLength:
        case StringCharAt:
        case StringCharCodeAt:
            setReplacement(pureCSE(node));
            break;
            
        case GetArrayLength:
            setReplacement(impureCSE(node));
            break;
            
        case GetScopeChain:
            setReplacement(getScopeChainLoadElimination(node.scopeChainDepth()));
            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 (isPredictedNumerical(node)) {
                NodeIndex replacementIndex = pureCSE(node);
                if (replacementIndex != NoNode && isPredictedNumerical(m_graph[replacementIndex]))
                    setReplacement(replacementIndex);
            }
            break;
        }
            
        case LogicalNot: {
            if (logicalNotIsPure(node)) {
                NodeIndex replacementIndex = pureCSE(node);
                if (replacementIndex != NoNode && logicalNotIsPure(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.varNumber(), m_codeBlock->globalObjectFor(node.codeOrigin)));
            break;
            
        case GetByVal:
            if (byValIsPure(node))
                setReplacement(getByValLoadElimination(node.child1(), node.child2()));
            break;
            
        case PutByVal:
            if (byValIsPure(node) && getByValLoadElimination(node.child1(), node.child2()) != NoNode)
                node.op = PutByValAlias;
            break;
            
        case CheckStructure:
            if (checkStructureLoadElimination(node.structureSet(), node.child1()))
                eliminate();
            break;

        case CheckFunction:
            if (checkFunctionElimination(node.function(), node.child1()))
                eliminate();
            break;
                
        case GetIndexedPropertyStorage: {
            PredictedType basePrediction = m_graph[node.child2()].prediction();
            bool nodeHasIntegerIndexPrediction = !(!(basePrediction & PredictInt32) && basePrediction);
            setReplacement(getIndexedPropertyStorageLoadElimination(node.child1(), nodeHasIntegerIndexPrediction));
            break;
        }

        case GetPropertyStorage:
            setReplacement(getPropertyStorageLoadElimination(node.child1()));
            break;

        case GetByOffset:
            setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1()));
            break;
            
        default:
            // do nothing.
            break;
        }
        
        m_lastSeen[node.op & NodeIdMask] = m_compileIndex;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("\n");
#endif
    }
    
    void performBlockCSE(BasicBlock& block)
    {
        m_start = block.begin;
        NodeIndex end = block.end;
        for (m_compileIndex = m_start; m_compileIndex < end; ++m_compileIndex)
            performNodeCSE(m_graph[m_compileIndex]);
    }
    
    void localCSE()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("Performing local CSE:");
#endif
        for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block)
            performBlockCSE(*m_graph.m_blocks[block]);
    }
    
    void allocateVirtualRegisters()
    {
#if DFG_ENABLE(DEBUG_VERBOSE)
        printf("Preserved vars: ");
        m_graph.m_preservedVars.dump(stdout);
        printf("\n");
#endif
        ScoreBoard scoreBoard(m_graph, m_graph.m_preservedVars);
        unsigned sizeExcludingPhiNodes = m_graph.m_blocks.last()->end;
        for (size_t i = 0; i < sizeExcludingPhiNodes; ++i) {
            Node& node = m_graph[i];
        
            if (!node.shouldGenerate())
                continue;
        
            // GetLocal nodes are effectively phi nodes in the graph, referencing
            // results from prior blocks.
            if (node.op != GetLocal) {
                // First, call use on all of the current node's children, then
                // allocate a VirtualRegister for this node. We do so in this
                // order so that if a child is on its last use, and a
                // VirtualRegister is freed, then it may be reused for node.
                if (node.op & NodeHasVarArgs) {
                    for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)
                        scoreBoard.use(m_graph.m_varArgChildren[childIdx]);
                } else {
                    scoreBoard.use(node.child1());
                    scoreBoard.use(node.child2());
                    scoreBoard.use(node.child3());
                }
            }

            if (!node.hasResult())
                continue;

            node.setVirtualRegister(scoreBoard.allocate());
            // 'mustGenerate' nodes have their useCount artificially elevated,
            // call use now to account for this.
            if (node.mustGenerate())
                scoreBoard.use(i);
        }

        // 'm_numCalleeRegisters' is the number of locals and temporaries allocated
        // for the function (and checked for on entry). Since we perform a new and
        // different allocation of temporaries, more registers may now be required.
        unsigned calleeRegisters = scoreBoard.highWatermark() + m_graph.m_parameterSlots;
        if ((unsigned)m_codeBlock->m_numCalleeRegisters < calleeRegisters)
            m_codeBlock->m_numCalleeRegisters = calleeRegisters;
#if DFG_ENABLE(DEBUG_VERBOSE)
        printf("Num callee registers: %u\n", calleeRegisters);
#endif
    }
    
    void performBlockCFA(AbstractState& state, BlockIndex blockIndex)
    {
        BasicBlock* block = m_graph.m_blocks[blockIndex].get();
        if (!block->cfaShouldRevisit)
            return;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("   Block #%u (bc#%u):\n", blockIndex, block->bytecodeBegin);
#endif
        state.beginBasicBlock(block);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("      head vars: ");
        dumpOperands(block->valuesAtHead, stdout);
        printf("\n");
#endif
        for (NodeIndex nodeIndex = block->begin; nodeIndex < block->end; ++nodeIndex) {
            if (!m_graph[nodeIndex].shouldGenerate())
                continue;
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
            printf("      %s @%u: ", Graph::opName(m_graph[nodeIndex].op), nodeIndex);
            state.dump(stdout);
            printf("\n");
#endif
            if (!state.execute(nodeIndex))
                break;
        }
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("      tail regs: ");
        state.dump(stdout);
        printf("\n");
#endif
        m_changed |= state.endBasicBlock(AbstractState::MergeToSuccessors);
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("      tail vars: ");
        dumpOperands(block->valuesAtTail, stdout);
        printf("\n");
#endif
    }
    
    void performForwardCFA(AbstractState& state)
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        printf("CFA [%u]\n", ++m_count);
#endif
        
        for (BlockIndex block = 0; block < m_graph.m_blocks.size(); ++block)
            performBlockCFA(state, block);
    }
    
    void globalCFA()
    {
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
        m_count = 0;
#endif
        
        // This implements a pseudo-worklist-based forward CFA, except that the visit order
        // of blocks is the bytecode program order (which is nearly topological), and
        // instead of a worklist we just walk all basic blocks checking if cfaShouldRevisit
        // is set to true. This is likely to balance the efficiency properties of both
        // worklist-based and forward fixpoint-based approaches. Like a worklist-based
        // approach, it won't visit code if it's meaningless to do so (nothing changed at
        // the head of the block or the predecessors have not been visited). Like a forward
        // fixpoint-based approach, it has a high probability of only visiting a block
        // after all predecessors have been visited. Only loops will cause this analysis to
        // revisit blocks, and the amount of revisiting is proportional to loop depth.
        
        AbstractState::initialize(m_graph);
        
        AbstractState state(m_codeBlock, m_graph);
        
        do {
            m_changed = false;
            performForwardCFA(state);
        } while (m_changed);
    }
    
    Graph& m_graph;
    JSGlobalData& m_globalData;
    CodeBlock* m_codeBlock;
    CodeBlock* m_profiledBlock;
    
    NodeIndex m_start;
    NodeIndex m_compileIndex;
    
#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)
    unsigned m_count;
#endif
    
    bool m_changed;

    Vector<NodeIndex, 16> m_replacements;
    FixedArray<NodeIndex, LastNodeId> m_lastSeen;
};

void propagate(Graph& graph, JSGlobalData* globalData, CodeBlock* codeBlock)
{
    ASSERT(codeBlock);
    CodeBlock* profiledBlock = codeBlock->alternative();
    ASSERT(profiledBlock);
    
    Propagator propagator(graph, *globalData, codeBlock, profiledBlock);
    propagator.fixpoint();
    
}

} } // namespace JSC::DFG

#endif // ENABLE(DFG_JIT)