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/scheduler.h"
6 : #include "src/compiler/access-builder.h"
7 : #include "src/compiler/common-operator.h"
8 : #include "src/compiler/compiler-source-position-table.h"
9 : #include "src/compiler/graph-visualizer.h"
10 : #include "src/compiler/graph.h"
11 : #include "src/compiler/js-operator.h"
12 : #include "src/compiler/node-origin-table.h"
13 : #include "src/compiler/node.h"
14 : #include "src/compiler/opcodes.h"
15 : #include "src/compiler/operator.h"
16 : #include "src/compiler/schedule.h"
17 : #include "src/compiler/simplified-operator.h"
18 : #include "src/compiler/verifier.h"
19 : #include "test/unittests/compiler/compiler-test-utils.h"
20 : #include "test/unittests/test-utils.h"
21 : #include "testing/gmock/include/gmock/gmock.h"
22 :
23 : using testing::AnyOf;
24 :
25 : namespace v8 {
26 : namespace internal {
27 : namespace compiler {
28 :
29 42 : class SchedulerTest : public TestWithIsolateAndZone {
30 : public:
31 21 : SchedulerTest()
32 42 : : graph_(zone()), common_(zone()), simplified_(zone()), js_(zone()) {}
33 :
34 19 : Schedule* ComputeAndVerifySchedule(size_t expected) {
35 19 : if (FLAG_trace_turbo) {
36 0 : SourcePositionTable table(graph());
37 0 : NodeOriginTable table2(graph());
38 0 : StdoutStream{} << AsJSON(*graph(), &table, &table2);
39 : }
40 :
41 : Schedule* schedule =
42 19 : Scheduler::ComputeSchedule(zone(), graph(), Scheduler::kSplitNodes);
43 :
44 19 : if (FLAG_trace_turbo_scheduler) {
45 0 : StdoutStream{} << *schedule << std::endl;
46 : }
47 19 : ScheduleVerifier::Run(schedule);
48 38 : EXPECT_EQ(expected, GetScheduledNodeCount(schedule));
49 19 : return schedule;
50 : }
51 :
52 : size_t GetScheduledNodeCount(const Schedule* schedule) {
53 : size_t node_count = 0;
54 148 : for (auto block : *schedule->rpo_order()) {
55 129 : node_count += block->NodeCount();
56 129 : if (block->control() != BasicBlock::kNone) ++node_count;
57 : }
58 : return node_count;
59 : }
60 :
61 40 : Graph* graph() { return &graph_; }
62 21 : CommonOperatorBuilder* common() { return &common_; }
63 1 : SimplifiedOperatorBuilder* simplified() { return &simplified_; }
64 : JSOperatorBuilder* js() { return &js_; }
65 :
66 : private:
67 : Graph graph_;
68 : CommonOperatorBuilder common_;
69 : SimplifiedOperatorBuilder simplified_;
70 : JSOperatorBuilder js_;
71 : };
72 :
73 :
74 : namespace {
75 :
76 6166 : const Operator kHeapConstant(IrOpcode::kHeapConstant, Operator::kPure,
77 3083 : "HeapConstant", 0, 0, 0, 1, 0, 0);
78 6166 : const Operator kIntAdd(IrOpcode::kInt32Add, Operator::kPure, "Int32Add", 2, 0,
79 3083 : 0, 1, 0, 0);
80 6166 : const Operator kMockCall(IrOpcode::kCall, Operator::kNoProperties, "MockCall",
81 3083 : 0, 0, 1, 1, 1, 2);
82 6166 : const Operator kMockTailCall(IrOpcode::kTailCall, Operator::kNoProperties,
83 3083 : "MockTailCall", 1, 1, 1, 0, 0, 1);
84 :
85 : } // namespace
86 :
87 :
88 15419 : TEST_F(SchedulerTest, BuildScheduleEmpty) {
89 1 : graph()->SetStart(graph()->NewNode(common()->Start(0)));
90 1 : graph()->SetEnd(graph()->NewNode(common()->End(1), graph()->start()));
91 1 : USE(Scheduler::ComputeSchedule(zone(), graph(), Scheduler::kNoFlags));
92 1 : }
93 :
94 :
95 15419 : TEST_F(SchedulerTest, BuildScheduleOneParameter) {
96 1 : graph()->SetStart(graph()->NewNode(common()->Start(0)));
97 :
98 1 : Node* p1 = graph()->NewNode(common()->Parameter(0), graph()->start());
99 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
100 1 : Node* ret = graph()->NewNode(common()->Return(), zero, p1, graph()->start(),
101 : graph()->start());
102 :
103 1 : graph()->SetEnd(graph()->NewNode(common()->End(1), ret));
104 :
105 1 : USE(Scheduler::ComputeSchedule(zone(), graph(), Scheduler::kNoFlags));
106 1 : }
107 :
108 :
109 : namespace {
110 :
111 7 : Node* CreateDiamond(Graph* graph, CommonOperatorBuilder* common, Node* cond) {
112 7 : Node* tv = graph->NewNode(common->Int32Constant(6));
113 7 : Node* fv = graph->NewNode(common->Int32Constant(7));
114 7 : Node* br = graph->NewNode(common->Branch(), cond, graph->start());
115 7 : Node* t = graph->NewNode(common->IfTrue(), br);
116 7 : Node* f = graph->NewNode(common->IfFalse(), br);
117 7 : Node* m = graph->NewNode(common->Merge(2), t, f);
118 : Node* phi =
119 7 : graph->NewNode(common->Phi(MachineRepresentation::kTagged, 2), tv, fv, m);
120 7 : return phi;
121 : }
122 :
123 : } // namespace
124 :
125 :
126 15419 : TARGET_TEST_F(SchedulerTest, FloatingDiamond1) {
127 1 : Node* start = graph()->NewNode(common()->Start(1));
128 : graph()->SetStart(start);
129 :
130 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
131 1 : Node* d1 = CreateDiamond(graph(), common(), p0);
132 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
133 1 : Node* ret = graph()->NewNode(common()->Return(), zero, d1, start, start);
134 1 : Node* end = graph()->NewNode(common()->End(1), ret);
135 :
136 : graph()->SetEnd(end);
137 :
138 1 : ComputeAndVerifySchedule(14);
139 1 : }
140 :
141 15419 : TARGET_TEST_F(SchedulerTest, FloatingDeadDiamond1) {
142 1 : Node* start = graph()->NewNode(common()->Start(1));
143 : graph()->SetStart(start);
144 :
145 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
146 1 : Node* d1 = CreateDiamond(graph(), common(), p0);
147 : USE(d1);
148 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
149 1 : Node* ret = graph()->NewNode(common()->Return(), zero, p0, start, start);
150 1 : Node* end = graph()->NewNode(common()->End(1), ret);
151 :
152 : graph()->SetEnd(end);
153 :
154 1 : ComputeAndVerifySchedule(5);
155 1 : }
156 :
157 15419 : TARGET_TEST_F(SchedulerTest, FloatingDeadDiamond2) {
158 : Graph* g = graph();
159 1 : Node* start = g->NewNode(common()->Start(1));
160 : g->SetStart(start);
161 :
162 1 : Node* n1 = g->NewNode(common()->Parameter(1), start);
163 :
164 1 : Node* n2 = g->NewNode(common()->Branch(), n1, start);
165 1 : Node* n3 = g->NewNode(common()->IfTrue(), n2);
166 1 : Node* n4 = g->NewNode(common()->IfFalse(), n2);
167 1 : Node* n5 = g->NewNode(common()->Int32Constant(-100));
168 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
169 1 : Node* n6 = g->NewNode(common()->Return(), zero, n5, start, n4);
170 1 : Node* n7 = g->NewNode(common()->Int32Constant(0));
171 1 : Node* n8 = g->NewNode(common()->Return(), zero, n7, start, n3);
172 1 : Node* n9 = g->NewNode(common()->End(2), n6, n8);
173 :
174 : // Dead nodes
175 1 : Node* n10 = g->NewNode(common()->Branch(), n1, n3);
176 1 : Node* n11 = g->NewNode(common()->IfTrue(), n10);
177 1 : Node* n12 = g->NewNode(common()->IfFalse(), n10);
178 1 : Node* n13 = g->NewNode(common()->Merge(2), n11, n12);
179 : Node* n14 =
180 1 : g->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), n1, n7, n13);
181 :
182 : USE(n14);
183 :
184 : g->SetEnd(n9);
185 :
186 1 : ComputeAndVerifySchedule(11);
187 1 : }
188 :
189 15419 : TARGET_TEST_F(SchedulerTest, FloatingDiamond2) {
190 1 : Node* start = graph()->NewNode(common()->Start(2));
191 : graph()->SetStart(start);
192 :
193 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
194 1 : Node* p1 = graph()->NewNode(common()->Parameter(1), start);
195 1 : Node* d1 = CreateDiamond(graph(), common(), p0);
196 1 : Node* d2 = CreateDiamond(graph(), common(), p1);
197 : Node* add = graph()->NewNode(&kIntAdd, d1, d2);
198 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
199 1 : Node* ret = graph()->NewNode(common()->Return(), zero, add, start, start);
200 1 : Node* end = graph()->NewNode(common()->End(1), ret);
201 :
202 : graph()->SetEnd(end);
203 :
204 1 : ComputeAndVerifySchedule(25);
205 1 : }
206 :
207 :
208 15419 : TARGET_TEST_F(SchedulerTest, FloatingDiamond3) {
209 1 : Node* start = graph()->NewNode(common()->Start(2));
210 : graph()->SetStart(start);
211 :
212 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
213 1 : Node* p1 = graph()->NewNode(common()->Parameter(1), start);
214 1 : Node* d1 = CreateDiamond(graph(), common(), p0);
215 1 : Node* d2 = CreateDiamond(graph(), common(), p1);
216 : Node* add = graph()->NewNode(&kIntAdd, d1, d2);
217 1 : Node* d3 = CreateDiamond(graph(), common(), add);
218 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
219 1 : Node* ret = graph()->NewNode(common()->Return(), zero, d3, start, start);
220 1 : Node* end = graph()->NewNode(common()->End(1), ret);
221 :
222 : graph()->SetEnd(end);
223 :
224 1 : ComputeAndVerifySchedule(34);
225 1 : }
226 :
227 :
228 15419 : TARGET_TEST_F(SchedulerTest, NestedFloatingDiamonds) {
229 1 : Node* start = graph()->NewNode(common()->Start(2));
230 : graph()->SetStart(start);
231 :
232 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
233 :
234 1 : Node* fv = graph()->NewNode(common()->Int32Constant(7));
235 1 : Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start());
236 1 : Node* t = graph()->NewNode(common()->IfTrue(), br);
237 1 : Node* f = graph()->NewNode(common()->IfFalse(), br);
238 :
239 1 : Node* map = graph()->NewNode(
240 2 : simplified()->LoadElement(AccessBuilder::ForFixedArrayElement()), p0, p0,
241 : start, f);
242 1 : Node* br1 = graph()->NewNode(common()->Branch(), map, graph()->start());
243 1 : Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
244 1 : Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
245 1 : Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1);
246 1 : Node* ttrue = graph()->NewNode(common()->Int32Constant(1));
247 1 : Node* ffalse = graph()->NewNode(common()->Int32Constant(0));
248 1 : Node* phi1 = graph()->NewNode(
249 : common()->Phi(MachineRepresentation::kTagged, 2), ttrue, ffalse, m1);
250 :
251 :
252 1 : Node* m = graph()->NewNode(common()->Merge(2), t, f);
253 1 : Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
254 : fv, phi1, m);
255 1 : Node* ephi1 = graph()->NewNode(common()->EffectPhi(2), start, map, m);
256 :
257 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
258 1 : Node* ret = graph()->NewNode(common()->Return(), zero, phi, ephi1, start);
259 1 : Node* end = graph()->NewNode(common()->End(1), ret);
260 :
261 : graph()->SetEnd(end);
262 :
263 1 : ComputeAndVerifySchedule(24);
264 1 : }
265 :
266 :
267 15419 : TARGET_TEST_F(SchedulerTest, NestedFloatingDiamondWithChain) {
268 1 : Node* start = graph()->NewNode(common()->Start(2));
269 : graph()->SetStart(start);
270 :
271 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
272 1 : Node* p1 = graph()->NewNode(common()->Parameter(1), start);
273 1 : Node* c = graph()->NewNode(common()->Int32Constant(7));
274 :
275 1 : Node* brA1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
276 1 : Node* tA1 = graph()->NewNode(common()->IfTrue(), brA1);
277 1 : Node* fA1 = graph()->NewNode(common()->IfFalse(), brA1);
278 1 : Node* mA1 = graph()->NewNode(common()->Merge(2), tA1, fA1);
279 1 : Node* phiA1 = graph()->NewNode(
280 : common()->Phi(MachineRepresentation::kTagged, 2), p0, p1, mA1);
281 :
282 1 : Node* brB1 = graph()->NewNode(common()->Branch(), p1, graph()->start());
283 1 : Node* tB1 = graph()->NewNode(common()->IfTrue(), brB1);
284 1 : Node* fB1 = graph()->NewNode(common()->IfFalse(), brB1);
285 1 : Node* mB1 = graph()->NewNode(common()->Merge(2), tB1, fB1);
286 1 : Node* phiB1 = graph()->NewNode(
287 : common()->Phi(MachineRepresentation::kTagged, 2), p0, p1, mB1);
288 :
289 1 : Node* brA2 = graph()->NewNode(common()->Branch(), phiB1, mA1);
290 1 : Node* tA2 = graph()->NewNode(common()->IfTrue(), brA2);
291 1 : Node* fA2 = graph()->NewNode(common()->IfFalse(), brA2);
292 1 : Node* mA2 = graph()->NewNode(common()->Merge(2), tA2, fA2);
293 1 : Node* phiA2 = graph()->NewNode(
294 : common()->Phi(MachineRepresentation::kTagged, 2), phiB1, c, mA2);
295 :
296 1 : Node* brB2 = graph()->NewNode(common()->Branch(), phiA1, mB1);
297 1 : Node* tB2 = graph()->NewNode(common()->IfTrue(), brB2);
298 1 : Node* fB2 = graph()->NewNode(common()->IfFalse(), brB2);
299 1 : Node* mB2 = graph()->NewNode(common()->Merge(2), tB2, fB2);
300 1 : Node* phiB2 = graph()->NewNode(
301 : common()->Phi(MachineRepresentation::kTagged, 2), phiA1, c, mB2);
302 :
303 : Node* add = graph()->NewNode(&kIntAdd, phiA2, phiB2);
304 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
305 1 : Node* ret = graph()->NewNode(common()->Return(), zero, add, start, start);
306 1 : Node* end = graph()->NewNode(common()->End(1), ret);
307 :
308 : graph()->SetEnd(end);
309 :
310 1 : ComputeAndVerifySchedule(37);
311 1 : }
312 :
313 :
314 15419 : TARGET_TEST_F(SchedulerTest, NestedFloatingDiamondWithLoop) {
315 1 : Node* start = graph()->NewNode(common()->Start(2));
316 : graph()->SetStart(start);
317 :
318 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
319 :
320 1 : Node* fv = graph()->NewNode(common()->Int32Constant(7));
321 1 : Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start());
322 1 : Node* t = graph()->NewNode(common()->IfTrue(), br);
323 1 : Node* f = graph()->NewNode(common()->IfFalse(), br);
324 :
325 1 : Node* loop = graph()->NewNode(common()->Loop(2), f, start);
326 1 : Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
327 : p0, p0, loop);
328 :
329 : Node* add = graph()->NewNode(&kIntAdd, ind, fv);
330 1 : Node* br1 = graph()->NewNode(common()->Branch(), add, loop);
331 1 : Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
332 1 : Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
333 :
334 1 : loop->ReplaceInput(1, t1); // close loop.
335 1 : ind->ReplaceInput(1, ind); // close induction variable.
336 :
337 1 : Node* m = graph()->NewNode(common()->Merge(2), t, f1);
338 1 : Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
339 : fv, ind, m);
340 :
341 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
342 1 : Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, start);
343 1 : Node* end = graph()->NewNode(common()->End(1), ret);
344 :
345 : graph()->SetEnd(end);
346 :
347 1 : ComputeAndVerifySchedule(21);
348 1 : }
349 :
350 :
351 15419 : TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond1) {
352 1 : Node* start = graph()->NewNode(common()->Start(2));
353 : graph()->SetStart(start);
354 :
355 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
356 :
357 1 : Node* c = graph()->NewNode(common()->Int32Constant(7));
358 1 : Node* loop = graph()->NewNode(common()->Loop(2), start, start);
359 1 : Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
360 : p0, p0, loop);
361 : Node* add = graph()->NewNode(&kIntAdd, ind, c);
362 :
363 1 : Node* br = graph()->NewNode(common()->Branch(), add, loop);
364 1 : Node* t = graph()->NewNode(common()->IfTrue(), br);
365 1 : Node* f = graph()->NewNode(common()->IfFalse(), br);
366 :
367 1 : Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
368 1 : Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
369 1 : Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
370 1 : Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1);
371 1 : Node* phi1 = graph()->NewNode(
372 : common()->Phi(MachineRepresentation::kTagged, 2), add, p0, m1);
373 :
374 1 : loop->ReplaceInput(1, t); // close loop.
375 1 : ind->ReplaceInput(1, phi1); // close induction variable.
376 :
377 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
378 1 : Node* ret = graph()->NewNode(common()->Return(), zero, ind, start, f);
379 1 : Node* end = graph()->NewNode(common()->End(2), ret, f);
380 :
381 : graph()->SetEnd(end);
382 :
383 1 : ComputeAndVerifySchedule(21);
384 1 : }
385 :
386 :
387 15419 : TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond2) {
388 1 : Node* start = graph()->NewNode(common()->Start(2));
389 : graph()->SetStart(start);
390 :
391 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
392 :
393 1 : Node* c = graph()->NewNode(common()->Int32Constant(7));
394 1 : Node* loop = graph()->NewNode(common()->Loop(2), start, start);
395 1 : Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
396 : p0, p0, loop);
397 :
398 1 : Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
399 1 : Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
400 1 : Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
401 1 : Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1);
402 1 : Node* phi1 = graph()->NewNode(
403 : common()->Phi(MachineRepresentation::kTagged, 2), c, ind, m1);
404 :
405 : Node* add = graph()->NewNode(&kIntAdd, ind, phi1);
406 :
407 1 : Node* br = graph()->NewNode(common()->Branch(), add, loop);
408 1 : Node* t = graph()->NewNode(common()->IfTrue(), br);
409 1 : Node* f = graph()->NewNode(common()->IfFalse(), br);
410 :
411 1 : loop->ReplaceInput(1, t); // close loop.
412 1 : ind->ReplaceInput(1, add); // close induction variable.
413 :
414 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
415 1 : Node* ret = graph()->NewNode(common()->Return(), zero, ind, start, f);
416 1 : Node* end = graph()->NewNode(common()->End(2), ret, f);
417 :
418 : graph()->SetEnd(end);
419 :
420 1 : ComputeAndVerifySchedule(21);
421 1 : }
422 :
423 :
424 15419 : TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond3) {
425 1 : Node* start = graph()->NewNode(common()->Start(2));
426 : graph()->SetStart(start);
427 :
428 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
429 :
430 1 : Node* c = graph()->NewNode(common()->Int32Constant(7));
431 1 : Node* loop = graph()->NewNode(common()->Loop(2), start, start);
432 1 : Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
433 : p0, p0, loop);
434 :
435 1 : Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
436 1 : Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
437 1 : Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
438 :
439 1 : Node* loop1 = graph()->NewNode(common()->Loop(2), t1, start);
440 1 : Node* ind1 = graph()->NewNode(
441 : common()->Phi(MachineRepresentation::kTagged, 2), p0, p0, loop);
442 :
443 : Node* add1 = graph()->NewNode(&kIntAdd, ind1, c);
444 1 : Node* br2 = graph()->NewNode(common()->Branch(), add1, loop1);
445 1 : Node* t2 = graph()->NewNode(common()->IfTrue(), br2);
446 1 : Node* f2 = graph()->NewNode(common()->IfFalse(), br2);
447 :
448 1 : loop1->ReplaceInput(1, t2); // close inner loop.
449 1 : ind1->ReplaceInput(1, ind1); // close inner induction variable.
450 :
451 1 : Node* m1 = graph()->NewNode(common()->Merge(2), f1, f2);
452 1 : Node* phi1 = graph()->NewNode(
453 : common()->Phi(MachineRepresentation::kTagged, 2), c, ind1, m1);
454 :
455 : Node* add = graph()->NewNode(&kIntAdd, ind, phi1);
456 :
457 1 : Node* br = graph()->NewNode(common()->Branch(), add, loop);
458 1 : Node* t = graph()->NewNode(common()->IfTrue(), br);
459 1 : Node* f = graph()->NewNode(common()->IfFalse(), br);
460 :
461 1 : loop->ReplaceInput(1, t); // close loop.
462 1 : ind->ReplaceInput(1, add); // close induction variable.
463 :
464 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
465 1 : Node* ret = graph()->NewNode(common()->Return(), zero, ind, start, f);
466 1 : Node* end = graph()->NewNode(common()->End(2), ret, f);
467 :
468 : graph()->SetEnd(end);
469 :
470 1 : ComputeAndVerifySchedule(29);
471 1 : }
472 :
473 :
474 15419 : TARGET_TEST_F(SchedulerTest, PhisPushedDownToDifferentBranches) {
475 1 : Node* start = graph()->NewNode(common()->Start(2));
476 : graph()->SetStart(start);
477 :
478 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
479 1 : Node* p1 = graph()->NewNode(common()->Parameter(1), start);
480 :
481 1 : Node* v1 = graph()->NewNode(common()->Int32Constant(1));
482 1 : Node* v2 = graph()->NewNode(common()->Int32Constant(2));
483 1 : Node* v3 = graph()->NewNode(common()->Int32Constant(3));
484 1 : Node* v4 = graph()->NewNode(common()->Int32Constant(4));
485 1 : Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start());
486 1 : Node* t = graph()->NewNode(common()->IfTrue(), br);
487 1 : Node* f = graph()->NewNode(common()->IfFalse(), br);
488 1 : Node* m = graph()->NewNode(common()->Merge(2), t, f);
489 1 : Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
490 : v1, v2, m);
491 1 : Node* phi2 = graph()->NewNode(
492 : common()->Phi(MachineRepresentation::kTagged, 2), v3, v4, m);
493 :
494 1 : Node* br2 = graph()->NewNode(common()->Branch(), p1, graph()->start());
495 1 : Node* t2 = graph()->NewNode(common()->IfTrue(), br2);
496 1 : Node* f2 = graph()->NewNode(common()->IfFalse(), br2);
497 1 : Node* m2 = graph()->NewNode(common()->Merge(2), t2, f2);
498 1 : Node* phi3 = graph()->NewNode(
499 : common()->Phi(MachineRepresentation::kTagged, 2), phi, phi2, m2);
500 :
501 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
502 1 : Node* ret = graph()->NewNode(common()->Return(), zero, phi3, start, start);
503 1 : Node* end = graph()->NewNode(common()->End(1), ret);
504 :
505 : graph()->SetEnd(end);
506 :
507 1 : ComputeAndVerifySchedule(25);
508 1 : }
509 :
510 :
511 15419 : TARGET_TEST_F(SchedulerTest, BranchHintTrue) {
512 1 : Node* start = graph()->NewNode(common()->Start(1));
513 : graph()->SetStart(start);
514 :
515 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
516 1 : Node* tv = graph()->NewNode(common()->Int32Constant(6));
517 1 : Node* fv = graph()->NewNode(common()->Int32Constant(7));
518 1 : Node* br = graph()->NewNode(common()->Branch(BranchHint::kTrue), p0, start);
519 1 : Node* t = graph()->NewNode(common()->IfTrue(), br);
520 1 : Node* f = graph()->NewNode(common()->IfFalse(), br);
521 1 : Node* m = graph()->NewNode(common()->Merge(2), t, f);
522 1 : Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
523 : tv, fv, m);
524 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
525 1 : Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, start);
526 1 : Node* end = graph()->NewNode(common()->End(1), ret);
527 :
528 : graph()->SetEnd(end);
529 :
530 1 : Schedule* schedule = ComputeAndVerifySchedule(14);
531 : // Make sure the false block is marked as deferred.
532 2 : EXPECT_FALSE(schedule->block(t)->deferred());
533 2 : EXPECT_TRUE(schedule->block(f)->deferred());
534 1 : }
535 :
536 :
537 15419 : TARGET_TEST_F(SchedulerTest, BranchHintFalse) {
538 1 : Node* start = graph()->NewNode(common()->Start(1));
539 : graph()->SetStart(start);
540 :
541 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
542 1 : Node* tv = graph()->NewNode(common()->Int32Constant(6));
543 1 : Node* fv = graph()->NewNode(common()->Int32Constant(7));
544 1 : Node* br = graph()->NewNode(common()->Branch(BranchHint::kFalse), p0, start);
545 1 : Node* t = graph()->NewNode(common()->IfTrue(), br);
546 1 : Node* f = graph()->NewNode(common()->IfFalse(), br);
547 1 : Node* m = graph()->NewNode(common()->Merge(2), t, f);
548 1 : Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
549 : tv, fv, m);
550 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
551 1 : Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, start);
552 1 : Node* end = graph()->NewNode(common()->End(1), ret);
553 :
554 : graph()->SetEnd(end);
555 :
556 1 : Schedule* schedule = ComputeAndVerifySchedule(14);
557 : // Make sure the true block is marked as deferred.
558 2 : EXPECT_TRUE(schedule->block(t)->deferred());
559 2 : EXPECT_FALSE(schedule->block(f)->deferred());
560 1 : }
561 :
562 :
563 15419 : TARGET_TEST_F(SchedulerTest, CallException) {
564 1 : Node* start = graph()->NewNode(common()->Start(1));
565 : graph()->SetStart(start);
566 :
567 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
568 : Node* c1 = graph()->NewNode(&kMockCall, start);
569 1 : Node* ok1 = graph()->NewNode(common()->IfSuccess(), c1);
570 1 : Node* ex1 = graph()->NewNode(common()->IfException(), c1, c1);
571 : Node* c2 = graph()->NewNode(&kMockCall, ok1);
572 1 : Node* ok2 = graph()->NewNode(common()->IfSuccess(), c2);
573 1 : Node* ex2 = graph()->NewNode(common()->IfException(), c2, c2);
574 1 : Node* hdl = graph()->NewNode(common()->Merge(2), ex1, ex2);
575 1 : Node* m = graph()->NewNode(common()->Merge(2), ok2, hdl);
576 1 : Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
577 : c2, p0, m);
578 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
579 1 : Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, m);
580 1 : Node* end = graph()->NewNode(common()->End(1), ret);
581 :
582 : graph()->SetEnd(end);
583 :
584 1 : Schedule* schedule = ComputeAndVerifySchedule(18);
585 : // Make sure the exception blocks as well as the handler are deferred.
586 2 : EXPECT_TRUE(schedule->block(ex1)->deferred());
587 2 : EXPECT_TRUE(schedule->block(ex2)->deferred());
588 2 : EXPECT_TRUE(schedule->block(hdl)->deferred());
589 2 : EXPECT_FALSE(schedule->block(m)->deferred());
590 1 : }
591 :
592 :
593 15419 : TARGET_TEST_F(SchedulerTest, TailCall) {
594 1 : Node* start = graph()->NewNode(common()->Start(1));
595 : graph()->SetStart(start);
596 :
597 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
598 : Node* call = graph()->NewNode(&kMockTailCall, p0, start, start);
599 1 : Node* end = graph()->NewNode(common()->End(1), call);
600 :
601 : graph()->SetEnd(end);
602 :
603 1 : ComputeAndVerifySchedule(4);
604 1 : }
605 :
606 :
607 15419 : TARGET_TEST_F(SchedulerTest, Switch) {
608 1 : Node* start = graph()->NewNode(common()->Start(1));
609 : graph()->SetStart(start);
610 :
611 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
612 1 : Node* sw = graph()->NewNode(common()->Switch(3), p0, start);
613 1 : Node* c0 = graph()->NewNode(common()->IfValue(0), sw);
614 1 : Node* v0 = graph()->NewNode(common()->Int32Constant(11));
615 1 : Node* c1 = graph()->NewNode(common()->IfValue(1), sw);
616 1 : Node* v1 = graph()->NewNode(common()->Int32Constant(22));
617 1 : Node* d = graph()->NewNode(common()->IfDefault(), sw);
618 1 : Node* vd = graph()->NewNode(common()->Int32Constant(33));
619 1 : Node* m = graph()->NewNode(common()->Merge(3), c0, c1, d);
620 1 : Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 3),
621 : v0, v1, vd, m);
622 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
623 1 : Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, m);
624 1 : Node* end = graph()->NewNode(common()->End(1), ret);
625 :
626 : graph()->SetEnd(end);
627 :
628 1 : ComputeAndVerifySchedule(17);
629 1 : }
630 :
631 :
632 15419 : TARGET_TEST_F(SchedulerTest, FloatingSwitch) {
633 1 : Node* start = graph()->NewNode(common()->Start(1));
634 : graph()->SetStart(start);
635 :
636 1 : Node* p0 = graph()->NewNode(common()->Parameter(0), start);
637 1 : Node* sw = graph()->NewNode(common()->Switch(3), p0, start);
638 1 : Node* c0 = graph()->NewNode(common()->IfValue(0), sw);
639 1 : Node* v0 = graph()->NewNode(common()->Int32Constant(11));
640 1 : Node* c1 = graph()->NewNode(common()->IfValue(1), sw);
641 1 : Node* v1 = graph()->NewNode(common()->Int32Constant(22));
642 1 : Node* d = graph()->NewNode(common()->IfDefault(), sw);
643 1 : Node* vd = graph()->NewNode(common()->Int32Constant(33));
644 1 : Node* m = graph()->NewNode(common()->Merge(3), c0, c1, d);
645 1 : Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 3),
646 : v0, v1, vd, m);
647 1 : Node* zero = graph()->NewNode(common()->Int32Constant(0));
648 1 : Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, start);
649 1 : Node* end = graph()->NewNode(common()->End(1), ret);
650 :
651 : graph()->SetEnd(end);
652 :
653 1 : ComputeAndVerifySchedule(17);
654 1 : }
655 :
656 :
657 15419 : TARGET_TEST_F(SchedulerTest, Terminate) {
658 1 : Node* start = graph()->NewNode(common()->Start(1));
659 : graph()->SetStart(start);
660 :
661 1 : Node* loop = graph()->NewNode(common()->Loop(2), start, start);
662 1 : loop->ReplaceInput(1, loop); // self loop, NTL.
663 :
664 1 : Node* effect = graph()->NewNode(common()->EffectPhi(2), start, start, loop);
665 1 : effect->ReplaceInput(1, effect); // self loop.
666 :
667 1 : Node* terminate = graph()->NewNode(common()->Terminate(), effect, loop);
668 1 : Node* end = graph()->NewNode(common()->End(1), terminate);
669 : graph()->SetEnd(end);
670 :
671 1 : Schedule* schedule = ComputeAndVerifySchedule(6);
672 1 : BasicBlock* block = schedule->block(loop);
673 2 : EXPECT_EQ(block, schedule->block(effect));
674 1 : EXPECT_GE(block->rpo_number(), 0);
675 1 : }
676 :
677 : } // namespace compiler
678 : } // namespace internal
679 9249 : } // namespace v8
|
