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