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 (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 (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 (before) 105 ## CHECK: irreducible:true 106 107 ## CHECK-START: int IrreducibleLoop.dce(int) dead_code_elimination (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, LIrreducibleLoop; 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, LIrreducibleLoop; 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, LIrreducibleLoop; 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
