deps/v8/test/cctest/compiler/test-control-reducer.cc

   1 // Copyright 2014 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/v8.h"
   6 #include "test/cctest/cctest.h"
   7
   8 #include "src/base/bits.h"
   9 #include "src/compiler/common-operator.h"
  10 #include "src/compiler/control-reducer.h"
  11 #include "src/compiler/graph-inl.h"
  12 #include "src/compiler/js-graph.h"
  13 #include "src/compiler/node-properties.h"
  14
  15 using namespace v8::internal;
  16 using namespace v8::internal::compiler;
  17
  18 static const size_t kNumLeafs = 4;
  19
  20 enum Decision { kFalse, kUnknown, kTrue };
  21
  22 // TODO(titzer): convert this whole file into unit tests.
  23
  24 static int CheckInputs(Node* node, Node* i0 = NULL, Node* i1 = NULL,
  25                        Node* i2 = NULL) {
  26   int count = 3;
  27   if (i2 == NULL) count = 2;
  28   if (i1 == NULL) count = 1;
  29   if (i0 == NULL) count = 0;
  30   CHECK_EQ(count, node->InputCount());
  31   if (i0 != NULL) CHECK_EQ(i0, node->InputAt(0));
  32   if (i1 != NULL) CHECK_EQ(i1, node->InputAt(1));
  33   if (i2 != NULL) CHECK_EQ(i2, node->InputAt(2));
  34   return count;
  35 }
  36
  37
  38 static int CheckMerge(Node* node, Node* i0 = NULL, Node* i1 = NULL,
  39                       Node* i2 = NULL) {
  40   CHECK_EQ(IrOpcode::kMerge, node->opcode());
  41   int count = CheckInputs(node, i0, i1, i2);
  42   CHECK_EQ(count, node->op()->ControlInputCount());
  43   return count;
  44 }
  45
  46
  47 static int CheckLoop(Node* node, Node* i0 = NULL, Node* i1 = NULL,
  48                      Node* i2 = NULL) {
  49   CHECK_EQ(IrOpcode::kLoop, node->opcode());
  50   int count = CheckInputs(node, i0, i1, i2);
  51   CHECK_EQ(count, node->op()->ControlInputCount());
  52   return count;
  53 }
  54
  55
  56 bool IsUsedBy(Node* a, Node* b) {
  57   auto const uses = a->uses();
  58   return std::find(uses.begin(), uses.end(), b) != uses.end();
  59 }
  60
  61
  62 // A helper for all tests dealing with ControlTester.
  63 class ControlReducerTester : HandleAndZoneScope {
  64  public:
  65   ControlReducerTester()
  66       : isolate(main_isolate()),
  67         common(main_zone()),
  68         graph(main_zone()),
  69         jsgraph(main_isolate(), &graph, &common, NULL, NULL),
  70         start(graph.NewNode(common.Start(1))),
  71         end(graph.NewNode(common.End(), start)),
  72         p0(graph.NewNode(common.Parameter(0), start)),
  73         zero(jsgraph.Int32Constant(0)),
  74         one(jsgraph.OneConstant()),
  75         half(jsgraph.Constant(0.5)),
  76         self(graph.NewNode(common.Int32Constant(0xaabbccdd))),
  77         dead(graph.NewNode(common.Dead())) {
  78     graph.SetEnd(end);
  79     graph.SetStart(start);
  80     leaf[0] = zero;
  81     leaf[1] = one;
  82     leaf[2] = half;
  83     leaf[3] = p0;
  84   }
  85
  86   Isolate* isolate;
  87   CommonOperatorBuilder common;
  88   Graph graph;
  89   JSGraph jsgraph;
  90   Node* start;
  91   Node* end;
  92   Node* p0;
  93   Node* zero;
  94   Node* one;
  95   Node* half;
  96   Node* self;
  97   Node* dead;
  98   Node* leaf[kNumLeafs];
  99
 100   Node* Phi(Node* a) {
 101     return SetSelfReferences(graph.NewNode(op(1, false), a, start));
 102   }
 103
 104   Node* Phi(Node* a, Node* b) {
 105     return SetSelfReferences(graph.NewNode(op(2, false), a, b, start));
 106   }
 107
 108   Node* Phi(Node* a, Node* b, Node* c) {
 109     return SetSelfReferences(graph.NewNode(op(3, false), a, b, c, start));
 110   }
 111
 112   Node* Phi(Node* a, Node* b, Node* c, Node* d) {
 113     return SetSelfReferences(graph.NewNode(op(4, false), a, b, c, d, start));
 114   }
 115
 116   Node* EffectPhi(Node* a) {
 117     return SetSelfReferences(graph.NewNode(op(1, true), a, start));
 118   }
 119
 120   Node* EffectPhi(Node* a, Node* b) {
 121     return SetSelfReferences(graph.NewNode(op(2, true), a, b, start));
 122   }
 123
 124   Node* EffectPhi(Node* a, Node* b, Node* c) {
 125     return SetSelfReferences(graph.NewNode(op(3, true), a, b, c, start));
 126   }
 127
 128   Node* EffectPhi(Node* a, Node* b, Node* c, Node* d) {
 129     return SetSelfReferences(graph.NewNode(op(4, true), a, b, c, d, start));
 130   }
 131
 132   Node* SetSelfReferences(Node* node) {
 133     for (Edge edge : node->input_edges()) {
 134       if (edge.to() == self) node->ReplaceInput(edge.index(), node);
 135     }
 136     return node;
 137   }
 138
 139   const Operator* op(int count, bool effect) {
 140     return effect ? common.EffectPhi(count) : common.Phi(kMachAnyTagged, count);
 141   }
 142
 143   void Trim() { ControlReducer::TrimGraph(main_zone(), &jsgraph); }
 144
 145   void ReduceGraph() {
 146     ControlReducer::ReduceGraph(main_zone(), &jsgraph, &common);
 147   }
 148
 149   // Checks one-step reduction of a phi.
 150   void ReducePhi(Node* expect, Node* phi) {
 151     Node* result = ControlReducer::ReducePhiForTesting(&jsgraph, &common, phi);
 152     CHECK_EQ(expect, result);
 153     ReducePhiIterative(expect, phi);  // iterative should give the same result.
 154   }
 155
 156   // Checks one-step reduction of a phi.
 157   void ReducePhiNonIterative(Node* expect, Node* phi) {
 158     Node* result = ControlReducer::ReducePhiForTesting(&jsgraph, &common, phi);
 159     CHECK_EQ(expect, result);
 160   }
 161
 162   void ReducePhiIterative(Node* expect, Node* phi) {
 163     p0->ReplaceInput(0, start);  // hack: parameters may be trimmed.
 164     Node* ret = graph.NewNode(common.Return(), phi, start, start);
 165     Node* end = graph.NewNode(common.End(), ret);
 166     graph.SetEnd(end);
 167     ControlReducer::ReduceGraph(main_zone(), &jsgraph, &common);
 168     CheckInputs(end, ret);
 169     CheckInputs(ret, expect, start, start);
 170   }
 171
 172   void ReduceMerge(Node* expect, Node* merge) {
 173     Node* result = ControlReducer::ReduceMerge(&jsgraph, &common, merge);
 174     CHECK_EQ(expect, result);
 175   }
 176
 177   void ReduceMergeIterative(Node* expect, Node* merge) {
 178     p0->ReplaceInput(0, start);  // hack: parameters may be trimmed.
 179     Node* end = graph.NewNode(common.End(), merge);
 180     graph.SetEnd(end);
 181     ReduceGraph();
 182     CheckInputs(end, expect);
 183   }
 184
 185   void ReduceBranch(Decision expected, Node* branch) {
 186     Node* control = branch->InputAt(1);
 187     for (Node* use : branch->uses()) {
 188       if (use->opcode() == IrOpcode::kIfTrue) {
 189         Node* result =
 190             ControlReducer::ReduceIfNodeForTesting(&jsgraph, &common, use);
 191         if (expected == kTrue) CHECK_EQ(control, result);
 192         if (expected == kFalse) CHECK_EQ(IrOpcode::kDead, result->opcode());
 193         if (expected == kUnknown) CHECK_EQ(use, result);
 194       } else if (use->opcode() == IrOpcode::kIfFalse) {
 195         Node* result =
 196             ControlReducer::ReduceIfNodeForTesting(&jsgraph, &common, use);
 197         if (expected == kFalse) CHECK_EQ(control, result);
 198         if (expected == kTrue) CHECK_EQ(IrOpcode::kDead, result->opcode());
 199         if (expected == kUnknown) CHECK_EQ(use, result);
 200       } else {
 201         UNREACHABLE();
 202       }
 203     }
 204   }
 205
 206   Node* Return(Node* val, Node* effect, Node* control) {
 207     Node* ret = graph.NewNode(common.Return(), val, effect, control);
 208     end->ReplaceInput(0, ret);
 209     return ret;
 210   }
 211 };
 212
 213
 214 TEST(Trim1_live) {
 215   ControlReducerTester T;
 216   CHECK(IsUsedBy(T.start, T.p0));
 217   T.graph.SetEnd(T.p0);
 218   T.Trim();
 219   CHECK(IsUsedBy(T.start, T.p0));
 220   CheckInputs(T.p0, T.start);
 221 }
 222
 223
 224 TEST(Trim1_dead) {
 225   ControlReducerTester T;
 226   CHECK(IsUsedBy(T.start, T.p0));
 227   T.Trim();
 228   CHECK(!IsUsedBy(T.start, T.p0));
 229   CHECK(!T.p0->InputAt(0));
 230 }
 231
 232
 233 TEST(Trim2_live) {
 234   ControlReducerTester T;
 235   Node* phi =
 236       T.graph.NewNode(T.common.Phi(kMachAnyTagged, 2), T.one, T.half, T.start);
 237   CHECK(IsUsedBy(T.one, phi));
 238   CHECK(IsUsedBy(T.half, phi));
 239   CHECK(IsUsedBy(T.start, phi));
 240   T.graph.SetEnd(phi);
 241   T.Trim();
 242   CHECK(IsUsedBy(T.one, phi));
 243   CHECK(IsUsedBy(T.half, phi));
 244   CHECK(IsUsedBy(T.start, phi));
 245   CheckInputs(phi, T.one, T.half, T.start);
 246 }
 247
 248
 249 TEST(Trim2_dead) {
 250   ControlReducerTester T;
 251   Node* phi =
 252       T.graph.NewNode(T.common.Phi(kMachAnyTagged, 2), T.one, T.half, T.start);
 253   CHECK(IsUsedBy(T.one, phi));
 254   CHECK(IsUsedBy(T.half, phi));
 255   CHECK(IsUsedBy(T.start, phi));
 256   T.Trim();
 257   CHECK(!IsUsedBy(T.one, phi));
 258   CHECK(!IsUsedBy(T.half, phi));
 259   CHECK(!IsUsedBy(T.start, phi));
 260   CHECK(!phi->InputAt(0));
 261   CHECK(!phi->InputAt(1));
 262   CHECK(!phi->InputAt(2));
 263 }
 264
 265
 266 TEST(Trim_chain1) {
 267   ControlReducerTester T;
 268   const int kDepth = 15;
 269   Node* live[kDepth];
 270   Node* dead[kDepth];
 271   Node* end = T.start;
 272   for (int i = 0; i < kDepth; i++) {
 273     live[i] = end = T.graph.NewNode(T.common.Merge(1), end);
 274     dead[i] = T.graph.NewNode(T.common.Merge(1), end);
 275   }
 276   // end         -> live[last] ->  live[last-1] -> ... -> start
 277   //     dead[last] ^ dead[last-1] ^ ...                  ^
 278   T.graph.SetEnd(end);
 279   T.Trim();
 280   for (int i = 0; i < kDepth; i++) {
 281     CHECK(!IsUsedBy(live[i], dead[i]));
 282     CHECK(!dead[i]->InputAt(0));
 283     CHECK_EQ(i == 0 ? T.start : live[i - 1], live[i]->InputAt(0));
 284   }
 285 }
 286
 287
 288 TEST(Trim_chain2) {
 289   ControlReducerTester T;
 290   const int kDepth = 15;
 291   Node* live[kDepth];
 292   Node* dead[kDepth];
 293   Node* l = T.start;
 294   Node* d = T.start;
 295   for (int i = 0; i < kDepth; i++) {
 296     live[i] = l = T.graph.NewNode(T.common.Merge(1), l);
 297     dead[i] = d = T.graph.NewNode(T.common.Merge(1), d);
 298   }
 299   // end -> live[last] -> live[last-1] -> ... -> start
 300   //        dead[last] -> dead[last-1] -> ... -> start
 301   T.graph.SetEnd(l);
 302   T.Trim();
 303   CHECK(!IsUsedBy(T.start, dead[0]));
 304   for (int i = 0; i < kDepth; i++) {
 305     CHECK_EQ(i == 0 ? NULL : dead[i - 1], dead[i]->InputAt(0));
 306     CHECK_EQ(i == 0 ? T.start : live[i - 1], live[i]->InputAt(0));
 307   }
 308 }
 309
 310
 311 TEST(Trim_cycle1) {
 312   ControlReducerTester T;
 313   Node* loop = T.graph.NewNode(T.common.Loop(1), T.start, T.start);
 314   loop->ReplaceInput(1, loop);
 315   Node* end = T.graph.NewNode(T.common.End(), loop);
 316   T.graph.SetEnd(end);
 317
 318   CHECK(IsUsedBy(T.start, loop));
 319   CHECK(IsUsedBy(loop, end));
 320   CHECK(IsUsedBy(loop, loop));
 321
 322   T.Trim();
 323
 324   // nothing should have happened to the loop itself.
 325   CHECK(IsUsedBy(T.start, loop));
 326   CHECK(IsUsedBy(loop, end));
 327   CHECK(IsUsedBy(loop, loop));
 328   CheckInputs(loop, T.start, loop);
 329   CheckInputs(end, loop);
 330 }
 331
 332
 333 TEST(Trim_cycle2) {
 334   ControlReducerTester T;
 335   Node* loop = T.graph.NewNode(T.common.Loop(2), T.start, T.start);
 336   loop->ReplaceInput(1, loop);
 337   Node* end = T.graph.NewNode(T.common.End(), loop);
 338   Node* phi =
 339       T.graph.NewNode(T.common.Phi(kMachAnyTagged, 2), T.one, T.half, loop);
 340   T.graph.SetEnd(end);
 341
 342   CHECK(IsUsedBy(T.start, loop));
 343   CHECK(IsUsedBy(loop, end));
 344   CHECK(IsUsedBy(loop, loop));
 345   CHECK(IsUsedBy(loop, phi));
 346   CHECK(IsUsedBy(T.one, phi));
 347   CHECK(IsUsedBy(T.half, phi));
 348
 349   T.Trim();
 350
 351   // nothing should have happened to the loop itself.
 352   CHECK(IsUsedBy(T.start, loop));
 353   CHECK(IsUsedBy(loop, end));
 354   CHECK(IsUsedBy(loop, loop));
 355   CheckInputs(loop, T.start, loop);
 356   CheckInputs(end, loop);
 357
 358   // phi should have been trimmed away.
 359   CHECK(!IsUsedBy(loop, phi));
 360   CHECK(!IsUsedBy(T.one, phi));
 361   CHECK(!IsUsedBy(T.half, phi));
 362   CHECK(!phi->InputAt(0));
 363   CHECK(!phi->InputAt(1));
 364   CHECK(!phi->InputAt(2));
 365 }
 366
 367
 368 void CheckTrimConstant(ControlReducerTester* T, Node* k) {
 369   Node* phi = T->graph.NewNode(T->common.Phi(kMachInt32, 1), k, T->start);
 370   CHECK(IsUsedBy(k, phi));
 371   T->Trim();
 372   CHECK(!IsUsedBy(k, phi));
 373   CHECK(!phi->InputAt(0));
 374   CHECK(!phi->InputAt(1));
 375 }
 376
 377
 378 TEST(Trim_constants) {
 379   ControlReducerTester T;
 380   int32_t int32_constants[] = {
 381       0, -1,  -2,  2,  2,  3,  3,  4,  4,  5,  5,  4,  5,  6, 6, 7, 8, 7, 8, 9,
 382       0, -11, -12, 12, 12, 13, 13, 14, 14, 15, 15, 14, 15, 6, 6, 7, 8, 7, 8, 9};
 383
 384   for (size_t i = 0; i < arraysize(int32_constants); i++) {
 385     CheckTrimConstant(&T, T.jsgraph.Int32Constant(int32_constants[i]));
 386     CheckTrimConstant(&T, T.jsgraph.Float64Constant(int32_constants[i]));
 387     CheckTrimConstant(&T, T.jsgraph.Constant(int32_constants[i]));
 388   }
 389
 390   Node* other_constants[] = {
 391       T.jsgraph.UndefinedConstant(), T.jsgraph.TheHoleConstant(),
 392       T.jsgraph.TrueConstant(),      T.jsgraph.FalseConstant(),
 393       T.jsgraph.NullConstant(),      T.jsgraph.ZeroConstant(),
 394       T.jsgraph.OneConstant(),       T.jsgraph.NaNConstant(),
 395       T.jsgraph.Constant(21),        T.jsgraph.Constant(22.2)};
 396
 397   for (size_t i = 0; i < arraysize(other_constants); i++) {
 398     CheckTrimConstant(&T, other_constants[i]);
 399   }
 400 }
 401
 402
 403 TEST(CReducePhi1) {
 404   ControlReducerTester R;
 405
 406   R.ReducePhi(R.leaf[0], R.Phi(R.leaf[0]));
 407   R.ReducePhi(R.leaf[1], R.Phi(R.leaf[1]));
 408   R.ReducePhi(R.leaf[2], R.Phi(R.leaf[2]));
 409   R.ReducePhi(R.leaf[3], R.Phi(R.leaf[3]));
 410 }
 411
 412
 413 TEST(CReducePhi1_dead) {
 414   ControlReducerTester R;
 415
 416   R.ReducePhi(R.leaf[0], R.Phi(R.leaf[0], R.dead));
 417   R.ReducePhi(R.leaf[1], R.Phi(R.leaf[1], R.dead));
 418   R.ReducePhi(R.leaf[2], R.Phi(R.leaf[2], R.dead));
 419   R.ReducePhi(R.leaf[3], R.Phi(R.leaf[3], R.dead));
 420
 421   R.ReducePhi(R.leaf[0], R.Phi(R.dead, R.leaf[0]));
 422   R.ReducePhi(R.leaf[1], R.Phi(R.dead, R.leaf[1]));
 423   R.ReducePhi(R.leaf[2], R.Phi(R.dead, R.leaf[2]));
 424   R.ReducePhi(R.leaf[3], R.Phi(R.dead, R.leaf[3]));
 425 }
 426
 427
 428 TEST(CReducePhi1_dead2) {
 429   ControlReducerTester R;
 430
 431   R.ReducePhi(R.leaf[0], R.Phi(R.leaf[0], R.dead, R.dead));
 432   R.ReducePhi(R.leaf[0], R.Phi(R.dead, R.leaf[0], R.dead));
 433   R.ReducePhi(R.leaf[0], R.Phi(R.dead, R.dead, R.leaf[0]));
 434 }
 435
 436
 437 TEST(CReducePhi2a) {
 438   ControlReducerTester R;
 439
 440   for (size_t i = 0; i < kNumLeafs; i++) {
 441     Node* a = R.leaf[i];
 442     R.ReducePhi(a, R.Phi(a, a));
 443   }
 444 }
 445
 446
 447 TEST(CReducePhi2b) {
 448   ControlReducerTester R;
 449
 450   for (size_t i = 0; i < kNumLeafs; i++) {
 451     Node* a = R.leaf[i];
 452     R.ReducePhi(a, R.Phi(R.self, a));
 453     R.ReducePhi(a, R.Phi(a, R.self));
 454   }
 455 }
 456
 457
 458 TEST(CReducePhi2c) {
 459   ControlReducerTester R;
 460
 461   for (size_t i = 1; i < kNumLeafs; i++) {
 462     Node* a = R.leaf[i], *b = R.leaf[0];
 463     Node* phi1 = R.Phi(b, a);
 464     R.ReducePhi(phi1, phi1);
 465
 466     Node* phi2 = R.Phi(a, b);
 467     R.ReducePhi(phi2, phi2);
 468   }
 469 }
 470
 471
 472 TEST(CReducePhi2_dead) {
 473   ControlReducerTester R;
 474
 475   for (size_t i = 0; i < kNumLeafs; i++) {
 476     Node* a = R.leaf[i];
 477     R.ReducePhi(a, R.Phi(a, a, R.dead));
 478     R.ReducePhi(a, R.Phi(a, R.dead, a));
 479     R.ReducePhi(a, R.Phi(R.dead, a, a));
 480   }
 481
 482   for (size_t i = 0; i < kNumLeafs; i++) {
 483     Node* a = R.leaf[i];
 484     R.ReducePhi(a, R.Phi(R.self, a));
 485     R.ReducePhi(a, R.Phi(a, R.self));
 486     R.ReducePhi(a, R.Phi(R.self, a, R.dead));
 487     R.ReducePhi(a, R.Phi(a, R.self, R.dead));
 488   }
 489
 490   for (size_t i = 1; i < kNumLeafs; i++) {
 491     Node* a = R.leaf[i], *b = R.leaf[0];
 492     Node* phi1 = R.Phi(b, a, R.dead);
 493     R.ReducePhiNonIterative(phi1, phi1);
 494
 495     Node* phi2 = R.Phi(a, b, R.dead);
 496     R.ReducePhiNonIterative(phi2, phi2);
 497   }
 498 }
 499
 500
 501 TEST(CReducePhi3) {
 502   ControlReducerTester R;
 503
 504   for (size_t i = 0; i < kNumLeafs; i++) {
 505     Node* a = R.leaf[i];
 506     R.ReducePhi(a, R.Phi(a, a, a));
 507   }
 508
 509   for (size_t i = 0; i < kNumLeafs; i++) {
 510     Node* a = R.leaf[i];
 511     R.ReducePhi(a, R.Phi(R.self, a, a));
 512     R.ReducePhi(a, R.Phi(a, R.self, a));
 513     R.ReducePhi(a, R.Phi(a, a, R.self));
 514   }
 515
 516   for (size_t i = 1; i < kNumLeafs; i++) {
 517     Node* a = R.leaf[i], *b = R.leaf[0];
 518     Node* phi1 = R.Phi(b, a, a);
 519     R.ReducePhi(phi1, phi1);
 520
 521     Node* phi2 = R.Phi(a, b, a);
 522     R.ReducePhi(phi2, phi2);
 523
 524     Node* phi3 = R.Phi(a, a, b);
 525     R.ReducePhi(phi3, phi3);
 526   }
 527 }
 528
 529
 530 TEST(CReducePhi4) {
 531   ControlReducerTester R;
 532
 533   for (size_t i = 0; i < kNumLeafs; i++) {
 534     Node* a = R.leaf[i];
 535     R.ReducePhi(a, R.Phi(a, a, a, a));
 536   }
 537
 538   for (size_t i = 0; i < kNumLeafs; i++) {
 539     Node* a = R.leaf[i];
 540     R.ReducePhi(a, R.Phi(R.self, a, a, a));
 541     R.ReducePhi(a, R.Phi(a, R.self, a, a));
 542     R.ReducePhi(a, R.Phi(a, a, R.self, a));
 543     R.ReducePhi(a, R.Phi(a, a, a, R.self));
 544
 545     R.ReducePhi(a, R.Phi(R.self, R.self, a, a));
 546     R.ReducePhi(a, R.Phi(a, R.self, R.self, a));
 547     R.ReducePhi(a, R.Phi(a, a, R.self, R.self));
 548     R.ReducePhi(a, R.Phi(R.self, a, a, R.self));
 549   }
 550
 551   for (size_t i = 1; i < kNumLeafs; i++) {
 552     Node* a = R.leaf[i], *b = R.leaf[0];
 553     Node* phi1 = R.Phi(b, a, a, a);
 554     R.ReducePhi(phi1, phi1);
 555
 556     Node* phi2 = R.Phi(a, b, a, a);
 557     R.ReducePhi(phi2, phi2);
 558
 559     Node* phi3 = R.Phi(a, a, b, a);
 560     R.ReducePhi(phi3, phi3);
 561
 562     Node* phi4 = R.Phi(a, a, a, b);
 563     R.ReducePhi(phi4, phi4);
 564   }
 565 }
 566
 567
 568 TEST(CReducePhi_iterative1) {
 569   ControlReducerTester R;
 570
 571   R.ReducePhiIterative(R.leaf[0], R.Phi(R.leaf[0], R.Phi(R.leaf[0])));
 572   R.ReducePhiIterative(R.leaf[0], R.Phi(R.Phi(R.leaf[0]), R.leaf[0]));
 573 }
 574
 575
 576 TEST(CReducePhi_iterative2) {
 577   ControlReducerTester R;
 578
 579   R.ReducePhiIterative(R.leaf[0], R.Phi(R.Phi(R.leaf[0]), R.Phi(R.leaf[0])));
 580 }
 581
 582
 583 TEST(CReducePhi_iterative3) {
 584   ControlReducerTester R;
 585
 586   R.ReducePhiIterative(R.leaf[0],
 587                        R.Phi(R.leaf[0], R.Phi(R.leaf[0], R.leaf[0])));
 588   R.ReducePhiIterative(R.leaf[0],
 589                        R.Phi(R.Phi(R.leaf[0], R.leaf[0]), R.leaf[0]));
 590 }
 591
 592
 593 TEST(CReducePhi_iterative4) {
 594   ControlReducerTester R;
 595
 596   R.ReducePhiIterative(R.leaf[0], R.Phi(R.Phi(R.leaf[0], R.leaf[0]),
 597                                         R.Phi(R.leaf[0], R.leaf[0])));
 598
 599   Node* p1 = R.Phi(R.leaf[0], R.leaf[0]);
 600   R.ReducePhiIterative(R.leaf[0], R.Phi(p1, p1));
 601
 602   Node* p2 = R.Phi(R.leaf[0], R.leaf[0], R.leaf[0]);
 603   R.ReducePhiIterative(R.leaf[0], R.Phi(p2, p2, p2));
 604
 605   Node* p3 = R.Phi(R.leaf[0], R.leaf[0], R.leaf[0]);
 606   R.ReducePhiIterative(R.leaf[0], R.Phi(p3, p3, R.leaf[0]));
 607 }
 608
 609
 610 TEST(CReducePhi_iterative_self1) {
 611   ControlReducerTester R;
 612
 613   R.ReducePhiIterative(R.leaf[0], R.Phi(R.leaf[0], R.Phi(R.leaf[0], R.self)));
 614   R.ReducePhiIterative(R.leaf[0], R.Phi(R.Phi(R.leaf[0], R.self), R.leaf[0]));
 615 }
 616
 617
 618 TEST(CReducePhi_iterative_self2) {
 619   ControlReducerTester R;
 620
 621   R.ReducePhiIterative(
 622       R.leaf[0], R.Phi(R.Phi(R.leaf[0], R.self), R.Phi(R.leaf[0], R.self)));
 623   R.ReducePhiIterative(
 624       R.leaf[0], R.Phi(R.Phi(R.self, R.leaf[0]), R.Phi(R.self, R.leaf[0])));
 625
 626   Node* p1 = R.Phi(R.leaf[0], R.self);
 627   R.ReducePhiIterative(R.leaf[0], R.Phi(p1, p1));
 628
 629   Node* p2 = R.Phi(R.self, R.leaf[0]);
 630   R.ReducePhiIterative(R.leaf[0], R.Phi(p2, p2));
 631 }
 632
 633
 634 TEST(EReducePhi1) {
 635   ControlReducerTester R;
 636
 637   R.ReducePhi(R.leaf[0], R.EffectPhi(R.leaf[0]));
 638   R.ReducePhi(R.leaf[1], R.EffectPhi(R.leaf[1]));
 639   R.ReducePhi(R.leaf[2], R.EffectPhi(R.leaf[2]));
 640   R.ReducePhi(R.leaf[3], R.EffectPhi(R.leaf[3]));
 641 }
 642
 643
 644 TEST(EReducePhi1_dead) {
 645   ControlReducerTester R;
 646
 647   R.ReducePhi(R.leaf[0], R.EffectPhi(R.leaf[0], R.dead));
 648   R.ReducePhi(R.leaf[1], R.EffectPhi(R.leaf[1], R.dead));
 649   R.ReducePhi(R.leaf[2], R.EffectPhi(R.leaf[2], R.dead));
 650   R.ReducePhi(R.leaf[3], R.EffectPhi(R.leaf[3], R.dead));
 651
 652   R.ReducePhi(R.leaf[0], R.EffectPhi(R.dead, R.leaf[0]));
 653   R.ReducePhi(R.leaf[1], R.EffectPhi(R.dead, R.leaf[1]));
 654   R.ReducePhi(R.leaf[2], R.EffectPhi(R.dead, R.leaf[2]));
 655   R.ReducePhi(R.leaf[3], R.EffectPhi(R.dead, R.leaf[3]));
 656 }
 657
 658
 659 TEST(EReducePhi1_dead2) {
 660   ControlReducerTester R;
 661
 662   R.ReducePhi(R.leaf[0], R.EffectPhi(R.leaf[0], R.dead, R.dead));
 663   R.ReducePhi(R.leaf[0], R.EffectPhi(R.dead, R.leaf[0], R.dead));
 664   R.ReducePhi(R.leaf[0], R.EffectPhi(R.dead, R.dead, R.leaf[0]));
 665 }
 666
 667
 668 TEST(CMergeReduce_simple1) {
 669   ControlReducerTester R;
 670
 671   Node* merge = R.graph.NewNode(R.common.Merge(1), R.start);
 672   R.ReduceMerge(R.start, merge);
 673 }
 674
 675
 676 TEST(CMergeReduce_simple2) {
 677   ControlReducerTester R;
 678
 679   Node* merge1 = R.graph.NewNode(R.common.Merge(1), R.start);
 680   Node* merge2 = R.graph.NewNode(R.common.Merge(1), merge1);
 681   R.ReduceMerge(merge1, merge2);
 682   R.ReduceMergeIterative(R.start, merge2);
 683 }
 684
 685
 686 TEST(CMergeReduce_none1) {
 687   ControlReducerTester R;
 688
 689   Node* merge = R.graph.NewNode(R.common.Merge(2), R.start, R.start);
 690   R.ReduceMerge(merge, merge);
 691 }
 692
 693
 694 TEST(CMergeReduce_none2) {
 695   ControlReducerTester R;
 696
 697   Node* t = R.graph.NewNode(R.common.IfTrue(), R.start);
 698   Node* f = R.graph.NewNode(R.common.IfFalse(), R.start);
 699   Node* merge = R.graph.NewNode(R.common.Merge(2), t, f);
 700   R.ReduceMerge(merge, merge);
 701 }
 702
 703
 704 TEST(CMergeReduce_self3) {
 705   ControlReducerTester R;
 706
 707   Node* merge =
 708       R.SetSelfReferences(R.graph.NewNode(R.common.Merge(2), R.start, R.self));
 709   R.ReduceMerge(merge, merge);
 710 }
 711
 712
 713 TEST(CMergeReduce_dead1) {
 714   ControlReducerTester R;
 715
 716   Node* merge = R.graph.NewNode(R.common.Merge(2), R.start, R.dead);
 717   R.ReduceMerge(R.start, merge);
 718 }
 719
 720
 721 TEST(CMergeReduce_dead2) {
 722   ControlReducerTester R;
 723
 724   Node* merge1 = R.graph.NewNode(R.common.Merge(1), R.start);
 725   Node* merge2 = R.graph.NewNode(R.common.Merge(2), merge1, R.dead);
 726   R.ReduceMerge(merge1, merge2);
 727   R.ReduceMergeIterative(R.start, merge2);
 728 }
 729
 730
 731 TEST(CMergeReduce_dead_rm1a) {
 732   ControlReducerTester R;
 733
 734   for (int i = 0; i < 3; i++) {
 735     Node* merge = R.graph.NewNode(R.common.Merge(3), R.start, R.start, R.start);
 736     merge->ReplaceInput(i, R.dead);
 737     R.ReduceMerge(merge, merge);
 738     CheckMerge(merge, R.start, R.start);
 739   }
 740 }
 741
 742
 743 TEST(CMergeReduce_dead_rm1b) {
 744   ControlReducerTester R;
 745
 746   Node* t = R.graph.NewNode(R.common.IfTrue(), R.start);
 747   Node* f = R.graph.NewNode(R.common.IfFalse(), R.start);
 748   for (int i = 0; i < 2; i++) {
 749     Node* merge = R.graph.NewNode(R.common.Merge(3), R.dead, R.dead, R.dead);
 750     for (int j = i + 1; j < 3; j++) {
 751       merge->ReplaceInput(i, t);
 752       merge->ReplaceInput(j, f);
 753       R.ReduceMerge(merge, merge);
 754       CheckMerge(merge, t, f);
 755     }
 756   }
 757 }
 758
 759
 760 TEST(CMergeReduce_dead_rm2) {
 761   ControlReducerTester R;
 762
 763   for (int i = 0; i < 3; i++) {
 764     Node* merge = R.graph.NewNode(R.common.Merge(3), R.dead, R.dead, R.dead);
 765     merge->ReplaceInput(i, R.start);
 766     R.ReduceMerge(R.start, merge);
 767   }
 768 }
 769
 770
 771 TEST(CLoopReduce_dead_rm1) {
 772   ControlReducerTester R;
 773
 774   for (int i = 0; i < 3; i++) {
 775     Node* loop = R.graph.NewNode(R.common.Loop(3), R.dead, R.start, R.start);
 776     R.ReduceMerge(loop, loop);
 777     CheckLoop(loop, R.start, R.start);
 778   }
 779 }
 780
 781
 782 TEST(CMergeReduce_edit_phi1) {
 783   ControlReducerTester R;
 784
 785   for (int i = 0; i < 3; i++) {
 786     Node* merge = R.graph.NewNode(R.common.Merge(3), R.start, R.start, R.start);
 787     merge->ReplaceInput(i, R.dead);
 788     Node* phi = R.graph.NewNode(R.common.Phi(kMachAnyTagged, 3), R.leaf[0],
 789                                 R.leaf[1], R.leaf[2], merge);
 790     R.ReduceMerge(merge, merge);
 791     CHECK_EQ(IrOpcode::kPhi, phi->opcode());
 792     CHECK_EQ(2, phi->op()->ValueInputCount());
 793     CHECK_EQ(3, phi->InputCount());
 794     CHECK_EQ(R.leaf[i < 1 ? 1 : 0], phi->InputAt(0));
 795     CHECK_EQ(R.leaf[i < 2 ? 2 : 1], phi->InputAt(1));
 796     CHECK_EQ(merge, phi->InputAt(2));
 797   }
 798 }
 799
 800
 801 TEST(CMergeReduce_edit_effect_phi1) {
 802   ControlReducerTester R;
 803
 804   for (int i = 0; i < 3; i++) {
 805     Node* merge = R.graph.NewNode(R.common.Merge(3), R.start, R.start, R.start);
 806     merge->ReplaceInput(i, R.dead);
 807     Node* phi = R.graph.NewNode(R.common.EffectPhi(3), R.leaf[0], R.leaf[1],
 808                                 R.leaf[2], merge);
 809     R.ReduceMerge(merge, merge);
 810     CHECK_EQ(IrOpcode::kEffectPhi, phi->opcode());
 811     CHECK_EQ(0, phi->op()->ValueInputCount());
 812     CHECK_EQ(2, phi->op()->EffectInputCount());
 813     CHECK_EQ(3, phi->InputCount());
 814     CHECK_EQ(R.leaf[i < 1 ? 1 : 0], phi->InputAt(0));
 815     CHECK_EQ(R.leaf[i < 2 ? 2 : 1], phi->InputAt(1));
 816     CHECK_EQ(merge, phi->InputAt(2));
 817   }
 818 }
 819
 820
 821 static const int kSelectorSize = 4;
 822
 823 // Helper to select K of N nodes according to a mask, useful for the test below.
 824 struct Selector {
 825   int mask;
 826   int count;
 827   explicit Selector(int m) {
 828     mask = m;
 829     count = v8::base::bits::CountPopulation32(m);
 830   }
 831   bool is_selected(int i) { return (mask & (1 << i)) != 0; }
 832   void CheckNode(Node* node, IrOpcode::Value opcode, Node** inputs,
 833                  Node* control) {
 834     CHECK_EQ(opcode, node->opcode());
 835     CHECK_EQ(count + (control != NULL ? 1 : 0), node->InputCount());
 836     int index = 0;
 837     for (int i = 0; i < kSelectorSize; i++) {
 838       if (mask & (1 << i)) {
 839         CHECK_EQ(inputs[i], node->InputAt(index++));
 840       }
 841     }
 842     CHECK_EQ(count, index);
 843     if (control != NULL) CHECK_EQ(control, node->InputAt(index++));
 844   }
 845   int single_index() {
 846     CHECK_EQ(1, count);
 847     return WhichPowerOf2(mask);
 848   }
 849 };
 850
 851
 852 TEST(CMergeReduce_exhaustive_4) {
 853   ControlReducerTester R;
 854   Node* controls[] = {
 855       R.graph.NewNode(R.common.Start(1)), R.graph.NewNode(R.common.Start(2)),
 856       R.graph.NewNode(R.common.Start(3)), R.graph.NewNode(R.common.Start(4))};
 857   Node* values[] = {R.jsgraph.Int32Constant(11), R.jsgraph.Int32Constant(22),
 858                     R.jsgraph.Int32Constant(33), R.jsgraph.Int32Constant(44)};
 859   Node* effects[] = {
 860       R.jsgraph.Float64Constant(123.4), R.jsgraph.Float64Constant(223.4),
 861       R.jsgraph.Float64Constant(323.4), R.jsgraph.Float64Constant(423.4)};
 862
 863   for (int mask = 0; mask < (1 << (kSelectorSize - 1)); mask++) {
 864     // Reduce a single merge with a given mask.
 865     Node* merge = R.graph.NewNode(R.common.Merge(4), controls[0], controls[1],
 866                                   controls[2], controls[3]);
 867     Node* phi = R.graph.NewNode(R.common.Phi(kMachAnyTagged, 4), values[0],
 868                                 values[1], values[2], values[3], merge);
 869     Node* ephi = R.graph.NewNode(R.common.EffectPhi(4), effects[0], effects[1],
 870                                  effects[2], effects[3], merge);
 871
 872     Node* phi_use =
 873         R.graph.NewNode(R.common.Phi(kMachAnyTagged, 1), phi, R.start);
 874     Node* ephi_use = R.graph.NewNode(R.common.EffectPhi(1), ephi, R.start);
 875
 876     Selector selector(mask);
 877
 878     for (int i = 0; i < kSelectorSize; i++) {  // set up dead merge inputs.
 879       if (!selector.is_selected(i)) merge->ReplaceInput(i, R.dead);
 880     }
 881
 882     Node* result = ControlReducer::ReduceMerge(&R.jsgraph, &R.common, merge);
 883
 884     int count = selector.count;
 885     if (count == 0) {
 886       // result should be dead.
 887       CHECK_EQ(IrOpcode::kDead, result->opcode());
 888     } else if (count == 1) {
 889       // merge should be replaced with one of the controls.
 890       CHECK_EQ(controls[selector.single_index()], result);
 891       // Phis should have been directly replaced.
 892       CHECK_EQ(values[selector.single_index()], phi_use->InputAt(0));
 893       CHECK_EQ(effects[selector.single_index()], ephi_use->InputAt(0));
 894     } else {
 895       // Otherwise, nodes should be edited in place.
 896       CHECK_EQ(merge, result);
 897       selector.CheckNode(merge, IrOpcode::kMerge, controls, NULL);
 898       selector.CheckNode(phi, IrOpcode::kPhi, values, merge);
 899       selector.CheckNode(ephi, IrOpcode::kEffectPhi, effects, merge);
 900       CHECK_EQ(phi, phi_use->InputAt(0));
 901       CHECK_EQ(ephi, ephi_use->InputAt(0));
 902       CHECK_EQ(count, phi->op()->ValueInputCount());
 903       CHECK_EQ(count + 1, phi->InputCount());
 904       CHECK_EQ(count, ephi->op()->EffectInputCount());
 905       CHECK_EQ(count + 1, ephi->InputCount());
 906     }
 907   }
 908 }
 909
 910
 911 TEST(CMergeReduce_edit_many_phis1) {
 912   ControlReducerTester R;
 913
 914   const int kPhiCount = 10;
 915   Node* phis[kPhiCount];
 916
 917   for (int i = 0; i < 3; i++) {
 918     Node* merge = R.graph.NewNode(R.common.Merge(3), R.start, R.start, R.start);
 919     merge->ReplaceInput(i, R.dead);
 920     for (int j = 0; j < kPhiCount; j++) {
 921       phis[j] = R.graph.NewNode(R.common.Phi(kMachAnyTagged, 3), R.leaf[0],
 922                                 R.leaf[1], R.leaf[2], merge);
 923     }
 924     R.ReduceMerge(merge, merge);
 925     for (int j = 0; j < kPhiCount; j++) {
 926       Node* phi = phis[j];
 927       CHECK_EQ(IrOpcode::kPhi, phi->opcode());
 928       CHECK_EQ(2, phi->op()->ValueInputCount());
 929       CHECK_EQ(3, phi->InputCount());
 930       CHECK_EQ(R.leaf[i < 1 ? 1 : 0], phi->InputAt(0));
 931       CHECK_EQ(R.leaf[i < 2 ? 2 : 1], phi->InputAt(1));
 932       CHECK_EQ(merge, phi->InputAt(2));
 933     }
 934   }
 935 }
 936
 937
 938 TEST(CMergeReduce_simple_chain1) {
 939   ControlReducerTester R;
 940   for (int i = 0; i < 5; i++) {
 941     Node* merge = R.graph.NewNode(R.common.Merge(1), R.start);
 942     for (int j = 0; j < i; j++) {
 943       merge = R.graph.NewNode(R.common.Merge(1), merge);
 944     }
 945     R.ReduceMergeIterative(R.start, merge);
 946   }
 947 }
 948
 949
 950 TEST(CMergeReduce_dead_chain1) {
 951   ControlReducerTester R;
 952   for (int i = 0; i < 5; i++) {
 953     Node* merge = R.graph.NewNode(R.common.Merge(1), R.dead);
 954     for (int j = 0; j < i; j++) {
 955       merge = R.graph.NewNode(R.common.Merge(1), merge);
 956     }
 957     Node* end = R.graph.NewNode(R.common.End(), merge);
 958     R.graph.SetEnd(end);
 959     R.ReduceGraph();
 960     CHECK(merge->IsDead());
 961     CHECK(!end->InputAt(0));  // end dies.
 962   }
 963 }
 964
 965
 966 TEST(CMergeReduce_dead_chain2) {
 967   ControlReducerTester R;
 968   for (int i = 0; i < 5; i++) {
 969     Node* merge = R.graph.NewNode(R.common.Merge(1), R.start);
 970     for (int j = 0; j < i; j++) {
 971       merge = R.graph.NewNode(R.common.Merge(2), merge, R.dead);
 972     }
 973     R.ReduceMergeIterative(R.start, merge);
 974   }
 975 }
 976
 977
 978 struct Branch {
 979   Node* branch;
 980   Node* if_true;
 981   Node* if_false;
 982
 983   Branch(ControlReducerTester& R, Node* cond, Node* control = NULL) {
 984     if (control == NULL) control = R.start;
 985     branch = R.graph.NewNode(R.common.Branch(), cond, control);
 986     if_true = R.graph.NewNode(R.common.IfTrue(), branch);
 987     if_false = R.graph.NewNode(R.common.IfFalse(), branch);
 988   }
 989 };
 990
 991
 992 // TODO(titzer): use the diamonds from src/compiler/diamond.h here.
 993 struct Diamond {
 994   Node* branch;
 995   Node* if_true;
 996   Node* if_false;
 997   Node* merge;
 998   Node* phi;
 999
1000   Diamond(ControlReducerTester& R, Node* cond) {
1001     branch = R.graph.NewNode(R.common.Branch(), cond, R.start);
1002     if_true = R.graph.NewNode(R.common.IfTrue(), branch);
1003     if_false = R.graph.NewNode(R.common.IfFalse(), branch);
1004     merge = R.graph.NewNode(R.common.Merge(2), if_true, if_false);
1005     phi = NULL;
1006   }
1007
1008   Diamond(ControlReducerTester& R, Node* cond, Node* tv, Node* fv) {
1009     branch = R.graph.NewNode(R.common.Branch(), cond, R.start);
1010     if_true = R.graph.NewNode(R.common.IfTrue(), branch);
1011     if_false = R.graph.NewNode(R.common.IfFalse(), branch);
1012     merge = R.graph.NewNode(R.common.Merge(2), if_true, if_false);
1013     phi = R.graph.NewNode(R.common.Phi(kMachAnyTagged, 2), tv, fv, merge);
1014   }
1015
1016   void chain(Diamond& that) { branch->ReplaceInput(1, that.merge); }
1017
1018   // Nest {this} into either the if_true or if_false branch of {that}.
1019   void nest(Diamond& that, bool if_true) {
1020     if (if_true) {
1021       branch->ReplaceInput(1, that.if_true);
1022       that.merge->ReplaceInput(0, merge);
1023     } else {
1024       branch->ReplaceInput(1, that.if_false);
1025       that.merge->ReplaceInput(1, merge);
1026     }
1027   }
1028 };
1029
1030
1031 struct While {
1032   Node* branch;
1033   Node* if_true;
1034   Node* exit;
1035   Node* loop;
1036
1037   While(ControlReducerTester& R, Node* cond) {
1038     loop = R.graph.NewNode(R.common.Loop(2), R.start, R.start);
1039     branch = R.graph.NewNode(R.common.Branch(), cond, loop);
1040     if_true = R.graph.NewNode(R.common.IfTrue(), branch);
1041     exit = R.graph.NewNode(R.common.IfFalse(), branch);
1042     loop->ReplaceInput(1, if_true);
1043   }
1044
1045   void chain(Node* control) { loop->ReplaceInput(0, control); }
1046 };
1047
1048
1049 TEST(CBranchReduce_none1) {
1050   ControlReducerTester R;
1051   Diamond d(R, R.p0);
1052   R.ReduceBranch(kUnknown, d.branch);
1053 }
1054
1055
1056 TEST(CBranchReduce_none2) {
1057   ControlReducerTester R;
1058   Diamond d1(R, R.p0);
1059   Diamond d2(R, R.p0);
1060   d2.chain(d1);
1061   R.ReduceBranch(kUnknown, d2.branch);
1062 }
1063
1064
1065 TEST(CBranchReduce_true) {
1066   ControlReducerTester R;
1067   Node* true_values[] = {
1068       R.one,                               R.jsgraph.Int32Constant(2),
1069       R.jsgraph.Int32Constant(0x7fffffff), R.jsgraph.Constant(1.0),
1070       R.jsgraph.Constant(22.1),            R.jsgraph.TrueConstant()};
1071
1072   for (size_t i = 0; i < arraysize(true_values); i++) {
1073     Diamond d(R, true_values[i]);
1074     R.ReduceBranch(kTrue, d.branch);
1075   }
1076 }
1077
1078
1079 TEST(CBranchReduce_false) {
1080   ControlReducerTester R;
1081   Node* false_values[] = {R.zero, R.jsgraph.Constant(0.0),
1082                           R.jsgraph.Constant(-0.0), R.jsgraph.FalseConstant()};
1083
1084   for (size_t i = 0; i < arraysize(false_values); i++) {
1085     Diamond d(R, false_values[i]);
1086     R.ReduceBranch(kFalse, d.branch);
1087   }
1088 }
1089
1090
1091 TEST(CDiamondReduce_true) {
1092   ControlReducerTester R;
1093   Diamond d1(R, R.one);
1094   R.ReduceMergeIterative(R.start, d1.merge);
1095 }
1096
1097
1098 TEST(CDiamondReduce_false) {
1099   ControlReducerTester R;
1100   Diamond d2(R, R.zero);
1101   R.ReduceMergeIterative(R.start, d2.merge);
1102 }
1103
1104
1105 TEST(CChainedDiamondsReduce_true_false) {
1106   ControlReducerTester R;
1107   Diamond d1(R, R.one);
1108   Diamond d2(R, R.zero);
1109   d2.chain(d1);
1110
1111   R.ReduceMergeIterative(R.start, d2.merge);
1112 }
1113
1114
1115 TEST(CChainedDiamondsReduce_x_false) {
1116   ControlReducerTester R;
1117   Diamond d1(R, R.p0);
1118   Diamond d2(R, R.zero);
1119   d2.chain(d1);
1120
1121   R.ReduceMergeIterative(d1.merge, d2.merge);
1122 }
1123
1124
1125 TEST(CChainedDiamondsReduce_false_x) {
1126   ControlReducerTester R;
1127   Diamond d1(R, R.zero);
1128   Diamond d2(R, R.p0);
1129   d2.chain(d1);
1130
1131   R.ReduceMergeIterative(d2.merge, d2.merge);
1132   CheckInputs(d2.branch, R.p0, R.start);
1133 }
1134
1135
1136 TEST(CChainedDiamondsReduce_phi1) {
1137   ControlReducerTester R;
1138   Diamond d1(R, R.zero, R.one, R.zero);  // foldable branch, phi.
1139   Diamond d2(R, d1.phi);
1140   d2.chain(d1);
1141
1142   R.ReduceMergeIterative(R.start, d2.merge);
1143 }
1144
1145
1146 TEST(CChainedDiamondsReduce_phi2) {
1147   ControlReducerTester R;
1148   Diamond d1(R, R.p0, R.one, R.one);  // redundant phi.
1149   Diamond d2(R, d1.phi);
1150   d2.chain(d1);
1151
1152   R.ReduceMergeIterative(d1.merge, d2.merge);
1153 }
1154
1155
1156 TEST(CNestedDiamondsReduce_true_true_false) {
1157   ControlReducerTester R;
1158   Diamond d1(R, R.one);
1159   Diamond d2(R, R.zero);
1160   d2.nest(d1, true);
1161
1162   R.ReduceMergeIterative(R.start, d1.merge);
1163 }
1164
1165
1166 TEST(CNestedDiamondsReduce_false_true_false) {
1167   ControlReducerTester R;
1168   Diamond d1(R, R.one);
1169   Diamond d2(R, R.zero);
1170   d2.nest(d1, false);
1171
1172   R.ReduceMergeIterative(R.start, d1.merge);
1173 }
1174
1175
1176 TEST(CNestedDiamonds_xyz) {
1177   ControlReducerTester R;
1178
1179   for (int a = 0; a < 2; a++) {
1180     for (int b = 0; b < 2; b++) {
1181       for (int c = 0; c < 2; c++) {
1182         Diamond d1(R, R.jsgraph.Int32Constant(a));
1183         Diamond d2(R, R.jsgraph.Int32Constant(b));
1184         d2.nest(d1, c);
1185
1186         R.ReduceMergeIterative(R.start, d1.merge);
1187       }
1188     }
1189   }
1190 }
1191
1192
1193 TEST(CDeadLoop1) {
1194   ControlReducerTester R;
1195
1196   Node* loop = R.graph.NewNode(R.common.Loop(1), R.start);
1197   Branch b(R, R.p0, loop);
1198   loop->ReplaceInput(0, b.if_true);  // loop is not connected to start.
1199   Node* merge = R.graph.NewNode(R.common.Merge(2), R.start, b.if_false);
1200   R.ReduceMergeIterative(R.start, merge);
1201   CHECK(b.if_true->IsDead());
1202   CHECK(b.if_false->IsDead());
1203 }
1204
1205
1206 TEST(CDeadLoop2) {
1207   ControlReducerTester R;
1208
1209   While w(R, R.p0);
1210   Diamond d(R, R.zero);
1211   // if (0) { while (p0) ; } else { }
1212   w.branch->ReplaceInput(1, d.if_true);
1213   d.merge->ReplaceInput(0, w.exit);
1214
1215   R.ReduceMergeIterative(R.start, d.merge);
1216   CHECK(d.if_true->IsDead());
1217   CHECK(d.if_false->IsDead());
1218 }
1219
1220
1221 TEST(Return1) {
1222   ControlReducerTester R;
1223   Node* ret = R.Return(R.one, R.start, R.start);
1224   R.ReduceGraph();
1225   CheckInputs(R.graph.end(), ret);
1226   CheckInputs(ret, R.one, R.start, R.start);
1227 }
1228
1229
1230 TEST(Return2) {
1231   ControlReducerTester R;
1232   Diamond d(R, R.one);
1233   Node* ret = R.Return(R.half, R.start, d.merge);
1234   R.ReduceGraph();
1235   CHECK(d.branch->IsDead());
1236   CHECK(d.if_true->IsDead());
1237   CHECK(d.if_false->IsDead());
1238   CHECK(d.merge->IsDead());
1239
1240   CheckInputs(R.graph.end(), ret);
1241   CheckInputs(ret, R.half, R.start, R.start);
1242 }
1243
1244
1245 TEST(Return_true1) {
1246   ControlReducerTester R;
1247   Diamond d(R, R.one, R.half, R.zero);
1248   Node* ret = R.Return(d.phi, R.start, d.merge);
1249   R.ReduceGraph();
1250   CHECK(d.branch->IsDead());
1251   CHECK(d.if_true->IsDead());
1252   CHECK(d.if_false->IsDead());
1253   CHECK(d.merge->IsDead());
1254   CHECK(d.phi->IsDead());
1255
1256   CheckInputs(R.graph.end(), ret);
1257   CheckInputs(ret, R.half, R.start, R.start);
1258 }
1259
1260
1261 TEST(Return_false1) {
1262   ControlReducerTester R;
1263   Diamond d(R, R.zero, R.one, R.half);
1264   Node* ret = R.Return(d.phi, R.start, d.merge);
1265   R.ReduceGraph();
1266   CHECK(d.branch->IsDead());
1267   CHECK(d.if_true->IsDead());
1268   CHECK(d.if_false->IsDead());
1269   CHECK(d.merge->IsDead());
1270   CHECK(d.phi->IsDead());
1271
1272   CheckInputs(R.graph.end(), ret);
1273   CheckInputs(ret, R.half, R.start, R.start);
1274 }
1275
1276
1277 void CheckDeadDiamond(Diamond& d) {
1278   CHECK(d.branch->IsDead());
1279   CHECK(d.if_true->IsDead());
1280   CHECK(d.if_false->IsDead());
1281   CHECK(d.merge->IsDead());
1282   if (d.phi != NULL) CHECK(d.phi->IsDead());
1283 }
1284
1285
1286 void CheckLiveDiamond(Diamond& d, bool live_phi = true) {
1287   CheckInputs(d.merge, d.if_true, d.if_false);
1288   CheckInputs(d.if_true, d.branch);
1289   CheckInputs(d.if_false, d.branch);
1290   if (d.phi != NULL) {
1291     if (live_phi) {
1292       CHECK_EQ(3, d.phi->InputCount());
1293       CHECK_EQ(d.merge, d.phi->InputAt(2));
1294     } else {
1295       CHECK(d.phi->IsDead());
1296     }
1297   }
1298 }
1299
1300
1301 TEST(Return_effect1) {
1302   ControlReducerTester R;
1303   Diamond d(R, R.one);
1304   Node* e1 = R.jsgraph.Float64Constant(-100.1);
1305   Node* e2 = R.jsgraph.Float64Constant(+100.1);
1306   Node* effect = R.graph.NewNode(R.common.EffectPhi(2), e1, e2, d.merge);
1307   Node* ret = R.Return(R.p0, effect, d.merge);
1308   R.ReduceGraph();
1309   CheckDeadDiamond(d);
1310   CHECK(effect->IsDead());
1311
1312   CheckInputs(R.graph.end(), ret);
1313   CheckInputs(ret, R.p0, e1, R.start);
1314 }
1315
1316
1317 TEST(Return_nested_diamonds1) {
1318   ControlReducerTester R;
1319   Diamond d1(R, R.p0, R.one, R.zero);
1320   Diamond d2(R, R.p0);
1321   Diamond d3(R, R.p0);
1322
1323   d2.nest(d1, true);
1324   d3.nest(d1, false);
1325
1326   Node* ret = R.Return(d1.phi, R.start, d1.merge);
1327
1328   R.ReduceGraph();  // nothing should happen.
1329
1330   CheckInputs(ret, d1.phi, R.start, d1.merge);
1331   CheckInputs(d1.phi, R.one, R.zero, d1.merge);
1332   CheckInputs(d1.merge, d2.merge, d3.merge);
1333   CheckLiveDiamond(d2);
1334   CheckLiveDiamond(d3);
1335 }
1336
1337
1338 TEST(Return_nested_diamonds_true1) {
1339   ControlReducerTester R;
1340   Diamond d1(R, R.one, R.one, R.zero);
1341   Diamond d2(R, R.p0);
1342   Diamond d3(R, R.p0);
1343
1344   d2.nest(d1, true);
1345   d3.nest(d1, false);
1346
1347   Node* ret = R.Return(d1.phi, R.start, d1.merge);
1348
1349   R.ReduceGraph();  // d1 gets folded true.
1350
1351   CheckInputs(ret, R.one, R.start, d2.merge);
1352   CheckInputs(d2.branch, R.p0, R.start);
1353   CheckDeadDiamond(d1);
1354   CheckLiveDiamond(d2);
1355   CheckDeadDiamond(d3);
1356 }
1357
1358
1359 TEST(Return_nested_diamonds_false1) {
1360   ControlReducerTester R;
1361   Diamond d1(R, R.zero, R.one, R.zero);
1362   Diamond d2(R, R.p0);
1363   Diamond d3(R, R.p0);
1364
1365   d2.nest(d1, true);
1366   d3.nest(d1, false);
1367
1368   Node* ret = R.Return(d1.phi, R.start, d1.merge);
1369
1370   R.ReduceGraph();  // d1 gets folded false.
1371
1372   CheckInputs(ret, R.zero, R.start, d3.merge);
1373   CheckInputs(d3.branch, R.p0, R.start);
1374   CheckDeadDiamond(d1);
1375   CheckDeadDiamond(d2);
1376   CheckLiveDiamond(d3);
1377 }
1378
1379
1380 TEST(Return_nested_diamonds_true_true1) {
1381   ControlReducerTester R;
1382   Diamond d1(R, R.one, R.one, R.zero);
1383   Diamond d2(R, R.one);
1384   Diamond d3(R, R.p0);
1385
1386   d2.nest(d1, true);
1387   d3.nest(d1, false);
1388
1389   Node* ret = R.Return(d1.phi, R.start, d1.merge);
1390
1391   R.ReduceGraph();  // d1 and d2 both get folded true.
1392
1393   CheckInputs(ret, R.one, R.start, R.start);
1394   CheckDeadDiamond(d1);
1395   CheckDeadDiamond(d2);
1396   CheckDeadDiamond(d3);
1397 }
1398
1399
1400 TEST(Return_nested_diamonds_true_false1) {
1401   ControlReducerTester R;
1402   Diamond d1(R, R.one, R.one, R.zero);
1403   Diamond d2(R, R.zero);
1404   Diamond d3(R, R.p0);
1405
1406   d2.nest(d1, true);
1407   d3.nest(d1, false);
1408
1409   Node* ret = R.Return(d1.phi, R.start, d1.merge);
1410
1411   R.ReduceGraph();  // d1 gets folded true and d2 gets folded false.
1412
1413   CheckInputs(ret, R.one, R.start, R.start);
1414   CheckDeadDiamond(d1);
1415   CheckDeadDiamond(d2);
1416   CheckDeadDiamond(d3);
1417 }
1418
1419
1420 TEST(Return_nested_diamonds2) {
1421   ControlReducerTester R;
1422   Node* x2 = R.jsgraph.Float64Constant(11.1);
1423   Node* y2 = R.jsgraph.Float64Constant(22.2);
1424   Node* x3 = R.jsgraph.Float64Constant(33.3);
1425   Node* y3 = R.jsgraph.Float64Constant(44.4);
1426
1427   Diamond d2(R, R.p0, x2, y2);
1428   Diamond d3(R, R.p0, x3, y3);
1429   Diamond d1(R, R.p0, d2.phi, d3.phi);
1430
1431   d2.nest(d1, true);
1432   d3.nest(d1, false);
1433
1434   Node* ret = R.Return(d1.phi, R.start, d1.merge);
1435
1436   R.ReduceGraph();  // nothing should happen.
1437
1438   CheckInputs(ret, d1.phi, R.start, d1.merge);
1439   CheckInputs(d1.phi, d2.phi, d3.phi, d1.merge);
1440   CheckInputs(d1.merge, d2.merge, d3.merge);
1441   CheckLiveDiamond(d2);
1442   CheckLiveDiamond(d3);
1443 }
1444
1445
1446 TEST(Return_nested_diamonds_true2) {
1447   ControlReducerTester R;
1448   Node* x2 = R.jsgraph.Float64Constant(11.1);
1449   Node* y2 = R.jsgraph.Float64Constant(22.2);
1450   Node* x3 = R.jsgraph.Float64Constant(33.3);
1451   Node* y3 = R.jsgraph.Float64Constant(44.4);
1452
1453   Diamond d2(R, R.p0, x2, y2);
1454   Diamond d3(R, R.p0, x3, y3);
1455   Diamond d1(R, R.one, d2.phi, d3.phi);
1456
1457   d2.nest(d1, true);
1458   d3.nest(d1, false);
1459
1460   Node* ret = R.Return(d1.phi, R.start, d1.merge);
1461
1462   R.ReduceGraph();  // d1 gets folded true.
1463
1464   CheckInputs(ret, d2.phi, R.start, d2.merge);
1465   CheckInputs(d2.branch, R.p0, R.start);
1466   CheckDeadDiamond(d1);
1467   CheckLiveDiamond(d2);
1468   CheckDeadDiamond(d3);
1469 }
1470
1471
1472 TEST(Return_nested_diamonds_true_true2) {
1473   ControlReducerTester R;
1474   Node* x2 = R.jsgraph.Float64Constant(11.1);
1475   Node* y2 = R.jsgraph.Float64Constant(22.2);
1476   Node* x3 = R.jsgraph.Float64Constant(33.3);
1477   Node* y3 = R.jsgraph.Float64Constant(44.4);
1478
1479   Diamond d2(R, R.one, x2, y2);
1480   Diamond d3(R, R.p0, x3, y3);
1481   Diamond d1(R, R.one, d2.phi, d3.phi);
1482
1483   d2.nest(d1, true);
1484   d3.nest(d1, false);
1485
1486   Node* ret = R.Return(d1.phi, R.start, d1.merge);
1487
1488   R.ReduceGraph();  // d1 gets folded true.
1489
1490   CheckInputs(ret, x2, R.start, R.start);
1491   CheckDeadDiamond(d1);
1492   CheckDeadDiamond(d2);
1493   CheckDeadDiamond(d3);
1494 }
1495
1496
1497 TEST(Return_nested_diamonds_true_false2) {
1498   ControlReducerTester R;
1499   Node* x2 = R.jsgraph.Float64Constant(11.1);
1500   Node* y2 = R.jsgraph.Float64Constant(22.2);
1501   Node* x3 = R.jsgraph.Float64Constant(33.3);
1502   Node* y3 = R.jsgraph.Float64Constant(44.4);
1503
1504   Diamond d2(R, R.zero, x2, y2);
1505   Diamond d3(R, R.p0, x3, y3);
1506   Diamond d1(R, R.one, d2.phi, d3.phi);
1507
1508   d2.nest(d1, true);
1509   d3.nest(d1, false);
1510
1511   Node* ret = R.Return(d1.phi, R.start, d1.merge);
1512
1513   R.ReduceGraph();  // d1 gets folded true.
1514
1515   CheckInputs(ret, y2, R.start, R.start);
1516   CheckDeadDiamond(d1);
1517   CheckDeadDiamond(d2);
1518   CheckDeadDiamond(d3);
1519 }