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