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/compiler/access-builder.h" 6 #include "src/compiler/graph.h" 7 #include "src/compiler/graph-visualizer.h" 8 #include "src/compiler/js-graph.h" 9 #include "src/compiler/loop-peeling.h" 10 #include "src/compiler/machine-operator.h" 11 #include "src/compiler/node.h" 12 #include "src/compiler/node-properties.h" 13 #include "test/unittests/compiler/compiler-test-utils.h" 14 #include "test/unittests/compiler/graph-unittest.h" 15 #include "test/unittests/compiler/node-test-utils.h" 16 #include "testing/gmock-support.h" 17 18 using testing::AllOf; 19 using testing::BitEq; 20 using testing::Capture; 21 using testing::CaptureEq; 22 23 namespace v8 { 24 namespace internal { 25 namespace compiler { 26 27 struct While { 28 Node* loop; 29 Node* branch; 30 Node* if_true; 31 Node* exit; 32 }; 33 34 35 // A helper for building branches. 36 struct Branch { 37 Node* branch; 38 Node* if_true; 39 Node* if_false; 40 }; 41 42 43 // A helper for building counters attached to loops. 44 struct Counter { 45 Node* base; 46 Node* inc; 47 Node* phi; 48 Node* add; 49 }; 50 51 52 class LoopPeelingTest : public GraphTest { 53 public: 54 LoopPeelingTest() : GraphTest(1), machine_(zone()) {} 55 ~LoopPeelingTest() override {} 56 57 protected: 58 MachineOperatorBuilder machine_; 59 60 MachineOperatorBuilder* machine() { return &machine_; } 61 62 LoopTree* GetLoopTree() { 63 if (FLAG_trace_turbo_graph) { 64 OFStream os(stdout); 65 os << AsRPO(*graph()); 66 } 67 Zone zone(isolate()->allocator()); 68 return LoopFinder::BuildLoopTree(graph(), &zone); 69 } 70 71 72 PeeledIteration* PeelOne() { 73 LoopTree* loop_tree = GetLoopTree(); 74 LoopTree::Loop* loop = loop_tree->outer_loops()[0]; 75 EXPECT_TRUE(LoopPeeler::CanPeel(loop_tree, loop)); 76 return Peel(loop_tree, loop); 77 } 78 79 PeeledIteration* Peel(LoopTree* loop_tree, LoopTree::Loop* loop) { 80 EXPECT_TRUE(LoopPeeler::CanPeel(loop_tree, loop)); 81 PeeledIteration* peeled = 82 LoopPeeler::Peel(graph(), common(), loop_tree, loop, zone()); 83 if (FLAG_trace_turbo_graph) { 84 OFStream os(stdout); 85 os << AsRPO(*graph()); 86 } 87 return peeled; 88 } 89 90 Node* InsertReturn(Node* val, Node* effect, Node* control) { 91 Node* r = graph()->NewNode(common()->Return(), val, effect, control); 92 graph()->SetEnd(r); 93 return r; 94 } 95 96 Node* ExpectPeeled(Node* node, PeeledIteration* iter) { 97 Node* p = iter->map(node); 98 EXPECT_NE(node, p); 99 return p; 100 } 101 102 void ExpectNotPeeled(Node* node, PeeledIteration* iter) { 103 EXPECT_EQ(node, iter->map(node)); 104 } 105 106 While NewWhile(Node* cond, Node* control = nullptr) { 107 if (control == nullptr) control = start(); 108 Node* loop = graph()->NewNode(common()->Loop(2), control, control); 109 Node* branch = graph()->NewNode(common()->Branch(), cond, loop); 110 Node* if_true = graph()->NewNode(common()->IfTrue(), branch); 111 Node* exit = graph()->NewNode(common()->IfFalse(), branch); 112 loop->ReplaceInput(1, if_true); 113 return {loop, branch, if_true, exit}; 114 } 115 116 void Chain(While* a, Node* control) { a->loop->ReplaceInput(0, control); } 117 void Nest(While* a, While* b) { 118 b->loop->ReplaceInput(1, a->exit); 119 a->loop->ReplaceInput(0, b->if_true); 120 } 121 Node* NewPhi(While* w, Node* a, Node* b) { 122 return graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), a, 123 b, w->loop); 124 } 125 126 Branch NewBranch(Node* cond, Node* control = nullptr) { 127 if (control == nullptr) control = start(); 128 Node* branch = graph()->NewNode(common()->Branch(), cond, control); 129 Node* if_true = graph()->NewNode(common()->IfTrue(), branch); 130 Node* if_false = graph()->NewNode(common()->IfFalse(), branch); 131 return {branch, if_true, if_false}; 132 } 133 134 Counter NewCounter(While* w, int32_t b, int32_t k) { 135 Node* base = Int32Constant(b); 136 Node* inc = Int32Constant(k); 137 Node* phi = graph()->NewNode( 138 common()->Phi(MachineRepresentation::kTagged, 2), base, base, w->loop); 139 Node* add = graph()->NewNode(machine()->Int32Add(), phi, inc); 140 phi->ReplaceInput(1, add); 141 return {base, inc, phi, add}; 142 } 143 }; 144 145 146 TEST_F(LoopPeelingTest, SimpleLoop) { 147 Node* p0 = Parameter(0); 148 While w = NewWhile(p0); 149 Node* r = InsertReturn(p0, start(), w.exit); 150 151 PeeledIteration* peeled = PeelOne(); 152 153 Node* br1 = ExpectPeeled(w.branch, peeled); 154 Node* if_true1 = ExpectPeeled(w.if_true, peeled); 155 Node* if_false1 = ExpectPeeled(w.exit, peeled); 156 157 EXPECT_THAT(br1, IsBranch(p0, start())); 158 EXPECT_THAT(if_true1, IsIfTrue(br1)); 159 EXPECT_THAT(if_false1, IsIfFalse(br1)); 160 161 EXPECT_THAT(w.loop, IsLoop(if_true1, w.if_true)); 162 EXPECT_THAT(r, IsReturn(p0, start(), IsMerge(w.exit, if_false1))); 163 } 164 165 166 TEST_F(LoopPeelingTest, SimpleLoopWithCounter) { 167 Node* p0 = Parameter(0); 168 While w = NewWhile(p0); 169 Counter c = NewCounter(&w, 0, 1); 170 Node* r = InsertReturn(c.phi, start(), w.exit); 171 172 PeeledIteration* peeled = PeelOne(); 173 174 Node* br1 = ExpectPeeled(w.branch, peeled); 175 Node* if_true1 = ExpectPeeled(w.if_true, peeled); 176 Node* if_false1 = ExpectPeeled(w.exit, peeled); 177 178 EXPECT_THAT(br1, IsBranch(p0, start())); 179 EXPECT_THAT(if_true1, IsIfTrue(br1)); 180 EXPECT_THAT(if_false1, IsIfFalse(br1)); 181 EXPECT_THAT(w.loop, IsLoop(if_true1, w.if_true)); 182 183 EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); 184 185 Capture<Node*> merge; 186 EXPECT_THAT( 187 r, IsReturn(IsPhi(MachineRepresentation::kTagged, c.phi, c.base, 188 AllOf(CaptureEq(&merge), IsMerge(w.exit, if_false1))), 189 start(), CaptureEq(&merge))); 190 } 191 192 193 TEST_F(LoopPeelingTest, SimpleNestedLoopWithCounter_peel_outer) { 194 Node* p0 = Parameter(0); 195 While outer = NewWhile(p0); 196 While inner = NewWhile(p0); 197 Nest(&inner, &outer); 198 199 Counter c = NewCounter(&outer, 0, 1); 200 Node* r = InsertReturn(c.phi, start(), outer.exit); 201 202 PeeledIteration* peeled = PeelOne(); 203 204 Node* bro = ExpectPeeled(outer.branch, peeled); 205 Node* if_trueo = ExpectPeeled(outer.if_true, peeled); 206 Node* if_falseo = ExpectPeeled(outer.exit, peeled); 207 208 EXPECT_THAT(bro, IsBranch(p0, start())); 209 EXPECT_THAT(if_trueo, IsIfTrue(bro)); 210 EXPECT_THAT(if_falseo, IsIfFalse(bro)); 211 212 Node* bri = ExpectPeeled(inner.branch, peeled); 213 Node* if_truei = ExpectPeeled(inner.if_true, peeled); 214 Node* if_falsei = ExpectPeeled(inner.exit, peeled); 215 216 EXPECT_THAT(bri, IsBranch(p0, ExpectPeeled(inner.loop, peeled))); 217 EXPECT_THAT(if_truei, IsIfTrue(bri)); 218 EXPECT_THAT(if_falsei, IsIfFalse(bri)); 219 220 EXPECT_THAT(outer.loop, IsLoop(if_falsei, inner.exit)); 221 EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); 222 223 Capture<Node*> merge; 224 EXPECT_THAT( 225 r, 226 IsReturn(IsPhi(MachineRepresentation::kTagged, c.phi, c.base, 227 AllOf(CaptureEq(&merge), IsMerge(outer.exit, if_falseo))), 228 start(), CaptureEq(&merge))); 229 } 230 231 232 TEST_F(LoopPeelingTest, SimpleNestedLoopWithCounter_peel_inner) { 233 Node* p0 = Parameter(0); 234 While outer = NewWhile(p0); 235 While inner = NewWhile(p0); 236 Nest(&inner, &outer); 237 238 Counter c = NewCounter(&outer, 0, 1); 239 Node* r = InsertReturn(c.phi, start(), outer.exit); 240 241 LoopTree* loop_tree = GetLoopTree(); 242 LoopTree::Loop* loop = loop_tree->ContainingLoop(inner.loop); 243 EXPECT_NE(nullptr, loop); 244 EXPECT_EQ(1u, loop->depth()); 245 246 PeeledIteration* peeled = Peel(loop_tree, loop); 247 248 ExpectNotPeeled(outer.loop, peeled); 249 ExpectNotPeeled(outer.branch, peeled); 250 ExpectNotPeeled(outer.if_true, peeled); 251 ExpectNotPeeled(outer.exit, peeled); 252 253 Node* bri = ExpectPeeled(inner.branch, peeled); 254 Node* if_truei = ExpectPeeled(inner.if_true, peeled); 255 Node* if_falsei = ExpectPeeled(inner.exit, peeled); 256 257 EXPECT_THAT(bri, IsBranch(p0, ExpectPeeled(inner.loop, peeled))); 258 EXPECT_THAT(if_truei, IsIfTrue(bri)); 259 EXPECT_THAT(if_falsei, IsIfFalse(bri)); 260 261 EXPECT_THAT(outer.loop, IsLoop(start(), IsMerge(inner.exit, if_falsei))); 262 ExpectNotPeeled(c.add, peeled); 263 264 EXPECT_THAT(r, IsReturn(c.phi, start(), outer.exit)); 265 } 266 267 268 TEST_F(LoopPeelingTest, SimpleInnerCounter_peel_inner) { 269 Node* p0 = Parameter(0); 270 While outer = NewWhile(p0); 271 While inner = NewWhile(p0); 272 Nest(&inner, &outer); 273 Counter c = NewCounter(&inner, 0, 1); 274 Node* phi = NewPhi(&outer, Int32Constant(11), c.phi); 275 276 Node* r = InsertReturn(phi, start(), outer.exit); 277 278 LoopTree* loop_tree = GetLoopTree(); 279 LoopTree::Loop* loop = loop_tree->ContainingLoop(inner.loop); 280 EXPECT_NE(nullptr, loop); 281 EXPECT_EQ(1u, loop->depth()); 282 283 PeeledIteration* peeled = Peel(loop_tree, loop); 284 285 ExpectNotPeeled(outer.loop, peeled); 286 ExpectNotPeeled(outer.branch, peeled); 287 ExpectNotPeeled(outer.if_true, peeled); 288 ExpectNotPeeled(outer.exit, peeled); 289 290 Node* bri = ExpectPeeled(inner.branch, peeled); 291 Node* if_truei = ExpectPeeled(inner.if_true, peeled); 292 Node* if_falsei = ExpectPeeled(inner.exit, peeled); 293 294 EXPECT_THAT(bri, IsBranch(p0, ExpectPeeled(inner.loop, peeled))); 295 EXPECT_THAT(if_truei, IsIfTrue(bri)); 296 EXPECT_THAT(if_falsei, IsIfFalse(bri)); 297 298 EXPECT_THAT(outer.loop, IsLoop(start(), IsMerge(inner.exit, if_falsei))); 299 EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); 300 301 Node* back = phi->InputAt(1); 302 EXPECT_THAT(back, IsPhi(MachineRepresentation::kTagged, c.phi, c.base, 303 IsMerge(inner.exit, if_falsei))); 304 305 EXPECT_THAT(phi, IsPhi(MachineRepresentation::kTagged, IsInt32Constant(11), 306 back, outer.loop)); 307 308 EXPECT_THAT(r, IsReturn(phi, start(), outer.exit)); 309 } 310 311 312 TEST_F(LoopPeelingTest, TwoBackedgeLoop) { 313 Node* p0 = Parameter(0); 314 Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); 315 Branch b1 = NewBranch(p0, loop); 316 Branch b2 = NewBranch(p0, b1.if_true); 317 318 loop->ReplaceInput(1, b2.if_true); 319 loop->ReplaceInput(2, b2.if_false); 320 321 Node* r = InsertReturn(p0, start(), b1.if_false); 322 323 PeeledIteration* peeled = PeelOne(); 324 325 Node* b1b = ExpectPeeled(b1.branch, peeled); 326 Node* b1t = ExpectPeeled(b1.if_true, peeled); 327 Node* b1f = ExpectPeeled(b1.if_false, peeled); 328 329 EXPECT_THAT(b1b, IsBranch(p0, start())); 330 EXPECT_THAT(ExpectPeeled(b1.if_true, peeled), IsIfTrue(b1b)); 331 EXPECT_THAT(b1f, IsIfFalse(b1b)); 332 333 Node* b2b = ExpectPeeled(b2.branch, peeled); 334 Node* b2t = ExpectPeeled(b2.if_true, peeled); 335 Node* b2f = ExpectPeeled(b2.if_false, peeled); 336 337 EXPECT_THAT(b2b, IsBranch(p0, b1t)); 338 EXPECT_THAT(b2t, IsIfTrue(b2b)); 339 EXPECT_THAT(b2f, IsIfFalse(b2b)); 340 341 EXPECT_THAT(loop, IsLoop(IsMerge(b2t, b2f), b2.if_true, b2.if_false)); 342 EXPECT_THAT(r, IsReturn(p0, start(), IsMerge(b1.if_false, b1f))); 343 } 344 345 346 TEST_F(LoopPeelingTest, TwoBackedgeLoopWithPhi) { 347 Node* p0 = Parameter(0); 348 Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); 349 Branch b1 = NewBranch(p0, loop); 350 Branch b2 = NewBranch(p0, b1.if_true); 351 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 3), 352 Int32Constant(0), Int32Constant(1), 353 Int32Constant(2), loop); 354 355 loop->ReplaceInput(1, b2.if_true); 356 loop->ReplaceInput(2, b2.if_false); 357 358 Node* r = InsertReturn(phi, start(), b1.if_false); 359 360 PeeledIteration* peeled = PeelOne(); 361 362 Node* b1b = ExpectPeeled(b1.branch, peeled); 363 Node* b1t = ExpectPeeled(b1.if_true, peeled); 364 Node* b1f = ExpectPeeled(b1.if_false, peeled); 365 366 EXPECT_THAT(b1b, IsBranch(p0, start())); 367 EXPECT_THAT(ExpectPeeled(b1.if_true, peeled), IsIfTrue(b1b)); 368 EXPECT_THAT(b1f, IsIfFalse(b1b)); 369 370 Node* b2b = ExpectPeeled(b2.branch, peeled); 371 Node* b2t = ExpectPeeled(b2.if_true, peeled); 372 Node* b2f = ExpectPeeled(b2.if_false, peeled); 373 374 EXPECT_THAT(b2b, IsBranch(p0, b1t)); 375 EXPECT_THAT(b2t, IsIfTrue(b2b)); 376 EXPECT_THAT(b2f, IsIfFalse(b2b)); 377 378 EXPECT_THAT(loop, IsLoop(IsMerge(b2t, b2f), b2.if_true, b2.if_false)); 379 380 EXPECT_THAT(phi, 381 IsPhi(MachineRepresentation::kTagged, 382 IsPhi(MachineRepresentation::kTagged, IsInt32Constant(1), 383 IsInt32Constant(2), IsMerge(b2t, b2f)), 384 IsInt32Constant(1), IsInt32Constant(2), loop)); 385 386 Capture<Node*> merge; 387 EXPECT_THAT( 388 r, IsReturn(IsPhi(MachineRepresentation::kTagged, phi, IsInt32Constant(0), 389 AllOf(CaptureEq(&merge), IsMerge(b1.if_false, b1f))), 390 start(), CaptureEq(&merge))); 391 } 392 393 394 TEST_F(LoopPeelingTest, TwoBackedgeLoopWithCounter) { 395 Node* p0 = Parameter(0); 396 Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); 397 Branch b1 = NewBranch(p0, loop); 398 Branch b2 = NewBranch(p0, b1.if_true); 399 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 3), 400 Int32Constant(0), Int32Constant(1), 401 Int32Constant(2), loop); 402 403 phi->ReplaceInput( 404 1, graph()->NewNode(machine()->Int32Add(), phi, Int32Constant(1))); 405 phi->ReplaceInput( 406 2, graph()->NewNode(machine()->Int32Add(), phi, Int32Constant(2))); 407 408 loop->ReplaceInput(1, b2.if_true); 409 loop->ReplaceInput(2, b2.if_false); 410 411 Node* r = InsertReturn(phi, start(), b1.if_false); 412 413 PeeledIteration* peeled = PeelOne(); 414 415 Node* b1b = ExpectPeeled(b1.branch, peeled); 416 Node* b1t = ExpectPeeled(b1.if_true, peeled); 417 Node* b1f = ExpectPeeled(b1.if_false, peeled); 418 419 EXPECT_THAT(b1b, IsBranch(p0, start())); 420 EXPECT_THAT(ExpectPeeled(b1.if_true, peeled), IsIfTrue(b1b)); 421 EXPECT_THAT(b1f, IsIfFalse(b1b)); 422 423 Node* b2b = ExpectPeeled(b2.branch, peeled); 424 Node* b2t = ExpectPeeled(b2.if_true, peeled); 425 Node* b2f = ExpectPeeled(b2.if_false, peeled); 426 427 EXPECT_THAT(b2b, IsBranch(p0, b1t)); 428 EXPECT_THAT(b2t, IsIfTrue(b2b)); 429 EXPECT_THAT(b2f, IsIfFalse(b2b)); 430 431 Capture<Node*> entry; 432 EXPECT_THAT(loop, IsLoop(AllOf(CaptureEq(&entry), IsMerge(b2t, b2f)), 433 b2.if_true, b2.if_false)); 434 435 Node* eval = phi->InputAt(0); 436 437 EXPECT_THAT(eval, IsPhi(MachineRepresentation::kTagged, 438 IsInt32Add(IsInt32Constant(0), IsInt32Constant(1)), 439 IsInt32Add(IsInt32Constant(0), IsInt32Constant(2)), 440 CaptureEq(&entry))); 441 442 EXPECT_THAT(phi, IsPhi(MachineRepresentation::kTagged, eval, 443 IsInt32Add(phi, IsInt32Constant(1)), 444 IsInt32Add(phi, IsInt32Constant(2)), loop)); 445 446 Capture<Node*> merge; 447 EXPECT_THAT( 448 r, IsReturn(IsPhi(MachineRepresentation::kTagged, phi, IsInt32Constant(0), 449 AllOf(CaptureEq(&merge), IsMerge(b1.if_false, b1f))), 450 start(), CaptureEq(&merge))); 451 } 452 453 454 TEST_F(LoopPeelingTest, TwoExitLoop_nope) { 455 Node* p0 = Parameter(0); 456 Node* loop = graph()->NewNode(common()->Loop(2), start(), start()); 457 Branch b1 = NewBranch(p0, loop); 458 Branch b2 = NewBranch(p0, b1.if_true); 459 460 loop->ReplaceInput(1, b2.if_true); 461 Node* merge = graph()->NewNode(common()->Merge(2), b1.if_false, b2.if_false); 462 InsertReturn(p0, start(), merge); 463 464 { 465 LoopTree* loop_tree = GetLoopTree(); 466 LoopTree::Loop* loop = loop_tree->outer_loops()[0]; 467 EXPECT_FALSE(LoopPeeler::CanPeel(loop_tree, loop)); 468 } 469 } 470 471 472 const Operator kMockCall(IrOpcode::kCall, Operator::kNoProperties, "MockCall", 473 0, 0, 1, 1, 1, 2); 474 475 476 TEST_F(LoopPeelingTest, TwoExitLoopWithCall_nope) { 477 Node* p0 = Parameter(0); 478 Node* loop = graph()->NewNode(common()->Loop(2), start(), start()); 479 Branch b1 = NewBranch(p0, loop); 480 481 Node* call = graph()->NewNode(&kMockCall, b1.if_true); 482 Node* if_success = graph()->NewNode(common()->IfSuccess(), call); 483 Node* if_exception = graph()->NewNode( 484 common()->IfException(IfExceptionHint::kLocallyUncaught), call, call); 485 486 loop->ReplaceInput(1, if_success); 487 Node* merge = graph()->NewNode(common()->Merge(2), b1.if_false, if_exception); 488 InsertReturn(p0, start(), merge); 489 490 { 491 LoopTree* loop_tree = GetLoopTree(); 492 LoopTree::Loop* loop = loop_tree->outer_loops()[0]; 493 EXPECT_FALSE(LoopPeeler::CanPeel(loop_tree, loop)); 494 } 495 } 496 497 498 } // namespace compiler 499 } // namespace internal 500 } // namespace v8 501
