deps/v8/test/cctest/compiler/test-osr.cc

   1 // Copyright 2015 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/codegen.h"
   6 #include "src/compiler/all-nodes.h"
   7 #include "src/compiler/common-operator.h"
   8 #include "src/compiler/diamond.h"
   9 #include "src/compiler/graph.h"
  10 #include "src/compiler/js-graph.h"
  11 #include "src/compiler/js-operator.h"
  12 #include "src/compiler/operator.h"
  13 #include "src/compiler/osr.h"
  14 #include "test/cctest/cctest.h"
  15
  16 using namespace v8::internal;
  17 using namespace v8::internal::compiler;
  18
  19 // TODO(titzer): move this method to a common testing place.
  20
  21 static int CheckInputs(Node* node, Node* i0 = NULL, Node* i1 = NULL,
  22                        Node* i2 = NULL, Node* i3 = NULL) {
  23   int count = 4;
  24   if (i3 == NULL) count = 3;
  25   if (i2 == NULL) count = 2;
  26   if (i1 == NULL) count = 1;
  27   if (i0 == NULL) count = 0;
  28   CHECK_EQ(count, node->InputCount());
  29   if (i0 != NULL) CHECK_EQ(i0, node->InputAt(0));
  30   if (i1 != NULL) CHECK_EQ(i1, node->InputAt(1));
  31   if (i2 != NULL) CHECK_EQ(i2, node->InputAt(2));
  32   if (i3 != NULL) CHECK_EQ(i3, node->InputAt(3));
  33   return count;
  34 }
  35
  36
  37 static Operator kIntLt(IrOpcode::kInt32LessThan, Operator::kPure,
  38                        "Int32LessThan", 2, 0, 0, 1, 0, 0);
  39
  40
  41 static const int kMaxOsrValues = 10;
  42
  43 class OsrDeconstructorTester : public HandleAndZoneScope {
  44  public:
  45   explicit OsrDeconstructorTester(int num_values)
  46       : isolate(main_isolate()),
  47         common(main_zone()),
  48         graph(main_zone()),
  49         jsgraph(main_isolate(), &graph, &common, NULL, NULL),
  50         start(graph.NewNode(common.Start(1))),
  51         p0(graph.NewNode(common.Parameter(0), start)),
  52         end(graph.NewNode(common.End(), start)),
  53         osr_normal_entry(graph.NewNode(common.OsrNormalEntry(), start, start)),
  54         osr_loop_entry(graph.NewNode(common.OsrLoopEntry(), start, start)),
  55         self(graph.NewNode(common.Int32Constant(0xaabbccdd))) {
  56     CHECK(num_values <= kMaxOsrValues);
  57     graph.SetStart(start);
  58     for (int i = 0; i < num_values; i++) {
  59       osr_values[i] = graph.NewNode(common.OsrValue(i), osr_loop_entry);
  60     }
  61   }
  62
  63   Isolate* isolate;
  64   CommonOperatorBuilder common;
  65   Graph graph;
  66   JSGraph jsgraph;
  67   Node* start;
  68   Node* p0;
  69   Node* end;
  70   Node* osr_normal_entry;
  71   Node* osr_loop_entry;
  72   Node* self;
  73   Node* osr_values[kMaxOsrValues];
  74
  75   Node* NewOsrPhi(Node* loop, Node* incoming, int osr_value, Node* back1 = NULL,
  76                   Node* back2 = NULL, Node* back3 = NULL) {
  77     int count = 5;
  78     if (back3 == NULL) count = 4;
  79     if (back2 == NULL) count = 3;
  80     if (back1 == NULL) count = 2;
  81     CHECK_EQ(loop->InputCount(), count);
  82     CHECK_EQ(osr_loop_entry, loop->InputAt(1));
  83
  84     Node* inputs[6];
  85     inputs[0] = incoming;
  86     inputs[1] = osr_values[osr_value];
  87     if (count > 2) inputs[2] = back1;
  88     if (count > 3) inputs[3] = back2;
  89     if (count > 4) inputs[4] = back3;
  90     inputs[count] = loop;
  91     return graph.NewNode(common.Phi(kMachAnyTagged, count), count + 1, inputs);
  92   }
  93
  94   Node* NewLoop(bool is_osr, int num_backedges, Node* entry = NULL) {
  95     CHECK_LT(num_backedges, 4);
  96     CHECK_GE(num_backedges, 0);
  97     int count = 1 + num_backedges;
  98     if (entry == NULL) entry = osr_normal_entry;
  99     Node* inputs[5] = {entry, self, self, self, self};
 100     if (is_osr) {
 101       count = 2 + num_backedges;
 102       inputs[1] = osr_loop_entry;
 103     }
 104
 105     Node* loop = graph.NewNode(common.Loop(count), count, inputs);
 106     for (int i = 0; i < loop->InputCount(); i++) {
 107       if (loop->InputAt(i) == self) loop->ReplaceInput(i, loop);
 108     }
 109
 110     return loop;
 111   }
 112
 113   Node* NewOsrLoop(int num_backedges, Node* entry = NULL) {
 114     return NewLoop(true, num_backedges, entry);
 115   }
 116
 117   void DeconstructOsr() {
 118     OsrHelper helper(0, 0);
 119     helper.Deconstruct(&jsgraph, &common, main_zone());
 120     AllNodes nodes(main_zone(), &graph);
 121     // Should be edited out.
 122     CHECK(!nodes.IsLive(osr_normal_entry));
 123     CHECK(!nodes.IsLive(osr_loop_entry));
 124     // No dangling nodes should be left over.
 125     CHECK_EQ(0u, nodes.gray.size());
 126   }
 127 };
 128
 129
 130 TEST(Deconstruct_osr0) {
 131   OsrDeconstructorTester T(0);
 132
 133   Node* loop = T.NewOsrLoop(1);
 134
 135   T.graph.SetEnd(loop);
 136
 137   T.DeconstructOsr();
 138
 139   CheckInputs(loop, T.start, loop);
 140 }
 141
 142
 143 TEST(Deconstruct_osr1) {
 144   OsrDeconstructorTester T(1);
 145
 146   Node* loop = T.NewOsrLoop(1);
 147   Node* osr_phi =
 148       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
 149
 150   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, loop);
 151   T.graph.SetEnd(ret);
 152
 153   T.DeconstructOsr();
 154
 155   CheckInputs(loop, T.start, loop);
 156   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), loop);
 157   CheckInputs(ret, osr_phi, T.start, loop);
 158 }
 159
 160
 161 TEST(Deconstruct_osr1_type) {
 162   OsrDeconstructorTester T(1);
 163
 164   Node* loop = T.NewOsrLoop(1);
 165   Node* osr_phi =
 166       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
 167   Type* type = Type::Signed32();
 168   NodeProperties::SetBounds(osr_phi, Bounds(type, type));
 169
 170   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, loop);
 171   T.graph.SetEnd(ret);
 172
 173   OsrHelper helper(0, 0);
 174   helper.Deconstruct(&T.jsgraph, &T.common, T.main_zone());
 175
 176   CHECK_EQ(type, NodeProperties::GetBounds(T.osr_values[0]).lower);
 177   CHECK_EQ(type, NodeProperties::GetBounds(T.osr_values[0]).upper);
 178
 179   CheckInputs(loop, T.start, loop);
 180   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), loop);
 181   CheckInputs(ret, osr_phi, T.start, loop);
 182 }
 183
 184
 185 TEST(Deconstruct_osr_remove_prologue) {
 186   OsrDeconstructorTester T(1);
 187   Diamond d(&T.graph, &T.common, T.p0);
 188   d.Chain(T.osr_normal_entry);
 189
 190   Node* loop = T.NewOsrLoop(1, d.merge);
 191   Node* osr_phi =
 192       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
 193
 194   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, loop);
 195   T.graph.SetEnd(ret);
 196
 197   T.DeconstructOsr();
 198
 199   CheckInputs(loop, T.start, loop);
 200   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), loop);
 201   CheckInputs(ret, osr_phi, T.start, loop);
 202
 203   // The control before the loop should have been removed.
 204   AllNodes nodes(T.main_zone(), &T.graph);
 205   CHECK(!nodes.IsLive(d.branch));
 206   CHECK(!nodes.IsLive(d.if_true));
 207   CHECK(!nodes.IsLive(d.if_false));
 208   CHECK(!nodes.IsLive(d.merge));
 209 }
 210
 211
 212 TEST(Deconstruct_osr_with_body1) {
 213   OsrDeconstructorTester T(1);
 214
 215   Node* loop = T.NewOsrLoop(1);
 216
 217   Node* branch = T.graph.NewNode(T.common.Branch(), T.p0, loop);
 218   Node* if_true = T.graph.NewNode(T.common.IfTrue(), branch);
 219   Node* if_false = T.graph.NewNode(T.common.IfFalse(), branch);
 220   loop->ReplaceInput(2, if_true);
 221
 222   Node* osr_phi =
 223       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
 224
 225   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, if_false);
 226   T.graph.SetEnd(ret);
 227
 228   T.DeconstructOsr();
 229
 230   CheckInputs(loop, T.start, if_true);
 231   CheckInputs(branch, T.p0, loop);
 232   CheckInputs(if_true, branch);
 233   CheckInputs(if_false, branch);
 234   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), loop);
 235   CheckInputs(ret, osr_phi, T.start, if_false);
 236 }
 237
 238
 239 TEST(Deconstruct_osr_with_body2) {
 240   OsrDeconstructorTester T(1);
 241
 242   Node* loop = T.NewOsrLoop(1);
 243
 244   // Two chained branches in the the body of the loop.
 245   Node* branch1 = T.graph.NewNode(T.common.Branch(), T.p0, loop);
 246   Node* if_true1 = T.graph.NewNode(T.common.IfTrue(), branch1);
 247   Node* if_false1 = T.graph.NewNode(T.common.IfFalse(), branch1);
 248
 249   Node* branch2 = T.graph.NewNode(T.common.Branch(), T.p0, if_true1);
 250   Node* if_true2 = T.graph.NewNode(T.common.IfTrue(), branch2);
 251   Node* if_false2 = T.graph.NewNode(T.common.IfFalse(), branch2);
 252   loop->ReplaceInput(2, if_true2);
 253
 254   Node* osr_phi =
 255       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
 256
 257   Node* merge = T.graph.NewNode(T.common.Merge(2), if_false1, if_false2);
 258   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, merge);
 259   T.graph.SetEnd(ret);
 260
 261   T.DeconstructOsr();
 262
 263   CheckInputs(loop, T.start, if_true2);
 264   CheckInputs(branch1, T.p0, loop);
 265   CheckInputs(branch2, T.p0, if_true1);
 266   CheckInputs(if_true1, branch1);
 267   CheckInputs(if_false1, branch1);
 268   CheckInputs(if_true2, branch2);
 269   CheckInputs(if_false2, branch2);
 270
 271   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), loop);
 272   CheckInputs(ret, osr_phi, T.start, merge);
 273   CheckInputs(merge, if_false1, if_false2);
 274 }
 275
 276
 277 TEST(Deconstruct_osr_with_body3) {
 278   OsrDeconstructorTester T(1);
 279
 280   Node* loop = T.NewOsrLoop(2);
 281
 282   // Two branches that create two different backedges.
 283   Node* branch1 = T.graph.NewNode(T.common.Branch(), T.p0, loop);
 284   Node* if_true1 = T.graph.NewNode(T.common.IfTrue(), branch1);
 285   Node* if_false1 = T.graph.NewNode(T.common.IfFalse(), branch1);
 286
 287   Node* branch2 = T.graph.NewNode(T.common.Branch(), T.p0, if_true1);
 288   Node* if_true2 = T.graph.NewNode(T.common.IfTrue(), branch2);
 289   Node* if_false2 = T.graph.NewNode(T.common.IfFalse(), branch2);
 290   loop->ReplaceInput(2, if_false1);
 291   loop->ReplaceInput(3, if_true2);
 292
 293   Node* osr_phi =
 294       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant(),
 295                   T.jsgraph.ZeroConstant());
 296
 297   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, if_false2);
 298   T.graph.SetEnd(ret);
 299
 300   T.DeconstructOsr();
 301
 302   CheckInputs(loop, T.start, if_false1, if_true2);
 303   CheckInputs(branch1, T.p0, loop);
 304   CheckInputs(branch2, T.p0, if_true1);
 305   CheckInputs(if_true1, branch1);
 306   CheckInputs(if_false1, branch1);
 307   CheckInputs(if_true2, branch2);
 308   CheckInputs(if_false2, branch2);
 309
 310   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(),
 311               T.jsgraph.ZeroConstant(), loop);
 312   CheckInputs(ret, osr_phi, T.start, if_false2);
 313 }
 314
 315
 316 struct While {
 317   OsrDeconstructorTester& t;
 318   Node* branch;
 319   Node* if_true;
 320   Node* exit;
 321   Node* loop;
 322
 323   While(OsrDeconstructorTester& R, Node* cond, bool is_osr, int backedges = 1)
 324       : t(R) {
 325     loop = t.NewLoop(is_osr, backedges);
 326     branch = t.graph.NewNode(t.common.Branch(), cond, loop);
 327     if_true = t.graph.NewNode(t.common.IfTrue(), branch);
 328     exit = t.graph.NewNode(t.common.IfFalse(), branch);
 329     loop->ReplaceInput(loop->InputCount() - 1, if_true);
 330   }
 331
 332   void Nest(While& that) {
 333     that.loop->ReplaceInput(that.loop->InputCount() - 1, exit);
 334     this->loop->ReplaceInput(0, that.if_true);
 335   }
 336
 337   Node* Phi(Node* i1, Node* i2, Node* i3) {
 338     if (loop->InputCount() == 2) {
 339       return t.graph.NewNode(t.common.Phi(kMachAnyTagged, 2), i1, i2, loop);
 340     } else {
 341       return t.graph.NewNode(t.common.Phi(kMachAnyTagged, 3), i1, i2, i3, loop);
 342     }
 343   }
 344 };
 345
 346
 347 static Node* FindSuccessor(Node* node, IrOpcode::Value opcode) {
 348   for (Node* use : node->uses()) {
 349     if (use->opcode() == opcode) return use;
 350   }
 351   UNREACHABLE();  // should have been found.
 352   return nullptr;
 353 }
 354
 355
 356 TEST(Deconstruct_osr_nested1) {
 357   OsrDeconstructorTester T(1);
 358
 359   While outer(T, T.p0, false);
 360   While inner(T, T.p0, true);
 361   inner.Nest(outer);
 362
 363   Node* outer_phi = outer.Phi(T.p0, T.p0, nullptr);
 364   outer.branch->ReplaceInput(0, outer_phi);
 365
 366   Node* osr_phi = inner.Phi(T.jsgraph.OneConstant(), T.osr_values[0],
 367                             T.jsgraph.ZeroConstant());
 368   inner.branch->ReplaceInput(0, osr_phi);
 369   outer_phi->ReplaceInput(1, osr_phi);
 370
 371   Node* ret =
 372       T.graph.NewNode(T.common.Return(), outer_phi, T.start, outer.exit);
 373   Node* end = T.graph.NewNode(T.common.End(), ret);
 374   T.graph.SetEnd(end);
 375
 376   T.DeconstructOsr();
 377
 378   // Check structure of deconstructed graph.
 379   // Check inner OSR loop is directly connected to start.
 380   CheckInputs(inner.loop, T.start, inner.if_true);
 381   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), inner.loop);
 382
 383   // Check control transfer to copy of outer loop.
 384   Node* new_outer_loop = FindSuccessor(inner.exit, IrOpcode::kLoop);
 385   Node* new_outer_phi = FindSuccessor(new_outer_loop, IrOpcode::kPhi);
 386   CHECK_NE(new_outer_loop, outer.loop);
 387   CHECK_NE(new_outer_phi, outer_phi);
 388
 389   CheckInputs(new_outer_loop, inner.exit, new_outer_loop->InputAt(1));
 390
 391   // Check structure of outer loop.
 392   Node* new_outer_branch = FindSuccessor(new_outer_loop, IrOpcode::kBranch);
 393   CHECK_NE(new_outer_branch, outer.branch);
 394   CheckInputs(new_outer_branch, new_outer_phi, new_outer_loop);
 395   Node* new_outer_exit = FindSuccessor(new_outer_branch, IrOpcode::kIfFalse);
 396   Node* new_outer_if_true = FindSuccessor(new_outer_branch, IrOpcode::kIfTrue);
 397
 398   // Check structure of return.
 399   end = T.graph.end();
 400   Node* new_ret = end->InputAt(0);
 401   CHECK_EQ(IrOpcode::kReturn, new_ret->opcode());
 402   CheckInputs(new_ret, new_outer_phi, T.start, new_outer_exit);
 403
 404   // Check structure of inner loop.
 405   Node* new_inner_loop = FindSuccessor(new_outer_if_true, IrOpcode::kLoop);
 406   Node* new_inner_phi = FindSuccessor(new_inner_loop, IrOpcode::kPhi);
 407
 408   CheckInputs(new_inner_phi, T.jsgraph.OneConstant(), T.jsgraph.ZeroConstant(),
 409               new_inner_loop);
 410   CheckInputs(new_outer_phi, osr_phi, new_inner_phi, new_outer_loop);
 411 }
 412
 413
 414 TEST(Deconstruct_osr_nested2) {
 415   OsrDeconstructorTester T(1);
 416
 417   // Test multiple backedge outer loop.
 418   While outer(T, T.p0, false, 2);
 419   While inner(T, T.p0, true);
 420   inner.Nest(outer);
 421
 422   Node* outer_phi = outer.Phi(T.p0, T.p0, T.p0);
 423   outer.branch->ReplaceInput(0, outer_phi);
 424
 425   Node* osr_phi = inner.Phi(T.jsgraph.OneConstant(), T.osr_values[0],
 426                             T.jsgraph.ZeroConstant());
 427   inner.branch->ReplaceInput(0, osr_phi);
 428   outer_phi->ReplaceInput(1, osr_phi);
 429   outer_phi->ReplaceInput(2, T.jsgraph.ZeroConstant());
 430
 431   Node* x_branch = T.graph.NewNode(T.common.Branch(), osr_phi, inner.exit);
 432   Node* x_true = T.graph.NewNode(T.common.IfTrue(), x_branch);
 433   Node* x_false = T.graph.NewNode(T.common.IfFalse(), x_branch);
 434
 435   outer.loop->ReplaceInput(1, x_true);
 436   outer.loop->ReplaceInput(2, x_false);
 437
 438   Node* ret =
 439       T.graph.NewNode(T.common.Return(), outer_phi, T.start, outer.exit);
 440   Node* end = T.graph.NewNode(T.common.End(), ret);
 441   T.graph.SetEnd(end);
 442
 443   T.DeconstructOsr();
 444
 445   // Check structure of deconstructed graph.
 446   // Check inner OSR loop is directly connected to start.
 447   CheckInputs(inner.loop, T.start, inner.if_true);
 448   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), inner.loop);
 449
 450   // Check control transfer to copy of outer loop.
 451   Node* new_merge = FindSuccessor(x_true, IrOpcode::kMerge);
 452   CHECK_EQ(new_merge, FindSuccessor(x_false, IrOpcode::kMerge));
 453   CheckInputs(new_merge, x_true, x_false);
 454
 455   Node* new_outer_loop = FindSuccessor(new_merge, IrOpcode::kLoop);
 456   Node* new_outer_phi = FindSuccessor(new_outer_loop, IrOpcode::kPhi);
 457   CHECK_NE(new_outer_loop, outer.loop);
 458   CHECK_NE(new_outer_phi, outer_phi);
 459
 460   Node* new_entry_phi = FindSuccessor(new_merge, IrOpcode::kPhi);
 461   CheckInputs(new_entry_phi, osr_phi, T.jsgraph.ZeroConstant(), new_merge);
 462
 463   CHECK_EQ(new_merge, new_outer_loop->InputAt(0));
 464
 465   // Check structure of outer loop.
 466   Node* new_outer_branch = FindSuccessor(new_outer_loop, IrOpcode::kBranch);
 467   CHECK_NE(new_outer_branch, outer.branch);
 468   CheckInputs(new_outer_branch, new_outer_phi, new_outer_loop);
 469   Node* new_outer_exit = FindSuccessor(new_outer_branch, IrOpcode::kIfFalse);
 470   Node* new_outer_if_true = FindSuccessor(new_outer_branch, IrOpcode::kIfTrue);
 471
 472   // Check structure of return.
 473   end = T.graph.end();
 474   Node* new_ret = end->InputAt(0);
 475   CHECK_EQ(IrOpcode::kReturn, new_ret->opcode());
 476   CheckInputs(new_ret, new_outer_phi, T.start, new_outer_exit);
 477
 478   // Check structure of inner loop.
 479   Node* new_inner_loop = FindSuccessor(new_outer_if_true, IrOpcode::kLoop);
 480   Node* new_inner_phi = FindSuccessor(new_inner_loop, IrOpcode::kPhi);
 481
 482   CheckInputs(new_inner_phi, T.jsgraph.OneConstant(), T.jsgraph.ZeroConstant(),
 483               new_inner_loop);
 484   CheckInputs(new_outer_phi, new_entry_phi, new_inner_phi,
 485               T.jsgraph.ZeroConstant(), new_outer_loop);
 486 }