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 250
