1// Copyright 2015 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "src/compiler/loop-peeling.h"
6
7#include "src/compiler/common-operator.h"
8#include "src/compiler/compiler-source-position-table.h"
9#include "src/compiler/graph.h"
10#include "src/compiler/loop-analysis.h"
11#include "src/compiler/node-marker.h"
12#include "src/compiler/node-origin-table.h"
13#include "src/compiler/node-properties.h"
14#include "src/compiler/node.h"
15#include "src/zone/zone.h"
16
17// Loop peeling is an optimization that copies the body of a loop, creating
18// a new copy of the body called the "peeled iteration" that represents the
19// first iteration. Beginning with a loop as follows:
20
21//             E
22//             |                 A
23//             |                 |                     (backedges)
24//             | +---------------|---------------------------------+
25//             | | +-------------|-------------------------------+ |
26//             | | |             | +--------+                    | |
27//             | | |             | | +----+ |                    | |
28//             | | |             | | |    | |                    | |
29//           ( Loop )<-------- ( phiA )   | |                    | |
30//              |                 |       | |                    | |
31//      ((======P=================U=======|=|=====))             | |
32//      ((                                | |     ))             | |
33//      ((        X <---------------------+ |     ))             | |
34//      ((                                  |     ))             | |
35//      ((     body                         |     ))             | |
36//      ((                                  |     ))             | |
37//      ((        Y <-----------------------+     ))             | |
38//      ((                                        ))             | |
39//      ((===K====L====M==========================))             | |
40//           |    |    |                                         | |
41//           |    |    +-----------------------------------------+ |
42//           |    +------------------------------------------------+
43//           |
44//          exit
45
46// The body of the loop is duplicated so that all nodes considered "inside"
47// the loop (e.g. {P, U, X, Y, K, L, M}) have a corresponding copies in the
48// peeled iteration (e.g. {P', U', X', Y', K', L', M'}). What were considered
49// backedges of the loop correspond to edges from the peeled iteration to
50// the main loop body, with multiple backedges requiring a merge.
51
52// Similarly, any exits from the loop body need to be merged with "exits"
53// from the peeled iteration, resulting in the graph as follows:
54
55//             E
56//             |                 A
57//             |                 |
58//      ((=====P'================U'===============))
59//      ((                                        ))
60//      ((        X'<-------------+               ))
61//      ((                        |               ))
62//      ((   peeled iteration     |               ))
63//      ((                        |               ))
64//      ((        Y'<-----------+ |               ))
65//      ((                      | |               ))
66//      ((===K'===L'====M'======|=|===============))
67//           |    |     |       | |
68//  +--------+    +-+ +-+       | |
69//  |               | |         | |
70//  |              Merge <------phi
71//  |                |           |
72//  |          +-----+           |
73//  |          |                 |                     (backedges)
74//  |          | +---------------|---------------------------------+
75//  |          | | +-------------|-------------------------------+ |
76//  |          | | |             | +--------+                    | |
77//  |          | | |             | | +----+ |                    | |
78//  |          | | |             | | |    | |                    | |
79//  |        ( Loop )<-------- ( phiA )   | |                    | |
80//  |           |                 |       | |                    | |
81//  |   ((======P=================U=======|=|=====))             | |
82//  |   ((                                | |     ))             | |
83//  |   ((        X <---------------------+ |     ))             | |
84//  |   ((                                  |     ))             | |
85//  |   ((     body                         |     ))             | |
86//  |   ((                                  |     ))             | |
87//  |   ((        Y <-----------------------+     ))             | |
88//  |   ((                                        ))             | |
89//  |   ((===K====L====M==========================))             | |
90//  |        |    |    |                                         | |
91//  |        |    |    +-----------------------------------------+ |
92//  |        |    +------------------------------------------------+
93//  |        |
94//  |        |
95//  +----+ +-+
96//       | |
97//      Merge
98//        |
99//      exit
100
101// Note that the boxes ((===)) above are not explicitly represented in the
102// graph, but are instead computed by the {LoopFinder}.
103
104namespace v8 {
105namespace internal {
106namespace compiler {
107
108class PeeledIterationImpl : public PeeledIteration {
109 public:
110  NodeVector node_pairs_;
111  explicit PeeledIterationImpl(Zone* zone) : node_pairs_(zone) {}
112};
113
114
115Node* PeeledIteration::map(Node* node) {
116  // TODO(turbofan): we use a simple linear search, since the peeled iteration
117  // is really only used in testing.
118  PeeledIterationImpl* impl = static_cast<PeeledIterationImpl*>(this);
119  for (size_t i = 0; i < impl->node_pairs_.size(); i += 2) {
120    if (impl->node_pairs_[i] == node) return impl->node_pairs_[i + 1];
121  }
122  return node;
123}
124
125PeeledIteration* LoopPeeler::Peel(LoopTree::Loop* loop) {
126  if (!CanPeel(loop)) return nullptr;
127
128  //============================================================================
129  // Construct the peeled iteration.
130  //============================================================================
131  PeeledIterationImpl* iter = tmp_zone_->New<PeeledIterationImpl>(tmp_zone_);
132  uint32_t estimated_peeled_size = 5 + loop->TotalSize() * 2;
133  NodeCopier copier(graph_, estimated_peeled_size, &iter->node_pairs_, 1);
134
135  Node* dead = graph_->NewNode(common_->Dead());
136
137  // Map the loop header nodes to their entry values.
138  for (Node* node : loop_tree_->HeaderNodes(loop)) {
139    copier.Insert(node, node->InputAt(kAssumedLoopEntryIndex));
140  }
141
142  // Copy all the nodes of loop body for the peeled iteration.
143  copier.CopyNodes(graph_, tmp_zone_, dead, loop_tree_->BodyNodes(loop),
144                   source_positions_, node_origins_);
145
146  //============================================================================
147  // Replace the entry to the loop with the output of the peeled iteration.
148  //============================================================================
149  Node* loop_node = loop_tree_->GetLoopControl(loop);
150  Node* new_entry;
151  int backedges = loop_node->InputCount() - 1;
152  if (backedges > 1) {
153    // Multiple backedges from original loop, therefore multiple output edges
154    // from the peeled iteration.
155    NodeVector inputs(tmp_zone_);
156    for (int i = 1; i < loop_node->InputCount(); i++) {
157      inputs.push_back(copier.map(loop_node->InputAt(i)));
158    }
159    Node* merge =
160        graph_->NewNode(common_->Merge(backedges), backedges, &inputs[0]);
161
162    // Merge values from the multiple output edges of the peeled iteration.
163    for (Node* node : loop_tree_->HeaderNodes(loop)) {
164      if (node->opcode() == IrOpcode::kLoop) continue;  // already done.
165      inputs.clear();
166      for (int i = 0; i < backedges; i++) {
167        inputs.push_back(copier.map(node->InputAt(1 + i)));
168      }
169      for (Node* input : inputs) {
170        if (input != inputs[0]) {  // Non-redundant phi.
171          inputs.push_back(merge);
172          const Operator* op = common_->ResizeMergeOrPhi(node->op(), backedges);
173          Node* phi = graph_->NewNode(op, backedges + 1, &inputs[0]);
174          node->ReplaceInput(0, phi);
175          break;
176        }
177      }
178    }
179    new_entry = merge;
180  } else {
181    // Only one backedge, simply replace the input to loop with output of
182    // peeling.
183    for (Node* node : loop_tree_->HeaderNodes(loop)) {
184      node->ReplaceInput(0, copier.map(node->InputAt(1)));
185    }
186    new_entry = copier.map(loop_node->InputAt(1));
187  }
188  loop_node->ReplaceInput(0, new_entry);
189
190  //============================================================================
191  // Change the exit and exit markers to merge/phi/effect-phi.
192  //============================================================================
193  for (Node* exit : loop_tree_->ExitNodes(loop)) {
194    switch (exit->opcode()) {
195      case IrOpcode::kLoopExit:
196        // Change the loop exit node to a merge node.
197        exit->ReplaceInput(1, copier.map(exit->InputAt(0)));
198        NodeProperties::ChangeOp(exit, common_->Merge(2));
199        break;
200      case IrOpcode::kLoopExitValue:
201        // Change exit marker to phi.
202        exit->InsertInput(graph_->zone(), 1, copier.map(exit->InputAt(0)));
203        NodeProperties::ChangeOp(
204            exit, common_->Phi(LoopExitValueRepresentationOf(exit->op()), 2));
205        break;
206      case IrOpcode::kLoopExitEffect:
207        // Change effect exit marker to effect phi.
208        exit->InsertInput(graph_->zone(), 1, copier.map(exit->InputAt(0)));
209        NodeProperties::ChangeOp(exit, common_->EffectPhi(2));
210        break;
211      default:
212        break;
213    }
214  }
215  return iter;
216}
217
218void LoopPeeler::PeelInnerLoops(LoopTree::Loop* loop) {
219  // If the loop has nested loops, peel inside those.
220  if (!loop->children().empty()) {
221    for (LoopTree::Loop* inner_loop : loop->children()) {
222      PeelInnerLoops(inner_loop);
223    }
224    return;
225  }
226  // Only peel small-enough loops.
227  if (loop->TotalSize() > LoopPeeler::kMaxPeeledNodes) return;
228  if (FLAG_trace_turbo_loop) {
229    PrintF("Peeling loop with header: ");
230    for (Node* node : loop_tree_->HeaderNodes(loop)) {
231      PrintF("%i ", node->id());
232    }
233    PrintF("\n");
234  }
235
236  Peel(loop);
237}
238
239void LoopPeeler::EliminateLoopExit(Node* node) {
240  DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
241  // The exit markers take the loop exit as input. We iterate over uses
242  // and remove all the markers from the graph.
243  for (Edge edge : node->use_edges()) {
244    if (NodeProperties::IsControlEdge(edge)) {
245      Node* marker = edge.from();
246      if (marker->opcode() == IrOpcode::kLoopExitValue) {
247        NodeProperties::ReplaceUses(marker, marker->InputAt(0));
248        marker->Kill();
249      } else if (marker->opcode() == IrOpcode::kLoopExitEffect) {
250        NodeProperties::ReplaceUses(marker, nullptr,
251                                    NodeProperties::GetEffectInput(marker));
252        marker->Kill();
253      }
254    }
255  }
256  NodeProperties::ReplaceUses(node, nullptr, nullptr,
257                              NodeProperties::GetControlInput(node, 0));
258  node->Kill();
259}
260
261void LoopPeeler::PeelInnerLoopsOfTree() {
262  for (LoopTree::Loop* loop : loop_tree_->outer_loops()) {
263    PeelInnerLoops(loop);
264  }
265
266  EliminateLoopExits(graph_, tmp_zone_);
267}
268
269// static
270void LoopPeeler::EliminateLoopExits(Graph* graph, Zone* tmp_zone) {
271  ZoneQueue<Node*> queue(tmp_zone);
272  ZoneVector<bool> visited(graph->NodeCount(), false, tmp_zone);
273  queue.push(graph->end());
274  while (!queue.empty()) {
275    Node* node = queue.front();
276    queue.pop();
277
278    if (node->opcode() == IrOpcode::kLoopExit) {
279      Node* control = NodeProperties::GetControlInput(node);
280      EliminateLoopExit(node);
281      if (!visited[control->id()]) {
282        visited[control->id()] = true;
283        queue.push(control);
284      }
285    } else {
286      for (int i = 0; i < node->op()->ControlInputCount(); i++) {
287        Node* control = NodeProperties::GetControlInput(node, i);
288        if (!visited[control->id()]) {
289          visited[control->id()] = true;
290          queue.push(control);
291        }
292      }
293    }
294  }
295}
296
297}  // namespace compiler
298}  // namespace internal
299}  // namespace v8
300