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