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