src/v8/test/cctest/compiler/test-structured-machine-assembler.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/utils/random-number-generator.h"
   9 #include "src/compiler/structured-machine-assembler.h"
  10 #include "test/cctest/compiler/codegen-tester.h"
  11 #include "test/cctest/compiler/value-helper.h"
  12
  13 #if V8_TURBOFAN_TARGET
  14
  15 using namespace v8::internal::compiler;
  16
  17 typedef StructuredMachineAssembler::IfBuilder IfBuilder;
  18 typedef StructuredMachineAssembler::LoopBuilder Loop;
  19
  20 namespace v8 {
  21 namespace internal {
  22 namespace compiler {
  23
  24 class StructuredMachineAssemblerFriend {
  25  public:
  26   static bool VariableAlive(StructuredMachineAssembler* m,
  27                             const Variable& var) {
  28     CHECK(m->current_environment_ != NULL);
  29     int offset = var.offset_;
  30     return offset < static_cast<int>(m->CurrentVars()->size()) &&
  31            m->CurrentVars()->at(offset) != NULL;
  32   }
  33 };
  34 }
  35 }
  36 }  // namespace v8::internal::compiler
  37
  38
  39 TEST(RunVariable) {
  40   StructuredMachineAssemblerTester<int32_t> m;
  41
  42   int32_t constant = 0x86c2bb16;
  43
  44   Variable v1 = m.NewVariable(m.Int32Constant(constant));
  45   Variable v2 = m.NewVariable(v1.Get());
  46   m.Return(v2.Get());
  47
  48   CHECK_EQ(constant, m.Call());
  49 }
  50
  51
  52 TEST(RunSimpleIf) {
  53   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
  54
  55   int32_t constant = 0xc4a3e3a6;
  56   {
  57     IfBuilder cond(&m);
  58     cond.If(m.Parameter(0)).Then();
  59     m.Return(m.Int32Constant(constant));
  60   }
  61   m.Return(m.Word32Not(m.Int32Constant(constant)));
  62
  63   CHECK_EQ(~constant, m.Call(0));
  64   CHECK_EQ(constant, m.Call(1));
  65 }
  66
  67
  68 TEST(RunSimpleIfVariable) {
  69   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
  70
  71   int32_t constant = 0xdb6f20c2;
  72   Variable var = m.NewVariable(m.Int32Constant(constant));
  73   {
  74     IfBuilder cond(&m);
  75     cond.If(m.Parameter(0)).Then();
  76     var.Set(m.Word32Not(var.Get()));
  77   }
  78   m.Return(var.Get());
  79
  80   CHECK_EQ(constant, m.Call(0));
  81   CHECK_EQ(~constant, m.Call(1));
  82 }
  83
  84
  85 TEST(RunSimpleElse) {
  86   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
  87
  88   int32_t constant = 0xfc5eadf4;
  89   {
  90     IfBuilder cond(&m);
  91     cond.If(m.Parameter(0)).Else();
  92     m.Return(m.Int32Constant(constant));
  93   }
  94   m.Return(m.Word32Not(m.Int32Constant(constant)));
  95
  96   CHECK_EQ(constant, m.Call(0));
  97   CHECK_EQ(~constant, m.Call(1));
  98 }
  99
 100
 101 TEST(RunSimpleIfElse) {
 102   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 103
 104   int32_t constant = 0xaa9c8cd3;
 105   {
 106     IfBuilder cond(&m);
 107     cond.If(m.Parameter(0)).Then();
 108     m.Return(m.Int32Constant(constant));
 109     cond.Else();
 110     m.Return(m.Word32Not(m.Int32Constant(constant)));
 111   }
 112
 113   CHECK_EQ(~constant, m.Call(0));
 114   CHECK_EQ(constant, m.Call(1));
 115 }
 116
 117
 118 TEST(RunSimpleIfElseVariable) {
 119   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 120
 121   int32_t constant = 0x67b6f39c;
 122   Variable var = m.NewVariable(m.Int32Constant(constant));
 123   {
 124     IfBuilder cond(&m);
 125     cond.If(m.Parameter(0)).Then();
 126     var.Set(m.Word32Not(m.Word32Not(var.Get())));
 127     cond.Else();
 128     var.Set(m.Word32Not(var.Get()));
 129   }
 130   m.Return(var.Get());
 131
 132   CHECK_EQ(~constant, m.Call(0));
 133   CHECK_EQ(constant, m.Call(1));
 134 }
 135
 136
 137 TEST(RunSimpleIfNoThenElse) {
 138   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 139
 140   int32_t constant = 0xd5e550ed;
 141   {
 142     IfBuilder cond(&m);
 143     cond.If(m.Parameter(0));
 144   }
 145   m.Return(m.Int32Constant(constant));
 146
 147   CHECK_EQ(constant, m.Call(0));
 148   CHECK_EQ(constant, m.Call(1));
 149 }
 150
 151
 152 TEST(RunSimpleConjunctionVariable) {
 153   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 154
 155   int32_t constant = 0xf8fb9ec6;
 156   Variable var = m.NewVariable(m.Int32Constant(constant));
 157   {
 158     IfBuilder cond(&m);
 159     cond.If(m.Int32Constant(1)).And();
 160     var.Set(m.Word32Not(var.Get()));
 161     cond.If(m.Parameter(0)).Then();
 162     var.Set(m.Word32Not(m.Word32Not(var.Get())));
 163     cond.Else();
 164     var.Set(m.Word32Not(var.Get()));
 165   }
 166   m.Return(var.Get());
 167
 168   CHECK_EQ(constant, m.Call(0));
 169   CHECK_EQ(~constant, m.Call(1));
 170 }
 171
 172
 173 TEST(RunSimpleDisjunctionVariable) {
 174   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 175
 176   int32_t constant = 0x118f6ffc;
 177   Variable var = m.NewVariable(m.Int32Constant(constant));
 178   {
 179     IfBuilder cond(&m);
 180     cond.If(m.Int32Constant(0)).Or();
 181     var.Set(m.Word32Not(var.Get()));
 182     cond.If(m.Parameter(0)).Then();
 183     var.Set(m.Word32Not(m.Word32Not(var.Get())));
 184     cond.Else();
 185     var.Set(m.Word32Not(var.Get()));
 186   }
 187   m.Return(var.Get());
 188
 189   CHECK_EQ(constant, m.Call(0));
 190   CHECK_EQ(~constant, m.Call(1));
 191 }
 192
 193
 194 TEST(RunIfElse) {
 195   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 196
 197   {
 198     IfBuilder cond(&m);
 199     bool first = true;
 200     FOR_INT32_INPUTS(i) {
 201       Node* c = m.Int32Constant(*i);
 202       if (first) {
 203         cond.If(m.Word32Equal(m.Parameter(0), c)).Then();
 204         m.Return(c);
 205         first = false;
 206       } else {
 207         cond.Else();
 208         cond.If(m.Word32Equal(m.Parameter(0), c)).Then();
 209         m.Return(c);
 210       }
 211     }
 212   }
 213   m.Return(m.Int32Constant(333));
 214
 215   FOR_INT32_INPUTS(i) { CHECK_EQ(*i, m.Call(*i)); }
 216 }
 217
 218
 219 enum IfBuilderBranchType { kSkipBranch, kBranchFallsThrough, kBranchReturns };
 220
 221
 222 static IfBuilderBranchType all_branch_types[] = {
 223     kSkipBranch, kBranchFallsThrough, kBranchReturns};
 224
 225
 226 static void RunIfBuilderDisjunction(size_t max, IfBuilderBranchType then_type,
 227                                     IfBuilderBranchType else_type) {
 228   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 229
 230   std::vector<int32_t> inputs = ValueHelper::int32_vector();
 231   std::vector<int32_t>::const_iterator i = inputs.begin();
 232   int32_t hit = 0x8c723c9a;
 233   int32_t miss = 0x88a6b9f3;
 234   {
 235     Node* p0 = m.Parameter(0);
 236     IfBuilder cond(&m);
 237     for (size_t j = 0; j < max; j++, ++i) {
 238       CHECK(i != inputs.end());  // Thank you STL.
 239       if (j > 0) cond.Or();
 240       cond.If(m.Word32Equal(p0, m.Int32Constant(*i)));
 241     }
 242     switch (then_type) {
 243       case kSkipBranch:
 244         break;
 245       case kBranchFallsThrough:
 246         cond.Then();
 247         break;
 248       case kBranchReturns:
 249         cond.Then();
 250         m.Return(m.Int32Constant(hit));
 251         break;
 252     }
 253     switch (else_type) {
 254       case kSkipBranch:
 255         break;
 256       case kBranchFallsThrough:
 257         cond.Else();
 258         break;
 259       case kBranchReturns:
 260         cond.Else();
 261         m.Return(m.Int32Constant(miss));
 262         break;
 263     }
 264   }
 265   if (then_type != kBranchReturns || else_type != kBranchReturns) {
 266     m.Return(m.Int32Constant(miss));
 267   }
 268
 269   if (then_type != kBranchReturns) hit = miss;
 270
 271   i = inputs.begin();
 272   for (size_t j = 0; i != inputs.end(); j++, ++i) {
 273     int32_t result = m.Call(*i);
 274     CHECK_EQ(j < max ? hit : miss, result);
 275   }
 276 }
 277
 278
 279 TEST(RunIfBuilderDisjunction) {
 280   size_t len = ValueHelper::int32_vector().size() - 1;
 281   size_t max = len > 10 ? 10 : len - 1;
 282   for (size_t i = 0; i < ARRAY_SIZE(all_branch_types); i++) {
 283     for (size_t j = 0; j < ARRAY_SIZE(all_branch_types); j++) {
 284       for (size_t size = 1; size < max; size++) {
 285         RunIfBuilderDisjunction(size, all_branch_types[i], all_branch_types[j]);
 286       }
 287       RunIfBuilderDisjunction(len, all_branch_types[i], all_branch_types[j]);
 288     }
 289   }
 290 }
 291
 292
 293 static void RunIfBuilderConjunction(size_t max, IfBuilderBranchType then_type,
 294                                     IfBuilderBranchType else_type) {
 295   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 296
 297   std::vector<int32_t> inputs = ValueHelper::int32_vector();
 298   std::vector<int32_t>::const_iterator i = inputs.begin();
 299   int32_t hit = 0xa0ceb9ca;
 300   int32_t miss = 0x226cafaa;
 301   {
 302     IfBuilder cond(&m);
 303     Node* p0 = m.Parameter(0);
 304     for (size_t j = 0; j < max; j++, ++i) {
 305       if (j > 0) cond.And();
 306       cond.If(m.Word32NotEqual(p0, m.Int32Constant(*i)));
 307     }
 308     switch (then_type) {
 309       case kSkipBranch:
 310         break;
 311       case kBranchFallsThrough:
 312         cond.Then();
 313         break;
 314       case kBranchReturns:
 315         cond.Then();
 316         m.Return(m.Int32Constant(hit));
 317         break;
 318     }
 319     switch (else_type) {
 320       case kSkipBranch:
 321         break;
 322       case kBranchFallsThrough:
 323         cond.Else();
 324         break;
 325       case kBranchReturns:
 326         cond.Else();
 327         m.Return(m.Int32Constant(miss));
 328         break;
 329     }
 330   }
 331   if (then_type != kBranchReturns || else_type != kBranchReturns) {
 332     m.Return(m.Int32Constant(miss));
 333   }
 334
 335   if (then_type != kBranchReturns) hit = miss;
 336
 337   i = inputs.begin();
 338   for (size_t j = 0; i != inputs.end(); j++, ++i) {
 339     int32_t result = m.Call(*i);
 340     CHECK_EQ(j >= max ? hit : miss, result);
 341   }
 342 }
 343
 344
 345 TEST(RunIfBuilderConjunction) {
 346   size_t len = ValueHelper::int32_vector().size() - 1;
 347   size_t max = len > 10 ? 10 : len - 1;
 348   for (size_t i = 0; i < ARRAY_SIZE(all_branch_types); i++) {
 349     for (size_t j = 0; j < ARRAY_SIZE(all_branch_types); j++) {
 350       for (size_t size = 1; size < max; size++) {
 351         RunIfBuilderConjunction(size, all_branch_types[i], all_branch_types[j]);
 352       }
 353       RunIfBuilderConjunction(len, all_branch_types[i], all_branch_types[j]);
 354     }
 355   }
 356 }
 357
 358
 359 static void RunDisjunctionVariables(int disjunctions, bool explicit_then,
 360                                     bool explicit_else) {
 361   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 362
 363   int32_t constant = 0x65a09535;
 364
 365   Node* cmp_val = m.Int32Constant(constant);
 366   Node* one = m.Int32Constant(1);
 367   Variable var = m.NewVariable(m.Parameter(0));
 368   {
 369     IfBuilder cond(&m);
 370     cond.If(m.Word32Equal(var.Get(), cmp_val));
 371     for (int i = 0; i < disjunctions; i++) {
 372       cond.Or();
 373       var.Set(m.Int32Add(var.Get(), one));
 374       cond.If(m.Word32Equal(var.Get(), cmp_val));
 375     }
 376     if (explicit_then) {
 377       cond.Then();
 378     }
 379     if (explicit_else) {
 380       cond.Else();
 381       var.Set(m.Int32Add(var.Get(), one));
 382     }
 383   }
 384   m.Return(var.Get());
 385
 386   int adds = disjunctions + (explicit_else ? 1 : 0);
 387   int32_t input = constant - 2 * adds;
 388   for (int i = 0; i < adds; i++) {
 389     CHECK_EQ(input + adds, m.Call(input));
 390     input++;
 391   }
 392   for (int i = 0; i < adds + 1; i++) {
 393     CHECK_EQ(constant, m.Call(input));
 394     input++;
 395   }
 396   for (int i = 0; i < adds; i++) {
 397     CHECK_EQ(input + adds, m.Call(input));
 398     input++;
 399   }
 400 }
 401
 402
 403 TEST(RunDisjunctionVariables) {
 404   for (int disjunctions = 0; disjunctions < 10; disjunctions++) {
 405     RunDisjunctionVariables(disjunctions, false, false);
 406     RunDisjunctionVariables(disjunctions, false, true);
 407     RunDisjunctionVariables(disjunctions, true, false);
 408     RunDisjunctionVariables(disjunctions, true, true);
 409   }
 410 }
 411
 412
 413 static void RunConjunctionVariables(int conjunctions, bool explicit_then,
 414                                     bool explicit_else) {
 415   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 416
 417   int32_t constant = 0x2c7f4b45;
 418   Node* cmp_val = m.Int32Constant(constant);
 419   Node* one = m.Int32Constant(1);
 420   Variable var = m.NewVariable(m.Parameter(0));
 421   {
 422     IfBuilder cond(&m);
 423     cond.If(m.Word32NotEqual(var.Get(), cmp_val));
 424     for (int i = 0; i < conjunctions; i++) {
 425       cond.And();
 426       var.Set(m.Int32Add(var.Get(), one));
 427       cond.If(m.Word32NotEqual(var.Get(), cmp_val));
 428     }
 429     if (explicit_then) {
 430       cond.Then();
 431       var.Set(m.Int32Add(var.Get(), one));
 432     }
 433     if (explicit_else) {
 434       cond.Else();
 435     }
 436   }
 437   m.Return(var.Get());
 438
 439   int adds = conjunctions + (explicit_then ? 1 : 0);
 440   int32_t input = constant - 2 * adds;
 441   for (int i = 0; i < adds; i++) {
 442     CHECK_EQ(input + adds, m.Call(input));
 443     input++;
 444   }
 445   for (int i = 0; i < adds + 1; i++) {
 446     CHECK_EQ(constant, m.Call(input));
 447     input++;
 448   }
 449   for (int i = 0; i < adds; i++) {
 450     CHECK_EQ(input + adds, m.Call(input));
 451     input++;
 452   }
 453 }
 454
 455
 456 TEST(RunConjunctionVariables) {
 457   for (int conjunctions = 0; conjunctions < 10; conjunctions++) {
 458     RunConjunctionVariables(conjunctions, false, false);
 459     RunConjunctionVariables(conjunctions, false, true);
 460     RunConjunctionVariables(conjunctions, true, false);
 461     RunConjunctionVariables(conjunctions, true, true);
 462   }
 463 }
 464
 465
 466 TEST(RunSimpleNestedIf) {
 467   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32, kMachineWord32);
 468   const size_t NUM_VALUES = 7;
 469   std::vector<int32_t> inputs = ValueHelper::int32_vector();
 470   CHECK(inputs.size() >= NUM_VALUES);
 471   Node* values[NUM_VALUES];
 472   for (size_t j = 0; j < NUM_VALUES; j++) {
 473     values[j] = m.Int32Constant(inputs[j]);
 474   }
 475   {
 476     IfBuilder if_0(&m);
 477     if_0.If(m.Word32Equal(m.Parameter(0), values[0])).Then();
 478     {
 479       IfBuilder if_1(&m);
 480       if_1.If(m.Word32Equal(m.Parameter(1), values[1])).Then();
 481       { m.Return(values[3]); }
 482       if_1.Else();
 483       { m.Return(values[4]); }
 484     }
 485     if_0.Else();
 486     {
 487       IfBuilder if_1(&m);
 488       if_1.If(m.Word32Equal(m.Parameter(1), values[2])).Then();
 489       { m.Return(values[5]); }
 490       if_1.Else();
 491       { m.Return(values[6]); }
 492     }
 493   }
 494
 495   int32_t result = m.Call(inputs[0], inputs[1]);
 496   CHECK_EQ(inputs[3], result);
 497
 498   result = m.Call(inputs[0], inputs[1] + 1);
 499   CHECK_EQ(inputs[4], result);
 500
 501   result = m.Call(inputs[0] + 1, inputs[2]);
 502   CHECK_EQ(inputs[5], result);
 503
 504   result = m.Call(inputs[0] + 1, inputs[2] + 1);
 505   CHECK_EQ(inputs[6], result);
 506 }
 507
 508
 509 TEST(RunUnreachableBlockAfterIf) {
 510   StructuredMachineAssemblerTester<int32_t> m;
 511   {
 512     IfBuilder cond(&m);
 513     cond.If(m.Int32Constant(0)).Then();
 514     m.Return(m.Int32Constant(1));
 515     cond.Else();
 516     m.Return(m.Int32Constant(2));
 517   }
 518   // This is unreachable.
 519   m.Return(m.Int32Constant(3));
 520   CHECK_EQ(2, m.Call());
 521 }
 522
 523
 524 TEST(RunUnreachableBlockAfterLoop) {
 525   StructuredMachineAssemblerTester<int32_t> m;
 526   {
 527     Loop loop(&m);
 528     m.Return(m.Int32Constant(1));
 529   }
 530   // This is unreachable.
 531   m.Return(m.Int32Constant(3));
 532   CHECK_EQ(1, m.Call());
 533 }
 534
 535
 536 TEST(RunSimpleLoop) {
 537   StructuredMachineAssemblerTester<int32_t> m;
 538   int32_t constant = 0x120c1f85;
 539   {
 540     Loop loop(&m);
 541     m.Return(m.Int32Constant(constant));
 542   }
 543   CHECK_EQ(constant, m.Call());
 544 }
 545
 546
 547 TEST(RunSimpleLoopBreak) {
 548   StructuredMachineAssemblerTester<int32_t> m;
 549   int32_t constant = 0x10ddb0a6;
 550   {
 551     Loop loop(&m);
 552     loop.Break();
 553   }
 554   m.Return(m.Int32Constant(constant));
 555   CHECK_EQ(constant, m.Call());
 556 }
 557
 558
 559 TEST(RunCountToTen) {
 560   StructuredMachineAssemblerTester<int32_t> m;
 561   Variable i = m.NewVariable(m.Int32Constant(0));
 562   Node* ten = m.Int32Constant(10);
 563   Node* one = m.Int32Constant(1);
 564   {
 565     Loop loop(&m);
 566     {
 567       IfBuilder cond(&m);
 568       cond.If(m.Word32Equal(i.Get(), ten)).Then();
 569       loop.Break();
 570     }
 571     i.Set(m.Int32Add(i.Get(), one));
 572   }
 573   m.Return(i.Get());
 574   CHECK_EQ(10, m.Call());
 575 }
 576
 577
 578 TEST(RunCountToTenAcc) {
 579   StructuredMachineAssemblerTester<int32_t> m;
 580   int32_t constant = 0xf27aed64;
 581   Variable i = m.NewVariable(m.Int32Constant(0));
 582   Variable var = m.NewVariable(m.Int32Constant(constant));
 583   Node* ten = m.Int32Constant(10);
 584   Node* one = m.Int32Constant(1);
 585   {
 586     Loop loop(&m);
 587     {
 588       IfBuilder cond(&m);
 589       cond.If(m.Word32Equal(i.Get(), ten)).Then();
 590       loop.Break();
 591     }
 592     i.Set(m.Int32Add(i.Get(), one));
 593     var.Set(m.Int32Add(var.Get(), i.Get()));
 594   }
 595   m.Return(var.Get());
 596
 597   CHECK_EQ(constant + 10 + 9 * 5, m.Call());
 598 }
 599
 600
 601 TEST(RunSimpleNestedLoop) {
 602   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 603
 604   Node* zero = m.Int32Constant(0);
 605   Node* one = m.Int32Constant(1);
 606   Node* two = m.Int32Constant(2);
 607   Node* three = m.Int32Constant(3);
 608   {
 609     Loop l1(&m);
 610     {
 611       Loop l2(&m);
 612       {
 613         IfBuilder cond(&m);
 614         cond.If(m.Word32Equal(m.Parameter(0), one)).Then();
 615         l1.Break();
 616       }
 617       {
 618         Loop l3(&m);
 619         {
 620           IfBuilder cond(&m);
 621           cond.If(m.Word32Equal(m.Parameter(0), two)).Then();
 622           l2.Break();
 623           cond.Else();
 624           cond.If(m.Word32Equal(m.Parameter(0), three)).Then();
 625           l3.Break();
 626         }
 627         m.Return(three);
 628       }
 629       m.Return(two);
 630     }
 631     m.Return(one);
 632   }
 633   m.Return(zero);
 634
 635   CHECK_EQ(0, m.Call(1));
 636   CHECK_EQ(1, m.Call(2));
 637   CHECK_EQ(2, m.Call(3));
 638   CHECK_EQ(3, m.Call(4));
 639 }
 640
 641
 642 TEST(RunFib) {
 643   StructuredMachineAssemblerTester<int32_t> m(kMachineWord32);
 644
 645   // Constants.
 646   Node* zero = m.Int32Constant(0);
 647   Node* one = m.Int32Constant(1);
 648   Node* two = m.Int32Constant(2);
 649   // Variables.
 650   // cnt = input
 651   Variable cnt = m.NewVariable(m.Parameter(0));
 652   // if (cnt < 2) return i
 653   {
 654     IfBuilder lt2(&m);
 655     lt2.If(m.Int32LessThan(cnt.Get(), two)).Then();
 656     m.Return(cnt.Get());
 657   }
 658   // cnt -= 2
 659   cnt.Set(m.Int32Sub(cnt.Get(), two));
 660   // res = 1
 661   Variable res = m.NewVariable(one);
 662   {
 663     // prv_0 = 1
 664     // prv_1 = 1
 665     Variable prv_0 = m.NewVariable(one);
 666     Variable prv_1 = m.NewVariable(one);
 667     // while (cnt != 0) {
 668     Loop main(&m);
 669     {
 670       IfBuilder nz(&m);
 671       nz.If(m.Word32Equal(cnt.Get(), zero)).Then();
 672       main.Break();
 673     }
 674     // res = prv_0 + prv_1
 675     // prv_0 = prv_1
 676     // prv_1 = res
 677     res.Set(m.Int32Add(prv_0.Get(), prv_1.Get()));
 678     prv_0.Set(prv_1.Get());
 679     prv_1.Set(res.Get());
 680     // cnt--
 681     cnt.Set(m.Int32Sub(cnt.Get(), one));
 682   }
 683   m.Return(res.Get());
 684
 685   int32_t values[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144};
 686   for (size_t i = 0; i < ARRAY_SIZE(values); i++) {
 687     CHECK_EQ(values[i], m.Call(static_cast<int32_t>(i)));
 688   }
 689 }
 690
 691
 692 static int VariableIntroduction() {
 693   while (true) {
 694     int ret = 0;
 695     for (int i = 0; i < 10; i++) {
 696       for (int j = i; j < 10; j++) {
 697         for (int k = j; k < 10; k++) {
 698           ret++;
 699         }
 700         ret++;
 701       }
 702       ret++;
 703     }
 704     return ret;
 705   }
 706 }
 707
 708
 709 TEST(RunVariableIntroduction) {
 710   StructuredMachineAssemblerTester<int32_t> m;
 711   Node* zero = m.Int32Constant(0);
 712   Node* one = m.Int32Constant(1);
 713   // Use an IfBuilder to get out of start block.
 714   {
 715     IfBuilder i0(&m);
 716     i0.If(zero).Then();
 717     m.Return(one);
 718   }
 719   Node* ten = m.Int32Constant(10);
 720   Variable v0 =
 721       m.NewVariable(zero);  // Introduce variable outside of start block.
 722   {
 723     Loop l0(&m);
 724     Variable ret = m.NewVariable(zero);  // Introduce loop variable.
 725     {
 726       Loop l1(&m);
 727       {
 728         IfBuilder i1(&m);
 729         i1.If(m.Word32Equal(v0.Get(), ten)).Then();
 730         l1.Break();
 731       }
 732       Variable v1 = m.NewVariable(v0.Get());  // Introduce loop variable.
 733       {
 734         Loop l2(&m);
 735         {
 736           IfBuilder i2(&m);
 737           i2.If(m.Word32Equal(v1.Get(), ten)).Then();
 738           l2.Break();
 739         }
 740         Variable v2 = m.NewVariable(v1.Get());  // Introduce loop variable.
 741         {
 742           Loop l3(&m);
 743           {
 744             IfBuilder i3(&m);
 745             i3.If(m.Word32Equal(v2.Get(), ten)).Then();
 746             l3.Break();
 747           }
 748           ret.Set(m.Int32Add(ret.Get(), one));
 749           v2.Set(m.Int32Add(v2.Get(), one));
 750         }
 751         ret.Set(m.Int32Add(ret.Get(), one));
 752         v1.Set(m.Int32Add(v1.Get(), one));
 753       }
 754       ret.Set(m.Int32Add(ret.Get(), one));
 755       v0.Set(m.Int32Add(v0.Get(), one));
 756     }
 757     m.Return(ret.Get());  // Return loop variable.
 758   }
 759   CHECK_EQ(VariableIntroduction(), m.Call());
 760 }
 761
 762
 763 TEST(RunIfBuilderVariableLiveness) {
 764   StructuredMachineAssemblerTester<int32_t> m;
 765   typedef i::compiler::StructuredMachineAssemblerFriend F;
 766   Node* zero = m.Int32Constant(0);
 767   Variable v_outer = m.NewVariable(zero);
 768   IfBuilder cond(&m);
 769   cond.If(zero).Then();
 770   Variable v_then = m.NewVariable(zero);
 771   CHECK(F::VariableAlive(&m, v_outer));
 772   CHECK(F::VariableAlive(&m, v_then));
 773   cond.Else();
 774   Variable v_else = m.NewVariable(zero);
 775   CHECK(F::VariableAlive(&m, v_outer));
 776   CHECK(F::VariableAlive(&m, v_else));
 777   CHECK(!F::VariableAlive(&m, v_then));
 778   cond.End();
 779   CHECK(F::VariableAlive(&m, v_outer));
 780   CHECK(!F::VariableAlive(&m, v_then));
 781   CHECK(!F::VariableAlive(&m, v_else));
 782 }
 783
 784
 785 TEST(RunSimpleExpression1) {
 786   StructuredMachineAssemblerTester<int32_t> m;
 787
 788   int32_t constant = 0x0c2974ef;
 789   Node* zero = m.Int32Constant(0);
 790   Node* one = m.Int32Constant(1);
 791   {
 792     // if (((1 && 1) && 1) && 1) return constant; return 0;
 793     IfBuilder cond(&m);
 794     cond.OpenParen();
 795     cond.OpenParen().If(one).And();
 796     cond.If(one).CloseParen().And();
 797     cond.If(one).CloseParen().And();
 798     cond.If(one).Then();
 799     m.Return(m.Int32Constant(constant));
 800   }
 801   m.Return(zero);
 802
 803   CHECK_EQ(constant, m.Call());
 804 }
 805
 806
 807 TEST(RunSimpleExpression2) {
 808   StructuredMachineAssemblerTester<int32_t> m;
 809
 810   int32_t constant = 0x2eddc11b;
 811   Node* zero = m.Int32Constant(0);
 812   Node* one = m.Int32Constant(1);
 813   {
 814     // if (((0 || 1) && 1) && 1) return constant; return 0;
 815     IfBuilder cond(&m);
 816     cond.OpenParen();
 817     cond.OpenParen().If(zero).Or();
 818     cond.If(one).CloseParen().And();
 819     cond.If(one).CloseParen().And();
 820     cond.If(one).Then();
 821     m.Return(m.Int32Constant(constant));
 822   }
 823   m.Return(zero);
 824
 825   CHECK_EQ(constant, m.Call());
 826 }
 827
 828
 829 TEST(RunSimpleExpression3) {
 830   StructuredMachineAssemblerTester<int32_t> m;
 831
 832   int32_t constant = 0x9ed5e9ef;
 833   Node* zero = m.Int32Constant(0);
 834   Node* one = m.Int32Constant(1);
 835   {
 836     // if (1 && ((0 || 1) && 1) && 1) return constant; return 0;
 837     IfBuilder cond(&m);
 838     cond.If(one).And();
 839     cond.OpenParen();
 840     cond.OpenParen().If(zero).Or();
 841     cond.If(one).CloseParen().And();
 842     cond.If(one).CloseParen().And();
 843     cond.If(one).Then();
 844     m.Return(m.Int32Constant(constant));
 845   }
 846   m.Return(zero);
 847
 848   CHECK_EQ(constant, m.Call());
 849 }
 850
 851
 852 TEST(RunSimpleExpressionVariable1) {
 853   StructuredMachineAssemblerTester<int32_t> m;
 854
 855   int32_t constant = 0x4b40a986;
 856   Node* one = m.Int32Constant(1);
 857   Variable var = m.NewVariable(m.Int32Constant(constant));
 858   {
 859     // if (var.Get() && ((!var || var) && var) && var) {} return var;
 860     // incrementing var in each environment.
 861     IfBuilder cond(&m);
 862     cond.If(var.Get()).And();
 863     var.Set(m.Int32Add(var.Get(), one));
 864     cond.OpenParen().OpenParen().If(m.Word32BinaryNot(var.Get())).Or();
 865     var.Set(m.Int32Add(var.Get(), one));
 866     cond.If(var.Get()).CloseParen().And();
 867     var.Set(m.Int32Add(var.Get(), one));
 868     cond.If(var.Get()).CloseParen().And();
 869     var.Set(m.Int32Add(var.Get(), one));
 870     cond.If(var.Get());
 871   }
 872   m.Return(var.Get());
 873
 874   CHECK_EQ(constant + 4, m.Call());
 875 }
 876
 877
 878 class QuicksortHelper : public StructuredMachineAssemblerTester<int32_t> {
 879  public:
 880   QuicksortHelper()
 881       : StructuredMachineAssemblerTester<int32_t>(
 882             MachineOperatorBuilder::pointer_rep(), kMachineWord32,
 883             MachineOperatorBuilder::pointer_rep(), kMachineWord32),
 884         input_(NULL),
 885         stack_limit_(NULL),
 886         one_(Int32Constant(1)),
 887         stack_frame_size_(Int32Constant(kFrameVariables * 4)),
 888         left_offset_(Int32Constant(0 * 4)),
 889         right_offset_(Int32Constant(1 * 4)) {
 890     Build();
 891   }
 892
 893   int32_t DoCall(int32_t* input, int32_t input_length) {
 894     int32_t stack_space[20];
 895     // Do call.
 896     int32_t return_val = Call(input, input_length, stack_space,
 897                               static_cast<int32_t>(ARRAY_SIZE(stack_space)));
 898     // Ran out of stack space.
 899     if (return_val != 0) return return_val;
 900     // Check sorted.
 901     int32_t last = input[0];
 902     for (int32_t i = 0; i < input_length; i++) {
 903       CHECK(last <= input[i]);
 904       last = input[i];
 905     }
 906     return return_val;
 907   }
 908
 909  private:
 910   void Inc32(const Variable& var) { var.Set(Int32Add(var.Get(), one_)); }
 911   Node* Index(Node* index) { return Word32Shl(index, Int32Constant(2)); }
 912   Node* ArrayLoad(Node* index) {
 913     return Load(kMachineWord32, input_, Index(index));
 914   }
 915   void Swap(Node* a_index, Node* b_index) {
 916     Node* a = ArrayLoad(a_index);
 917     Node* b = ArrayLoad(b_index);
 918     Store(kMachineWord32, input_, Index(a_index), b);
 919     Store(kMachineWord32, input_, Index(b_index), a);
 920   }
 921   void AddToCallStack(const Variable& fp, Node* left, Node* right) {
 922     {
 923       // Stack limit check.
 924       IfBuilder cond(this);
 925       cond.If(IntPtrLessThanOrEqual(fp.Get(), stack_limit_)).Then();
 926       Return(Int32Constant(-1));
 927     }
 928     Store(kMachineWord32, fp.Get(), left_offset_, left);
 929     Store(kMachineWord32, fp.Get(), right_offset_, right);
 930     fp.Set(IntPtrAdd(fp.Get(), ConvertInt32ToIntPtr(stack_frame_size_)));
 931   }
 932   void Build() {
 933     Variable left = NewVariable(Int32Constant(0));
 934     Variable right =
 935         NewVariable(Int32Sub(Parameter(kInputLengthParameter), one_));
 936     input_ = Parameter(kInputParameter);
 937     Node* top_of_stack = Parameter(kStackParameter);
 938     stack_limit_ = IntPtrSub(
 939         top_of_stack, ConvertInt32ToIntPtr(Parameter(kStackLengthParameter)));
 940     Variable fp = NewVariable(top_of_stack);
 941     {
 942       Loop outermost(this);
 943       // Edge case - 2 element array.
 944       {
 945         IfBuilder cond(this);
 946         cond.If(Word32Equal(left.Get(), Int32Sub(right.Get(), one_))).And();
 947         cond.If(Int32LessThanOrEqual(ArrayLoad(right.Get()),
 948                                      ArrayLoad(left.Get()))).Then();
 949         Swap(left.Get(), right.Get());
 950       }
 951       {
 952         IfBuilder cond(this);
 953         // Algorithm complete condition.
 954         cond.If(WordEqual(top_of_stack, fp.Get())).And();
 955         cond.If(Int32LessThanOrEqual(Int32Sub(right.Get(), one_), left.Get()))
 956             .Then();
 957         outermost.Break();
 958         // 'Recursion' exit condition. Pop frame and continue.
 959         cond.Else();
 960         cond.If(Int32LessThanOrEqual(Int32Sub(right.Get(), one_), left.Get()))
 961             .Then();
 962         fp.Set(IntPtrSub(fp.Get(), ConvertInt32ToIntPtr(stack_frame_size_)));
 963         left.Set(Load(kMachineWord32, fp.Get(), left_offset_));
 964         right.Set(Load(kMachineWord32, fp.Get(), right_offset_));
 965         outermost.Continue();
 966       }
 967       // Partition.
 968       Variable store_index = NewVariable(left.Get());
 969       {
 970         Node* pivot_index =
 971             Int32Div(Int32Add(left.Get(), right.Get()), Int32Constant(2));
 972         Node* pivot = ArrayLoad(pivot_index);
 973         Swap(pivot_index, right.Get());
 974         Variable i = NewVariable(left.Get());
 975         {
 976           Loop partition(this);
 977           {
 978             IfBuilder cond(this);
 979             // Parition complete.
 980             cond.If(Word32Equal(i.Get(), right.Get())).Then();
 981             partition.Break();
 982             // Need swap.
 983             cond.Else();
 984             cond.If(Int32LessThanOrEqual(ArrayLoad(i.Get()), pivot)).Then();
 985             Swap(i.Get(), store_index.Get());
 986             Inc32(store_index);
 987           }
 988           Inc32(i);
 989         }  // End partition loop.
 990         Swap(store_index.Get(), right.Get());
 991       }
 992       // 'Recurse' left and right halves of partition.
 993       // Tail recurse second one.
 994       AddToCallStack(fp, left.Get(), Int32Sub(store_index.Get(), one_));
 995       left.Set(Int32Add(store_index.Get(), one_));
 996     }  // End outermost loop.
 997     Return(Int32Constant(0));
 998   }
 999
1000   static const int kFrameVariables = 2;  // left, right
1001   // Parameter offsets.
1002   static const int kInputParameter = 0;
1003   static const int kInputLengthParameter = 1;
1004   static const int kStackParameter = 2;
1005   static const int kStackLengthParameter = 3;
1006   // Function inputs.
1007   Node* input_;
1008   Node* stack_limit_;
1009   // Constants.
1010   Node* const one_;
1011   // Frame constants.
1012   Node* const stack_frame_size_;
1013   Node* const left_offset_;
1014   Node* const right_offset_;
1015 };
1016
1017
1018 TEST(RunSimpleQuicksort) {
1019   QuicksortHelper m;
1020   int32_t inputs[] = {9, 7, 1, 8, 11};
1021   CHECK_EQ(0, m.DoCall(inputs, ARRAY_SIZE(inputs)));
1022 }
1023
1024
1025 TEST(RunRandomQuicksort) {
1026   QuicksortHelper m;
1027
1028   v8::base::RandomNumberGenerator rng;
1029   static const int kMaxLength = 40;
1030   int32_t inputs[kMaxLength];
1031
1032   for (int length = 1; length < kMaxLength; length++) {
1033     for (int i = 0; i < 70; i++) {
1034       // Randomize inputs.
1035       for (int j = 0; j < length; j++) {
1036         inputs[j] = rng.NextInt(10) - 5;
1037       }
1038       CHECK_EQ(0, m.DoCall(inputs, length));
1039     }
1040   }
1041 }
1042
1043
1044 TEST(MultipleScopes) {
1045   StructuredMachineAssemblerTester<int32_t> m;
1046   for (int i = 0; i < 10; i++) {
1047     IfBuilder b(&m);
1048     b.If(m.Int32Constant(0)).Then();
1049     m.NewVariable(m.Int32Constant(0));
1050   }
1051   m.Return(m.Int32Constant(0));
1052   CHECK_EQ(0, m.Call());
1053 }
1054
1055 #endif