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 <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 22 : class SchedulerRPOTest : public TestWithZone {
20 : public:
21 22 : SchedulerRPOTest() = default;
22 :
23 177 : void CheckRPONumbers(BasicBlockVector* order, size_t expected,
24 : bool loops_allowed) {
25 177 : CHECK(expected == order->size());
26 3919 : for (int i = 0; i < static_cast<int>(order->size()); i++) {
27 3742 : CHECK(order->at(i)->rpo_number() == i);
28 1871 : if (!loops_allowed) {
29 62 : CHECK(!order->at(i)->loop_end());
30 62 : CHECK(!order->at(i)->loop_header());
31 : }
32 : }
33 177 : }
34 :
35 258 : void CheckLoop(BasicBlockVector* order, BasicBlock** blocks, int body_size) {
36 258 : BasicBlock* header = blocks[0];
37 : BasicBlock* end = header->loop_end();
38 258 : CHECK(end);
39 258 : CHECK_GT(end->rpo_number(), 0);
40 258 : CHECK_EQ(body_size, end->rpo_number() - header->rpo_number());
41 3134 : for (int i = 0; i < body_size; i++) {
42 1438 : CHECK_GE(blocks[i]->rpo_number(), header->rpo_number());
43 1438 : CHECK_LT(blocks[i]->rpo_number(), end->rpo_number());
44 1438 : CHECK(header->LoopContains(blocks[i]));
45 1438 : CHECK(header->IsLoopHeader() || blocks[i]->loop_header() == header);
46 : }
47 258 : if (header->rpo_number() > 0) {
48 512 : CHECK_NE(order->at(header->rpo_number() - 1)->loop_header(), header);
49 : }
50 258 : if (end->rpo_number() < static_cast<int>(order->size())) {
51 506 : CHECK_NE(order->at(end->rpo_number())->loop_header(), header);
52 : }
53 258 : }
54 :
55 : struct TestLoop {
56 : int count;
57 : BasicBlock** nodes;
58 365 : BasicBlock* header() { return nodes[0]; }
59 212 : BasicBlock* last() { return nodes[count - 1]; }
60 236 : ~TestLoop() { delete[] nodes; }
61 : };
62 :
63 236 : TestLoop* CreateLoop(Schedule* schedule, int count) {
64 236 : TestLoop* loop = new TestLoop();
65 236 : loop->count = count;
66 236 : loop->nodes = new BasicBlock*[count];
67 2936 : for (int i = 0; i < count; i++) {
68 1350 : loop->nodes[i] = schedule->NewBasicBlock();
69 1350 : if (i > 0) {
70 1114 : schedule->AddSuccessorForTesting(loop->nodes[i - 1], loop->nodes[i]);
71 : }
72 : }
73 236 : schedule->AddSuccessorForTesting(loop->nodes[count - 1], loop->nodes[0]);
74 236 : return loop;
75 : }
76 : };
77 :
78 15444 : TEST_F(SchedulerRPOTest, Degenerate1) {
79 1 : Schedule schedule(zone());
80 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
81 1 : CheckRPONumbers(order, 1, false);
82 2 : EXPECT_EQ(schedule.start(), order->at(0));
83 1 : }
84 :
85 15444 : TEST_F(SchedulerRPOTest, Degenerate2) {
86 1 : Schedule schedule(zone());
87 :
88 1 : schedule.AddGoto(schedule.start(), schedule.end());
89 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
90 1 : CheckRPONumbers(order, 2, false);
91 2 : EXPECT_EQ(schedule.start(), order->at(0));
92 2 : EXPECT_EQ(schedule.end(), order->at(1));
93 1 : }
94 :
95 15444 : TEST_F(SchedulerRPOTest, Line) {
96 21 : for (int i = 0; i < 10; i++) {
97 10 : Schedule schedule(zone());
98 :
99 : BasicBlock* last = schedule.start();
100 100 : for (int j = 0; j < i; j++) {
101 45 : BasicBlock* block = schedule.NewBasicBlock();
102 45 : block->set_deferred(i & 1);
103 45 : schedule.AddGoto(last, block);
104 : last = block;
105 : }
106 10 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
107 10 : CheckRPONumbers(order, 1 + i, false);
108 :
109 140 : for (size_t i = 0; i < schedule.BasicBlockCount(); i++) {
110 65 : BasicBlock* block = schedule.GetBlockById(BasicBlock::Id::FromSize(i));
111 120 : if (block->rpo_number() >= 0 && block->SuccessorCount() == 1) {
112 90 : EXPECT_EQ(block->rpo_number() + 1, block->SuccessorAt(0)->rpo_number());
113 : }
114 : }
115 : }
116 1 : }
117 :
118 15444 : TEST_F(SchedulerRPOTest, SelfLoop) {
119 1 : Schedule schedule(zone());
120 : schedule.AddSuccessorForTesting(schedule.start(), schedule.start());
121 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
122 1 : CheckRPONumbers(order, 1, true);
123 1 : BasicBlock* loop[] = {schedule.start()};
124 1 : CheckLoop(order, loop, 1);
125 1 : }
126 :
127 15444 : TEST_F(SchedulerRPOTest, EntryLoop) {
128 1 : Schedule schedule(zone());
129 1 : BasicBlock* body = schedule.NewBasicBlock();
130 : schedule.AddSuccessorForTesting(schedule.start(), body);
131 : schedule.AddSuccessorForTesting(body, schedule.start());
132 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
133 1 : CheckRPONumbers(order, 2, true);
134 1 : BasicBlock* loop[] = {schedule.start(), body};
135 1 : CheckLoop(order, loop, 2);
136 1 : }
137 :
138 15444 : TEST_F(SchedulerRPOTest, EndLoop) {
139 1 : Schedule schedule(zone());
140 1 : std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 2));
141 : schedule.AddSuccessorForTesting(schedule.start(), loop1->header());
142 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
143 1 : CheckRPONumbers(order, 3, true);
144 1 : CheckLoop(order, loop1->nodes, loop1->count);
145 1 : }
146 :
147 15444 : TEST_F(SchedulerRPOTest, EndLoopNested) {
148 1 : Schedule schedule(zone());
149 1 : std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 2));
150 : schedule.AddSuccessorForTesting(schedule.start(), loop1->header());
151 : schedule.AddSuccessorForTesting(loop1->last(), schedule.start());
152 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
153 1 : CheckRPONumbers(order, 3, true);
154 1 : CheckLoop(order, loop1->nodes, loop1->count);
155 1 : }
156 :
157 15444 : TEST_F(SchedulerRPOTest, Diamond) {
158 1 : Schedule schedule(zone());
159 :
160 : BasicBlock* A = schedule.start();
161 1 : BasicBlock* B = schedule.NewBasicBlock();
162 1 : 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 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
171 1 : CheckRPONumbers(order, 4, false);
172 :
173 2 : EXPECT_EQ(0, A->rpo_number());
174 2 : EXPECT_THAT(B->rpo_number(), AnyOf(1, 2));
175 2 : EXPECT_THAT(C->rpo_number(), AnyOf(1, 2));
176 2 : EXPECT_EQ(3, D->rpo_number());
177 1 : }
178 :
179 15444 : TEST_F(SchedulerRPOTest, Loop1) {
180 1 : Schedule schedule(zone());
181 :
182 : BasicBlock* A = schedule.start();
183 1 : BasicBlock* B = schedule.NewBasicBlock();
184 1 : 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 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
193 1 : CheckRPONumbers(order, 4, true);
194 1 : BasicBlock* loop[] = {B, C};
195 1 : CheckLoop(order, loop, 2);
196 1 : }
197 :
198 15444 : TEST_F(SchedulerRPOTest, Loop2) {
199 1 : Schedule schedule(zone());
200 :
201 : BasicBlock* A = schedule.start();
202 1 : BasicBlock* B = schedule.NewBasicBlock();
203 1 : 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 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
212 1 : CheckRPONumbers(order, 4, true);
213 1 : BasicBlock* loop[] = {B, C};
214 1 : CheckLoop(order, loop, 2);
215 1 : }
216 :
217 15444 : TEST_F(SchedulerRPOTest, LoopN) {
218 23 : for (int i = 0; i < 11; i++) {
219 11 : Schedule schedule(zone());
220 : BasicBlock* A = schedule.start();
221 11 : BasicBlock* B = schedule.NewBasicBlock();
222 11 : BasicBlock* C = schedule.NewBasicBlock();
223 11 : BasicBlock* D = schedule.NewBasicBlock();
224 11 : BasicBlock* E = schedule.NewBasicBlock();
225 11 : 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 11 : if (i == 1) schedule.AddSuccessorForTesting(B, B);
238 11 : if (i == 2) schedule.AddSuccessorForTesting(C, B);
239 11 : if (i == 3) schedule.AddSuccessorForTesting(D, B);
240 11 : if (i == 4) schedule.AddSuccessorForTesting(E, B);
241 11 : if (i == 5) schedule.AddSuccessorForTesting(F, B);
242 :
243 : // Throw in extra loop exits from time to time.
244 11 : if (i == 6) schedule.AddSuccessorForTesting(B, G);
245 11 : if (i == 7) schedule.AddSuccessorForTesting(C, G);
246 11 : if (i == 8) schedule.AddSuccessorForTesting(D, G);
247 11 : if (i == 9) schedule.AddSuccessorForTesting(E, G);
248 11 : if (i == 10) schedule.AddSuccessorForTesting(F, G);
249 :
250 11 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
251 11 : CheckRPONumbers(order, 7, true);
252 11 : BasicBlock* loop[] = {B, C, D, E, F};
253 11 : CheckLoop(order, loop, 5);
254 : }
255 1 : }
256 :
257 15444 : TEST_F(SchedulerRPOTest, LoopNest1) {
258 1 : Schedule schedule(zone());
259 :
260 : BasicBlock* A = schedule.start();
261 1 : BasicBlock* B = schedule.NewBasicBlock();
262 1 : BasicBlock* C = schedule.NewBasicBlock();
263 1 : BasicBlock* D = schedule.NewBasicBlock();
264 1 : 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 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
276 1 : CheckRPONumbers(order, 6, true);
277 1 : BasicBlock* loop1[] = {B, C, D, E};
278 1 : CheckLoop(order, loop1, 4);
279 :
280 1 : BasicBlock* loop2[] = {C, D};
281 1 : CheckLoop(order, loop2, 2);
282 1 : }
283 :
284 15444 : TEST_F(SchedulerRPOTest, LoopNest2) {
285 1 : Schedule schedule(zone());
286 :
287 : BasicBlock* A = schedule.start();
288 1 : BasicBlock* B = schedule.NewBasicBlock();
289 1 : BasicBlock* C = schedule.NewBasicBlock();
290 1 : BasicBlock* D = schedule.NewBasicBlock();
291 1 : BasicBlock* E = schedule.NewBasicBlock();
292 1 : BasicBlock* F = schedule.NewBasicBlock();
293 1 : 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 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
309 1 : CheckRPONumbers(order, 8, true);
310 1 : BasicBlock* loop1[] = {B, C, D, E, F, G};
311 1 : CheckLoop(order, loop1, 6);
312 :
313 1 : BasicBlock* loop2[] = {C, D, E, F};
314 1 : CheckLoop(order, loop2, 4);
315 :
316 1 : BasicBlock* loop3[] = {D, E};
317 1 : CheckLoop(order, loop3, 2);
318 1 : }
319 :
320 15444 : TEST_F(SchedulerRPOTest, LoopFollow1) {
321 1 : Schedule schedule(zone());
322 :
323 1 : std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 1));
324 1 : 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 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
334 :
335 3 : EXPECT_EQ(schedule.BasicBlockCount(), order->size());
336 1 : CheckLoop(order, loop1->nodes, loop1->count);
337 1 : CheckLoop(order, loop2->nodes, loop2->count);
338 1 : }
339 :
340 15444 : TEST_F(SchedulerRPOTest, LoopFollow2) {
341 1 : Schedule schedule(zone());
342 :
343 1 : std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 1));
344 1 : std::unique_ptr<TestLoop> loop2(CreateLoop(&schedule, 1));
345 :
346 : BasicBlock* A = schedule.start();
347 1 : 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 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
356 :
357 3 : EXPECT_EQ(schedule.BasicBlockCount(), order->size());
358 1 : CheckLoop(order, loop1->nodes, loop1->count);
359 1 : CheckLoop(order, loop2->nodes, loop2->count);
360 1 : }
361 :
362 15444 : TEST_F(SchedulerRPOTest, LoopFollowN) {
363 9 : for (int size = 1; size < 5; size++) {
364 24 : for (int exit = 0; exit < size; exit++) {
365 10 : Schedule schedule(zone());
366 10 : std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size));
367 10 : 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 10 : schedule.AddSuccessorForTesting(loop1->nodes[exit], loop2->header());
373 10 : schedule.AddSuccessorForTesting(loop2->nodes[exit], E);
374 10 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
375 :
376 30 : EXPECT_EQ(schedule.BasicBlockCount(), order->size());
377 10 : CheckLoop(order, loop1->nodes, loop1->count);
378 10 : CheckLoop(order, loop2->nodes, loop2->count);
379 : }
380 : }
381 1 : }
382 :
383 15444 : TEST_F(SchedulerRPOTest, NestedLoopFollow1) {
384 1 : Schedule schedule(zone());
385 :
386 1 : std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, 1));
387 1 : std::unique_ptr<TestLoop> loop2(CreateLoop(&schedule, 1));
388 :
389 : BasicBlock* A = schedule.start();
390 1 : BasicBlock* B = schedule.NewBasicBlock();
391 1 : 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 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
402 :
403 3 : EXPECT_EQ(schedule.BasicBlockCount(), order->size());
404 1 : CheckLoop(order, loop1->nodes, loop1->count);
405 1 : CheckLoop(order, loop2->nodes, loop2->count);
406 :
407 1 : BasicBlock* loop3[] = {B, loop1->nodes[0], loop2->nodes[0], C};
408 1 : CheckLoop(order, loop3, 4);
409 1 : }
410 :
411 15444 : TEST_F(SchedulerRPOTest, LoopBackedges1) {
412 : int size = 8;
413 17 : for (int i = 0; i < size; i++) {
414 136 : for (int j = 0; j < size; j++) {
415 64 : Schedule schedule(zone());
416 : BasicBlock* A = schedule.start();
417 : BasicBlock* E = schedule.end();
418 :
419 64 : std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size));
420 : schedule.AddSuccessorForTesting(A, loop1->header());
421 : schedule.AddSuccessorForTesting(loop1->last(), E);
422 :
423 64 : schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header());
424 64 : schedule.AddSuccessorForTesting(loop1->nodes[j], E);
425 :
426 64 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
427 64 : CheckRPONumbers(order, schedule.BasicBlockCount(), true);
428 64 : CheckLoop(order, loop1->nodes, loop1->count);
429 : }
430 : }
431 1 : }
432 :
433 15444 : TEST_F(SchedulerRPOTest, LoopOutedges1) {
434 : int size = 8;
435 17 : for (int i = 0; i < size; i++) {
436 136 : for (int j = 0; j < size; j++) {
437 64 : Schedule schedule(zone());
438 : BasicBlock* A = schedule.start();
439 64 : BasicBlock* D = schedule.NewBasicBlock();
440 : BasicBlock* E = schedule.end();
441 :
442 64 : std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size));
443 : schedule.AddSuccessorForTesting(A, loop1->header());
444 : schedule.AddSuccessorForTesting(loop1->last(), E);
445 :
446 64 : schedule.AddSuccessorForTesting(loop1->nodes[i], loop1->header());
447 64 : schedule.AddSuccessorForTesting(loop1->nodes[j], D);
448 : schedule.AddSuccessorForTesting(D, E);
449 :
450 64 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
451 64 : CheckRPONumbers(order, schedule.BasicBlockCount(), true);
452 64 : CheckLoop(order, loop1->nodes, loop1->count);
453 : }
454 : }
455 1 : }
456 :
457 15444 : TEST_F(SchedulerRPOTest, LoopOutedges2) {
458 : int size = 8;
459 17 : for (int i = 0; i < size; i++) {
460 8 : Schedule schedule(zone());
461 : BasicBlock* A = schedule.start();
462 : BasicBlock* E = schedule.end();
463 :
464 8 : std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size));
465 : schedule.AddSuccessorForTesting(A, loop1->header());
466 : schedule.AddSuccessorForTesting(loop1->last(), E);
467 :
468 136 : for (int j = 0; j < size; j++) {
469 64 : BasicBlock* O = schedule.NewBasicBlock();
470 64 : schedule.AddSuccessorForTesting(loop1->nodes[j], O);
471 : schedule.AddSuccessorForTesting(O, E);
472 : }
473 :
474 8 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
475 8 : CheckRPONumbers(order, schedule.BasicBlockCount(), true);
476 8 : CheckLoop(order, loop1->nodes, loop1->count);
477 : }
478 1 : }
479 :
480 12356 : TEST_F(SchedulerRPOTest, LoopOutloops1) {
481 : int size = 8;
482 17 : for (int i = 0; i < size; i++) {
483 8 : Schedule schedule(zone());
484 : BasicBlock* A = schedule.start();
485 : BasicBlock* E = schedule.end();
486 8 : std::unique_ptr<TestLoop> loop1(CreateLoop(&schedule, size));
487 : schedule.AddSuccessorForTesting(A, loop1->header());
488 : schedule.AddSuccessorForTesting(loop1->last(), E);
489 :
490 8 : TestLoop** loopN = new TestLoop*[size];
491 136 : for (int j = 0; j < size; j++) {
492 64 : loopN[j] = CreateLoop(&schedule, 2);
493 64 : schedule.AddSuccessorForTesting(loop1->nodes[j], loopN[j]->header());
494 64 : schedule.AddSuccessorForTesting(loopN[j]->last(), E);
495 : }
496 :
497 8 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
498 8 : CheckRPONumbers(order, schedule.BasicBlockCount(), true);
499 8 : CheckLoop(order, loop1->nodes, loop1->count);
500 :
501 136 : for (int j = 0; j < size; j++) {
502 64 : CheckLoop(order, loopN[j]->nodes, loopN[j]->count);
503 128 : delete loopN[j];
504 : }
505 8 : delete[] loopN;
506 : }
507 1 : }
508 :
509 15444 : TEST_F(SchedulerRPOTest, LoopMultibackedge) {
510 1 : Schedule schedule(zone());
511 :
512 : BasicBlock* A = schedule.start();
513 1 : BasicBlock* B = schedule.NewBasicBlock();
514 1 : BasicBlock* C = schedule.NewBasicBlock();
515 1 : BasicBlock* D = schedule.NewBasicBlock();
516 1 : 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 1 : BasicBlockVector* order = Scheduler::ComputeSpecialRPO(zone(), &schedule);
527 1 : CheckRPONumbers(order, 5, true);
528 :
529 1 : BasicBlock* loop1[] = {B, C, D, E};
530 1 : CheckLoop(order, loop1, 4);
531 1 : }
532 :
533 : } // namespace compiler
534 : } // namespace internal
535 9264 : } // namespace v8
|
