# 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: <<Arg:i\d+>> ParameterValue liveness:<<ArgLiv:\d+>> ranges:{[<<ArgLiv>>,<<ArgLoopPhiUse:\d+>>)}
## CHECK-DAG: <<LoopPhi:i\d+>> Phi [<<Arg>>,<<PhiInLoop:i\d+>>] liveness:<<ArgLoopPhiUse>> ranges:{[<<ArgLoopPhiUse>>,<<PhiInLoopUse:\d+>>)}
## CHECK-DAG: <<PhiInLoop>> Phi [<<Arg>>,<<LoopPhi>>] liveness:<<PhiInLoopUse>> ranges:{[<<PhiInLoopUse>>,<<BackEdgeLifetimeEnd:\d+>>)}
## CHECK: Return liveness:<<ReturnLiveness:\d+>>
## CHECK-EVAL: <<ReturnLiveness>> == <<BackEdgeLifetimeEnd>> + 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:<<OuterLoop:B\d+>> irreducible:false
## CHECK: Goto outer_loop:<<OuterLoop>> 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:<<OuterLoop:B\d+>> outer_loop:none irreducible:true
## CHECK-DAG: Goto outer_loop:<<OuterLoop>> 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:<<OuterLoop:B\d+>> outer_loop:none irreducible:true
## CHECK-DAG: Goto outer_loop:<<OuterLoop>> 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:<<OuterLoop:B\d+>> outer_loop:none irreducible:true
## CHECK-DAG: Goto outer_loop:<<OuterLoop>> 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:<<OuterLoop:B\d+>> outer_loop:none irreducible:true
## CHECK-DAG: Goto outer_loop:<<OuterLoop>> 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