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/effect-control-linearizer.h"
      6 #include "src/compiler/access-builder.h"
      7 #include "src/compiler/js-graph.h"
      8 #include "src/compiler/linkage.h"
      9 #include "src/compiler/node-properties.h"
     10 #include "src/compiler/schedule.h"
     11 #include "src/compiler/simplified-operator.h"
     12 #include "test/unittests/compiler/graph-unittest.h"
     13 #include "test/unittests/compiler/node-test-utils.h"
     14 #include "test/unittests/test-utils.h"
     15 #include "testing/gmock/include/gmock/gmock.h"
     16 
     17 namespace v8 {
     18 namespace internal {
     19 namespace compiler {
     20 
     21 class EffectControlLinearizerTest : public TypedGraphTest {
     22  public:
     23   EffectControlLinearizerTest()
     24       : TypedGraphTest(3),
     25         machine_(zone()),
     26         javascript_(zone()),
     27         simplified_(zone()),
     28         jsgraph_(isolate(), graph(), common(), &javascript_, &simplified_,
     29                  &machine_) {}
     30 
     31   JSGraph* jsgraph() { return &jsgraph_; }
     32   SimplifiedOperatorBuilder* simplified() { return &simplified_; }
     33 
     34  private:
     35   MachineOperatorBuilder machine_;
     36   JSOperatorBuilder javascript_;
     37   SimplifiedOperatorBuilder simplified_;
     38   JSGraph jsgraph_;
     39 };
     40 
     41 namespace {
     42 
     43 BasicBlock* AddBlockToSchedule(Schedule* schedule) {
     44   BasicBlock* block = schedule->NewBasicBlock();
     45   block->set_rpo_number(static_cast<int32_t>(schedule->rpo_order()->size()));
     46   schedule->rpo_order()->push_back(block);
     47   return block;
     48 }
     49 
     50 }  // namespace
     51 
     52 TEST_F(EffectControlLinearizerTest, SimpleLoad) {
     53   Schedule schedule(zone());
     54 
     55   // Create the graph.
     56   Node* heap_number = NumberConstant(0.5);
     57   Node* load = graph()->NewNode(
     58       simplified()->LoadField(AccessBuilder::ForHeapNumberValue()), heap_number,
     59       graph()->start(), graph()->start());
     60   Node* ret = graph()->NewNode(common()->Return(), load, graph()->start(),
     61                                graph()->start());
     62 
     63   // Build the basic block structure.
     64   BasicBlock* start = schedule.start();
     65   schedule.rpo_order()->push_back(start);
     66   start->set_rpo_number(0);
     67 
     68   // Populate the basic blocks with nodes.
     69   schedule.AddNode(start, graph()->start());
     70   schedule.AddNode(start, heap_number);
     71   schedule.AddNode(start, load);
     72   schedule.AddReturn(start, ret);
     73 
     74   // Run the state effect introducer.
     75   EffectControlLinearizer introducer(jsgraph(), &schedule, zone());
     76   introducer.Run();
     77 
     78   EXPECT_THAT(load,
     79               IsLoadField(AccessBuilder::ForHeapNumberValue(), heap_number,
     80                           graph()->start(), graph()->start()));
     81   // The return should have reconnected effect edge to the load.
     82   EXPECT_THAT(ret, IsReturn(load, load, graph()->start()));
     83 }
     84 
     85 TEST_F(EffectControlLinearizerTest, DiamondLoad) {
     86   Schedule schedule(zone());
     87 
     88   // Create the graph.
     89   Node* branch =
     90       graph()->NewNode(common()->Branch(), Int32Constant(0), graph()->start());
     91 
     92   Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
     93   Node* heap_number = NumberConstant(0.5);
     94   Node* vtrue = graph()->NewNode(
     95       simplified()->LoadField(AccessBuilder::ForHeapNumberValue()), heap_number,
     96       graph()->start(), if_true);
     97 
     98   Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
     99   Node* vfalse = Float64Constant(2);
    100 
    101   Node* merge = graph()->NewNode(common()->Merge(2), if_true, if_false);
    102   Node* phi = graph()->NewNode(
    103       common()->Phi(MachineRepresentation::kFloat64, 2), vtrue, vfalse, merge);
    104 
    105   Node* ret =
    106       graph()->NewNode(common()->Return(), phi, graph()->start(), merge);
    107 
    108   // Build the basic block structure.
    109   BasicBlock* start = schedule.start();
    110   schedule.rpo_order()->push_back(start);
    111   start->set_rpo_number(0);
    112 
    113   BasicBlock* tblock = AddBlockToSchedule(&schedule);
    114   BasicBlock* fblock = AddBlockToSchedule(&schedule);
    115   BasicBlock* mblock = AddBlockToSchedule(&schedule);
    116 
    117   // Populate the basic blocks with nodes.
    118   schedule.AddNode(start, graph()->start());
    119   schedule.AddBranch(start, branch, tblock, fblock);
    120 
    121   schedule.AddNode(tblock, if_true);
    122   schedule.AddNode(tblock, heap_number);
    123   schedule.AddNode(tblock, vtrue);
    124   schedule.AddGoto(tblock, mblock);
    125 
    126   schedule.AddNode(fblock, if_false);
    127   schedule.AddNode(fblock, vfalse);
    128   schedule.AddGoto(fblock, mblock);
    129 
    130   schedule.AddNode(mblock, merge);
    131   schedule.AddNode(mblock, phi);
    132   schedule.AddReturn(mblock, ret);
    133 
    134   // Run the state effect introducer.
    135   EffectControlLinearizer introducer(jsgraph(), &schedule, zone());
    136   introducer.Run();
    137 
    138   // The effect input to the return should be an effect phi with the
    139   // newly introduced effectful change operators.
    140   ASSERT_THAT(
    141       ret, IsReturn(phi, IsEffectPhi(vtrue, graph()->start(), merge), merge));
    142 }
    143 
    144 TEST_F(EffectControlLinearizerTest, FloatingDiamondsControlWiring) {
    145   Schedule schedule(zone());
    146 
    147   // Create the graph and schedule. Roughly (omitting effects and unimportant
    148   // nodes):
    149   //
    150   //            BLOCK 0:
    151   //             r1: Start
    152   //             c1: Call
    153   //             b1: Branch(const0, s1)
    154   //                |
    155   //        +-------+------+
    156   //        |              |
    157   //   BLOCK 1:           BLOCK 2:
    158   //    t1: IfTrue(b1)     f1: IfFalse(b1)
    159   //        |              |
    160   //        +-------+------+
    161   //                |
    162   //            BLOCK 3:
    163   //             m1: Merge(t1, f1)
    164   //             c2: IfSuccess(c1)
    165   //             b2: Branch(const0 , s1)
    166   //                |
    167   //        +-------+------+
    168   //        |              |
    169   //   BLOCK 4:           BLOCK 5:
    170   //    t2: IfTrue(b2)     f2:IfFalse(b2)
    171   //        |              |
    172   //        +-------+------+
    173   //                |
    174   //            BLOCK 6:
    175   //             m2: Merge(t2, f2)
    176   //             r1: Return(c1, c2)
    177   MachineType kMachineSignature[] = {MachineType::AnyTagged(),
    178                                      MachineType::AnyTagged()};
    179   LinkageLocation kLocationSignature[] = {LinkageLocation::ForRegister(0),
    180                                           LinkageLocation::ForRegister(1)};
    181   const CallDescriptor* kCallDescriptor = new (zone()) CallDescriptor(
    182       CallDescriptor::kCallCodeObject, MachineType::AnyTagged(),
    183       LinkageLocation::ForRegister(0),
    184       new (zone()) MachineSignature(1, 1, kMachineSignature),
    185       new (zone()) LocationSignature(1, 1, kLocationSignature), 0,
    186       Operator::kNoProperties, 0, 0, CallDescriptor::kNoFlags);
    187   Node* p0 = Parameter(0);
    188   Node* p1 = Parameter(1);
    189   Node* const0 = Int32Constant(0);
    190   Node* call = graph()->NewNode(common()->Call(kCallDescriptor), p0, p1,
    191                                 graph()->start(), graph()->start());
    192   Node* if_success = graph()->NewNode(common()->IfSuccess(), call);
    193 
    194   // First Floating diamond.
    195   Node* branch1 =
    196       graph()->NewNode(common()->Branch(), const0, graph()->start());
    197   Node* if_true1 = graph()->NewNode(common()->IfTrue(), branch1);
    198   Node* if_false1 = graph()->NewNode(common()->IfFalse(), branch1);
    199   Node* merge1 = graph()->NewNode(common()->Merge(2), if_true1, if_false1);
    200 
    201   // Second floating diamond.
    202   Node* branch2 =
    203       graph()->NewNode(common()->Branch(), const0, graph()->start());
    204   Node* if_true2 = graph()->NewNode(common()->IfTrue(), branch2);
    205   Node* if_false2 = graph()->NewNode(common()->IfFalse(), branch2);
    206   Node* merge2 = graph()->NewNode(common()->Merge(2), if_true2, if_false2);
    207 
    208   Node* ret =
    209       graph()->NewNode(common()->Return(), call, graph()->start(), if_success);
    210 
    211   // Build the basic block structure.
    212   BasicBlock* start = schedule.start();
    213   schedule.rpo_order()->push_back(start);
    214   start->set_rpo_number(0);
    215 
    216   BasicBlock* t1block = AddBlockToSchedule(&schedule);
    217   BasicBlock* f1block = AddBlockToSchedule(&schedule);
    218   BasicBlock* m1block = AddBlockToSchedule(&schedule);
    219 
    220   BasicBlock* t2block = AddBlockToSchedule(&schedule);
    221   BasicBlock* f2block = AddBlockToSchedule(&schedule);
    222   BasicBlock* m2block = AddBlockToSchedule(&schedule);
    223 
    224   // Populate the basic blocks with nodes.
    225   schedule.AddNode(start, graph()->start());
    226   schedule.AddNode(start, p0);
    227   schedule.AddNode(start, p1);
    228   schedule.AddNode(start, const0);
    229   schedule.AddNode(start, call);
    230   schedule.AddBranch(start, branch1, t1block, f1block);
    231 
    232   schedule.AddNode(t1block, if_true1);
    233   schedule.AddGoto(t1block, m1block);
    234 
    235   schedule.AddNode(f1block, if_false1);
    236   schedule.AddGoto(f1block, m1block);
    237 
    238   schedule.AddNode(m1block, merge1);
    239   // The scheduler does not always put the IfSuccess node to the corresponding
    240   // call's block, simulate that here.
    241   schedule.AddNode(m1block, if_success);
    242   schedule.AddBranch(m1block, branch2, t2block, f2block);
    243 
    244   schedule.AddNode(t2block, if_true2);
    245   schedule.AddGoto(t2block, m2block);
    246 
    247   schedule.AddNode(f2block, if_false2);
    248   schedule.AddGoto(f2block, m2block);
    249 
    250   schedule.AddNode(m2block, merge2);
    251   schedule.AddReturn(m2block, ret);
    252 
    253   // Run the state effect introducer.
    254   EffectControlLinearizer introducer(jsgraph(), &schedule, zone());
    255   introducer.Run();
    256 
    257   // The effect input to the return should be an effect phi with the
    258   // newly introduced effectful change operators.
    259   ASSERT_THAT(ret, IsReturn(call, call, merge2));
    260   ASSERT_THAT(branch2, IsBranch(const0, merge1));
    261   ASSERT_THAT(branch1, IsBranch(const0, if_success));
    262   ASSERT_THAT(if_success, IsIfSuccess(call));
    263 }
    264 
    265 TEST_F(EffectControlLinearizerTest, LoopLoad) {
    266   Schedule schedule(zone());
    267 
    268   // Create the graph.
    269   Node* loop = graph()->NewNode(common()->Loop(1), graph()->start());
    270   Node* effect_phi =
    271       graph()->NewNode(common()->EffectPhi(1), graph()->start(), loop);
    272 
    273   Node* cond = Int32Constant(0);
    274   Node* branch = graph()->NewNode(common()->Branch(), cond, loop);
    275 
    276   Node* if_true = graph()->NewNode(common()->IfTrue(), branch);
    277 
    278   Node* if_false = graph()->NewNode(common()->IfFalse(), branch);
    279 
    280   loop->AppendInput(zone(), if_false);
    281   NodeProperties::ChangeOp(loop, common()->Loop(2));
    282 
    283   effect_phi->InsertInput(zone(), 1, effect_phi);
    284   NodeProperties::ChangeOp(effect_phi, common()->EffectPhi(2));
    285 
    286   Node* heap_number = NumberConstant(0.5);
    287   Node* load = graph()->NewNode(
    288       simplified()->LoadField(AccessBuilder::ForHeapNumberValue()), heap_number,
    289       graph()->start(), loop);
    290 
    291   Node* ret = graph()->NewNode(common()->Return(), load, effect_phi, if_true);
    292 
    293   // Build the basic block structure.
    294   BasicBlock* start = schedule.start();
    295   schedule.rpo_order()->push_back(start);
    296   start->set_rpo_number(0);
    297 
    298   BasicBlock* lblock = AddBlockToSchedule(&schedule);
    299   BasicBlock* fblock = AddBlockToSchedule(&schedule);
    300   BasicBlock* rblock = AddBlockToSchedule(&schedule);
    301 
    302   // Populate the basic blocks with nodes.
    303   schedule.AddNode(start, graph()->start());
    304   schedule.AddGoto(start, lblock);
    305 
    306   schedule.AddNode(lblock, loop);
    307   schedule.AddNode(lblock, effect_phi);
    308   schedule.AddNode(lblock, heap_number);
    309   schedule.AddNode(lblock, load);
    310   schedule.AddNode(lblock, cond);
    311   schedule.AddBranch(lblock, branch, rblock, fblock);
    312 
    313   schedule.AddNode(fblock, if_false);
    314   schedule.AddGoto(fblock, lblock);
    315 
    316   schedule.AddNode(rblock, if_true);
    317   schedule.AddReturn(rblock, ret);
    318 
    319   // Run the state effect introducer.
    320   EffectControlLinearizer introducer(jsgraph(), &schedule, zone());
    321   introducer.Run();
    322 
    323   ASSERT_THAT(ret, IsReturn(load, load, if_true));
    324   EXPECT_THAT(load, IsLoadField(AccessBuilder::ForHeapNumberValue(),
    325                                 heap_number, effect_phi, loop));
    326 }
    327 
    328 }  // namespace compiler
    329 }  // namespace internal
    330 }  // namespace v8
    331