deps/v8/test/unittests/compiler/schedule-unittest.cc

   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/node.h"
   6 #include "src/compiler/schedule.h"
   7 #include "test/unittests/test-utils.h"
   8 #include "testing/gmock/include/gmock/gmock.h"
   9
  10 using testing::ElementsAre;
  11
  12 namespace v8 {
  13 namespace internal {
  14 namespace compiler {
  15
  16 typedef TestWithIsolateAndZone BasicBlockTest;
  17
  18
  19 TEST_F(BasicBlockTest, Constructor) {
  20   int const id = random_number_generator()->NextInt();
  21   BasicBlock b(zone(), BasicBlock::Id::FromInt(id));
  22   EXPECT_FALSE(b.deferred());
  23   EXPECT_GT(0, b.dominator_depth());
  24   EXPECT_EQ(nullptr, b.dominator());
  25   EXPECT_EQ(nullptr, b.rpo_next());
  26   EXPECT_EQ(id, b.id().ToInt());
  27 }
  28
  29
  30 TEST_F(BasicBlockTest, GetCommonDominator1) {
  31   BasicBlock b(zone(), BasicBlock::Id::FromInt(0));
  32   EXPECT_EQ(&b, BasicBlock::GetCommonDominator(&b, &b));
  33 }
  34
  35
  36 TEST_F(BasicBlockTest, GetCommonDominator2) {
  37   BasicBlock b0(zone(), BasicBlock::Id::FromInt(0));
  38   BasicBlock b1(zone(), BasicBlock::Id::FromInt(1));
  39   BasicBlock b2(zone(), BasicBlock::Id::FromInt(2));
  40   b0.set_dominator_depth(0);
  41   b1.set_dominator(&b0);
  42   b1.set_dominator_depth(1);
  43   b2.set_dominator(&b1);
  44   b2.set_dominator_depth(2);
  45   EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b0, &b1));
  46   EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b0, &b2));
  47   EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b1, &b0));
  48   EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b2, &b0));
  49   EXPECT_EQ(&b1, BasicBlock::GetCommonDominator(&b1, &b2));
  50   EXPECT_EQ(&b1, BasicBlock::GetCommonDominator(&b2, &b1));
  51 }
  52
  53
  54 TEST_F(BasicBlockTest, GetCommonDominator3) {
  55   BasicBlock b0(zone(), BasicBlock::Id::FromInt(0));
  56   BasicBlock b1(zone(), BasicBlock::Id::FromInt(1));
  57   BasicBlock b2(zone(), BasicBlock::Id::FromInt(2));
  58   BasicBlock b3(zone(), BasicBlock::Id::FromInt(3));
  59   b0.set_dominator_depth(0);
  60   b1.set_dominator(&b0);
  61   b1.set_dominator_depth(1);
  62   b2.set_dominator(&b0);
  63   b2.set_dominator_depth(1);
  64   b3.set_dominator(&b2);
  65   b3.set_dominator_depth(2);
  66   EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b1, &b3));
  67   EXPECT_EQ(&b0, BasicBlock::GetCommonDominator(&b3, &b1));
  68 }
  69
  70
  71 typedef TestWithZone ScheduleTest;
  72
  73
  74 namespace {
  75
  76 const Operator kCallOperator(IrOpcode::kCall, Operator::kNoProperties,
  77                              "MockCall", 0, 0, 0, 0, 0, 0);
  78 const Operator kBranchOperator(IrOpcode::kBranch, Operator::kNoProperties,
  79                                "MockBranch", 0, 0, 0, 0, 0, 0);
  80 const Operator kDummyOperator(IrOpcode::kParameter, Operator::kNoProperties,
  81                               "Dummy", 0, 0, 0, 0, 0, 0);
  82
  83 }  // namespace
  84
  85
  86 TEST_F(ScheduleTest, Constructor) {
  87   Schedule schedule(zone());
  88   EXPECT_NE(nullptr, schedule.start());
  89   EXPECT_EQ(schedule.start(),
  90             schedule.GetBlockById(BasicBlock::Id::FromInt(0)));
  91   EXPECT_NE(nullptr, schedule.end());
  92   EXPECT_EQ(schedule.end(), schedule.GetBlockById(BasicBlock::Id::FromInt(1)));
  93   EXPECT_NE(schedule.start(), schedule.end());
  94 }
  95
  96
  97 TEST_F(ScheduleTest, AddNode) {
  98   Schedule schedule(zone());
  99   BasicBlock* start = schedule.start();
 100
 101   Node* node0 = Node::New(zone(), 0, &kDummyOperator, 0, nullptr, false);
 102   EXPECT_EQ(nullptr, schedule.block(node0));
 103   schedule.AddNode(start, node0);
 104   EXPECT_EQ(start, schedule.block(node0));
 105   EXPECT_THAT(*start, ElementsAre(node0));
 106
 107   Node* node1 = Node::New(zone(), 1, &kDummyOperator, 0, nullptr, false);
 108   EXPECT_EQ(nullptr, schedule.block(node1));
 109   schedule.AddNode(start, node1);
 110   EXPECT_EQ(start, schedule.block(node1));
 111   EXPECT_THAT(*start, ElementsAre(node0, node1));
 112
 113   EXPECT_TRUE(schedule.SameBasicBlock(node0, node1));
 114 }
 115
 116
 117 TEST_F(ScheduleTest, AddGoto) {
 118   Schedule schedule(zone());
 119   BasicBlock* start = schedule.start();
 120   BasicBlock* end = schedule.end();
 121
 122   BasicBlock* block = schedule.NewBasicBlock();
 123   schedule.AddGoto(start, block);
 124
 125   EXPECT_EQ(0u, start->PredecessorCount());
 126   EXPECT_EQ(1u, start->SuccessorCount());
 127   EXPECT_EQ(block, start->SuccessorAt(0));
 128   EXPECT_THAT(start->successors(), ElementsAre(block));
 129
 130   EXPECT_EQ(1u, block->PredecessorCount());
 131   EXPECT_EQ(0u, block->SuccessorCount());
 132   EXPECT_EQ(start, block->PredecessorAt(0));
 133   EXPECT_THAT(block->predecessors(), ElementsAre(start));
 134
 135   EXPECT_EQ(0u, end->PredecessorCount());
 136   EXPECT_EQ(0u, end->SuccessorCount());
 137 }
 138
 139
 140 TEST_F(ScheduleTest, AddCall) {
 141   Schedule schedule(zone());
 142   BasicBlock* start = schedule.start();
 143
 144   Node* call = Node::New(zone(), 0, &kCallOperator, 0, nullptr, false);
 145   BasicBlock* sblock = schedule.NewBasicBlock();
 146   BasicBlock* eblock = schedule.NewBasicBlock();
 147   schedule.AddCall(start, call, sblock, eblock);
 148
 149   EXPECT_EQ(start, schedule.block(call));
 150
 151   EXPECT_EQ(0u, start->PredecessorCount());
 152   EXPECT_EQ(2u, start->SuccessorCount());
 153   EXPECT_EQ(sblock, start->SuccessorAt(0));
 154   EXPECT_EQ(eblock, start->SuccessorAt(1));
 155   EXPECT_THAT(start->successors(), ElementsAre(sblock, eblock));
 156
 157   EXPECT_EQ(1u, sblock->PredecessorCount());
 158   EXPECT_EQ(0u, sblock->SuccessorCount());
 159   EXPECT_EQ(start, sblock->PredecessorAt(0));
 160   EXPECT_THAT(sblock->predecessors(), ElementsAre(start));
 161
 162   EXPECT_EQ(1u, eblock->PredecessorCount());
 163   EXPECT_EQ(0u, eblock->SuccessorCount());
 164   EXPECT_EQ(start, eblock->PredecessorAt(0));
 165   EXPECT_THAT(eblock->predecessors(), ElementsAre(start));
 166 }
 167
 168
 169 TEST_F(ScheduleTest, AddBranch) {
 170   Schedule schedule(zone());
 171   BasicBlock* start = schedule.start();
 172
 173   Node* branch = Node::New(zone(), 0, &kBranchOperator, 0, nullptr, false);
 174   BasicBlock* tblock = schedule.NewBasicBlock();
 175   BasicBlock* fblock = schedule.NewBasicBlock();
 176   schedule.AddBranch(start, branch, tblock, fblock);
 177
 178   EXPECT_EQ(start, schedule.block(branch));
 179
 180   EXPECT_EQ(0u, start->PredecessorCount());
 181   EXPECT_EQ(2u, start->SuccessorCount());
 182   EXPECT_EQ(tblock, start->SuccessorAt(0));
 183   EXPECT_EQ(fblock, start->SuccessorAt(1));
 184   EXPECT_THAT(start->successors(), ElementsAre(tblock, fblock));
 185
 186   EXPECT_EQ(1u, tblock->PredecessorCount());
 187   EXPECT_EQ(0u, tblock->SuccessorCount());
 188   EXPECT_EQ(start, tblock->PredecessorAt(0));
 189   EXPECT_THAT(tblock->predecessors(), ElementsAre(start));
 190
 191   EXPECT_EQ(1u, fblock->PredecessorCount());
 192   EXPECT_EQ(0u, fblock->SuccessorCount());
 193   EXPECT_EQ(start, fblock->PredecessorAt(0));
 194   EXPECT_THAT(fblock->predecessors(), ElementsAre(start));
 195 }
 196
 197
 198 TEST_F(ScheduleTest, AddReturn) {
 199   Schedule schedule(zone());
 200   BasicBlock* start = schedule.start();
 201   BasicBlock* end = schedule.end();
 202
 203   Node* node = Node::New(zone(), 0, &kDummyOperator, 0, nullptr, false);
 204   schedule.AddReturn(start, node);
 205
 206   EXPECT_EQ(0u, start->PredecessorCount());
 207   EXPECT_EQ(1u, start->SuccessorCount());
 208   EXPECT_EQ(end, start->SuccessorAt(0));
 209   EXPECT_THAT(start->successors(), ElementsAre(end));
 210 }
 211
 212
 213 TEST_F(ScheduleTest, InsertBranch) {
 214   Schedule schedule(zone());
 215   BasicBlock* start = schedule.start();
 216   BasicBlock* end = schedule.end();
 217
 218   Node* node = Node::New(zone(), 0, &kDummyOperator, 0, nullptr, false);
 219   Node* branch = Node::New(zone(), 0, &kBranchOperator, 0, nullptr, false);
 220   BasicBlock* tblock = schedule.NewBasicBlock();
 221   BasicBlock* fblock = schedule.NewBasicBlock();
 222   BasicBlock* mblock = schedule.NewBasicBlock();
 223
 224   schedule.AddReturn(start, node);
 225   schedule.AddGoto(tblock, mblock);
 226   schedule.AddGoto(fblock, mblock);
 227   schedule.InsertBranch(start, mblock, branch, tblock, fblock);
 228
 229   EXPECT_EQ(0u, start->PredecessorCount());
 230   EXPECT_EQ(2u, start->SuccessorCount());
 231   EXPECT_EQ(tblock, start->SuccessorAt(0));
 232   EXPECT_EQ(fblock, start->SuccessorAt(1));
 233   EXPECT_THAT(start->successors(), ElementsAre(tblock, fblock));
 234
 235   EXPECT_EQ(2u, mblock->PredecessorCount());
 236   EXPECT_EQ(1u, mblock->SuccessorCount());
 237   EXPECT_EQ(end, mblock->SuccessorAt(0));
 238   EXPECT_THAT(mblock->predecessors(), ElementsAre(tblock, fblock));
 239   EXPECT_THAT(mblock->successors(), ElementsAre(end));
 240
 241   EXPECT_EQ(1u, end->PredecessorCount());
 242   EXPECT_EQ(0u, end->SuccessorCount());
 243   EXPECT_EQ(mblock, end->PredecessorAt(0));
 244   EXPECT_THAT(end->predecessors(), ElementsAre(mblock));
 245 }
 246
 247 }  // namespace compiler
 248 }  // namespace internal
 249 }  // namespace v8