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.
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"
16 using namespace v8::internal;
17 using namespace v8::internal::compiler;
19 // TODO(titzer): move this method to a common testing place.
21 static int CheckInputs(Node* node, Node* i0 = NULL, Node* i1 = NULL,
22 Node* i2 = NULL, Node* i3 = NULL) {
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));
37 static Operator kIntLt(IrOpcode::kInt32LessThan, Operator::kPure,
38 "Int32LessThan", 2, 0, 0, 1, 0, 0);
41 static const int kMaxOsrValues = 10;
43 class OsrDeconstructorTester : public HandleAndZoneScope {
45 explicit OsrDeconstructorTester(int num_values)
46 : isolate(main_isolate()),
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);
64 CommonOperatorBuilder common;
70 Node* osr_normal_entry;
73 Node* osr_values[kMaxOsrValues];
75 Node* NewOsrPhi(Node* loop, Node* incoming, int osr_value, Node* back1 = NULL,
76 Node* back2 = NULL, Node* back3 = NULL) {
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));
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;
91 return graph.NewNode(common.Phi(kMachAnyTagged, count), count + 1, inputs);
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};
101 count = 2 + num_backedges;
102 inputs[1] = osr_loop_entry;
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);
113 Node* NewOsrLoop(int num_backedges, Node* entry = NULL) {
114 return NewLoop(true, num_backedges, entry);
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());
130 TEST(Deconstruct_osr0) {
131 OsrDeconstructorTester T(0);
133 Node* loop = T.NewOsrLoop(1);
135 T.graph.SetEnd(loop);
139 CheckInputs(loop, T.start, loop);
143 TEST(Deconstruct_osr1) {
144 OsrDeconstructorTester T(1);
146 Node* loop = T.NewOsrLoop(1);
148 T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
150 Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, loop);
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);
161 TEST(Deconstruct_osr1_type) {
162 OsrDeconstructorTester T(1);
164 Node* loop = T.NewOsrLoop(1);
166 T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
167 Type* type = Type::Signed32();
168 NodeProperties::SetBounds(osr_phi, Bounds(type, type));
170 Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, loop);
173 OsrHelper helper(0, 0);
174 helper.Deconstruct(&T.jsgraph, &T.common, T.main_zone());
176 CHECK_EQ(type, NodeProperties::GetBounds(T.osr_values[0]).lower);
177 CHECK_EQ(type, NodeProperties::GetBounds(T.osr_values[0]).upper);
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);
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);
190 Node* loop = T.NewOsrLoop(1, d.merge);
192 T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
194 Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, loop);
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);
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));
212 TEST(Deconstruct_osr_with_body1) {
213 OsrDeconstructorTester T(1);
215 Node* loop = T.NewOsrLoop(1);
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);
223 T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
225 Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, if_false);
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);
239 TEST(Deconstruct_osr_with_body2) {
240 OsrDeconstructorTester T(1);
242 Node* loop = T.NewOsrLoop(1);
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);
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);
255 T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant());
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);
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);
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);
277 TEST(Deconstruct_osr_with_body3) {
278 OsrDeconstructorTester T(1);
280 Node* loop = T.NewOsrLoop(2);
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);
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);
294 T.NewOsrPhi(loop, T.jsgraph.OneConstant(), 0, T.jsgraph.ZeroConstant(),
295 T.jsgraph.ZeroConstant());
297 Node* ret = T.graph.NewNode(T.common.Return(), osr_phi, T.start, if_false2);
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);
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);
317 OsrDeconstructorTester& t;
323 While(OsrDeconstructorTester& R, Node* cond, bool is_osr, int backedges = 1)
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);
332 void Nest(While& that) {
333 that.loop->ReplaceInput(that.loop->InputCount() - 1, exit);
334 this->loop->ReplaceInput(0, that.if_true);
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);
341 return t.graph.NewNode(t.common.Phi(kMachAnyTagged, 3), i1, i2, i3, loop);
347 static Node* FindSuccessor(Node* node, IrOpcode::Value opcode) {
348 for (Node* use : node->uses()) {
349 if (use->opcode() == opcode) return use;
351 UNREACHABLE(); // should have been found.
356 TEST(Deconstruct_osr_nested1) {
357 OsrDeconstructorTester T(1);
359 While outer(T, T.p0, false);
360 While inner(T, T.p0, true);
363 Node* outer_phi = outer.Phi(T.p0, T.p0, nullptr);
364 outer.branch->ReplaceInput(0, outer_phi);
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);
372 T.graph.NewNode(T.common.Return(), outer_phi, T.start, outer.exit);
373 Node* end = T.graph.NewNode(T.common.End(), ret);
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);
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);
389 CheckInputs(new_outer_loop, inner.exit, new_outer_loop->InputAt(1));
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);
398 // Check structure of return.
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);
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);
408 CheckInputs(new_inner_phi, T.jsgraph.OneConstant(), T.jsgraph.ZeroConstant(),
410 CheckInputs(new_outer_phi, osr_phi, new_inner_phi, new_outer_loop);
414 TEST(Deconstruct_osr_nested2) {
415 OsrDeconstructorTester T(1);
417 // Test multiple backedge outer loop.
418 While outer(T, T.p0, false, 2);
419 While inner(T, T.p0, true);
422 Node* outer_phi = outer.Phi(T.p0, T.p0, T.p0);
423 outer.branch->ReplaceInput(0, outer_phi);
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());
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);
435 outer.loop->ReplaceInput(1, x_true);
436 outer.loop->ReplaceInput(2, x_false);
439 T.graph.NewNode(T.common.Return(), outer_phi, T.start, outer.exit);
440 Node* end = T.graph.NewNode(T.common.End(), ret);
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);
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);
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);
460 Node* new_entry_phi = FindSuccessor(new_merge, IrOpcode::kPhi);
461 CheckInputs(new_entry_phi, osr_phi, T.jsgraph.ZeroConstant(), new_merge);
463 CHECK_EQ(new_merge, new_outer_loop->InputAt(0));
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);
472 // Check structure of return.
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);
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);
482 CheckInputs(new_inner_phi, T.jsgraph.OneConstant(), T.jsgraph.ZeroConstant(),
484 CheckInputs(new_outer_phi, new_entry_phi, new_inner_phi,
485 T.jsgraph.ZeroConstant(), new_outer_loop);