1# Copyright (C) 2015 The Android Open Source Project 2# 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# http://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14 15.class public LIrreducibleLoop; 16 17.super Ljava/lang/Object; 18 19# Back-edges in the ascii-art graphs are represented with dash '-'. 20 21# Test that we support a simple irreducible loop. 22# 23# entry 24# / \ 25# / \ 26# loop_entry \ 27# / \- \ 28# exit \- \ 29# other_loop_entry 30# 31## CHECK-START: int IrreducibleLoop.simpleLoop(int) dead_code_elimination$initial (before) 32## CHECK: irreducible:true 33.method public static simpleLoop(I)I 34 .registers 2 35 const/16 v0, 42 36 if-eq v1, v0, :other_loop_entry 37 :loop_entry 38 if-ne v1, v0, :exit 39 add-int v0, v0, v0 40 :other_loop_entry 41 add-int v0, v0, v0 42 goto :loop_entry 43 :exit 44 return v0 45.end method 46 47# Test that lse does not wrongly optimize loads in irreducible loops. At the 48# SSA level, since we create redundant phis for irreducible loop headers, lse 49# does not see the relation between the dex register and the phi. 50# 51# entry 52# p1 53# / \ 54# / \ 55# / \ 56# / \ 57# loop_pre_entry \ 58# set 42 in p1:myField \ 59# / \ 60# loop_entry \ 61# get p1.myField \ 62# / \- \ 63# exit \- \ 64# \- \ 65# other_loop_entry 66# set 30 in p1:myField 67# 68## CHECK-START: int IrreducibleLoop.lse(int, Main) dead_code_elimination$initial (after) 69## CHECK: irreducible:true 70# 71## CHECK-START: int IrreducibleLoop.lse(int, Main) load_store_elimination (after) 72## CHECK: InstanceFieldGet 73.method public static lse(ILMain;)I 74 .registers 4 75 const/16 v0, 42 76 const/16 v1, 30 77 if-eq p0, v0, :other_loop_pre_entry 78 goto: loop_pre_entry 79 :loop_pre_entry 80 iput v0, p1, LMain;->myField:I 81 :loop_entry 82 if-ne v1, v0, :exit 83 :other_loop_entry 84 iget v0, p1, LMain;->myField:I 85 if-eq v1, v0, :exit 86 goto :loop_entry 87 :exit 88 return v0 89 :other_loop_pre_entry 90 iput v1, p1, LMain;->myField:I 91 goto :other_loop_entry 92.end method 93 94# Check that dce does not apply for irreducible loops. 95# 96# entry 97# / \ 98# / \ 99# loop_entry \ 100# / \- \ 101# exit \- \ 102# other_loop_entry 103# 104## CHECK-START: int IrreducibleLoop.dce(int) dead_code_elimination$initial (before) 105## CHECK: irreducible:true 106 107## CHECK-START: int IrreducibleLoop.dce(int) dead_code_elimination$initial (after) 108## CHECK: irreducible:true 109.method public static dce(I)I 110 .registers 3 111 const/16 v0, 42 112 const/16 v1, 168 113 if-ne v0, v0, :other_loop_pre_entry 114 :loop_entry 115 if-ne v0, v0, :exit 116 add-int v0, v0, v0 117 :other_loop_entry 118 add-int v0, v0, v0 119 if-eq v0, v1, :exit 120 goto :loop_entry 121 :exit 122 return v0 123 :other_loop_pre_entry 124 add-int v0, v0, v0 125 goto :other_loop_entry 126.end method 127 128# Check that a dex register only used in the loop header remains live thanks 129# to the (redundant) Phi created at the loop header for it. 130# 131# entry 132# p0 133# / \ 134# / \ 135# / \ 136# loop_entry \ 137# i0 = phi(p0,i1) \ 138# / \- \ 139# exit \- \ 140# other_loop_entry 141# i1 = phi(p0, i0) 142# 143## CHECK-START: int IrreducibleLoop.liveness(int, int) liveness (after) 144## CHECK-DAG: <<Arg:i\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopPhiUse:\d+>>)} 145## CHECK-DAG: <<LoopPhi:i\d+>> Phi [<<Arg>>,<<PhiInLoop:i\d+>>] liveness:<<ArgLoopPhiUse>> ranges:{[<<ArgLoopPhiUse>>,<<PhiInLoopUse:\d+>>)} 146## CHECK-DAG: <<PhiInLoop>> Phi [<<Arg>>,<<LoopPhi>>] liveness:<<PhiInLoopUse>> ranges:{[<<PhiInLoopUse>>,<<BackEdgeLifetimeEnd:\d+>>)} 147## CHECK: Return liveness:<<ReturnLiveness:\d+>> 148## CHECK-EVAL: <<ReturnLiveness>> == <<BackEdgeLifetimeEnd>> + 2 149.method public static liveness(II)I 150 .registers 2 151 if-eq p0, p1, :other_loop_entry 152 :loop_entry 153 add-int p1, p1, p0 154 if-ne v0, p1, :exit 155 :other_loop_entry 156 add-int p1, p1, p1 157 goto :loop_entry 158 :exit 159 return p1 160.end method 161 162# Check that we don't GVN across irreducible loops: 163# "const-class 1" in loop_entry should not be GVN with 164# "const-class 1" in entry. 165# 166# entry 167# const-class 1 168# / \ 169# / \ 170# loop_entry \ 171# const-class 1 \ 172# / \- \ 173# exit \- \ 174# other_loop_entry 175# const-class 2 176# 177## CHECK-START: java.lang.Class IrreducibleLoop.gvn() GVN (before) 178## CHECK: LoadClass 179## CHECK: LoadClass 180## CHECK: LoadClass 181## CHECK-NOT: LoadClass 182 183## CHECK-START: java.lang.Class IrreducibleLoop.gvn() GVN (after) 184## CHECK: LoadClass 185## CHECK: LoadClass 186## CHECK: LoadClass 187## CHECK-NOT: LoadClass 188 189.method public static gvn()Ljava/lang/Class; 190 .registers 3 191 const/4 v2, 0 192 const-class v0, LMain; 193 if-ne v0, v2, :other_loop_entry 194 :loop_entry 195 const-class v0, LMain; 196 if-ne v0, v2, :exit 197 :other_loop_entry 198 const-class v1, LOther; # LoadClass that can throw 199 goto :loop_entry 200 :exit 201 return-object v0 202.end method 203 204# Check that we don't LICM across irreducible loops: 205# "add" in loop_entry should not be LICMed. 206# 207# entry 208# / \ 209# / \ 210# loop_entry \ 211# add \ 212# / \- \ 213# exit \- \ 214# other_loop_entry 215# 216## CHECK-START: int IrreducibleLoop.licm1(int) licm (after) 217## CHECK: Add irreducible:true 218.method public static licm1(I)I 219 .registers 3 220 const/4 v0, 0 221 if-ne p0, v0, :other_loop_entry 222 :loop_entry 223 add-int v0, p0, p0 224 if-ne v0, p0, :exit 225 :other_loop_entry 226 sub-int v1, p0, p0 227 goto :loop_entry 228 :exit 229 sub-int v0, v0, p0 230 return v0 231.end method 232 233# Check that we don't LICM across irreducible loops: 234# "const-class" in loop_entry should not be LICMed. 235# 236# entry 237# / \ 238# / \ 239# loop_entry \ 240# const-class \ 241# / \- \ 242# exit \- \ 243# other_loop_entry 244# 245## CHECK-START: int IrreducibleLoop.licm2(int) licm (after) 246## CHECK: LoadClass irreducible:true 247.method public static licm2(I)I 248 .registers 3 249 const/4 v0, 0 250 if-ne p0, v0, :other_loop_entry 251 :loop_entry 252 const-class v1, LOther; # LoadClass that can throw 253 if-ne v0, p0, :exit 254 :other_loop_entry 255 sub-int v1, p0, p0 256 goto :loop_entry 257 :exit 258 sub-int v0, v0, p0 259 return v0 260.end method 261 262# Check that we don't LICM in a natural loop that contains an irreducible loop: 263# "const-class" should not be LICMed. 264# 265# entry 266# | 267# loop_entry 268# const-class ------------------- 269# / \ - 270# / \ - 271# exit loop_body - 272# / \ - 273# / \ - 274# irreducible_loop_entry \ - 275# - \ \ - 276# - \ \ - 277# - irreducible_loop_other_entry 278# - | 279# - | 280# ------ irreducible_loop_back_edge 281# 282## CHECK-START: int IrreducibleLoop.licm3(int, int, int) licm (after) 283## CHECK: LoadClass loop:<<OuterLoop:B\d+>> irreducible:false 284## CHECK: Goto outer_loop:<<OuterLoop>> irreducible:true 285.method public static licm3(III)I 286 .registers 4 287 :loop_entry 288 const-class v0, LOther; # LoadClass that can throw 289 if-ne p1, p2, :exit 290 goto :loop_body 291 292 :loop_body 293 if-eq p0, p1, :irreducible_loop_entry 294 goto :irreducible_loop_other_entry 295 296 :irreducible_loop_entry 297 goto :irreducible_loop_other_entry 298 299 :irreducible_loop_other_entry 300 if-eq p0, p2, :loop_entry 301 goto :irreducible_loop_back_edge 302 303 :irreducible_loop_back_edge 304 goto :irreducible_loop_entry 305 :exit 306 return p0 307.end method 308 309# Check a loop within an irreducible loop 310# 311# entry 312# / \ 313# / \ 314# irreducible_loop_entry \ 315# / - \ irreducible_loop_pre_other_entry 316# exit - \ / 317# - irreducible_loop_body 318# - | 319# - | 320# - loop_within_header 321# - / \- 322# - / \- 323# irreducible_loop_back_edge loop_within_back_edge 324# 325## CHECK-START: void IrreducibleLoop.analyze1(int) builder (after) 326## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true 327## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:false 328.method public static analyze1(I)V 329 .registers 1 330 if-eq p0, p0, :irreducible_loop_entry 331 goto :irreducible_loop_pre_other_entry 332 333 :irreducible_loop_entry 334 if-eq p0, p0, :exit 335 goto :irreducible_loop_body 336 337 :irreducible_loop_body 338 :loop_within_header 339 if-eq p0, p0, :irreducible_loop_back_edge 340 goto :loop_within_back_edge 341 342 :loop_within_back_edge 343 goto :loop_within_header 344 345 :irreducible_loop_back_edge 346 goto :irreducible_loop_entry 347 348 :irreducible_loop_pre_other_entry 349 goto :irreducible_loop_body 350 351 :exit 352 return-void 353.end method 354 355# Check than a loop before an irreducible loop is not part of the 356# irreducible loop. 357# 358# entry 359# | 360# | 361# loop_header 362# / \- 363# / \- 364# irreducible_loop_pre_entry loop_body 365# / \ 366# / \ 367# irreducible_loop_entry \ 368# / \- irreducible_loop_other_pre_entry 369# / \- / 370# exit \- / 371# irreducible_loop_body 372# 373## CHECK-START: void IrreducibleLoop.analyze2(int) builder (after) 374## CHECK-DAG: Goto outer_loop:none irreducible:false 375## CHECK-DAG: Goto outer_loop:none irreducible:true 376.method public static analyze2(I)V 377 .registers 1 378 :loop_header 379 if-eq p0, p0, :irreducible_loop_pre_entry 380 goto :loop_body 381 :loop_body 382 goto :loop_header 383 384 :irreducible_loop_pre_entry 385 if-eq p0, p0, :irreducible_loop_other_pre_entry 386 goto :irreducible_loop_entry 387 388 :irreducible_loop_entry 389 if-eq p0, p0, :exit 390 goto :irreducible_loop_body 391 392 :irreducible_loop_body 393 goto :irreducible_loop_entry 394 395 :irreducible_loop_other_pre_entry 396 goto :irreducible_loop_body 397 398 :exit 399 return-void 400.end method 401 402# Check two irreducible loops, one within another. 403# 404# entry 405# / \ 406# / \ 407# loop1_header loop2_header 408# - | / - 409# - | / - 410# - | / - 411# - | / - 412# - loop2_body - 413# - / \ - 414# - / \ - 415# loop1_body loop2_back_edge 416# | 417# | 418# exit 419# 420## CHECK-START: void IrreducibleLoop.analyze3(int) builder (after) 421## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true 422## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:true 423.method public static analyze3(I)V 424 .registers 1 425 if-eq p0, p0, :loop2_header 426 goto :loop1_header 427 428 :loop1_header 429 goto :loop2_body 430 431 :loop2_header 432 goto :loop2_body 433 434 :loop2_body 435 if-eq p0, p0, :loop2_back_edge 436 goto :loop1_body 437 438 :loop2_back_edge 439 goto :loop2_header 440 441 :loop1_body 442 if-eq p0, p0, :exit 443 goto :loop1_header 444 445 :exit 446 return-void 447.end method 448 449# Check two irreducible loops, one within another. Almost identical 450# to analyze3 except the branches of the first 'if' are swapped, to 451# ensure the order at which we find the back edges does not matter. 452# 453# entry 454# / \ 455# / \ 456# loop1_header loop2_header 457# - | / - 458# - | / - 459# - | / - 460# - | / - 461# - loop2_body - 462# - / \ - 463# - / \ - 464# loop1_body loop2_back_edge 465# | 466# | 467# exit 468# 469## CHECK-START: void IrreducibleLoop.analyze4(int) builder (after) 470## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true 471## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:true 472.method public static analyze4(I)V 473 .registers 1 474 if-eq p0, p0, :loop1_header 475 goto :loop2_header 476 477 :loop1_header 478 goto :loop2_body 479 480 :loop2_header 481 goto :loop2_body 482 483 :loop2_body 484 if-eq p0, p0, :loop2_back_edge 485 goto :loop1_body 486 487 :loop2_back_edge 488 goto :loop2_header 489 490 :loop1_body 491 if-eq p0, p0, :exit 492 goto :loop1_header 493 494 :exit 495 return-void 496.end method 497 498# Check two irreducible loops, one within another. Almost identical 499# to analyze3 and analyze4, except that the inner loop exits from the 500# back edge, and not the body. 501# 502# entry 503# / \ 504# / \ 505# loop1_header loop2_header 506# - \ / - 507# - \ / - 508# - \ / - 509# - \ / - 510# - loop2_body - 511# - | - 512# - | - 513# - loop2_back_edge ------ 514# - | 515# - | 516# ----- loop1_body 517# | 518# | 519# exit 520# 521## CHECK-START: void IrreducibleLoop.analyze5(int) builder (after) 522## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true 523## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:true 524.method public static analyze5(I)V 525 .registers 1 526 if-eq p0, p0, :loop1_header 527 goto :loop2_header 528 529 :loop1_header 530 goto :loop2_body 531 532 :loop2_header 533 goto :loop2_body 534 535 :loop2_body 536 goto :loop2_back_edge 537 538 :loop2_back_edge 539 if-eq p0, p0, :loop2_header 540 goto :loop1_body 541 542 :loop1_body 543 if-eq p0, p0, :exit 544 goto :loop1_header 545 546 :exit 547 return-void 548.end method 549 550## CHECK-START: int IrreducibleLoop.testDoNotInlineIrreducible(int) inliner (before) 551## CHECK: InvokeStaticOrDirect method_name:IrreducibleLoop.doNotInlineIrreducible 552# 553## CHECK-START: int IrreducibleLoop.testDoNotInlineIrreducible(int) inliner (after) 554## CHECK: InvokeStaticOrDirect method_name:IrreducibleLoop.doNotInlineIrreducible 555.method public static testDoNotInlineIrreducible(I)I 556 .registers 2 557 invoke-static {p0}, LIrreducibleLoop;->doNotInlineIrreducible(I)I 558 move-result v0 559 return v0 560.end method 561 562# Check that doNotInlineIrreducible has a simple irreducible loop 563# 564# entry 565# / \ 566# / \ 567# loop_entry \ 568# / \- \ 569# try_start\- \ 570# other_loop_entry 571# 572## CHECK-START: int IrreducibleLoop.doNotInlineIrreducible(int) register (after) 573## CHECK: irreducible:true 574# 575# Check that we didn't optimized away the try. 576## CHECK-START: int IrreducibleLoop.doNotInlineIrreducible(int) register (after) 577## CHECK: TryBoundary kind:exit 578.method public static doNotInlineIrreducible(I)I 579 .registers 3 580 const/16 v0, 42 581 const/16 v1, 21 582 # Irreducible loop 583 if-eq v1, v0, :other_loop_entry 584 :loop_entry 585 if-ne v1, v0, :try_start 586 add-int v0, v0, v0 587 :other_loop_entry 588 add-int v0, v0, v0 589 goto :loop_entry 590 591 :try_start 592 # We make this division to make sure the try doesn't get optimized out 593 div-int v0, v0, p0 594 return v0 595 :try_end 596 .catchall {:try_start .. :try_end} :catch_all 597 598 :catch_all 599 # This is only reachable if the parameter is 0 600 const/4 v0, -0x1 601 return v0 602.end method 603