X-Git-Url: https://git.saurik.com/apple/javascriptcore.git/blobdiff_plain/1df5f87f1309a8daa30dabdee855f48ae40d14ab..6fe7ccc865dc7d7541b93c5bcaf6368d2c98a174:/dfg/DFGAbstractState.cpp?ds=sidebyside diff --git a/dfg/DFGAbstractState.cpp b/dfg/DFGAbstractState.cpp new file mode 100644 index 0000000..6df40ca --- /dev/null +++ b/dfg/DFGAbstractState.cpp @@ -0,0 +1,1219 @@ +/* + * 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 "DFGAbstractState.h" + +#if ENABLE(DFG_JIT) + +#include "CodeBlock.h" +#include "DFGBasicBlock.h" + +namespace JSC { namespace DFG { + +#define CFA_PROFILING 0 + +#if CFA_PROFILING +#define PROFILE(flag) SamplingFlags::ScopedFlag scopedFlag(flag) +#else +#define PROFILE(flag) do { } while (false) +#endif + +// Profiling flags +#define FLAG_FOR_BLOCK_INITIALIZATION 17 +#define FLAG_FOR_BLOCK_END 18 +#define FLAG_FOR_EXECUTION 19 +#define FLAG_FOR_MERGE_TO_SUCCESSORS 20 +#define FLAG_FOR_STRUCTURE_CLOBBERING 21 + +AbstractState::AbstractState(Graph& graph) + : m_codeBlock(graph.m_codeBlock) + , m_graph(graph) + , m_variables(m_codeBlock->numParameters(), graph.m_localVars) + , m_block(0) +{ + m_nodes.resize(graph.size()); +} + +AbstractState::~AbstractState() { } + +void AbstractState::beginBasicBlock(BasicBlock* basicBlock) +{ + PROFILE(FLAG_FOR_BLOCK_INITIALIZATION); + + ASSERT(!m_block); + + ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->valuesAtHead.numberOfLocals()); + ASSERT(basicBlock->variablesAtTail.numberOfLocals() == basicBlock->valuesAtTail.numberOfLocals()); + ASSERT(basicBlock->variablesAtHead.numberOfLocals() == basicBlock->variablesAtTail.numberOfLocals()); + + for (size_t i = 0; i < basicBlock->size(); i++) + m_nodes[basicBlock->at(i)].clear(); + + m_variables = basicBlock->valuesAtHead; + m_haveStructures = false; + for (size_t i = 0; i < m_variables.numberOfArguments(); ++i) { + if (m_variables.argument(i).m_structure.isNeitherClearNorTop()) { + m_haveStructures = true; + break; + } + } + for (size_t i = 0; i < m_variables.numberOfLocals(); ++i) { + if (m_variables.local(i).m_structure.isNeitherClearNorTop()) { + m_haveStructures = true; + break; + } + } + + basicBlock->cfaShouldRevisit = false; + basicBlock->cfaHasVisited = true; + m_block = basicBlock; + m_isValid = true; +} + +void AbstractState::initialize(Graph& graph) +{ + PROFILE(FLAG_FOR_BLOCK_INITIALIZATION); + BasicBlock* root = graph.m_blocks[0].get(); + root->cfaShouldRevisit = true; + for (size_t i = 0; i < root->valuesAtHead.numberOfArguments(); ++i) { + Node& node = graph[root->variablesAtHead.argument(i)]; + ASSERT(node.op() == SetArgument); + if (!node.shouldGenerate()) { + // The argument is dead. We don't do any checks for such arguments, and so + // for the purpose of the analysis, they contain no value. + root->valuesAtHead.argument(i).clear(); + continue; + } + + if (graph.argumentIsCaptured(i)) { + root->valuesAtHead.argument(i).makeTop(); + continue; + } + + PredictedType prediction = node.variableAccessData()->prediction(); + if (isInt32Prediction(prediction)) + root->valuesAtHead.argument(i).set(PredictInt32); + else if (isArrayPrediction(prediction)) + root->valuesAtHead.argument(i).set(PredictArray); + else if (isBooleanPrediction(prediction)) + root->valuesAtHead.argument(i).set(PredictBoolean); + else if (isInt8ArrayPrediction(prediction)) + root->valuesAtHead.argument(i).set(PredictInt8Array); + else if (isInt16ArrayPrediction(prediction)) + root->valuesAtHead.argument(i).set(PredictInt16Array); + else if (isInt32ArrayPrediction(prediction)) + root->valuesAtHead.argument(i).set(PredictInt32Array); + else if (isUint8ArrayPrediction(prediction)) + root->valuesAtHead.argument(i).set(PredictUint8Array); + else if (isUint8ClampedArrayPrediction(prediction)) + root->valuesAtHead.argument(i).set(PredictUint8ClampedArray); + else if (isUint16ArrayPrediction(prediction)) + root->valuesAtHead.argument(i).set(PredictUint16Array); + else if (isUint32ArrayPrediction(prediction)) + root->valuesAtHead.argument(i).set(PredictUint32Array); + else if (isFloat32ArrayPrediction(prediction)) + root->valuesAtHead.argument(i).set(PredictFloat32Array); + else if (isFloat64ArrayPrediction(prediction)) + root->valuesAtHead.argument(i).set(PredictFloat64Array); + else + root->valuesAtHead.argument(i).makeTop(); + } + for (size_t i = 0; i < root->valuesAtHead.numberOfLocals(); ++i) { + if (!graph.localIsCaptured(i)) + continue; + root->valuesAtHead.local(i).makeTop(); + } +} + +bool AbstractState::endBasicBlock(MergeMode mergeMode) +{ + PROFILE(FLAG_FOR_BLOCK_END); + ASSERT(m_block); + + BasicBlock* block = m_block; // Save the block for successor merging. + + if (!m_isValid) { + reset(); + return false; + } + + bool changed = false; + + if (mergeMode != DontMerge || !ASSERT_DISABLED) { + for (size_t argument = 0; argument < block->variablesAtTail.numberOfArguments(); ++argument) { +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" Merging state for argument %zu.\n", argument); +#endif + AbstractValue& destination = block->valuesAtTail.argument(argument); + if (m_graph.argumentIsCaptured(argument)) { + if (!destination.isTop()) { + destination.makeTop(); + changed = true; + } + } else + changed |= mergeStateAtTail(destination, m_variables.argument(argument), block->variablesAtTail.argument(argument)); + } + + for (size_t local = 0; local < block->variablesAtTail.numberOfLocals(); ++local) { +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" Merging state for local %zu.\n", local); +#endif + AbstractValue& destination = block->valuesAtTail.local(local); + if (m_graph.localIsCaptured(local)) { + if (!destination.isTop()) { + destination.makeTop(); + changed = true; + } + } else + changed |= mergeStateAtTail(destination, m_variables.local(local), block->variablesAtTail.local(local)); + } + } + + ASSERT(mergeMode != DontMerge || !changed); + + reset(); + + if (mergeMode != MergeToSuccessors) + return changed; + + return mergeToSuccessors(m_graph, block); +} + +void AbstractState::reset() +{ + m_block = 0; + m_isValid = false; +} + +bool AbstractState::execute(unsigned indexInBlock) +{ + PROFILE(FLAG_FOR_EXECUTION); + ASSERT(m_block); + ASSERT(m_isValid); + + NodeIndex nodeIndex = m_block->at(indexInBlock); + Node& node = m_graph[nodeIndex]; + + if (!node.shouldGenerate()) + return true; + + switch (node.op()) { + case JSConstant: + case WeakJSConstant: { + JSValue value = m_graph.valueOfJSConstant(nodeIndex); + // Have to be careful here! It's tempting to call set(value), but + // that would be wrong, since that would constitute a proof that this + // value will always have the same structure. The whole point of a value + // having a structure is that it may change in the future - for example + // between when we compile the code and when we run it. + forNode(nodeIndex).set(predictionFromValue(value)); + break; + } + + case GetLocal: { + if (m_graph.isCaptured(node.local())) + forNode(nodeIndex).makeTop(); + else + forNode(nodeIndex) = m_variables.operand(node.local()); + break; + } + + case SetLocal: { + if (m_graph.isCaptured(node.local())) + break; + + if (node.variableAccessData()->shouldUseDoubleFormat()) { + forNode(node.child1()).filter(PredictNumber); + m_variables.operand(node.local()).set(PredictDouble); + break; + } + + PredictedType predictedType = node.variableAccessData()->argumentAwarePrediction(); + if (isInt32Prediction(predictedType)) + forNode(node.child1()).filter(PredictInt32); + else if (isArrayPrediction(predictedType)) + forNode(node.child1()).filter(PredictArray); + else if (isBooleanPrediction(predictedType)) + forNode(node.child1()).filter(PredictBoolean); + + m_variables.operand(node.local()) = forNode(node.child1()); + break; + } + + case SetArgument: + // Assert that the state of arguments has been set. + ASSERT(!m_block->valuesAtHead.operand(node.local()).isClear()); + break; + + case BitAnd: + case BitOr: + case BitXor: + case BitRShift: + case BitLShift: + case BitURShift: + forNode(node.child1()).filter(PredictInt32); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + + case UInt32ToNumber: + if (!node.canSpeculateInteger()) + forNode(nodeIndex).set(PredictDouble); + else + forNode(nodeIndex).set(PredictInt32); + break; + + case DoubleAsInt32: + forNode(node.child1()).filter(PredictNumber); + forNode(nodeIndex).set(PredictInt32); + break; + + case ValueToInt32: + if (m_graph[node.child1()].shouldSpeculateInteger()) + forNode(node.child1()).filter(PredictInt32); + else if (m_graph[node.child1()].shouldSpeculateNumber()) + forNode(node.child1()).filter(PredictNumber); + else if (m_graph[node.child1()].shouldSpeculateBoolean()) + forNode(node.child1()).filter(PredictBoolean); + + forNode(nodeIndex).set(PredictInt32); + break; + + case Int32ToDouble: + forNode(node.child1()).filter(PredictNumber); + forNode(nodeIndex).set(PredictDouble); + break; + + case CheckNumber: + forNode(node.child1()).filter(PredictNumber); + break; + + case ValueAdd: + case ArithAdd: { + if (m_graph.addShouldSpeculateInteger(node)) { + forNode(node.child1()).filter(PredictInt32); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + if (Node::shouldSpeculateNumber(m_graph[node.child1()], m_graph[node.child2()])) { + forNode(node.child1()).filter(PredictNumber); + forNode(node.child2()).filter(PredictNumber); + forNode(nodeIndex).set(PredictDouble); + break; + } + if (node.op() == ValueAdd) { + clobberStructures(indexInBlock); + forNode(nodeIndex).set(PredictString | PredictInt32 | PredictNumber); + break; + } + // We don't handle this yet. :-( + m_isValid = false; + break; + } + + case ArithSub: { + if (m_graph.addShouldSpeculateInteger(node)) { + forNode(node.child1()).filter(PredictInt32); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + forNode(node.child1()).filter(PredictNumber); + forNode(node.child2()).filter(PredictNumber); + forNode(nodeIndex).set(PredictDouble); + break; + } + + case ArithNegate: { + if (m_graph.negateShouldSpeculateInteger(node)) { + forNode(node.child1()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + forNode(node.child1()).filter(PredictNumber); + forNode(nodeIndex).set(PredictDouble); + break; + } + + case ArithMul: + case ArithDiv: + case ArithMin: + case ArithMax: + case ArithMod: { + if (Node::shouldSpeculateInteger(m_graph[node.child1()], m_graph[node.child2()]) && node.canSpeculateInteger()) { + forNode(node.child1()).filter(PredictInt32); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + forNode(node.child1()).filter(PredictNumber); + forNode(node.child2()).filter(PredictNumber); + forNode(nodeIndex).set(PredictDouble); + break; + } + + case ArithAbs: + if (m_graph[node.child1()].shouldSpeculateInteger() && node.canSpeculateInteger()) { + forNode(node.child1()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + forNode(node.child1()).filter(PredictNumber); + forNode(nodeIndex).set(PredictDouble); + break; + + case ArithSqrt: + forNode(node.child1()).filter(PredictNumber); + forNode(nodeIndex).set(PredictDouble); + break; + + case LogicalNot: { + Node& child = m_graph[node.child1()]; + if (isBooleanPrediction(child.prediction())) + forNode(node.child1()).filter(PredictBoolean); + else if (child.shouldSpeculateFinalObjectOrOther()) + forNode(node.child1()).filter(PredictFinalObject | PredictOther); + else if (child.shouldSpeculateArrayOrOther()) + forNode(node.child1()).filter(PredictArray | PredictOther); + else if (child.shouldSpeculateInteger()) + forNode(node.child1()).filter(PredictInt32); + else if (child.shouldSpeculateNumber()) + forNode(node.child1()).filter(PredictNumber); + else + clobberStructures(indexInBlock); + forNode(nodeIndex).set(PredictBoolean); + break; + } + + case IsUndefined: + case IsBoolean: + case IsNumber: + case IsString: + case IsObject: + case IsFunction: { + forNode(nodeIndex).set(PredictBoolean); + break; + } + + case CompareLess: + case CompareLessEq: + case CompareGreater: + case CompareGreaterEq: + case CompareEq: { + forNode(nodeIndex).set(PredictBoolean); + + Node& left = m_graph[node.child1()]; + Node& right = m_graph[node.child2()]; + PredictedType filter; + if (Node::shouldSpeculateInteger(left, right)) + filter = PredictInt32; + else if (Node::shouldSpeculateNumber(left, right)) + filter = PredictNumber; + else if (node.op() == CompareEq) { + if ((m_graph.isConstant(node.child1().index()) + && m_graph.valueOfJSConstant(node.child1().index()).isNull()) + || (m_graph.isConstant(node.child2().index()) + && m_graph.valueOfJSConstant(node.child2().index()).isNull())) { + // We know that this won't clobber the world. But that's all we know. + break; + } + + if (Node::shouldSpeculateFinalObject(left, right)) + filter = PredictFinalObject; + else if (Node::shouldSpeculateArray(left, right)) + filter = PredictArray; + else if (left.shouldSpeculateFinalObject() && right.shouldSpeculateFinalObjectOrOther()) { + forNode(node.child1()).filter(PredictFinalObject); + forNode(node.child2()).filter(PredictFinalObject | PredictOther); + break; + } else if (right.shouldSpeculateFinalObject() && left.shouldSpeculateFinalObjectOrOther()) { + forNode(node.child1()).filter(PredictFinalObject | PredictOther); + forNode(node.child2()).filter(PredictFinalObject); + break; + } else if (left.shouldSpeculateArray() && right.shouldSpeculateArrayOrOther()) { + forNode(node.child1()).filter(PredictFinalObject); + forNode(node.child2()).filter(PredictFinalObject | PredictOther); + break; + } else if (right.shouldSpeculateArray() && left.shouldSpeculateArrayOrOther()) { + forNode(node.child1()).filter(PredictFinalObject | PredictOther); + forNode(node.child2()).filter(PredictFinalObject); + break; + } else { + filter = PredictTop; + clobberStructures(indexInBlock); + } + } else { + filter = PredictTop; + clobberStructures(indexInBlock); + } + forNode(node.child1()).filter(filter); + forNode(node.child2()).filter(filter); + break; + } + + case CompareStrictEq: + forNode(nodeIndex).set(PredictBoolean); + break; + + case StringCharCodeAt: + forNode(node.child1()).filter(PredictString); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + + case StringCharAt: + forNode(node.child1()).filter(PredictString); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictString); + break; + + case GetByVal: { + if (!node.prediction() || !m_graph[node.child1()].prediction() || !m_graph[node.child2()].prediction()) { + m_isValid = false; + break; + } + if (!isActionableArrayPrediction(m_graph[node.child1()].prediction()) || !m_graph[node.child2()].shouldSpeculateInteger()) { + clobberStructures(indexInBlock); + forNode(nodeIndex).makeTop(); + break; + } + if (m_graph[node.child1()].prediction() == PredictString) { + forNode(node.child1()).filter(PredictString); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictString); + break; + } + + if (m_graph[node.child1()].shouldSpeculateInt8Array()) { + forNode(node.child1()).filter(PredictInt8Array); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + if (m_graph[node.child1()].shouldSpeculateInt16Array()) { + forNode(node.child1()).filter(PredictInt16Array); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + if (m_graph[node.child1()].shouldSpeculateInt32Array()) { + forNode(node.child1()).filter(PredictInt32Array); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint8Array()) { + forNode(node.child1()).filter(PredictUint8Array); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint8ClampedArray()) { + forNode(node.child1()).filter(PredictUint8ClampedArray); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint16Array()) { + forNode(node.child1()).filter(PredictUint16Array); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint32Array()) { + forNode(node.child1()).filter(PredictUint32Array); + forNode(node.child2()).filter(PredictInt32); + if (node.shouldSpeculateInteger()) + forNode(nodeIndex).set(PredictInt32); + else + forNode(nodeIndex).set(PredictDouble); + break; + } + if (m_graph[node.child1()].shouldSpeculateFloat32Array()) { + forNode(node.child1()).filter(PredictFloat32Array); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictDouble); + break; + } + if (m_graph[node.child1()].shouldSpeculateFloat64Array()) { + forNode(node.child1()).filter(PredictFloat64Array); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).set(PredictDouble); + break; + } + ASSERT(m_graph[node.child1()].shouldSpeculateArray()); + forNode(node.child1()).filter(PredictArray); + forNode(node.child2()).filter(PredictInt32); + forNode(nodeIndex).makeTop(); + break; + } + + case PutByVal: + case PutByValAlias: { + if (!m_graph[node.child1()].prediction() || !m_graph[node.child2()].prediction()) { + m_isValid = false; + break; + } + if (!m_graph[node.child2()].shouldSpeculateInteger() || !isActionableMutableArrayPrediction(m_graph[node.child1()].prediction())) { + ASSERT(node.op() == PutByVal); + clobberStructures(indexInBlock); + forNode(nodeIndex).makeTop(); + break; + } + + if (m_graph[node.child1()].shouldSpeculateInt8Array()) { + forNode(node.child1()).filter(PredictInt8Array); + forNode(node.child2()).filter(PredictInt32); + if (m_graph[node.child3()].shouldSpeculateInteger()) + forNode(node.child3()).filter(PredictInt32); + else + forNode(node.child3()).filter(PredictNumber); + break; + } + if (m_graph[node.child1()].shouldSpeculateInt16Array()) { + forNode(node.child1()).filter(PredictInt16Array); + forNode(node.child2()).filter(PredictInt32); + if (m_graph[node.child3()].shouldSpeculateInteger()) + forNode(node.child3()).filter(PredictInt32); + else + forNode(node.child3()).filter(PredictNumber); + break; + } + if (m_graph[node.child1()].shouldSpeculateInt32Array()) { + forNode(node.child1()).filter(PredictInt32Array); + forNode(node.child2()).filter(PredictInt32); + if (m_graph[node.child3()].shouldSpeculateInteger()) + forNode(node.child3()).filter(PredictInt32); + else + forNode(node.child3()).filter(PredictNumber); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint8Array()) { + forNode(node.child1()).filter(PredictUint8Array); + forNode(node.child2()).filter(PredictInt32); + if (m_graph[node.child3()].shouldSpeculateInteger()) + forNode(node.child3()).filter(PredictInt32); + else + forNode(node.child3()).filter(PredictNumber); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint8ClampedArray()) { + forNode(node.child1()).filter(PredictUint8ClampedArray); + forNode(node.child2()).filter(PredictInt32); + if (m_graph[node.child3()].shouldSpeculateInteger()) + forNode(node.child3()).filter(PredictInt32); + else + forNode(node.child3()).filter(PredictNumber); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint16Array()) { + forNode(node.child1()).filter(PredictUint16Array); + forNode(node.child2()).filter(PredictInt32); + if (m_graph[node.child3()].shouldSpeculateInteger()) + forNode(node.child3()).filter(PredictInt32); + else + forNode(node.child3()).filter(PredictNumber); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint32Array()) { + forNode(node.child1()).filter(PredictUint32Array); + forNode(node.child2()).filter(PredictInt32); + if (m_graph[node.child3()].shouldSpeculateInteger()) + forNode(node.child3()).filter(PredictInt32); + else + forNode(node.child3()).filter(PredictNumber); + break; + } + if (m_graph[node.child1()].shouldSpeculateFloat32Array()) { + forNode(node.child1()).filter(PredictFloat32Array); + forNode(node.child2()).filter(PredictInt32); + forNode(node.child3()).filter(PredictNumber); + break; + } + if (m_graph[node.child1()].shouldSpeculateFloat64Array()) { + forNode(node.child1()).filter(PredictFloat64Array); + forNode(node.child2()).filter(PredictInt32); + forNode(node.child3()).filter(PredictNumber); + break; + } + ASSERT(m_graph[node.child1()].shouldSpeculateArray()); + forNode(node.child1()).filter(PredictArray); + forNode(node.child2()).filter(PredictInt32); + break; + } + + case ArrayPush: + forNode(node.child1()).filter(PredictArray); + forNode(nodeIndex).set(PredictNumber); + break; + + case ArrayPop: + forNode(node.child1()).filter(PredictArray); + forNode(nodeIndex).makeTop(); + break; + + case RegExpExec: + case RegExpTest: + forNode(node.child1()).filter(PredictCell); + forNode(node.child2()).filter(PredictCell); + forNode(nodeIndex).makeTop(); + break; + + case Jump: + break; + + case Branch: { + // There is probably profit to be found in doing sparse conditional constant + // propagation, and to take it one step further, where a variable's value + // is specialized on each direction of a branch. For now, we don't do this. + Node& child = m_graph[node.child1()]; + if (child.shouldSpeculateBoolean()) + forNode(node.child1()).filter(PredictBoolean); + else if (child.shouldSpeculateFinalObjectOrOther()) + forNode(node.child1()).filter(PredictFinalObject | PredictOther); + else if (child.shouldSpeculateArrayOrOther()) + forNode(node.child1()).filter(PredictArray | PredictOther); + else if (child.shouldSpeculateInteger()) + forNode(node.child1()).filter(PredictInt32); + else if (child.shouldSpeculateNumber()) + forNode(node.child1()).filter(PredictNumber); + break; + } + + case Return: + case Throw: + case ThrowReferenceError: + m_isValid = false; + break; + + case ToPrimitive: { + Node& child = m_graph[node.child1()]; + if (child.shouldSpeculateInteger()) { + forNode(node.child1()).filter(PredictInt32); + forNode(nodeIndex).set(PredictInt32); + break; + } + + AbstractValue& source = forNode(node.child1()); + AbstractValue& destination = forNode(nodeIndex); + + PredictedType type = source.m_type; + if (type & ~(PredictNumber | PredictString | PredictBoolean)) { + type &= (PredictNumber | PredictString | PredictBoolean); + type |= PredictString; + } + destination.set(type); + break; + } + + case StrCat: + forNode(nodeIndex).set(PredictString); + break; + + case NewArray: + case NewArrayBuffer: + forNode(nodeIndex).set(m_codeBlock->globalObject()->arrayStructure()); + m_haveStructures = true; + break; + + case NewRegexp: + forNode(nodeIndex).set(m_codeBlock->globalObject()->regExpStructure()); + m_haveStructures = true; + break; + + case ConvertThis: { + Node& child = m_graph[node.child1()]; + AbstractValue& source = forNode(node.child1()); + AbstractValue& destination = forNode(nodeIndex); + + if (isObjectPrediction(source.m_type)) { + // This is the simple case. We already know that the source is an + // object, so there's nothing to do. I don't think this case will + // be hit, but then again, you never know. + destination = source; + break; + } + + if (isOtherPrediction(child.prediction())) { + source.filter(PredictOther); + destination.set(PredictObjectOther); + break; + } + + if (isObjectPrediction(child.prediction())) { + source.filter(PredictObjectMask); + destination = source; + break; + } + + destination = source; + destination.merge(PredictObjectOther); + break; + } + + case CreateThis: { + Node& child = m_graph[node.child1()]; + AbstractValue& source = forNode(node.child1()); + AbstractValue& destination = forNode(nodeIndex); + + if (child.shouldSpeculateFinalObject()) + source.filter(PredictFinalObject); + + destination.set(PredictFinalObject); + break; + } + + case NewObject: + forNode(nodeIndex).set(m_codeBlock->globalObjectFor(node.codeOrigin)->emptyObjectStructure()); + m_haveStructures = true; + break; + + case CreateActivation: + forNode(nodeIndex).set(m_graph.m_globalData.activationStructure.get()); + m_haveStructures = true; + break; + + case TearOffActivation: + // Does nothing that is user-visible. + break; + + case NewFunction: + case NewFunctionExpression: + case NewFunctionNoCheck: + forNode(nodeIndex).set(m_codeBlock->globalObjectFor(node.codeOrigin)->functionStructure()); + break; + + case GetCallee: + forNode(nodeIndex).set(PredictFunction); + break; + + case GetScopeChain: + forNode(nodeIndex).set(PredictCellOther); + break; + + case GetScopedVar: + forNode(nodeIndex).makeTop(); + break; + + case PutScopedVar: + clobberStructures(indexInBlock); + break; + + case GetById: + case GetByIdFlush: + if (!node.prediction()) { + m_isValid = false; + break; + } + if (isCellPrediction(m_graph[node.child1()].prediction())) + forNode(node.child1()).filter(PredictCell); + clobberStructures(indexInBlock); + forNode(nodeIndex).makeTop(); + break; + + case GetArrayLength: + forNode(node.child1()).filter(PredictArray); + forNode(nodeIndex).set(PredictInt32); + break; + + case GetStringLength: + forNode(node.child1()).filter(PredictString); + forNode(nodeIndex).set(PredictInt32); + break; + + case GetInt8ArrayLength: + forNode(node.child1()).filter(PredictInt8Array); + forNode(nodeIndex).set(PredictInt32); + break; + case GetInt16ArrayLength: + forNode(node.child1()).filter(PredictInt16Array); + forNode(nodeIndex).set(PredictInt32); + break; + case GetInt32ArrayLength: + forNode(node.child1()).filter(PredictInt32Array); + forNode(nodeIndex).set(PredictInt32); + break; + case GetUint8ArrayLength: + forNode(node.child1()).filter(PredictUint8Array); + forNode(nodeIndex).set(PredictInt32); + break; + case GetUint8ClampedArrayLength: + forNode(node.child1()).filter(PredictUint8ClampedArray); + forNode(nodeIndex).set(PredictInt32); + break; + case GetUint16ArrayLength: + forNode(node.child1()).filter(PredictUint16Array); + forNode(nodeIndex).set(PredictInt32); + break; + case GetUint32ArrayLength: + forNode(node.child1()).filter(PredictUint32Array); + forNode(nodeIndex).set(PredictInt32); + break; + case GetFloat32ArrayLength: + forNode(node.child1()).filter(PredictFloat32Array); + forNode(nodeIndex).set(PredictInt32); + break; + case GetFloat64ArrayLength: + forNode(node.child1()).filter(PredictFloat64Array); + forNode(nodeIndex).set(PredictInt32); + break; + + case CheckStructure: + // FIXME: We should be able to propagate the structure sets of constants (i.e. prototypes). + forNode(node.child1()).filter(node.structureSet()); + m_haveStructures = true; + break; + + case PutStructure: + clobberStructures(indexInBlock); + forNode(node.child1()).set(node.structureTransitionData().newStructure); + m_haveStructures = true; + break; + case GetPropertyStorage: + forNode(node.child1()).filter(PredictCell); + forNode(nodeIndex).clear(); // The result is not a JS value. + break; + case GetIndexedPropertyStorage: { + PredictedType basePrediction = m_graph[node.child2()].prediction(); + if (!(basePrediction & PredictInt32) && basePrediction) { + forNode(nodeIndex).clear(); + break; + } + if (m_graph[node.child1()].prediction() == PredictString) { + forNode(node.child1()).filter(PredictString); + forNode(nodeIndex).clear(); + break; + } + + if (m_graph[node.child1()].shouldSpeculateInt8Array()) { + forNode(node.child1()).filter(PredictInt8Array); + forNode(nodeIndex).clear(); + break; + } + if (m_graph[node.child1()].shouldSpeculateInt16Array()) { + forNode(node.child1()).filter(PredictInt16Array); + forNode(nodeIndex).clear(); + break; + } + if (m_graph[node.child1()].shouldSpeculateInt32Array()) { + forNode(node.child1()).filter(PredictInt32Array); + forNode(nodeIndex).clear(); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint8Array()) { + forNode(node.child1()).filter(PredictUint8Array); + forNode(nodeIndex).clear(); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint8ClampedArray()) { + forNode(node.child1()).filter(PredictUint8ClampedArray); + forNode(nodeIndex).clear(); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint16Array()) { + forNode(node.child1()).filter(PredictUint16Array); + forNode(nodeIndex).set(PredictOther); + break; + } + if (m_graph[node.child1()].shouldSpeculateUint32Array()) { + forNode(node.child1()).filter(PredictUint32Array); + forNode(nodeIndex).clear(); + break; + } + if (m_graph[node.child1()].shouldSpeculateFloat32Array()) { + forNode(node.child1()).filter(PredictFloat32Array); + forNode(nodeIndex).clear(); + break; + } + if (m_graph[node.child1()].shouldSpeculateFloat64Array()) { + forNode(node.child1()).filter(PredictFloat64Array); + forNode(nodeIndex).clear(); + break; + } + forNode(node.child1()).filter(PredictArray); + forNode(nodeIndex).clear(); + break; + } + case GetByOffset: + forNode(node.child1()).filter(PredictCell); + forNode(nodeIndex).makeTop(); + break; + + case PutByOffset: + forNode(node.child1()).filter(PredictCell); + break; + + case CheckFunction: + forNode(node.child1()).filter(PredictFunction); + // FIXME: Should be able to propagate the fact that we know what the function is. + break; + + case PutById: + case PutByIdDirect: + forNode(node.child1()).filter(PredictCell); + clobberStructures(indexInBlock); + break; + + case GetGlobalVar: + forNode(nodeIndex).makeTop(); + break; + + case PutGlobalVar: + break; + + case CheckHasInstance: + forNode(node.child1()).filter(PredictCell); + // Sadly, we don't propagate the fact that we've done CheckHasInstance + break; + + case InstanceOf: + // Again, sadly, we don't propagate the fact that we've done InstanceOf + if (!(m_graph[node.child1()].prediction() & ~PredictCell) && !(forNode(node.child1()).m_type & ~PredictCell)) + forNode(node.child1()).filter(PredictCell); + forNode(node.child3()).filter(PredictCell); + forNode(nodeIndex).set(PredictBoolean); + break; + + case Phi: + case Flush: + break; + + case Breakpoint: + break; + + case Call: + case Construct: + case Resolve: + case ResolveBase: + case ResolveBaseStrictPut: + case ResolveGlobal: + clobberStructures(indexInBlock); + forNode(nodeIndex).makeTop(); + break; + + case ForceOSRExit: + m_isValid = false; + break; + + case Phantom: + case InlineStart: + case Nop: + break; + + case LastNodeType: + ASSERT_NOT_REACHED(); + break; + } + + return m_isValid; +} + +inline void AbstractState::clobberStructures(unsigned indexInBlock) +{ + PROFILE(FLAG_FOR_STRUCTURE_CLOBBERING); + if (!m_haveStructures) + return; + for (size_t i = indexInBlock + 1; i--;) + forNode(m_block->at(i)).clobberStructures(); + for (size_t i = 0; i < m_variables.numberOfArguments(); ++i) + m_variables.argument(i).clobberStructures(); + for (size_t i = 0; i < m_variables.numberOfLocals(); ++i) + m_variables.local(i).clobberStructures(); + m_haveStructures = false; +} + +inline bool AbstractState::mergeStateAtTail(AbstractValue& destination, AbstractValue& inVariable, NodeIndex nodeIndex) +{ + if (nodeIndex == NoNode) + return false; + + AbstractValue source; + + Node& node = m_graph[nodeIndex]; + if (!node.refCount()) + return false; + +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" It's live, node @%u.\n", nodeIndex); +#endif + + switch (node.op()) { + case Phi: + case SetArgument: + case Flush: + // The block transfers the value from head to tail. + source = inVariable; +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" Transfering from head to tail.\n"); +#endif + break; + + case GetLocal: + // The block refines the value with additional speculations. + source = forNode(nodeIndex); +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" Refining.\n"); +#endif + break; + + case SetLocal: + // The block sets the variable, and potentially refines it, both + // before and after setting it. + if (node.variableAccessData()->shouldUseDoubleFormat()) + source.set(PredictDouble); + else + source = forNode(node.child1()); +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" Setting.\n"); +#endif + break; + + default: + ASSERT_NOT_REACHED(); + break; + } + + if (destination == source) { + // Abstract execution did not change the output value of the variable, for this + // basic block, on this iteration. +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" Not changed!\n"); +#endif + return false; + } + + // Abstract execution reached a new conclusion about the speculations reached about + // this variable after execution of this basic block. Update the state, and return + // true to indicate that the fixpoint must go on! + destination = source; +#if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) + dataLog(" Changed!\n"); +#endif + return true; +} + +inline bool AbstractState::merge(BasicBlock* from, BasicBlock* to) +{ + ASSERT(from->variablesAtTail.numberOfArguments() == to->variablesAtHead.numberOfArguments()); + ASSERT(from->variablesAtTail.numberOfLocals() == to->variablesAtHead.numberOfLocals()); + + bool changed = false; + + for (size_t argument = 0; argument < from->variablesAtTail.numberOfArguments(); ++argument) { + AbstractValue& destination = to->valuesAtHead.argument(argument); + if (m_graph.argumentIsCaptured(argument)) { + if (destination.isTop()) + continue; + destination.makeTop(); + changed = true; + continue; + } + changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.argument(argument), to->variablesAtHead.argument(argument), from->variablesAtTail.argument(argument)); + } + + for (size_t local = 0; local < from->variablesAtTail.numberOfLocals(); ++local) { + AbstractValue& destination = to->valuesAtHead.local(local); + if (m_graph.localIsCaptured(local)) { + if (destination.isTop()) + continue; + destination.makeTop(); + changed = true; + continue; + } + changed |= mergeVariableBetweenBlocks(destination, from->valuesAtTail.local(local), to->variablesAtHead.local(local), from->variablesAtTail.local(local)); + } + + if (!to->cfaHasVisited) + changed = true; + + to->cfaShouldRevisit |= changed; + + return changed; +} + +inline bool AbstractState::mergeToSuccessors(Graph& graph, BasicBlock* basicBlock) +{ + PROFILE(FLAG_FOR_MERGE_TO_SUCCESSORS); + + Node& terminal = graph[basicBlock->last()]; + + ASSERT(terminal.isTerminal()); + + switch (terminal.op()) { + case Jump: + return merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get()); + + case Branch: + return merge(basicBlock, graph.m_blocks[terminal.takenBlockIndex()].get()) + | merge(basicBlock, graph.m_blocks[terminal.notTakenBlockIndex()].get()); + + case Return: + case Throw: + case ThrowReferenceError: + return false; + + default: + ASSERT_NOT_REACHED(); + return false; + } +} + +inline bool AbstractState::mergeVariableBetweenBlocks(AbstractValue& destination, AbstractValue& source, NodeIndex destinationNodeIndex, NodeIndex sourceNodeIndex) +{ + if (destinationNodeIndex == NoNode) + return false; + + ASSERT_UNUSED(sourceNodeIndex, sourceNodeIndex != NoNode); + + // FIXME: We could do some sparse conditional propagation here! + + return destination.merge(source); +} + +#ifndef NDEBUG +void AbstractState::dump(FILE* out) +{ + bool first = true; + for (size_t i = 0; i < m_block->size(); ++i) { + NodeIndex index = m_block->at(i); + AbstractValue& value = m_nodes[index]; + if (value.isClear()) + continue; + if (first) + first = false; + else + fprintf(out, " "); + fprintf(out, "@%lu:", static_cast(index)); + value.dump(out); + } +} +#endif + +} } // namespace JSC::DFG + +#endif // ENABLE(DFG_JIT) +