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 
TEST_F(BasicBlockTest,Constructor)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 
TEST_F(BasicBlockTest,GetCommonDominator1)30 TEST_F(BasicBlockTest, GetCommonDominator1) {
31   BasicBlock b(zone(), BasicBlock::Id::FromInt(0));
32   EXPECT_EQ(&b, BasicBlock::GetCommonDominator(&b, &b));
33 }
34 
35 
TEST_F(BasicBlockTest,GetCommonDominator2)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 
TEST_F(BasicBlockTest,GetCommonDominator3)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 
TEST_F(ScheduleTest,Constructor)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 
TEST_F(ScheduleTest,AddNode)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 
TEST_F(ScheduleTest,AddGoto)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 
TEST_F(ScheduleTest,AddCall)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 
TEST_F(ScheduleTest,AddBranch)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 
TEST_F(ScheduleTest,AddReturn)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 
TEST_F(ScheduleTest,InsertBranch)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