# Copyright (C) 2015 The Android Open Source Project # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # http://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. .class public LIrreducibleLoop; .super Ljava/lang/Object; # Back-edges in the ascii-art graphs are represented with dash '-'. # Test that we support a simple irreducible loop. # # entry # / \ # / \ # loop_entry \ # / \- \ # exit \- \ # other_loop_entry # ## CHECK-START: int IrreducibleLoop.simpleLoop(int) dead_code_elimination$initial (before) ## CHECK: irreducible:true .method public static simpleLoop(I)I .registers 2 const/16 v0, 42 if-eq v1, v0, :other_loop_entry :loop_entry if-ne v1, v0, :exit add-int v0, v0, v0 :other_loop_entry add-int v0, v0, v0 goto :loop_entry :exit return v0 .end method # Test that lse does not wrongly optimize loads in irreducible loops. At the # SSA level, since we create redundant phis for irreducible loop headers, lse # does not see the relation between the dex register and the phi. # # entry # p1 # / \ # / \ # / \ # / \ # loop_pre_entry \ # set 42 in p1:myField \ # / \ # loop_entry \ # get p1.myField \ # / \- \ # exit \- \ # \- \ # other_loop_entry # set 30 in p1:myField # ## CHECK-START: int IrreducibleLoop.lse(int, Main) dead_code_elimination$initial (after) ## CHECK: irreducible:true # ## CHECK-START: int IrreducibleLoop.lse(int, Main) load_store_elimination (after) ## CHECK: InstanceFieldGet .method public static lse(ILMain;)I .registers 4 const/16 v0, 42 const/16 v1, 30 if-eq p0, v0, :other_loop_pre_entry goto: loop_pre_entry :loop_pre_entry iput v0, p1, LMain;->myField:I :loop_entry if-ne v1, v0, :exit :other_loop_entry iget v0, p1, LMain;->myField:I if-eq v1, v0, :exit goto :loop_entry :exit return v0 :other_loop_pre_entry iput v1, p1, LMain;->myField:I goto :other_loop_entry .end method # Check that dce does not apply for irreducible loops. # # entry # / \ # / \ # loop_entry \ # / \- \ # exit \- \ # other_loop_entry # ## CHECK-START: int IrreducibleLoop.dce(int) dead_code_elimination$initial (before) ## CHECK: irreducible:true ## CHECK-START: int IrreducibleLoop.dce(int) dead_code_elimination$initial (after) ## CHECK: irreducible:true .method public static dce(I)I .registers 3 const/16 v0, 42 const/16 v1, 168 if-ne v0, v0, :other_loop_pre_entry :loop_entry if-ne v0, v0, :exit add-int v0, v0, v0 :other_loop_entry add-int v0, v0, v0 if-eq v0, v1, :exit goto :loop_entry :exit return v0 :other_loop_pre_entry add-int v0, v0, v0 goto :other_loop_entry .end method # Check that a dex register only used in the loop header remains live thanks # to the (redundant) Phi created at the loop header for it. # # entry # p0 # / \ # / \ # / \ # loop_entry \ # i0 = phi(p0,i1) \ # / \- \ # exit \- \ # other_loop_entry # i1 = phi(p0, i0) # ## CHECK-START: int IrreducibleLoop.liveness(int) liveness (after) ## CHECK-DAG: <> ParameterValue liveness:<> ranges:{[<>,<>)} ## CHECK-DAG: <> Phi [<>,<>] liveness:<> ranges:{[<>,<>)} ## CHECK-DAG: <> Phi [<>,<>] liveness:<> ranges:{[<>,<>)} ## CHECK: Return liveness:<> ## CHECK-EVAL: <> == <> + 2 .method public static liveness(I)I .registers 2 const/16 v0, 42 if-eq p0, v0, :other_loop_entry :loop_entry add-int v0, v0, p0 if-ne v1, v0, :exit :other_loop_entry add-int v0, v0, v0 goto :loop_entry :exit return v0 .end method # Check that we don't GVN across irreducible loops: # "const-class 1" in loop_entry should not be GVN with # "const-class 1" in entry. # # entry # const-class 1 # / \ # / \ # loop_entry \ # const-class 1 \ # / \- \ # exit \- \ # other_loop_entry # const-class 2 # ## CHECK-START: java.lang.Class IrreducibleLoop.gvn() GVN (before) ## CHECK: LoadClass ## CHECK: LoadClass ## CHECK: LoadClass ## CHECK-NOT: LoadClass ## CHECK-START: java.lang.Class IrreducibleLoop.gvn() GVN (after) ## CHECK: LoadClass ## CHECK: LoadClass ## CHECK: LoadClass ## CHECK-NOT: LoadClass .method public static gvn()Ljava/lang/Class; .registers 3 const/4 v2, 0 const-class v0, LMain; if-ne v0, v2, :other_loop_entry :loop_entry const-class v0, LMain; if-ne v0, v2, :exit :other_loop_entry const-class v1, LOther; # LoadClass that can throw goto :loop_entry :exit return-object v0 .end method # Check that we don't LICM across irreducible loops: # "add" in loop_entry should not be LICMed. # # entry # / \ # / \ # loop_entry \ # add \ # / \- \ # exit \- \ # other_loop_entry # ## CHECK-START: int IrreducibleLoop.licm1(int) licm (after) ## CHECK: Add irreducible:true .method public static licm1(I)I .registers 3 const/4 v0, 0 if-ne p0, v0, :other_loop_entry :loop_entry add-int v0, p0, p0 if-ne v0, p0, :exit :other_loop_entry sub-int v1, p0, p0 goto :loop_entry :exit sub-int v0, v0, p0 return v0 .end method # Check that we don't LICM across irreducible loops: # "const-class" in loop_entry should not be LICMed. # # entry # / \ # / \ # loop_entry \ # const-class \ # / \- \ # exit \- \ # other_loop_entry # ## CHECK-START: int IrreducibleLoop.licm2(int) licm (after) ## CHECK: LoadClass irreducible:true .method public static licm2(I)I .registers 3 const/4 v0, 0 if-ne p0, v0, :other_loop_entry :loop_entry const-class v1, LOther; # LoadClass that can throw if-ne v0, p0, :exit :other_loop_entry sub-int v1, p0, p0 goto :loop_entry :exit sub-int v0, v0, p0 return v0 .end method # Check that we don't LICM in a natural loop that contains an irreducible loop: # "const-class" should not be LICMed. # # entry # | # loop_entry # const-class ------------------- # / \ - # / \ - # exit loop_body - # / \ - # / \ - # irreducible_loop_entry \ - # - \ \ - # - \ \ - # - irreducible_loop_other_entry # - | # - | # ------ irreducible_loop_back_edge # ## CHECK-START: int IrreducibleLoop.licm3(int, int, int) licm (after) ## CHECK: LoadClass loop:<> irreducible:false ## CHECK: Goto outer_loop:<> irreducible:true .method public static licm3(III)I .registers 4 :loop_entry const-class v0, LOther; # LoadClass that can throw if-ne p1, p2, :exit goto :loop_body :loop_body if-eq p0, p1, :irreducible_loop_entry goto :irreducible_loop_other_entry :irreducible_loop_entry goto :irreducible_loop_other_entry :irreducible_loop_other_entry if-eq p0, p2, :loop_entry goto :irreducible_loop_back_edge :irreducible_loop_back_edge goto :irreducible_loop_entry :exit return p0 .end method # Check a loop within an irreducible loop # # entry # / \ # / \ # irreducible_loop_entry \ # / - \ irreducible_loop_pre_other_entry # exit - \ / # - irreducible_loop_body # - | # - | # - loop_within_header # - / \- # - / \- # irreducible_loop_back_edge loop_within_back_edge # ## CHECK-START: void IrreducibleLoop.analyze1(int) builder (after) ## CHECK-DAG: Goto loop:<> outer_loop:none irreducible:true ## CHECK-DAG: Goto outer_loop:<> irreducible:false .method public static analyze1(I)V .registers 1 if-eq p0, p0, :irreducible_loop_entry goto :irreducible_loop_pre_other_entry :irreducible_loop_entry if-eq p0, p0, :exit goto :irreducible_loop_body :irreducible_loop_body :loop_within_header if-eq p0, p0, :irreducible_loop_back_edge goto :loop_within_back_edge :loop_within_back_edge goto :loop_within_header :irreducible_loop_back_edge goto :irreducible_loop_entry :irreducible_loop_pre_other_entry goto :irreducible_loop_body :exit return-void .end method # Check than a loop before an irreducible loop is not part of the # irreducible loop. # # entry # | # | # loop_header # / \- # / \- # irreducible_loop_pre_entry loop_body # / \ # / \ # irreducible_loop_entry \ # / \- irreducible_loop_other_pre_entry # / \- / # exit \- / # irreducible_loop_body # ## CHECK-START: void IrreducibleLoop.analyze2(int) builder (after) ## CHECK-DAG: Goto outer_loop:none irreducible:false ## CHECK-DAG: Goto outer_loop:none irreducible:true .method public static analyze2(I)V .registers 1 :loop_header if-eq p0, p0, :irreducible_loop_pre_entry goto :loop_body :loop_body goto :loop_header :irreducible_loop_pre_entry if-eq p0, p0, :irreducible_loop_other_pre_entry goto :irreducible_loop_entry :irreducible_loop_entry if-eq p0, p0, :exit goto :irreducible_loop_body :irreducible_loop_body goto :irreducible_loop_entry :irreducible_loop_other_pre_entry goto :irreducible_loop_body :exit return-void .end method # Check two irreducible loops, one within another. # # entry # / \ # / \ # loop1_header loop2_header # - | / - # - | / - # - | / - # - | / - # - loop2_body - # - / \ - # - / \ - # loop1_body loop2_back_edge # | # | # exit # ## CHECK-START: void IrreducibleLoop.analyze3(int) builder (after) ## CHECK-DAG: Goto loop:<> outer_loop:none irreducible:true ## CHECK-DAG: Goto outer_loop:<> irreducible:true .method public static analyze3(I)V .registers 1 if-eq p0, p0, :loop2_header goto :loop1_header :loop1_header goto :loop2_body :loop2_header goto :loop2_body :loop2_body if-eq p0, p0, :loop2_back_edge goto :loop1_body :loop2_back_edge goto :loop2_header :loop1_body if-eq p0, p0, :exit goto :loop1_header :exit return-void .end method # Check two irreducible loops, one within another. Almost identical # to analyze3 except the branches of the first 'if' are swapped, to # ensure the order at which we find the back edges does not matter. # # entry # / \ # / \ # loop1_header loop2_header # - | / - # - | / - # - | / - # - | / - # - loop2_body - # - / \ - # - / \ - # loop1_body loop2_back_edge # | # | # exit # ## CHECK-START: void IrreducibleLoop.analyze4(int) builder (after) ## CHECK-DAG: Goto loop:<> outer_loop:none irreducible:true ## CHECK-DAG: Goto outer_loop:<> irreducible:true .method public static analyze4(I)V .registers 1 if-eq p0, p0, :loop1_header goto :loop2_header :loop1_header goto :loop2_body :loop2_header goto :loop2_body :loop2_body if-eq p0, p0, :loop2_back_edge goto :loop1_body :loop2_back_edge goto :loop2_header :loop1_body if-eq p0, p0, :exit goto :loop1_header :exit return-void .end method # Check two irreducible loops, one within another. Almost identical # to analyze3 and analyze4, except that the inner loop exits from the # back edge, and not the body. # # entry # / \ # / \ # loop1_header loop2_header # - \ / - # - \ / - # - \ / - # - \ / - # - loop2_body - # - | - # - | - # - loop2_back_edge ------ # - | # - | # ----- loop1_body # | # | # exit # ## CHECK-START: void IrreducibleLoop.analyze5(int) builder (after) ## CHECK-DAG: Goto loop:<> outer_loop:none irreducible:true ## CHECK-DAG: Goto outer_loop:<> irreducible:true .method public static analyze5(I)V .registers 1 if-eq p0, p0, :loop1_header goto :loop2_header :loop1_header goto :loop2_body :loop2_header goto :loop2_body :loop2_body goto :loop2_back_edge :loop2_back_edge if-eq p0, p0, :loop2_header goto :loop1_body :loop1_body if-eq p0, p0, :exit goto :loop1_header :exit return-void .end method