/*

* 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)

dataLog("Graph after propagation fixup:\n");

m_graph.dump(m_codeBlock);

#endif

localCSE();

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)

dataLog("Graph after CSE:\n");

m_graph.dump(m_codeBlock);

#endif

allocateVirtualRegisters();

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)

dataLog("Graph after virtual register allocation:\n");

m_graph.dump(m_codeBlock);

#endif

globalCFA();

#if DFG_ENABLE(DEBUG_VERBOSE)

dataLog("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)

dataLog(" %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 UInt32ToNumber: {

changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);

break;

}

case ArithAdd:

case ValueAdd: {

if (isNotNegZero(node.child1().index()) || isNotNegZero(node.child2().index()))

flags &= ~NodeNeedsNegZero;

changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);

changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);

break;

}

case ArithSub: {

if (isNotZero(node.child1().index()) || isNotZero(node.child2().index()))

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())

break;

changed |= m_graph[node.child1()].mergeArithNodeFlags(flags);

if (!node.child2())

break;

changed |= m_graph[node.child2()].mergeArithNodeFlags(flags);

if (!node.child3())

break;

changed |= m_graph[node.child3()].mergeArithNodeFlags(flags);

}

break;

}

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)

dataLog("%s\n", changed ? "CHANGED" : "");

#endif

m_changed |= changed;

}

void propagateArithNodeFlagsForward()

{

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)

dataLog("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)

dataLog("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)

dataLog(" %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 ValueAdd: {

PredictedType left = m_graph[node.child1()].prediction();

PredictedType right = m_graph[node.child2()].prediction();

if (left && right) {

if (isNumberPrediction(left) && isNumberPrediction(right)) {

if (m_graph.addShouldSpeculateInteger(node, m_codeBlock))

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: {

PredictedType left = m_graph[node.child1()].prediction();

PredictedType right = m_graph[node.child2()].prediction();

if (left && right) {

if (m_graph.addShouldSpeculateInteger(node, m_codeBlock))

changed |= mergePrediction(PredictInt32);

else

changed |= mergePrediction(PredictDouble);

}

break;

}

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 isUint8ClampedArray = m_graph[node.child1()].shouldSpeculateUint8ClampedArray();

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 || isUint8ClampedArray || 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 GetArrayLength:

case GetByteArrayLength:

case GetInt8ArrayLength:

case GetInt16ArrayLength:

case GetInt32ArrayLength:

case GetUint8ArrayLength:

case GetUint8ClampedArrayLength:

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)

dataLog("%s\n", predictionToString(m_graph[m_compileIndex].prediction()));

#endif

m_changed |= changed;

}

void propagatePredictionsForward()

{

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)

dataLog("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)

dataLog("Propagating predictions backward [%u]\n", ++m_count);

#endif

for (m_compileIndex = m_graph.size(); m_compileIndex-- > 0;)

propagateNodePredictions(m_graph[m_compileIndex]);

}

void vote(NodeUse nodeUse, VariableAccessData::Ballot ballot)

{

switch (m_graph[nodeUse].op) {

case ValueToInt32:

case UInt32ToNumber:

nodeUse = m_graph[nodeUse].child1();

break;

default:

break;

}

if (m_graph[nodeUse].op == GetLocal)

m_graph[nodeUse].variableAccessData()->vote(ballot);

}

void vote(Node& node, VariableAccessData::Ballot ballot)

{

if (node.op & NodeHasVarArgs) {

for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++)

vote(m_graph.m_varArgChildren[childIdx], ballot);

return;

}

if (!node.child1())

return;

vote(node.child1(), ballot);

if (!node.child2())

return;

vote(node.child2(), ballot);

if (!node.child3())

return;

vote(node.child3(), ballot);

}

void doRoundOfDoubleVoting()

{

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)

dataLog("Voting on double uses of locals [%u]\n", m_count);

#endif

for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)

m_graph.m_variableAccessData[i].find()->clearVotes();

for (m_compileIndex = 0; m_compileIndex < m_graph.size(); ++m_compileIndex) {

Node& node = m_graph[m_compileIndex];

switch (node.op) {

case ValueAdd:

case ArithAdd:

case ArithSub: {

PredictedType left = m_graph[node.child1()].prediction();

PredictedType right = m_graph[node.child2()].prediction();

VariableAccessData::Ballot ballot;

if (isNumberPrediction(left) && isNumberPrediction(right)

&& !m_graph.addShouldSpeculateInteger(node, m_codeBlock))

ballot = VariableAccessData::VoteDouble;

else

ballot = VariableAccessData::VoteValue;

vote(node.child1(), ballot);

vote(node.child2(), ballot);

break;

}

case ArithMul:

case ArithMin:

case ArithMax:

case ArithMod:

case ArithDiv: {

PredictedType left = m_graph[node.child1()].prediction();

PredictedType right = m_graph[node.child2()].prediction();

VariableAccessData::Ballot ballot;

if (isNumberPrediction(left) && isNumberPrediction(right) && !(Node::shouldSpeculateInteger(m_graph[node.child1()], m_graph[node.child1()]) && node.canSpeculateInteger()))

ballot = VariableAccessData::VoteDouble;

else

ballot = VariableAccessData::VoteValue;

vote(node.child1(), ballot);

vote(node.child2(), ballot);

break;

}

case ArithAbs:

VariableAccessData::Ballot ballot;

if (!(m_graph[node.child1()].shouldSpeculateInteger() && node.canSpeculateInteger()))

ballot = VariableAccessData::VoteDouble;

else

ballot = VariableAccessData::VoteValue;

vote(node.child1(), ballot);

break;

case ArithSqrt:

vote(node.child1(), VariableAccessData::VoteDouble);

break;

case SetLocal: {

PredictedType prediction = m_graph[node.child1()].prediction();

if (isDoublePrediction(prediction))

node.variableAccessData()->vote(VariableAccessData::VoteDouble);

else if (!isNumberPrediction(prediction) || isInt32Prediction(prediction))

node.variableAccessData()->vote(VariableAccessData::VoteValue);

break;

}

default:

vote(node, VariableAccessData::VoteValue);

break;

}

}

for (unsigned i = 0; i < m_graph.m_variableAccessData.size(); ++i)

m_changed |= m_graph.m_variableAccessData[i].find()->tallyVotesForShouldUseDoubleFormat();

}

void propagatePredictions()

{

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)

m_count = 0;

#endif

// Two stage process: first propagate predictions, then propagate while doing double voting.

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

do {

m_changed = false;

doRoundOfDoubleVoting();

propagatePredictionsForward();

if (!m_changed)

break;

m_changed = false;

doRoundOfDoubleVoting();

propagatePredictionsBackward();

} while (m_changed);

}

void fixupNode(Node& node)

{

if (!node.shouldGenerate())

return;

NodeType op = node.op;

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)

dataLog(" %s @%u: ", Graph::opName(op), m_compileIndex);

#endif

switch (op) {

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 isUint8ClampedArray = m_graph[node.child1()].shouldSpeculateUint8ClampedArray();

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 && !isUint8ClampedArray && !isUint16Array && !isUint32Array && !isFloat32Array && !isFloat64Array)

break;

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)

dataLog(" @%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 (isUint8ClampedArray)

node.op = GetUint8ClampedArrayLength;

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() && m_graph[node.child3()].op == Nop)

node.children.child3() = NodeUse();

break;

}

default:

break;

}

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)

dataLog("\n");

#endif

}

void fixup()

{

#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE)

dataLog("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 == ValueToInt32)

nodeIndex = m_graph[nodeIndex].child1().index();

return nodeIndex;

}

NodeIndex canonicalize(NodeUse nodeUse)

{

return canonicalize(nodeUse.indexUnchecked());

}

// 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)

dataLog(" lookback %u: ", result);

#endif

return result;

}

NodeIndex startIndex()

{

Node& node = m_graph[m_compileIndex];

return startIndexForChildren(

node.child1().indexUnchecked(),

node.child2().indexUnchecked(),

node.child3().indexUnchecked());

}

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)

dataLog(" limit %u: ", result);

#endif

return result;

}

NodeIndex pureCSE(Node& node)

{

NodeIndex child1 = canonicalize(node.child1());