| /* |
| * Copyright (C) 2024 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 "DFGLoopUnrollingPhase.h" |
| |
| #if ENABLE(DFG_JIT) |
| |
| #include "CodeOrigin.h" |
| #include "DFGBasicBlockInlines.h" |
| #include "DFGBlockInsertionSet.h" |
| #include "DFGCFAPhase.h" |
| #include "DFGGraph.h" |
| #include "DFGNaturalLoops.h" |
| #include "DFGNodeOrigin.h" |
| #include "DFGNodeType.h" |
| #include "DFGPhase.h" |
| #include <wtf/IndexMap.h> |
| |
| namespace JSC { |
| namespace DFG { |
| |
| class LoopUnrollingPhase : public Phase { |
| public: |
| using NaturalLoop = CPSNaturalLoop; |
| |
| using ComparisonFunction = bool (*)(CheckedInt32, CheckedInt32); |
| using UpdateFunction = CheckedInt32 (*)(CheckedInt32, CheckedInt32); |
| |
| struct LoopData { |
| uint32_t loopSize() { return loop->size(); } |
| BasicBlock* loopBody(uint32_t i) { return loop->at(i).node(); } |
| BasicBlock* header() const { return loop->header().node(); } |
| |
| Node* condition() const |
| { |
| if (tail && tail->terminal()->isBranch()) |
| return tail->terminal()->child1().node(); |
| return nullptr; |
| } |
| |
| bool isInductionVariable(Node* node) { return node->operand() == inductionVariable->operand(); } |
| void dump(PrintStream& out) const; |
| |
| const NaturalLoop* loop { nullptr }; |
| BasicBlock* preHeader { nullptr }; |
| BasicBlock* tail { nullptr }; |
| BasicBlock* next { nullptr }; |
| |
| // for (i = initialValue; condition(i, operand); i = update(i, updateValue)) { ... } |
| Node* inductionVariable { nullptr }; |
| CheckedInt32 initialValue { INT_MIN }; |
| CheckedInt32 operand { INT_MIN }; |
| Node* update { nullptr }; |
| CheckedInt32 updateValue { INT_MIN }; |
| CheckedUint32 iterationCount { 0 }; |
| |
| std::optional<bool> inverseCondition { }; |
| }; |
| |
| LoopUnrollingPhase(Graph& graph) |
| : Phase(graph, "Loop Unrolling"_s) |
| , m_blockInsertionSet(graph) |
| { |
| } |
| |
| bool run() |
| { |
| if (UNLIKELY(Options::verboseLoopUnrolling())) { |
| dataLogLn("Graph before Loop Unrolling Phase:"); |
| m_graph.dump(); |
| } |
| |
| uint32_t unrolledCount = 0; |
| while (true) { |
| auto loops = populateCandidateLoops(); |
| if (loops.isEmpty() || unrolledCount >= Options::maxLoopUnrollingCount()) |
| break; |
| |
| bool unrolled = false; |
| for (auto [loop, depth] : loops) { |
| if (!loop) |
| break; |
| if (tryUnroll(loop)) { |
| unrolled = true; |
| ++unrolledCount; |
| break; |
| } |
| } |
| if (!unrolled) |
| break; |
| } |
| |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Successfully unrolled ", unrolledCount, " loops."); |
| return !!unrolledCount; |
| } |
| |
| Vector<std::tuple<const NaturalLoop*, int32_t>, 16> populateCandidateLoops() |
| { |
| m_graph.ensureCPSNaturalLoops(); |
| |
| uint32_t loopCount = m_graph.m_cpsNaturalLoops->numLoops(); |
| Vector<std::tuple<const NaturalLoop*, int32_t>, 16> loops(loopCount, std::tuple { nullptr, INT_MIN }); |
| for (uint32_t loopIndex = loopCount; loopIndex--;) { |
| const NaturalLoop& loop = m_graph.m_cpsNaturalLoops->loop(loopIndex); |
| ASSERT(loop.index() == loopIndex && std::get<1>(loops[loopIndex]) == INT_MIN); |
| |
| int32_t depth = 0; |
| const NaturalLoop* current = &loop; |
| while (current) { |
| int32_t cachedDepth = std::get<1>(loops[current->index()]); |
| if (cachedDepth != INT_MIN) { |
| depth += cachedDepth; |
| break; |
| } |
| ++depth; |
| current = m_graph.m_cpsNaturalLoops->innerMostOuterLoop(*current); |
| } |
| loops[loopIndex] = std::tuple { &loop, depth }; |
| } |
| std::sort(loops.begin(), loops.end(), [&](const auto& lhs, const auto& rhs) { |
| return std::get<1>(lhs) > std::get<1>(rhs); |
| }); |
| return loops; |
| } |
| |
| bool tryUnroll(const NaturalLoop* loop) |
| { |
| if (UNLIKELY(Options::verboseLoopUnrolling())) { |
| const NaturalLoop* outerLoop = m_graph.m_cpsNaturalLoops->innerMostOuterLoop(*loop); |
| dataLogLnIf(Options::verboseLoopUnrolling(), "\nTry unroll innerMostLoop=", *loop, " with innerMostOuterLoop=", outerLoop ? *outerLoop : NaturalLoop()); |
| } |
| |
| LoopData data = { loop }; |
| |
| if (!shouldUnrollLoop(data)) |
| return false; |
| |
| // PreHeader PreHeader |
| // | | |
| // Header <--- HeaderBodyTailGraph_0 <-- original loop |
| // | | unrolled to | |
| // Body | ================> HeaderBodyTailGraph_1 <-- 1st copy |
| // | | | |
| // Tail ------ ... |
| // | | |
| // Next HeaderBodyTailGraph_n <-- n_th copy |
| // | |
| // Next |
| // |
| // Note that NaturalLoop's body includes Header, Body, and Tail. The unrolling |
| // process appends the HeaderBodyTailGraph copies in reverse order (from n_th to 1st). |
| |
| if (!locatePreHeader(data)) |
| return false; |
| dataLogLnIf(Options::verboseLoopUnrolling(), "\tFound PreHeader with LoopData=", data); |
| |
| if (!locateTail(data)) |
| return false; |
| dataLogLnIf(Options::verboseLoopUnrolling(), "\tFound Tail with LoopData=", data); |
| |
| if (!identifyInductionVariable(data)) |
| return false; |
| dataLogLnIf(Options::verboseLoopUnrolling(), "\tFound InductionVariable with LoopData=", data); |
| |
| if (!canCloneLoop(data)) |
| return false; |
| |
| BasicBlock* header = data.header(); |
| unrollLoop(data); |
| |
| if (UNLIKELY(Options::verboseLoopUnrolling())) { |
| dataLogLn("\tGraph after Loop Unrolling for loop"); |
| m_graph.dump(); |
| } |
| |
| if (UNLIKELY(Options::printEachUnrolledLoop())) |
| dataLogLn("\tIn function ", m_graph.m_codeBlock->inferredName(), ", successfully unrolled the loop header=", *header); |
| return true; |
| } |
| |
| bool locatePreHeader(LoopData& data) |
| { |
| BasicBlock* preHeader = nullptr; |
| BasicBlock* header = data.header(); |
| |
| // This is guaranteed because we expect the CFG not to have unreachable code. Therefore, a |
| // loop header must have a predecessor. (Also, we don't allow the root block to be a loop, |
| // which cuts out the one other way of having a loop header with only one predecessor.) |
| DFG_ASSERT(m_graph, header->at(0), header->predecessors.size() > 1, header->predecessors.size()); |
| |
| uint32_t preHeaderCount = 0; |
| for (uint32_t i = header->predecessors.size(); i--;) { |
| BasicBlock* predecessor = header->predecessors[i]; |
| if (m_graph.m_cpsDominators->dominates(header, predecessor)) |
| continue; |
| |
| preHeader = predecessor; |
| ++preHeaderCount; |
| } |
| |
| if (preHeaderCount != 1) |
| return false; |
| |
| data.preHeader = preHeader; |
| return true; |
| } |
| |
| bool locateTail(LoopData& data) |
| { |
| BasicBlock* header = data.header(); |
| BasicBlock* tail = nullptr; |
| |
| for (BasicBlock* predecessor : header->predecessors) { |
| if (!m_graph.m_cpsDominators->dominates(header, predecessor)) |
| continue; |
| |
| if (tail) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *header, " since it contains two tails: ", *predecessor, " and ", *tail); |
| return false; |
| } |
| |
| tail = predecessor; |
| } |
| |
| if (!tail) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *header, " since it has no tail"); |
| return false; |
| } |
| |
| // PreHeader PreHeader |
| // | | |
| // Header <--- Header_0 |
| // | | unrolled to | |
| // | Tail =================> Branch_0 |
| // | | | |
| // Branch ---- Tail_0 |
| // | | |
| // Next ... |
| // | |
| // Header_n |
| // | |
| // Branch_n |
| // | |
| // Next |
| // |
| // FIXME: This is not supported yet. We should do it only if it's profitable. |
| if (!tail->terminal()->isBranch()) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *header, " since it has a non-branch tail"); |
| return false; |
| } |
| |
| for (BasicBlock* successor : tail->successors()) { |
| if (data.loop->contains(successor)) |
| continue; |
| data.next = successor; |
| } |
| data.tail = tail; |
| |
| // PreHeader |
| // | |
| // Header <---------- |
| // | | |
| // Body | |
| // | True/False | |
| // Tail ------------- |
| // | False/True |
| // Next |
| // |
| // Determine if the condition should be inverted based on whether the "not taken" branch points into the loop. |
| Node* terminal = tail->terminal(); |
| ASSERT(terminal->op() == Branch); |
| if (data.loop->contains(terminal->branchData()->notTaken.block)) { |
| // If tail's branch is both jumping into the loop, then it is not a tail. |
| // This happens when we already unrolled this loop before. |
| if (data.loop->contains(terminal->branchData()->taken.block)) |
| return false; |
| data.inverseCondition = true; |
| } else |
| data.inverseCondition = false; |
| |
| return true; |
| } |
| |
| bool isSupportedConditionOp(NodeType op); |
| bool isSupportedUpdateOp(NodeType op); |
| |
| ComparisonFunction comparisonFunction(Node* condition, bool inverseCondition); |
| UpdateFunction updateFunction(Node* update); |
| |
| bool identifyInductionVariable(LoopData& data) |
| { |
| Node* condition = data.condition(); |
| ASSERT(condition); |
| auto isConditionValid = [&]() ALWAYS_INLINE_LAMBDA { |
| if (!isSupportedConditionOp(condition->op())) |
| return false; |
| |
| // Condition left |
| Edge update = condition->child1(); |
| if (!isSupportedUpdateOp(update->op()) || update.useKind() != Int32Use) |
| return false; |
| // FIXME: Currently, we assume the left operand is the induction variable. |
| if (update->child1()->op() != GetLocal) |
| return false; |
| if (!update->child2()->isInt32Constant()) |
| return false; |
| |
| // Condition right |
| Edge operand = condition->child2(); |
| if (!operand->isInt32Constant() || operand.useKind() != Int32Use) |
| return false; |
| |
| data.operand = condition->child2()->asInt32(); |
| data.update = condition->child1().node(); |
| data.updateValue = update->child2()->asInt32(); |
| data.inductionVariable = condition->child1()->child1().node(); |
| return true; |
| }; |
| if (!isConditionValid()) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *data.header(), " since the invalid loop condition node D@", condition->index()); |
| return false; |
| } |
| |
| auto isInitialValueValid = [&]() ALWAYS_INLINE_LAMBDA { |
| Node* initialization = nullptr; |
| for (Node* n : *data.preHeader) { |
| if (n->op() != SetLocal || !data.isInductionVariable(n)) |
| continue; |
| initialization = n; |
| } |
| if (!initialization || !initialization->child1()->isInt32Constant()) |
| return false; |
| data.initialValue = initialization->child1()->asInt32(); |
| return true; |
| }; |
| if (!isInitialValueValid()) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *data.header(), " since the initial value is invalid"); |
| return false; |
| } |
| |
| auto isInductionVariableValid = [&]() ALWAYS_INLINE_LAMBDA { |
| uint32_t updateCount = 0; |
| for (uint32_t i = 0; i < data.loopSize(); ++i) { |
| BasicBlock* body = data.loopBody(i); |
| for (Node* node : *body) { |
| if (node->op() != SetLocal || !data.isInductionVariable(node)) |
| continue; |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Induction variable ", data.inductionVariable->index(), " is updated at node ", node->index(), " at ", *body); |
| ++updateCount; |
| // FIXME: Maybe we can extend this and do better here? |
| if (updateCount != 1) |
| return false; |
| if (!m_graph.m_cpsDominators->dominates(data.tail, body)) |
| return false; |
| } |
| } |
| return true; |
| }; |
| if (!isInductionVariableValid()) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *data.header(), " since the induction variable is invalid"); |
| return false; |
| } |
| |
| // Compute the number of iterations in the loop. |
| { |
| CheckedUint32 iterationCount = 0; |
| auto compare = comparisonFunction(condition, data.inverseCondition.value()); |
| auto update = updateFunction(data.update); |
| for (CheckedInt32 i = data.initialValue; compare(i, data.operand);) { |
| if (iterationCount > Options::maxLoopUnrollingIterationCount()) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *data.header(), " since maxLoopUnrollingIterationCount =", Options::maxLoopUnrollingIterationCount()); |
| return false; |
| } |
| i = update(i, data.updateValue); |
| if (i.hasOverflowed()) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *data.header(), " since the induction variable overflowed after the update"); |
| return false; |
| } |
| ++iterationCount; |
| if (iterationCount.hasOverflowed()) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *data.header(), " since the iteration count overflowed after the update"); |
| return false; |
| } |
| } |
| if (!iterationCount) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *data.header(), " since the iteration count is zero"); |
| return false; |
| } |
| data.iterationCount = iterationCount; |
| } |
| return true; |
| } |
| |
| bool shouldUnrollLoop(LoopData& data) |
| { |
| uint32_t totalNodeCount = 0; |
| for (uint32_t i = 0; i < data.loopSize(); ++i) { |
| BasicBlock* body = data.loopBody(i); |
| if (!body->isReachable) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *data.header(), " since block ", *body, " is not reachable"); |
| return false; |
| } |
| |
| // FIXME: We may also need to check whether the block is valid using CFA. |
| // If the block is unreachable or invalid in the CFG, we can directly |
| // ignore the loop, avoiding unnecessary cloneability checks for nodes in invalid blocks. |
| |
| totalNodeCount += body->size(); |
| if (totalNodeCount > Options::maxLoopUnrollingBodyNodeSize()) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *data.header(), " and loop node count=", totalNodeCount, " since maxLoopUnrollingBodyNodeSize =", Options::maxLoopUnrollingBodyNodeSize()); |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| bool canCloneLoop(LoopData& data) |
| { |
| HashSet<Node*> cloneableCache; |
| for (uint32_t i = 0; i < data.loopSize(); ++i) { |
| BasicBlock* body = data.loopBody(i); |
| for (Node* node : *body) { |
| if (!isNodeCloneable(cloneableCache, node)) { |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Skipping loop with header ", *data.header(), " since D@", node->index(), " with op ", node->op(), " is not cloneable"); |
| return false; |
| } |
| } |
| } |
| return true; |
| } |
| |
| BasicBlock* makeBlock(uint32_t executionCount = 0) |
| { |
| auto* block = m_blockInsertionSet.insert(m_graph.numBlocks(), executionCount); |
| block->cfaHasVisited = false; |
| block->cfaDidFinish = false; |
| return block; |
| } |
| |
| void unrollLoop(LoopData& data) |
| { |
| BasicBlock* const header = data.header(); |
| BasicBlock* const tail = data.tail; |
| |
| dataLogLnIf(Options::verboseLoopUnrolling(), "tailTerminalOriginSemantic ", tail->terminal()->origin.semantic); |
| |
| // Mapping from the origin to the clones. |
| UncheckedKeyHashMap<BasicBlock*, BasicBlock*> blockClones; |
| UncheckedKeyHashMap<Node*, Node*> nodeClones; |
| |
| auto replaceOperands = [&](auto& nodes) ALWAYS_INLINE_LAMBDA { |
| for (uint32_t i = 0; i < nodes.size(); ++i) { |
| if (auto& node = nodes.at(i)) { |
| auto itr = nodeClones.find(node); |
| if (itr != nodeClones.end()) |
| node = itr->value; |
| } |
| } |
| }; |
| |
| auto convertTailBranchToNextJump = [&](BasicBlock* tail, BasicBlock* next) { |
| // Why don't we use Jump instead of Branch? The reason is tail's original terminal was Branch. |
| // If we change this from Branch to Jump, we need to preserve how variables are used (via GetLocal, MovHint, SetLocal) |
| // not to confuse these variables liveness, it involves what blocks are used for successors of this tail block. |
| // Here, we can simplify the problem by using Branch and using the original "header" successors as never-taken branch. |
| // FTL's subsequent pass will optimize this and convert this Branch to Jump and/or eliminate this Branch and merge |
| // multiple blocks easily since its condition is constant boolean True. But we do not need to do the complicated analysis |
| // here. So let's just use Branch. |
| ASSERT(tail->terminal()->isBranch()); |
| auto* constant = m_graph.addNode(SpecBoolean, JSConstant, tail->terminal()->origin, OpInfo(m_graph.freezeStrong(jsBoolean(true)))); |
| tail->insertBeforeTerminal(constant); |
| auto* terminal = tail->terminal(); |
| terminal->child1() = Edge(constant, KnownBooleanUse); |
| terminal->branchData()->taken = BranchTarget(next); |
| terminal->branchData()->notTaken = BranchTarget(header); |
| }; |
| |
| #if ASSERT_ENABLED |
| m_graph.initializeNodeOwners(); // This is only used for the debug assertion in cloneNodeImpl. |
| #endif |
| |
| BasicBlock* next = data.next; |
| ASSERT(!data.iterationCount.hasOverflowed() && data.iterationCount); |
| for (uint32_t cloneCount = data.iterationCount - 1; cloneCount--;) { |
| blockClones.clear(); |
| nodeClones.clear(); |
| |
| // 1. Initialize all block clones. |
| for (uint32_t i = 0; i < data.loopSize(); ++i) { |
| BasicBlock* body = data.loopBody(i); |
| blockClones.add(body, makeBlock(body->executionCount)); |
| } |
| |
| for (uint32_t i = 0; i < data.loopSize(); ++i) { |
| BasicBlock* const body = data.loopBody(i); |
| BasicBlock* const clone = blockClones.get(body); |
| |
| // 2. Clone Phis. |
| clone->phis.resize(body->phis.size()); |
| for (size_t i = 0; i < body->phis.size(); ++i) { |
| Node* bodyPhi = body->phis[i]; |
| Node* phiClone = m_graph.addNode(bodyPhi->prediction(), bodyPhi->op(), bodyPhi->origin, OpInfo(bodyPhi->variableAccessData())); |
| nodeClones.add(bodyPhi, phiClone); |
| clone->phis[i] = phiClone; |
| } |
| |
| // 3. Clone nodes. |
| for (Node* node : *body) |
| cloneNode(nodeClones, clone, node); |
| |
| // 4. Clone variables and tail and head. |
| clone->variablesAtTail = body->variablesAtTail; |
| replaceOperands(clone->variablesAtTail); |
| clone->variablesAtHead = body->variablesAtHead; |
| replaceOperands(clone->variablesAtHead); |
| |
| // 5. Clone successors. (predecessors will be fixed in resetReachability below) |
| if (body == tail) { |
| ASSERT(tail->terminal()->isBranch()); |
| convertTailBranchToNextJump(clone, next); |
| } else { |
| for (uint32_t i = 0; i < body->numSuccessors(); ++i) { |
| auto& successor = clone->successor(i); |
| ASSERT(successor == body->successor(i)); |
| if (data.loop->contains(successor)) |
| successor = blockClones.get(successor); |
| } |
| } |
| } |
| |
| next = blockClones.get(header); |
| } |
| |
| // 6. Replace the original loop tail branch with a jump to the last header clone. |
| convertTailBranchToNextJump(tail, next); |
| |
| // Done clone. |
| if (!m_blockInsertionSet.execute()) { |
| m_graph.invalidateCFG(); |
| m_graph.dethread(); |
| } |
| m_graph.resetReachability(); |
| m_graph.killUnreachableBlocks(); |
| ASSERT(m_graph.m_form == LoadStore); |
| } |
| |
| bool isNodeCloneable(HashSet<Node*>& cloneableCache, Node*); |
| Node* cloneNode(UncheckedKeyHashMap<Node*, Node*>& nodeClones, BasicBlock* into, Node*); |
| Node* cloneNodeImpl(UncheckedKeyHashMap<Node*, Node*>& nodeClones, BasicBlock* into, Node*); |
| |
| private: |
| BlockInsertionSet m_blockInsertionSet; |
| }; |
| |
| bool performLoopUnrolling(Graph& graph) |
| { |
| return runPhase<LoopUnrollingPhase>(graph); |
| } |
| |
| void LoopUnrollingPhase::LoopData::dump(PrintStream& out) const |
| { |
| out.print(*loop); |
| |
| out.print(" preHeader="); |
| if (preHeader) |
| out.print(*preHeader); |
| else |
| out.print("<null>"); |
| out.print(", "); |
| |
| out.print("tail="); |
| if (tail) { |
| out.print(*tail, " with branch condition="); |
| Node* condition = this->condition(); |
| if (condition) |
| out.print(condition, "<", condition->op(), ">"); |
| else |
| out.print("<null>"); |
| } else |
| out.print("<null>"); |
| out.print(", "); |
| |
| out.print("next="); |
| if (tail) |
| out.print(*next); |
| else |
| out.print("<null>"); |
| out.print(", "); |
| |
| out.print("inductionVariable="); |
| if (inductionVariable) |
| out.print("D@", inductionVariable->index()); |
| else |
| out.print("<null>"); |
| out.print(", "); |
| |
| out.print("initValue=", initialValue, ", "); |
| out.print("operand=", operand, ", "); |
| |
| out.print("update="); |
| if (update) |
| out.print(update, "<", update->op(), ">"); |
| else |
| out.print("<null>"); |
| out.print(", "); |
| |
| out.print("updateValue=", updateValue, ", "); |
| |
| out.print("iterationCount=", iterationCount, ", "); |
| |
| out.print("inverseCondition=", inverseCondition); |
| } |
| |
| bool LoopUnrollingPhase::isNodeCloneable(HashSet<Node*>& cloneableCache, Node* node) |
| { |
| if (cloneableCache.contains(node)) |
| return true; |
| |
| bool result = true; |
| switch (node->op()) { |
| case Phi: |
| break; |
| case ValueRep: |
| case DoubleRep: |
| case PurifyNaN: |
| case JSConstant: |
| case LoopHint: |
| case PhantomLocal: |
| case SetArgumentDefinitely: |
| case Jump: |
| case Branch: |
| case MovHint: |
| case ExitOK: |
| case ZombieHint: |
| case InvalidationPoint: |
| case Check: |
| case CheckVarargs: |
| case Flush: |
| case GetLocal: |
| case SetLocal: |
| case GetButterfly: |
| case CheckArray: |
| case AssertNotEmpty: |
| case CheckStructure: |
| case FilterCallLinkStatus: |
| case ArrayifyToStructure: |
| case NewArrayWithConstantSize: |
| case NewArrayWithSize: |
| case ValueToInt32: |
| case ArithAdd: |
| case ArithSub: |
| case ArithMul: |
| case ArithDiv: |
| case ArithMod: |
| case ArithBitAnd: |
| case ArithBitOr: |
| case ArithBitNot: |
| case ArithBitRShift: |
| case ArithBitLShift: |
| case ArithBitXor: |
| case BitURShift: |
| case CompareLess: |
| case CompareLessEq: |
| case CompareGreater: |
| case CompareGreaterEq: |
| case CompareEq: |
| case CompareStrictEq: |
| case PutByVal: |
| case PutByValAlias: |
| case GetByVal: { |
| m_graph.doToChildrenWithCheck(node, [&](Edge& edge) { |
| if (isNodeCloneable(cloneableCache, edge.node())) |
| return IterationStatus::Continue; |
| result = false; |
| return IterationStatus::Done; |
| }); |
| break; |
| } |
| default: |
| result = false; |
| } |
| |
| if (result) |
| cloneableCache.add(node); |
| return result; |
| } |
| |
| Node* LoopUnrollingPhase::cloneNode(UncheckedKeyHashMap<Node*, Node*>& nodeClones, BasicBlock* into, Node* node) |
| { |
| ASSERT(node); |
| auto itr = nodeClones.find(node); |
| if (itr != nodeClones.end()) |
| return itr->value; |
| Node* result = cloneNodeImpl(nodeClones, into, node); |
| ASSERT(result); |
| nodeClones.add(node, result); |
| return result; |
| } |
| |
| Node* LoopUnrollingPhase::cloneNodeImpl(UncheckedKeyHashMap<Node*, Node*>& nodeClones, BasicBlock* into, Node* node) |
| { |
| #if ASSERT_ENABLED |
| m_graph.doToChildren(node, [&](Edge& e) { |
| ASSERT(e.node()->owner == node->owner); |
| }); |
| #endif |
| |
| auto cloneEdge = [&](Edge& edge) ALWAYS_INLINE_LAMBDA { |
| return edge ? Edge(cloneNode(nodeClones, into, edge.node()), edge.useKind()) : Edge(); |
| }; |
| |
| switch (node->op()) { |
| case Phi: { |
| // Phi nodes should already be cloned in the step 2 of unrollLoop. |
| RELEASE_ASSERT_NOT_REACHED(); |
| return nullptr; |
| } |
| case Branch: { |
| Node* clone = into->cloneAndAppend(m_graph, node); |
| clone->setOpInfo(OpInfo(m_graph.m_branchData.add(WTFMove(*node->branchData())))); |
| clone->child1() = cloneEdge(node->child1()); |
| return clone; |
| } |
| case PutByVal: |
| case GetByVal: |
| case PutByValAlias: |
| case CheckVarargs: { |
| if (node->hasVarArgs()) { |
| size_t firstChild = m_graph.m_varArgChildren.size(); |
| |
| uint32_t validChildrenCount = 0; |
| m_graph.doToChildren(node, [&](Edge& edge) { |
| m_graph.m_varArgChildren.append(cloneEdge(edge)); |
| ++validChildrenCount; |
| }); |
| |
| uint32_t expectedCount = m_graph.numChildren(node); |
| for (uint32_t i = validChildrenCount; i < expectedCount; ++i) |
| m_graph.m_varArgChildren.append(Edge()); |
| |
| Node* clone = into->cloneAndAppend(m_graph, node); |
| clone->children.setFirstChild(firstChild); |
| return clone; |
| } |
| FALLTHROUGH; |
| } |
| case ValueRep: |
| case DoubleRep: |
| case PurifyNaN: |
| case ExitOK: |
| case LoopHint: |
| case GetButterfly: |
| case JSConstant: |
| case Jump: |
| case CompareLess: |
| case CompareLessEq: |
| case CompareGreater: |
| case CompareGreaterEq: |
| case CompareEq: |
| case CompareStrictEq: |
| case CheckStructure: |
| case ArithBitNot: |
| case ArrayifyToStructure: |
| case ArithBitAnd: |
| case ArithBitOr: |
| case ArithBitRShift: |
| case ArithBitLShift: |
| case ArithBitXor: |
| case BitURShift: |
| case ArithAdd: |
| case ArithSub: |
| case ArithMul: |
| case ArithDiv: |
| case ArithMod: |
| case CheckArray: |
| case FilterCallLinkStatus: |
| case GetLocal: |
| case MovHint: |
| case Flush: |
| case ZombieHint: |
| case SetLocal: |
| case PhantomLocal: |
| case Check: |
| case AssertNotEmpty: |
| case SetArgumentDefinitely: |
| case NewArrayWithSize: |
| case NewArrayWithConstantSize: |
| case ValueToInt32: |
| case InvalidationPoint: { |
| Node* clone = into->cloneAndAppend(m_graph, node); |
| clone->child1() = cloneEdge(node->child1()); |
| clone->child2() = cloneEdge(node->child2()); |
| clone->child3() = cloneEdge(node->child3()); |
| return clone; |
| } |
| default: |
| dataLogLnIf(Options::verboseLoopUnrolling(), "Could not clone node: ", node, " into ", into); |
| RELEASE_ASSERT_NOT_REACHED(); |
| return nullptr; |
| } |
| } |
| |
| // FIXME: Add more condition and update operations if they are profitable. |
| bool LoopUnrollingPhase::isSupportedConditionOp(NodeType op) |
| { |
| switch (op) { |
| case CompareLess: |
| case CompareLessEq: |
| case CompareGreater: |
| case CompareGreaterEq: |
| case CompareEq: |
| case CompareStrictEq: |
| return true; |
| default: |
| return false; |
| } |
| } |
| |
| bool LoopUnrollingPhase::isSupportedUpdateOp(NodeType op) |
| { |
| switch (op) { |
| case ArithAdd: |
| case ArithSub: |
| case ArithMul: |
| case ArithDiv: |
| return true; |
| default: |
| return false; |
| } |
| } |
| |
| LoopUnrollingPhase::ComparisonFunction LoopUnrollingPhase::comparisonFunction(Node* condition, bool inverseCondition) |
| { |
| static const ComparisonFunction less = [](auto a, auto b) { return a < b; }; |
| static const ComparisonFunction lessEq = [](auto a, auto b) { return a <= b; }; |
| static const ComparisonFunction greater = [](auto a, auto b) { return a > b; }; |
| static const ComparisonFunction greaterEq = [](auto a, auto b) { return a >= b; }; |
| static const ComparisonFunction equal = [](auto a, auto b) { return a == b; }; |
| static const ComparisonFunction notEqual = [](auto a, auto b) { return a != b; }; |
| |
| switch (condition->op()) { |
| case CompareLess: |
| return inverseCondition ? greaterEq : less; |
| case CompareLessEq: |
| return inverseCondition ? greater : lessEq; |
| case CompareGreater: |
| return inverseCondition ? lessEq : greater; |
| case CompareGreaterEq: |
| return inverseCondition ? less : greaterEq; |
| case CompareEq: |
| case CompareStrictEq: |
| return inverseCondition ? notEqual : equal; |
| default: |
| RELEASE_ASSERT_NOT_REACHED(); |
| return [](auto, auto) { return false; }; |
| } |
| } |
| |
| LoopUnrollingPhase::UpdateFunction LoopUnrollingPhase::updateFunction(Node* update) |
| { |
| switch (update->op()) { |
| case ArithAdd: |
| return [](auto a, auto b) { return a + b; }; |
| case ArithSub: |
| return [](auto a, auto b) { return a - b; }; |
| case ArithMul: |
| return [](auto a, auto b) { return a * b; }; |
| case ArithDiv: |
| return [](auto a, auto b) { return a / b; }; |
| default: |
| RELEASE_ASSERT_NOT_REACHED(); |
| return [](auto, auto) { return CheckedInt32(); }; |
| } |
| } |
| |
| } |
| } // namespace JSC::DFG |
| |
| #endif // ENABLE(DFG_JIT) |
