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) 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(I)I 150 .registers 2 151 const/16 v0, 42 152 if-eq p0, v0, :other_loop_entry 153 :loop_entry 154 add-int v0, v0, p0 155 if-ne v1, v0, :exit 156 :other_loop_entry 157 add-int v0, v0, v0 158 goto :loop_entry 159 :exit 160 return v0 161.end method 162 163# Check that we don't GVN across irreducible loops: 164# "const-class 1" in loop_entry should not be GVN with 165# "const-class 1" in entry. 166# 167# entry 168# const-class 1 169# / \ 170# / \ 171# loop_entry \ 172# const-class 1 \ 173# / \- \ 174# exit \- \ 175# other_loop_entry 176# const-class 2 177# 178## CHECK-START: java.lang.Class IrreducibleLoop.gvn() GVN (before) 179## CHECK: LoadClass 180## CHECK: LoadClass 181## CHECK: LoadClass 182## CHECK-NOT: LoadClass 183 184## CHECK-START: java.lang.Class IrreducibleLoop.gvn() GVN (after) 185## CHECK: LoadClass 186## CHECK: LoadClass 187## CHECK: LoadClass 188## CHECK-NOT: LoadClass 189 190.method public static gvn()Ljava/lang/Class; 191 .registers 3 192 const/4 v2, 0 193 const-class v0, LMain; 194 if-ne v0, v2, :other_loop_entry 195 :loop_entry 196 const-class v0, LMain; 197 if-ne v0, v2, :exit 198 :other_loop_entry 199 const-class v1, LOther; # LoadClass that can throw 200 goto :loop_entry 201 :exit 202 return-object v0 203.end method 204 205# Check that we don't LICM across irreducible loops: 206# "add" in loop_entry should not be LICMed. 207# 208# entry 209# / \ 210# / \ 211# loop_entry \ 212# add \ 213# / \- \ 214# exit \- \ 215# other_loop_entry 216# 217## CHECK-START: int IrreducibleLoop.licm1(int) licm (after) 218## CHECK: Add irreducible:true 219.method public static licm1(I)I 220 .registers 3 221 const/4 v0, 0 222 if-ne p0, v0, :other_loop_entry 223 :loop_entry 224 add-int v0, p0, p0 225 if-ne v0, p0, :exit 226 :other_loop_entry 227 sub-int v1, p0, p0 228 goto :loop_entry 229 :exit 230 sub-int v0, v0, p0 231 return v0 232.end method 233 234# Check that we don't LICM across irreducible loops: 235# "const-class" in loop_entry should not be LICMed. 236# 237# entry 238# / \ 239# / \ 240# loop_entry \ 241# const-class \ 242# / \- \ 243# exit \- \ 244# other_loop_entry 245# 246## CHECK-START: int IrreducibleLoop.licm2(int) licm (after) 247## CHECK: LoadClass irreducible:true 248.method public static licm2(I)I 249 .registers 3 250 const/4 v0, 0 251 if-ne p0, v0, :other_loop_entry 252 :loop_entry 253 const-class v1, LOther; # LoadClass that can throw 254 if-ne v0, p0, :exit 255 :other_loop_entry 256 sub-int v1, p0, p0 257 goto :loop_entry 258 :exit 259 sub-int v0, v0, p0 260 return v0 261.end method 262 263# Check that we don't LICM in a natural loop that contains an irreducible loop: 264# "const-class" should not be LICMed. 265# 266# entry 267# | 268# loop_entry 269# const-class ------------------- 270# / \ - 271# / \ - 272# exit loop_body - 273# / \ - 274# / \ - 275# irreducible_loop_entry \ - 276# - \ \ - 277# - \ \ - 278# - irreducible_loop_other_entry 279# - | 280# - | 281# ------ irreducible_loop_back_edge 282# 283## CHECK-START: int IrreducibleLoop.licm3(int, int, int) licm (after) 284## CHECK: LoadClass loop:<<OuterLoop:B\d+>> irreducible:false 285## CHECK: Goto outer_loop:<<OuterLoop>> irreducible:true 286.method public static licm3(III)I 287 .registers 4 288 :loop_entry 289 const-class v0, LOther; # LoadClass that can throw 290 if-ne p1, p2, :exit 291 goto :loop_body 292 293 :loop_body 294 if-eq p0, p1, :irreducible_loop_entry 295 goto :irreducible_loop_other_entry 296 297 :irreducible_loop_entry 298 goto :irreducible_loop_other_entry 299 300 :irreducible_loop_other_entry 301 if-eq p0, p2, :loop_entry 302 goto :irreducible_loop_back_edge 303 304 :irreducible_loop_back_edge 305 goto :irreducible_loop_entry 306 :exit 307 return p0 308.end method 309 310# Check a loop within an irreducible loop 311# 312# entry 313# / \ 314# / \ 315# irreducible_loop_entry \ 316# / - \ irreducible_loop_pre_other_entry 317# exit - \ / 318# - irreducible_loop_body 319# - | 320# - | 321# - loop_within_header 322# - / \- 323# - / \- 324# irreducible_loop_back_edge loop_within_back_edge 325# 326## CHECK-START: void IrreducibleLoop.analyze1(int) builder (after) 327## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true 328## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:false 329.method public static analyze1(I)V 330 .registers 1 331 if-eq p0, p0, :irreducible_loop_entry 332 goto :irreducible_loop_pre_other_entry 333 334 :irreducible_loop_entry 335 if-eq p0, p0, :exit 336 goto :irreducible_loop_body 337 338 :irreducible_loop_body 339 :loop_within_header 340 if-eq p0, p0, :irreducible_loop_back_edge 341 goto :loop_within_back_edge 342 343 :loop_within_back_edge 344 goto :loop_within_header 345 346 :irreducible_loop_back_edge 347 goto :irreducible_loop_entry 348 349 :irreducible_loop_pre_other_entry 350 goto :irreducible_loop_body 351 352 :exit 353 return-void 354.end method 355 356# Check than a loop before an irreducible loop is not part of the 357# irreducible loop. 358# 359# entry 360# | 361# | 362# loop_header 363# / \- 364# / \- 365# irreducible_loop_pre_entry loop_body 366# / \ 367# / \ 368# irreducible_loop_entry \ 369# / \- irreducible_loop_other_pre_entry 370# / \- / 371# exit \- / 372# irreducible_loop_body 373# 374## CHECK-START: void IrreducibleLoop.analyze2(int) builder (after) 375## CHECK-DAG: Goto outer_loop:none irreducible:false 376## CHECK-DAG: Goto outer_loop:none irreducible:true 377.method public static analyze2(I)V 378 .registers 1 379 :loop_header 380 if-eq p0, p0, :irreducible_loop_pre_entry 381 goto :loop_body 382 :loop_body 383 goto :loop_header 384 385 :irreducible_loop_pre_entry 386 if-eq p0, p0, :irreducible_loop_other_pre_entry 387 goto :irreducible_loop_entry 388 389 :irreducible_loop_entry 390 if-eq p0, p0, :exit 391 goto :irreducible_loop_body 392 393 :irreducible_loop_body 394 goto :irreducible_loop_entry 395 396 :irreducible_loop_other_pre_entry 397 goto :irreducible_loop_body 398 399 :exit 400 return-void 401.end method 402 403# Check two irreducible loops, one within another. 404# 405# entry 406# / \ 407# / \ 408# loop1_header loop2_header 409# - | / - 410# - | / - 411# - | / - 412# - | / - 413# - loop2_body - 414# - / \ - 415# - / \ - 416# loop1_body loop2_back_edge 417# | 418# | 419# exit 420# 421## CHECK-START: void IrreducibleLoop.analyze3(int) builder (after) 422## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true 423## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:true 424.method public static analyze3(I)V 425 .registers 1 426 if-eq p0, p0, :loop2_header 427 goto :loop1_header 428 429 :loop1_header 430 goto :loop2_body 431 432 :loop2_header 433 goto :loop2_body 434 435 :loop2_body 436 if-eq p0, p0, :loop2_back_edge 437 goto :loop1_body 438 439 :loop2_back_edge 440 goto :loop2_header 441 442 :loop1_body 443 if-eq p0, p0, :exit 444 goto :loop1_header 445 446 :exit 447 return-void 448.end method 449 450# Check two irreducible loops, one within another. Almost identical 451# to analyze3 except the branches of the first 'if' are swapped, to 452# ensure the order at which we find the back edges does not matter. 453# 454# entry 455# / \ 456# / \ 457# loop1_header loop2_header 458# - | / - 459# - | / - 460# - | / - 461# - | / - 462# - loop2_body - 463# - / \ - 464# - / \ - 465# loop1_body loop2_back_edge 466# | 467# | 468# exit 469# 470## CHECK-START: void IrreducibleLoop.analyze4(int) builder (after) 471## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true 472## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:true 473.method public static analyze4(I)V 474 .registers 1 475 if-eq p0, p0, :loop1_header 476 goto :loop2_header 477 478 :loop1_header 479 goto :loop2_body 480 481 :loop2_header 482 goto :loop2_body 483 484 :loop2_body 485 if-eq p0, p0, :loop2_back_edge 486 goto :loop1_body 487 488 :loop2_back_edge 489 goto :loop2_header 490 491 :loop1_body 492 if-eq p0, p0, :exit 493 goto :loop1_header 494 495 :exit 496 return-void 497.end method 498 499# Check two irreducible loops, one within another. Almost identical 500# to analyze3 and analyze4, except that the inner loop exits from the 501# back edge, and not the body. 502# 503# entry 504# / \ 505# / \ 506# loop1_header loop2_header 507# - \ / - 508# - \ / - 509# - \ / - 510# - \ / - 511# - loop2_body - 512# - | - 513# - | - 514# - loop2_back_edge ------ 515# - | 516# - | 517# ----- loop1_body 518# | 519# | 520# exit 521# 522## CHECK-START: void IrreducibleLoop.analyze5(int) builder (after) 523## CHECK-DAG: Goto loop:<<OuterLoop:B\d+>> outer_loop:none irreducible:true 524## CHECK-DAG: Goto outer_loop:<<OuterLoop>> irreducible:true 525.method public static analyze5(I)V 526 .registers 1 527 if-eq p0, p0, :loop1_header 528 goto :loop2_header 529 530 :loop1_header 531 goto :loop2_body 532 533 :loop2_header 534 goto :loop2_body 535 536 :loop2_body 537 goto :loop2_back_edge 538 539 :loop2_back_edge 540 if-eq p0, p0, :loop2_header 541 goto :loop1_body 542 543 :loop1_body 544 if-eq p0, p0, :exit 545 goto :loop1_header 546 547 :exit 548 return-void 549.end method 550