Home | History | Annotate | Download | only in compiler 
      1 // Copyright 2015 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "src/compiler/schedule.h"
      6 #include "src/compiler/access-builder.h"
      7 #include "src/compiler/common-operator.h"
      8 #include "src/compiler/graph-visualizer.h"
      9 #include "src/compiler/graph.h"
     10 #include "src/compiler/js-operator.h"
     11 #include "src/compiler/node.h"
     12 #include "src/compiler/opcodes.h"
     13 #include "src/compiler/operator.h"
     14 #include "src/compiler/scheduler.h"
     15 #include "src/compiler/simplified-operator.h"
     16 #include "src/compiler/source-position.h"
     17 #include "src/compiler/verifier.h"
     18 #include "test/unittests/compiler/compiler-test-utils.h"
     19 #include "test/unittests/test-utils.h"
     20 #include "testing/gmock/include/gmock/gmock.h"
     21 
     22 using testing::AnyOf;
     23 
     24 namespace v8 {
     25 namespace internal {
     26 namespace compiler {
     27 
     28 class SchedulerTest : public TestWithIsolateAndZone {
     29  public:
     30   SchedulerTest()
     31       : graph_(zone()), common_(zone()), simplified_(zone()), js_(zone()) {}
     32 
     33   Schedule* ComputeAndVerifySchedule(size_t expected) {
     34     if (FLAG_trace_turbo) {
     35       OFStream os(stdout);
     36       SourcePositionTable table(graph());
     37       os << AsJSON(*graph(), &table);
     38     }
     39 
     40     Schedule* schedule =
     41         Scheduler::ComputeSchedule(zone(), graph(), Scheduler::kSplitNodes);
     42 
     43     if (FLAG_trace_turbo_scheduler) {
     44       OFStream os(stdout);
     45       os << *schedule << std::endl;
     46     }
     47     ScheduleVerifier::Run(schedule);
     48     EXPECT_EQ(expected, GetScheduledNodeCount(schedule));
     49     return schedule;
     50   }
     51 
     52   size_t GetScheduledNodeCount(const Schedule* schedule) {
     53     size_t node_count = 0;
     54     for (auto block : *schedule->rpo_order()) {
     55       node_count += block->NodeCount();
     56       if (block->control() != BasicBlock::kNone) ++node_count;
     57     }
     58     return node_count;
     59   }
     60 
     61   Graph* graph() { return &graph_; }
     62   CommonOperatorBuilder* common() { return &common_; }
     63   SimplifiedOperatorBuilder* simplified() { return &simplified_; }
     64   JSOperatorBuilder* js() { return &js_; }
     65 
     66  private:
     67   Graph graph_;
     68   CommonOperatorBuilder common_;
     69   SimplifiedOperatorBuilder simplified_;
     70   JSOperatorBuilder js_;
     71 };
     72 
     73 
     74 namespace {
     75 
     76 const Operator kHeapConstant(IrOpcode::kHeapConstant, Operator::kPure,
     77                              "HeapConstant", 0, 0, 0, 1, 0, 0);
     78 const Operator kIntAdd(IrOpcode::kInt32Add, Operator::kPure, "Int32Add", 2, 0,
     79                        0, 1, 0, 0);
     80 const Operator kMockCall(IrOpcode::kCall, Operator::kNoProperties, "MockCall",
     81                          0, 0, 1, 1, 1, 2);
     82 const Operator kMockTailCall(IrOpcode::kTailCall, Operator::kNoProperties,
     83                              "MockTailCall", 1, 1, 1, 0, 0, 1);
     84 
     85 }  // namespace
     86 
     87 
     88 TEST_F(SchedulerTest, BuildScheduleEmpty) {
     89   graph()->SetStart(graph()->NewNode(common()->Start(0)));
     90   graph()->SetEnd(graph()->NewNode(common()->End(1), graph()->start()));
     91   USE(Scheduler::ComputeSchedule(zone(), graph(), Scheduler::kNoFlags));
     92 }
     93 
     94 
     95 TEST_F(SchedulerTest, BuildScheduleOneParameter) {
     96   graph()->SetStart(graph()->NewNode(common()->Start(0)));
     97 
     98   Node* p1 = graph()->NewNode(common()->Parameter(0), graph()->start());
     99   Node* ret = graph()->NewNode(common()->Return(), p1, graph()->start(),
    100                                graph()->start());
    101 
    102   graph()->SetEnd(graph()->NewNode(common()->End(1), ret));
    103 
    104   USE(Scheduler::ComputeSchedule(zone(), graph(), Scheduler::kNoFlags));
    105 }
    106 
    107 
    108 namespace {
    109 
    110 Node* CreateDiamond(Graph* graph, CommonOperatorBuilder* common, Node* cond) {
    111   Node* tv = graph->NewNode(common->Int32Constant(6));
    112   Node* fv = graph->NewNode(common->Int32Constant(7));
    113   Node* br = graph->NewNode(common->Branch(), cond, graph->start());
    114   Node* t = graph->NewNode(common->IfTrue(), br);
    115   Node* f = graph->NewNode(common->IfFalse(), br);
    116   Node* m = graph->NewNode(common->Merge(2), t, f);
    117   Node* phi =
    118       graph->NewNode(common->Phi(MachineRepresentation::kTagged, 2), tv, fv, m);
    119   return phi;
    120 }
    121 
    122 }  // namespace
    123 
    124 
    125 TARGET_TEST_F(SchedulerTest, FloatingDiamond1) {
    126   Node* start = graph()->NewNode(common()->Start(1));
    127   graph()->SetStart(start);
    128 
    129   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    130   Node* d1 = CreateDiamond(graph(), common(), p0);
    131   Node* ret = graph()->NewNode(common()->Return(), d1, start, start);
    132   Node* end = graph()->NewNode(common()->End(1), ret);
    133 
    134   graph()->SetEnd(end);
    135 
    136   ComputeAndVerifySchedule(13);
    137 }
    138 
    139 TARGET_TEST_F(SchedulerTest, FloatingDeadDiamond1) {
    140   Node* start = graph()->NewNode(common()->Start(1));
    141   graph()->SetStart(start);
    142 
    143   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    144   Node* d1 = CreateDiamond(graph(), common(), p0);
    145   USE(d1);
    146   Node* ret = graph()->NewNode(common()->Return(), p0, start, start);
    147   Node* end = graph()->NewNode(common()->End(1), ret);
    148 
    149   graph()->SetEnd(end);
    150 
    151   ComputeAndVerifySchedule(4);
    152 }
    153 
    154 TARGET_TEST_F(SchedulerTest, FloatingDeadDiamond2) {
    155   Graph* g = graph();
    156   Node* start = g->NewNode(common()->Start(1));
    157   g->SetStart(start);
    158 
    159   Node* n1 = g->NewNode(common()->Parameter(1), start);
    160 
    161   Node* n2 = g->NewNode(common()->Branch(), n1, start);
    162   Node* n3 = g->NewNode(common()->IfTrue(), n2);
    163   Node* n4 = g->NewNode(common()->IfFalse(), n2);
    164   Node* n5 = g->NewNode(common()->Int32Constant(-100));
    165   Node* n6 = g->NewNode(common()->Return(), n5, start, n4);
    166   Node* n7 = g->NewNode(common()->Int32Constant(0));
    167   Node* n8 = g->NewNode(common()->Return(), n7, start, n3);
    168   Node* n9 = g->NewNode(common()->End(2), n6, n8);
    169 
    170   // Dead nodes
    171   Node* n10 = g->NewNode(common()->Branch(), n1, n3);
    172   Node* n11 = g->NewNode(common()->IfTrue(), n10);
    173   Node* n12 = g->NewNode(common()->IfFalse(), n10);
    174   Node* n13 = g->NewNode(common()->Merge(2), n11, n12);
    175   Node* n14 =
    176       g->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), n1, n7, n13);
    177 
    178   USE(n14);
    179 
    180   g->SetEnd(n9);
    181 
    182   ComputeAndVerifySchedule(10);
    183 }
    184 
    185 TARGET_TEST_F(SchedulerTest, FloatingDiamond2) {
    186   Node* start = graph()->NewNode(common()->Start(2));
    187   graph()->SetStart(start);
    188 
    189   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    190   Node* p1 = graph()->NewNode(common()->Parameter(1), start);
    191   Node* d1 = CreateDiamond(graph(), common(), p0);
    192   Node* d2 = CreateDiamond(graph(), common(), p1);
    193   Node* add = graph()->NewNode(&kIntAdd, d1, d2);
    194   Node* ret = graph()->NewNode(common()->Return(), add, start, start);
    195   Node* end = graph()->NewNode(common()->End(1), ret);
    196 
    197   graph()->SetEnd(end);
    198 
    199   ComputeAndVerifySchedule(24);
    200 }
    201 
    202 
    203 TARGET_TEST_F(SchedulerTest, FloatingDiamond3) {
    204   Node* start = graph()->NewNode(common()->Start(2));
    205   graph()->SetStart(start);
    206 
    207   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    208   Node* p1 = graph()->NewNode(common()->Parameter(1), start);
    209   Node* d1 = CreateDiamond(graph(), common(), p0);
    210   Node* d2 = CreateDiamond(graph(), common(), p1);
    211   Node* add = graph()->NewNode(&kIntAdd, d1, d2);
    212   Node* d3 = CreateDiamond(graph(), common(), add);
    213   Node* ret = graph()->NewNode(common()->Return(), d3, start, start);
    214   Node* end = graph()->NewNode(common()->End(1), ret);
    215 
    216   graph()->SetEnd(end);
    217 
    218   ComputeAndVerifySchedule(33);
    219 }
    220 
    221 
    222 TARGET_TEST_F(SchedulerTest, NestedFloatingDiamonds) {
    223   Node* start = graph()->NewNode(common()->Start(2));
    224   graph()->SetStart(start);
    225 
    226   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    227 
    228   Node* fv = graph()->NewNode(common()->Int32Constant(7));
    229   Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start());
    230   Node* t = graph()->NewNode(common()->IfTrue(), br);
    231   Node* f = graph()->NewNode(common()->IfFalse(), br);
    232 
    233   Node* map = graph()->NewNode(
    234       simplified()->LoadElement(AccessBuilder::ForFixedArrayElement()), p0, p0,
    235       start, f);
    236   Node* br1 = graph()->NewNode(common()->Branch(), map, graph()->start());
    237   Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
    238   Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
    239   Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1);
    240   Node* ttrue = graph()->NewNode(common()->Int32Constant(1));
    241   Node* ffalse = graph()->NewNode(common()->Int32Constant(0));
    242   Node* phi1 = graph()->NewNode(
    243       common()->Phi(MachineRepresentation::kTagged, 2), ttrue, ffalse, m1);
    244 
    245 
    246   Node* m = graph()->NewNode(common()->Merge(2), t, f);
    247   Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
    248                                fv, phi1, m);
    249   Node* ephi1 = graph()->NewNode(common()->EffectPhi(2), start, map, m);
    250 
    251   Node* ret = graph()->NewNode(common()->Return(), phi, ephi1, start);
    252   Node* end = graph()->NewNode(common()->End(1), ret);
    253 
    254   graph()->SetEnd(end);
    255 
    256   ComputeAndVerifySchedule(23);
    257 }
    258 
    259 
    260 TARGET_TEST_F(SchedulerTest, NestedFloatingDiamondWithChain) {
    261   Node* start = graph()->NewNode(common()->Start(2));
    262   graph()->SetStart(start);
    263 
    264   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    265   Node* p1 = graph()->NewNode(common()->Parameter(1), start);
    266   Node* c = graph()->NewNode(common()->Int32Constant(7));
    267 
    268   Node* brA1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
    269   Node* tA1 = graph()->NewNode(common()->IfTrue(), brA1);
    270   Node* fA1 = graph()->NewNode(common()->IfFalse(), brA1);
    271   Node* mA1 = graph()->NewNode(common()->Merge(2), tA1, fA1);
    272   Node* phiA1 = graph()->NewNode(
    273       common()->Phi(MachineRepresentation::kTagged, 2), p0, p1, mA1);
    274 
    275   Node* brB1 = graph()->NewNode(common()->Branch(), p1, graph()->start());
    276   Node* tB1 = graph()->NewNode(common()->IfTrue(), brB1);
    277   Node* fB1 = graph()->NewNode(common()->IfFalse(), brB1);
    278   Node* mB1 = graph()->NewNode(common()->Merge(2), tB1, fB1);
    279   Node* phiB1 = graph()->NewNode(
    280       common()->Phi(MachineRepresentation::kTagged, 2), p0, p1, mB1);
    281 
    282   Node* brA2 = graph()->NewNode(common()->Branch(), phiB1, mA1);
    283   Node* tA2 = graph()->NewNode(common()->IfTrue(), brA2);
    284   Node* fA2 = graph()->NewNode(common()->IfFalse(), brA2);
    285   Node* mA2 = graph()->NewNode(common()->Merge(2), tA2, fA2);
    286   Node* phiA2 = graph()->NewNode(
    287       common()->Phi(MachineRepresentation::kTagged, 2), phiB1, c, mA2);
    288 
    289   Node* brB2 = graph()->NewNode(common()->Branch(), phiA1, mB1);
    290   Node* tB2 = graph()->NewNode(common()->IfTrue(), brB2);
    291   Node* fB2 = graph()->NewNode(common()->IfFalse(), brB2);
    292   Node* mB2 = graph()->NewNode(common()->Merge(2), tB2, fB2);
    293   Node* phiB2 = graph()->NewNode(
    294       common()->Phi(MachineRepresentation::kTagged, 2), phiA1, c, mB2);
    295 
    296   Node* add = graph()->NewNode(&kIntAdd, phiA2, phiB2);
    297   Node* ret = graph()->NewNode(common()->Return(), add, start, start);
    298   Node* end = graph()->NewNode(common()->End(1), ret);
    299 
    300   graph()->SetEnd(end);
    301 
    302   ComputeAndVerifySchedule(36);
    303 }
    304 
    305 
    306 TARGET_TEST_F(SchedulerTest, NestedFloatingDiamondWithLoop) {
    307   Node* start = graph()->NewNode(common()->Start(2));
    308   graph()->SetStart(start);
    309 
    310   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    311 
    312   Node* fv = graph()->NewNode(common()->Int32Constant(7));
    313   Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start());
    314   Node* t = graph()->NewNode(common()->IfTrue(), br);
    315   Node* f = graph()->NewNode(common()->IfFalse(), br);
    316 
    317   Node* loop = graph()->NewNode(common()->Loop(2), f, start);
    318   Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
    319                                p0, p0, loop);
    320 
    321   Node* add = graph()->NewNode(&kIntAdd, ind, fv);
    322   Node* br1 = graph()->NewNode(common()->Branch(), add, loop);
    323   Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
    324   Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
    325 
    326   loop->ReplaceInput(1, t1);  // close loop.
    327   ind->ReplaceInput(1, ind);  // close induction variable.
    328 
    329   Node* m = graph()->NewNode(common()->Merge(2), t, f1);
    330   Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
    331                                fv, ind, m);
    332 
    333   Node* ret = graph()->NewNode(common()->Return(), phi, start, start);
    334   Node* end = graph()->NewNode(common()->End(1), ret);
    335 
    336   graph()->SetEnd(end);
    337 
    338   ComputeAndVerifySchedule(20);
    339 }
    340 
    341 
    342 TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond1) {
    343   Node* start = graph()->NewNode(common()->Start(2));
    344   graph()->SetStart(start);
    345 
    346   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    347 
    348   Node* c = graph()->NewNode(common()->Int32Constant(7));
    349   Node* loop = graph()->NewNode(common()->Loop(2), start, start);
    350   Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
    351                                p0, p0, loop);
    352   Node* add = graph()->NewNode(&kIntAdd, ind, c);
    353 
    354   Node* br = graph()->NewNode(common()->Branch(), add, loop);
    355   Node* t = graph()->NewNode(common()->IfTrue(), br);
    356   Node* f = graph()->NewNode(common()->IfFalse(), br);
    357 
    358   Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
    359   Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
    360   Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
    361   Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1);
    362   Node* phi1 = graph()->NewNode(
    363       common()->Phi(MachineRepresentation::kTagged, 2), add, p0, m1);
    364 
    365   loop->ReplaceInput(1, t);    // close loop.
    366   ind->ReplaceInput(1, phi1);  // close induction variable.
    367 
    368   Node* ret = graph()->NewNode(common()->Return(), ind, start, f);
    369   Node* end = graph()->NewNode(common()->End(2), ret, f);
    370 
    371   graph()->SetEnd(end);
    372 
    373   ComputeAndVerifySchedule(20);
    374 }
    375 
    376 
    377 TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond2) {
    378   Node* start = graph()->NewNode(common()->Start(2));
    379   graph()->SetStart(start);
    380 
    381   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    382 
    383   Node* c = graph()->NewNode(common()->Int32Constant(7));
    384   Node* loop = graph()->NewNode(common()->Loop(2), start, start);
    385   Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
    386                                p0, p0, loop);
    387 
    388   Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
    389   Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
    390   Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
    391   Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1);
    392   Node* phi1 = graph()->NewNode(
    393       common()->Phi(MachineRepresentation::kTagged, 2), c, ind, m1);
    394 
    395   Node* add = graph()->NewNode(&kIntAdd, ind, phi1);
    396 
    397   Node* br = graph()->NewNode(common()->Branch(), add, loop);
    398   Node* t = graph()->NewNode(common()->IfTrue(), br);
    399   Node* f = graph()->NewNode(common()->IfFalse(), br);
    400 
    401   loop->ReplaceInput(1, t);   // close loop.
    402   ind->ReplaceInput(1, add);  // close induction variable.
    403 
    404   Node* ret = graph()->NewNode(common()->Return(), ind, start, f);
    405   Node* end = graph()->NewNode(common()->End(2), ret, f);
    406 
    407   graph()->SetEnd(end);
    408 
    409   ComputeAndVerifySchedule(20);
    410 }
    411 
    412 
    413 TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond3) {
    414   Node* start = graph()->NewNode(common()->Start(2));
    415   graph()->SetStart(start);
    416 
    417   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    418 
    419   Node* c = graph()->NewNode(common()->Int32Constant(7));
    420   Node* loop = graph()->NewNode(common()->Loop(2), start, start);
    421   Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
    422                                p0, p0, loop);
    423 
    424   Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
    425   Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
    426   Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
    427 
    428   Node* loop1 = graph()->NewNode(common()->Loop(2), t1, start);
    429   Node* ind1 = graph()->NewNode(
    430       common()->Phi(MachineRepresentation::kTagged, 2), p0, p0, loop);
    431 
    432   Node* add1 = graph()->NewNode(&kIntAdd, ind1, c);
    433   Node* br2 = graph()->NewNode(common()->Branch(), add1, loop1);
    434   Node* t2 = graph()->NewNode(common()->IfTrue(), br2);
    435   Node* f2 = graph()->NewNode(common()->IfFalse(), br2);
    436 
    437   loop1->ReplaceInput(1, t2);   // close inner loop.
    438   ind1->ReplaceInput(1, ind1);  // close inner induction variable.
    439 
    440   Node* m1 = graph()->NewNode(common()->Merge(2), f1, f2);
    441   Node* phi1 = graph()->NewNode(
    442       common()->Phi(MachineRepresentation::kTagged, 2), c, ind1, m1);
    443 
    444   Node* add = graph()->NewNode(&kIntAdd, ind, phi1);
    445 
    446   Node* br = graph()->NewNode(common()->Branch(), add, loop);
    447   Node* t = graph()->NewNode(common()->IfTrue(), br);
    448   Node* f = graph()->NewNode(common()->IfFalse(), br);
    449 
    450   loop->ReplaceInput(1, t);   // close loop.
    451   ind->ReplaceInput(1, add);  // close induction variable.
    452 
    453   Node* ret = graph()->NewNode(common()->Return(), ind, start, f);
    454   Node* end = graph()->NewNode(common()->End(2), ret, f);
    455 
    456   graph()->SetEnd(end);
    457 
    458   ComputeAndVerifySchedule(28);
    459 }
    460 
    461 
    462 TARGET_TEST_F(SchedulerTest, PhisPushedDownToDifferentBranches) {
    463   Node* start = graph()->NewNode(common()->Start(2));
    464   graph()->SetStart(start);
    465 
    466   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    467   Node* p1 = graph()->NewNode(common()->Parameter(1), start);
    468 
    469   Node* v1 = graph()->NewNode(common()->Int32Constant(1));
    470   Node* v2 = graph()->NewNode(common()->Int32Constant(2));
    471   Node* v3 = graph()->NewNode(common()->Int32Constant(3));
    472   Node* v4 = graph()->NewNode(common()->Int32Constant(4));
    473   Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start());
    474   Node* t = graph()->NewNode(common()->IfTrue(), br);
    475   Node* f = graph()->NewNode(common()->IfFalse(), br);
    476   Node* m = graph()->NewNode(common()->Merge(2), t, f);
    477   Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
    478                                v1, v2, m);
    479   Node* phi2 = graph()->NewNode(
    480       common()->Phi(MachineRepresentation::kTagged, 2), v3, v4, m);
    481 
    482   Node* br2 = graph()->NewNode(common()->Branch(), p1, graph()->start());
    483   Node* t2 = graph()->NewNode(common()->IfTrue(), br2);
    484   Node* f2 = graph()->NewNode(common()->IfFalse(), br2);
    485   Node* m2 = graph()->NewNode(common()->Merge(2), t2, f2);
    486   Node* phi3 = graph()->NewNode(
    487       common()->Phi(MachineRepresentation::kTagged, 2), phi, phi2, m2);
    488 
    489   Node* ret = graph()->NewNode(common()->Return(), phi3, start, start);
    490   Node* end = graph()->NewNode(common()->End(1), ret);
    491 
    492   graph()->SetEnd(end);
    493 
    494   ComputeAndVerifySchedule(24);
    495 }
    496 
    497 
    498 TARGET_TEST_F(SchedulerTest, BranchHintTrue) {
    499   Node* start = graph()->NewNode(common()->Start(1));
    500   graph()->SetStart(start);
    501 
    502   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    503   Node* tv = graph()->NewNode(common()->Int32Constant(6));
    504   Node* fv = graph()->NewNode(common()->Int32Constant(7));
    505   Node* br = graph()->NewNode(common()->Branch(BranchHint::kTrue), p0, start);
    506   Node* t = graph()->NewNode(common()->IfTrue(), br);
    507   Node* f = graph()->NewNode(common()->IfFalse(), br);
    508   Node* m = graph()->NewNode(common()->Merge(2), t, f);
    509   Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
    510                                tv, fv, m);
    511   Node* ret = graph()->NewNode(common()->Return(), phi, start, start);
    512   Node* end = graph()->NewNode(common()->End(1), ret);
    513 
    514   graph()->SetEnd(end);
    515 
    516   Schedule* schedule = ComputeAndVerifySchedule(13);
    517   // Make sure the false block is marked as deferred.
    518   EXPECT_FALSE(schedule->block(t)->deferred());
    519   EXPECT_TRUE(schedule->block(f)->deferred());
    520 }
    521 
    522 
    523 TARGET_TEST_F(SchedulerTest, BranchHintFalse) {
    524   Node* start = graph()->NewNode(common()->Start(1));
    525   graph()->SetStart(start);
    526 
    527   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    528   Node* tv = graph()->NewNode(common()->Int32Constant(6));
    529   Node* fv = graph()->NewNode(common()->Int32Constant(7));
    530   Node* br = graph()->NewNode(common()->Branch(BranchHint::kFalse), p0, start);
    531   Node* t = graph()->NewNode(common()->IfTrue(), br);
    532   Node* f = graph()->NewNode(common()->IfFalse(), br);
    533   Node* m = graph()->NewNode(common()->Merge(2), t, f);
    534   Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
    535                                tv, fv, m);
    536   Node* ret = graph()->NewNode(common()->Return(), phi, start, start);
    537   Node* end = graph()->NewNode(common()->End(1), ret);
    538 
    539   graph()->SetEnd(end);
    540 
    541   Schedule* schedule = ComputeAndVerifySchedule(13);
    542   // Make sure the true block is marked as deferred.
    543   EXPECT_TRUE(schedule->block(t)->deferred());
    544   EXPECT_FALSE(schedule->block(f)->deferred());
    545 }
    546 
    547 
    548 TARGET_TEST_F(SchedulerTest, CallException) {
    549   Node* start = graph()->NewNode(common()->Start(1));
    550   graph()->SetStart(start);
    551 
    552   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    553   Node* c1 = graph()->NewNode(&kMockCall, start);
    554   Node* ok1 = graph()->NewNode(common()->IfSuccess(), c1);
    555   Node* ex1 = graph()->NewNode(
    556       common()->IfException(IfExceptionHint::kLocallyUncaught), c1, c1);
    557   Node* c2 = graph()->NewNode(&kMockCall, ok1);
    558   Node* ok2 = graph()->NewNode(common()->IfSuccess(), c2);
    559   Node* ex2 = graph()->NewNode(
    560       common()->IfException(IfExceptionHint::kLocallyUncaught), c2, c2);
    561   Node* hdl = graph()->NewNode(common()->Merge(2), ex1, ex2);
    562   Node* m = graph()->NewNode(common()->Merge(2), ok2, hdl);
    563   Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
    564                                c2, p0, m);
    565   Node* ret = graph()->NewNode(common()->Return(), phi, start, m);
    566   Node* end = graph()->NewNode(common()->End(1), ret);
    567 
    568   graph()->SetEnd(end);
    569 
    570   Schedule* schedule = ComputeAndVerifySchedule(17);
    571   // Make sure the exception blocks as well as the handler are deferred.
    572   EXPECT_TRUE(schedule->block(ex1)->deferred());
    573   EXPECT_TRUE(schedule->block(ex2)->deferred());
    574   EXPECT_TRUE(schedule->block(hdl)->deferred());
    575   EXPECT_FALSE(schedule->block(m)->deferred());
    576 }
    577 
    578 
    579 TARGET_TEST_F(SchedulerTest, TailCall) {
    580   Node* start = graph()->NewNode(common()->Start(1));
    581   graph()->SetStart(start);
    582 
    583   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    584   Node* call = graph()->NewNode(&kMockTailCall, p0, start, start);
    585   Node* end = graph()->NewNode(common()->End(1), call);
    586 
    587   graph()->SetEnd(end);
    588 
    589   ComputeAndVerifySchedule(4);
    590 }
    591 
    592 
    593 TARGET_TEST_F(SchedulerTest, Switch) {
    594   Node* start = graph()->NewNode(common()->Start(1));
    595   graph()->SetStart(start);
    596 
    597   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    598   Node* sw = graph()->NewNode(common()->Switch(3), p0, start);
    599   Node* c0 = graph()->NewNode(common()->IfValue(0), sw);
    600   Node* v0 = graph()->NewNode(common()->Int32Constant(11));
    601   Node* c1 = graph()->NewNode(common()->IfValue(1), sw);
    602   Node* v1 = graph()->NewNode(common()->Int32Constant(22));
    603   Node* d = graph()->NewNode(common()->IfDefault(), sw);
    604   Node* vd = graph()->NewNode(common()->Int32Constant(33));
    605   Node* m = graph()->NewNode(common()->Merge(3), c0, c1, d);
    606   Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 3),
    607                                v0, v1, vd, m);
    608   Node* ret = graph()->NewNode(common()->Return(), phi, start, m);
    609   Node* end = graph()->NewNode(common()->End(1), ret);
    610 
    611   graph()->SetEnd(end);
    612 
    613   ComputeAndVerifySchedule(16);
    614 }
    615 
    616 
    617 TARGET_TEST_F(SchedulerTest, FloatingSwitch) {
    618   Node* start = graph()->NewNode(common()->Start(1));
    619   graph()->SetStart(start);
    620 
    621   Node* p0 = graph()->NewNode(common()->Parameter(0), start);
    622   Node* sw = graph()->NewNode(common()->Switch(3), p0, start);
    623   Node* c0 = graph()->NewNode(common()->IfValue(0), sw);
    624   Node* v0 = graph()->NewNode(common()->Int32Constant(11));
    625   Node* c1 = graph()->NewNode(common()->IfValue(1), sw);
    626   Node* v1 = graph()->NewNode(common()->Int32Constant(22));
    627   Node* d = graph()->NewNode(common()->IfDefault(), sw);
    628   Node* vd = graph()->NewNode(common()->Int32Constant(33));
    629   Node* m = graph()->NewNode(common()->Merge(3), c0, c1, d);
    630   Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 3),
    631                                v0, v1, vd, m);
    632   Node* ret = graph()->NewNode(common()->Return(), phi, start, start);
    633   Node* end = graph()->NewNode(common()->End(1), ret);
    634 
    635   graph()->SetEnd(end);
    636 
    637   ComputeAndVerifySchedule(16);
    638 }
    639 
    640 
    641 TARGET_TEST_F(SchedulerTest, Terminate) {
    642   Node* start = graph()->NewNode(common()->Start(1));
    643   graph()->SetStart(start);
    644 
    645   Node* loop = graph()->NewNode(common()->Loop(2), start, start);
    646   loop->ReplaceInput(1, loop);  // self loop, NTL.
    647 
    648   Node* effect = graph()->NewNode(common()->EffectPhi(2), start, start, loop);
    649   effect->ReplaceInput(1, effect);  // self loop.
    650 
    651   Node* terminate = graph()->NewNode(common()->Terminate(), effect, loop);
    652   Node* end = graph()->NewNode(common()->End(1), terminate);
    653   graph()->SetEnd(end);
    654 
    655   Schedule* schedule = ComputeAndVerifySchedule(6);
    656   BasicBlock* block = schedule->block(loop);
    657   EXPECT_EQ(block, schedule->block(effect));
    658   EXPECT_GE(block->rpo_number(), 0);
    659 }
    660 
    661 }  // namespace compiler
    662 }  // namespace internal
    663 }  // namespace v8
    664