ART: Dead block removal

Adds a new pass which finds all unreachable blocks, typically due to
simplifying an if-condition to a constant, and removes them from the
graph. The patch also slightly generalizes the graph-transforming
operations.

Change-Id: Iff7c97f1d10b52886f3cd7401689ebe1bfdbf456

3 files changed, 148 insertions, 0 deletions

diff --git a/test/480-checker-dead-blocks/expected.txt b/test/480-checker-dead-blocks/expected.txt
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/test/480-checker-dead-blocks/expected.txt
diff --git a/test/480-checker-dead-blocks/info.txt b/test/480-checker-dead-blocks/info.txt
new file mode 100644
index 0000000..5aeafac
--- /dev/null
+++ b/test/480-checker-dead-blocks/info.txt
@@ -0,0 +1 @@
+Test removal of dead blocks.
\ No newline at end of file
diff --git a/test/480-checker-dead-blocks/src/Main.java b/test/480-checker-dead-blocks/src/Main.java
new file mode 100644
index 0000000..560ce95
--- /dev/null
+++ b/test/480-checker-dead-blocks/src/Main.java
@@ -0,0 +1,147 @@
+/*
+* 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.
+*/
+
+public class Main {
+
+  public static void assertIntEquals(int expected, int result) {
+    if (expected != result) {
+      throw new Error("Expected: " + expected + ", found: " + result);
+    }
+  }
+
+  public static boolean inlineTrue() {
+    return true;
+  }
+
+  public static boolean inlineFalse() {
+    return false;
+  }
+
+  // CHECK-START: int Main.testTrueBranch(int, int) dead_code_elimination_final (before)
+  // CHECK-DAG:     [[ArgX:i\d+]]    ParameterValue
+  // CHECK-DAG:     [[ArgY:i\d+]]    ParameterValue
+  // CHECK-DAG:                      If
+  // CHECK-DAG:     [[Add:i\d+]]     Add [ [[ArgX]] [[ArgY]] ]
+  // CHECK-DAG:     [[Sub:i\d+]]     Sub [ [[ArgX]] [[ArgY]] ]
+  // CHECK-DAG:     [[Phi:i\d+]]     Phi [ [[Add]] [[Sub]] ]
+  // CHECK-DAG:                      Return [ [[Phi]] ]
+
+  // CHECK-START: int Main.testTrueBranch(int, int) dead_code_elimination_final (after)
+  // CHECK-DAG:     [[ArgX:i\d+]]    ParameterValue
+  // CHECK-DAG:     [[ArgY:i\d+]]    ParameterValue
+  // CHECK-DAG:     [[Add:i\d+]]     Add [ [[ArgX]] [[ArgY]] ]
+  // CHECK-DAG:                      Return [ [[Add]] ]
+
+  // CHECK-START: int Main.testTrueBranch(int, int) dead_code_elimination_final (after)
+  // CHECK-NOT:                      If
+  // CHECK-NOT:                      Sub
+  // CHECK-NOT:                      Phi
+
+  public static int testTrueBranch(int x, int y) {
+    int z;
+    if (inlineTrue()) {
+      z = x + y;
+    } else {
+      z = x - y;
+    }
+    return z;
+  }
+
+  // CHECK-START: int Main.testFalseBranch(int, int) dead_code_elimination_final (before)
+  // CHECK-DAG:     [[ArgX:i\d+]]    ParameterValue
+  // CHECK-DAG:     [[ArgY:i\d+]]    ParameterValue
+  // CHECK-DAG:                      If
+  // CHECK-DAG:     [[Add:i\d+]]     Add [ [[ArgX]] [[ArgY]] ]
+  // CHECK-DAG:     [[Sub:i\d+]]     Sub [ [[ArgX]] [[ArgY]] ]
+  // CHECK-DAG:     [[Phi:i\d+]]     Phi [ [[Add]] [[Sub]] ]
+  // CHECK-DAG:                      Return [ [[Phi]] ]
+
+  // CHECK-START: int Main.testFalseBranch(int, int) dead_code_elimination_final (after)
+  // CHECK-DAG:     [[ArgX:i\d+]]    ParameterValue
+  // CHECK-DAG:     [[ArgY:i\d+]]    ParameterValue
+  // CHECK-DAG:     [[Sub:i\d+]]     Sub [ [[ArgX]] [[ArgY]] ]
+  // CHECK-DAG:                      Return [ [[Sub]] ]
+
+  // CHECK-START: int Main.testFalseBranch(int, int) dead_code_elimination_final (after)
+  // CHECK-NOT:                      If
+  // CHECK-NOT:                      Add
+  // CHECK-NOT:                      Phi
+
+  public static int testFalseBranch(int x, int y) {
+    int z;
+    if (inlineFalse()) {
+      z = x + y;
+    } else {
+      z = x - y;
+    }
+    return z;
+  }
+
+  // CHECK-START: int Main.testRemoveLoop(int) dead_code_elimination_final (before)
+  // CHECK:                          Mul
+
+  // CHECK-START: int Main.testRemoveLoop(int) dead_code_elimination_final (after)
+  // CHECK-NOT:                      Mul
+
+  public static int testRemoveLoop(int x) {
+    if (inlineFalse()) {
+      for (int i = 0; i < x; ++i) {
+        x *= x;
+      }
+    }
+    return x;
+  }
+
+  // CHECK-START: int Main.testInfiniteLoop(int) dead_code_elimination_final (before)
+  // CHECK-DAG:                      Return
+  // CHECK-DAG:                      Exit
+
+  // CHECK-START: int Main.testInfiniteLoop(int) dead_code_elimination_final (after)
+  // CHECK-NOT:                      Return
+  // CHECK-NOT:                      Exit
+
+  public static int testInfiniteLoop(int x) {
+    while (inlineTrue()) {
+      x++;
+    }
+    return x;
+  }
+
+  // CHECK-START: int Main.testDeadLoop(int) dead_code_elimination_final (before)
+  // CHECK-DAG:                      If
+  // CHECK-DAG:                      Add
+
+  // CHECK-START: int Main.testDeadLoop(int) dead_code_elimination_final (after)
+  // CHECK-DAG:     [[Arg:i\d+]]     ParameterValue
+  // CHECK-DAG:                      Return [ [[Arg]] ]
+
+  // CHECK-START: int Main.testRemoveLoop(int) dead_code_elimination_final (after)
+  // CHECK-NOT:                      If
+  // CHECK-NOT:                      Add
+
+  public static int testDeadLoop(int x) {
+    while (inlineFalse()) {
+      x++;
+    }
+    return x;
+  }
+
+  public static void main(String[] args) {
+    assertIntEquals(7, testTrueBranch(4, 3));
+    assertIntEquals(1, testFalseBranch(4, 3));
+    assertIntEquals(42, testRemoveLoop(42));
+  }
+}