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/compiler-source-position-table.h"
8 : #include "src/compiler/graph.h"
9 : #include "src/compiler/node-marker.h"
10 : #include "src/compiler/node-origin-table.h"
11 : #include "src/compiler/node-properties.h"
12 : #include "src/compiler/node.h"
13 : #include "src/zone/zone.h"
14 :
15 : // Loop peeling is an optimization that copies the body of a loop, creating
16 : // a new copy of the body called the "peeled iteration" that represents the
17 : // first iteration. Beginning with a loop as follows:
18 :
19 : // E
20 : // | A
21 : // | | (backedges)
22 : // | +---------------|---------------------------------+
23 : // | | +-------------|-------------------------------+ |
24 : // | | | | +--------+ | |
25 : // | | | | | +----+ | | |
26 : // | | | | | | | | | |
27 : // ( Loop )<-------- ( phiA ) | | | |
28 : // | | | | | |
29 : // ((======P=================U=======|=|=====)) | |
30 : // (( | | )) | |
31 : // (( X <---------------------+ | )) | |
32 : // (( | )) | |
33 : // (( body | )) | |
34 : // (( | )) | |
35 : // (( Y <-----------------------+ )) | |
36 : // (( )) | |
37 : // ((===K====L====M==========================)) | |
38 : // | | | | |
39 : // | | +-----------------------------------------+ |
40 : // | +------------------------------------------------+
41 : // |
42 : // exit
43 :
44 : // The body of the loop is duplicated so that all nodes considered "inside"
45 : // the loop (e.g. {P, U, X, Y, K, L, M}) have a corresponding copies in the
46 : // peeled iteration (e.g. {P', U', X', Y', K', L', M'}). What were considered
47 : // backedges of the loop correspond to edges from the peeled iteration to
48 : // the main loop body, with multiple backedges requiring a merge.
49 :
50 : // Similarly, any exits from the loop body need to be merged with "exits"
51 : // from the peeled iteration, resulting in the graph as follows:
52 :
53 : // E
54 : // | A
55 : // | |
56 : // ((=====P'================U'===============))
57 : // (( ))
58 : // (( X'<-------------+ ))
59 : // (( | ))
60 : // (( peeled iteration | ))
61 : // (( | ))
62 : // (( Y'<-----------+ | ))
63 : // (( | | ))
64 : // ((===K'===L'====M'======|=|===============))
65 : // | | | | |
66 : // +--------+ +-+ +-+ | |
67 : // | | | | |
68 : // | Merge <------phi
69 : // | | |
70 : // | +-----+ |
71 : // | | | (backedges)
72 : // | | +---------------|---------------------------------+
73 : // | | | +-------------|-------------------------------+ |
74 : // | | | | | +--------+ | |
75 : // | | | | | | +----+ | | |
76 : // | | | | | | | | | | |
77 : // | ( Loop )<-------- ( phiA ) | | | |
78 : // | | | | | | |
79 : // | ((======P=================U=======|=|=====)) | |
80 : // | (( | | )) | |
81 : // | (( X <---------------------+ | )) | |
82 : // | (( | )) | |
83 : // | (( body | )) | |
84 : // | (( | )) | |
85 : // | (( Y <-----------------------+ )) | |
86 : // | (( )) | |
87 : // | ((===K====L====M==========================)) | |
88 : // | | | | | |
89 : // | | | +-----------------------------------------+ |
90 : // | | +------------------------------------------------+
91 : // | |
92 : // | |
93 : // +----+ +-+
94 : // | |
95 : // Merge
96 : // |
97 : // exit
98 :
99 : // Note that the boxes ((===)) above are not explicitly represented in the
100 : // graph, but are instead computed by the {LoopFinder}.
101 :
102 : namespace v8 {
103 : namespace internal {
104 : namespace compiler {
105 :
106 : struct Peeling {
107 : // Maps a node to its index in the {pairs} vector.
108 : NodeMarker<size_t> node_map;
109 : // The vector which contains the mapped nodes.
110 : NodeVector* pairs;
111 :
112 : Peeling(Graph* graph, size_t max, NodeVector* p)
113 53862 : : node_map(graph, static_cast<uint32_t>(max)), pairs(p) {}
114 :
115 9780271 : Node* map(Node* node) {
116 9780319 : if (node_map.Get(node) == 0) return node;
117 8246458 : return pairs->at(node_map.Get(node));
118 : }
119 :
120 1411829 : void Insert(Node* original, Node* copy) {
121 2823658 : node_map.Set(original, 1 + pairs->size());
122 1411816 : pairs->push_back(original);
123 1411797 : pairs->push_back(copy);
124 1411723 : }
125 :
126 26930 : void CopyNodes(Graph* graph, Zone* tmp_zone_, Node* dead, NodeRange nodes,
127 : SourcePositionTable* source_positions,
128 : NodeOriginTable* node_origins) {
129 : NodeVector inputs(tmp_zone_);
130 : // Copy all the nodes first.
131 2641008 : for (Node* node : nodes) {
132 : SourcePositionTable::Scope position(
133 1307031 : source_positions, source_positions->GetSourcePosition(node));
134 : NodeOriginTable::Scope origin_scope(node_origins, "copy nodes", node);
135 : inputs.clear();
136 7393140 : for (Node* input : node->inputs()) {
137 9558303 : inputs.push_back(map(input));
138 : }
139 2614098 : Node* copy = graph->NewNode(node->op(), node->InputCount(), &inputs[0]);
140 1307139 : if (NodeProperties::IsTyped(node)) {
141 : NodeProperties::SetType(copy, NodeProperties::GetType(node));
142 : }
143 1307139 : Insert(node, copy);
144 : }
145 :
146 : // Fix remaining inputs of the copies.
147 2614259 : for (Node* original : nodes) {
148 2614330 : Node* copy = pairs->at(node_map.Get(original));
149 12172236 : for (int i = 0; i < copy->InputCount(); i++) {
150 4778987 : copy->ReplaceInput(i, map(original->InputAt(i)));
151 : }
152 : }
153 26931 : }
154 :
155 : bool Marked(Node* node) { return node_map.Get(node) > 0; }
156 : };
157 :
158 :
159 : class PeeledIterationImpl : public PeeledIteration {
160 : public:
161 : NodeVector node_pairs_;
162 : explicit PeeledIterationImpl(Zone* zone) : node_pairs_(zone) {}
163 : };
164 :
165 :
166 63 : Node* PeeledIteration::map(Node* node) {
167 : // TODO(turbofan): we use a simple linear search, since the peeled iteration
168 : // is really only used in testing.
169 : PeeledIterationImpl* impl = static_cast<PeeledIterationImpl*>(this);
170 678 : for (size_t i = 0; i < impl->node_pairs_.size(); i += 2) {
171 719 : if (impl->node_pairs_[i] == node) return impl->node_pairs_[i + 1];
172 : }
173 : return node;
174 : }
175 :
176 75130 : bool LoopPeeler::CanPeel(LoopTree::Loop* loop) {
177 : // Look for returns and if projections that are outside the loop but whose
178 : // control input is inside the loop.
179 37565 : Node* loop_node = loop_tree_->GetLoopControl(loop);
180 2098309 : for (Node* node : loop_tree_->LoopNodes(loop)) {
181 8280199 : for (Node* use : node->uses()) {
182 4469123 : if (!loop_tree_->Contains(loop, use)) {
183 : bool unmarked_exit;
184 200028 : switch (node->opcode()) {
185 : case IrOpcode::kLoopExit:
186 58798 : unmarked_exit = (node->InputAt(1) != loop_node);
187 58798 : break;
188 : case IrOpcode::kLoopExitValue:
189 : case IrOpcode::kLoopExitEffect:
190 61889 : unmarked_exit = (node->InputAt(1)->InputAt(1) != loop_node);
191 61889 : break;
192 : default:
193 79341 : unmarked_exit = (use->opcode() != IrOpcode::kTerminate);
194 : }
195 200028 : if (unmarked_exit) {
196 10620 : if (FLAG_trace_turbo_loop) {
197 0 : Node* loop_node = loop_tree_->GetLoopControl(loop);
198 : PrintF(
199 : "Cannot peel loop %i. Loop exit without explicit mark: Node %i "
200 : "(%s) is inside "
201 : "loop, but its use %i (%s) is outside.\n",
202 : loop_node->id(), node->id(), node->op()->mnemonic(), use->id(),
203 0 : use->op()->mnemonic());
204 : }
205 : return false;
206 : }
207 : }
208 : }
209 : }
210 : return true;
211 : }
212 :
213 172202 : PeeledIteration* LoopPeeler::Peel(LoopTree::Loop* loop) {
214 37548 : if (!CanPeel(loop)) return nullptr;
215 :
216 : //============================================================================
217 : // Construct the peeled iteration.
218 : //============================================================================
219 53862 : PeeledIterationImpl* iter = new (tmp_zone_) PeeledIterationImpl(tmp_zone_);
220 26931 : size_t estimated_peeled_size = 5 + (loop->TotalSize()) * 2;
221 82274 : Peeling peeling(graph_, estimated_peeled_size, &iter->node_pairs_);
222 :
223 26931 : Node* dead = graph_->NewNode(common_->Dead());
224 :
225 : // Map the loop header nodes to their entry values.
226 158561 : for (Node* node : loop_tree_->HeaderNodes(loop)) {
227 104700 : peeling.Insert(node, node->InputAt(kAssumedLoopEntryIndex));
228 : }
229 :
230 : // Copy all the nodes of loop body for the peeled iteration.
231 : peeling.CopyNodes(graph_, tmp_zone_, dead, loop_tree_->BodyNodes(loop),
232 53862 : source_positions_, node_origins_);
233 :
234 : //============================================================================
235 : // Replace the entry to the loop with the output of the peeled iteration.
236 : //============================================================================
237 26931 : Node* loop_node = loop_tree_->GetLoopControl(loop);
238 : Node* new_entry;
239 26931 : int backedges = loop_node->InputCount() - 1;
240 26931 : if (backedges > 1) {
241 : // Multiple backedges from original loop, therefore multiple output edges
242 : // from the peeled iteration.
243 3 : NodeVector inputs(tmp_zone_);
244 18 : for (int i = 1; i < loop_node->InputCount(); i++) {
245 12 : inputs.push_back(peeling.map(loop_node->InputAt(i)));
246 : }
247 : Node* merge =
248 3 : graph_->NewNode(common_->Merge(backedges), backedges, &inputs[0]);
249 :
250 : // Merge values from the multiple output edges of the peeled iteration.
251 13 : for (Node* node : loop_tree_->HeaderNodes(loop)) {
252 5 : if (node->opcode() == IrOpcode::kLoop) continue; // already done.
253 : inputs.clear();
254 8 : for (int i = 0; i < backedges; i++) {
255 12 : inputs.push_back(peeling.map(node->InputAt(1 + i)));
256 : }
257 6 : for (Node* input : inputs) {
258 4 : if (input != inputs[0]) { // Non-redundant phi.
259 2 : inputs.push_back(merge);
260 2 : const Operator* op = common_->ResizeMergeOrPhi(node->op(), backedges);
261 2 : Node* phi = graph_->NewNode(op, backedges + 1, &inputs[0]);
262 2 : node->ReplaceInput(0, phi);
263 2 : break;
264 : }
265 : }
266 : }
267 3 : new_entry = merge;
268 : } else {
269 : // Only one backedge, simply replace the input to loop with output of
270 : // peeling.
271 131624 : for (Node* node : loop_tree_->HeaderNodes(loop)) {
272 104696 : node->ReplaceInput(0, peeling.map(node->InputAt(1)));
273 : }
274 26928 : new_entry = peeling.map(loop_node->InputAt(1));
275 : }
276 26931 : loop_node->ReplaceInput(0, new_entry);
277 :
278 : //============================================================================
279 : // Change the exit and exit markers to merge/phi/effect-phi.
280 : //============================================================================
281 145384 : for (Node* exit : loop_tree_->ExitNodes(loop)) {
282 91523 : switch (exit->opcode()) {
283 : case IrOpcode::kLoopExit:
284 : // Change the loop exit node to a merge node.
285 36181 : exit->ReplaceInput(1, peeling.map(exit->InputAt(0)));
286 36180 : NodeProperties::ChangeOp(exit, common_->Merge(2));
287 36180 : break;
288 : case IrOpcode::kLoopExitValue:
289 : // Change exit marker to phi.
290 38346 : exit->InsertInput(graph_->zone(), 1, peeling.map(exit->InputAt(0)));
291 : NodeProperties::ChangeOp(
292 19173 : exit, common_->Phi(MachineRepresentation::kTagged, 2));
293 19173 : break;
294 : case IrOpcode::kLoopExitEffect:
295 : // Change effect exit marker to effect phi.
296 72340 : exit->InsertInput(graph_->zone(), 1, peeling.map(exit->InputAt(0)));
297 36170 : NodeProperties::ChangeOp(exit, common_->EffectPhi(2));
298 36170 : break;
299 : default:
300 : break;
301 : }
302 : }
303 : return iter;
304 : }
305 :
306 79753 : void LoopPeeler::PeelInnerLoops(LoopTree::Loop* loop) {
307 : // If the loop has nested loops, peel inside those.
308 42155 : if (!loop->children().empty()) {
309 16045 : for (LoopTree::Loop* inner_loop : loop->children()) {
310 5744 : PeelInnerLoops(inner_loop);
311 : }
312 : return;
313 : }
314 : // Only peel small-enough loops.
315 37598 : if (loop->TotalSize() > LoopPeeler::kMaxPeeledNodes) return;
316 37539 : if (FLAG_trace_turbo_loop) {
317 0 : PrintF("Peeling loop with header: ");
318 0 : for (Node* node : loop_tree_->HeaderNodes(loop)) {
319 0 : PrintF("%i ", node->id());
320 : }
321 0 : PrintF("\n");
322 : }
323 :
324 37539 : Peel(loop);
325 : }
326 :
327 : namespace {
328 :
329 103727 : void EliminateLoopExit(Node* node) {
330 : DCHECK_EQ(IrOpcode::kLoopExit, node->opcode());
331 : // The exit markers take the loop exit as input. We iterate over uses
332 : // and remove all the markers from the graph.
333 875600 : for (Edge edge : node->use_edges()) {
334 334073 : if (NodeProperties::IsControlEdge(edge)) {
335 334074 : Node* marker = edge.from();
336 334074 : if (marker->opcode() == IrOpcode::kLoopExitValue) {
337 121878 : NodeProperties::ReplaceUses(marker, marker->InputAt(0));
338 121878 : marker->Kill();
339 212196 : } else if (marker->opcode() == IrOpcode::kLoopExitEffect) {
340 : NodeProperties::ReplaceUses(marker, nullptr,
341 103727 : NodeProperties::GetEffectInput(marker));
342 103727 : marker->Kill();
343 : }
344 : }
345 : }
346 : NodeProperties::ReplaceUses(node, nullptr, nullptr,
347 103727 : NodeProperties::GetControlInput(node, 0));
348 103727 : node->Kill();
349 103727 : }
350 :
351 : } // namespace
352 :
353 451937 : void LoopPeeler::PeelInnerLoopsOfTree() {
354 940286 : for (LoopTree::Loop* loop : loop_tree_->outer_loops()) {
355 36411 : PeelInnerLoops(loop);
356 : }
357 :
358 451938 : EliminateLoopExits(graph_, tmp_zone_);
359 451966 : }
360 :
361 : // static
362 1368310 : void LoopPeeler::EliminateLoopExits(Graph* graph, Zone* tmp_zone) {
363 456085 : ZoneQueue<Node*> queue(tmp_zone);
364 : ZoneVector<bool> visited(graph->NodeCount(), false, tmp_zone);
365 912214 : queue.push(graph->end());
366 7749408 : while (!queue.empty()) {
367 27488640 : Node* node = queue.front();
368 : queue.pop();
369 :
370 6837174 : if (node->opcode() == IrOpcode::kLoopExit) {
371 103726 : Node* control = NodeProperties::GetControlInput(node);
372 103727 : EliminateLoopExit(node);
373 311181 : if (!visited[control->id()]) {
374 : visited[control->id()] = true;
375 : queue.push(control);
376 : }
377 : } else {
378 34709341 : for (int i = 0; i < node->op()->ControlInputCount(); i++) {
379 7080786 : Node* control = NodeProperties::GetControlInput(node, i);
380 21242430 : if (!visited[control->id()]) {
381 : visited[control->id()] = true;
382 : queue.push(control);
383 : }
384 : }
385 : }
386 : }
387 456114 : }
388 :
389 : } // namespace compiler
390 : } // namespace internal
391 183867 : } // namespace v8
|
