OLD | NEW |
1 // Copyright 2015 the V8 project authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/compiler/access-builder.h" | 5 #include "src/compiler/access-builder.h" |
6 #include "src/compiler/graph.h" | 6 #include "src/compiler/graph.h" |
7 #include "src/compiler/graph-visualizer.h" | 7 #include "src/compiler/graph-visualizer.h" |
8 #include "src/compiler/js-graph.h" | 8 #include "src/compiler/js-graph.h" |
9 #include "src/compiler/loop-peeling.h" | 9 #include "src/compiler/loop-peeling.h" |
10 #include "src/compiler/machine-operator.h" | 10 #include "src/compiler/machine-operator.h" |
(...skipping 101 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
112 loop->ReplaceInput(1, if_true); | 112 loop->ReplaceInput(1, if_true); |
113 return {loop, branch, if_true, exit}; | 113 return {loop, branch, if_true, exit}; |
114 } | 114 } |
115 | 115 |
116 void Chain(While* a, Node* control) { a->loop->ReplaceInput(0, control); } | 116 void Chain(While* a, Node* control) { a->loop->ReplaceInput(0, control); } |
117 void Nest(While* a, While* b) { | 117 void Nest(While* a, While* b) { |
118 b->loop->ReplaceInput(1, a->exit); | 118 b->loop->ReplaceInput(1, a->exit); |
119 a->loop->ReplaceInput(0, b->if_true); | 119 a->loop->ReplaceInput(0, b->if_true); |
120 } | 120 } |
121 Node* NewPhi(While* w, Node* a, Node* b) { | 121 Node* NewPhi(While* w, Node* a, Node* b) { |
122 return graph()->NewNode(common()->Phi(kMachAnyTagged, 2), a, b, w->loop); | 122 return graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 2), a, |
| 123 b, w->loop); |
123 } | 124 } |
124 | 125 |
125 Branch NewBranch(Node* cond, Node* control = nullptr) { | 126 Branch NewBranch(Node* cond, Node* control = nullptr) { |
126 if (control == nullptr) control = start(); | 127 if (control == nullptr) control = start(); |
127 Node* branch = graph()->NewNode(common()->Branch(), cond, control); | 128 Node* branch = graph()->NewNode(common()->Branch(), cond, control); |
128 Node* if_true = graph()->NewNode(common()->IfTrue(), branch); | 129 Node* if_true = graph()->NewNode(common()->IfTrue(), branch); |
129 Node* if_false = graph()->NewNode(common()->IfFalse(), branch); | 130 Node* if_false = graph()->NewNode(common()->IfFalse(), branch); |
130 return {branch, if_true, if_false}; | 131 return {branch, if_true, if_false}; |
131 } | 132 } |
132 | 133 |
133 Counter NewCounter(While* w, int32_t b, int32_t k) { | 134 Counter NewCounter(While* w, int32_t b, int32_t k) { |
134 Node* base = Int32Constant(b); | 135 Node* base = Int32Constant(b); |
135 Node* inc = Int32Constant(k); | 136 Node* inc = Int32Constant(k); |
136 Node* phi = | 137 Node* phi = graph()->NewNode( |
137 graph()->NewNode(common()->Phi(kMachAnyTagged, 2), base, base, w->loop); | 138 common()->Phi(MachineRepresentation::kTagged, 2), base, base, w->loop); |
138 Node* add = graph()->NewNode(machine()->Int32Add(), phi, inc); | 139 Node* add = graph()->NewNode(machine()->Int32Add(), phi, inc); |
139 phi->ReplaceInput(1, add); | 140 phi->ReplaceInput(1, add); |
140 return {base, inc, phi, add}; | 141 return {base, inc, phi, add}; |
141 } | 142 } |
142 }; | 143 }; |
143 | 144 |
144 | 145 |
145 TEST_F(LoopPeelingTest, SimpleLoop) { | 146 TEST_F(LoopPeelingTest, SimpleLoop) { |
146 Node* p0 = Parameter(0); | 147 Node* p0 = Parameter(0); |
147 While w = NewWhile(p0); | 148 While w = NewWhile(p0); |
(...skipping 28 matching lines...) Expand all Loading... |
176 | 177 |
177 EXPECT_THAT(br1, IsBranch(p0, start())); | 178 EXPECT_THAT(br1, IsBranch(p0, start())); |
178 EXPECT_THAT(if_true1, IsIfTrue(br1)); | 179 EXPECT_THAT(if_true1, IsIfTrue(br1)); |
179 EXPECT_THAT(if_false1, IsIfFalse(br1)); | 180 EXPECT_THAT(if_false1, IsIfFalse(br1)); |
180 EXPECT_THAT(w.loop, IsLoop(if_true1, w.if_true)); | 181 EXPECT_THAT(w.loop, IsLoop(if_true1, w.if_true)); |
181 | 182 |
182 EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); | 183 EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); |
183 | 184 |
184 Capture<Node*> merge; | 185 Capture<Node*> merge; |
185 EXPECT_THAT( | 186 EXPECT_THAT( |
186 r, IsReturn(IsPhi(kMachAnyTagged, c.phi, c.base, | 187 r, IsReturn(IsPhi(MachineRepresentation::kTagged, c.phi, c.base, |
187 AllOf(CaptureEq(&merge), IsMerge(w.exit, if_false1))), | 188 AllOf(CaptureEq(&merge), IsMerge(w.exit, if_false1))), |
188 start(), CaptureEq(&merge))); | 189 start(), CaptureEq(&merge))); |
189 } | 190 } |
190 | 191 |
191 | 192 |
192 TEST_F(LoopPeelingTest, SimpleNestedLoopWithCounter_peel_outer) { | 193 TEST_F(LoopPeelingTest, SimpleNestedLoopWithCounter_peel_outer) { |
193 Node* p0 = Parameter(0); | 194 Node* p0 = Parameter(0); |
194 While outer = NewWhile(p0); | 195 While outer = NewWhile(p0); |
195 While inner = NewWhile(p0); | 196 While inner = NewWhile(p0); |
196 Nest(&inner, &outer); | 197 Nest(&inner, &outer); |
(...skipping 18 matching lines...) Expand all Loading... |
215 EXPECT_THAT(bri, IsBranch(p0, ExpectPeeled(inner.loop, peeled))); | 216 EXPECT_THAT(bri, IsBranch(p0, ExpectPeeled(inner.loop, peeled))); |
216 EXPECT_THAT(if_truei, IsIfTrue(bri)); | 217 EXPECT_THAT(if_truei, IsIfTrue(bri)); |
217 EXPECT_THAT(if_falsei, IsIfFalse(bri)); | 218 EXPECT_THAT(if_falsei, IsIfFalse(bri)); |
218 | 219 |
219 EXPECT_THAT(outer.loop, IsLoop(if_falsei, inner.exit)); | 220 EXPECT_THAT(outer.loop, IsLoop(if_falsei, inner.exit)); |
220 EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); | 221 EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); |
221 | 222 |
222 Capture<Node*> merge; | 223 Capture<Node*> merge; |
223 EXPECT_THAT( | 224 EXPECT_THAT( |
224 r, | 225 r, |
225 IsReturn(IsPhi(kMachAnyTagged, c.phi, c.base, | 226 IsReturn(IsPhi(MachineRepresentation::kTagged, c.phi, c.base, |
226 AllOf(CaptureEq(&merge), IsMerge(outer.exit, if_falseo))), | 227 AllOf(CaptureEq(&merge), IsMerge(outer.exit, if_falseo))), |
227 start(), CaptureEq(&merge))); | 228 start(), CaptureEq(&merge))); |
228 } | 229 } |
229 | 230 |
230 | 231 |
231 TEST_F(LoopPeelingTest, SimpleNestedLoopWithCounter_peel_inner) { | 232 TEST_F(LoopPeelingTest, SimpleNestedLoopWithCounter_peel_inner) { |
232 Node* p0 = Parameter(0); | 233 Node* p0 = Parameter(0); |
233 While outer = NewWhile(p0); | 234 While outer = NewWhile(p0); |
234 While inner = NewWhile(p0); | 235 While inner = NewWhile(p0); |
235 Nest(&inner, &outer); | 236 Nest(&inner, &outer); |
(...skipping 55 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
291 Node* if_falsei = ExpectPeeled(inner.exit, peeled); | 292 Node* if_falsei = ExpectPeeled(inner.exit, peeled); |
292 | 293 |
293 EXPECT_THAT(bri, IsBranch(p0, ExpectPeeled(inner.loop, peeled))); | 294 EXPECT_THAT(bri, IsBranch(p0, ExpectPeeled(inner.loop, peeled))); |
294 EXPECT_THAT(if_truei, IsIfTrue(bri)); | 295 EXPECT_THAT(if_truei, IsIfTrue(bri)); |
295 EXPECT_THAT(if_falsei, IsIfFalse(bri)); | 296 EXPECT_THAT(if_falsei, IsIfFalse(bri)); |
296 | 297 |
297 EXPECT_THAT(outer.loop, IsLoop(start(), IsMerge(inner.exit, if_falsei))); | 298 EXPECT_THAT(outer.loop, IsLoop(start(), IsMerge(inner.exit, if_falsei))); |
298 EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); | 299 EXPECT_THAT(peeled->map(c.add), IsInt32Add(c.base, c.inc)); |
299 | 300 |
300 Node* back = phi->InputAt(1); | 301 Node* back = phi->InputAt(1); |
301 EXPECT_THAT(back, IsPhi(kMachAnyTagged, c.phi, c.base, | 302 EXPECT_THAT(back, IsPhi(MachineRepresentation::kTagged, c.phi, c.base, |
302 IsMerge(inner.exit, if_falsei))); | 303 IsMerge(inner.exit, if_falsei))); |
303 | 304 |
304 EXPECT_THAT(phi, | 305 EXPECT_THAT(phi, IsPhi(MachineRepresentation::kTagged, IsInt32Constant(11), |
305 IsPhi(kMachAnyTagged, IsInt32Constant(11), back, outer.loop)); | 306 back, outer.loop)); |
306 | 307 |
307 EXPECT_THAT(r, IsReturn(phi, start(), outer.exit)); | 308 EXPECT_THAT(r, IsReturn(phi, start(), outer.exit)); |
308 } | 309 } |
309 | 310 |
310 | 311 |
311 TEST_F(LoopPeelingTest, TwoBackedgeLoop) { | 312 TEST_F(LoopPeelingTest, TwoBackedgeLoop) { |
312 Node* p0 = Parameter(0); | 313 Node* p0 = Parameter(0); |
313 Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); | 314 Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); |
314 Branch b1 = NewBranch(p0, loop); | 315 Branch b1 = NewBranch(p0, loop); |
315 Branch b2 = NewBranch(p0, b1.if_true); | 316 Branch b2 = NewBranch(p0, b1.if_true); |
(...skipping 24 matching lines...) Expand all Loading... |
340 EXPECT_THAT(loop, IsLoop(IsMerge(b2t, b2f), b2.if_true, b2.if_false)); | 341 EXPECT_THAT(loop, IsLoop(IsMerge(b2t, b2f), b2.if_true, b2.if_false)); |
341 EXPECT_THAT(r, IsReturn(p0, start(), IsMerge(b1.if_false, b1f))); | 342 EXPECT_THAT(r, IsReturn(p0, start(), IsMerge(b1.if_false, b1f))); |
342 } | 343 } |
343 | 344 |
344 | 345 |
345 TEST_F(LoopPeelingTest, TwoBackedgeLoopWithPhi) { | 346 TEST_F(LoopPeelingTest, TwoBackedgeLoopWithPhi) { |
346 Node* p0 = Parameter(0); | 347 Node* p0 = Parameter(0); |
347 Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); | 348 Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); |
348 Branch b1 = NewBranch(p0, loop); | 349 Branch b1 = NewBranch(p0, loop); |
349 Branch b2 = NewBranch(p0, b1.if_true); | 350 Branch b2 = NewBranch(p0, b1.if_true); |
350 Node* phi = | 351 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 3), |
351 graph()->NewNode(common()->Phi(kMachAnyTagged, 3), Int32Constant(0), | 352 Int32Constant(0), Int32Constant(1), |
352 Int32Constant(1), Int32Constant(2), loop); | 353 Int32Constant(2), loop); |
353 | 354 |
354 loop->ReplaceInput(1, b2.if_true); | 355 loop->ReplaceInput(1, b2.if_true); |
355 loop->ReplaceInput(2, b2.if_false); | 356 loop->ReplaceInput(2, b2.if_false); |
356 | 357 |
357 Node* r = InsertReturn(phi, start(), b1.if_false); | 358 Node* r = InsertReturn(phi, start(), b1.if_false); |
358 | 359 |
359 PeeledIteration* peeled = PeelOne(); | 360 PeeledIteration* peeled = PeelOne(); |
360 | 361 |
361 Node* b1b = ExpectPeeled(b1.branch, peeled); | 362 Node* b1b = ExpectPeeled(b1.branch, peeled); |
362 Node* b1t = ExpectPeeled(b1.if_true, peeled); | 363 Node* b1t = ExpectPeeled(b1.if_true, peeled); |
363 Node* b1f = ExpectPeeled(b1.if_false, peeled); | 364 Node* b1f = ExpectPeeled(b1.if_false, peeled); |
364 | 365 |
365 EXPECT_THAT(b1b, IsBranch(p0, start())); | 366 EXPECT_THAT(b1b, IsBranch(p0, start())); |
366 EXPECT_THAT(ExpectPeeled(b1.if_true, peeled), IsIfTrue(b1b)); | 367 EXPECT_THAT(ExpectPeeled(b1.if_true, peeled), IsIfTrue(b1b)); |
367 EXPECT_THAT(b1f, IsIfFalse(b1b)); | 368 EXPECT_THAT(b1f, IsIfFalse(b1b)); |
368 | 369 |
369 Node* b2b = ExpectPeeled(b2.branch, peeled); | 370 Node* b2b = ExpectPeeled(b2.branch, peeled); |
370 Node* b2t = ExpectPeeled(b2.if_true, peeled); | 371 Node* b2t = ExpectPeeled(b2.if_true, peeled); |
371 Node* b2f = ExpectPeeled(b2.if_false, peeled); | 372 Node* b2f = ExpectPeeled(b2.if_false, peeled); |
372 | 373 |
373 EXPECT_THAT(b2b, IsBranch(p0, b1t)); | 374 EXPECT_THAT(b2b, IsBranch(p0, b1t)); |
374 EXPECT_THAT(b2t, IsIfTrue(b2b)); | 375 EXPECT_THAT(b2t, IsIfTrue(b2b)); |
375 EXPECT_THAT(b2f, IsIfFalse(b2b)); | 376 EXPECT_THAT(b2f, IsIfFalse(b2b)); |
376 | 377 |
377 EXPECT_THAT(loop, IsLoop(IsMerge(b2t, b2f), b2.if_true, b2.if_false)); | 378 EXPECT_THAT(loop, IsLoop(IsMerge(b2t, b2f), b2.if_true, b2.if_false)); |
378 | 379 |
379 EXPECT_THAT( | 380 EXPECT_THAT(phi, |
380 phi, IsPhi(kMachAnyTagged, IsPhi(kMachAnyTagged, IsInt32Constant(1), | 381 IsPhi(MachineRepresentation::kTagged, |
381 IsInt32Constant(2), IsMerge(b2t, b2f)), | 382 IsPhi(MachineRepresentation::kTagged, IsInt32Constant(1), |
382 IsInt32Constant(1), IsInt32Constant(2), loop)); | 383 IsInt32Constant(2), IsMerge(b2t, b2f)), |
| 384 IsInt32Constant(1), IsInt32Constant(2), loop)); |
383 | 385 |
384 Capture<Node*> merge; | 386 Capture<Node*> merge; |
385 EXPECT_THAT( | 387 EXPECT_THAT( |
386 r, IsReturn(IsPhi(kMachAnyTagged, phi, IsInt32Constant(0), | 388 r, IsReturn(IsPhi(MachineRepresentation::kTagged, phi, IsInt32Constant(0), |
387 AllOf(CaptureEq(&merge), IsMerge(b1.if_false, b1f))), | 389 AllOf(CaptureEq(&merge), IsMerge(b1.if_false, b1f))), |
388 start(), CaptureEq(&merge))); | 390 start(), CaptureEq(&merge))); |
389 } | 391 } |
390 | 392 |
391 | 393 |
392 TEST_F(LoopPeelingTest, TwoBackedgeLoopWithCounter) { | 394 TEST_F(LoopPeelingTest, TwoBackedgeLoopWithCounter) { |
393 Node* p0 = Parameter(0); | 395 Node* p0 = Parameter(0); |
394 Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); | 396 Node* loop = graph()->NewNode(common()->Loop(3), start(), start(), start()); |
395 Branch b1 = NewBranch(p0, loop); | 397 Branch b1 = NewBranch(p0, loop); |
396 Branch b2 = NewBranch(p0, b1.if_true); | 398 Branch b2 = NewBranch(p0, b1.if_true); |
397 Node* phi = | 399 Node* phi = graph()->NewNode(common()->Phi(MachineRepresentation::kTagged, 3), |
398 graph()->NewNode(common()->Phi(kMachAnyTagged, 3), Int32Constant(0), | 400 Int32Constant(0), Int32Constant(1), |
399 Int32Constant(1), Int32Constant(2), loop); | 401 Int32Constant(2), loop); |
400 | 402 |
401 phi->ReplaceInput( | 403 phi->ReplaceInput( |
402 1, graph()->NewNode(machine()->Int32Add(), phi, Int32Constant(1))); | 404 1, graph()->NewNode(machine()->Int32Add(), phi, Int32Constant(1))); |
403 phi->ReplaceInput( | 405 phi->ReplaceInput( |
404 2, graph()->NewNode(machine()->Int32Add(), phi, Int32Constant(2))); | 406 2, graph()->NewNode(machine()->Int32Add(), phi, Int32Constant(2))); |
405 | 407 |
406 loop->ReplaceInput(1, b2.if_true); | 408 loop->ReplaceInput(1, b2.if_true); |
407 loop->ReplaceInput(2, b2.if_false); | 409 loop->ReplaceInput(2, b2.if_false); |
408 | 410 |
409 Node* r = InsertReturn(phi, start(), b1.if_false); | 411 Node* r = InsertReturn(phi, start(), b1.if_false); |
(...skipping 15 matching lines...) Expand all Loading... |
425 EXPECT_THAT(b2b, IsBranch(p0, b1t)); | 427 EXPECT_THAT(b2b, IsBranch(p0, b1t)); |
426 EXPECT_THAT(b2t, IsIfTrue(b2b)); | 428 EXPECT_THAT(b2t, IsIfTrue(b2b)); |
427 EXPECT_THAT(b2f, IsIfFalse(b2b)); | 429 EXPECT_THAT(b2f, IsIfFalse(b2b)); |
428 | 430 |
429 Capture<Node*> entry; | 431 Capture<Node*> entry; |
430 EXPECT_THAT(loop, IsLoop(AllOf(CaptureEq(&entry), IsMerge(b2t, b2f)), | 432 EXPECT_THAT(loop, IsLoop(AllOf(CaptureEq(&entry), IsMerge(b2t, b2f)), |
431 b2.if_true, b2.if_false)); | 433 b2.if_true, b2.if_false)); |
432 | 434 |
433 Node* eval = phi->InputAt(0); | 435 Node* eval = phi->InputAt(0); |
434 | 436 |
435 EXPECT_THAT(eval, IsPhi(kMachAnyTagged, | 437 EXPECT_THAT(eval, IsPhi(MachineRepresentation::kTagged, |
436 IsInt32Add(IsInt32Constant(0), IsInt32Constant(1)), | 438 IsInt32Add(IsInt32Constant(0), IsInt32Constant(1)), |
437 IsInt32Add(IsInt32Constant(0), IsInt32Constant(2)), | 439 IsInt32Add(IsInt32Constant(0), IsInt32Constant(2)), |
438 CaptureEq(&entry))); | 440 CaptureEq(&entry))); |
439 | 441 |
440 EXPECT_THAT(phi, | 442 EXPECT_THAT(phi, IsPhi(MachineRepresentation::kTagged, eval, |
441 IsPhi(kMachAnyTagged, eval, IsInt32Add(phi, IsInt32Constant(1)), | 443 IsInt32Add(phi, IsInt32Constant(1)), |
442 IsInt32Add(phi, IsInt32Constant(2)), loop)); | 444 IsInt32Add(phi, IsInt32Constant(2)), loop)); |
443 | 445 |
444 Capture<Node*> merge; | 446 Capture<Node*> merge; |
445 EXPECT_THAT( | 447 EXPECT_THAT( |
446 r, IsReturn(IsPhi(kMachAnyTagged, phi, IsInt32Constant(0), | 448 r, IsReturn(IsPhi(MachineRepresentation::kTagged, phi, IsInt32Constant(0), |
447 AllOf(CaptureEq(&merge), IsMerge(b1.if_false, b1f))), | 449 AllOf(CaptureEq(&merge), IsMerge(b1.if_false, b1f))), |
448 start(), CaptureEq(&merge))); | 450 start(), CaptureEq(&merge))); |
449 } | 451 } |
450 | 452 |
451 | 453 |
452 TEST_F(LoopPeelingTest, TwoExitLoop_nope) { | 454 TEST_F(LoopPeelingTest, TwoExitLoop_nope) { |
453 Node* p0 = Parameter(0); | 455 Node* p0 = Parameter(0); |
454 Node* loop = graph()->NewNode(common()->Loop(2), start(), start()); | 456 Node* loop = graph()->NewNode(common()->Loop(2), start(), start()); |
455 Branch b1 = NewBranch(p0, loop); | 457 Branch b1 = NewBranch(p0, loop); |
456 Branch b2 = NewBranch(p0, b1.if_true); | 458 Branch b2 = NewBranch(p0, b1.if_true); |
(...skipping 32 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
489 LoopTree* loop_tree = GetLoopTree(); | 491 LoopTree* loop_tree = GetLoopTree(); |
490 LoopTree::Loop* loop = loop_tree->outer_loops()[0]; | 492 LoopTree::Loop* loop = loop_tree->outer_loops()[0]; |
491 EXPECT_FALSE(LoopPeeler::CanPeel(loop_tree, loop)); | 493 EXPECT_FALSE(LoopPeeler::CanPeel(loop_tree, loop)); |
492 } | 494 } |
493 } | 495 } |
494 | 496 |
495 | 497 |
496 } // namespace compiler | 498 } // namespace compiler |
497 } // namespace internal | 499 } // namespace internal |
498 } // namespace v8 | 500 } // namespace v8 |
OLD | NEW |