Line data Source code
1 : // Copyright 2014 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/access-builder.h"
6 : #include "src/compiler/common-operator.h"
7 : #include "src/compiler/graph.h"
8 : #include "src/compiler/graph-visualizer.h"
9 : #include "src/compiler/js-graph.h"
10 : #include "src/compiler/js-operator.h"
11 : #include "src/compiler/loop-analysis.h"
12 : #include "src/compiler/node.h"
13 : #include "src/compiler/opcodes.h"
14 : #include "src/compiler/operator.h"
15 : #include "src/compiler/schedule.h"
16 : #include "src/compiler/scheduler.h"
17 : #include "src/compiler/simplified-operator.h"
18 : #include "src/compiler/verifier.h"
19 : #include "test/cctest/cctest.h"
20 :
21 : namespace v8 {
22 : namespace internal {
23 : namespace compiler {
24 :
25 47436 : static Operator kIntAdd(IrOpcode::kInt32Add, Operator::kPure, "Int32Add", 2, 0,
26 23718 : 0, 1, 0, 0);
27 47436 : static Operator kIntLt(IrOpcode::kInt32LessThan, Operator::kPure,
28 23718 : "Int32LessThan", 2, 0, 0, 1, 0, 0);
29 47436 : static Operator kStore(IrOpcode::kStore, Operator::kNoProperties, "Store", 1, 1,
30 23718 : 1, 0, 1, 0);
31 :
32 : static const int kNumLeafs = 4;
33 :
34 : // A helper for all tests dealing with LoopFinder.
35 195648 : class LoopFinderTester : HandleAndZoneScope {
36 : public:
37 195648 : LoopFinderTester()
38 391296 : : isolate(main_isolate()),
39 : common(main_zone()),
40 : graph(main_zone()),
41 : jsgraph(main_isolate(), &graph, &common, nullptr, nullptr, nullptr),
42 195648 : start(graph.NewNode(common.Start(1))),
43 195648 : end(graph.NewNode(common.End(1), start)),
44 195648 : p0(graph.NewNode(common.Parameter(0), start)),
45 195648 : zero(jsgraph.Int32Constant(0)),
46 195648 : one(jsgraph.OneConstant()),
47 195648 : half(jsgraph.Constant(0.5)),
48 195648 : self(graph.NewNode(common.Int32Constant(0xaabbccdd))),
49 195648 : dead(graph.NewNode(common.Dead())),
50 2347776 : loop_tree(nullptr) {
51 195648 : graph.SetEnd(end);
52 195648 : graph.SetStart(start);
53 195648 : leaf[0] = zero;
54 195648 : leaf[1] = one;
55 195648 : leaf[2] = half;
56 195648 : leaf[3] = p0;
57 195648 : }
58 :
59 : Isolate* isolate;
60 : CommonOperatorBuilder common;
61 : Graph graph;
62 : JSGraph jsgraph;
63 : Node* start;
64 : Node* end;
65 : Node* p0;
66 : Node* zero;
67 : Node* one;
68 : Node* half;
69 : Node* self;
70 : Node* dead;
71 : Node* leaf[kNumLeafs];
72 : LoopTree* loop_tree;
73 :
74 : Node* Phi(Node* a) {
75 : return SetSelfReferences(graph.NewNode(op(1, false), a, start));
76 : }
77 :
78 : Node* Phi(Node* a, Node* b) {
79 : return SetSelfReferences(graph.NewNode(op(2, false), a, b, start));
80 : }
81 :
82 : Node* Phi(Node* a, Node* b, Node* c) {
83 : return SetSelfReferences(graph.NewNode(op(3, false), a, b, c, start));
84 : }
85 :
86 : Node* Phi(Node* a, Node* b, Node* c, Node* d) {
87 : return SetSelfReferences(graph.NewNode(op(4, false), a, b, c, d, start));
88 : }
89 :
90 : Node* EffectPhi(Node* a) {
91 : return SetSelfReferences(graph.NewNode(op(1, true), a, start));
92 : }
93 :
94 : Node* EffectPhi(Node* a, Node* b) {
95 : return SetSelfReferences(graph.NewNode(op(2, true), a, b, start));
96 : }
97 :
98 : Node* EffectPhi(Node* a, Node* b, Node* c) {
99 : return SetSelfReferences(graph.NewNode(op(3, true), a, b, c, start));
100 : }
101 :
102 : Node* EffectPhi(Node* a, Node* b, Node* c, Node* d) {
103 : return SetSelfReferences(graph.NewNode(op(4, true), a, b, c, d, start));
104 : }
105 :
106 : Node* SetSelfReferences(Node* node) {
107 : for (Edge edge : node->input_edges()) {
108 : if (edge.to() == self) node->ReplaceInput(edge.index(), node);
109 : }
110 : return node;
111 : }
112 :
113 162 : const Operator* op(int count, bool effect) {
114 6 : return effect ? common.EffectPhi(count)
115 168 : : common.Phi(MachineRepresentation::kTagged, count);
116 : }
117 :
118 126 : Node* Return(Node* val, Node* effect, Node* control) {
119 126 : Node* zero = graph.NewNode(common.Int32Constant(0));
120 126 : Node* ret = graph.NewNode(common.Return(), zero, val, effect, control);
121 126 : end->ReplaceInput(0, ret);
122 126 : return ret;
123 : }
124 :
125 784740 : LoopTree* GetLoopTree() {
126 784740 : if (loop_tree == nullptr) {
127 195642 : if (FLAG_trace_turbo_graph) {
128 0 : OFStream os(stdout);
129 0 : os << AsRPO(graph);
130 : }
131 195642 : Zone zone(main_isolate()->allocator(), ZONE_NAME);
132 195642 : loop_tree = LoopFinder::BuildLoopTree(&graph, &zone);
133 : }
134 784740 : return loop_tree;
135 : }
136 :
137 589398 : void CheckLoop(Node** header, int header_count, Node** body, int body_count) {
138 589398 : LoopTree* tree = GetLoopTree();
139 1768194 : LoopTree::Loop* loop = tree->ContainingLoop(header[0]);
140 589398 : CHECK(loop);
141 :
142 589398 : CHECK(header_count == static_cast<int>(loop->HeaderSize()));
143 1178640 : for (int i = 0; i < header_count; i++) {
144 : // Each header node should be in the loop.
145 2357280 : CHECK_EQ(loop, tree->ContainingLoop(header[i]));
146 1178640 : CheckRangeContains(tree->HeaderNodes(loop), header[i]);
147 : }
148 :
149 589398 : CHECK_EQ(body_count, static_cast<int>(loop->BodySize()));
150 : // TODO(turbofan): O(n^2) set equivalence in this test.
151 5519274 : for (int i = 0; i < body_count; i++) {
152 : // Each body node should be contained in the loop.
153 5519274 : CHECK(tree->Contains(loop, body[i]));
154 5519274 : CheckRangeContains(tree->BodyNodes(loop), body[i]);
155 : }
156 589398 : }
157 :
158 6697914 : void CheckRangeContains(NodeRange range, Node* node) {
159 13395828 : CHECK_NE(range.end(), std::find(range.begin(), range.end(), node));
160 6697914 : }
161 :
162 195342 : void CheckNestedLoops(Node** chain, int chain_count) {
163 195342 : LoopTree* tree = GetLoopTree();
164 780288 : for (int i = 0; i < chain_count; i++) {
165 584946 : Node* header = chain[i];
166 : // Each header should be in a loop.
167 584946 : LoopTree::Loop* loop = tree->ContainingLoop(header);
168 584946 : CHECK(loop);
169 : // Check parentage.
170 : LoopTree::Loop* parent =
171 584946 : i == 0 ? nullptr : tree->ContainingLoop(chain[i - 1]);
172 584946 : CHECK_EQ(parent, loop->parent());
173 1168962 : for (int j = i - 1; j >= 0; j--) {
174 : // This loop should be nested inside all the outer loops.
175 584016 : Node* outer_header = chain[j];
176 : LoopTree::Loop* outer = tree->ContainingLoop(outer_header);
177 584016 : CHECK(tree->Contains(outer, header));
178 584016 : CHECK(!tree->Contains(loop, outer_header));
179 : }
180 : }
181 195342 : }
182 :
183 : Zone* zone() { return main_zone(); }
184 : };
185 :
186 :
187 : struct While {
188 : LoopFinderTester& t;
189 : Node* branch;
190 : Node* if_true;
191 : Node* exit;
192 : Node* loop;
193 :
194 240 : While(LoopFinderTester& R, Node* cond) : t(R) {
195 480 : loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start);
196 480 : branch = t.graph.NewNode(t.common.Branch(), cond, loop);
197 480 : if_true = t.graph.NewNode(t.common.IfTrue(), branch);
198 480 : exit = t.graph.NewNode(t.common.IfFalse(), branch);
199 240 : loop->ReplaceInput(1, if_true);
200 240 : }
201 :
202 66 : void chain(Node* control) { loop->ReplaceInput(0, control); }
203 30 : void nest(While& that) {
204 30 : that.loop->ReplaceInput(1, exit);
205 30 : this->loop->ReplaceInput(0, that.if_true);
206 30 : }
207 : };
208 :
209 :
210 : struct Counter {
211 : Node* base;
212 : Node* inc;
213 : Node* phi;
214 : Node* add;
215 :
216 108 : Counter(While& w, int32_t b, int32_t k)
217 108 : : base(w.t.jsgraph.Int32Constant(b)), inc(w.t.jsgraph.Int32Constant(k)) {
218 108 : Build(w);
219 108 : }
220 :
221 48 : Counter(While& w, Node* b, Node* k) : base(b), inc(k) { Build(w); }
222 :
223 156 : void Build(While& w) {
224 312 : phi = w.t.graph.NewNode(w.t.op(2, false), base, base, w.loop);
225 312 : add = w.t.graph.NewNode(&kIntAdd, phi, inc);
226 156 : phi->ReplaceInput(1, add);
227 156 : }
228 : };
229 :
230 :
231 : struct StoreLoop {
232 : Node* base;
233 : Node* val;
234 : Node* phi;
235 : Node* store;
236 :
237 6 : explicit StoreLoop(While& w)
238 6 : : base(w.t.graph.start()), val(w.t.jsgraph.Int32Constant(13)) {
239 6 : Build(w);
240 6 : }
241 :
242 : StoreLoop(While& w, Node* b, Node* v) : base(b), val(v) { Build(w); }
243 :
244 6 : void Build(While& w) {
245 12 : phi = w.t.graph.NewNode(w.t.op(2, true), base, base, w.loop);
246 12 : store = w.t.graph.NewNode(&kStore, val, phi, w.loop);
247 6 : phi->ReplaceInput(1, store);
248 6 : }
249 : };
250 :
251 :
252 23724 : TEST(LaLoop1) {
253 : // One loop.
254 6 : LoopFinderTester t;
255 6 : While w(t, t.p0);
256 6 : t.Return(t.p0, t.start, w.exit);
257 :
258 6 : Node* chain[] = {w.loop};
259 6 : t.CheckNestedLoops(chain, 1);
260 :
261 6 : Node* header[] = {w.loop};
262 6 : Node* body[] = {w.branch, w.if_true};
263 6 : t.CheckLoop(header, 1, body, 2);
264 6 : }
265 :
266 :
267 23724 : TEST(LaLoop1phi) {
268 : // One loop with a simple phi.
269 6 : LoopFinderTester t;
270 6 : While w(t, t.p0);
271 : Node* phi = t.graph.NewNode(t.common.Phi(MachineRepresentation::kTagged, 2),
272 6 : t.zero, t.one, w.loop);
273 6 : t.Return(phi, t.start, w.exit);
274 :
275 6 : Node* chain[] = {w.loop};
276 6 : t.CheckNestedLoops(chain, 1);
277 :
278 6 : Node* header[] = {w.loop, phi};
279 6 : Node* body[] = {w.branch, w.if_true};
280 6 : t.CheckLoop(header, 2, body, 2);
281 6 : }
282 :
283 :
284 23724 : TEST(LaLoop1c) {
285 : // One loop with a counter.
286 6 : LoopFinderTester t;
287 6 : While w(t, t.p0);
288 6 : Counter c(w, 0, 1);
289 6 : t.Return(c.phi, t.start, w.exit);
290 :
291 6 : Node* chain[] = {w.loop};
292 6 : t.CheckNestedLoops(chain, 1);
293 :
294 6 : Node* header[] = {w.loop, c.phi};
295 6 : Node* body[] = {w.branch, w.if_true, c.add};
296 6 : t.CheckLoop(header, 2, body, 3);
297 6 : }
298 :
299 :
300 23724 : TEST(LaLoop1e) {
301 : // One loop with an effect phi.
302 6 : LoopFinderTester t;
303 6 : While w(t, t.p0);
304 6 : StoreLoop c(w);
305 6 : t.Return(t.p0, c.phi, w.exit);
306 :
307 6 : Node* chain[] = {w.loop};
308 6 : t.CheckNestedLoops(chain, 1);
309 :
310 6 : Node* header[] = {w.loop, c.phi};
311 6 : Node* body[] = {w.branch, w.if_true, c.store};
312 6 : t.CheckLoop(header, 2, body, 3);
313 6 : }
314 :
315 :
316 23724 : TEST(LaLoop1d) {
317 : // One loop with two counters.
318 6 : LoopFinderTester t;
319 6 : While w(t, t.p0);
320 6 : Counter c1(w, 0, 1);
321 6 : Counter c2(w, 1, 1);
322 12 : t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w.exit);
323 :
324 6 : Node* chain[] = {w.loop};
325 6 : t.CheckNestedLoops(chain, 1);
326 :
327 6 : Node* header[] = {w.loop, c1.phi, c2.phi};
328 6 : Node* body[] = {w.branch, w.if_true, c1.add, c2.add};
329 6 : t.CheckLoop(header, 3, body, 4);
330 6 : }
331 :
332 :
333 23724 : TEST(LaLoop2) {
334 : // One loop following another.
335 6 : LoopFinderTester t;
336 6 : While w1(t, t.p0);
337 6 : While w2(t, t.p0);
338 6 : w2.chain(w1.exit);
339 6 : t.Return(t.p0, t.start, w2.exit);
340 :
341 : {
342 6 : Node* chain[] = {w1.loop};
343 6 : t.CheckNestedLoops(chain, 1);
344 :
345 6 : Node* header[] = {w1.loop};
346 6 : Node* body[] = {w1.branch, w1.if_true};
347 6 : t.CheckLoop(header, 1, body, 2);
348 : }
349 :
350 : {
351 6 : Node* chain[] = {w2.loop};
352 6 : t.CheckNestedLoops(chain, 1);
353 :
354 6 : Node* header[] = {w2.loop};
355 6 : Node* body[] = {w2.branch, w2.if_true};
356 6 : t.CheckLoop(header, 1, body, 2);
357 : }
358 6 : }
359 :
360 :
361 23724 : TEST(LaLoop2c) {
362 : // One loop following another, each with counters.
363 6 : LoopFinderTester t;
364 6 : While w1(t, t.p0);
365 6 : While w2(t, t.p0);
366 6 : Counter c1(w1, 0, 1);
367 6 : Counter c2(w2, 0, 1);
368 6 : w2.chain(w1.exit);
369 12 : t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w2.exit);
370 :
371 : {
372 6 : Node* chain[] = {w1.loop};
373 6 : t.CheckNestedLoops(chain, 1);
374 :
375 6 : Node* header[] = {w1.loop, c1.phi};
376 6 : Node* body[] = {w1.branch, w1.if_true, c1.add};
377 6 : t.CheckLoop(header, 2, body, 3);
378 : }
379 :
380 : {
381 6 : Node* chain[] = {w2.loop};
382 6 : t.CheckNestedLoops(chain, 1);
383 :
384 6 : Node* header[] = {w2.loop, c2.phi};
385 6 : Node* body[] = {w2.branch, w2.if_true, c2.add};
386 6 : t.CheckLoop(header, 2, body, 3);
387 : }
388 6 : }
389 :
390 :
391 23724 : TEST(LaLoop2cc) {
392 : // One loop following another; second loop uses phi from first.
393 54 : for (int i = 0; i < 8; i++) {
394 48 : LoopFinderTester t;
395 48 : While w1(t, t.p0);
396 48 : While w2(t, t.p0);
397 48 : Counter c1(w1, 0, 1);
398 :
399 : // various usage scenarios for the second loop.
400 48 : Counter c2(w2, i & 1 ? t.p0 : c1.phi, i & 2 ? t.p0 : c1.phi);
401 48 : if (i & 3) w2.branch->ReplaceInput(0, c1.phi);
402 :
403 48 : w2.chain(w1.exit);
404 96 : t.Return(t.graph.NewNode(&kIntAdd, c1.phi, c2.phi), t.start, w2.exit);
405 :
406 : {
407 48 : Node* chain[] = {w1.loop};
408 48 : t.CheckNestedLoops(chain, 1);
409 :
410 48 : Node* header[] = {w1.loop, c1.phi};
411 48 : Node* body[] = {w1.branch, w1.if_true, c1.add};
412 48 : t.CheckLoop(header, 2, body, 3);
413 : }
414 :
415 : {
416 48 : Node* chain[] = {w2.loop};
417 48 : t.CheckNestedLoops(chain, 1);
418 :
419 48 : Node* header[] = {w2.loop, c2.phi};
420 48 : Node* body[] = {w2.branch, w2.if_true, c2.add};
421 48 : t.CheckLoop(header, 2, body, 3);
422 : }
423 : }
424 6 : }
425 :
426 :
427 23724 : TEST(LaNestedLoop1) {
428 : // One loop nested in another.
429 6 : LoopFinderTester t;
430 6 : While w1(t, t.p0);
431 6 : While w2(t, t.p0);
432 6 : w2.nest(w1);
433 6 : t.Return(t.p0, t.start, w1.exit);
434 :
435 6 : Node* chain[] = {w1.loop, w2.loop};
436 6 : t.CheckNestedLoops(chain, 2);
437 :
438 6 : Node* h1[] = {w1.loop};
439 6 : Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true, w2.exit};
440 6 : t.CheckLoop(h1, 1, b1, 6);
441 :
442 6 : Node* h2[] = {w2.loop};
443 6 : Node* b2[] = {w2.branch, w2.if_true};
444 6 : t.CheckLoop(h2, 1, b2, 2);
445 6 : }
446 :
447 :
448 23724 : TEST(LaNestedLoop1c) {
449 : // One loop nested in another, each with a counter.
450 6 : LoopFinderTester t;
451 6 : While w1(t, t.p0);
452 6 : While w2(t, t.p0);
453 6 : Counter c1(w1, 0, 1);
454 6 : Counter c2(w2, 0, 1);
455 6 : w2.branch->ReplaceInput(0, c2.phi);
456 6 : w2.nest(w1);
457 6 : t.Return(c1.phi, t.start, w1.exit);
458 :
459 6 : Node* chain[] = {w1.loop, w2.loop};
460 6 : t.CheckNestedLoops(chain, 2);
461 :
462 6 : Node* h1[] = {w1.loop, c1.phi};
463 : Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true,
464 6 : w2.exit, c2.phi, c1.add, c2.add};
465 6 : t.CheckLoop(h1, 2, b1, 9);
466 :
467 6 : Node* h2[] = {w2.loop, c2.phi};
468 6 : Node* b2[] = {w2.branch, w2.if_true, c2.add};
469 6 : t.CheckLoop(h2, 2, b2, 3);
470 6 : }
471 :
472 :
473 23724 : TEST(LaNestedLoop1x) {
474 : // One loop nested in another.
475 6 : LoopFinderTester t;
476 6 : While w1(t, t.p0);
477 6 : While w2(t, t.p0);
478 6 : w2.nest(w1);
479 :
480 6 : const Operator* op = t.common.Phi(MachineRepresentation::kWord32, 2);
481 6 : Node* p1a = t.graph.NewNode(op, t.p0, t.p0, w1.loop);
482 6 : Node* p1b = t.graph.NewNode(op, t.p0, t.p0, w1.loop);
483 6 : Node* p2a = t.graph.NewNode(op, p1a, t.p0, w2.loop);
484 6 : Node* p2b = t.graph.NewNode(op, p1b, t.p0, w2.loop);
485 :
486 6 : p1a->ReplaceInput(1, p2b);
487 6 : p1b->ReplaceInput(1, p2a);
488 :
489 6 : p2a->ReplaceInput(1, p2b);
490 6 : p2b->ReplaceInput(1, p2a);
491 :
492 6 : t.Return(t.p0, t.start, w1.exit);
493 :
494 6 : Node* chain[] = {w1.loop, w2.loop};
495 6 : t.CheckNestedLoops(chain, 2);
496 :
497 6 : Node* h1[] = {w1.loop, p1a, p1b};
498 : Node* b1[] = {w1.branch, w1.if_true, w2.loop, p2a,
499 6 : p2b, w2.branch, w2.if_true, w2.exit};
500 6 : t.CheckLoop(h1, 3, b1, 8);
501 :
502 6 : Node* h2[] = {w2.loop, p2a, p2b};
503 6 : Node* b2[] = {w2.branch, w2.if_true};
504 6 : t.CheckLoop(h2, 3, b2, 2);
505 6 : }
506 :
507 :
508 23724 : TEST(LaNestedLoop2) {
509 : // Two loops nested in an outer loop.
510 6 : LoopFinderTester t;
511 6 : While w1(t, t.p0);
512 6 : While w2(t, t.p0);
513 6 : While w3(t, t.p0);
514 6 : w2.nest(w1);
515 6 : w3.nest(w1);
516 6 : w3.chain(w2.exit);
517 6 : t.Return(t.p0, t.start, w1.exit);
518 :
519 6 : Node* chain1[] = {w1.loop, w2.loop};
520 6 : t.CheckNestedLoops(chain1, 2);
521 :
522 6 : Node* chain2[] = {w1.loop, w3.loop};
523 6 : t.CheckNestedLoops(chain2, 2);
524 :
525 6 : Node* h1[] = {w1.loop};
526 : Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true,
527 6 : w2.exit, w3.loop, w3.branch, w3.if_true, w3.exit};
528 6 : t.CheckLoop(h1, 1, b1, 10);
529 :
530 6 : Node* h2[] = {w2.loop};
531 6 : Node* b2[] = {w2.branch, w2.if_true};
532 6 : t.CheckLoop(h2, 1, b2, 2);
533 :
534 6 : Node* h3[] = {w3.loop};
535 6 : Node* b3[] = {w3.branch, w3.if_true};
536 6 : t.CheckLoop(h3, 1, b3, 2);
537 6 : }
538 :
539 :
540 23724 : TEST(LaNestedLoop3) {
541 : // Three nested loops.
542 6 : LoopFinderTester t;
543 6 : While w1(t, t.p0);
544 6 : While w2(t, t.p0);
545 6 : While w3(t, t.p0);
546 6 : w2.loop->ReplaceInput(0, w1.if_true);
547 6 : w3.loop->ReplaceInput(0, w2.if_true);
548 6 : w2.loop->ReplaceInput(1, w3.exit);
549 6 : w1.loop->ReplaceInput(1, w2.exit);
550 6 : t.Return(t.p0, t.start, w1.exit);
551 :
552 6 : Node* chain[] = {w1.loop, w2.loop, w3.loop};
553 6 : t.CheckNestedLoops(chain, 3);
554 :
555 6 : Node* h1[] = {w1.loop};
556 : Node* b1[] = {w1.branch, w1.if_true, w2.loop, w2.branch, w2.if_true,
557 6 : w2.exit, w3.loop, w3.branch, w3.if_true, w3.exit};
558 6 : t.CheckLoop(h1, 1, b1, 10);
559 :
560 6 : Node* h2[] = {w2.loop};
561 6 : Node* b2[] = {w2.branch, w2.if_true, w3.loop, w3.branch, w3.if_true, w3.exit};
562 6 : t.CheckLoop(h2, 1, b2, 6);
563 :
564 6 : Node* h3[] = {w3.loop};
565 6 : Node* b3[] = {w3.branch, w3.if_true};
566 6 : t.CheckLoop(h3, 1, b3, 2);
567 6 : }
568 :
569 :
570 23724 : TEST(LaNestedLoop3c) {
571 : // Three nested loops with counters.
572 6 : LoopFinderTester t;
573 6 : While w1(t, t.p0);
574 6 : Counter c1(w1, 0, 1);
575 6 : While w2(t, t.p0);
576 6 : Counter c2(w2, 0, 1);
577 6 : While w3(t, t.p0);
578 6 : Counter c3(w3, 0, 1);
579 6 : w2.loop->ReplaceInput(0, w1.if_true);
580 6 : w3.loop->ReplaceInput(0, w2.if_true);
581 6 : w2.loop->ReplaceInput(1, w3.exit);
582 6 : w1.loop->ReplaceInput(1, w2.exit);
583 6 : w1.branch->ReplaceInput(0, c1.phi);
584 6 : w2.branch->ReplaceInput(0, c2.phi);
585 6 : w3.branch->ReplaceInput(0, c3.phi);
586 6 : t.Return(c1.phi, t.start, w1.exit);
587 :
588 6 : Node* chain[] = {w1.loop, w2.loop, w3.loop};
589 6 : t.CheckNestedLoops(chain, 3);
590 :
591 6 : Node* h1[] = {w1.loop, c1.phi};
592 : Node* b1[] = {w1.branch, w1.if_true, c1.add, c2.add, c2.add,
593 : c2.phi, c3.phi, w2.loop, w2.branch, w2.if_true,
594 6 : w2.exit, w3.loop, w3.branch, w3.if_true, w3.exit};
595 6 : t.CheckLoop(h1, 2, b1, 15);
596 :
597 6 : Node* h2[] = {w2.loop, c2.phi};
598 : Node* b2[] = {w2.branch, w2.if_true, c2.add, c3.add, c3.phi,
599 6 : w3.loop, w3.branch, w3.if_true, w3.exit};
600 6 : t.CheckLoop(h2, 2, b2, 9);
601 :
602 6 : Node* h3[] = {w3.loop, c3.phi};
603 6 : Node* b3[] = {w3.branch, w3.if_true, c3.add};
604 6 : t.CheckLoop(h3, 2, b3, 3);
605 6 : }
606 :
607 :
608 23724 : TEST(LaMultipleExit1) {
609 : const int kMaxExits = 10;
610 : Node* merge[1 + kMaxExits];
611 : Node* body[2 * kMaxExits];
612 :
613 : // A single loop with {i} exits.
614 60 : for (int i = 1; i < kMaxExits; i++) {
615 54 : LoopFinderTester t;
616 54 : Node* cond = t.p0;
617 :
618 : int merge_count = 0;
619 : int body_count = 0;
620 54 : Node* loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start);
621 : Node* last = loop;
622 :
623 324 : for (int e = 0; e < i; e++) {
624 270 : Node* branch = t.graph.NewNode(t.common.Branch(), cond, last);
625 270 : Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch);
626 270 : Node* exit = t.graph.NewNode(t.common.IfFalse(), branch);
627 : last = if_true;
628 :
629 270 : body[body_count++] = branch;
630 270 : body[body_count++] = if_true;
631 270 : merge[merge_count++] = exit;
632 : }
633 :
634 54 : loop->ReplaceInput(1, last); // form loop backedge.
635 54 : Node* end = t.graph.NewNode(t.common.Merge(i), i, merge); // form exit.
636 : t.graph.SetEnd(end);
637 :
638 54 : Node* h[] = {loop};
639 54 : t.CheckLoop(h, 1, body, body_count);
640 : }
641 6 : }
642 :
643 :
644 23724 : TEST(LaMultipleBackedge1) {
645 : const int kMaxBackedges = 10;
646 : Node* loop_inputs[1 + kMaxBackedges];
647 : Node* body[3 * kMaxBackedges];
648 :
649 : // A single loop with {i} backedges.
650 66 : for (int i = 1; i < kMaxBackedges; i++) {
651 54 : LoopFinderTester t;
652 :
653 54 : for (int j = 0; j <= i; j++) loop_inputs[j] = t.start;
654 54 : Node* loop = t.graph.NewNode(t.common.Loop(1 + i), 1 + i, loop_inputs);
655 :
656 54 : Node* cond = t.p0;
657 : int body_count = 0;
658 : Node* exit = loop;
659 :
660 378 : for (int b = 0; b < i; b++) {
661 270 : Node* branch = t.graph.NewNode(t.common.Branch(), cond, exit);
662 270 : Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch);
663 270 : Node* if_false = t.graph.NewNode(t.common.IfFalse(), branch);
664 : exit = if_false;
665 :
666 270 : body[body_count++] = branch;
667 270 : body[body_count++] = if_true;
668 270 : if (b != (i - 1)) body[body_count++] = if_false;
669 :
670 270 : loop->ReplaceInput(1 + b, if_true);
671 : }
672 :
673 : t.graph.SetEnd(exit);
674 :
675 54 : Node* h[] = {loop};
676 54 : t.CheckLoop(h, 1, body, body_count);
677 : }
678 6 : }
679 :
680 :
681 23724 : TEST(LaEdgeMatrix1) {
682 : // Test various kinds of extra edges added to a simple loop.
683 24 : for (int i = 0; i < 3; i++) {
684 54 : for (int j = 0; j < 3; j++) {
685 162 : for (int k = 0; k < 3; k++) {
686 162 : LoopFinderTester t;
687 :
688 162 : Node* p1 = t.jsgraph.Int32Constant(11);
689 162 : Node* p2 = t.jsgraph.Int32Constant(22);
690 162 : Node* p3 = t.jsgraph.Int32Constant(33);
691 :
692 162 : Node* loop = t.graph.NewNode(t.common.Loop(2), t.start, t.start);
693 : Node* phi = t.graph.NewNode(
694 162 : t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p1, loop);
695 : Node* cond = t.graph.NewNode(&kIntAdd, phi, p2);
696 162 : Node* branch = t.graph.NewNode(t.common.Branch(), cond, loop);
697 162 : Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch);
698 162 : Node* exit = t.graph.NewNode(t.common.IfFalse(), branch);
699 162 : loop->ReplaceInput(1, if_true);
700 162 : Node* zero = t.graph.NewNode(t.common.Int32Constant(0));
701 162 : Node* ret = t.graph.NewNode(t.common.Return(), zero, p3, t.start, exit);
702 : t.graph.SetEnd(ret);
703 :
704 162 : Node* choices[] = {p1, phi, cond};
705 162 : p1->ReplaceUses(choices[i]);
706 162 : p2->ReplaceUses(choices[j]);
707 162 : p3->ReplaceUses(choices[k]);
708 :
709 162 : Node* header[] = {loop, phi};
710 162 : Node* body[] = {cond, branch, if_true};
711 162 : t.CheckLoop(header, 2, body, 3);
712 : }
713 : }
714 : }
715 6 : }
716 :
717 :
718 30 : void RunEdgeMatrix2(int i) {
719 30 : CHECK(i >= 0 && i < 5);
720 150 : for (int j = 0; j < 5; j++) {
721 750 : for (int k = 0; k < 5; k++) {
722 750 : LoopFinderTester t;
723 :
724 750 : Node* p1 = t.jsgraph.Int32Constant(11);
725 750 : Node* p2 = t.jsgraph.Int32Constant(22);
726 750 : Node* p3 = t.jsgraph.Int32Constant(33);
727 :
728 : // outer loop.
729 750 : Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start);
730 : Node* phi1 = t.graph.NewNode(
731 750 : t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p1, loop1);
732 750 : Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, t.one);
733 750 : Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1);
734 750 : Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1);
735 750 : Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1);
736 :
737 : // inner loop.
738 750 : Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start);
739 : Node* phi2 = t.graph.NewNode(
740 750 : t.common.Phi(MachineRepresentation::kWord32, 2), t.one, p2, loop2);
741 : Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p3);
742 750 : Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2);
743 750 : Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2);
744 750 : Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2);
745 750 : loop2->ReplaceInput(1, if_true2);
746 750 : loop1->ReplaceInput(1, exit2);
747 :
748 750 : Node* zero = t.graph.NewNode(t.common.Int32Constant(0));
749 : Node* ret =
750 750 : t.graph.NewNode(t.common.Return(), zero, phi1, t.start, exit1);
751 : t.graph.SetEnd(ret);
752 :
753 750 : Node* choices[] = {p1, phi1, cond1, phi2, cond2};
754 750 : p1->ReplaceUses(choices[i]);
755 750 : p2->ReplaceUses(choices[j]);
756 750 : p3->ReplaceUses(choices[k]);
757 :
758 750 : Node* header1[] = {loop1, phi1};
759 : Node* body1[] = {cond1, branch1, if_true1, exit2, loop2,
760 750 : phi2, cond2, branch2, if_true2};
761 750 : t.CheckLoop(header1, 2, body1, 9);
762 :
763 750 : Node* header2[] = {loop2, phi2};
764 750 : Node* body2[] = {cond2, branch2, if_true2};
765 750 : t.CheckLoop(header2, 2, body2, 3);
766 :
767 750 : Node* chain[] = {loop1, loop2};
768 750 : t.CheckNestedLoops(chain, 2);
769 : }
770 : }
771 30 : }
772 :
773 :
774 23724 : TEST(LaEdgeMatrix2_0) { RunEdgeMatrix2(0); }
775 :
776 :
777 23724 : TEST(LaEdgeMatrix2_1) { RunEdgeMatrix2(1); }
778 :
779 :
780 23724 : TEST(LaEdgeMatrix2_2) { RunEdgeMatrix2(2); }
781 :
782 :
783 23724 : TEST(LaEdgeMatrix2_3) { RunEdgeMatrix2(3); }
784 :
785 :
786 23724 : TEST(LaEdgeMatrix2_4) { RunEdgeMatrix2(4); }
787 :
788 :
789 : // Generates a triply-nested loop with extra edges between the phis and
790 : // conditions according to the edge choice parameters.
791 194400 : void RunEdgeMatrix3(int c1a, int c1b, int c1c, // line break
792 : int c2a, int c2b, int c2c, // line break
793 : int c3a, int c3b, int c3c) { // line break
794 194400 : LoopFinderTester t;
795 :
796 194400 : Node* p1a = t.jsgraph.Int32Constant(11);
797 194400 : Node* p1b = t.jsgraph.Int32Constant(22);
798 194400 : Node* p1c = t.jsgraph.Int32Constant(33);
799 194400 : Node* p2a = t.jsgraph.Int32Constant(44);
800 194400 : Node* p2b = t.jsgraph.Int32Constant(55);
801 194400 : Node* p2c = t.jsgraph.Int32Constant(66);
802 194400 : Node* p3a = t.jsgraph.Int32Constant(77);
803 194400 : Node* p3b = t.jsgraph.Int32Constant(88);
804 194400 : Node* p3c = t.jsgraph.Int32Constant(99);
805 :
806 : // L1 depth = 0
807 194400 : Node* loop1 = t.graph.NewNode(t.common.Loop(2), t.start, t.start);
808 : Node* phi1 = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2),
809 194400 : p1a, p1c, loop1);
810 : Node* cond1 = t.graph.NewNode(&kIntAdd, phi1, p1b);
811 194400 : Node* branch1 = t.graph.NewNode(t.common.Branch(), cond1, loop1);
812 194400 : Node* if_true1 = t.graph.NewNode(t.common.IfTrue(), branch1);
813 194400 : Node* exit1 = t.graph.NewNode(t.common.IfFalse(), branch1);
814 :
815 : // L2 depth = 1
816 194400 : Node* loop2 = t.graph.NewNode(t.common.Loop(2), if_true1, t.start);
817 : Node* phi2 = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2),
818 194400 : p2a, p2c, loop2);
819 : Node* cond2 = t.graph.NewNode(&kIntAdd, phi2, p2b);
820 194400 : Node* branch2 = t.graph.NewNode(t.common.Branch(), cond2, loop2);
821 194400 : Node* if_true2 = t.graph.NewNode(t.common.IfTrue(), branch2);
822 194400 : Node* exit2 = t.graph.NewNode(t.common.IfFalse(), branch2);
823 :
824 : // L3 depth = 2
825 194400 : Node* loop3 = t.graph.NewNode(t.common.Loop(2), if_true2, t.start);
826 : Node* phi3 = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2),
827 194400 : p3a, p3c, loop3);
828 : Node* cond3 = t.graph.NewNode(&kIntAdd, phi3, p3b);
829 194400 : Node* branch3 = t.graph.NewNode(t.common.Branch(), cond3, loop3);
830 194400 : Node* if_true3 = t.graph.NewNode(t.common.IfTrue(), branch3);
831 194400 : Node* exit3 = t.graph.NewNode(t.common.IfFalse(), branch3);
832 :
833 194400 : loop3->ReplaceInput(1, if_true3);
834 194400 : loop2->ReplaceInput(1, exit3);
835 194400 : loop1->ReplaceInput(1, exit2);
836 :
837 194400 : Node* zero = t.graph.NewNode(t.common.Int32Constant(0));
838 194400 : Node* ret = t.graph.NewNode(t.common.Return(), zero, phi1, t.start, exit1);
839 : t.graph.SetEnd(ret);
840 :
841 : // Mutate the graph according to the edge choices.
842 :
843 194400 : Node* o1[] = {t.one};
844 194400 : Node* o2[] = {t.one, phi1, cond1};
845 194400 : Node* o3[] = {t.one, phi1, cond1, phi2, cond2};
846 :
847 194400 : p1a->ReplaceUses(o1[c1a]);
848 194400 : p1b->ReplaceUses(o1[c1b]);
849 :
850 194400 : p2a->ReplaceUses(o2[c2a]);
851 194400 : p2b->ReplaceUses(o2[c2b]);
852 :
853 194400 : p3a->ReplaceUses(o3[c3a]);
854 194400 : p3b->ReplaceUses(o3[c3b]);
855 :
856 194400 : Node* l2[] = {phi1, cond1, phi2, cond2};
857 194400 : Node* l3[] = {phi1, cond1, phi2, cond2, phi3, cond3};
858 :
859 194400 : p1c->ReplaceUses(l2[c1c]);
860 194400 : p2c->ReplaceUses(l3[c2c]);
861 194400 : p3c->ReplaceUses(l3[c3c]);
862 :
863 : // Run the tests and verify loop structure.
864 :
865 194400 : Node* chain[] = {loop1, loop2, loop3};
866 194400 : t.CheckNestedLoops(chain, 3);
867 :
868 194400 : Node* header1[] = {loop1, phi1};
869 : Node* body1[] = {cond1, branch1, if_true1, exit2, loop2,
870 : phi2, cond2, branch2, if_true2, exit3,
871 194400 : loop3, phi3, cond3, branch3, if_true3};
872 194400 : t.CheckLoop(header1, 2, body1, 15);
873 :
874 194400 : Node* header2[] = {loop2, phi2};
875 : Node* body2[] = {cond2, branch2, if_true2, exit3, loop3,
876 194400 : phi3, cond3, branch3, if_true3};
877 194400 : t.CheckLoop(header2, 2, body2, 9);
878 :
879 194400 : Node* header3[] = {loop3, phi3};
880 194400 : Node* body3[] = {cond3, branch3, if_true3};
881 194400 : t.CheckLoop(header3, 2, body3, 3);
882 194400 : }
883 :
884 :
885 : // Runs all combinations with a fixed {i}.
886 36 : static void RunEdgeMatrix3_i(int i) {
887 72 : for (int a = 0; a < 1; a++) {
888 36 : for (int b = 0; b < 1; b++) {
889 144 : for (int c = 0; c < 4; c++) {
890 432 : for (int d = 0; d < 3; d++) {
891 1296 : for (int e = 0; e < 3; e++) {
892 7776 : for (int f = 0; f < 6; f++) {
893 38880 : for (int g = 0; g < 5; g++) {
894 194400 : for (int h = 0; h < 5; h++) {
895 194400 : RunEdgeMatrix3(a, b, c, d, e, f, g, h, i);
896 : }
897 : }
898 : }
899 : }
900 : }
901 : }
902 : }
903 : }
904 36 : }
905 :
906 :
907 : // Test all possible legal triply-nested loops with conditions and phis.
908 23724 : TEST(LaEdgeMatrix3_0) { RunEdgeMatrix3_i(0); }
909 :
910 :
911 23724 : TEST(LaEdgeMatrix3_1) { RunEdgeMatrix3_i(1); }
912 :
913 :
914 23724 : TEST(LaEdgeMatrix3_2) { RunEdgeMatrix3_i(2); }
915 :
916 :
917 23724 : TEST(LaEdgeMatrix3_3) { RunEdgeMatrix3_i(3); }
918 :
919 :
920 23724 : TEST(LaEdgeMatrix3_4) { RunEdgeMatrix3_i(4); }
921 :
922 :
923 23724 : TEST(LaEdgeMatrix3_5) { RunEdgeMatrix3_i(5); }
924 :
925 :
926 48 : static void RunManyChainedLoops_i(int count) {
927 48 : LoopFinderTester t;
928 48 : Node** nodes = t.zone()->NewArray<Node*>(count * 4);
929 48 : Node* k11 = t.jsgraph.Int32Constant(11);
930 48 : Node* k12 = t.jsgraph.Int32Constant(12);
931 48 : Node* last = t.start;
932 :
933 : // Build loops.
934 2142 : for (int i = 0; i < count; i++) {
935 2094 : Node* loop = t.graph.NewNode(t.common.Loop(2), last, t.start);
936 : Node* phi = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2),
937 2094 : k11, k12, loop);
938 2094 : Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop);
939 2094 : Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch);
940 2094 : Node* exit = t.graph.NewNode(t.common.IfFalse(), branch);
941 2094 : loop->ReplaceInput(1, if_true);
942 :
943 2094 : nodes[i * 4 + 0] = loop;
944 2094 : nodes[i * 4 + 1] = phi;
945 2094 : nodes[i * 4 + 2] = branch;
946 2094 : nodes[i * 4 + 3] = if_true;
947 :
948 : last = exit;
949 : }
950 :
951 48 : Node* zero = t.graph.NewNode(t.common.Int32Constant(0));
952 48 : Node* ret = t.graph.NewNode(t.common.Return(), zero, t.p0, t.start, last);
953 : t.graph.SetEnd(ret);
954 :
955 : // Verify loops.
956 2142 : for (int i = 0; i < count; i++) {
957 2094 : t.CheckLoop(nodes + i * 4, 2, nodes + i * 4 + 2, 2);
958 : }
959 48 : }
960 :
961 :
962 48 : static void RunManyNestedLoops_i(int count) {
963 48 : LoopFinderTester t;
964 48 : Node** nodes = t.zone()->NewArray<Node*>(count * 5);
965 48 : Node* k11 = t.jsgraph.Int32Constant(11);
966 48 : Node* k12 = t.jsgraph.Int32Constant(12);
967 : Node* outer = nullptr;
968 48 : Node* entry = t.start;
969 :
970 : // Build loops.
971 48 : Node* zero = t.graph.NewNode(t.common.Int32Constant(0));
972 2142 : for (int i = 0; i < count; i++) {
973 2094 : Node* loop = t.graph.NewNode(t.common.Loop(2), entry, t.start);
974 : Node* phi = t.graph.NewNode(t.common.Phi(MachineRepresentation::kWord32, 2),
975 2094 : k11, k12, loop);
976 2094 : Node* branch = t.graph.NewNode(t.common.Branch(), phi, loop);
977 2094 : Node* if_true = t.graph.NewNode(t.common.IfTrue(), branch);
978 2094 : Node* exit = t.graph.NewNode(t.common.IfFalse(), branch);
979 :
980 2094 : nodes[i * 5 + 0] = exit; // outside
981 2094 : nodes[i * 5 + 1] = loop; // header
982 2094 : nodes[i * 5 + 2] = phi; // header
983 2094 : nodes[i * 5 + 3] = branch; // body
984 2094 : nodes[i * 5 + 4] = if_true; // body
985 :
986 2094 : if (outer != nullptr) {
987 : // inner loop.
988 2046 : outer->ReplaceInput(1, exit);
989 : } else {
990 : // outer loop.
991 48 : Node* ret = t.graph.NewNode(t.common.Return(), zero, t.p0, t.start, exit);
992 : t.graph.SetEnd(ret);
993 : }
994 : outer = loop;
995 : entry = if_true;
996 : }
997 48 : outer->ReplaceInput(1, entry); // innermost loop.
998 :
999 : // Verify loops.
1000 2142 : for (int i = 0; i < count; i++) {
1001 2094 : int k = i * 5;
1002 2094 : t.CheckLoop(nodes + k + 1, 2, nodes + k + 3, count * 5 - k - 3);
1003 : }
1004 48 : }
1005 :
1006 :
1007 23724 : TEST(LaManyChained_30) { RunManyChainedLoops_i(30); }
1008 23724 : TEST(LaManyChained_31) { RunManyChainedLoops_i(31); }
1009 23724 : TEST(LaManyChained_32) { RunManyChainedLoops_i(32); }
1010 23724 : TEST(LaManyChained_33) { RunManyChainedLoops_i(33); }
1011 23724 : TEST(LaManyChained_34) { RunManyChainedLoops_i(34); }
1012 23724 : TEST(LaManyChained_62) { RunManyChainedLoops_i(62); }
1013 23724 : TEST(LaManyChained_63) { RunManyChainedLoops_i(63); }
1014 23724 : TEST(LaManyChained_64) { RunManyChainedLoops_i(64); }
1015 :
1016 23724 : TEST(LaManyNested_30) { RunManyNestedLoops_i(30); }
1017 23724 : TEST(LaManyNested_31) { RunManyNestedLoops_i(31); }
1018 23724 : TEST(LaManyNested_32) { RunManyNestedLoops_i(32); }
1019 23724 : TEST(LaManyNested_33) { RunManyNestedLoops_i(33); }
1020 23724 : TEST(LaManyNested_34) { RunManyNestedLoops_i(34); }
1021 23724 : TEST(LaManyNested_62) { RunManyNestedLoops_i(62); }
1022 23724 : TEST(LaManyNested_63) { RunManyNestedLoops_i(63); }
1023 23724 : TEST(LaManyNested_64) { RunManyNestedLoops_i(64); }
1024 :
1025 :
1026 23730 : TEST(LaPhiTangle) { LoopFinderTester t; }
1027 :
1028 : } // namespace compiler
1029 : } // namespace internal
1030 71154 : } // namespace v8
|
