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
10using testing::ElementsAre;
11
12namespace v8 {
13namespace internal {
14namespace compiler {
15
16typedef TestWithIsolateAndZone BasicBlockTest;
17
18
19TEST_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
30TEST_F(BasicBlockTest, GetCommonDominator1) {
31  BasicBlock b(zone(), BasicBlock::Id::FromInt(0));
32  EXPECT_EQ(&b, BasicBlock::GetCommonDominator(&b, &b));
33}
34
35
36TEST_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
54TEST_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
71typedef TestWithZone ScheduleTest;
72
73
74namespace {
75
76const Operator kCallOperator(IrOpcode::kCall, Operator::kNoProperties,
77                             "MockCall", 0, 0, 0, 0, 0, 0);
78const Operator kBranchOperator(IrOpcode::kBranch, Operator::kNoProperties,
79                               "MockBranch", 0, 0, 0, 0, 0, 0);
80const Operator kDummyOperator(IrOpcode::kParameter, Operator::kNoProperties,
81                              "Dummy", 0, 0, 0, 0, 0, 0);
82
83}  // namespace
84
85
86TEST_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
97TEST_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
117TEST_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
140TEST_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
169TEST_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
198TEST_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
213TEST_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