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 static Operator kIntAdd(IrOpcode::kInt32Add, Operator::kPure, "Int32Add", 2, 0,
  40                         0, 1, 0, 0);
  41
  42
  43 static const int kMaxOsrValues = 10;
  44
  45 class OsrDeconstructorTester : public HandleAndZoneScope {
  46  public:
  47   explicit OsrDeconstructorTester(int num_values)
  48       : isolate(main_isolate()),
  49         common(main_zone()),
  50         graph(main_zone()),
  51         jsgraph(main_isolate(), &graph, &common, NULL, NULL),
  52         start(graph.NewNode(common.Start(1))),
  53         p0(graph.NewNode(common.Parameter(0), start)),
  54         end(graph.NewNode(common.End(), start)),
  55         osr_normal_entry(graph.NewNode(common.OsrNormalEntry(), start, start)),
  56         osr_loop_entry(graph.NewNode(common.OsrLoopEntry(), start, start)),
  57         self(graph.NewNode(common.Int32Constant(0xaabbccdd))) {
  58     CHECK(num_values <= kMaxOsrValues);
  59     graph.SetStart(start);
  60     for (int i = 0; i < num_values; i++) {
  61       osr_values[i] = graph.NewNode(common.OsrValue(i), osr_loop_entry);
  62     }
  63   }
  64
  65   Isolate* isolate;
  66   CommonOperatorBuilder common;
  67   Graph graph;
  68   JSGraph jsgraph;
  69   Node* start;
  70   Node* p0;
  71   Node* end;
  72   Node* osr_normal_entry;
  73   Node* osr_loop_entry;
  74   Node* self;
  75   Node* osr_values[kMaxOsrValues];
  76
  77   Node* NewOsrPhi(Node* loop, Node* incoming, int osr_value, Node* back1 = NULL,
  78                   Node* back2 = NULL, Node* back3 = NULL) {
  79     int count = 5;
  80     if (back3 == NULL) count = 4;
  81     if (back2 == NULL) count = 3;
  82     if (back1 == NULL) count = 2;
  83     CHECK_EQ(loop->InputCount(), count);
  84     CHECK_EQ(osr_loop_entry, loop->InputAt(1));
  85
  86     Node* inputs[6];
  87     inputs[0] = incoming;
  88     inputs[1] = osr_values[osr_value];
  89     if (count > 2) inputs[2] = back1;
  90     if (count > 3) inputs[3] = back2;
  91     if (count > 4) inputs[4] = back3;
  92     inputs[count] = loop;
  93     return graph.NewNode(common.Phi(kMachAnyTagged, count), count + 1, inputs);
  94   }
  95
  96   Node* NewLoop(bool is_osr, int num_backedges, Node* entry = NULL) {
  97     CHECK_LT(num_backedges, 4);
  98     CHECK_GE(num_backedges, 0);
  99     int count = 1 + num_backedges;
 100     if (entry == NULL) entry = osr_normal_entry;
 101     Node* inputs[5] = {entry, self, self, self, self};
 102     if (is_osr) {
 103       count = 2 + num_backedges;
 104       inputs[1] = osr_loop_entry;
 105     }
 106
 107     Node* loop = graph.NewNode(common.Loop(count), count, inputs);
 108     for (int i = 0; i < loop->InputCount(); i++) {
 109       if (loop->InputAt(i) == self) loop->ReplaceInput(i, loop);
 110     }
 111
 112     return loop;
 113   }
 114
 115   Node* NewOsrLoop(int num_backedges, Node* entry = NULL) {
 116     return NewLoop(true, num_backedges, entry);
 117   }
 118
 119   void DeconstructOsr() {
 120     OsrHelper helper(0, 0);
 121     helper.Deconstruct(&jsgraph, &common, main_zone());
 122     AllNodes nodes(main_zone(), &graph);
 123     // Should be edited out.
 124     CHECK(!nodes.IsLive(osr_normal_entry));
 125     CHECK(!nodes.IsLive(osr_loop_entry));
 126     // No dangling nodes should be left over.
 127     for (Node* const node : nodes.live) {
 128       for (Node* const use : node->uses()) {
 129         CHECK(std::find(nodes.live.begin(), nodes.live.end(), use) !=
 130               nodes.live.end());
 131       }
 132     }
 133   }
 134 };
 135
 136
 137 TEST(Deconstruct_osr0) {
 138   OsrDeconstructorTester T(0);
 139
 140   Node* loop = T.NewOsrLoop(1);
 141
 142   T.graph.SetEnd(loop);
 143
 144   T.DeconstructOsr();
 145
 146   CheckInputs(loop, T.start, loop);
 147 }
 148
 149
 150 TEST(Deconstruct_osr1) {
 151   OsrDeconstructorTester T(1);
 152
 153   Node* loop = T.NewOsrLoop(1);
 154   Node* osr_phi =
 155       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
 156
 157   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, loop);
 158   T.graph.SetEnd(ret);
 159
 160   T.DeconstructOsr();
 161
 162   CheckInputs(loop, T.start, loop);
 163   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), loop);
 164   CheckInputs(ret, osr_phi, T.start, loop);
 165 }
 166
 167
 168 TEST(Deconstruct_osr1_type) {
 169   OsrDeconstructorTester T(1);
 170
 171   Node* loop = T.NewOsrLoop(1);
 172   Node* osr_phi =
 173       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
 174   Type* type = Type::Signed32();
 175   NodeProperties::SetBounds(osr_phi, Bounds(type, type));
 176
 177   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, loop);
 178   T.graph.SetEnd(ret);
 179
 180   OsrHelper helper(0, 0);
 181   helper.Deconstruct(&T.jsgraph, &T.common, T.main_zone());
 182
 183   CHECK_EQ(type, NodeProperties::GetBounds(T.osr_values[0]).lower);
 184   CHECK_EQ(type, NodeProperties::GetBounds(T.osr_values[0]).upper);
 185
 186   CheckInputs(loop, T.start, loop);
 187   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), loop);
 188   CheckInputs(ret, osr_phi, T.start, loop);
 189 }
 190
 191
 192 TEST(Deconstruct_osr_remove_prologue) {
 193   OsrDeconstructorTester T(1);
 194   Diamond d(&T.graph, &T.common, T.p0);
 195   d.Chain(T.osr_normal_entry);
 196
 197   Node* loop = T.NewOsrLoop(1, d.merge);
 198   Node* osr_phi =
 199       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
 200
 201   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, loop);
 202   T.graph.SetEnd(ret);
 203
 204   T.DeconstructOsr();
 205
 206   CheckInputs(loop, T.start, loop);
 207   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), loop);
 208   CheckInputs(ret, osr_phi, T.start, loop);
 209
 210   // The control before the loop should have been removed.
 211   AllNodes nodes(T.main_zone(), &T.graph);
 212   CHECK(!nodes.IsLive(d.branch));
 213   CHECK(!nodes.IsLive(d.if_true));
 214   CHECK(!nodes.IsLive(d.if_false));
 215   CHECK(!nodes.IsLive(d.merge));
 216 }
 217
 218
 219 TEST(Deconstruct_osr_with_body1) {
 220   OsrDeconstructorTester T(1);
 221
 222   Node* loop = T.NewOsrLoop(1);
 223
 224   Node* branch = T.graph.NewNode(T.common.Branch(), T.p0, loop);
 225   Node* if_true = T.graph.NewNode(T.common.IfTrue(), branch);
 226   Node* if_false = T.graph.NewNode(T.common.IfFalse(), branch);
 227   loop->ReplaceInput(2, if_true);
 228
 229   Node* osr_phi =
 230       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
 231
 232   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, if_false);
 233   T.graph.SetEnd(ret);
 234
 235   T.DeconstructOsr();
 236
 237   CheckInputs(loop, T.start, if_true);
 238   CheckInputs(branch, T.p0, loop);
 239   CheckInputs(if_true, branch);
 240   CheckInputs(if_false, branch);
 241   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), loop);
 242   CheckInputs(ret, osr_phi, T.start, if_false);
 243 }
 244
 245
 246 TEST(Deconstruct_osr_with_body2) {
 247   OsrDeconstructorTester T(1);
 248
 249   Node* loop = T.NewOsrLoop(1);
 250
 251   // Two chained branches in the the body of the loop.
 252   Node* branch1 = T.graph.NewNode(T.common.Branch(), T.p0, loop);
 253   Node* if_true1 = T.graph.NewNode(T.common.IfTrue(), branch1);
 254   Node* if_false1 = T.graph.NewNode(T.common.IfFalse(), branch1);
 255
 256   Node* branch2 = T.graph.NewNode(T.common.Branch(), T.p0, if_true1);
 257   Node* if_true2 = T.graph.NewNode(T.common.IfTrue(), branch2);
 258   Node* if_false2 = T.graph.NewNode(T.common.IfFalse(), branch2);
 259   loop->ReplaceInput(2, if_true2);
 260
 261   Node* osr_phi =
 262       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
 263
 264   Node* merge = T.graph.NewNode(T.common.Merge(2), if_false1, if_false2);
 265   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, merge);
 266   T.graph.SetEnd(ret);
 267
 268   T.DeconstructOsr();
 269
 270   CheckInputs(loop, T.start, if_true2);
 271   CheckInputs(branch1, T.p0, loop);
 272   CheckInputs(branch2, T.p0, if_true1);
 273   CheckInputs(if_true1, branch1);
 274   CheckInputs(if_false1, branch1);
 275   CheckInputs(if_true2, branch2);
 276   CheckInputs(if_false2, branch2);
 277
 278   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), loop);
 279   CheckInputs(ret, osr_phi, T.start, merge);
 280   CheckInputs(merge, if_false1, if_false2);
 281 }
 282
 283
 284 TEST(Deconstruct_osr_with_body3) {
 285   OsrDeconstructorTester T(1);
 286
 287   Node* loop = T.NewOsrLoop(2);
 288
 289   // Two branches that create two different backedges.
 290   Node* branch1 = T.graph.NewNode(T.common.Branch(), T.p0, loop);
 291   Node* if_true1 = T.graph.NewNode(T.common.IfTrue(), branch1);
 292   Node* if_false1 = T.graph.NewNode(T.common.IfFalse(), branch1);
 293
 294   Node* branch2 = T.graph.NewNode(T.common.Branch(), T.p0, if_true1);
 295   Node* if_true2 = T.graph.NewNode(T.common.IfTrue(), branch2);
 296   Node* if_false2 = T.graph.NewNode(T.common.IfFalse(), branch2);
 297   loop->ReplaceInput(2, if_false1);
 298   loop->ReplaceInput(3, if_true2);
 299
 300   Node* osr_phi =
 301       T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant(),
 302                   T.jsgraph.ZeroConstant());
 303
 304   Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, if_false2);
 305   T.graph.SetEnd(ret);
 306
 307   T.DeconstructOsr();
 308
 309   CheckInputs(loop, T.start, if_false1, if_true2);
 310   CheckInputs(branch1, T.p0, loop);
 311   CheckInputs(branch2, T.p0, if_true1);
 312   CheckInputs(if_true1, branch1);
 313   CheckInputs(if_false1, branch1);
 314   CheckInputs(if_true2, branch2);
 315   CheckInputs(if_false2, branch2);
 316
 317   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(),
 318               T.jsgraph.ZeroConstant(), loop);
 319   CheckInputs(ret, osr_phi, T.start, if_false2);
 320 }
 321
 322
 323 struct While {
 324   OsrDeconstructorTester& t;
 325   Node* branch;
 326   Node* if_true;
 327   Node* exit;
 328   Node* loop;
 329
 330   While(OsrDeconstructorTester& R, Node* cond, bool is_osr, int backedges = 1)
 331       : t(R) {
 332     loop = t.NewLoop(is_osr, backedges);
 333     branch = t.graph.NewNode(t.common.Branch(), cond, loop);
 334     if_true = t.graph.NewNode(t.common.IfTrue(), branch);
 335     exit = t.graph.NewNode(t.common.IfFalse(), branch);
 336     loop->ReplaceInput(loop->InputCount() - 1, if_true);
 337   }
 338
 339   void Nest(While& that) {
 340     that.loop->ReplaceInput(that.loop->InputCount() - 1, exit);
 341     this->loop->ReplaceInput(0, that.if_true);
 342   }
 343
 344   Node* Phi(Node* i1, Node* i2, Node* i3) {
 345     if (loop->InputCount() == 2) {
 346       return t.graph.NewNode(t.common.Phi(kMachAnyTagged, 2), i1, i2, loop);
 347     } else {
 348       return t.graph.NewNode(t.common.Phi(kMachAnyTagged, 3), i1, i2, i3, loop);
 349     }
 350   }
 351 };
 352
 353
 354 static Node* FindSuccessor(Node* node, IrOpcode::Value opcode) {
 355   for (Node* use : node->uses()) {
 356     if (use->opcode() == opcode) return use;
 357   }
 358   UNREACHABLE();  // should have been found.
 359   return nullptr;
 360 }
 361
 362
 363 TEST(Deconstruct_osr_nested1) {
 364   OsrDeconstructorTester T(1);
 365
 366   While outer(T, T.p0, false);
 367   While inner(T, T.p0, true);
 368   inner.Nest(outer);
 369
 370   Node* outer_phi = outer.Phi(T.p0, T.p0, nullptr);
 371   outer.branch->ReplaceInput(0, outer_phi);
 372
 373   Node* osr_phi = inner.Phi(T.jsgraph.OneConstant(), T.osr_values[0],
 374                             T.jsgraph.ZeroConstant());
 375   inner.branch->ReplaceInput(0, osr_phi);
 376   outer_phi->ReplaceInput(1, osr_phi);
 377
 378   Node* ret =
 379       T.graph.NewNode(T.common.Return(), outer_phi, T.start, outer.exit);
 380   Node* end = T.graph.NewNode(T.common.End(), ret);
 381   T.graph.SetEnd(end);
 382
 383   T.DeconstructOsr();
 384
 385   // Check structure of deconstructed graph.
 386   // Check inner OSR loop is directly connected to start.
 387   CheckInputs(inner.loop, T.start, inner.if_true);
 388   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), inner.loop);
 389
 390   // Check control transfer to copy of outer loop.
 391   Node* new_outer_loop = FindSuccessor(inner.exit, IrOpcode::kLoop);
 392   Node* new_outer_phi = FindSuccessor(new_outer_loop, IrOpcode::kPhi);
 393   CHECK_NE(new_outer_loop, outer.loop);
 394   CHECK_NE(new_outer_phi, outer_phi);
 395
 396   CheckInputs(new_outer_loop, inner.exit, new_outer_loop->InputAt(1));
 397
 398   // Check structure of outer loop.
 399   Node* new_outer_branch = FindSuccessor(new_outer_loop, IrOpcode::kBranch);
 400   CHECK_NE(new_outer_branch, outer.branch);
 401   CheckInputs(new_outer_branch, new_outer_phi, new_outer_loop);
 402   Node* new_outer_exit = FindSuccessor(new_outer_branch, IrOpcode::kIfFalse);
 403   Node* new_outer_if_true = FindSuccessor(new_outer_branch, IrOpcode::kIfTrue);
 404
 405   // Check structure of return.
 406   end = T.graph.end();
 407   Node* new_ret = end->InputAt(0);
 408   CHECK_EQ(IrOpcode::kReturn, new_ret->opcode());
 409   CheckInputs(new_ret, new_outer_phi, T.start, new_outer_exit);
 410
 411   // Check structure of inner loop.
 412   Node* new_inner_loop = FindSuccessor(new_outer_if_true, IrOpcode::kLoop);
 413   Node* new_inner_phi = FindSuccessor(new_inner_loop, IrOpcode::kPhi);
 414
 415   CheckInputs(new_inner_phi, T.jsgraph.OneConstant(), T.jsgraph.ZeroConstant(),
 416               new_inner_loop);
 417   CheckInputs(new_outer_phi, osr_phi, new_inner_phi, new_outer_loop);
 418 }
 419
 420
 421 TEST(Deconstruct_osr_nested2) {
 422   OsrDeconstructorTester T(1);
 423
 424   // Test multiple backedge outer loop.
 425   While outer(T, T.p0, false, 2);
 426   While inner(T, T.p0, true);
 427   inner.Nest(outer);
 428
 429   Node* outer_phi = outer.Phi(T.p0, T.p0, T.p0);
 430   outer.branch->ReplaceInput(0, outer_phi);
 431
 432   Node* osr_phi = inner.Phi(T.jsgraph.OneConstant(), T.osr_values[0],
 433                             T.jsgraph.ZeroConstant());
 434   inner.branch->ReplaceInput(0, osr_phi);
 435   outer_phi->ReplaceInput(1, osr_phi);
 436   outer_phi->ReplaceInput(2, T.jsgraph.ZeroConstant());
 437
 438   Node* x_branch = T.graph.NewNode(T.common.Branch(), osr_phi, inner.exit);
 439   Node* x_true = T.graph.NewNode(T.common.IfTrue(), x_branch);
 440   Node* x_false = T.graph.NewNode(T.common.IfFalse(), x_branch);
 441
 442   outer.loop->ReplaceInput(1, x_true);
 443   outer.loop->ReplaceInput(2, x_false);
 444
 445   Node* ret =
 446       T.graph.NewNode(T.common.Return(), outer_phi, T.start, outer.exit);
 447   Node* end = T.graph.NewNode(T.common.End(), ret);
 448   T.graph.SetEnd(end);
 449
 450   T.DeconstructOsr();
 451
 452   // Check structure of deconstructed graph.
 453   // Check inner OSR loop is directly connected to start.
 454   CheckInputs(inner.loop, T.start, inner.if_true);
 455   CheckInputs(osr_phi, T.osr_values[0], T.jsgraph.ZeroConstant(), inner.loop);
 456
 457   // Check control transfer to copy of outer loop.
 458   Node* new_merge = FindSuccessor(x_true, IrOpcode::kMerge);
 459   CHECK_EQ(new_merge, FindSuccessor(x_false, IrOpcode::kMerge));
 460   CheckInputs(new_merge, x_true, x_false);
 461
 462   Node* new_outer_loop = FindSuccessor(new_merge, IrOpcode::kLoop);
 463   Node* new_outer_phi = FindSuccessor(new_outer_loop, IrOpcode::kPhi);
 464   CHECK_NE(new_outer_loop, outer.loop);
 465   CHECK_NE(new_outer_phi, outer_phi);
 466
 467   Node* new_entry_phi = FindSuccessor(new_merge, IrOpcode::kPhi);
 468   CheckInputs(new_entry_phi, osr_phi, T.jsgraph.ZeroConstant(), new_merge);
 469
 470   CHECK_EQ(new_merge, new_outer_loop->InputAt(0));
 471
 472   // Check structure of outer loop.
 473   Node* new_outer_branch = FindSuccessor(new_outer_loop, IrOpcode::kBranch);
 474   CHECK_NE(new_outer_branch, outer.branch);
 475   CheckInputs(new_outer_branch, new_outer_phi, new_outer_loop);
 476   Node* new_outer_exit = FindSuccessor(new_outer_branch, IrOpcode::kIfFalse);
 477   Node* new_outer_if_true = FindSuccessor(new_outer_branch, IrOpcode::kIfTrue);
 478
 479   // Check structure of return.
 480   end = T.graph.end();
 481   Node* new_ret = end->InputAt(0);
 482   CHECK_EQ(IrOpcode::kReturn, new_ret->opcode());
 483   CheckInputs(new_ret, new_outer_phi, T.start, new_outer_exit);
 484
 485   // Check structure of inner loop.
 486   Node* new_inner_loop = FindSuccessor(new_outer_if_true, IrOpcode::kLoop);
 487   Node* new_inner_phi = FindSuccessor(new_inner_loop, IrOpcode::kPhi);
 488
 489   CheckInputs(new_inner_phi, T.jsgraph.OneConstant(), T.jsgraph.ZeroConstant(),
 490               new_inner_loop);
 491   CheckInputs(new_outer_phi, new_entry_phi, new_inner_phi,
 492               T.jsgraph.ZeroConstant(), new_outer_loop);
 493 }
 494
 495
 496 Node* MakeCounter(JSGraph* jsgraph, Node* start, Node* loop) {
 497   int count = loop->InputCount();
 498   NodeVector tmp_inputs(jsgraph->graph()->zone());
 499   for (int i = 0; i < count; i++) {
 500     tmp_inputs.push_back(start);
 501   }
 502   tmp_inputs.push_back(loop);
 503
 504   Node* phi = jsgraph->graph()->NewNode(
 505       jsgraph->common()->Phi(kMachInt32, count), count + 1, &tmp_inputs[0]);
 506   Node* inc = jsgraph->graph()->NewNode(&kIntAdd, phi, jsgraph->OneConstant());
 507
 508   for (int i = 1; i < count; i++) {
 509     phi->ReplaceInput(i, inc);
 510   }
 511   return phi;
 512 }
 513
 514
 515 TEST(Deconstruct_osr_nested3) {
 516   OsrDeconstructorTester T(1);
 517
 518   // outermost loop.
 519   While loop0(T, T.p0, false, 1);
 520   Node* loop0_cntr = MakeCounter(&T.jsgraph, T.p0, loop0.loop);
 521   loop0.branch->ReplaceInput(0, loop0_cntr);
 522
 523   // middle loop.
 524   Node* loop1 = T.graph.NewNode(T.common.Loop(2), loop0.if_true, T.self);
 525   loop1->ReplaceInput(0, loop0.if_true);
 526   Node* loop1_phi =
 527       T.graph.NewNode(T.common.Phi(kMachAnyTagged, 2), loop0_cntr, loop0_cntr);
 528
 529   // innermost (OSR) loop.
 530   While loop2(T, T.p0, true, 1);
 531   loop2.loop->ReplaceInput(0, loop1);
 532
 533   Node* loop2_cntr = MakeCounter(&T.jsgraph, loop1_phi, loop2.loop);
 534   loop2_cntr->ReplaceInput(1, T.osr_values[0]);
 535   Node* osr_phi = loop2_cntr;
 536   Node* loop2_inc = loop2_cntr->InputAt(2);
 537   loop2.branch->ReplaceInput(0, loop2_cntr);
 538
 539   loop1_phi->ReplaceInput(1, loop2_cntr);
 540   loop0_cntr->ReplaceInput(1, loop2_cntr);
 541
 542   // Branch to either the outer or middle loop.
 543   Node* branch = T.graph.NewNode(T.common.Branch(), loop2_cntr, loop2.exit);
 544   Node* if_true = T.graph.NewNode(T.common.IfTrue(), branch);
 545   Node* if_false = T.graph.NewNode(T.common.IfFalse(), branch);
 546
 547   loop0.loop->ReplaceInput(1, if_true);
 548   loop1->ReplaceInput(1, if_false);
 549
 550   Node* ret =
 551       T.graph.NewNode(T.common.Return(), loop0_cntr, T.start, loop0.exit);
 552   Node* end = T.graph.NewNode(T.common.End(), ret);
 553   T.graph.SetEnd(end);
 554
 555   T.DeconstructOsr();
 556
 557   // Check structure of deconstructed graph.
 558   // Check loop2 (OSR loop) is directly connected to start.
 559   CheckInputs(loop2.loop, T.start, loop2.if_true);
 560   CheckInputs(osr_phi, T.osr_values[0], loop2_inc, loop2.loop);
 561   CheckInputs(loop2.branch, osr_phi, loop2.loop);
 562   CheckInputs(loop2.if_true, loop2.branch);
 563   CheckInputs(loop2.exit, loop2.branch);
 564   CheckInputs(branch, osr_phi, loop2.exit);
 565   CheckInputs(if_true, branch);
 566   CheckInputs(if_false, branch);
 567
 568   // Check structure of new_loop1.
 569   Node* new_loop1_loop = FindSuccessor(if_false, IrOpcode::kLoop);
 570   // TODO(titzer): check the internal copy of loop2.
 571   USE(new_loop1_loop);
 572
 573   // Check structure of new_loop0.
 574   Node* new_loop0_loop_entry = FindSuccessor(if_true, IrOpcode::kMerge);
 575   Node* new_loop0_loop = FindSuccessor(new_loop0_loop_entry, IrOpcode::kLoop);
 576   // TODO(titzer): check the internal copies of loop1 and loop2.
 577
 578   Node* new_loop0_branch = FindSuccessor(new_loop0_loop, IrOpcode::kBranch);
 579   Node* new_loop0_if_true = FindSuccessor(new_loop0_branch, IrOpcode::kIfTrue);
 580   Node* new_loop0_exit = FindSuccessor(new_loop0_branch, IrOpcode::kIfFalse);
 581
 582   USE(new_loop0_if_true);
 583
 584   Node* new_ret = T.graph.end()->InputAt(0);
 585   CHECK_EQ(IrOpcode::kReturn, new_ret->opcode());
 586
 587   Node* new_loop0_phi = new_ret->InputAt(0);
 588   CHECK_EQ(IrOpcode::kPhi, new_loop0_phi->opcode());
 589   CHECK_EQ(new_loop0_loop, NodeProperties::GetControlInput(new_loop0_phi));
 590   CHECK_EQ(new_loop0_phi, FindSuccessor(new_loop0_loop, IrOpcode::kPhi));
 591
 592   // Check that the return returns the phi from the OSR loop and control
 593   // depends on the copy of the outer loop0.
 594   CheckInputs(new_ret, new_loop0_phi, T.graph.start(), new_loop0_exit);
 595 }