src/v8/test/cctest/compiler/test-branch-combine.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
   7 #include "src/compiler/generic-node-inl.h"
   8 #include "test/cctest/cctest.h"
   9 #include "test/cctest/compiler/codegen-tester.h"
  10 #include "test/cctest/compiler/value-helper.h"
  11
  12 #if V8_TURBOFAN_TARGET
  13
  14 using namespace v8::internal;
  15 using namespace v8::internal::compiler;
  16
  17 typedef RawMachineAssembler::Label MLabel;
  18
  19 static IrOpcode::Value int32cmp_opcodes[] = {
  20     IrOpcode::kWord32Equal, IrOpcode::kInt32LessThan,
  21     IrOpcode::kInt32LessThanOrEqual, IrOpcode::kUint32LessThan,
  22     IrOpcode::kUint32LessThanOrEqual};
  23
  24
  25 TEST(BranchCombineWord32EqualZero_1) {
  26   // Test combining a branch with x == 0
  27   RawMachineAssemblerTester<int32_t> m(kMachInt32);
  28   int32_t eq_constant = -1033;
  29   int32_t ne_constant = 825118;
  30   Node* p0 = m.Parameter(0);
  31
  32   MLabel blocka, blockb;
  33   m.Branch(m.Word32Equal(p0, m.Int32Constant(0)), &blocka, &blockb);
  34   m.Bind(&blocka);
  35   m.Return(m.Int32Constant(eq_constant));
  36   m.Bind(&blockb);
  37   m.Return(m.Int32Constant(ne_constant));
  38
  39   FOR_INT32_INPUTS(i) {
  40     int32_t a = *i;
  41     int32_t expect = a == 0 ? eq_constant : ne_constant;
  42     CHECK_EQ(expect, m.Call(a));
  43   }
  44 }
  45
  46
  47 TEST(BranchCombineWord32EqualZero_chain) {
  48   // Test combining a branch with a chain of x == 0 == 0 == 0 ...
  49   int32_t eq_constant = -1133;
  50   int32_t ne_constant = 815118;
  51
  52   for (int k = 0; k < 6; k++) {
  53     RawMachineAssemblerTester<int32_t> m(kMachInt32);
  54     Node* p0 = m.Parameter(0);
  55     MLabel blocka, blockb;
  56     Node* cond = p0;
  57     for (int j = 0; j < k; j++) {
  58       cond = m.Word32Equal(cond, m.Int32Constant(0));
  59     }
  60     m.Branch(cond, &blocka, &blockb);
  61     m.Bind(&blocka);
  62     m.Return(m.Int32Constant(eq_constant));
  63     m.Bind(&blockb);
  64     m.Return(m.Int32Constant(ne_constant));
  65
  66     FOR_INT32_INPUTS(i) {
  67       int32_t a = *i;
  68       int32_t expect = (k & 1) == 1 ? (a == 0 ? eq_constant : ne_constant)
  69                                     : (a == 0 ? ne_constant : eq_constant);
  70       CHECK_EQ(expect, m.Call(a));
  71     }
  72   }
  73 }
  74
  75
  76 TEST(BranchCombineInt32LessThanZero_1) {
  77   // Test combining a branch with x < 0
  78   RawMachineAssemblerTester<int32_t> m(kMachInt32);
  79   int32_t eq_constant = -1433;
  80   int32_t ne_constant = 845118;
  81   Node* p0 = m.Parameter(0);
  82
  83   MLabel blocka, blockb;
  84   m.Branch(m.Int32LessThan(p0, m.Int32Constant(0)), &blocka, &blockb);
  85   m.Bind(&blocka);
  86   m.Return(m.Int32Constant(eq_constant));
  87   m.Bind(&blockb);
  88   m.Return(m.Int32Constant(ne_constant));
  89
  90   FOR_INT32_INPUTS(i) {
  91     int32_t a = *i;
  92     int32_t expect = a < 0 ? eq_constant : ne_constant;
  93     CHECK_EQ(expect, m.Call(a));
  94   }
  95 }
  96
  97
  98 TEST(BranchCombineUint32LessThan100_1) {
  99   // Test combining a branch with x < 100
 100   RawMachineAssemblerTester<int32_t> m(kMachUint32);
 101   int32_t eq_constant = 1471;
 102   int32_t ne_constant = 88845718;
 103   Node* p0 = m.Parameter(0);
 104
 105   MLabel blocka, blockb;
 106   m.Branch(m.Uint32LessThan(p0, m.Int32Constant(100)), &blocka, &blockb);
 107   m.Bind(&blocka);
 108   m.Return(m.Int32Constant(eq_constant));
 109   m.Bind(&blockb);
 110   m.Return(m.Int32Constant(ne_constant));
 111
 112   FOR_UINT32_INPUTS(i) {
 113     uint32_t a = *i;
 114     int32_t expect = a < 100 ? eq_constant : ne_constant;
 115     CHECK_EQ(expect, m.Call(a));
 116   }
 117 }
 118
 119
 120 TEST(BranchCombineUint32LessThanOrEqual100_1) {
 121   // Test combining a branch with x <= 100
 122   RawMachineAssemblerTester<int32_t> m(kMachUint32);
 123   int32_t eq_constant = 1479;
 124   int32_t ne_constant = 77845719;
 125   Node* p0 = m.Parameter(0);
 126
 127   MLabel blocka, blockb;
 128   m.Branch(m.Uint32LessThanOrEqual(p0, m.Int32Constant(100)), &blocka, &blockb);
 129   m.Bind(&blocka);
 130   m.Return(m.Int32Constant(eq_constant));
 131   m.Bind(&blockb);
 132   m.Return(m.Int32Constant(ne_constant));
 133
 134   FOR_UINT32_INPUTS(i) {
 135     uint32_t a = *i;
 136     int32_t expect = a <= 100 ? eq_constant : ne_constant;
 137     CHECK_EQ(expect, m.Call(a));
 138   }
 139 }
 140
 141
 142 TEST(BranchCombineZeroLessThanInt32_1) {
 143   // Test combining a branch with 0 < x
 144   RawMachineAssemblerTester<int32_t> m(kMachInt32);
 145   int32_t eq_constant = -2033;
 146   int32_t ne_constant = 225118;
 147   Node* p0 = m.Parameter(0);
 148
 149   MLabel blocka, blockb;
 150   m.Branch(m.Int32LessThan(m.Int32Constant(0), p0), &blocka, &blockb);
 151   m.Bind(&blocka);
 152   m.Return(m.Int32Constant(eq_constant));
 153   m.Bind(&blockb);
 154   m.Return(m.Int32Constant(ne_constant));
 155
 156   FOR_INT32_INPUTS(i) {
 157     int32_t a = *i;
 158     int32_t expect = 0 < a ? eq_constant : ne_constant;
 159     CHECK_EQ(expect, m.Call(a));
 160   }
 161 }
 162
 163
 164 TEST(BranchCombineInt32GreaterThanZero_1) {
 165   // Test combining a branch with x > 0
 166   RawMachineAssemblerTester<int32_t> m(kMachInt32);
 167   int32_t eq_constant = -1073;
 168   int32_t ne_constant = 825178;
 169   Node* p0 = m.Parameter(0);
 170
 171   MLabel blocka, blockb;
 172   m.Branch(m.Int32GreaterThan(p0, m.Int32Constant(0)), &blocka, &blockb);
 173   m.Bind(&blocka);
 174   m.Return(m.Int32Constant(eq_constant));
 175   m.Bind(&blockb);
 176   m.Return(m.Int32Constant(ne_constant));
 177
 178   FOR_INT32_INPUTS(i) {
 179     int32_t a = *i;
 180     int32_t expect = a > 0 ? eq_constant : ne_constant;
 181     CHECK_EQ(expect, m.Call(a));
 182   }
 183 }
 184
 185
 186 TEST(BranchCombineWord32EqualP) {
 187   // Test combining a branch with an Word32Equal.
 188   RawMachineAssemblerTester<int32_t> m(kMachInt32, kMachInt32);
 189   int32_t eq_constant = -1035;
 190   int32_t ne_constant = 825018;
 191   Node* p0 = m.Parameter(0);
 192   Node* p1 = m.Parameter(1);
 193
 194   MLabel blocka, blockb;
 195   m.Branch(m.Word32Equal(p0, p1), &blocka, &blockb);
 196   m.Bind(&blocka);
 197   m.Return(m.Int32Constant(eq_constant));
 198   m.Bind(&blockb);
 199   m.Return(m.Int32Constant(ne_constant));
 200
 201   FOR_INT32_INPUTS(i) {
 202     FOR_INT32_INPUTS(j) {
 203       int32_t a = *i;
 204       int32_t b = *j;
 205       int32_t expect = a == b ? eq_constant : ne_constant;
 206       CHECK_EQ(expect, m.Call(a, b));
 207     }
 208   }
 209 }
 210
 211
 212 TEST(BranchCombineWord32EqualI) {
 213   int32_t eq_constant = -1135;
 214   int32_t ne_constant = 925718;
 215
 216   for (int left = 0; left < 2; left++) {
 217     FOR_INT32_INPUTS(i) {
 218       RawMachineAssemblerTester<int32_t> m(kMachInt32);
 219       int32_t a = *i;
 220
 221       Node* p0 = m.Int32Constant(a);
 222       Node* p1 = m.Parameter(0);
 223
 224       MLabel blocka, blockb;
 225       if (left == 1) m.Branch(m.Word32Equal(p0, p1), &blocka, &blockb);
 226       if (left == 0) m.Branch(m.Word32Equal(p1, p0), &blocka, &blockb);
 227       m.Bind(&blocka);
 228       m.Return(m.Int32Constant(eq_constant));
 229       m.Bind(&blockb);
 230       m.Return(m.Int32Constant(ne_constant));
 231
 232       FOR_INT32_INPUTS(j) {
 233         int32_t b = *j;
 234         int32_t expect = a == b ? eq_constant : ne_constant;
 235         CHECK_EQ(expect, m.Call(b));
 236       }
 237     }
 238   }
 239 }
 240
 241
 242 TEST(BranchCombineInt32CmpP) {
 243   int32_t eq_constant = -1235;
 244   int32_t ne_constant = 725018;
 245
 246   for (int op = 0; op < 2; op++) {
 247     RawMachineAssemblerTester<int32_t> m(kMachInt32, kMachInt32);
 248     Node* p0 = m.Parameter(0);
 249     Node* p1 = m.Parameter(1);
 250
 251     MLabel blocka, blockb;
 252     if (op == 0) m.Branch(m.Int32LessThan(p0, p1), &blocka, &blockb);
 253     if (op == 1) m.Branch(m.Int32LessThanOrEqual(p0, p1), &blocka, &blockb);
 254     m.Bind(&blocka);
 255     m.Return(m.Int32Constant(eq_constant));
 256     m.Bind(&blockb);
 257     m.Return(m.Int32Constant(ne_constant));
 258
 259     FOR_INT32_INPUTS(i) {
 260       FOR_INT32_INPUTS(j) {
 261         int32_t a = *i;
 262         int32_t b = *j;
 263         int32_t expect = 0;
 264         if (op == 0) expect = a < b ? eq_constant : ne_constant;
 265         if (op == 1) expect = a <= b ? eq_constant : ne_constant;
 266         CHECK_EQ(expect, m.Call(a, b));
 267       }
 268     }
 269   }
 270 }
 271
 272
 273 TEST(BranchCombineInt32CmpI) {
 274   int32_t eq_constant = -1175;
 275   int32_t ne_constant = 927711;
 276
 277   for (int op = 0; op < 2; op++) {
 278     FOR_INT32_INPUTS(i) {
 279       RawMachineAssemblerTester<int32_t> m(kMachInt32);
 280       int32_t a = *i;
 281       Node* p0 = m.Int32Constant(a);
 282       Node* p1 = m.Parameter(0);
 283
 284       MLabel blocka, blockb;
 285       if (op == 0) m.Branch(m.Int32LessThan(p0, p1), &blocka, &blockb);
 286       if (op == 1) m.Branch(m.Int32LessThanOrEqual(p0, p1), &blocka, &blockb);
 287       m.Bind(&blocka);
 288       m.Return(m.Int32Constant(eq_constant));
 289       m.Bind(&blockb);
 290       m.Return(m.Int32Constant(ne_constant));
 291
 292       FOR_INT32_INPUTS(j) {
 293         int32_t b = *j;
 294         int32_t expect = 0;
 295         if (op == 0) expect = a < b ? eq_constant : ne_constant;
 296         if (op == 1) expect = a <= b ? eq_constant : ne_constant;
 297         CHECK_EQ(expect, m.Call(b));
 298       }
 299     }
 300   }
 301 }
 302
 303
 304 // Now come the sophisticated tests for many input shape combinations.
 305
 306 // Materializes a boolean (1 or 0) from a comparison.
 307 class CmpMaterializeBoolGen : public BinopGen<int32_t> {
 308  public:
 309   CompareWrapper w;
 310   bool invert;
 311
 312   CmpMaterializeBoolGen(IrOpcode::Value opcode, bool i)
 313       : w(opcode), invert(i) {}
 314
 315   virtual void gen(RawMachineAssemblerTester<int32_t>* m, Node* a, Node* b) {
 316     Node* cond = w.MakeNode(m, a, b);
 317     if (invert) cond = m->Word32Equal(cond, m->Int32Constant(0));
 318     m->Return(cond);
 319   }
 320   virtual int32_t expected(int32_t a, int32_t b) {
 321     if (invert) return !w.Int32Compare(a, b) ? 1 : 0;
 322     return w.Int32Compare(a, b) ? 1 : 0;
 323   }
 324 };
 325
 326
 327 // Generates a branch and return one of two values from a comparison.
 328 class CmpBranchGen : public BinopGen<int32_t> {
 329  public:
 330   CompareWrapper w;
 331   bool invert;
 332   bool true_first;
 333   int32_t eq_constant;
 334   int32_t ne_constant;
 335
 336   CmpBranchGen(IrOpcode::Value opcode, bool i, bool t, int32_t eq, int32_t ne)
 337       : w(opcode), invert(i), true_first(t), eq_constant(eq), ne_constant(ne) {}
 338
 339   virtual void gen(RawMachineAssemblerTester<int32_t>* m, Node* a, Node* b) {
 340     MLabel blocka, blockb;
 341     Node* cond = w.MakeNode(m, a, b);
 342     if (invert) cond = m->Word32Equal(cond, m->Int32Constant(0));
 343     m->Branch(cond, &blocka, &blockb);
 344     if (true_first) {
 345       m->Bind(&blocka);
 346       m->Return(m->Int32Constant(eq_constant));
 347       m->Bind(&blockb);
 348       m->Return(m->Int32Constant(ne_constant));
 349     } else {
 350       m->Bind(&blockb);
 351       m->Return(m->Int32Constant(ne_constant));
 352       m->Bind(&blocka);
 353       m->Return(m->Int32Constant(eq_constant));
 354     }
 355   }
 356   virtual int32_t expected(int32_t a, int32_t b) {
 357     if (invert) return !w.Int32Compare(a, b) ? eq_constant : ne_constant;
 358     return w.Int32Compare(a, b) ? eq_constant : ne_constant;
 359   }
 360 };
 361
 362
 363 TEST(BranchCombineInt32CmpAllInputShapes_materialized) {
 364   for (size_t i = 0; i < arraysize(int32cmp_opcodes); i++) {
 365     CmpMaterializeBoolGen gen(int32cmp_opcodes[i], false);
 366     Int32BinopInputShapeTester tester(&gen);
 367     tester.TestAllInputShapes();
 368   }
 369 }
 370
 371
 372 TEST(BranchCombineInt32CmpAllInputShapes_inverted_materialized) {
 373   for (size_t i = 0; i < arraysize(int32cmp_opcodes); i++) {
 374     CmpMaterializeBoolGen gen(int32cmp_opcodes[i], true);
 375     Int32BinopInputShapeTester tester(&gen);
 376     tester.TestAllInputShapes();
 377   }
 378 }
 379
 380
 381 TEST(BranchCombineInt32CmpAllInputShapes_branch_true) {
 382   for (int i = 0; i < static_cast<int>(arraysize(int32cmp_opcodes)); i++) {
 383     CmpBranchGen gen(int32cmp_opcodes[i], false, false, 995 + i, -1011 - i);
 384     Int32BinopInputShapeTester tester(&gen);
 385     tester.TestAllInputShapes();
 386   }
 387 }
 388
 389
 390 TEST(BranchCombineInt32CmpAllInputShapes_branch_false) {
 391   for (int i = 0; i < static_cast<int>(arraysize(int32cmp_opcodes)); i++) {
 392     CmpBranchGen gen(int32cmp_opcodes[i], false, true, 795 + i, -2011 - i);
 393     Int32BinopInputShapeTester tester(&gen);
 394     tester.TestAllInputShapes();
 395   }
 396 }
 397
 398
 399 TEST(BranchCombineInt32CmpAllInputShapes_inverse_branch_true) {
 400   for (int i = 0; i < static_cast<int>(arraysize(int32cmp_opcodes)); i++) {
 401     CmpBranchGen gen(int32cmp_opcodes[i], true, false, 695 + i, -3011 - i);
 402     Int32BinopInputShapeTester tester(&gen);
 403     tester.TestAllInputShapes();
 404   }
 405 }
 406
 407
 408 TEST(BranchCombineInt32CmpAllInputShapes_inverse_branch_false) {
 409   for (int i = 0; i < static_cast<int>(arraysize(int32cmp_opcodes)); i++) {
 410     CmpBranchGen gen(int32cmp_opcodes[i], true, true, 595 + i, -4011 - i);
 411     Int32BinopInputShapeTester tester(&gen);
 412     tester.TestAllInputShapes();
 413   }
 414 }
 415
 416
 417 TEST(BranchCombineFloat64Compares) {
 418   double inf = V8_INFINITY;
 419   double nan = v8::base::OS::nan_value();
 420   double inputs[] = {0.0, 1.0, -1.0, -inf, inf, nan};
 421
 422   int32_t eq_constant = -1733;
 423   int32_t ne_constant = 915118;
 424
 425   double input_a = 0.0;
 426   double input_b = 0.0;
 427
 428   CompareWrapper cmps[] = {CompareWrapper(IrOpcode::kFloat64Equal),
 429                            CompareWrapper(IrOpcode::kFloat64LessThan),
 430                            CompareWrapper(IrOpcode::kFloat64LessThanOrEqual)};
 431
 432   for (size_t c = 0; c < arraysize(cmps); c++) {
 433     CompareWrapper cmp = cmps[c];
 434     for (int invert = 0; invert < 2; invert++) {
 435       RawMachineAssemblerTester<int32_t> m;
 436       Node* a = m.LoadFromPointer(&input_a, kMachFloat64);
 437       Node* b = m.LoadFromPointer(&input_b, kMachFloat64);
 438
 439       MLabel blocka, blockb;
 440       Node* cond = cmp.MakeNode(&m, a, b);
 441       if (invert) cond = m.Word32Equal(cond, m.Int32Constant(0));
 442       m.Branch(cond, &blocka, &blockb);
 443       m.Bind(&blocka);
 444       m.Return(m.Int32Constant(eq_constant));
 445       m.Bind(&blockb);
 446       m.Return(m.Int32Constant(ne_constant));
 447
 448       for (size_t i = 0; i < arraysize(inputs); i++) {
 449         for (size_t j = 0; j < arraysize(inputs); j += 2) {
 450           input_a = inputs[i];
 451           input_b = inputs[i];
 452           int32_t expected =
 453               invert ? (cmp.Float64Compare(input_a, input_b) ? ne_constant
 454                                                              : eq_constant)
 455                      : (cmp.Float64Compare(input_a, input_b) ? eq_constant
 456                                                              : ne_constant);
 457           CHECK_EQ(expected, m.Call());
 458         }
 459       }
 460     }
 461   }
 462 }
 463 #endif  // V8_TURBOFAN_TARGET