Line data Source code
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 : #include "src/compiler/common-operator.h"
7 : #include "src/compiler/graph.h"
8 : #include "src/compiler/node-marker.h"
9 : #include "src/compiler/node-properties.h"
10 : #include "src/compiler/node.h"
11 : #include "src/zone/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 :
100 : namespace v8 {
101 : namespace internal {
102 : namespace compiler {
103 :
104 : struct 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 66788 : : node_map(graph, static_cast<uint32_t>(max)), pairs(p) {}
112 :
113 15465117 : Node* map(Node* node) {
114 15465117 : if (node_map.Get(node) == 0) return node;
115 12069592 : return pairs->at(node_map.Get(node));
116 : }
117 :
118 2205738 : void Insert(Node* original, Node* copy) {
119 4411476 : node_map.Set(original, 1 + pairs->size());
120 2205723 : pairs->push_back(original);
121 2205709 : pairs->push_back(copy);
122 2205637 : }
123 :
124 33399 : void CopyNodes(Graph* graph, Zone* tmp_zone, Node* dead, NodeRange nodes) {
125 : NodeVector inputs(tmp_zone);
126 : // Copy all the nodes first.
127 4178808 : for (Node* node : nodes) {
128 : inputs.clear();
129 9611417 : for (Node* input : node->inputs()) {
130 15077423 : inputs.push_back(map(input));
131 : }
132 4145342 : Node* copy = graph->NewNode(node->op(), node->InputCount(), &inputs[0]);
133 2072835 : if (NodeProperties::IsTyped(node)) {
134 : NodeProperties::SetType(copy, NodeProperties::GetType(node));
135 : }
136 2072835 : Insert(node, copy);
137 : }
138 :
139 : // Fix remaining inputs of the copies.
140 4145617 : for (Node* original : nodes) {
141 4145670 : Node* copy = pairs->at(node_map.Get(original));
142 19223198 : for (int i = 0; i < copy->InputCount(); i++) {
143 7538792 : copy->ReplaceInput(i, map(original->InputAt(i)));
144 : }
145 : }
146 33394 : }
147 :
148 : bool Marked(Node* node) { return node_map.Get(node) > 0; }
149 : };
150 :
151 :
152 : class PeeledIterationImpl : public PeeledIteration {
153 : public:
154 : NodeVector node_pairs_;
155 : explicit PeeledIterationImpl(Zone* zone) : node_pairs_(zone) {}
156 : };
157 :
158 :
159 63 : Node* PeeledIteration::map(Node* node) {
160 : // TODO(turbofan): we use a simple linear search, since the peeled iteration
161 : // is really only used in testing.
162 : PeeledIterationImpl* impl = static_cast<PeeledIterationImpl*>(this);
163 678 : for (size_t i = 0; i < impl->node_pairs_.size(); i += 2) {
164 719 : if (impl->node_pairs_[i] == node) return impl->node_pairs_[i + 1];
165 : }
166 : return node;
167 : }
168 :
169 74360 : bool LoopPeeler::CanPeel(LoopTree* loop_tree, LoopTree::Loop* loop) {
170 : // Look for returns and if projections that are outside the loop but whose
171 : // control input is inside the loop.
172 37180 : Node* loop_node = loop_tree->GetLoopControl(loop);
173 2944454 : for (Node* node : loop_tree->LoopNodes(loop)) {
174 8458967 : for (Node* use : node->uses()) {
175 5835509 : if (!loop_tree->Contains(loop, use)) {
176 : bool unmarked_exit;
177 358536 : switch (node->opcode()) {
178 : case IrOpcode::kLoopExit:
179 117619 : unmarked_exit = (node->InputAt(1) != loop_node);
180 117619 : break;
181 : case IrOpcode::kLoopExitValue:
182 : case IrOpcode::kLoopExitEffect:
183 166197 : unmarked_exit = (node->InputAt(1)->InputAt(1) != loop_node);
184 166197 : break;
185 : default:
186 74720 : unmarked_exit = (use->opcode() != IrOpcode::kTerminate);
187 : }
188 358536 : if (unmarked_exit) {
189 3770 : if (FLAG_trace_turbo_loop) {
190 0 : Node* loop_node = loop_tree->GetLoopControl(loop);
191 : PrintF(
192 : "Cannot peel loop %i. Loop exit without explicit mark: Node %i "
193 : "(%s) is inside "
194 : "loop, but its use %i (%s) is outside.\n",
195 : loop_node->id(), node->id(), node->op()->mnemonic(), use->id(),
196 0 : use->op()->mnemonic());
197 : }
198 : return false;
199 : }
200 : }
201 : }
202 : }
203 : return true;
204 : }
205 :
206 :
207 184943 : PeeledIteration* LoopPeeler::Peel(Graph* graph, CommonOperatorBuilder* common,
208 166970 : LoopTree* loop_tree, LoopTree::Loop* loop,
209 : Zone* tmp_zone) {
210 37163 : if (!CanPeel(loop_tree, loop)) return nullptr;
211 :
212 : //============================================================================
213 : // Construct the peeled iteration.
214 : //============================================================================
215 : PeeledIterationImpl* iter = new (tmp_zone) PeeledIterationImpl(tmp_zone);
216 33394 : size_t estimated_peeled_size = 5 + (loop->TotalSize()) * 2;
217 33394 : Peeling peeling(graph, tmp_zone, estimated_peeled_size, &iter->node_pairs_);
218 :
219 33394 : Node* dead = graph->NewNode(common->Dead());
220 :
221 : // Map the loop header nodes to their entry values.
222 166311 : for (Node* node : loop_tree->HeaderNodes(loop)) {
223 132917 : peeling.Insert(node, node->InputAt(kAssumedLoopEntryIndex));
224 : }
225 :
226 : // Copy all the nodes of loop body for the peeled iteration.
227 33394 : peeling.CopyNodes(graph, tmp_zone, dead, loop_tree->BodyNodes(loop));
228 :
229 : //============================================================================
230 : // Replace the entry to the loop with the output of the peeled iteration.
231 : //============================================================================
232 33394 : Node* loop_node = loop_tree->GetLoopControl(loop);
233 : Node* new_entry;
234 33394 : int backedges = loop_node->InputCount() - 1;
235 33394 : if (backedges > 1) {
236 : // Multiple backedges from original loop, therefore multiple output edges
237 : // from the peeled iteration.
238 : NodeVector inputs(tmp_zone);
239 18 : for (int i = 1; i < loop_node->InputCount(); i++) {
240 12 : inputs.push_back(peeling.map(loop_node->InputAt(i)));
241 : }
242 : Node* merge =
243 3 : graph->NewNode(common->Merge(backedges), backedges, &inputs[0]);
244 :
245 : // Merge values from the multiple output edges of the peeled iteration.
246 10 : for (Node* node : loop_tree->HeaderNodes(loop)) {
247 5 : if (node->opcode() == IrOpcode::kLoop) continue; // already done.
248 : inputs.clear();
249 8 : for (int i = 0; i < backedges; i++) {
250 12 : inputs.push_back(peeling.map(node->InputAt(1 + i)));
251 : }
252 6 : for (Node* input : inputs) {
253 4 : if (input != inputs[0]) { // Non-redundant phi.
254 2 : inputs.push_back(merge);
255 2 : const Operator* op = common->ResizeMergeOrPhi(node->op(), backedges);
256 2 : Node* phi = graph->NewNode(op, backedges + 1, &inputs[0]);
257 2 : node->ReplaceInput(0, phi);
258 2 : break;
259 : }
260 : }
261 : }
262 3 : new_entry = merge;
263 : } else {
264 : // Only one backedge, simply replace the input to loop with output of
265 : // peeling.
266 166303 : for (Node* node : loop_tree->HeaderNodes(loop)) {
267 132912 : node->ReplaceInput(0, peeling.map(node->InputAt(1)));
268 : }
269 33391 : new_entry = peeling.map(loop_node->InputAt(1));
270 : }
271 33394 : loop_node->ReplaceInput(0, new_entry);
272 :
273 : //============================================================================
274 : // Change the exit and exit markers to merge/phi/effect-phi.
275 : //============================================================================
276 256711 : for (Node* exit : loop_tree->ExitNodes(loop)) {
277 223317 : switch (exit->opcode()) {
278 : case IrOpcode::kLoopExit:
279 : // Change the loop exit node to a merge node.
280 75537 : exit->ReplaceInput(1, peeling.map(exit->InputAt(0)));
281 75537 : NodeProperties::ChangeOp(exit, common->Merge(2));
282 75537 : break;
283 : case IrOpcode::kLoopExitValue:
284 : // Change exit marker to phi.
285 144506 : exit->InsertInput(graph->zone(), 1, peeling.map(exit->InputAt(0)));
286 : NodeProperties::ChangeOp(
287 72253 : exit, common->Phi(MachineRepresentation::kTagged, 2));
288 72253 : break;
289 : case IrOpcode::kLoopExitEffect:
290 : // Change effect exit marker to effect phi.
291 151054 : exit->InsertInput(graph->zone(), 1, peeling.map(exit->InputAt(0)));
292 75527 : NodeProperties::ChangeOp(exit, common->EffectPhi(2));
293 75527 : break;
294 : default:
295 : break;
296 : }
297 : }
298 : return iter;
299 : }
300 :
301 : namespace {
302 :
303 44014 : void PeelInnerLoops(Graph* graph, CommonOperatorBuilder* common,
304 37240 : LoopTree* loop_tree, LoopTree::Loop* loop,
305 : Zone* temp_zone) {
306 : // If the loop has nested loops, peel inside those.
307 44014 : if (!loop->children().empty()) {
308 22042 : for (LoopTree::Loop* inner_loop : loop->children()) {
309 7634 : PeelInnerLoops(graph, common, loop_tree, inner_loop, temp_zone);
310 : }
311 : return;
312 : }
313 : // Only peel small-enough loops.
314 37240 : if (loop->TotalSize() > LoopPeeler::kMaxPeeledNodes) return;
315 37154 : if (FLAG_trace_turbo_loop) {
316 0 : PrintF("Peeling loop with header: ");
317 0 : for (Node* node : loop_tree->HeaderNodes(loop)) {
318 0 : PrintF("%i ", node->id());
319 : }
320 0 : PrintF("\n");
321 : }
322 :
323 37154 : LoopPeeler::Peel(graph, common, loop_tree, loop, temp_zone);
324 : }
325 :
326 66776 : void EliminateLoopExit(Node* node) {
327 : DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
328 : // The exit markers take the loop exit as input. We iterate over uses
329 : // and remove all the markers from the graph.
330 513036 : for (Edge edge : node->use_edges()) {
331 223130 : if (NodeProperties::IsControlEdge(edge)) {
332 223130 : Node* marker = edge.from();
333 223130 : if (marker->opcode() == IrOpcode::kLoopExitValue) {
334 85190 : NodeProperties::ReplaceUses(marker, marker->InputAt(0));
335 85190 : marker->Kill();
336 137940 : } else if (marker->opcode() == IrOpcode::kLoopExitEffect) {
337 : NodeProperties::ReplaceUses(marker, nullptr,
338 66776 : NodeProperties::GetEffectInput(marker));
339 66776 : marker->Kill();
340 : }
341 : }
342 : }
343 : NodeProperties::ReplaceUses(node, nullptr, nullptr,
344 66776 : NodeProperties::GetControlInput(node, 0));
345 66776 : node->Kill();
346 66776 : }
347 :
348 : } // namespace
349 :
350 : // static
351 388307 : void LoopPeeler::PeelInnerLoopsOfTree(Graph* graph,
352 : CommonOperatorBuilder* common,
353 : LoopTree* loop_tree, Zone* temp_zone) {
354 812994 : for (LoopTree::Loop* loop : loop_tree->outer_loops()) {
355 36380 : PeelInnerLoops(graph, common, loop_tree, loop, temp_zone);
356 : }
357 :
358 388307 : EliminateLoopExits(graph, temp_zone);
359 388307 : }
360 :
361 : // static
362 1185909 : void LoopPeeler::EliminateLoopExits(Graph* graph, Zone* temp_zone) {
363 395303 : ZoneQueue<Node*> queue(temp_zone);
364 : ZoneVector<bool> visited(graph->NodeCount(), false, temp_zone);
365 790606 : queue.push(graph->end());
366 7914015 : while (!queue.empty()) {
367 28983240 : Node* node = queue.front();
368 : queue.pop();
369 :
370 7123409 : if (node->opcode() == IrOpcode::kLoopExit) {
371 66776 : Node* control = NodeProperties::GetControlInput(node);
372 66776 : EliminateLoopExit(node);
373 200328 : if (!visited[control->id()]) {
374 : visited[control->id()] = true;
375 : queue.push(control);
376 : }
377 : } else {
378 37152633 : for (int i = 0; i < node->op()->ControlInputCount(); i++) {
379 7679789 : Node* control = NodeProperties::GetControlInput(node, i);
380 23039367 : if (!visited[control->id()]) {
381 : visited[control->id()] = true;
382 : queue.push(control);
383 : }
384 : }
385 : }
386 : }
387 395303 : }
388 :
389 : } // namespace compiler
390 : } // namespace internal
391 : } // namespace v8
|
