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/common-operator.h"
6#include "src/compiler/graph.h"
7#include "src/compiler/loop-peeling.h"
8#include "src/compiler/node.h"
9#include "src/compiler/node-marker.h"
10#include "src/compiler/node-properties.h"
11#include "src/zone.h"
12
13// Loop peeling is an optimization that copies the body of a loop, creating
14// a new copy of the body called the "peeled iteration" that represents the
15// first iteration. Beginning with a loop as follows:
16
17//             E
18//             |                 A
19//             |                 |                     (backedges)
20//             | +---------------|---------------------------------+
21//             | | +-------------|-------------------------------+ |
22//             | | |             | +--------+                    | |
23//             | | |             | | +----+ |                    | |
24//             | | |             | | |    | |                    | |
25//           ( Loop )<-------- ( phiA )   | |                    | |
26//              |                 |       | |                    | |
27//      ((======P=================U=======|=|=====))             | |
28//      ((                                | |     ))             | |
29//      ((        X <---------------------+ |     ))             | |
30//      ((                                  |     ))             | |
31//      ((     body                         |     ))             | |
32//      ((                                  |     ))             | |
33//      ((        Y <-----------------------+     ))             | |
34//      ((                                        ))             | |
35//      ((===K====L====M==========================))             | |
36//           |    |    |                                         | |
37//           |    |    +-----------------------------------------+ |
38//           |    +------------------------------------------------+
39//           |
40//          exit
41
42// The body of the loop is duplicated so that all nodes considered "inside"
43// the loop (e.g. {P, U, X, Y, K, L, M}) have a corresponding copies in the
44// peeled iteration (e.g. {P', U', X', Y', K', L', M'}). What were considered
45// backedges of the loop correspond to edges from the peeled iteration to
46// the main loop body, with multiple backedges requiring a merge.
47
48// Similarly, any exits from the loop body need to be merged with "exits"
49// from the peeled iteration, resulting in the graph as follows:
50
51//             E
52//             |                 A
53//             |                 |
54//      ((=====P'================U'===============))
55//      ((                                        ))
56//      ((        X'<-------------+               ))
57//      ((                        |               ))
58//      ((   peeled iteration     |               ))
59//      ((                        |               ))
60//      ((        Y'<-----------+ |               ))
61//      ((                      | |               ))
62//      ((===K'===L'====M'======|=|===============))
63//           |    |     |       | |
64//  +--------+    +-+ +-+       | |
65//  |               | |         | |
66//  |              Merge <------phi
67//  |                |           |
68//  |          +-----+           |
69//  |          |                 |                     (backedges)
70//  |          | +---------------|---------------------------------+
71//  |          | | +-------------|-------------------------------+ |
72//  |          | | |             | +--------+                    | |
73//  |          | | |             | | +----+ |                    | |
74//  |          | | |             | | |    | |                    | |
75//  |        ( Loop )<-------- ( phiA )   | |                    | |
76//  |           |                 |       | |                    | |
77//  |   ((======P=================U=======|=|=====))             | |
78//  |   ((                                | |     ))             | |
79//  |   ((        X <---------------------+ |     ))             | |
80//  |   ((                                  |     ))             | |
81//  |   ((     body                         |     ))             | |
82//  |   ((                                  |     ))             | |
83//  |   ((        Y <-----------------------+     ))             | |
84//  |   ((                                        ))             | |
85//  |   ((===K====L====M==========================))             | |
86//  |        |    |    |                                         | |
87//  |        |    |    +-----------------------------------------+ |
88//  |        |    +------------------------------------------------+
89//  |        |
90//  |        |
91//  +----+ +-+
92//       | |
93//      Merge
94//        |
95//      exit
96
97// Note that the boxes ((===)) above are not explicitly represented in the
98// graph, but are instead computed by the {LoopFinder}.
99
100namespace v8 {
101namespace internal {
102namespace compiler {
103
104struct Peeling {
105  // Maps a node to its index in the {pairs} vector.
106  NodeMarker<size_t> node_map;
107  // The vector which contains the mapped nodes.
108  NodeVector* pairs;
109
110  Peeling(Graph* graph, Zone* tmp_zone, size_t max, NodeVector* p)
111      : node_map(graph, static_cast<uint32_t>(max)), pairs(p) {}
112
113  Node* map(Node* node) {
114    if (node_map.Get(node) == 0) return node;
115    return pairs->at(node_map.Get(node));
116  }
117
118  void Insert(Node* original, Node* copy) {
119    node_map.Set(original, 1 + pairs->size());
120    pairs->push_back(original);
121    pairs->push_back(copy);
122  }
123
124  void CopyNodes(Graph* graph, Zone* tmp_zone, Node* dead, NodeRange nodes) {
125    NodeVector inputs(tmp_zone);
126    // Copy all the nodes first.
127    for (Node* node : nodes) {
128      inputs.clear();
129      for (Node* input : node->inputs()) inputs.push_back(map(input));
130      Insert(node, graph->NewNode(node->op(), node->InputCount(), &inputs[0]));
131    }
132
133    // Fix remaining inputs of the copies.
134    for (Node* original : nodes) {
135      Node* copy = pairs->at(node_map.Get(original));
136      for (int i = 0; i < copy->InputCount(); i++) {
137        copy->ReplaceInput(i, map(original->InputAt(i)));
138      }
139    }
140  }
141
142  bool Marked(Node* node) { return node_map.Get(node) > 0; }
143};
144
145
146class PeeledIterationImpl : public PeeledIteration {
147 public:
148  NodeVector node_pairs_;
149  explicit PeeledIterationImpl(Zone* zone) : node_pairs_(zone) {}
150};
151
152
153Node* PeeledIteration::map(Node* node) {
154  // TODO(turbofan): we use a simple linear search, since the peeled iteration
155  // is really only used in testing.
156  PeeledIterationImpl* impl = static_cast<PeeledIterationImpl*>(this);
157  for (size_t i = 0; i < impl->node_pairs_.size(); i += 2) {
158    if (impl->node_pairs_[i] == node) return impl->node_pairs_[i + 1];
159  }
160  return node;
161}
162
163
164static void FindLoopExits(LoopTree* loop_tree, LoopTree::Loop* loop,
165                          NodeVector& exits, NodeVector& rets) {
166  // Look for returns and if projections that are outside the loop but whose
167  // control input is inside the loop.
168  for (Node* node : loop_tree->LoopNodes(loop)) {
169    for (Node* use : node->uses()) {
170      if (!loop_tree->Contains(loop, use)) {
171        if (IrOpcode::IsIfProjectionOpcode(use->opcode())) {
172          // This is a branch from inside the loop to outside the loop.
173          exits.push_back(use);
174        } else if (use->opcode() == IrOpcode::kReturn &&
175                   loop_tree->Contains(loop,
176                                       NodeProperties::GetControlInput(use))) {
177          // This is a return from inside the loop.
178          rets.push_back(use);
179        }
180      }
181    }
182  }
183}
184
185
186bool LoopPeeler::CanPeel(LoopTree* loop_tree, LoopTree::Loop* loop) {
187  Zone zone(loop_tree->zone()->allocator());
188  NodeVector exits(&zone);
189  NodeVector rets(&zone);
190  FindLoopExits(loop_tree, loop, exits, rets);
191  return exits.size() <= 1u;
192}
193
194
195PeeledIteration* LoopPeeler::Peel(Graph* graph, CommonOperatorBuilder* common,
196                                  LoopTree* loop_tree, LoopTree::Loop* loop,
197                                  Zone* tmp_zone) {
198  //============================================================================
199  // Find the loop exit region to determine if this loop can be peeled.
200  //============================================================================
201  NodeVector exits(tmp_zone);
202  NodeVector rets(tmp_zone);
203  FindLoopExits(loop_tree, loop, exits, rets);
204
205  if (exits.size() != 1) return nullptr;  // not peelable currently.
206
207  //============================================================================
208  // Construct the peeled iteration.
209  //============================================================================
210  PeeledIterationImpl* iter = new (tmp_zone) PeeledIterationImpl(tmp_zone);
211  size_t estimated_peeled_size =
212      5 + (loop->TotalSize() + exits.size() + rets.size()) * 2;
213  Peeling peeling(graph, tmp_zone, estimated_peeled_size, &iter->node_pairs_);
214
215  Node* dead = graph->NewNode(common->Dead());
216
217  // Map the loop header nodes to their entry values.
218  for (Node* node : loop_tree->HeaderNodes(loop)) {
219    peeling.Insert(node, node->InputAt(kAssumedLoopEntryIndex));
220  }
221
222  // Copy all the nodes of loop body for the peeled iteration.
223  peeling.CopyNodes(graph, tmp_zone, dead, loop_tree->BodyNodes(loop));
224
225  //============================================================================
226  // Replace the entry to the loop with the output of the peeled iteration.
227  //============================================================================
228  Node* loop_node = loop_tree->GetLoopControl(loop);
229  Node* new_entry;
230  int backedges = loop_node->InputCount() - 1;
231  if (backedges > 1) {
232    // Multiple backedges from original loop, therefore multiple output edges
233    // from the peeled iteration.
234    NodeVector inputs(tmp_zone);
235    for (int i = 1; i < loop_node->InputCount(); i++) {
236      inputs.push_back(peeling.map(loop_node->InputAt(i)));
237    }
238    Node* merge =
239        graph->NewNode(common->Merge(backedges), backedges, &inputs[0]);
240
241    // Merge values from the multiple output edges of the peeled iteration.
242    for (Node* node : loop_tree->HeaderNodes(loop)) {
243      if (node->opcode() == IrOpcode::kLoop) continue;  // already done.
244      inputs.clear();
245      for (int i = 0; i < backedges; i++) {
246        inputs.push_back(peeling.map(node->InputAt(1 + i)));
247      }
248      for (Node* input : inputs) {
249        if (input != inputs[0]) {  // Non-redundant phi.
250          inputs.push_back(merge);
251          const Operator* op = common->ResizeMergeOrPhi(node->op(), backedges);
252          Node* phi = graph->NewNode(op, backedges + 1, &inputs[0]);
253          node->ReplaceInput(0, phi);
254          break;
255        }
256      }
257    }
258    new_entry = merge;
259  } else {
260    // Only one backedge, simply replace the input to loop with output of
261    // peeling.
262    for (Node* node : loop_tree->HeaderNodes(loop)) {
263      node->ReplaceInput(0, peeling.map(node->InputAt(0)));
264    }
265    new_entry = peeling.map(loop_node->InputAt(1));
266  }
267  loop_node->ReplaceInput(0, new_entry);
268
269  //============================================================================
270  // Duplicate the loop exit region and add a merge.
271  //============================================================================
272
273  // Currently we are limited to peeling loops with a single exit. The exit is
274  // the postdominator of the loop (ignoring returns).
275  Node* postdom = exits[0];
276  for (Node* node : rets) exits.push_back(node);
277  for (Node* use : postdom->uses()) {
278    if (NodeProperties::IsPhi(use)) exits.push_back(use);
279  }
280
281  NodeRange exit_range(&exits[0], &exits[0] + exits.size());
282  peeling.CopyNodes(graph, tmp_zone, dead, exit_range);
283
284  Node* merge = graph->NewNode(common->Merge(2), postdom, peeling.map(postdom));
285  postdom->ReplaceUses(merge);
286  merge->ReplaceInput(0, postdom);  // input 0 overwritten by above line.
287
288  // Find and update all the edges into either the loop or exit region.
289  for (int i = 0; i < 2; i++) {
290    NodeRange range = i == 0 ? loop_tree->LoopNodes(loop) : exit_range;
291    ZoneVector<Edge> value_edges(tmp_zone);
292    ZoneVector<Edge> effect_edges(tmp_zone);
293
294    for (Node* node : range) {
295      // Gather value and effect edges from outside the region.
296      for (Edge edge : node->use_edges()) {
297        if (!peeling.Marked(edge.from())) {
298          // Edge from outside the loop into the region.
299          if (NodeProperties::IsValueEdge(edge) ||
300              NodeProperties::IsContextEdge(edge)) {
301            value_edges.push_back(edge);
302          } else if (NodeProperties::IsEffectEdge(edge)) {
303            effect_edges.push_back(edge);
304          } else {
305            // don't do anything for control edges.
306            // TODO(titzer): should update control edges to peeled?
307          }
308        }
309      }
310
311      // Update all the value and effect edges at once.
312      if (!value_edges.empty()) {
313        // TODO(titzer): machine type is wrong here.
314        Node* phi =
315            graph->NewNode(common->Phi(MachineRepresentation::kTagged, 2), node,
316                           peeling.map(node), merge);
317        for (Edge edge : value_edges) edge.UpdateTo(phi);
318        value_edges.clear();
319      }
320      if (!effect_edges.empty()) {
321        Node* effect_phi = graph->NewNode(common->EffectPhi(2), node,
322                                          peeling.map(node), merge);
323        for (Edge edge : effect_edges) edge.UpdateTo(effect_phi);
324        effect_edges.clear();
325      }
326    }
327  }
328
329  return iter;
330}
331
332}  // namespace compiler
333}  // namespace internal
334}  // namespace v8
335