Version 1.0.2.
Merge: Limit the amount of dominator tree computations.
CL: https://r8-review.googlesource.com/c/r8/+/14901
Merge: Fix unlinking of unreachable blocks.
CL: https://r8-review.googlesource.com/c/r8/+/14880
R=sgjesse@google.com
Change-Id: Idb5bcd5a4ea748f1bd23a5cdddf45f8afd56506d
diff --git a/src/main/java/com/android/tools/r8/Version.java b/src/main/java/com/android/tools/r8/Version.java
index 5344a61..74b730d 100644
--- a/src/main/java/com/android/tools/r8/Version.java
+++ b/src/main/java/com/android/tools/r8/Version.java
@@ -11,7 +11,7 @@
// This field is accessed from release scripts using simple pattern matching.
// Therefore, changing this field could break our release scripts.
- public static final String LABEL = "v1.0.1";
+ public static final String LABEL = "v1.0.2";
private Version() {
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index 1e076dd..d6fcd3c 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -30,7 +30,6 @@
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
-import java.util.TreeSet;
import java.util.function.Consumer;
import java.util.function.Function;
@@ -553,34 +552,28 @@
assert successors.contains(successor);
assert successor.predecessors.contains(this);
List<BasicBlock> removedBlocks = new ArrayList<>();
- TreeSet<Pair> worklist = new TreeSet<>();
- worklist.add(new Pair(this, successor));
- while (!worklist.isEmpty()) {
- Pair pair = worklist.pollFirst();
- BasicBlock pred = pair.first;
- BasicBlock succ = pair.second;
- assert pred.successors.contains(succ);
- assert succ.predecessors.contains(pred);
- int size = pred.successors.size();
- pred.removeSuccessor(succ);
- assert size == pred.successors.size() + 1;
- size = succ.predecessors.size();
- succ.removePredecessor(pred);
- assert size == succ.predecessors.size() + 1;
- // A predecessor has been removed. If all remaining predecessors are dominated by this block
- // schedule it for removal, as it is no longer reachable.
- if (allPredecessorsDominated(succ, dominator)) {
- removedBlocks.add(succ);
- for (BasicBlock block : succ.successors) {
- worklist.add(new Pair(succ, block));
+ for (BasicBlock dominated : dominator.dominatedBlocks(successor)) {
+ removedBlocks.add(dominated);
+ for (BasicBlock block : dominated.successors) {
+ block.removePredecessor(dominated);
+ }
+ dominated.successors.clear();
+ for (BasicBlock block : dominated.predecessors) {
+ block.removeSuccessor(dominated);
+ }
+ dominated.predecessors.clear();
+ for (Phi phi : dominated.getPhis()) {
+ for (Value operand : phi.getOperands()) {
+ operand.removePhiUser(phi);
}
- for (Instruction instruction : succ.getInstructions()) {
- for (Value value : instruction.inValues) {
- value.removeUser(instruction);
- }
- for (Value value : instruction.getDebugValues()) {
- value.removeDebugUser(instruction);
- }
+ }
+ dominated.getPhis().clear();
+ for (Instruction instruction : dominated.getInstructions()) {
+ for (Value value : instruction.inValues) {
+ value.removeUser(instruction);
+ }
+ for (Value value : instruction.getDebugValues()) {
+ value.removeDebugUser(instruction);
}
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index eeb843c..0b3b021 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -1700,8 +1700,6 @@
}
public void simplifyIf(IRCode code) {
- Supplier<DominatorTree> dominatorTreeMemoization = Suppliers
- .memoize(() -> new DominatorTree(code));
int color = code.reserveMarkingColor();
for (BasicBlock block : code.blocks) {
if (block.isMarked(color)) {
@@ -1711,7 +1709,7 @@
// First rewrite zero comparison.
rewriteIfWithConstZero(block);
- if (simplifyKnownBooleanCondition(code, dominatorTreeMemoization, block, color)) {
+ if (simplifyKnownBooleanCondition(code, block, color)) {
continue;
}
@@ -1757,7 +1755,7 @@
BasicBlock target = theIf.targetFromCondition(cond);
BasicBlock deadTarget =
target == theIf.getTrueTarget() ? theIf.fallthroughBlock() : theIf.getTrueTarget();
- rewriteIfToGoto(dominatorTreeMemoization, block, theIf, target, deadTarget, color);
+ rewriteIfToGoto(code, block, theIf, target, deadTarget, color);
}
}
code.removeMarkedBlocks(color);
@@ -1796,8 +1794,7 @@
* which can be replaced by a fallthrough and the phi value can be replaced
* by an xor instruction which is smaller.
*/
- private boolean simplifyKnownBooleanCondition(IRCode code,
- Supplier<DominatorTree> dominatorTreeMemoization, BasicBlock block, int color) {
+ private boolean simplifyKnownBooleanCondition(IRCode code, BasicBlock block, int color) {
If theIf = block.exit().asIf();
Value testValue = theIf.inValues().get(0);
if (theIf.isZeroTest() && testValue.knownToBeBoolean()) {
@@ -1859,7 +1856,7 @@
// If all phis were removed, there is no need for the diamond shape anymore
// and it can be rewritten to a goto to one of the branches.
if (deadPhis == targetBlock.getPhis().size()) {
- rewriteIfToGoto(dominatorTreeMemoization, block, theIf, trueBlock, falseBlock, color);
+ rewriteIfToGoto(code, block, theIf, trueBlock, falseBlock, color);
return true;
}
}
@@ -1901,9 +1898,10 @@
return false;
}
- private void rewriteIfToGoto(Supplier<DominatorTree> dominatorTreeMemoization, BasicBlock block,
+ private void rewriteIfToGoto(IRCode code, BasicBlock block,
If theIf, BasicBlock target, BasicBlock deadTarget, int color) {
- List<BasicBlock> removedBlocks = block.unlink(deadTarget, dominatorTreeMemoization.get());
+ DominatorTree dominatorTree = new DominatorTree(code);
+ List<BasicBlock> removedBlocks = block.unlink(deadTarget, dominatorTree);
for (BasicBlock removedBlock : removedBlocks) {
if (!removedBlock.isMarked(color)) {
removedBlock.mark(color);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java b/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
index 88f9e63..5144704 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/DeadCodeRemover.java
@@ -12,19 +12,15 @@
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.utils.InternalOptions;
-import com.google.common.base.Suppliers;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
-import java.util.function.Supplier;
public class DeadCodeRemover {
public static void removeDeadCode(
IRCode code, CodeRewriter codeRewriter, InternalOptions options) {
Queue<BasicBlock> worklist = new LinkedList<>();
- Supplier<DominatorTree> dominatorTreeMemoization = Suppliers
- .memoize(() -> new DominatorTree(code));
int color = code.reserveMarkingColor();
worklist.addAll(code.blocks);
for (BasicBlock block = worklist.poll(); block != null; block = worklist.poll()) {
@@ -34,7 +30,7 @@
}
removeDeadInstructions(worklist, code, block, options, color);
removeDeadPhis(worklist, block, options, color);
- removeUnneededCatchHandlers(worklist, block, dominatorTreeMemoization, color);
+ removeUnneededCatchHandlers(worklist, block, code, color);
}
code.removeMarkedBlocks(color);
code.returnMarkingColor(color);
@@ -113,11 +109,12 @@
}
private static void removeUnneededCatchHandlers(Queue<BasicBlock> worklist, BasicBlock block,
- Supplier<DominatorTree> dominatorTreeMemoization, int color) {
+ IRCode code, int color) {
if (block.hasCatchHandlers() && !block.canThrow()) {
CatchHandlers<BasicBlock> handlers = block.getCatchHandlers();
for (BasicBlock target : handlers.getUniqueTargets()) {
- for (BasicBlock unlinked : block.unlink(target, dominatorTreeMemoization.get())) {
+ DominatorTree dominatorTree = new DominatorTree(code);
+ for (BasicBlock unlinked : block.unlink(target, dominatorTree)) {
if (!unlinked.isMarked(color)) {
Iterator<Instruction> iterator = unlinked.iterator();
while (iterator.hasNext()) {
diff --git a/src/test/java/com/android/tools/r8/jasmin/Regress72269635.java b/src/test/java/com/android/tools/r8/jasmin/Regress72269635.java
new file mode 100644
index 0000000..e92b8a9
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/jasmin/Regress72269635.java
@@ -0,0 +1,63 @@
+// Copyright (c) 2018, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+package com.android.tools.r8.jasmin;
+
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.jasmin.JasminBuilder.ClassFileVersion;
+import com.android.tools.r8.naming.MemberNaming.MethodSignature;
+import com.android.tools.r8.utils.AndroidApp;
+import com.google.common.collect.ImmutableList;
+import org.junit.Test;
+
+public class Regress72269635 extends JasminTestBase {
+
+ @Test
+ public void testDeadBlocksRemoved() throws Exception {
+ JasminBuilder builder = new JasminBuilder(ClassFileVersion.JDK_1_4);
+ JasminBuilder.ClassBuilder clazz = builder.addClass("Test");
+
+ clazz.addStaticMethod("test", ImmutableList.of("IIII"), "J",
+ ".limit stack 3",
+ ".limit locals 5",
+ "L0:",
+ " iconst_2",
+ " ifge L0",
+ "L48:",
+ " iload 3",
+ " ifle L48",
+ " goto L209",
+ " aconst_null",
+ " athrow",
+ "L209:",
+ " aconst_null",
+ " iconst_2",
+ " newarray float",
+ " if_acmpne L250",
+ "L240:",
+ " iload 3",
+ " pop",
+ "L250:",
+ " iload 3",
+ " ifgt L240",
+ " iload 3",
+ " istore 0",
+ " goto L357",
+ "L318:",
+ " iinc 0 1",
+ "L351:",
+ " iinc 0 1",
+ " goto L351",
+ "L357:",
+ " iinc 0 1",
+ "L415:",
+ " iinc 0 1",
+ " goto L415"
+ );
+
+ // Just compiling this code used to throw exceptions because not all dead blocks
+ // were removed.
+ AndroidApp originalApplication = builder.build();
+ ToolHelper.runD8(originalApplication);
+ }
+}
