Home | History | Annotate | Download | only in compiler
      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