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