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 <memory>
6
7 #include "src/compiler/schedule.h"
8 #include "src/compiler/scheduler.h"
9 #include "test/unittests/compiler/compiler-test-utils.h"
10 #include "test/unittests/test-utils.h"
11 #include "testing/gmock/include/gmock/gmock.h"
12
13 using testing::AnyOf;
14
15 namespace v8 {
16 namespace internal {
17 namespace compiler {
18
19 class SchedulerRPOTest : public TestWithZone {
20 public:
21 SchedulerRPOTest() = default;
22
CheckRPONumbers(BasicBlockVector * order,size_t expected,bool loops_allowed)23 void CheckRPONumbers(BasicBlockVector* order, size_t expected,
24 bool loops_allowed) {
25 CHECK(expected == order->size());
26 for (int i = 0; i < static_cast<int>(order->size()); i++) {
27 CHECK(order->at(i)->rpo_number() == i);
28 if (!loops_allowed) {
29 CHECK(!order->at(i)->loop_end());
30 CHECK(!order->at(i)->loop_header());
31 }
32 }
33 }
34
CheckLoop(BasicBlockVector * order,BasicBlock ** blocks,int body_size)35 void CheckLoop(BasicBlockVector* order, BasicBlock** blocks, int body_size) {
36 BasicBlock* header = blocks[0];
37 BasicBlock* end = header->loop_end();
38 CHECK(end);
39 CHECK_GT(end->rpo_number(), 0);
40 CHECK_EQ(body_size, end->rpo_number() - header->rpo_number());
41 for (int i = 0; i < body_size; i++) {
42 CHECK_GE(blocks[i]->rpo_number(), header->rpo_number());
43 CHECK_LT(blocks[i]->rpo_number(), end->rpo_number());
44 CHECK(header->LoopContains(blocks[i]));
45 CHECK(header->IsLoopHeader() || blocks[i]->loop_header() == header);
46 }
47 if (header->rpo_number() > 0) {
48 CHECK_NE(order->at(header->rpo_number() - 1)->loop_header(), header);
49 }
50 if (end->rpo_number() < static_cast<int>(order->size())) {
51 CHECK_NE(order->at(end->rpo_number())->loop_header(), header);
52 }
53 }
54
55 struct TestLoop {
56 int count;
57 BasicBlock** nodes;
headerv8::internal::compiler::SchedulerRPOTest::TestLoop58 BasicBlock* header() { return nodes[0]; }
lastv8::internal::compiler::SchedulerRPOTest::TestLoop59 BasicBlock* last() { return nodes[count - 1]; }
~TestLoopv8::internal::compiler::SchedulerRPOTest::TestLoop60 ~TestLoop() { delete[] nodes; }
61 };
62
CreateLoop(Schedule * schedule,int count)63 TestLoop* CreateLoop(Schedule* schedule, int count) {
64 TestLoop* loop = new TestLoop();
65 loop->count = count;
66 loop->nodes = new BasicBlock*[count];
67 for (int i = 0; i < count; i++) {
68 loop->nodes[i] = schedule->NewBasicBlock();
69 if (i > 0) {
70 schedule->AddSuccessorForTesting(loop->nodes[i - 1], loop->nodes[i]);
71 }
72 }
73 schedule->AddSuccessorForTesting(loop->nodes[count - 1], loop->nodes[0]);
74 return loop;
75 }
76 };
77
TEST_F(SchedulerRPOTest,Degenerate1)78 TEST_F(SchedulerRPOTest, Degenerate1) {
79 Schedule schedule(zone());
80 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
81 CheckRPONumbers(order, 1, false);
82 EXPECT_EQ(schedule.start(), order->at(0));
83 }
84
TEST_F(SchedulerRPOTest,Degenerate2)85 TEST_F(SchedulerRPOTest, Degenerate2) {
86 Schedule schedule(zone());
87
88 schedule.AddGoto(schedule.start(), schedule.end());
89 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
90 CheckRPONumbers(order, 2, false);
91 EXPECT_EQ(schedule.start(), order->at(0));
92 EXPECT_EQ(schedule.end(), order->at(1));
93 }
94
TEST_F(SchedulerRPOTest,Line)95 TEST_F(SchedulerRPOTest, Line) {
96 for (int i = 0; i < 10; i++) {
97 Schedule schedule(zone());
98
99 BasicBlock* last = schedule.start();
100 for (int j = 0; j < i; j++) {
101 BasicBlock* block = schedule.NewBasicBlock();
102 block->set_deferred(i & 1);
103 schedule.AddGoto(last, block);
104 last = block;
105 }
106 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
107 CheckRPONumbers(order, 1 + i, false);
108
109 for (size_t j = 0; j < schedule.BasicBlockCount(); j++) {
110 BasicBlock* block = schedule.GetBlockById(BasicBlock::Id::FromSize(j));
111 if (block->rpo_number() >= 0 && block->SuccessorCount() == 1) {
112 EXPECT_EQ(block->rpo_number() + 1, block->SuccessorAt(0)->rpo_number());
113 }
114 }
115 }
116 }
117
TEST_F(SchedulerRPOTest,SelfLoop)118 TEST_F(SchedulerRPOTest, SelfLoop) {
119 Schedule schedule(zone());
120 schedule.AddSuccessorForTesting(schedule.start(), schedule.start());
121 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
122 CheckRPONumbers(order, 1, true);
123 BasicBlock* loop[] = {schedule.start()};
124 CheckLoop(order, loop, 1);
125 }
126
TEST_F(SchedulerRPOTest,EntryLoop)127 TEST_F(SchedulerRPOTest, EntryLoop) {
128 Schedule schedule(zone());
129 BasicBlock* body = schedule.NewBasicBlock();
130 schedule.AddSuccessorForTesting(schedule.start(), body);
131 schedule.AddSuccessorForTesting(body, schedule.start());
132 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
133 CheckRPONumbers(order, 2, true);
134 BasicBlock* loop[] = {schedule.start(), body};
135 CheckLoop(order, loop, 2);
136 }
137
TEST_F(SchedulerRPOTest,EndLoop)138 TEST_F(SchedulerRPOTest, EndLoop) {
139 Schedule schedule(zone());
140 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 2));
141 schedule.AddSuccessorForTesting(schedule.start(), loop1->header());
142 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
143 CheckRPONumbers(order, 3, true);
144 CheckLoop(order, loop1->nodes, loop1->count);
145 }
146
TEST_F(SchedulerRPOTest,EndLoopNested)147 TEST_F(SchedulerRPOTest, EndLoopNested) {
148 Schedule schedule(zone());
149 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 2));
150 schedule.AddSuccessorForTesting(schedule.start(), loop1->header());
151 schedule.AddSuccessorForTesting(loop1->last(), schedule.start());
152 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
153 CheckRPONumbers(order, 3, true);
154 CheckLoop(order, loop1->nodes, loop1->count);
155 }
156
TEST_F(SchedulerRPOTest,Diamond)157 TEST_F(SchedulerRPOTest, Diamond) {
158 Schedule schedule(zone());
159
160 BasicBlock* A = schedule.start();
161 BasicBlock* B = schedule.NewBasicBlock();
162 BasicBlock* C = schedule.NewBasicBlock();
163 BasicBlock* D = schedule.end();
164
165 schedule.AddSuccessorForTesting(A, B);
166 schedule.AddSuccessorForTesting(A, C);
167 schedule.AddSuccessorForTesting(B, D);
168 schedule.AddSuccessorForTesting(C, D);
169
170 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
171 CheckRPONumbers(order, 4, false);
172
173 EXPECT_EQ(0, A->rpo_number());
174 EXPECT_THAT(B->rpo_number(), AnyOf(1, 2));
175 EXPECT_THAT(C->rpo_number(), AnyOf(1, 2));
176 EXPECT_EQ(3, D->rpo_number());
177 }
178
TEST_F(SchedulerRPOTest,Loop1)179 TEST_F(SchedulerRPOTest, Loop1) {
180 Schedule schedule(zone());
181
182 BasicBlock* A = schedule.start();
183 BasicBlock* B = schedule.NewBasicBlock();
184 BasicBlock* C = schedule.NewBasicBlock();
185 BasicBlock* D = schedule.end();
186
187 schedule.AddSuccessorForTesting(A, B);
188 schedule.AddSuccessorForTesting(B, C);
189 schedule.AddSuccessorForTesting(C, B);
190 schedule.AddSuccessorForTesting(C, D);
191
192 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
193 CheckRPONumbers(order, 4, true);
194 BasicBlock* loop[] = {B, C};
195 CheckLoop(order, loop, 2);
196 }
197
TEST_F(SchedulerRPOTest,Loop2)198 TEST_F(SchedulerRPOTest, Loop2) {
199 Schedule schedule(zone());
200
201 BasicBlock* A = schedule.start();
202 BasicBlock* B = schedule.NewBasicBlock();
203 BasicBlock* C = schedule.NewBasicBlock();
204 BasicBlock* D = schedule.end();
205
206 schedule.AddSuccessorForTesting(A, B);
207 schedule.AddSuccessorForTesting(B, C);
208 schedule.AddSuccessorForTesting(C, B);
209 schedule.AddSuccessorForTesting(B, D);
210
211 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
212 CheckRPONumbers(order, 4, true);
213 BasicBlock* loop[] = {B, C};
214 CheckLoop(order, loop, 2);
215 }
216
TEST_F(SchedulerRPOTest,LoopN)217 TEST_F(SchedulerRPOTest, LoopN) {
218 for (int i = 0; i < 11; i++) {
219 Schedule schedule(zone());
220 BasicBlock* A = schedule.start();
221 BasicBlock* B = schedule.NewBasicBlock();
222 BasicBlock* C = schedule.NewBasicBlock();
223 BasicBlock* D = schedule.NewBasicBlock();
224 BasicBlock* E = schedule.NewBasicBlock();
225 BasicBlock* F = schedule.NewBasicBlock();
226 BasicBlock* G = schedule.end();
227
228 schedule.AddSuccessorForTesting(A, B);
229 schedule.AddSuccessorForTesting(B, C);
230 schedule.AddSuccessorForTesting(C, D);
231 schedule.AddSuccessorForTesting(D, E);
232 schedule.AddSuccessorForTesting(E, F);
233 schedule.AddSuccessorForTesting(F, B);
234 schedule.AddSuccessorForTesting(B, G);
235
236 // Throw in extra backedges from time to time.
237 if (i == 1) schedule.AddSuccessorForTesting(B, B);
238 if (i == 2) schedule.AddSuccessorForTesting(C, B);
239 if (i == 3) schedule.AddSuccessorForTesting(D, B);
240 if (i == 4) schedule.AddSuccessorForTesting(E, B);
241 if (i == 5) schedule.AddSuccessorForTesting(F, B);
242
243 // Throw in extra loop exits from time to time.
244 if (i == 6) schedule.AddSuccessorForTesting(B, G);
245 if (i == 7) schedule.AddSuccessorForTesting(C, G);
246 if (i == 8) schedule.AddSuccessorForTesting(D, G);
247 if (i == 9) schedule.AddSuccessorForTesting(E, G);
248 if (i == 10) schedule.AddSuccessorForTesting(F, G);
249
250 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
251 CheckRPONumbers(order, 7, true);
252 BasicBlock* loop[] = {B, C, D, E, F};
253 CheckLoop(order, loop, 5);
254 }
255 }
256
TEST_F(SchedulerRPOTest,LoopNest1)257 TEST_F(SchedulerRPOTest, LoopNest1) {
258 Schedule schedule(zone());
259
260 BasicBlock* A = schedule.start();
261 BasicBlock* B = schedule.NewBasicBlock();
262 BasicBlock* C = schedule.NewBasicBlock();
263 BasicBlock* D = schedule.NewBasicBlock();
264 BasicBlock* E = schedule.NewBasicBlock();
265 BasicBlock* F = schedule.end();
266
267 schedule.AddSuccessorForTesting(A, B);
268 schedule.AddSuccessorForTesting(B, C);
269 schedule.AddSuccessorForTesting(C, D);
270 schedule.AddSuccessorForTesting(D, C);
271 schedule.AddSuccessorForTesting(D, E);
272 schedule.AddSuccessorForTesting(E, B);
273 schedule.AddSuccessorForTesting(E, F);
274
275 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
276 CheckRPONumbers(order, 6, true);
277 BasicBlock* loop1[] = {B, C, D, E};
278 CheckLoop(order, loop1, 4);
279
280 BasicBlock* loop2[] = {C, D};
281 CheckLoop(order, loop2, 2);
282 }
283
TEST_F(SchedulerRPOTest,LoopNest2)284 TEST_F(SchedulerRPOTest, LoopNest2) {
285 Schedule schedule(zone());
286
287 BasicBlock* A = schedule.start();
288 BasicBlock* B = schedule.NewBasicBlock();
289 BasicBlock* C = schedule.NewBasicBlock();
290 BasicBlock* D = schedule.NewBasicBlock();
291 BasicBlock* E = schedule.NewBasicBlock();
292 BasicBlock* F = schedule.NewBasicBlock();
293 BasicBlock* G = schedule.NewBasicBlock();
294 BasicBlock* H = schedule.end();
295
296 schedule.AddSuccessorForTesting(A, B);
297 schedule.AddSuccessorForTesting(B, C);
298 schedule.AddSuccessorForTesting(C, D);
299 schedule.AddSuccessorForTesting(D, E);
300 schedule.AddSuccessorForTesting(E, F);
301 schedule.AddSuccessorForTesting(F, G);
302 schedule.AddSuccessorForTesting(G, H);
303
304 schedule.AddSuccessorForTesting(E, D);
305 schedule.AddSuccessorForTesting(F, C);
306 schedule.AddSuccessorForTesting(G, B);
307
308 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
309 CheckRPONumbers(order, 8, true);
310 BasicBlock* loop1[] = {B, C, D, E, F, G};
311 CheckLoop(order, loop1, 6);
312
313 BasicBlock* loop2[] = {C, D, E, F};
314 CheckLoop(order, loop2, 4);
315
316 BasicBlock* loop3[] = {D, E};
317 CheckLoop(order, loop3, 2);
318 }
319
TEST_F(SchedulerRPOTest,LoopFollow1)320 TEST_F(SchedulerRPOTest, LoopFollow1) {
321 Schedule schedule(zone());
322
323 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 1));
324 std::unique_ptr<TestLoop> loop2(CreateLoop(&schedule, 1));
325
326 BasicBlock* A = schedule.start();
327 BasicBlock* E = schedule.end();
328
329 schedule.AddSuccessorForTesting(A, loop1->header());
330 schedule.AddSuccessorForTesting(loop1->header(), loop2->header());
331 schedule.AddSuccessorForTesting(loop2->last(), E);
332
333 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
334
335 EXPECT_EQ(schedule.BasicBlockCount(), order->size());
336 CheckLoop(order, loop1->nodes, loop1->count);
337 CheckLoop(order, loop2->nodes, loop2->count);
338 }
339
TEST_F(SchedulerRPOTest,LoopFollow2)340 TEST_F(SchedulerRPOTest, LoopFollow2) {
341 Schedule schedule(zone());
342
343 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 1));
344 std::unique_ptr<TestLoop> loop2(CreateLoop(&schedule, 1));
345
346 BasicBlock* A = schedule.start();
347 BasicBlock* S = schedule.NewBasicBlock();
348 BasicBlock* E = schedule.end();
349
350 schedule.AddSuccessorForTesting(A, loop1->header());
351 schedule.AddSuccessorForTesting(loop1->header(), S);
352 schedule.AddSuccessorForTesting(S, loop2->header());
353 schedule.AddSuccessorForTesting(loop2->last(), E);
354
355 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
356
357 EXPECT_EQ(schedule.BasicBlockCount(), order->size());
358 CheckLoop(order, loop1->nodes, loop1->count);
359 CheckLoop(order, loop2->nodes, loop2->count);
360 }
361
TEST_F(SchedulerRPOTest,LoopFollowN)362 TEST_F(SchedulerRPOTest, LoopFollowN) {
363 for (int size = 1; size < 5; size++) {
364 for (int exit = 0; exit < size; exit++) {
365 Schedule schedule(zone());
366 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size));
367 std::unique_ptr<TestLoop> loop2(CreateLoop(&schedule, size));
368 BasicBlock* A = schedule.start();
369 BasicBlock* E = schedule.end();
370
371 schedule.AddSuccessorForTesting(A, loop1->header());
372 schedule.AddSuccessorForTesting(loop1->nodes[exit], loop2->header());
373 schedule.AddSuccessorForTesting(loop2->nodes[exit], E);
374 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
375
376 EXPECT_EQ(schedule.BasicBlockCount(), order->size());
377 CheckLoop(order, loop1->nodes, loop1->count);
378 CheckLoop(order, loop2->nodes, loop2->count);
379 }
380 }
381 }
382
TEST_F(SchedulerRPOTest,NestedLoopFollow1)383 TEST_F(SchedulerRPOTest, NestedLoopFollow1) {
384 Schedule schedule(zone());
385
386 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 1));
387 std::unique_ptr<TestLoop> loop2(CreateLoop(&schedule, 1));
388
389 BasicBlock* A = schedule.start();
390 BasicBlock* B = schedule.NewBasicBlock();
391 BasicBlock* C = schedule.NewBasicBlock();
392 BasicBlock* E = schedule.end();
393
394 schedule.AddSuccessorForTesting(A, B);
395 schedule.AddSuccessorForTesting(B, loop1->header());
396 schedule.AddSuccessorForTesting(loop1->header(), loop2->header());
397 schedule.AddSuccessorForTesting(loop2->last(), C);
398 schedule.AddSuccessorForTesting(C, E);
399 schedule.AddSuccessorForTesting(C, B);
400
401 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
402
403 EXPECT_EQ(schedule.BasicBlockCount(), order->size());
404 CheckLoop(order, loop1->nodes, loop1->count);
405 CheckLoop(order, loop2->nodes, loop2->count);
406
407 BasicBlock* loop3[] = {B, loop1->nodes[0], loop2->nodes[0], C};
408 CheckLoop(order, loop3, 4);
409 }
410
TEST_F(SchedulerRPOTest,LoopBackedges1)411 TEST_F(SchedulerRPOTest, LoopBackedges1) {
412 int size = 8;
413 for (int i = 0; i < size; i++) {
414 for (int j = 0; j < size; j++) {
415 Schedule schedule(zone());
416 BasicBlock* A = schedule.start();
417 BasicBlock* E = schedule.end();
418
419 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size));
420 schedule.AddSuccessorForTesting(A, loop1->header());
421 schedule.AddSuccessorForTesting(loop1->last(), E);
422
423 schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header());
424 schedule.AddSuccessorForTesting(loop1->nodes[j], E);
425
426 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
427 CheckRPONumbers(order, schedule.BasicBlockCount(), true);
428 CheckLoop(order, loop1->nodes, loop1->count);
429 }
430 }
431 }
432
TEST_F(SchedulerRPOTest,LoopOutedges1)433 TEST_F(SchedulerRPOTest, LoopOutedges1) {
434 int size = 8;
435 for (int i = 0; i < size; i++) {
436 for (int j = 0; j < size; j++) {
437 Schedule schedule(zone());
438 BasicBlock* A = schedule.start();
439 BasicBlock* D = schedule.NewBasicBlock();
440 BasicBlock* E = schedule.end();
441
442 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size));
443 schedule.AddSuccessorForTesting(A, loop1->header());
444 schedule.AddSuccessorForTesting(loop1->last(), E);
445
446 schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header());
447 schedule.AddSuccessorForTesting(loop1->nodes[j], D);
448 schedule.AddSuccessorForTesting(D, E);
449
450 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
451 CheckRPONumbers(order, schedule.BasicBlockCount(), true);
452 CheckLoop(order, loop1->nodes, loop1->count);
453 }
454 }
455 }
456
TEST_F(SchedulerRPOTest,LoopOutedges2)457 TEST_F(SchedulerRPOTest, LoopOutedges2) {
458 int size = 8;
459 for (int i = 0; i < size; i++) {
460 Schedule schedule(zone());
461 BasicBlock* A = schedule.start();
462 BasicBlock* E = schedule.end();
463
464 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size));
465 schedule.AddSuccessorForTesting(A, loop1->header());
466 schedule.AddSuccessorForTesting(loop1->last(), E);
467
468 for (int j = 0; j < size; j++) {
469 BasicBlock* O = schedule.NewBasicBlock();
470 schedule.AddSuccessorForTesting(loop1->nodes[j], O);
471 schedule.AddSuccessorForTesting(O, E);
472 }
473
474 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
475 CheckRPONumbers(order, schedule.BasicBlockCount(), true);
476 CheckLoop(order, loop1->nodes, loop1->count);
477 }
478 }
479
TEST_F(SchedulerRPOTest,LoopOutloops1)480 TEST_F(SchedulerRPOTest, LoopOutloops1) {
481 int size = 8;
482 for (int i = 0; i < size; i++) {
483 Schedule schedule(zone());
484 BasicBlock* A = schedule.start();
485 BasicBlock* E = schedule.end();
486 std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size));
487 schedule.AddSuccessorForTesting(A, loop1->header());
488 schedule.AddSuccessorForTesting(loop1->last(), E);
489
490 TestLoop** loopN = new TestLoop*[size];
491 for (int j = 0; j < size; j++) {
492 loopN[j] = CreateLoop(&schedule, 2);
493 schedule.AddSuccessorForTesting(loop1->nodes[j], loopN[j]->header());
494 schedule.AddSuccessorForTesting(loopN[j]->last(), E);
495 }
496
497 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
498 CheckRPONumbers(order, schedule.BasicBlockCount(), true);
499 CheckLoop(order, loop1->nodes, loop1->count);
500
501 for (int j = 0; j < size; j++) {
502 CheckLoop(order, loopN[j]->nodes, loopN[j]->count);
503 delete loopN[j];
504 }
505 delete[] loopN;
506 }
507 }
508
TEST_F(SchedulerRPOTest,LoopMultibackedge)509 TEST_F(SchedulerRPOTest, LoopMultibackedge) {
510 Schedule schedule(zone());
511
512 BasicBlock* A = schedule.start();
513 BasicBlock* B = schedule.NewBasicBlock();
514 BasicBlock* C = schedule.NewBasicBlock();
515 BasicBlock* D = schedule.NewBasicBlock();
516 BasicBlock* E = schedule.NewBasicBlock();
517
518 schedule.AddSuccessorForTesting(A, B);
519 schedule.AddSuccessorForTesting(B, C);
520 schedule.AddSuccessorForTesting(B, D);
521 schedule.AddSuccessorForTesting(B, E);
522 schedule.AddSuccessorForTesting(C, B);
523 schedule.AddSuccessorForTesting(D, B);
524 schedule.AddSuccessorForTesting(E, B);
525
526 BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
527 CheckRPONumbers(order, 5, true);
528
529 BasicBlock* loop1[] = {B, C, D, E};
530 CheckLoop(order, loop1, 4);
531 }
532
533 } // namespace compiler
534 } // namespace internal
535 } // namespace v8
536