Implement irreducible loop support in optimizing.
So we don't fallback to the interpreter in the presence of
irreducible loops.
Implications:
- A loop pre-header does not necessarily dominate a loop header.
- Non-constant redundant phis will be kept in loop headers, to
satisfy our linear scan register allocation algorithm.
- while-graph optimizations, such as gvn, licm, lse, and dce
need to know when they are dealing with irreducible loops.
Change-Id: I2cea8934ce0b40162d215353497c7f77d6c9137e
diff --git a/test/559-checker-irreducible-loop/expected.txt b/test/559-checker-irreducible-loop/expected.txt
new file mode 100644
index 0000000..b64be7a
--- /dev/null
+++ b/test/559-checker-irreducible-loop/expected.txt
@@ -0,0 +1,7 @@
+84
+30
+168
+126
+class Main
+42
+-42
diff --git a/test/559-checker-irreducible-loop/info.txt b/test/559-checker-irreducible-loop/info.txt
new file mode 100644
index 0000000..e0ace18
--- /dev/null
+++ b/test/559-checker-irreducible-loop/info.txt
@@ -0,0 +1 @@
+Tests for irreducible loop support in compiler.
diff --git a/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali b/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali
new file mode 100644
index 0000000..30a648d
--- /dev/null
+++ b/test/559-checker-irreducible-loop/smali/IrreducibleLoop.smali
@@ -0,0 +1,561 @@
+# 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 (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 (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 if a irreducible loop entry is dead, the loop can become
+# natural.
+# We start with:
+#
+# entry
+# / \
+# / \
+# loop_entry \
+# / \- \
+# exit \- \
+# other_loop_entry
+#
+## CHECK-START: int IrreducibleLoop.dce(int) dead_code_elimination (before)
+## CHECK: irreducible:true
+
+# And end with:
+#
+# entry
+# /
+# /
+# loop_entry
+# / \-
+# exit \-
+# other_loop_entry
+
+## CHECK-START: int IrreducibleLoop.dce(int) dead_code_elimination (after)
+## CHECK-NOT: 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, LIrreducibleLoop;
+ 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, LIrreducibleLoop;
+ 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, LIrreducibleLoop;
+ 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) ssa_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) ssa_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) ssa_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) ssa_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) ssa_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
diff --git a/test/559-checker-irreducible-loop/src/Main.java b/test/559-checker-irreducible-loop/src/Main.java
new file mode 100644
index 0000000..ab84f81
--- /dev/null
+++ b/test/559-checker-irreducible-loop/src/Main.java
@@ -0,0 +1,69 @@
+/*
+ * 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.
+ */
+
+import java.lang.reflect.Method;
+
+public class Main {
+ // Workaround for b/18051191.
+ class InnerClass {}
+
+ public static void main(String[] args) throws Exception {
+ Class<?> c = Class.forName("IrreducibleLoop");
+ {
+ Method m = c.getMethod("simpleLoop", int.class);
+ Object[] arguments = { 42 };
+ System.out.println(m.invoke(null, arguments));
+ }
+
+ {
+ Method m = c.getMethod("lse", int.class, Main.class);
+ Object[] arguments = { 42, new Main() };
+ System.out.println(m.invoke(null, arguments));
+ }
+
+ {
+ Method m = c.getMethod("dce", int.class);
+ Object[] arguments = { 42 };
+ System.out.println(m.invoke(null, arguments));
+ }
+
+ {
+ Method m = c.getMethod("liveness", int.class);
+ Object[] arguments = { 42 };
+ System.out.println(m.invoke(null, arguments));
+ }
+
+ {
+ Method m = c.getMethod("gvn");
+ Object[] arguments = { };
+ System.out.println(m.invoke(null, arguments));
+ }
+
+ {
+ Method m = c.getMethod("licm1", int.class);
+ Object[] arguments = { 42 };
+ System.out.println(m.invoke(null, arguments));
+ }
+
+ {
+ Method m = c.getMethod("licm2", int.class);
+ Object[] arguments = { 42 };
+ System.out.println(m.invoke(null, arguments));
+ }
+ }
+
+ int myField;
+}