| // 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/common-operator.h" |
| #include "src/compiler/graph.h" |
| #include "src/compiler/loop-peeling.h" |
| #include "src/compiler/node.h" |
| #include "src/compiler/node-marker.h" |
| #include "src/compiler/node-properties.h" |
| #include "src/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, Zone* tmp_zone, 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) { |
| NodeVector inputs(tmp_zone); |
| // Copy all the nodes first. |
| for (Node* node : nodes) { |
| inputs.clear(); |
| for (Node* input : node->inputs()) inputs.push_back(map(input)); |
| Insert(node, graph->NewNode(node->op(), node->InputCount(), &inputs[0])); |
| } |
| |
| // 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; |
| } |
| |
| |
| static void FindLoopExits(LoopTree* loop_tree, LoopTree::Loop* loop, |
| NodeVector& exits, NodeVector& rets) { |
| // Look for returns and if projections that are outside the loop but whose |
| // control input is inside the loop. |
| for (Node* node : loop_tree->LoopNodes(loop)) { |
| for (Node* use : node->uses()) { |
| if (!loop_tree->Contains(loop, use)) { |
| if (IrOpcode::IsIfProjectionOpcode(use->opcode())) { |
| // This is a branch from inside the loop to outside the loop. |
| exits.push_back(use); |
| } else if (use->opcode() == IrOpcode::kReturn && |
| loop_tree->Contains(loop, |
| NodeProperties::GetControlInput(use))) { |
| // This is a return from inside the loop. |
| rets.push_back(use); |
| } |
| } |
| } |
| } |
| } |
| |
| |
| bool LoopPeeler::CanPeel(LoopTree* loop_tree, LoopTree::Loop* loop) { |
| Zone zone(loop_tree->zone()->allocator()); |
| NodeVector exits(&zone); |
| NodeVector rets(&zone); |
| FindLoopExits(loop_tree, loop, exits, rets); |
| return exits.size() <= 1u; |
| } |
| |
| |
| PeeledIteration* LoopPeeler::Peel(Graph* graph, CommonOperatorBuilder* common, |
| LoopTree* loop_tree, LoopTree::Loop* loop, |
| Zone* tmp_zone) { |
| //============================================================================ |
| // Find the loop exit region to determine if this loop can be peeled. |
| //============================================================================ |
| NodeVector exits(tmp_zone); |
| NodeVector rets(tmp_zone); |
| FindLoopExits(loop_tree, loop, exits, rets); |
| |
| if (exits.size() != 1) return nullptr; // not peelable currently. |
| |
| //============================================================================ |
| // Construct the peeled iteration. |
| //============================================================================ |
| PeeledIterationImpl* iter = new (tmp_zone) PeeledIterationImpl(tmp_zone); |
| size_t estimated_peeled_size = |
| 5 + (loop->TotalSize() + exits.size() + rets.size()) * 2; |
| Peeling peeling(graph, tmp_zone, 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)); |
| |
| //============================================================================ |
| // 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(0))); |
| } |
| new_entry = peeling.map(loop_node->InputAt(1)); |
| } |
| loop_node->ReplaceInput(0, new_entry); |
| |
| //============================================================================ |
| // Duplicate the loop exit region and add a merge. |
| //============================================================================ |
| |
| // Currently we are limited to peeling loops with a single exit. The exit is |
| // the postdominator of the loop (ignoring returns). |
| Node* postdom = exits[0]; |
| for (Node* node : rets) exits.push_back(node); |
| for (Node* use : postdom->uses()) { |
| if (NodeProperties::IsPhi(use)) exits.push_back(use); |
| } |
| |
| NodeRange exit_range(&exits[0], &exits[0] + exits.size()); |
| peeling.CopyNodes(graph, tmp_zone, dead, exit_range); |
| |
| Node* merge = graph->NewNode(common->Merge(2), postdom, peeling.map(postdom)); |
| postdom->ReplaceUses(merge); |
| merge->ReplaceInput(0, postdom); // input 0 overwritten by above line. |
| |
| // Find and update all the edges into either the loop or exit region. |
| for (int i = 0; i < 2; i++) { |
| NodeRange range = i == 0 ? loop_tree->LoopNodes(loop) : exit_range; |
| ZoneVector<Edge> value_edges(tmp_zone); |
| ZoneVector<Edge> effect_edges(tmp_zone); |
| |
| for (Node* node : range) { |
| // Gather value and effect edges from outside the region. |
| for (Edge edge : node->use_edges()) { |
| if (!peeling.Marked(edge.from())) { |
| // Edge from outside the loop into the region. |
| if (NodeProperties::IsValueEdge(edge) || |
| NodeProperties::IsContextEdge(edge)) { |
| value_edges.push_back(edge); |
| } else if (NodeProperties::IsEffectEdge(edge)) { |
| effect_edges.push_back(edge); |
| } else { |
| // don't do anything for control edges. |
| // TODO(titzer): should update control edges to peeled? |
| } |
| } |
| } |
| |
| // Update all the value and effect edges at once. |
| if (!value_edges.empty()) { |
| // TODO(titzer): machine type is wrong here. |
| Node* phi = |
| graph->NewNode(common->Phi(MachineRepresentation::kTagged, 2), node, |
| peeling.map(node), merge); |
| for (Edge edge : value_edges) edge.UpdateTo(phi); |
| value_edges.clear(); |
| } |
| if (!effect_edges.empty()) { |
| Node* effect_phi = graph->NewNode(common->EffectPhi(2), node, |
| peeling.map(node), merge); |
| for (Edge edge : effect_edges) edge.UpdateTo(effect_phi); |
| effect_edges.clear(); |
| } |
| } |
| } |
| |
| return iter; |
| } |
| |
| } // namespace compiler |
| } // namespace internal |
| } // namespace v8 |