src/v8/test/cctest/compiler/test-machine-operator-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 "test/cctest/cctest.h"
   6
   7 #include "src/base/utils/random-number-generator.h"
   8 #include "src/compiler/graph-inl.h"
   9 #include "src/compiler/js-graph.h"
  10 #include "src/compiler/machine-operator-reducer.h"
  11 #include "src/compiler/typer.h"
  12 #include "test/cctest/compiler/value-helper.h"
  13
  14 using namespace v8::internal;
  15 using namespace v8::internal::compiler;
  16
  17 template <typename T>
  18 const Operator* NewConstantOperator(CommonOperatorBuilder* common,
  19                                     volatile T value);
  20
  21 template <>
  22 const Operator* NewConstantOperator<int32_t>(CommonOperatorBuilder* common,
  23                                              volatile int32_t value) {
  24   return common->Int32Constant(value);
  25 }
  26
  27 template <>
  28 const Operator* NewConstantOperator<double>(CommonOperatorBuilder* common,
  29                                             volatile double value) {
  30   return common->Float64Constant(value);
  31 }
  32
  33
  34 template <typename T>
  35 T ValueOfOperator(const Operator* op);
  36
  37 template <>
  38 int32_t ValueOfOperator<int32_t>(const Operator* op) {
  39   CHECK_EQ(IrOpcode::kInt32Constant, op->opcode());
  40   return OpParameter<int32_t>(op);
  41 }
  42
  43 template <>
  44 double ValueOfOperator<double>(const Operator* op) {
  45   CHECK_EQ(IrOpcode::kFloat64Constant, op->opcode());
  46   return OpParameter<double>(op);
  47 }
  48
  49
  50 class ReducerTester : public HandleAndZoneScope {
  51  public:
  52   explicit ReducerTester(int num_parameters = 0)
  53       : isolate(main_isolate()),
  54         binop(NULL),
  55         unop(NULL),
  56         common(main_zone()),
  57         graph(main_zone()),
  58         javascript(main_zone()),
  59         typer(main_zone()),
  60         jsgraph(&graph, &common, &javascript, &typer, &machine),
  61         maxuint32(Constant<int32_t>(kMaxUInt32)) {
  62     Node* s = graph.NewNode(common.Start(num_parameters));
  63     graph.SetStart(s);
  64   }
  65
  66   Isolate* isolate;
  67   const Operator* binop;
  68   const Operator* unop;
  69   MachineOperatorBuilder machine;
  70   CommonOperatorBuilder common;
  71   Graph graph;
  72   JSOperatorBuilder javascript;
  73   Typer typer;
  74   JSGraph jsgraph;
  75   Node* maxuint32;
  76
  77   template <typename T>
  78   Node* Constant(volatile T value) {
  79     return graph.NewNode(NewConstantOperator<T>(&common, value));
  80   }
  81
  82   template <typename T>
  83   const T ValueOf(const Operator* op) {
  84     return ValueOfOperator<T>(op);
  85   }
  86
  87   // Check that the reduction of this binop applied to constants {a} and {b}
  88   // yields the {expect} value.
  89   template <typename T>
  90   void CheckFoldBinop(volatile T expect, volatile T a, volatile T b) {
  91     CheckFoldBinop<T>(expect, Constant<T>(a), Constant<T>(b));
  92   }
  93
  94   // Check that the reduction of this binop applied to {a} and {b} yields
  95   // the {expect} value.
  96   template <typename T>
  97   void CheckFoldBinop(volatile T expect, Node* a, Node* b) {
  98     CHECK_NE(NULL, binop);
  99     Node* n = graph.NewNode(binop, a, b);
 100     MachineOperatorReducer reducer(&jsgraph);
 101     Reduction reduction = reducer.Reduce(n);
 102     CHECK(reduction.Changed());
 103     CHECK_NE(n, reduction.replacement());
 104     CHECK_EQ(expect, ValueOf<T>(reduction.replacement()->op()));
 105   }
 106
 107   // Check that the reduction of this binop applied to {a} and {b} yields
 108   // the {expect} node.
 109   void CheckBinop(Node* expect, Node* a, Node* b) {
 110     CHECK_NE(NULL, binop);
 111     Node* n = graph.NewNode(binop, a, b);
 112     MachineOperatorReducer reducer(&jsgraph);
 113     Reduction reduction = reducer.Reduce(n);
 114     CHECK(reduction.Changed());
 115     CHECK_EQ(expect, reduction.replacement());
 116   }
 117
 118   // Check that the reduction of this binop applied to {left} and {right} yields
 119   // this binop applied to {left_expect} and {right_expect}.
 120   void CheckFoldBinop(Node* left_expect, Node* right_expect, Node* left,
 121                       Node* right) {
 122     CHECK_NE(NULL, binop);
 123     Node* n = graph.NewNode(binop, left, right);
 124     MachineOperatorReducer reducer(&jsgraph);
 125     Reduction reduction = reducer.Reduce(n);
 126     CHECK(reduction.Changed());
 127     CHECK_EQ(binop, reduction.replacement()->op());
 128     CHECK_EQ(left_expect, reduction.replacement()->InputAt(0));
 129     CHECK_EQ(right_expect, reduction.replacement()->InputAt(1));
 130   }
 131
 132   // Check that the reduction of this binop applied to {left} and {right} yields
 133   // the {op_expect} applied to {left_expect} and {right_expect}.
 134   template <typename T>
 135   void CheckFoldBinop(volatile T left_expect, const Operator* op_expect,
 136                       Node* right_expect, Node* left, Node* right) {
 137     CHECK_NE(NULL, binop);
 138     Node* n = graph.NewNode(binop, left, right);
 139     MachineOperatorReducer reducer(&jsgraph);
 140     Reduction r = reducer.Reduce(n);
 141     CHECK(r.Changed());
 142     CHECK_EQ(op_expect->opcode(), r.replacement()->op()->opcode());
 143     CHECK_EQ(left_expect, ValueOf<T>(r.replacement()->InputAt(0)->op()));
 144     CHECK_EQ(right_expect, r.replacement()->InputAt(1));
 145   }
 146
 147   // Check that the reduction of this binop applied to {left} and {right} yields
 148   // the {op_expect} applied to {left_expect} and {right_expect}.
 149   template <typename T>
 150   void CheckFoldBinop(Node* left_expect, const Operator* op_expect,
 151                       volatile T right_expect, Node* left, Node* right) {
 152     CHECK_NE(NULL, binop);
 153     Node* n = graph.NewNode(binop, left, right);
 154     MachineOperatorReducer reducer(&jsgraph);
 155     Reduction r = reducer.Reduce(n);
 156     CHECK(r.Changed());
 157     CHECK_EQ(op_expect->opcode(), r.replacement()->op()->opcode());
 158     CHECK_EQ(left_expect, r.replacement()->InputAt(0));
 159     CHECK_EQ(right_expect, ValueOf<T>(r.replacement()->InputAt(1)->op()));
 160   }
 161
 162   // Check that if the given constant appears on the left, the reducer will
 163   // swap it to be on the right.
 164   template <typename T>
 165   void CheckPutConstantOnRight(volatile T constant) {
 166     // TODO(titzer): CHECK(binop->HasProperty(Operator::kCommutative));
 167     Node* p = Parameter();
 168     Node* k = Constant<T>(constant);
 169     {
 170       Node* n = graph.NewNode(binop, k, p);
 171       MachineOperatorReducer reducer(&jsgraph);
 172       Reduction reduction = reducer.Reduce(n);
 173       CHECK(!reduction.Changed() || reduction.replacement() == n);
 174       CHECK_EQ(p, n->InputAt(0));
 175       CHECK_EQ(k, n->InputAt(1));
 176     }
 177     {
 178       Node* n = graph.NewNode(binop, p, k);
 179       MachineOperatorReducer reducer(&jsgraph);
 180       Reduction reduction = reducer.Reduce(n);
 181       CHECK(!reduction.Changed());
 182       CHECK_EQ(p, n->InputAt(0));
 183       CHECK_EQ(k, n->InputAt(1));
 184     }
 185   }
 186
 187   // Check that if the given constant appears on the left, the reducer will
 188   // *NOT* swap it to be on the right.
 189   template <typename T>
 190   void CheckDontPutConstantOnRight(volatile T constant) {
 191     CHECK(!binop->HasProperty(Operator::kCommutative));
 192     Node* p = Parameter();
 193     Node* k = Constant<T>(constant);
 194     Node* n = graph.NewNode(binop, k, p);
 195     MachineOperatorReducer reducer(&jsgraph);
 196     Reduction reduction = reducer.Reduce(n);
 197     CHECK(!reduction.Changed());
 198     CHECK_EQ(k, n->InputAt(0));
 199     CHECK_EQ(p, n->InputAt(1));
 200   }
 201
 202   Node* Parameter(int32_t index = 0) {
 203     return graph.NewNode(common.Parameter(index), graph.start());
 204   }
 205 };
 206
 207
 208 TEST(ReduceWord32And) {
 209   ReducerTester R;
 210   R.binop = R.machine.Word32And();
 211
 212   FOR_INT32_INPUTS(pl) {
 213     FOR_INT32_INPUTS(pr) {
 214       int32_t x = *pl, y = *pr;
 215       R.CheckFoldBinop<int32_t>(x & y, x, y);
 216     }
 217   }
 218
 219   R.CheckPutConstantOnRight(33);
 220   R.CheckPutConstantOnRight(44000);
 221
 222   Node* x = R.Parameter();
 223   Node* zero = R.Constant<int32_t>(0);
 224   Node* minus_1 = R.Constant<int32_t>(-1);
 225
 226   R.CheckBinop(zero, x, zero);  // x  & 0  => 0
 227   R.CheckBinop(zero, zero, x);  // 0  & x  => 0
 228   R.CheckBinop(x, x, minus_1);  // x  & -1 => 0
 229   R.CheckBinop(x, minus_1, x);  // -1 & x  => 0
 230   R.CheckBinop(x, x, x);        // x  & x  => x
 231 }
 232
 233
 234 TEST(ReduceWord32Or) {
 235   ReducerTester R;
 236   R.binop = R.machine.Word32Or();
 237
 238   FOR_INT32_INPUTS(pl) {
 239     FOR_INT32_INPUTS(pr) {
 240       int32_t x = *pl, y = *pr;
 241       R.CheckFoldBinop<int32_t>(x | y, x, y);
 242     }
 243   }
 244
 245   R.CheckPutConstantOnRight(36);
 246   R.CheckPutConstantOnRight(44001);
 247
 248   Node* x = R.Parameter();
 249   Node* zero = R.Constant<int32_t>(0);
 250   Node* minus_1 = R.Constant<int32_t>(-1);
 251
 252   R.CheckBinop(x, x, zero);           // x  & 0  => x
 253   R.CheckBinop(x, zero, x);           // 0  & x  => x
 254   R.CheckBinop(minus_1, x, minus_1);  // x  & -1 => -1
 255   R.CheckBinop(minus_1, minus_1, x);  // -1 & x  => -1
 256   R.CheckBinop(x, x, x);              // x  & x  => x
 257 }
 258
 259
 260 TEST(ReduceWord32Xor) {
 261   ReducerTester R;
 262   R.binop = R.machine.Word32Xor();
 263
 264   FOR_INT32_INPUTS(pl) {
 265     FOR_INT32_INPUTS(pr) {
 266       int32_t x = *pl, y = *pr;
 267       R.CheckFoldBinop<int32_t>(x ^ y, x, y);
 268     }
 269   }
 270
 271   R.CheckPutConstantOnRight(39);
 272   R.CheckPutConstantOnRight(4403);
 273
 274   Node* x = R.Parameter();
 275   Node* zero = R.Constant<int32_t>(0);
 276
 277   R.CheckBinop(x, x, zero);            // x ^ 0  => x
 278   R.CheckBinop(x, zero, x);            // 0 ^ x  => x
 279   R.CheckFoldBinop<int32_t>(0, x, x);  // x ^ x  => 0
 280 }
 281
 282
 283 TEST(ReduceWord32Shl) {
 284   ReducerTester R;
 285   R.binop = R.machine.Word32Shl();
 286
 287   // TODO(titzer): out of range shifts
 288   FOR_INT32_INPUTS(i) {
 289     for (int y = 0; y < 32; y++) {
 290       int32_t x = *i;
 291       R.CheckFoldBinop<int32_t>(x << y, x, y);
 292     }
 293   }
 294
 295   R.CheckDontPutConstantOnRight(44);
 296
 297   Node* x = R.Parameter();
 298   Node* zero = R.Constant<int32_t>(0);
 299
 300   R.CheckBinop(x, x, zero);  // x << 0  => x
 301 }
 302
 303
 304 TEST(ReduceWord32Shr) {
 305   ReducerTester R;
 306   R.binop = R.machine.Word32Shr();
 307
 308   // TODO(titzer): test out of range shifts
 309   FOR_UINT32_INPUTS(i) {
 310     for (uint32_t y = 0; y < 32; y++) {
 311       uint32_t x = *i;
 312       R.CheckFoldBinop<int32_t>(x >> y, x, y);
 313     }
 314   }
 315
 316   R.CheckDontPutConstantOnRight(44);
 317
 318   Node* x = R.Parameter();
 319   Node* zero = R.Constant<int32_t>(0);
 320
 321   R.CheckBinop(x, x, zero);  // x >>> 0  => x
 322 }
 323
 324
 325 TEST(ReduceWord32Sar) {
 326   ReducerTester R;
 327   R.binop = R.machine.Word32Sar();
 328
 329   // TODO(titzer): test out of range shifts
 330   FOR_INT32_INPUTS(i) {
 331     for (int32_t y = 0; y < 32; y++) {
 332       int32_t x = *i;
 333       R.CheckFoldBinop<int32_t>(x >> y, x, y);
 334     }
 335   }
 336
 337   R.CheckDontPutConstantOnRight(44);
 338
 339   Node* x = R.Parameter();
 340   Node* zero = R.Constant<int32_t>(0);
 341
 342   R.CheckBinop(x, x, zero);  // x >> 0  => x
 343 }
 344
 345
 346 TEST(ReduceWord32Equal) {
 347   ReducerTester R;
 348   R.binop = R.machine.Word32Equal();
 349
 350   FOR_INT32_INPUTS(pl) {
 351     FOR_INT32_INPUTS(pr) {
 352       int32_t x = *pl, y = *pr;
 353       R.CheckFoldBinop<int32_t>(x == y ? 1 : 0, x, y);
 354     }
 355   }
 356
 357   R.CheckPutConstantOnRight(48);
 358   R.CheckPutConstantOnRight(-48);
 359
 360   Node* x = R.Parameter(0);
 361   Node* y = R.Parameter(1);
 362   Node* zero = R.Constant<int32_t>(0);
 363   Node* sub = R.graph.NewNode(R.machine.Int32Sub(), x, y);
 364
 365   R.CheckFoldBinop<int32_t>(1, x, x);  // x == x  => 1
 366   R.CheckFoldBinop(x, y, sub, zero);   // x - y == 0  => x == y
 367   R.CheckFoldBinop(x, y, zero, sub);   // 0 == x - y  => x == y
 368 }
 369
 370
 371 TEST(ReduceInt32Add) {
 372   ReducerTester R;
 373   R.binop = R.machine.Int32Add();
 374
 375   FOR_INT32_INPUTS(pl) {
 376     FOR_INT32_INPUTS(pr) {
 377       int32_t x = *pl, y = *pr;
 378       R.CheckFoldBinop<int32_t>(x + y, x, y);  // TODO(titzer): signed overflow
 379     }
 380   }
 381
 382   R.CheckPutConstantOnRight(41);
 383   R.CheckPutConstantOnRight(4407);
 384
 385   Node* x = R.Parameter();
 386   Node* zero = R.Constant<int32_t>(0);
 387
 388   R.CheckBinop(x, x, zero);  // x + 0  => x
 389   R.CheckBinop(x, zero, x);  // 0 + x  => x
 390 }
 391
 392
 393 TEST(ReduceInt32Sub) {
 394   ReducerTester R;
 395   R.binop = R.machine.Int32Sub();
 396
 397   FOR_INT32_INPUTS(pl) {
 398     FOR_INT32_INPUTS(pr) {
 399       int32_t x = *pl, y = *pr;
 400       R.CheckFoldBinop<int32_t>(x - y, x, y);
 401     }
 402   }
 403
 404   R.CheckDontPutConstantOnRight(412);
 405
 406   Node* x = R.Parameter();
 407   Node* zero = R.Constant<int32_t>(0);
 408
 409   R.CheckBinop(x, x, zero);  // x - 0  => x
 410 }
 411
 412
 413 TEST(ReduceInt32Mul) {
 414   ReducerTester R;
 415   R.binop = R.machine.Int32Mul();
 416
 417   FOR_INT32_INPUTS(pl) {
 418     FOR_INT32_INPUTS(pr) {
 419       int32_t x = *pl, y = *pr;
 420       R.CheckFoldBinop<int32_t>(x * y, x, y);  // TODO(titzer): signed overflow
 421     }
 422   }
 423
 424   R.CheckPutConstantOnRight(4111);
 425   R.CheckPutConstantOnRight(-4407);
 426
 427   Node* x = R.Parameter();
 428   Node* zero = R.Constant<int32_t>(0);
 429   Node* one = R.Constant<int32_t>(1);
 430   Node* minus_one = R.Constant<int32_t>(-1);
 431
 432   R.CheckBinop(zero, x, zero);  // x * 0  => 0
 433   R.CheckBinop(zero, zero, x);  // 0 * x  => 0
 434   R.CheckBinop(x, x, one);      // x * 1  => x
 435   R.CheckBinop(x, one, x);      // 1 * x  => x
 436   R.CheckFoldBinop<int32_t>(0, R.machine.Int32Sub(), x, minus_one,
 437                             x);  // -1 * x  => 0 - x
 438   R.CheckFoldBinop<int32_t>(0, R.machine.Int32Sub(), x, x,
 439                             minus_one);  // x * -1  => 0 - x
 440
 441   for (int32_t n = 1; n < 31; ++n) {
 442     Node* multiplier = R.Constant<int32_t>(1 << n);
 443     R.CheckFoldBinop<int32_t>(x, R.machine.Word32Shl(), n, x,
 444                               multiplier);  // x * 2^n => x << n
 445     R.CheckFoldBinop<int32_t>(x, R.machine.Word32Shl(), n, multiplier,
 446                               x);  // 2^n * x => x << n
 447   }
 448 }
 449
 450
 451 TEST(ReduceInt32Div) {
 452   ReducerTester R;
 453   R.binop = R.machine.Int32Div();
 454
 455   FOR_INT32_INPUTS(pl) {
 456     FOR_INT32_INPUTS(pr) {
 457       int32_t x = *pl, y = *pr;
 458       if (y == 0) continue;              // TODO(titzer): test / 0
 459       int32_t r = y == -1 ? -x : x / y;  // INT_MIN / -1 may explode in C
 460       R.CheckFoldBinop<int32_t>(r, x, y);
 461     }
 462   }
 463
 464   R.CheckDontPutConstantOnRight(41111);
 465   R.CheckDontPutConstantOnRight(-44071);
 466
 467   Node* x = R.Parameter();
 468   Node* one = R.Constant<int32_t>(1);
 469   Node* minus_one = R.Constant<int32_t>(-1);
 470
 471   R.CheckBinop(x, x, one);  // x / 1  => x
 472   // TODO(titzer):                          // 0 / x  => 0 if x != 0
 473   // TODO(titzer):                          // x / 2^n => x >> n and round
 474   R.CheckFoldBinop<int32_t>(0, R.machine.Int32Sub(), x, x,
 475                             minus_one);  // x / -1  => 0 - x
 476 }
 477
 478
 479 TEST(ReduceInt32UDiv) {
 480   ReducerTester R;
 481   R.binop = R.machine.Int32UDiv();
 482
 483   FOR_UINT32_INPUTS(pl) {
 484     FOR_UINT32_INPUTS(pr) {
 485       uint32_t x = *pl, y = *pr;
 486       if (y == 0) continue;  // TODO(titzer): test / 0
 487       R.CheckFoldBinop<int32_t>(x / y, x, y);
 488     }
 489   }
 490
 491   R.CheckDontPutConstantOnRight(41311);
 492   R.CheckDontPutConstantOnRight(-44371);
 493
 494   Node* x = R.Parameter();
 495   Node* one = R.Constant<int32_t>(1);
 496
 497   R.CheckBinop(x, x, one);  // x / 1  => x
 498   // TODO(titzer):                            // 0 / x  => 0 if x != 0
 499
 500   for (uint32_t n = 1; n < 32; ++n) {
 501     Node* divisor = R.Constant<int32_t>(1u << n);
 502     R.CheckFoldBinop<int32_t>(x, R.machine.Word32Shr(), n, x,
 503                               divisor);  // x / 2^n => x >> n
 504   }
 505 }
 506
 507
 508 TEST(ReduceInt32Mod) {
 509   ReducerTester R;
 510   R.binop = R.machine.Int32Mod();
 511
 512   FOR_INT32_INPUTS(pl) {
 513     FOR_INT32_INPUTS(pr) {
 514       int32_t x = *pl, y = *pr;
 515       if (y == 0) continue;             // TODO(titzer): test % 0
 516       int32_t r = y == -1 ? 0 : x % y;  // INT_MIN % -1 may explode in C
 517       R.CheckFoldBinop<int32_t>(r, x, y);
 518     }
 519   }
 520
 521   R.CheckDontPutConstantOnRight(413);
 522   R.CheckDontPutConstantOnRight(-4401);
 523
 524   Node* x = R.Parameter();
 525   Node* one = R.Constant<int32_t>(1);
 526
 527   R.CheckFoldBinop<int32_t>(0, x, one);  // x % 1  => 0
 528   // TODO(titzer):                       // x % 2^n => x & 2^n-1 and round
 529 }
 530
 531
 532 TEST(ReduceInt32UMod) {
 533   ReducerTester R;
 534   R.binop = R.machine.Int32UMod();
 535
 536   FOR_INT32_INPUTS(pl) {
 537     FOR_INT32_INPUTS(pr) {
 538       uint32_t x = *pl, y = *pr;
 539       if (y == 0) continue;  // TODO(titzer): test x % 0
 540       R.CheckFoldBinop<int32_t>(x % y, x, y);
 541     }
 542   }
 543
 544   R.CheckDontPutConstantOnRight(417);
 545   R.CheckDontPutConstantOnRight(-4371);
 546
 547   Node* x = R.Parameter();
 548   Node* one = R.Constant<int32_t>(1);
 549
 550   R.CheckFoldBinop<int32_t>(0, x, one);  // x % 1  => 0
 551
 552   for (uint32_t n = 1; n < 32; ++n) {
 553     Node* divisor = R.Constant<int32_t>(1u << n);
 554     R.CheckFoldBinop<int32_t>(x, R.machine.Word32And(), (1u << n) - 1, x,
 555                               divisor);  // x % 2^n => x & 2^n-1
 556   }
 557 }
 558
 559
 560 TEST(ReduceInt32LessThan) {
 561   ReducerTester R;
 562   R.binop = R.machine.Int32LessThan();
 563
 564   FOR_INT32_INPUTS(pl) {
 565     FOR_INT32_INPUTS(pr) {
 566       int32_t x = *pl, y = *pr;
 567       R.CheckFoldBinop<int32_t>(x < y ? 1 : 0, x, y);
 568     }
 569   }
 570
 571   R.CheckDontPutConstantOnRight(41399);
 572   R.CheckDontPutConstantOnRight(-440197);
 573
 574   Node* x = R.Parameter(0);
 575   Node* y = R.Parameter(1);
 576   Node* zero = R.Constant<int32_t>(0);
 577   Node* sub = R.graph.NewNode(R.machine.Int32Sub(), x, y);
 578
 579   R.CheckFoldBinop<int32_t>(0, x, x);  // x < x  => 0
 580   R.CheckFoldBinop(x, y, sub, zero);   // x - y < 0 => x < y
 581   R.CheckFoldBinop(y, x, zero, sub);   // 0 < x - y => y < x
 582 }
 583
 584
 585 TEST(ReduceInt32LessThanOrEqual) {
 586   ReducerTester R;
 587   R.binop = R.machine.Int32LessThanOrEqual();
 588
 589   FOR_INT32_INPUTS(pl) {
 590     FOR_INT32_INPUTS(pr) {
 591       int32_t x = *pl, y = *pr;
 592       R.CheckFoldBinop<int32_t>(x <= y ? 1 : 0, x, y);
 593     }
 594   }
 595
 596   FOR_INT32_INPUTS(i) { R.CheckDontPutConstantOnRight<int32_t>(*i); }
 597
 598   Node* x = R.Parameter(0);
 599   Node* y = R.Parameter(1);
 600   Node* zero = R.Constant<int32_t>(0);
 601   Node* sub = R.graph.NewNode(R.machine.Int32Sub(), x, y);
 602
 603   R.CheckFoldBinop<int32_t>(1, x, x);  // x <= x => 1
 604   R.CheckFoldBinop(x, y, sub, zero);   // x - y <= 0 => x <= y
 605   R.CheckFoldBinop(y, x, zero, sub);   // 0 <= x - y => y <= x
 606 }
 607
 608
 609 TEST(ReduceUint32LessThan) {
 610   ReducerTester R;
 611   R.binop = R.machine.Uint32LessThan();
 612
 613   FOR_UINT32_INPUTS(pl) {
 614     FOR_UINT32_INPUTS(pr) {
 615       uint32_t x = *pl, y = *pr;
 616       R.CheckFoldBinop<int32_t>(x < y ? 1 : 0, x, y);
 617     }
 618   }
 619
 620   R.CheckDontPutConstantOnRight(41399);
 621   R.CheckDontPutConstantOnRight(-440197);
 622
 623   Node* x = R.Parameter();
 624   Node* max = R.maxuint32;
 625   Node* zero = R.Constant<int32_t>(0);
 626
 627   R.CheckFoldBinop<int32_t>(0, max, x);   // M < x  => 0
 628   R.CheckFoldBinop<int32_t>(0, x, zero);  // x < 0  => 0
 629   R.CheckFoldBinop<int32_t>(0, x, x);     // x < x  => 0
 630 }
 631
 632
 633 TEST(ReduceUint32LessThanOrEqual) {
 634   ReducerTester R;
 635   R.binop = R.machine.Uint32LessThanOrEqual();
 636
 637   FOR_UINT32_INPUTS(pl) {
 638     FOR_UINT32_INPUTS(pr) {
 639       uint32_t x = *pl, y = *pr;
 640       R.CheckFoldBinop<int32_t>(x <= y ? 1 : 0, x, y);
 641     }
 642   }
 643
 644   R.CheckDontPutConstantOnRight(41399);
 645   R.CheckDontPutConstantOnRight(-440197);
 646
 647   Node* x = R.Parameter();
 648   Node* max = R.maxuint32;
 649   Node* zero = R.Constant<int32_t>(0);
 650
 651   R.CheckFoldBinop<int32_t>(1, x, max);   // x <= M  => 1
 652   R.CheckFoldBinop<int32_t>(1, zero, x);  // 0 <= x  => 1
 653   R.CheckFoldBinop<int32_t>(1, x, x);     // x <= x  => 1
 654 }
 655
 656
 657 TEST(ReduceLoadStore) {
 658   ReducerTester R;
 659
 660   Node* base = R.Constant<int32_t>(11);
 661   Node* index = R.Constant<int32_t>(4);
 662   Node* load = R.graph.NewNode(R.machine.Load(kMachInt32), base, index);
 663
 664   {
 665     MachineOperatorReducer reducer(&R.jsgraph);
 666     Reduction reduction = reducer.Reduce(load);
 667     CHECK(!reduction.Changed());  // loads should not be reduced.
 668   }
 669
 670   {
 671     Node* store = R.graph.NewNode(
 672         R.machine.Store(StoreRepresentation(kMachInt32, kNoWriteBarrier)), base,
 673         index, load);
 674     MachineOperatorReducer reducer(&R.jsgraph);
 675     Reduction reduction = reducer.Reduce(store);
 676     CHECK(!reduction.Changed());  // stores should not be reduced.
 677   }
 678 }
 679
 680
 681 static void CheckNans(ReducerTester* R) {
 682   Node* x = R->Parameter();
 683   std::vector<double> nans = ValueHelper::nan_vector();
 684   for (std::vector<double>::const_iterator pl = nans.begin(); pl != nans.end();
 685        ++pl) {
 686     for (std::vector<double>::const_iterator pr = nans.begin();
 687          pr != nans.end(); ++pr) {
 688       Node* nan1 = R->Constant<double>(*pl);
 689       Node* nan2 = R->Constant<double>(*pr);
 690       R->CheckBinop(nan1, x, nan1);     // x % NaN => NaN
 691       R->CheckBinop(nan1, nan1, x);     // NaN % x => NaN
 692       R->CheckBinop(nan1, nan2, nan1);  // NaN % NaN => NaN
 693     }
 694   }
 695 }
 696
 697
 698 TEST(ReduceFloat64Add) {
 699   ReducerTester R;
 700   R.binop = R.machine.Float64Add();
 701
 702   FOR_FLOAT64_INPUTS(pl) {
 703     FOR_FLOAT64_INPUTS(pr) {
 704       double x = *pl, y = *pr;
 705       R.CheckFoldBinop<double>(x + y, x, y);
 706     }
 707   }
 708
 709   FOR_FLOAT64_INPUTS(i) { R.CheckPutConstantOnRight(*i); }
 710   // TODO(titzer): CheckNans(&R);
 711 }
 712
 713
 714 TEST(ReduceFloat64Sub) {
 715   ReducerTester R;
 716   R.binop = R.machine.Float64Sub();
 717
 718   FOR_FLOAT64_INPUTS(pl) {
 719     FOR_FLOAT64_INPUTS(pr) {
 720       double x = *pl, y = *pr;
 721       R.CheckFoldBinop<double>(x - y, x, y);
 722     }
 723   }
 724   // TODO(titzer): CheckNans(&R);
 725 }
 726
 727
 728 TEST(ReduceFloat64Mul) {
 729   ReducerTester R;
 730   R.binop = R.machine.Float64Mul();
 731
 732   FOR_FLOAT64_INPUTS(pl) {
 733     FOR_FLOAT64_INPUTS(pr) {
 734       double x = *pl, y = *pr;
 735       R.CheckFoldBinop<double>(x * y, x, y);
 736     }
 737   }
 738
 739   double inf = V8_INFINITY;
 740   R.CheckPutConstantOnRight(-inf);
 741   R.CheckPutConstantOnRight(-0.1);
 742   R.CheckPutConstantOnRight(0.1);
 743   R.CheckPutConstantOnRight(inf);
 744
 745   Node* x = R.Parameter();
 746   Node* one = R.Constant<double>(1.0);
 747
 748   R.CheckBinop(x, x, one);  // x * 1.0 => x
 749   R.CheckBinop(x, one, x);  // 1.0 * x => x
 750
 751   CheckNans(&R);
 752 }
 753
 754
 755 TEST(ReduceFloat64Div) {
 756   ReducerTester R;
 757   R.binop = R.machine.Float64Div();
 758
 759   FOR_FLOAT64_INPUTS(pl) {
 760     FOR_FLOAT64_INPUTS(pr) {
 761       double x = *pl, y = *pr;
 762       R.CheckFoldBinop<double>(x / y, x, y);
 763     }
 764   }
 765
 766   Node* x = R.Parameter();
 767   Node* one = R.Constant<double>(1.0);
 768
 769   R.CheckBinop(x, x, one);  // x / 1.0 => x
 770
 771   CheckNans(&R);
 772 }
 773
 774
 775 TEST(ReduceFloat64Mod) {
 776   ReducerTester R;
 777   R.binop = R.machine.Float64Mod();
 778
 779   FOR_FLOAT64_INPUTS(pl) {
 780     FOR_FLOAT64_INPUTS(pr) {
 781       double x = *pl, y = *pr;
 782       R.CheckFoldBinop<double>(modulo(x, y), x, y);
 783     }
 784   }
 785
 786   CheckNans(&R);
 787 }
 788
 789
 790 // TODO(titzer): test MachineOperatorReducer for Word64And
 791 // TODO(titzer): test MachineOperatorReducer for Word64Or
 792 // TODO(titzer): test MachineOperatorReducer for Word64Xor
 793 // TODO(titzer): test MachineOperatorReducer for Word64Shl
 794 // TODO(titzer): test MachineOperatorReducer for Word64Shr
 795 // TODO(titzer): test MachineOperatorReducer for Word64Sar
 796 // TODO(titzer): test MachineOperatorReducer for Word64Equal
 797 // TODO(titzer): test MachineOperatorReducer for Word64Not
 798 // TODO(titzer): test MachineOperatorReducer for Int64Add
 799 // TODO(titzer): test MachineOperatorReducer for Int64Sub
 800 // TODO(titzer): test MachineOperatorReducer for Int64Mul
 801 // TODO(titzer): test MachineOperatorReducer for Int64UMul
 802 // TODO(titzer): test MachineOperatorReducer for Int64Div
 803 // TODO(titzer): test MachineOperatorReducer for Int64UDiv
 804 // TODO(titzer): test MachineOperatorReducer for Int64Mod
 805 // TODO(titzer): test MachineOperatorReducer for Int64UMod
 806 // TODO(titzer): test MachineOperatorReducer for Int64Neg
 807 // TODO(titzer): test MachineOperatorReducer for ChangeInt32ToFloat64
 808 // TODO(titzer): test MachineOperatorReducer for ChangeFloat64ToInt32
 809 // TODO(titzer): test MachineOperatorReducer for Float64Compare