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