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); + } +}