scheduler-unittest.cc 25.4 KB
Newer Older
1
// Copyright 2015 the V8 project authors. All rights reserved.
2 3 4
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

5
#include "src/compiler/scheduler.h"
6
#include "src/codegen/tick-counter.h"
7 8
#include "src/compiler/access-builder.h"
#include "src/compiler/common-operator.h"
9
#include "src/compiler/compiler-source-position-table.h"
10
#include "src/compiler/graph-visualizer.h"
11
#include "src/compiler/graph.h"
12
#include "src/compiler/js-operator.h"
13
#include "src/compiler/node-origin-table.h"
14 15 16
#include "src/compiler/node.h"
#include "src/compiler/opcodes.h"
#include "src/compiler/operator.h"
17
#include "src/compiler/schedule.h"
18 19
#include "src/compiler/simplified-operator.h"
#include "src/compiler/verifier.h"
20
#include "test/unittests/compiler/compiler-test-utils.h"
21
#include "test/unittests/test-utils.h"
22 23 24
#include "testing/gmock/include/gmock/gmock.h"

using testing::AnyOf;
25

26 27 28
namespace v8 {
namespace internal {
namespace compiler {
29

30
class SchedulerTest : public TestWithIsolateAndZone {
31 32
 public:
  SchedulerTest()
33 34 35 36 37
      : TestWithIsolateAndZone(kCompressGraphZone),
        graph_(zone()),
        common_(zone()),
        simplified_(zone()),
        js_(zone()) {}
38

39
  Schedule* ComputeAndVerifySchedule(size_t expected) {
40
    if (FLAG_trace_turbo) {
41
      SourcePositionTable table(graph());
42
      NodeOriginTable table2(graph());
43
      StdoutStream{} << AsJSON(*graph(), &table, &table2);
44 45
    }

46
    Schedule* schedule = Scheduler::ComputeSchedule(
47
        zone(), graph(), Scheduler::kSplitNodes, tick_counter(), nullptr);
48 49

    if (FLAG_trace_turbo_scheduler) {
50
      StdoutStream{} << *schedule << std::endl;
51 52
    }
    ScheduleVerifier::Run(schedule);
53
    EXPECT_EQ(expected, GetScheduledNodeCount(schedule));
54 55 56
    return schedule;
  }

57
  size_t GetScheduledNodeCount(const Schedule* schedule) {
58 59 60 61 62
    size_t node_count = 0;
    for (auto block : *schedule->rpo_order()) {
      node_count += block->NodeCount();
      if (block->control() != BasicBlock::kNone) ++node_count;
    }
63
    return node_count;
64 65 66 67 68 69
  }

  Graph* graph() { return &graph_; }
  CommonOperatorBuilder* common() { return &common_; }
  SimplifiedOperatorBuilder* simplified() { return &simplified_; }
  JSOperatorBuilder* js() { return &js_; }
70
  TickCounter* tick_counter() { return &tick_counter_; }
71 72

 private:
73
  TickCounter tick_counter_;
74 75 76 77 78 79
  Graph graph_;
  CommonOperatorBuilder common_;
  SimplifiedOperatorBuilder simplified_;
  JSOperatorBuilder js_;
};

80 81 82

namespace {

83 84
const Operator kHeapConstant(IrOpcode::kHeapConstant, Operator::kPure,
                             "HeapConstant", 0, 0, 0, 1, 0, 0);
85 86
const Operator kIntAdd(IrOpcode::kInt32Add, Operator::kPure, "Int32Add", 2, 0,
                       0, 1, 0, 0);
87
const Operator kMockCall(IrOpcode::kCall, Operator::kNoProperties, "MockCall",
88
                         0, 0, 1, 1, 1, 2);
89 90
const Operator kMockTailCall(IrOpcode::kTailCall, Operator::kNoProperties,
                             "MockTailCall", 1, 1, 1, 0, 0, 1);
91 92 93 94

}  // namespace


95 96
TEST_F(SchedulerTest, BuildScheduleEmpty) {
  graph()->SetStart(graph()->NewNode(common()->Start(0)));
97
  graph()->SetEnd(graph()->NewNode(common()->End(1), graph()->start()));
98
  USE(Scheduler::ComputeSchedule(zone(), graph(), Scheduler::kNoFlags,
99
                                 tick_counter(), nullptr));
100 101 102 103 104 105 106
}


TEST_F(SchedulerTest, BuildScheduleOneParameter) {
  graph()->SetStart(graph()->NewNode(common()->Start(0)));

  Node* p1 = graph()->NewNode(common()->Parameter(0), graph()->start());
107 108
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, p1, graph()->start(),
109 110
                               graph()->start());

111
  graph()->SetEnd(graph()->NewNode(common()->End(1), ret));
112

113
  USE(Scheduler::ComputeSchedule(zone(), graph(), Scheduler::kNoFlags,
114
                                 tick_counter(), nullptr));
115 116 117
}


118
namespace {
119

120
Node* CreateDiamond(Graph* graph, CommonOperatorBuilder* common, Node* cond) {
121 122 123 124 125 126
  Node* tv = graph->NewNode(common->Int32Constant(6));
  Node* fv = graph->NewNode(common->Int32Constant(7));
  Node* br = graph->NewNode(common->Branch(), cond, graph->start());
  Node* t = graph->NewNode(common->IfTrue(), br);
  Node* f = graph->NewNode(common->IfFalse(), br);
  Node* m = graph->NewNode(common->Merge(2), t, f);
127 128
  Node* phi =
      graph->NewNode(common->Phi(MachineRepresentation::kTagged, 2), tv, fv, m);
129 130 131
  return phi;
}

132 133
}  // namespace

134

135
TARGET_TEST_F(SchedulerTest, FloatingDiamond1) {
136 137 138 139 140
  Node* start = graph()->NewNode(common()->Start(1));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
  Node* d1 = CreateDiamond(graph(), common(), p0);
141 142
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, d1, start, start);
143
  Node* end = graph()->NewNode(common()->End(1), ret);
144 145 146

  graph()->SetEnd(end);

147
  ComputeAndVerifySchedule(14);
148 149
}

150 151 152 153 154 155 156
TARGET_TEST_F(SchedulerTest, FloatingDeadDiamond1) {
  Node* start = graph()->NewNode(common()->Start(1));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
  Node* d1 = CreateDiamond(graph(), common(), p0);
  USE(d1);
157 158
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, p0, start, start);
159 160 161 162
  Node* end = graph()->NewNode(common()->End(1), ret);

  graph()->SetEnd(end);

163
  ComputeAndVerifySchedule(5);
164 165 166 167 168 169 170 171 172 173 174 175 176
}

TARGET_TEST_F(SchedulerTest, FloatingDeadDiamond2) {
  Graph* g = graph();
  Node* start = g->NewNode(common()->Start(1));
  g->SetStart(start);

  Node* n1 = g->NewNode(common()->Parameter(1), start);

  Node* n2 = g->NewNode(common()->Branch(), n1, start);
  Node* n3 = g->NewNode(common()->IfTrue(), n2);
  Node* n4 = g->NewNode(common()->IfFalse(), n2);
  Node* n5 = g->NewNode(common()->Int32Constant(-100));
177 178
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* n6 = g->NewNode(common()->Return(), zero, n5, start, n4);
179
  Node* n7 = g->NewNode(common()->Int32Constant(0));
180
  Node* n8 = g->NewNode(common()->Return(), zero, n7, start, n3);
181 182 183 184 185 186 187 188 189 190 191 192 193 194
  Node* n9 = g->NewNode(common()->End(2), n6, n8);

  // Dead nodes
  Node* n10 = g->NewNode(common()->Branch(), n1, n3);
  Node* n11 = g->NewNode(common()->IfTrue(), n10);
  Node* n12 = g->NewNode(common()->IfFalse(), n10);
  Node* n13 = g->NewNode(common()->Merge(2), n11, n12);
  Node* n14 =
      g->NewNode(common()->Phi(MachineRepresentation::kWord32, 2), n1, n7, n13);

  USE(n14);

  g->SetEnd(n9);

195
  ComputeAndVerifySchedule(11);
196
}
197

198
TARGET_TEST_F(SchedulerTest, FloatingDiamond2) {
199 200 201 202 203 204 205 206
  Node* start = graph()->NewNode(common()->Start(2));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
  Node* p1 = graph()->NewNode(common()->Parameter(1), start);
  Node* d1 = CreateDiamond(graph(), common(), p0);
  Node* d2 = CreateDiamond(graph(), common(), p1);
  Node* add = graph()->NewNode(&kIntAdd, d1, d2);
207 208
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, add, start, start);
209
  Node* end = graph()->NewNode(common()->End(1), ret);
210 211 212

  graph()->SetEnd(end);

213
  ComputeAndVerifySchedule(25);
214 215 216
}


217
TARGET_TEST_F(SchedulerTest, FloatingDiamond3) {
218 219 220 221 222 223 224 225 226
  Node* start = graph()->NewNode(common()->Start(2));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
  Node* p1 = graph()->NewNode(common()->Parameter(1), start);
  Node* d1 = CreateDiamond(graph(), common(), p0);
  Node* d2 = CreateDiamond(graph(), common(), p1);
  Node* add = graph()->NewNode(&kIntAdd, d1, d2);
  Node* d3 = CreateDiamond(graph(), common(), add);
227 228
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, d3, start, start);
229
  Node* end = graph()->NewNode(common()->End(1), ret);
230 231 232

  graph()->SetEnd(end);

233
  ComputeAndVerifySchedule(34);
234 235 236
}


237
TARGET_TEST_F(SchedulerTest, NestedFloatingDiamonds) {
238 239 240 241 242 243 244 245 246 247 248 249
  Node* start = graph()->NewNode(common()->Start(2));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);

  Node* fv = graph()->NewNode(common()->Int32Constant(7));
  Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start());
  Node* t = graph()->NewNode(common()->IfTrue(), br);
  Node* f = graph()->NewNode(common()->IfFalse(), br);

  Node* map = graph()->NewNode(
      simplified()->LoadElement(AccessBuilder::ForFixedArrayElement()), p0, p0,
250
      start, f);
251 252 253 254 255 256
  Node* br1 = graph()->NewNode(common()->Branch(), map, graph()->start());
  Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
  Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
  Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1);
  Node* ttrue = graph()->NewNode(common()->Int32Constant(1));
  Node* ffalse = graph()->NewNode(common()->Int32Constant(0));
257 258
  Node* phi1 = graph()->NewNode(
      common()->Phi(MachineRepresentation::kTagged, 2), ttrue, ffalse, m1);
259 260 261


  Node* m = graph()->NewNode(common()->Merge(2), t, f);
262 263
  Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
                               fv, phi1, m);
264 265
  Node* ephi1 = graph()->NewNode(common()->EffectPhi(2), start, map, m);

266 267
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, phi, ephi1, start);
268
  Node* end = graph()->NewNode(common()->End(1), ret);
269 270 271

  graph()->SetEnd(end);

272
  ComputeAndVerifySchedule(24);
273 274 275
}


276
TARGET_TEST_F(SchedulerTest, NestedFloatingDiamondWithChain) {
277 278 279 280 281 282 283 284 285 286 287
  Node* start = graph()->NewNode(common()->Start(2));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
  Node* p1 = graph()->NewNode(common()->Parameter(1), start);
  Node* c = graph()->NewNode(common()->Int32Constant(7));

  Node* brA1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
  Node* tA1 = graph()->NewNode(common()->IfTrue(), brA1);
  Node* fA1 = graph()->NewNode(common()->IfFalse(), brA1);
  Node* mA1 = graph()->NewNode(common()->Merge(2), tA1, fA1);
288 289
  Node* phiA1 = graph()->NewNode(
      common()->Phi(MachineRepresentation::kTagged, 2), p0, p1, mA1);
290 291 292 293 294

  Node* brB1 = graph()->NewNode(common()->Branch(), p1, graph()->start());
  Node* tB1 = graph()->NewNode(common()->IfTrue(), brB1);
  Node* fB1 = graph()->NewNode(common()->IfFalse(), brB1);
  Node* mB1 = graph()->NewNode(common()->Merge(2), tB1, fB1);
295 296
  Node* phiB1 = graph()->NewNode(
      common()->Phi(MachineRepresentation::kTagged, 2), p0, p1, mB1);
297 298 299 300 301

  Node* brA2 = graph()->NewNode(common()->Branch(), phiB1, mA1);
  Node* tA2 = graph()->NewNode(common()->IfTrue(), brA2);
  Node* fA2 = graph()->NewNode(common()->IfFalse(), brA2);
  Node* mA2 = graph()->NewNode(common()->Merge(2), tA2, fA2);
302 303
  Node* phiA2 = graph()->NewNode(
      common()->Phi(MachineRepresentation::kTagged, 2), phiB1, c, mA2);
304 305 306 307 308

  Node* brB2 = graph()->NewNode(common()->Branch(), phiA1, mB1);
  Node* tB2 = graph()->NewNode(common()->IfTrue(), brB2);
  Node* fB2 = graph()->NewNode(common()->IfFalse(), brB2);
  Node* mB2 = graph()->NewNode(common()->Merge(2), tB2, fB2);
309 310
  Node* phiB2 = graph()->NewNode(
      common()->Phi(MachineRepresentation::kTagged, 2), phiA1, c, mB2);
311 312

  Node* add = graph()->NewNode(&kIntAdd, phiA2, phiB2);
313 314
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, add, start, start);
315
  Node* end = graph()->NewNode(common()->End(1), ret);
316 317 318

  graph()->SetEnd(end);

319
  ComputeAndVerifySchedule(37);
320 321 322
}


323
TARGET_TEST_F(SchedulerTest, NestedFloatingDiamondWithLoop) {
324 325 326 327 328 329 330 331 332 333 334
  Node* start = graph()->NewNode(common()->Start(2));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);

  Node* fv = graph()->NewNode(common()->Int32Constant(7));
  Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start());
  Node* t = graph()->NewNode(common()->IfTrue(), br);
  Node* f = graph()->NewNode(common()->IfFalse(), br);

  Node* loop = graph()->NewNode(common()->Loop(2), f, start);
335 336
  Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
                               p0, p0, loop);
337 338 339 340 341 342 343 344 345 346

  Node* add = graph()->NewNode(&kIntAdd, ind, fv);
  Node* br1 = graph()->NewNode(common()->Branch(), add, loop);
  Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
  Node* f1 = graph()->NewNode(common()->IfFalse(), br1);

  loop->ReplaceInput(1, t1);  // close loop.
  ind->ReplaceInput(1, ind);  // close induction variable.

  Node* m = graph()->NewNode(common()->Merge(2), t, f1);
347 348
  Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
                               fv, ind, m);
349

350 351
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, start);
352
  Node* end = graph()->NewNode(common()->End(1), ret);
353 354 355

  graph()->SetEnd(end);

356
  ComputeAndVerifySchedule(21);
357 358 359
}


360
TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond1) {
361 362 363 364 365 366 367
  Node* start = graph()->NewNode(common()->Start(2));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);

  Node* c = graph()->NewNode(common()->Int32Constant(7));
  Node* loop = graph()->NewNode(common()->Loop(2), start, start);
368 369
  Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
                               p0, p0, loop);
370 371 372 373 374 375 376 377 378 379
  Node* add = graph()->NewNode(&kIntAdd, ind, c);

  Node* br = graph()->NewNode(common()->Branch(), add, loop);
  Node* t = graph()->NewNode(common()->IfTrue(), br);
  Node* f = graph()->NewNode(common()->IfFalse(), br);

  Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
  Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
  Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
  Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1);
380 381
  Node* phi1 = graph()->NewNode(
      common()->Phi(MachineRepresentation::kTagged, 2), add, p0, m1);
382 383 384 385

  loop->ReplaceInput(1, t);    // close loop.
  ind->ReplaceInput(1, phi1);  // close induction variable.

386 387
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, ind, start, f);
388
  Node* end = graph()->NewNode(common()->End(2), ret, f);
389 390 391

  graph()->SetEnd(end);

392
  ComputeAndVerifySchedule(21);
393 394 395
}


396
TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond2) {
397 398 399 400 401 402 403
  Node* start = graph()->NewNode(common()->Start(2));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);

  Node* c = graph()->NewNode(common()->Int32Constant(7));
  Node* loop = graph()->NewNode(common()->Loop(2), start, start);
404 405
  Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
                               p0, p0, loop);
406 407 408 409 410

  Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
  Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
  Node* f1 = graph()->NewNode(common()->IfFalse(), br1);
  Node* m1 = graph()->NewNode(common()->Merge(2), t1, f1);
411 412
  Node* phi1 = graph()->NewNode(
      common()->Phi(MachineRepresentation::kTagged, 2), c, ind, m1);
413 414 415 416 417 418 419 420 421 422

  Node* add = graph()->NewNode(&kIntAdd, ind, phi1);

  Node* br = graph()->NewNode(common()->Branch(), add, loop);
  Node* t = graph()->NewNode(common()->IfTrue(), br);
  Node* f = graph()->NewNode(common()->IfFalse(), br);

  loop->ReplaceInput(1, t);   // close loop.
  ind->ReplaceInput(1, add);  // close induction variable.

423 424
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, ind, start, f);
425
  Node* end = graph()->NewNode(common()->End(2), ret, f);
426 427 428

  graph()->SetEnd(end);

429
  ComputeAndVerifySchedule(21);
430 431 432
}


433
TARGET_TEST_F(SchedulerTest, LoopedFloatingDiamond3) {
434 435 436 437 438 439 440
  Node* start = graph()->NewNode(common()->Start(2));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);

  Node* c = graph()->NewNode(common()->Int32Constant(7));
  Node* loop = graph()->NewNode(common()->Loop(2), start, start);
441 442
  Node* ind = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
                               p0, p0, loop);
443 444 445 446 447 448

  Node* br1 = graph()->NewNode(common()->Branch(), p0, graph()->start());
  Node* t1 = graph()->NewNode(common()->IfTrue(), br1);
  Node* f1 = graph()->NewNode(common()->IfFalse(), br1);

  Node* loop1 = graph()->NewNode(common()->Loop(2), t1, start);
449 450
  Node* ind1 = graph()->NewNode(
      common()->Phi(MachineRepresentation::kTagged, 2), p0, p0, loop);
451 452 453 454 455 456 457 458 459 460

  Node* add1 = graph()->NewNode(&kIntAdd, ind1, c);
  Node* br2 = graph()->NewNode(common()->Branch(), add1, loop1);
  Node* t2 = graph()->NewNode(common()->IfTrue(), br2);
  Node* f2 = graph()->NewNode(common()->IfFalse(), br2);

  loop1->ReplaceInput(1, t2);   // close inner loop.
  ind1->ReplaceInput(1, ind1);  // close inner induction variable.

  Node* m1 = graph()->NewNode(common()->Merge(2), f1, f2);
461 462
  Node* phi1 = graph()->NewNode(
      common()->Phi(MachineRepresentation::kTagged, 2), c, ind1, m1);
463 464 465 466 467 468 469 470 471 472

  Node* add = graph()->NewNode(&kIntAdd, ind, phi1);

  Node* br = graph()->NewNode(common()->Branch(), add, loop);
  Node* t = graph()->NewNode(common()->IfTrue(), br);
  Node* f = graph()->NewNode(common()->IfFalse(), br);

  loop->ReplaceInput(1, t);   // close loop.
  ind->ReplaceInput(1, add);  // close induction variable.

473 474
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, ind, start, f);
475
  Node* end = graph()->NewNode(common()->End(2), ret, f);
476 477 478

  graph()->SetEnd(end);

479
  ComputeAndVerifySchedule(29);
480 481 482
}


483
TARGET_TEST_F(SchedulerTest, PhisPushedDownToDifferentBranches) {
484 485 486 487 488 489 490 491 492 493 494 495 496 497
  Node* start = graph()->NewNode(common()->Start(2));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
  Node* p1 = graph()->NewNode(common()->Parameter(1), start);

  Node* v1 = graph()->NewNode(common()->Int32Constant(1));
  Node* v2 = graph()->NewNode(common()->Int32Constant(2));
  Node* v3 = graph()->NewNode(common()->Int32Constant(3));
  Node* v4 = graph()->NewNode(common()->Int32Constant(4));
  Node* br = graph()->NewNode(common()->Branch(), p0, graph()->start());
  Node* t = graph()->NewNode(common()->IfTrue(), br);
  Node* f = graph()->NewNode(common()->IfFalse(), br);
  Node* m = graph()->NewNode(common()->Merge(2), t, f);
498 499 500 501
  Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
                               v1, v2, m);
  Node* phi2 = graph()->NewNode(
      common()->Phi(MachineRepresentation::kTagged, 2), v3, v4, m);
502 503 504 505 506

  Node* br2 = graph()->NewNode(common()->Branch(), p1, graph()->start());
  Node* t2 = graph()->NewNode(common()->IfTrue(), br2);
  Node* f2 = graph()->NewNode(common()->IfFalse(), br2);
  Node* m2 = graph()->NewNode(common()->Merge(2), t2, f2);
507 508
  Node* phi3 = graph()->NewNode(
      common()->Phi(MachineRepresentation::kTagged, 2), phi, phi2, m2);
509

510 511
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, phi3, start, start);
512
  Node* end = graph()->NewNode(common()->End(1), ret);
513 514 515

  graph()->SetEnd(end);

516
  ComputeAndVerifySchedule(25);
517 518 519
}


520
TARGET_TEST_F(SchedulerTest, BranchHintTrue) {
521 522 523 524 525 526 527 528 529 530
  Node* start = graph()->NewNode(common()->Start(1));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
  Node* tv = graph()->NewNode(common()->Int32Constant(6));
  Node* fv = graph()->NewNode(common()->Int32Constant(7));
  Node* br = graph()->NewNode(common()->Branch(BranchHint::kTrue), p0, start);
  Node* t = graph()->NewNode(common()->IfTrue(), br);
  Node* f = graph()->NewNode(common()->IfFalse(), br);
  Node* m = graph()->NewNode(common()->Merge(2), t, f);
531 532
  Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
                               tv, fv, m);
533 534
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, start);
535
  Node* end = graph()->NewNode(common()->End(1), ret);
536 537 538

  graph()->SetEnd(end);

539
  Schedule* schedule = ComputeAndVerifySchedule(14);
540
  // Make sure the false block is marked as deferred.
541 542
  EXPECT_FALSE(schedule->block(t)->deferred());
  EXPECT_TRUE(schedule->block(f)->deferred());
543 544 545
}


546
TARGET_TEST_F(SchedulerTest, BranchHintFalse) {
547 548 549 550 551 552 553 554 555 556
  Node* start = graph()->NewNode(common()->Start(1));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
  Node* tv = graph()->NewNode(common()->Int32Constant(6));
  Node* fv = graph()->NewNode(common()->Int32Constant(7));
  Node* br = graph()->NewNode(common()->Branch(BranchHint::kFalse), p0, start);
  Node* t = graph()->NewNode(common()->IfTrue(), br);
  Node* f = graph()->NewNode(common()->IfFalse(), br);
  Node* m = graph()->NewNode(common()->Merge(2), t, f);
557 558
  Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
                               tv, fv, m);
559 560
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, start);
561
  Node* end = graph()->NewNode(common()->End(1), ret);
562 563 564

  graph()->SetEnd(end);

565
  Schedule* schedule = ComputeAndVerifySchedule(14);
566
  // Make sure the true block is marked as deferred.
567 568
  EXPECT_TRUE(schedule->block(t)->deferred());
  EXPECT_FALSE(schedule->block(f)->deferred());
569 570
}

571

572 573 574 575 576 577 578
TARGET_TEST_F(SchedulerTest, CallException) {
  Node* start = graph()->NewNode(common()->Start(1));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
  Node* c1 = graph()->NewNode(&kMockCall, start);
  Node* ok1 = graph()->NewNode(common()->IfSuccess(), c1);
579
  Node* ex1 = graph()->NewNode(common()->IfException(), c1, c1);
580 581
  Node* c2 = graph()->NewNode(&kMockCall, ok1);
  Node* ok2 = graph()->NewNode(common()->IfSuccess(), c2);
582
  Node* ex2 = graph()->NewNode(common()->IfException(), c2, c2);
583 584
  Node* hdl = graph()->NewNode(common()->Merge(2), ex1, ex2);
  Node* m = graph()->NewNode(common()->Merge(2), ok2, hdl);
585 586
  Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2),
                               c2, p0, m);
587 588
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, m);
589
  Node* end = graph()->NewNode(common()->End(1), ret);
590 591 592

  graph()->SetEnd(end);

593
  Schedule* schedule = ComputeAndVerifySchedule(18);
594 595 596 597 598 599 600 601
  // Make sure the exception blocks as well as the handler are deferred.
  EXPECT_TRUE(schedule->block(ex1)->deferred());
  EXPECT_TRUE(schedule->block(ex2)->deferred());
  EXPECT_TRUE(schedule->block(hdl)->deferred());
  EXPECT_FALSE(schedule->block(m)->deferred());
}


602 603 604 605 606 607
TARGET_TEST_F(SchedulerTest, TailCall) {
  Node* start = graph()->NewNode(common()->Start(1));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
  Node* call = graph()->NewNode(&kMockTailCall, p0, start, start);
608
  Node* end = graph()->NewNode(common()->End(1), call);
609 610 611 612 613 614 615

  graph()->SetEnd(end);

  ComputeAndVerifySchedule(4);
}


616 617 618 619 620
TARGET_TEST_F(SchedulerTest, Switch) {
  Node* start = graph()->NewNode(common()->Start(1));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
621 622
  Node* sw = graph()->NewNode(common()->Switch(3), p0, start);
  Node* c0 = graph()->NewNode(common()->IfValue(0), sw);
623
  Node* v0 = graph()->NewNode(common()->Int32Constant(11));
624
  Node* c1 = graph()->NewNode(common()->IfValue(1), sw);
625
  Node* v1 = graph()->NewNode(common()->Int32Constant(22));
626 627 628
  Node* d = graph()->NewNode(common()->IfDefault(), sw);
  Node* vd = graph()->NewNode(common()->Int32Constant(33));
  Node* m = graph()->NewNode(common()->Merge(3), c0, c1, d);
629 630
  Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 3),
                               v0, v1, vd, m);
631 632
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, m);
633
  Node* end = graph()->NewNode(common()->End(1), ret);
634 635 636

  graph()->SetEnd(end);

637
  ComputeAndVerifySchedule(17);
638 639 640 641 642 643 644 645
}


TARGET_TEST_F(SchedulerTest, FloatingSwitch) {
  Node* start = graph()->NewNode(common()->Start(1));
  graph()->SetStart(start);

  Node* p0 = graph()->NewNode(common()->Parameter(0), start);
646 647
  Node* sw = graph()->NewNode(common()->Switch(3), p0, start);
  Node* c0 = graph()->NewNode(common()->IfValue(0), sw);
648
  Node* v0 = graph()->NewNode(common()->Int32Constant(11));
649
  Node* c1 = graph()->NewNode(common()->IfValue(1), sw);
650
  Node* v1 = graph()->NewNode(common()->Int32Constant(22));
651 652 653
  Node* d = graph()->NewNode(common()->IfDefault(), sw);
  Node* vd = graph()->NewNode(common()->Int32Constant(33));
  Node* m = graph()->NewNode(common()->Merge(3), c0, c1, d);
654 655
  Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kWord32, 3),
                               v0, v1, vd, m);
656 657
  Node* zero = graph()->NewNode(common()->Int32Constant(0));
  Node* ret = graph()->NewNode(common()->Return(), zero, phi, start, start);
658
  Node* end = graph()->NewNode(common()->End(1), ret);
659 660 661

  graph()->SetEnd(end);

662
  ComputeAndVerifySchedule(17);
663 664
}

665 666 667 668 669 670 671 672

TARGET_TEST_F(SchedulerTest, Terminate) {
  Node* start = graph()->NewNode(common()->Start(1));
  graph()->SetStart(start);

  Node* loop = graph()->NewNode(common()->Loop(2), start, start);
  loop->ReplaceInput(1, loop);  // self loop, NTL.

673 674
  Node* effect = graph()->NewNode(common()->EffectPhi(2), start, start, loop);
  effect->ReplaceInput(1, effect);  // self loop.
675 676

  Node* terminate = graph()->NewNode(common()->Terminate(), effect, loop);
677
  Node* end = graph()->NewNode(common()->End(1), terminate);
678 679 680 681 682 683 684 685
  graph()->SetEnd(end);

  Schedule* schedule = ComputeAndVerifySchedule(6);
  BasicBlock* block = schedule->block(loop);
  EXPECT_EQ(block, schedule->block(effect));
  EXPECT_GE(block->rpo_number(), 0);
}

686 687 688
}  // namespace compiler
}  // namespace internal
}  // namespace v8