/* * Copyright (C) 2011, 2012, 2013 Apple Inc. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #include "config.h" #include "DFGCSEPhase.h" #if ENABLE(DFG_JIT) #include "DFGGraph.h" #include "DFGPhase.h" #include namespace JSC { namespace DFG { class CSEPhase : public Phase { public: CSEPhase(Graph& graph) : Phase(graph, "common subexpression elimination") { for (unsigned i = 0; i < m_graph.size(); ++i) m_graph[i].replacement = NoNode; m_relevantToOSR.resize(m_graph.size()); } bool run() { m_changed = false; for (unsigned block = 0; block < m_graph.m_blocks.size(); ++block) performBlockCSE(m_graph.m_blocks[block].get()); return m_changed; } private: NodeIndex canonicalize(NodeIndex nodeIndex) { if (nodeIndex == NoNode) return NoNode; if (m_graph[nodeIndex].op() == ValueToInt32) nodeIndex = m_graph[nodeIndex].child1().index(); return nodeIndex; } NodeIndex canonicalize(Edge nodeUse) { return canonicalize(nodeUse.indexUnchecked()); } unsigned endIndexForPureCSE() { unsigned result = m_lastSeen[m_graph[m_compileIndex].op()]; if (result == UINT_MAX) result = 0; else result++; ASSERT(result <= m_indexInBlock); #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) dataLogF(" limit %u: ", result); #endif return result; } NodeIndex pureCSE(Node& node) { NodeIndex child1 = canonicalize(node.child1()); NodeIndex child2 = canonicalize(node.child2()); NodeIndex child3 = canonicalize(node.child3()); for (unsigned i = endIndexForPureCSE(); i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1 || index == child2 || index == child3) break; Node& otherNode = m_graph[index]; if (!otherNode.shouldGenerate()) continue; if (node.op() != otherNode.op()) continue; if (node.arithNodeFlags() != otherNode.arithNodeFlags()) continue; NodeIndex otherChild = canonicalize(otherNode.child1()); if (otherChild == NoNode) return index; if (otherChild != child1) continue; otherChild = canonicalize(otherNode.child2()); if (otherChild == NoNode) return index; if (otherChild != child2) continue; otherChild = canonicalize(otherNode.child3()); if (otherChild == NoNode) return index; if (otherChild != child3) continue; return index; } return NoNode; } NodeIndex constantCSE(Node& node) { for (unsigned i = endIndexForPureCSE(); i--;) { NodeIndex index = m_currentBlock->at(i); Node& otherNode = m_graph[index]; if (otherNode.op() != JSConstant) continue; if (otherNode.constantNumber() != node.constantNumber()) continue; return index; } return NoNode; } NodeIndex weakConstantCSE(Node& node) { for (unsigned i = endIndexForPureCSE(); i--;) { NodeIndex index = m_currentBlock->at(i); Node& otherNode = m_graph[index]; if (otherNode.op() != WeakJSConstant) continue; if (otherNode.weakConstant() != node.weakConstant()) continue; return index; } return NoNode; } NodeIndex getCalleeLoadElimination(InlineCallFrame* inlineCallFrame) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; if (node.codeOrigin.inlineCallFrame != inlineCallFrame) continue; switch (node.op()) { case GetCallee: return index; case SetCallee: return node.child1().index(); default: break; } } return NoNode; } NodeIndex getArrayLengthElimination(NodeIndex array) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case GetArrayLength: if (node.child1() == array) return index; break; case PutByVal: if (!m_graph.byValIsPure(node)) return NoNode; if (node.arrayMode().mayStoreToHole()) return NoNode; break; default: if (m_graph.clobbersWorld(index)) return NoNode; } } return NoNode; } NodeIndex globalVarLoadElimination(WriteBarrier* registerPointer) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case GetGlobalVar: if (node.registerPointer() == registerPointer) return index; break; case PutGlobalVar: if (node.registerPointer() == registerPointer) return node.child1().index(); break; default: break; } if (m_graph.clobbersWorld(index)) break; } return NoNode; } NodeIndex scopedVarLoadElimination(NodeIndex registers, unsigned varNumber) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case GetScopedVar: { if (node.child1() == registers && node.varNumber() == varNumber) return index; break; } case PutScopedVar: { if (node.child2() == registers && node.varNumber() == varNumber) return node.child3().index(); break; } case SetLocal: { VariableAccessData* variableAccessData = node.variableAccessData(); if (variableAccessData->isCaptured() && variableAccessData->local() == static_cast(varNumber)) return NoNode; break; } default: break; } if (m_graph.clobbersWorld(index)) break; } return NoNode; } bool globalVarWatchpointElimination(WriteBarrier* registerPointer) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case GlobalVarWatchpoint: if (node.registerPointer() == registerPointer) return true; break; case PutGlobalVar: if (node.registerPointer() == registerPointer) return false; break; default: break; } if (m_graph.clobbersWorld(index)) break; } return false; } NodeIndex globalVarStoreElimination(WriteBarrier* registerPointer) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case PutGlobalVar: case PutGlobalVarCheck: if (node.registerPointer() == registerPointer) return index; break; case GetGlobalVar: if (node.registerPointer() == registerPointer) return NoNode; break; default: break; } if (m_graph.clobbersWorld(index) || node.canExit()) return NoNode; } return NoNode; } NodeIndex scopedVarStoreElimination(NodeIndex scope, NodeIndex registers, unsigned varNumber) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case PutScopedVar: { if (node.child1() == scope && node.child2() == registers && node.varNumber() == varNumber) return index; break; } case GetScopedVar: { // Let's be conservative. if (node.varNumber() == varNumber) return NoNode; break; } case GetLocal: { VariableAccessData* variableAccessData = node.variableAccessData(); if (variableAccessData->isCaptured() && variableAccessData->local() == static_cast(varNumber)) return NoNode; break; } default: break; } if (m_graph.clobbersWorld(index) || node.canExit()) return NoNode; } return NoNode; } NodeIndex getByValLoadElimination(NodeIndex child1, NodeIndex child2) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1 || index == canonicalize(child2)) break; Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case GetByVal: if (!m_graph.byValIsPure(node)) return NoNode; if (node.child1() == child1 && canonicalize(node.child2()) == canonicalize(child2)) return index; break; case PutByVal: case PutByValAlias: { if (!m_graph.byValIsPure(node)) return NoNode; if (m_graph.varArgChild(node, 0) == child1 && canonicalize(m_graph.varArgChild(node, 1)) == canonicalize(child2)) return m_graph.varArgChild(node, 2).index(); // We must assume that the PutByVal will clobber the location we're getting from. // FIXME: We can do better; if we know that the PutByVal is accessing an array of a // different type than the GetByVal, then we know that they won't clobber each other. return NoNode; } case PutStructure: case PutByOffset: // GetByVal currently always speculates that it's accessing an // array with an integer index, which means that it's impossible // for a structure change or a put to property storage to affect // the GetByVal. break; default: if (m_graph.clobbersWorld(index)) return NoNode; break; } } return NoNode; } bool checkFunctionElimination(JSCell* function, NodeIndex child1) { for (unsigned i = endIndexForPureCSE(); i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1) break; Node& node = m_graph[index]; if (node.op() == CheckFunction && node.child1() == child1 && node.function() == function) return true; } return false; } bool checkExecutableElimination(ExecutableBase* executable, NodeIndex child1) { for (unsigned i = endIndexForPureCSE(); i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1) break; Node& node = m_graph[index]; if (node.op() == CheckExecutable && node.child1() == child1 && node.executable() == executable) return true; } return false; } bool checkStructureElimination(const StructureSet& structureSet, NodeIndex child1) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1) break; Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case CheckStructure: case ForwardCheckStructure: if (node.child1() == child1 && structureSet.isSupersetOf(node.structureSet())) return true; break; case StructureTransitionWatchpoint: case ForwardStructureTransitionWatchpoint: if (node.child1() == child1 && structureSet.contains(node.structure())) return true; break; case PutStructure: if (node.child1() == child1 && structureSet.contains(node.structureTransitionData().newStructure)) return true; if (structureSet.contains(node.structureTransitionData().previousStructure)) return false; break; case PutByOffset: // Setting a property cannot change the structure. break; case PutByVal: case PutByValAlias: if (m_graph.byValIsPure(node)) { // If PutByVal speculates that it's accessing an array with an // integer index, then it's impossible for it to cause a structure // change. break; } return false; case Arrayify: case ArrayifyToStructure: // We could check if the arrayification could affect our structures. // But that seems like it would take Effort. return false; default: if (m_graph.clobbersWorld(index)) return false; break; } } return false; } bool structureTransitionWatchpointElimination(Structure* structure, NodeIndex child1) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1) break; Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case CheckStructure: case ForwardCheckStructure: if (node.child1() == child1 && node.structureSet().containsOnly(structure)) return true; break; case PutStructure: ASSERT(node.structureTransitionData().previousStructure != structure); break; case PutByOffset: // Setting a property cannot change the structure. break; case PutByVal: case PutByValAlias: if (m_graph.byValIsPure(node)) { // If PutByVal speculates that it's accessing an array with an // integer index, then it's impossible for it to cause a structure // change. break; } return false; case StructureTransitionWatchpoint: case ForwardStructureTransitionWatchpoint: if (node.structure() == structure && node.child1() == child1) return true; break; case Arrayify: case ArrayifyToStructure: // We could check if the arrayification could affect our structures. // But that seems like it would take Effort. return false; default: if (m_graph.clobbersWorld(index)) return false; break; } } return false; } NodeIndex putStructureStoreElimination(NodeIndex child1) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1) break; Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case CheckStructure: case ForwardCheckStructure: return NoNode; case PhantomPutStructure: if (node.child1() == child1) // No need to retrace our steps. return NoNode; break; case PutStructure: if (node.child1() == child1) return index; break; // PutStructure needs to execute if we GC. Hence this needs to // be careful with respect to nodes that GC. case CreateArguments: case TearOffArguments: case NewFunctionNoCheck: case NewFunction: case NewFunctionExpression: case CreateActivation: case TearOffActivation: case StrCat: case ToPrimitive: case NewRegexp: case NewArrayBuffer: case NewArray: case NewObject: case CreateThis: case AllocatePropertyStorage: case ReallocatePropertyStorage: case TypeOf: return NoNode; case GetIndexedPropertyStorage: if (node.arrayMode().getIndexedPropertyStorageMayTriggerGC()) return NoNode; break; default: break; } if (m_graph.clobbersWorld(index) || node.canExit()) return NoNode; } return NoNode; } NodeIndex getByOffsetLoadElimination(unsigned identifierNumber, NodeIndex child1) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1) break; Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case GetByOffset: if (node.child1() == child1 && m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) return index; break; case PutByOffset: if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) { if (node.child1() == child1) // Must be same property storage. return node.child3().index(); return NoNode; } break; case PutStructure: // Changing the structure cannot change the outcome of a property get. break; case PutByVal: case PutByValAlias: if (m_graph.byValIsPure(node)) { // If PutByVal speculates that it's accessing an array with an // integer index, then it's impossible for it to cause a structure // change. break; } return NoNode; default: if (m_graph.clobbersWorld(index)) return NoNode; break; } } return NoNode; } NodeIndex putByOffsetStoreElimination(unsigned identifierNumber, NodeIndex child1) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1) break; Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case GetByOffset: if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) return NoNode; break; case PutByOffset: if (m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber == identifierNumber) { if (node.child1() == child1) // Must be same property storage. return index; return NoNode; } break; case PutByVal: case PutByValAlias: case GetByVal: if (m_graph.byValIsPure(node)) { // If PutByVal speculates that it's accessing an array with an // integer index, then it's impossible for it to cause a structure // change. break; } return NoNode; default: if (m_graph.clobbersWorld(index)) return NoNode; break; } if (node.canExit()) return NoNode; } return NoNode; } NodeIndex getPropertyStorageLoadElimination(NodeIndex child1) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1) break; Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case GetButterfly: if (node.child1() == child1) return index; break; case AllocatePropertyStorage: case ReallocatePropertyStorage: // If we can cheaply prove this is a change to our object's storage, we // can optimize and use its result. if (node.child1() == child1) return index; // Otherwise, we currently can't prove that this doesn't change our object's // storage, so we conservatively assume that it may change the storage // pointer of any object, including ours. return NoNode; case PutByOffset: case PutStructure: // Changing the structure or putting to the storage cannot // change the property storage pointer. break; case PutByVal: case PutByValAlias: if (m_graph.byValIsPure(node)) { // If PutByVal speculates that it's accessing an array with an // integer index, then it's impossible for it to cause a structure // change. break; } return NoNode; case Arrayify: case ArrayifyToStructure: // We could check if the arrayification could affect our butterfly. // But that seems like it would take Effort. return NoNode; default: if (m_graph.clobbersWorld(index)) return NoNode; break; } } return NoNode; } bool checkArrayElimination(NodeIndex child1, ArrayMode arrayMode) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1) break; Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case PutByOffset: case PutStructure: // Changing the structure or putting to the storage cannot // change the property storage pointer. break; case CheckArray: if (node.child1() == child1 && node.arrayMode() == arrayMode) return true; break; case Arrayify: case ArrayifyToStructure: // We could check if the arrayification could affect our array. // But that seems like it would take Effort. return false; default: if (m_graph.clobbersWorld(index)) return false; break; } } return false; } NodeIndex getIndexedPropertyStorageLoadElimination(NodeIndex child1, ArrayMode arrayMode) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); if (index == child1) break; Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case GetIndexedPropertyStorage: { if (node.child1() == child1 && node.arrayMode() == arrayMode) return index; break; } case PutByOffset: case PutStructure: // Changing the structure or putting to the storage cannot // change the property storage pointer. break; default: if (m_graph.clobbersWorld(index)) return NoNode; break; } } return NoNode; } NodeIndex getMyScopeLoadElimination(InlineCallFrame* inlineCallFrame) { for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; if (node.codeOrigin.inlineCallFrame != inlineCallFrame) continue; switch (node.op()) { case CreateActivation: // This may cause us to return a different scope. return NoNode; case GetMyScope: return index; case SetMyScope: return node.child1().index(); default: break; } } return NoNode; } NodeIndex getLocalLoadElimination(VirtualRegister local, NodeIndex& relevantLocalOp, bool careAboutClobbering) { relevantLocalOp = NoNode; for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case GetLocal: if (node.local() == local) { relevantLocalOp = index; return index; } break; case GetLocalUnlinked: if (node.unlinkedLocal() == local) { relevantLocalOp = index; return index; } break; case SetLocal: if (node.local() == local) { relevantLocalOp = index; return node.child1().index(); } break; case PutScopedVar: if (static_cast(node.varNumber()) == local) return NoNode; break; default: if (careAboutClobbering && m_graph.clobbersWorld(index)) return NoNode; break; } } return NoNode; } struct SetLocalStoreEliminationResult { SetLocalStoreEliminationResult() : mayBeAccessed(false) , mayExit(false) , mayClobberWorld(false) { } bool mayBeAccessed; bool mayExit; bool mayClobberWorld; }; SetLocalStoreEliminationResult setLocalStoreElimination( VirtualRegister local, NodeIndex expectedNodeIndex) { SetLocalStoreEliminationResult result; for (unsigned i = m_indexInBlock; i--;) { NodeIndex index = m_currentBlock->at(i); Node& node = m_graph[index]; if (!node.shouldGenerate()) continue; switch (node.op()) { case GetLocal: case Flush: if (node.local() == local) result.mayBeAccessed = true; break; case GetLocalUnlinked: if (node.unlinkedLocal() == local) result.mayBeAccessed = true; break; case SetLocal: { if (node.local() != local) break; if (index != expectedNodeIndex) result.mayBeAccessed = true; if (m_graph[index].refCount() > 1) result.mayBeAccessed = true; return result; } case GetScopedVar: if (static_cast(node.varNumber()) == local) result.mayBeAccessed = true; break; case GetMyScope: case SkipTopScope: if (m_graph.uncheckedActivationRegisterFor(node.codeOrigin) == local) result.mayBeAccessed = true; break; case CheckArgumentsNotCreated: case GetMyArgumentsLength: case GetMyArgumentsLengthSafe: if (m_graph.uncheckedArgumentsRegisterFor(node.codeOrigin) == local) result.mayBeAccessed = true; break; case GetMyArgumentByVal: case GetMyArgumentByValSafe: result.mayBeAccessed = true; break; case GetByVal: // If this is accessing arguments then it's potentially accessing locals. if (m_graph[node.child1()].shouldSpeculateArguments()) result.mayBeAccessed = true; break; case CreateArguments: case TearOffActivation: case TearOffArguments: // If an activation is being torn off then it means that captured variables // are live. We could be clever here and check if the local qualifies as an // argument register. But that seems like it would buy us very little since // any kind of tear offs are rare to begin with. result.mayBeAccessed = true; break; default: break; } result.mayExit |= node.canExit(); result.mayClobberWorld |= m_graph.clobbersWorld(index); } ASSERT_NOT_REACHED(); // Be safe in release mode. result.mayBeAccessed = true; return result; } void performSubstitution(Edge& child, bool addRef = true) { // Check if this operand is actually unused. if (!child) return; // Check if there is any replacement. NodeIndex replacement = m_graph[child.index()].replacement; if (replacement == NoNode) return; child.setIndex(replacement); // There is definitely a replacement. Assert that the replacement does not // have a replacement. ASSERT(m_graph[child.index()].replacement == NoNode); if (addRef) m_graph.ref(child); } void eliminateIrrelevantPhantomChildren(Node& node) { ASSERT(node.op() == Phantom); for (unsigned i = 0; i < AdjacencyList::Size; ++i) { Edge edge = node.children.child(i); if (!edge) continue; if (m_relevantToOSR.get(edge.index())) continue; #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) dataLog(" Eliminating edge @", m_compileIndex, " -> @", edge.index()); #endif m_graph.deref(edge); node.children.removeEdgeFromBag(i--); m_changed = true; } } enum PredictionHandlingMode { RequireSamePrediction, AllowPredictionMismatch }; bool setReplacement(NodeIndex replacement, PredictionHandlingMode predictionHandlingMode = RequireSamePrediction) { if (replacement == NoNode) return false; // Be safe. Don't try to perform replacements if the predictions don't // agree. if (predictionHandlingMode == RequireSamePrediction && m_graph[m_compileIndex].prediction() != m_graph[replacement].prediction()) return false; #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) dataLogF(" Replacing @%u -> @%u", m_compileIndex, replacement); #endif Node& node = m_graph[m_compileIndex]; node.setOpAndDefaultFlags(Phantom); node.setRefCount(1); eliminateIrrelevantPhantomChildren(node); // At this point we will eliminate all references to this node. m_graph[m_compileIndex].replacement = replacement; m_changed = true; return true; } void eliminate() { #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) dataLogF(" Eliminating @%u", m_compileIndex); #endif Node& node = m_graph[m_compileIndex]; ASSERT(node.refCount() == 1); ASSERT(node.mustGenerate()); node.setOpAndDefaultFlags(Phantom); eliminateIrrelevantPhantomChildren(node); m_changed = true; } void eliminate(NodeIndex nodeIndex, NodeType phantomType = Phantom) { if (nodeIndex == NoNode) return; Node& node = m_graph[nodeIndex]; if (node.refCount() != 1) return; ASSERT(node.mustGenerate()); node.setOpAndDefaultFlags(phantomType); if (phantomType == Phantom) eliminateIrrelevantPhantomChildren(node); m_changed = true; } void performNodeCSE(Node& node) { bool shouldGenerate = node.shouldGenerate(); if (node.flags() & NodeHasVarArgs) { for (unsigned childIdx = node.firstChild(); childIdx < node.firstChild() + node.numChildren(); childIdx++) performSubstitution(m_graph.m_varArgChildren[childIdx], shouldGenerate); } else { performSubstitution(node.children.child1(), shouldGenerate); performSubstitution(node.children.child2(), shouldGenerate); performSubstitution(node.children.child3(), shouldGenerate); } if (node.op() == SetLocal) m_relevantToOSR.set(node.child1().index()); if (!shouldGenerate) return; #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) dataLogF(" %s @%u: ", Graph::opName(m_graph[m_compileIndex].op()), m_compileIndex); #endif // NOTE: there are some nodes that we deliberately don't CSE even though we // probably could, like StrCat and ToPrimitive. That's because there is no // evidence that doing CSE on these nodes would result in a performance // progression. Hence considering these nodes in CSE would just mean that this // code does more work with no win. Of course, we may want to reconsider this, // since StrCat is trivially CSE-able. It's not trivially doable for // ToPrimitive, but we could change that with some speculations if we really // needed to. switch (node.op()) { case Identity: setReplacement(node.child1().index()); break; // Handle the pure nodes. These nodes never have any side-effects. case BitAnd: case BitOr: case BitXor: case BitRShift: case BitLShift: case BitURShift: case ArithAdd: case ArithSub: case ArithNegate: case ArithMul: case ArithMod: case ArithDiv: case ArithAbs: case ArithMin: case ArithMax: case ArithSqrt: case StringCharAt: case StringCharCodeAt: case Int32ToDouble: case IsUndefined: case IsBoolean: case IsNumber: case IsString: case IsObject: case IsFunction: case DoubleAsInt32: case LogicalNot: case SkipTopScope: case SkipScope: case GetScopeRegisters: case GetScope: case TypeOf: setReplacement(pureCSE(node)); break; case GetCallee: setReplacement(getCalleeLoadElimination(node.codeOrigin.inlineCallFrame)); break; case GetLocal: { VariableAccessData* variableAccessData = node.variableAccessData(); if (!variableAccessData->isCaptured()) break; NodeIndex relevantLocalOp; NodeIndex possibleReplacement = getLocalLoadElimination(variableAccessData->local(), relevantLocalOp, variableAccessData->isCaptured()); if (relevantLocalOp == NoNode) break; if (m_graph[relevantLocalOp].op() != GetLocalUnlinked && m_graph[relevantLocalOp].variableAccessData() != variableAccessData) break; NodeIndex phiIndex = node.child1().index(); if (!setReplacement(possibleReplacement)) break; // If the GetLocal we replaced used to refer to a SetLocal, then it now // should refer to the child of the SetLocal instead. if (m_graph[phiIndex].op() == SetLocal) { ASSERT(node.child1().index() == phiIndex); m_graph.changeEdge(node.children.child1(), m_graph[phiIndex].child1()); } NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand( variableAccessData->local()); if (oldTailIndex == m_compileIndex) { m_currentBlock->variablesAtTail.operand(variableAccessData->local()) = relevantLocalOp; // Maintain graph integrity: since we're replacing a GetLocal with a GetLocalUnlinked, // make sure that the GetLocalUnlinked is now linked. if (m_graph[relevantLocalOp].op() == GetLocalUnlinked) { m_graph[relevantLocalOp].setOp(GetLocal); m_graph[relevantLocalOp].children.child1() = Edge(phiIndex); m_graph.ref(phiIndex); } } m_changed = true; break; } case GetLocalUnlinked: { NodeIndex relevantLocalOpIgnored; setReplacement(getLocalLoadElimination(node.unlinkedLocal(), relevantLocalOpIgnored, true)); break; } case Flush: { VariableAccessData* variableAccessData = node.variableAccessData(); VirtualRegister local = variableAccessData->local(); NodeIndex replacementIndex = node.child1().index(); Node& replacement = m_graph[replacementIndex]; if (replacement.op() != SetLocal) break; ASSERT(replacement.variableAccessData() == variableAccessData); // FIXME: We should be able to remove SetLocals that can exit; we just need // to replace them with appropriate type checks. if (m_graph.m_fixpointState == FixpointNotConverged) { // Need to be conservative at this time; if the SetLocal has any chance of performing // any speculations then we cannot do anything. if (variableAccessData->isCaptured()) { // Captured SetLocals never speculate and hence never exit. } else { if (variableAccessData->shouldUseDoubleFormat()) break; SpeculatedType prediction = variableAccessData->argumentAwarePrediction(); if (isInt32Speculation(prediction)) break; if (isArraySpeculation(prediction)) break; if (isBooleanSpeculation(prediction)) break; } } else { if (replacement.canExit()) break; } SetLocalStoreEliminationResult result = setLocalStoreElimination(local, replacementIndex); if (result.mayBeAccessed || result.mayClobberWorld) break; ASSERT(replacement.op() == SetLocal); ASSERT(replacement.refCount() == 1); ASSERT(replacement.shouldGenerate()); // FIXME: Investigate using mayExit as a further optimization. node.setOpAndDefaultFlags(Phantom); NodeIndex dataNodeIndex = replacement.child1().index(); ASSERT(m_graph[dataNodeIndex].hasResult()); m_graph.clearAndDerefChild1(node); node.children.child1() = Edge(dataNodeIndex); m_graph.ref(dataNodeIndex); NodeIndex oldTailIndex = m_currentBlock->variablesAtTail.operand(local); if (oldTailIndex == m_compileIndex) m_currentBlock->variablesAtTail.operand(local) = replacementIndex; m_changed = true; break; } case JSConstant: // This is strange, but necessary. Some phases will convert nodes to constants, // which may result in duplicated constants. We use CSE to clean this up. setReplacement(constantCSE(node), AllowPredictionMismatch); break; case WeakJSConstant: // FIXME: have CSE for weak constants against strong constants and vice-versa. setReplacement(weakConstantCSE(node)); break; case GetArrayLength: setReplacement(getArrayLengthElimination(node.child1().index())); break; case GetMyScope: setReplacement(getMyScopeLoadElimination(node.codeOrigin.inlineCallFrame)); break; // Handle nodes that are conditionally pure: these are pure, and can // be CSE'd, so long as the prediction is the one we want. case ValueAdd: case CompareLess: case CompareLessEq: case CompareGreater: case CompareGreaterEq: case CompareEq: { if (m_graph.isPredictedNumerical(node)) { NodeIndex replacementIndex = pureCSE(node); if (replacementIndex != NoNode && m_graph.isPredictedNumerical(m_graph[replacementIndex])) setReplacement(replacementIndex); } break; } // Finally handle heap accesses. These are not quite pure, but we can still // optimize them provided that some subtle conditions are met. case GetGlobalVar: setReplacement(globalVarLoadElimination(node.registerPointer())); break; case GetScopedVar: { setReplacement(scopedVarLoadElimination(node.child1().index(), node.varNumber())); break; } case GlobalVarWatchpoint: if (globalVarWatchpointElimination(node.registerPointer())) eliminate(); break; case PutGlobalVar: case PutGlobalVarCheck: if (m_graph.m_fixpointState == FixpointNotConverged) break; eliminate(globalVarStoreElimination(node.registerPointer())); break; case PutScopedVar: { if (m_graph.m_fixpointState == FixpointNotConverged) break; eliminate(scopedVarStoreElimination(node.child1().index(), node.child2().index(), node.varNumber())); break; } case GetByVal: if (m_graph.byValIsPure(node)) setReplacement(getByValLoadElimination(node.child1().index(), node.child2().index())); break; case PutByVal: { Edge child1 = m_graph.varArgChild(node, 0); Edge child2 = m_graph.varArgChild(node, 1); if (node.arrayMode().canCSEStorage()) { NodeIndex nodeIndex = getByValLoadElimination(child1.index(), child2.index()); if (nodeIndex == NoNode) break; node.setOp(PutByValAlias); } break; } case CheckStructure: case ForwardCheckStructure: if (checkStructureElimination(node.structureSet(), node.child1().index())) eliminate(); break; case StructureTransitionWatchpoint: case ForwardStructureTransitionWatchpoint: if (structureTransitionWatchpointElimination(node.structure(), node.child1().index())) eliminate(); break; case PutStructure: if (m_graph.m_fixpointState == FixpointNotConverged) break; eliminate(putStructureStoreElimination(node.child1().index()), PhantomPutStructure); break; case CheckFunction: if (checkFunctionElimination(node.function(), node.child1().index())) eliminate(); break; case CheckExecutable: if (checkExecutableElimination(node.executable(), node.child1().index())) eliminate(); break; case CheckArray: if (checkArrayElimination(node.child1().index(), node.arrayMode())) eliminate(); break; case GetIndexedPropertyStorage: { setReplacement(getIndexedPropertyStorageLoadElimination(node.child1().index(), node.arrayMode())); break; } case GetButterfly: setReplacement(getPropertyStorageLoadElimination(node.child1().index())); break; case GetByOffset: setReplacement(getByOffsetLoadElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index())); break; case PutByOffset: if (m_graph.m_fixpointState == FixpointNotConverged) break; eliminate(putByOffsetStoreElimination(m_graph.m_storageAccessData[node.storageAccessDataIndex()].identifierNumber, node.child1().index())); break; case Phantom: // FIXME: we ought to remove Phantom's that have no children. eliminateIrrelevantPhantomChildren(node); break; default: // do nothing. break; } m_lastSeen[node.op()] = m_indexInBlock; #if DFG_ENABLE(DEBUG_PROPAGATION_VERBOSE) dataLogF("\n"); #endif } void performBlockCSE(BasicBlock* block) { if (!block) return; if (!block->isReachable) return; m_currentBlock = block; for (unsigned i = 0; i < LastNodeType; ++i) m_lastSeen[i] = UINT_MAX; // Make all of my Phi nodes relevant to OSR. for (unsigned i = 0; i < block->phis.size(); ++i) m_relevantToOSR.set(block->phis[i]); // Make all of my SetLocal and GetLocal nodes relevant to OSR. for (unsigned i = 0; i < block->size(); ++i) { NodeIndex nodeIndex = block->at(i); Node& node = m_graph[nodeIndex]; switch (node.op()) { case SetLocal: case GetLocal: // FIXME: The GetLocal case is only necessary until we do https://bugs.webkit.org/show_bug.cgi?id=106707. m_relevantToOSR.set(nodeIndex); break; default: break; } } for (m_indexInBlock = 0; m_indexInBlock < block->size(); ++m_indexInBlock) { m_compileIndex = block->at(m_indexInBlock); performNodeCSE(m_graph[m_compileIndex]); } } BasicBlock* m_currentBlock; NodeIndex m_compileIndex; unsigned m_indexInBlock; FixedArray m_lastSeen; FastBitVector m_relevantToOSR; bool m_changed; // Only tracks changes that have a substantive effect on other optimizations. }; bool performCSE(Graph& graph) { SamplingRegion samplingRegion("DFG CSE Phase"); return runPhase(graph); } } } // namespace JSC::DFG #endif // ENABLE(DFG_JIT)