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