| // Copyright 2015 the V8 project authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #include "src/compiler/loop-peeling.h" |
| #include "src/compiler/common-operator.h" |
| #include "src/compiler/compiler-source-position-table.h" |
| #include "src/compiler/graph.h" |
| #include "src/compiler/node-marker.h" |
| #include "src/compiler/node-properties.h" |
| #include "src/compiler/node.h" |
| #include "src/zone/zone.h" |
| |
| // Loop peeling is an optimization that copies the body of a loop, creating |
| // a new copy of the body called the "peeled iteration" that represents the |
| // first iteration. Beginning with a loop as follows: |
| |
| // E |
| // | A |
| // | | (backedges) |
| // | +---------------|---------------------------------+ |
| // | | +-------------|-------------------------------+ | |
| // | | | | +--------+ | | |
| // | | | | | +----+ | | | |
| // | | | | | | | | | | |
| // ( Loop )<-------- ( phiA ) | | | | |
| // | | | | | | |
| // ((======P=================U=======|=|=====)) | | |
| // (( | | )) | | |
| // (( X <---------------------+ | )) | | |
| // (( | )) | | |
| // (( body | )) | | |
| // (( | )) | | |
| // (( Y <-----------------------+ )) | | |
| // (( )) | | |
| // ((===K====L====M==========================)) | | |
| // | | | | | |
| // | | +-----------------------------------------+ | |
| // | +------------------------------------------------+ |
| // | |
| // exit |
| |
| // The body of the loop is duplicated so that all nodes considered "inside" |
| // the loop (e.g. {P, U, X, Y, K, L, M}) have a corresponding copies in the |
| // peeled iteration (e.g. {P', U', X', Y', K', L', M'}). What were considered |
| // backedges of the loop correspond to edges from the peeled iteration to |
| // the main loop body, with multiple backedges requiring a merge. |
| |
| // Similarly, any exits from the loop body need to be merged with "exits" |
| // from the peeled iteration, resulting in the graph as follows: |
| |
| // E |
| // | A |
| // | | |
| // ((=====P'================U'===============)) |
| // (( )) |
| // (( X'<-------------+ )) |
| // (( | )) |
| // (( peeled iteration | )) |
| // (( | )) |
| // (( Y'<-----------+ | )) |
| // (( | | )) |
| // ((===K'===L'====M'======|=|===============)) |
| // | | | | | |
| // +--------+ +-+ +-+ | | |
| // | | | | | |
| // | Merge <------phi |
| // | | | |
| // | +-----+ | |
| // | | | (backedges) |
| // | | +---------------|---------------------------------+ |
| // | | | +-------------|-------------------------------+ | |
| // | | | | | +--------+ | | |
| // | | | | | | +----+ | | | |
| // | | | | | | | | | | | |
| // | ( Loop )<-------- ( phiA ) | | | | |
| // | | | | | | | |
| // | ((======P=================U=======|=|=====)) | | |
| // | (( | | )) | | |
| // | (( X <---------------------+ | )) | | |
| // | (( | )) | | |
| // | (( body | )) | | |
| // | (( | )) | | |
| // | (( Y <-----------------------+ )) | | |
| // | (( )) | | |
| // | ((===K====L====M==========================)) | | |
| // | | | | | | |
| // | | | +-----------------------------------------+ | |
| // | | +------------------------------------------------+ |
| // | | |
| // | | |
| // +----+ +-+ |
| // | | |
| // Merge |
| // | |
| // exit |
| |
| // Note that the boxes ((===)) above are not explicitly represented in the |
| // graph, but are instead computed by the {LoopFinder}. |
| |
| namespace v8 { |
| namespace internal { |
| namespace compiler { |
| |
| struct Peeling { |
| // Maps a node to its index in the {pairs} vector. |
| NodeMarker<size_t> node_map; |
| // The vector which contains the mapped nodes. |
| NodeVector* pairs; |
| |
| Peeling(Graph* graph, size_t max, NodeVector* p) |
| : node_map(graph, static_cast<uint32_t>(max)), pairs(p) {} |
| |
| Node* map(Node* node) { |
| if (node_map.Get(node) == 0) return node; |
| return pairs->at(node_map.Get(node)); |
| } |
| |
| void Insert(Node* original, Node* copy) { |
| node_map.Set(original, 1 + pairs->size()); |
| pairs->push_back(original); |
| pairs->push_back(copy); |
| } |
| |
| void CopyNodes(Graph* graph, Zone* tmp_zone_, Node* dead, NodeRange nodes, |
| SourcePositionTable* source_positions) { |
| NodeVector inputs(tmp_zone_); |
| // Copy all the nodes first. |
| for (Node* node : nodes) { |
| SourcePositionTable::Scope position( |
| source_positions, source_positions->GetSourcePosition(node)); |
| inputs.clear(); |
| for (Node* input : node->inputs()) { |
| inputs.push_back(map(input)); |
| } |
| Node* copy = graph->NewNode(node->op(), node->InputCount(), &inputs[0]); |
| if (NodeProperties::IsTyped(node)) { |
| NodeProperties::SetType(copy, NodeProperties::GetType(node)); |
| } |
| Insert(node, copy); |
| } |
| |
| // Fix remaining inputs of the copies. |
| for (Node* original : nodes) { |
| Node* copy = pairs->at(node_map.Get(original)); |
| for (int i = 0; i < copy->InputCount(); i++) { |
| copy->ReplaceInput(i, map(original->InputAt(i))); |
| } |
| } |
| } |
| |
| bool Marked(Node* node) { return node_map.Get(node) > 0; } |
| }; |
| |
| |
| class PeeledIterationImpl : public PeeledIteration { |
| public: |
| NodeVector node_pairs_; |
| explicit PeeledIterationImpl(Zone* zone) : node_pairs_(zone) {} |
| }; |
| |
| |
| Node* PeeledIteration::map(Node* node) { |
| // TODO(turbofan): we use a simple linear search, since the peeled iteration |
| // is really only used in testing. |
| PeeledIterationImpl* impl = static_cast<PeeledIterationImpl*>(this); |
| for (size_t i = 0; i < impl->node_pairs_.size(); i += 2) { |
| if (impl->node_pairs_[i] == node) return impl->node_pairs_[i + 1]; |
| } |
| return node; |
| } |
| |
| bool LoopPeeler::CanPeel(LoopTree::Loop* loop) { |
| // Look for returns and if projections that are outside the loop but whose |
| // control input is inside the loop. |
| Node* loop_node = loop_tree_->GetLoopControl(loop); |
| for (Node* node : loop_tree_->LoopNodes(loop)) { |
| for (Node* use : node->uses()) { |
| if (!loop_tree_->Contains(loop, use)) { |
| bool unmarked_exit; |
| switch (node->opcode()) { |
| case IrOpcode::kLoopExit: |
| unmarked_exit = (node->InputAt(1) != loop_node); |
| break; |
| case IrOpcode::kLoopExitValue: |
| case IrOpcode::kLoopExitEffect: |
| unmarked_exit = (node->InputAt(1)->InputAt(1) != loop_node); |
| break; |
| default: |
| unmarked_exit = (use->opcode() != IrOpcode::kTerminate); |
| } |
| if (unmarked_exit) { |
| if (FLAG_trace_turbo_loop) { |
| Node* loop_node = loop_tree_->GetLoopControl(loop); |
| PrintF( |
| "Cannot peel loop %i. Loop exit without explicit mark: Node %i " |
| "(%s) is inside " |
| "loop, but its use %i (%s) is outside.\n", |
| loop_node->id(), node->id(), node->op()->mnemonic(), use->id(), |
| use->op()->mnemonic()); |
| } |
| return false; |
| } |
| } |
| } |
| } |
| return true; |
| } |
| |
| PeeledIteration* LoopPeeler::Peel(LoopTree::Loop* loop) { |
| if (!CanPeel(loop)) return nullptr; |
| |
| //============================================================================ |
| // Construct the peeled iteration. |
| //============================================================================ |
| PeeledIterationImpl* iter = new (tmp_zone_) PeeledIterationImpl(tmp_zone_); |
| size_t estimated_peeled_size = 5 + (loop->TotalSize()) * 2; |
| Peeling peeling(graph_, estimated_peeled_size, &iter->node_pairs_); |
| |
| Node* dead = graph_->NewNode(common_->Dead()); |
| |
| // Map the loop header nodes to their entry values. |
| for (Node* node : loop_tree_->HeaderNodes(loop)) { |
| peeling.Insert(node, node->InputAt(kAssumedLoopEntryIndex)); |
| } |
| |
| // Copy all the nodes of loop body for the peeled iteration. |
| peeling.CopyNodes(graph_, tmp_zone_, dead, loop_tree_->BodyNodes(loop), |
| source_positions_); |
| |
| //============================================================================ |
| // Replace the entry to the loop with the output of the peeled iteration. |
| //============================================================================ |
| Node* loop_node = loop_tree_->GetLoopControl(loop); |
| Node* new_entry; |
| int backedges = loop_node->InputCount() - 1; |
| if (backedges > 1) { |
| // Multiple backedges from original loop, therefore multiple output edges |
| // from the peeled iteration. |
| NodeVector inputs(tmp_zone_); |
| for (int i = 1; i < loop_node->InputCount(); i++) { |
| inputs.push_back(peeling.map(loop_node->InputAt(i))); |
| } |
| Node* merge = |
| graph_->NewNode(common_->Merge(backedges), backedges, &inputs[0]); |
| |
| // Merge values from the multiple output edges of the peeled iteration. |
| for (Node* node : loop_tree_->HeaderNodes(loop)) { |
| if (node->opcode() == IrOpcode::kLoop) continue; // already done. |
| inputs.clear(); |
| for (int i = 0; i < backedges; i++) { |
| inputs.push_back(peeling.map(node->InputAt(1 + i))); |
| } |
| for (Node* input : inputs) { |
| if (input != inputs[0]) { // Non-redundant phi. |
| inputs.push_back(merge); |
| const Operator* op = common_->ResizeMergeOrPhi(node->op(), backedges); |
| Node* phi = graph_->NewNode(op, backedges + 1, &inputs[0]); |
| node->ReplaceInput(0, phi); |
| break; |
| } |
| } |
| } |
| new_entry = merge; |
| } else { |
| // Only one backedge, simply replace the input to loop with output of |
| // peeling. |
| for (Node* node : loop_tree_->HeaderNodes(loop)) { |
| node->ReplaceInput(0, peeling.map(node->InputAt(1))); |
| } |
| new_entry = peeling.map(loop_node->InputAt(1)); |
| } |
| loop_node->ReplaceInput(0, new_entry); |
| |
| //============================================================================ |
| // Change the exit and exit markers to merge/phi/effect-phi. |
| //============================================================================ |
| for (Node* exit : loop_tree_->ExitNodes(loop)) { |
| switch (exit->opcode()) { |
| case IrOpcode::kLoopExit: |
| // Change the loop exit node to a merge node. |
| exit->ReplaceInput(1, peeling.map(exit->InputAt(0))); |
| NodeProperties::ChangeOp(exit, common_->Merge(2)); |
| break; |
| case IrOpcode::kLoopExitValue: |
| // Change exit marker to phi. |
| exit->InsertInput(graph_->zone(), 1, peeling.map(exit->InputAt(0))); |
| NodeProperties::ChangeOp( |
| exit, common_->Phi(MachineRepresentation::kTagged, 2)); |
| break; |
| case IrOpcode::kLoopExitEffect: |
| // Change effect exit marker to effect phi. |
| exit->InsertInput(graph_->zone(), 1, peeling.map(exit->InputAt(0))); |
| NodeProperties::ChangeOp(exit, common_->EffectPhi(2)); |
| break; |
| default: |
| break; |
| } |
| } |
| return iter; |
| } |
| |
| void LoopPeeler::PeelInnerLoops(LoopTree::Loop* loop) { |
| // If the loop has nested loops, peel inside those. |
| if (!loop->children().empty()) { |
| for (LoopTree::Loop* inner_loop : loop->children()) { |
| PeelInnerLoops(inner_loop); |
| } |
| return; |
| } |
| // Only peel small-enough loops. |
| if (loop->TotalSize() > LoopPeeler::kMaxPeeledNodes) return; |
| if (FLAG_trace_turbo_loop) { |
| PrintF("Peeling loop with header: "); |
| for (Node* node : loop_tree_->HeaderNodes(loop)) { |
| PrintF("%i ", node->id()); |
| } |
| PrintF("\n"); |
| } |
| |
| Peel(loop); |
| } |
| |
| namespace { |
| |
| void EliminateLoopExit(Node* node) { |
| DCHECK_EQ(IrOpcode::kLoopExit, node->opcode()); |
| // The exit markers take the loop exit as input. We iterate over uses |
| // and remove all the markers from the graph. |
| for (Edge edge : node->use_edges()) { |
| if (NodeProperties::IsControlEdge(edge)) { |
| Node* marker = edge.from(); |
| if (marker->opcode() == IrOpcode::kLoopExitValue) { |
| NodeProperties::ReplaceUses(marker, marker->InputAt(0)); |
| marker->Kill(); |
| } else if (marker->opcode() == IrOpcode::kLoopExitEffect) { |
| NodeProperties::ReplaceUses(marker, nullptr, |
| NodeProperties::GetEffectInput(marker)); |
| marker->Kill(); |
| } |
| } |
| } |
| NodeProperties::ReplaceUses(node, nullptr, nullptr, |
| NodeProperties::GetControlInput(node, 0)); |
| node->Kill(); |
| } |
| |
| } // namespace |
| |
| void LoopPeeler::PeelInnerLoopsOfTree() { |
| for (LoopTree::Loop* loop : loop_tree_->outer_loops()) { |
| PeelInnerLoops(loop); |
| } |
| |
| EliminateLoopExits(graph_, tmp_zone_); |
| } |
| |
| // static |
| void LoopPeeler::EliminateLoopExits(Graph* graph, Zone* tmp_zone) { |
| ZoneQueue<Node*> queue(tmp_zone); |
| ZoneVector<bool> visited(graph->NodeCount(), false, tmp_zone); |
| queue.push(graph->end()); |
| while (!queue.empty()) { |
| Node* node = queue.front(); |
| queue.pop(); |
| |
| if (node->opcode() == IrOpcode::kLoopExit) { |
| Node* control = NodeProperties::GetControlInput(node); |
| EliminateLoopExit(node); |
| if (!visited[control->id()]) { |
| visited[control->id()] = true; |
| queue.push(control); |
| } |
| } else { |
| for (int i = 0; i < node->op()->ControlInputCount(); i++) { |
| Node* control = NodeProperties::GetControlInput(node, i); |
| if (!visited[control->id()]) { |
| visited[control->id()] = true; |
| queue.push(control); |
| } |
| } |
| } |
| } |
| } |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |