Reland "Make ThrowCatchOptimizer a CodeRewriterPass"
This reverts commit 57693cc9d715327ab0b44889fcb05f8637f7c442.
Change-Id: I5ba37246f42f5e563db57e1db13510c01158b0e5
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index 8941176..994d45b 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -36,6 +36,7 @@
import com.android.tools.r8.ir.conversion.passes.MoveResultRewriter;
import com.android.tools.r8.ir.conversion.passes.NaturalIntLoopRemover;
import com.android.tools.r8.ir.conversion.passes.ParentConstructorHoistingCodeRewriter;
+import com.android.tools.r8.ir.conversion.passes.RedundantConstNumberRemover;
import com.android.tools.r8.ir.conversion.passes.SplitBranch;
import com.android.tools.r8.ir.conversion.passes.ThrowCatchOptimizer;
import com.android.tools.r8.ir.conversion.passes.TrivialCheckCastAndInstanceOfRemover;
@@ -760,21 +761,16 @@
new StringBuilderAppendOptimizer(appView).run(code, timing);
}
new SparseConditionalConstantPropagation(appView, code).run(code, timing);
- timing.begin("Rewrite always throwing instructions");
- new ThrowCatchOptimizer(appView).optimizeAlwaysThrowingInstructions(code);
- timing.end();
- timing.begin("Simplify control flow");
- if (new BranchSimplifier(appView).simplifyBranches(code)) {
+ new ThrowCatchOptimizer(appView, isDebugMode).run(code, timing);
+ if (new BranchSimplifier(appView)
+ .run(code, timing)
+ .asControlFlowSimplificationResult()
+ .anyAffectedValues()) {
new TrivialCheckCastAndInstanceOfRemover(appView)
.run(code, methodProcessor, methodProcessingContext, timing);
}
- timing.end();
splitBranch.run(code, timing);
- if (options.enableRedundantConstNumberOptimization) {
- timing.begin("Remove const numbers");
- codeRewriter.redundantConstNumberRemoval(code);
- timing.end();
- }
+ new RedundantConstNumberRemover(appView).run(code, timing);
if (RedundantFieldLoadAndStoreElimination.shouldRun(appView, code)) {
timing.begin("Remove field loads");
new RedundantFieldLoadAndStoreElimination(appView, code).run();
@@ -788,13 +784,6 @@
invertConditionalsForTesting(code);
}
- if (!isDebugMode) {
- timing.begin("Rewrite throw NPE");
- new ThrowCatchOptimizer(appView).rewriteThrowNullPointerException(code);
- timing.end();
- previous = printMethod(code, "IR after rewrite throw null (SSA)", previous);
- }
-
timing.begin("Optimize class initializers");
ClassInitializerDefaultsResult classInitializerDefaultsResult =
classInitializerDefaultsOptimization.optimize(code, feedback);
@@ -934,7 +923,6 @@
// Assert that we do not have unremoved non-sense code in the output, e.g., v <- non-null NULL.
assert code.verifyNoNullabilityBottomTypes();
-
assert code.verifyTypes(appView);
previous =
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/BranchSimplifier.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/BranchSimplifier.java
index 28ddb01..44c9ddd 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/BranchSimplifier.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/BranchSimplifier.java
@@ -4,6 +4,10 @@
package com.android.tools.r8.ir.conversion.passes;
+import static com.android.tools.r8.ir.conversion.passes.BranchSimplifier.ControlFlowSimplificationResult.NO_CHANGE;
+import static com.android.tools.r8.ir.conversion.passes.BranchSimplifier.ControlFlowSimplificationResult.create;
+
+import com.android.tools.r8.graph.AppInfo;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexEncodedField;
@@ -35,10 +39,10 @@
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.code.ValueType;
import com.android.tools.r8.ir.code.Xor;
+import com.android.tools.r8.ir.conversion.passes.result.CodeRewriterResult;
import com.android.tools.r8.ir.optimize.controlflow.SwitchCaseAnalyzer;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.BooleanUtils;
-import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.InternalOutputMode;
import com.android.tools.r8.utils.LongInterval;
import com.google.common.collect.ImmutableList;
@@ -59,20 +63,27 @@
import java.util.PriorityQueue;
import java.util.Set;
-public class BranchSimplifier {
-
- private final AppView<?> appView;
- private final InternalOptions options;
+public class BranchSimplifier extends CodeRewriterPass<AppInfo> {
public BranchSimplifier(AppView<?> appView) {
- this.appView = appView;
- this.options = appView.options();
+ super(appView);
}
- public boolean simplifyBranches(IRCode code) {
- boolean anyAffectedValues = rewriteSwitch(code);
- anyAffectedValues |= simplifyIf(code).anyAffectedValues();
- return anyAffectedValues;
+ @Override
+ protected String getTimingId() {
+ return "BranchSimplifier";
+ }
+
+ @Override
+ protected boolean shouldRewriteCode(IRCode code) {
+ return true;
+ }
+
+ @Override
+ protected CodeRewriterResult rewriteCode(IRCode code) {
+ ControlFlowSimplificationResult switchResult = rewriteSwitch(code);
+ ControlFlowSimplificationResult ifResult = simplifyIf(code);
+ return switchResult.combine(ifResult);
}
public ControlFlowSimplificationResult simplifyIf(IRCode code) {
@@ -126,10 +137,26 @@
}
code.removeRedundantBlocks();
assert code.isConsistentSSA(appView);
- return new ControlFlowSimplificationResult(!affectedValues.isEmpty(), simplified);
+ return create(!affectedValues.isEmpty(), simplified);
}
- public static class ControlFlowSimplificationResult {
+ public static class ControlFlowSimplificationResult implements CodeRewriterResult {
+
+ static ControlFlowSimplificationResult create(
+ boolean anyAffectedValues, boolean anySimplifications) {
+ if (anyAffectedValues) {
+ assert anySimplifications;
+ return ALL_CHANGED;
+ }
+ return anySimplifications ? ONLY_SIMPLIFICATIONS : NO_CHANGE;
+ }
+
+ static final ControlFlowSimplificationResult ALL_CHANGED =
+ new ControlFlowSimplificationResult(true, true);
+ static final ControlFlowSimplificationResult ONLY_SIMPLIFICATIONS =
+ new ControlFlowSimplificationResult(false, true);
+ static final ControlFlowSimplificationResult NO_CHANGE =
+ new ControlFlowSimplificationResult(false, false);
private final boolean anyAffectedValues;
private final boolean anySimplifications;
@@ -140,6 +167,11 @@
this.anySimplifications = anySimplifications;
}
+ @Override
+ public ControlFlowSimplificationResult asControlFlowSimplificationResult() {
+ return this;
+ }
+
public boolean anyAffectedValues() {
return anyAffectedValues;
}
@@ -147,6 +179,18 @@
public boolean anySimplifications() {
return anySimplifications;
}
+
+ @Override
+ public boolean hasChanged() {
+ assert !anyAffectedValues || anySimplifications;
+ return anySimplifications();
+ }
+
+ public ControlFlowSimplificationResult combine(ControlFlowSimplificationResult ifResult) {
+ return create(
+ anyAffectedValues || ifResult.anyAffectedValues,
+ anySimplifications || ifResult.anySimplifications);
+ }
}
private boolean simplifyIfZeroTest(IRCode code, BasicBlock block, If theIf) {
@@ -567,22 +611,25 @@
return true;
}
- private boolean rewriteSwitch(IRCode code) {
+ private ControlFlowSimplificationResult rewriteSwitch(IRCode code) {
return rewriteSwitch(code, SwitchCaseAnalyzer.getInstance());
}
- private boolean rewriteSwitch(IRCode code, SwitchCaseAnalyzer switchCaseAnalyzer) {
+ private ControlFlowSimplificationResult rewriteSwitch(
+ IRCode code, SwitchCaseAnalyzer switchCaseAnalyzer) {
if (!options.isSwitchRewritingEnabled()) {
- return false;
+ return NO_CHANGE;
}
if (!code.metadata().mayHaveSwitch()) {
- return false;
+ return NO_CHANGE;
}
return rewriteSwitchFull(code, switchCaseAnalyzer);
}
- private boolean rewriteSwitchFull(IRCode code, SwitchCaseAnalyzer switchCaseAnalyzer) {
+ private ControlFlowSimplificationResult rewriteSwitchFull(
+ IRCode code, SwitchCaseAnalyzer switchCaseAnalyzer) {
boolean needToRemoveUnreachableBlocks = false;
+ boolean anySimplifications = false;
ListIterator<BasicBlock> blocksIterator = code.listIterator();
while (blocksIterator.hasNext()) {
BasicBlock block = blocksIterator.next();
@@ -594,6 +641,7 @@
if (options.testing.enableDeadSwitchCaseElimination) {
SwitchCaseEliminator eliminator =
removeUnnecessarySwitchCases(code, theSwitch, iterator, switchCaseAnalyzer);
+ anySimplifications |= eliminator.canBeOptimized();
if (eliminator.mayHaveIntroducedUnreachableBlocks()) {
needToRemoveUnreachableBlocks = true;
}
@@ -608,7 +656,8 @@
theSwitch = instruction.asSwitch();
}
if (theSwitch.isIntSwitch()) {
- rewriteIntSwitch(code, blocksIterator, block, iterator, theSwitch.asIntSwitch());
+ anySimplifications |=
+ rewriteIntSwitch(code, blocksIterator, block, iterator, theSwitch.asIntSwitch());
}
}
}
@@ -621,12 +670,13 @@
Set<Value> affectedValues =
needToRemoveUnreachableBlocks ? code.removeUnreachableBlocks() : ImmutableSet.of();
- if (!affectedValues.isEmpty()) {
+ boolean anyAffectedValues = !affectedValues.isEmpty();
+ if (anyAffectedValues) {
new TypeAnalysis(appView).narrowing(affectedValues);
}
code.removeRedundantBlocks();
assert code.isConsistentSSA(appView);
- return !affectedValues.isEmpty();
+ return create(anyAffectedValues, anySimplifications);
}
public void rewriteSingleKeySwitchToIf(
@@ -652,19 +702,19 @@
iterator.replaceCurrentInstruction(replacement);
}
- private void rewriteIntSwitch(
+ private boolean rewriteIntSwitch(
IRCode code,
ListIterator<BasicBlock> blockIterator,
BasicBlock block,
InstructionListIterator iterator,
IntSwitch theSwitch) {
if (disableSwitchToIfRewritingForClassIdComparisons(theSwitch)) {
- return;
+ return false;
}
if (theSwitch.numberOfKeys() == 1) {
rewriteSingleKeySwitchToIf(code, block, iterator, theSwitch);
- return;
+ return true;
}
// If there are more than 1 key, we use the following algorithm to find keys to combine.
@@ -753,7 +803,9 @@
if (newSwitchesSize + outliersAsIfSize + codeUnitMargin() < currentSize) {
convertSwitchToSwitchAndIfs(
code, blockIterator, block, iterator, theSwitch, newSwitchSequences, outliers);
+ return true;
}
+ return false;
}
// TODO(b/181732463): We currently disable switch-to-if rewritings for switches on $r8$classId
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/RedundantConstNumberRemover.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/RedundantConstNumberRemover.java
new file mode 100644
index 0000000..70402cc
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/RedundantConstNumberRemover.java
@@ -0,0 +1,278 @@
+// Copyright (c) 2023, 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.ir.conversion.passes;
+
+import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.ConstNumber;
+import com.android.tools.r8.ir.code.DominatorTree;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.If;
+import com.android.tools.r8.ir.code.IfType;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.conversion.passes.result.CodeRewriterResult;
+import com.android.tools.r8.utils.LazyBox;
+import it.unimi.dsi.fastutil.longs.Long2ReferenceMap;
+import it.unimi.dsi.fastutil.longs.Long2ReferenceOpenHashMap;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.ListIterator;
+
+/**
+ * This optimization exploits that we can sometimes learn the constant value of an SSA value that
+ * flows into an if-eq of if-neq instruction.
+ *
+ * <p>Consider the following example:
+ *
+ * <pre>
+ * 1. if (obj != null) {
+ * 2. return doStuff();
+ * 3. }
+ * 4. return null;
+ * </pre>
+ *
+ * <p>Since we know that `obj` is null in all blocks that are dominated by the false-target of the
+ * if-instruction in line 1, we can safely replace the null-constant in line 4 by `obj`, and thereby
+ * save a const-number instruction.
+ */
+public class RedundantConstNumberRemover extends CodeRewriterPass<AppInfo> {
+
+ public RedundantConstNumberRemover(AppView<?> appView) {
+ super(appView);
+ }
+
+ @Override
+ protected String getTimingId() {
+ return "RedundantConstNumberRemover";
+ }
+
+ @Override
+ protected boolean shouldRewriteCode(IRCode code) {
+ return options.enableRedundantConstNumberOptimization && code.metadata().mayHaveConstNumber();
+ }
+
+ @Override
+ protected CodeRewriterResult rewriteCode(IRCode code) {
+ redundantConstNumberRemoval(code);
+ return CodeRewriterResult.NONE;
+ }
+
+ public void redundantConstNumberRemoval(IRCode code) {
+ if (appView.options().canHaveDalvikIntUsedAsNonIntPrimitiveTypeBug()
+ && !appView.options().testing.forceRedundantConstNumberRemoval) {
+ // See also b/124152497.
+ return;
+ }
+
+ LazyBox<Long2ReferenceMap<List<ConstNumber>>> constantsByValue =
+ new LazyBox<>(() -> getConstantsByValue(code));
+ LazyBox<DominatorTree> dominatorTree = new LazyBox<>(() -> new DominatorTree(code));
+
+ boolean changed = false;
+ for (BasicBlock block : code.blocks) {
+ Instruction lastInstruction = block.getInstructions().getLast();
+ if (!lastInstruction.isIf()) {
+ continue;
+ }
+
+ If ifInstruction = lastInstruction.asIf();
+ IfType type = ifInstruction.getType();
+
+ Value lhs = ifInstruction.inValues().get(0);
+ Value rhs = !ifInstruction.isZeroTest() ? ifInstruction.inValues().get(1) : null;
+
+ if (!ifInstruction.isZeroTest() && !lhs.isConstNumber() && !rhs.isConstNumber()) {
+ // We can only conclude anything from an if-instruction if it is a zero-test or if one of
+ // the two operands is a constant.
+ continue;
+ }
+
+ // If the type is neither EQ nor NE, we cannot conclude anything about any of the in-values
+ // of the if-instruction from the outcome of the if-instruction.
+ if (type != IfType.EQ && type != IfType.NE) {
+ continue;
+ }
+
+ BasicBlock trueTarget, falseTarget;
+ if (type == IfType.EQ) {
+ trueTarget = ifInstruction.getTrueTarget();
+ falseTarget = ifInstruction.fallthroughBlock();
+ } else {
+ falseTarget = ifInstruction.getTrueTarget();
+ trueTarget = ifInstruction.fallthroughBlock();
+ }
+
+ if (ifInstruction.isZeroTest()) {
+ changed |=
+ replaceDominatedConstNumbers(0, lhs, trueTarget, constantsByValue, code, dominatorTree);
+ if (lhs.knownToBeBoolean()) {
+ changed |=
+ replaceDominatedConstNumbers(
+ 1, lhs, falseTarget, constantsByValue, code, dominatorTree);
+ }
+ } else {
+ assert rhs != null;
+ if (lhs.isConstNumber()) {
+ ConstNumber lhsAsNumber = lhs.getConstInstruction().asConstNumber();
+ changed |=
+ replaceDominatedConstNumbers(
+ lhsAsNumber.getRawValue(),
+ rhs,
+ trueTarget,
+ constantsByValue,
+ code,
+ dominatorTree);
+ if (lhs.knownToBeBoolean() && rhs.knownToBeBoolean()) {
+ changed |=
+ replaceDominatedConstNumbers(
+ negateBoolean(lhsAsNumber),
+ rhs,
+ falseTarget,
+ constantsByValue,
+ code,
+ dominatorTree);
+ }
+ } else {
+ assert rhs.isConstNumber();
+ ConstNumber rhsAsNumber = rhs.getConstInstruction().asConstNumber();
+ changed |=
+ replaceDominatedConstNumbers(
+ rhsAsNumber.getRawValue(),
+ lhs,
+ trueTarget,
+ constantsByValue,
+ code,
+ dominatorTree);
+ if (lhs.knownToBeBoolean() && rhs.knownToBeBoolean()) {
+ changed |=
+ replaceDominatedConstNumbers(
+ negateBoolean(rhsAsNumber),
+ lhs,
+ falseTarget,
+ constantsByValue,
+ code,
+ dominatorTree);
+ }
+ }
+ }
+
+ if (constantsByValue.computeIfAbsent().isEmpty()) {
+ break;
+ }
+ }
+
+ if (changed) {
+ code.removeAllDeadAndTrivialPhis();
+ }
+ assert code.isConsistentSSA(appView);
+ }
+
+ private static Long2ReferenceMap<List<ConstNumber>> getConstantsByValue(IRCode code) {
+ // A map from the raw value of constants in `code` to the const number instructions that define
+ // the given raw value (irrespective of the type of the raw value).
+ Long2ReferenceMap<List<ConstNumber>> constantsByValue = new Long2ReferenceOpenHashMap<>();
+
+ // Initialize `constantsByValue`.
+ for (Instruction instruction : code.instructions()) {
+ if (instruction.isConstNumber()) {
+ ConstNumber constNumber = instruction.asConstNumber();
+ if (constNumber.outValue().hasLocalInfo()) {
+ // Not necessarily constant, because it could be changed in the debugger.
+ continue;
+ }
+ long rawValue = constNumber.getRawValue();
+ if (constantsByValue.containsKey(rawValue)) {
+ constantsByValue.get(rawValue).add(constNumber);
+ } else {
+ List<ConstNumber> list = new ArrayList<>();
+ list.add(constNumber);
+ constantsByValue.put(rawValue, list);
+ }
+ }
+ }
+ return constantsByValue;
+ }
+
+ private static int negateBoolean(ConstNumber number) {
+ assert number.outValue().knownToBeBoolean();
+ return number.getRawValue() == 0 ? 1 : 0;
+ }
+
+ private boolean replaceDominatedConstNumbers(
+ long withValue,
+ Value newValue,
+ BasicBlock dominator,
+ LazyBox<Long2ReferenceMap<List<ConstNumber>>> constantsByValueSupplier,
+ IRCode code,
+ LazyBox<DominatorTree> dominatorTree) {
+ if (newValue.hasLocalInfo()) {
+ // We cannot replace a constant with a value that has local info, because that could change
+ // debugging behavior.
+ return false;
+ }
+
+ Long2ReferenceMap<List<ConstNumber>> constantsByValue =
+ constantsByValueSupplier.computeIfAbsent();
+ List<ConstNumber> constantsWithValue = constantsByValue.get(withValue);
+ if (constantsWithValue == null || constantsWithValue.isEmpty()) {
+ return false;
+ }
+
+ boolean changed = false;
+
+ ListIterator<ConstNumber> constantWithValueIterator = constantsWithValue.listIterator();
+ while (constantWithValueIterator.hasNext()) {
+ ConstNumber constNumber = constantWithValueIterator.next();
+ Value value = constNumber.outValue();
+ assert !value.hasLocalInfo();
+ assert constNumber.getRawValue() == withValue;
+
+ BasicBlock block = constNumber.getBlock();
+
+ // If the following condition does not hold, then the if-instruction does not dominate the
+ // block containing the constant, although the true or false target does.
+ if (block == dominator && block.getPredecessors().size() != 1) {
+ // This should generally not happen, but it is possible to write bytecode where it does.
+ assert false;
+ continue;
+ }
+
+ if (value.knownToBeBoolean() && !newValue.knownToBeBoolean()) {
+ // We cannot replace a boolean by a none-boolean since that can lead to verification
+ // errors. For example, the following code fails with "register v1 has type Imprecise
+ // Constant: 127 but expected Boolean return-1nr".
+ //
+ // public boolean convertIntToBoolean(int v1) {
+ // const/4 v0, 0x1
+ // if-eq v1, v0, :eq_true
+ // const/4 v1, 0x0
+ // :eq_true
+ // return v1
+ // }
+ continue;
+ }
+
+ if (dominatorTree.computeIfAbsent().dominatedBy(block, dominator)) {
+ if (newValue.getType().lessThanOrEqual(value.getType(), appView)) {
+ value.replaceUsers(newValue);
+ block.listIterator(code, constNumber).removeOrReplaceByDebugLocalRead();
+ constantWithValueIterator.remove();
+ changed = true;
+ } else if (value.getType().isNullType()) {
+ // TODO(b/120257211): Need a mechanism to determine if `newValue` can be used at all of
+ // the use sites of `value` without introducing a type error.
+ }
+ }
+ }
+
+ if (constantsWithValue.isEmpty()) {
+ constantsByValue.remove(withValue);
+ }
+
+ return changed;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/SwitchCaseEliminator.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/SwitchCaseEliminator.java
index cbda630..4a1a1d4 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/SwitchCaseEliminator.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/SwitchCaseEliminator.java
@@ -45,7 +45,7 @@
&& switchCasesToBeRemoved.size() == theSwitch.numberOfKeys();
}
- private boolean canBeOptimized() {
+ boolean canBeOptimized() {
assert switchCasesToBeRemoved == null || !switchCasesToBeRemoved.isEmpty();
return switchCasesToBeRemoved != null || hasAlwaysHitCase() || !isFallthroughLive();
}
@@ -96,7 +96,7 @@
liveFallthrough = false;
}
- boolean optimize() {
+ void optimize() {
if (canBeOptimized()) {
int originalNumberOfSuccessors = block.getSuccessors().size();
IntList removedSuccessorIndices = unlinkDeadSuccessors();
@@ -107,9 +107,7 @@
// Replace switch by a new switch where the dead switch cases have been removed.
replaceSwitchByOptimizedSwitch(originalNumberOfSuccessors, removedSuccessorIndices);
}
- return true;
}
- return false;
}
private IntList unlinkDeadSuccessors() {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/ThrowCatchOptimizer.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/ThrowCatchOptimizer.java
index f34a6bd..85cd30e 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/ThrowCatchOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/ThrowCatchOptimizer.java
@@ -5,10 +5,10 @@
package com.android.tools.r8.ir.conversion.passes;
import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppInfo;
import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexClassAndMethod;
-import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.ProgramMethod;
import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
@@ -32,6 +32,7 @@
import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.ir.code.Throw;
import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.conversion.passes.result.CodeRewriterResult;
import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Sets;
@@ -40,18 +41,42 @@
import java.util.ListIterator;
import java.util.Set;
-public class ThrowCatchOptimizer {
+public class ThrowCatchOptimizer extends CodeRewriterPass<AppInfo> {
- private final AppView<?> appView;
- private final DexItemFactory dexItemFactory;
+ private final boolean rewriteThrowNull;
+
+ public ThrowCatchOptimizer(AppView<?> appView, boolean isDebug) {
+ super(appView);
+ this.rewriteThrowNull = !isDebug;
+ }
public ThrowCatchOptimizer(AppView<?> appView) {
- this.appView = appView;
- this.dexItemFactory = appView.dexItemFactory();
+ super(appView);
+ this.rewriteThrowNull = false;
+ }
+
+ @Override
+ protected String getTimingId() {
+ return "ThrowCatchOptimizer";
+ }
+
+ @Override
+ protected boolean shouldRewriteCode(IRCode code) {
+ return true;
+ }
+
+ @Override
+ protected CodeRewriterResult rewriteCode(IRCode code) {
+ optimizeAlwaysThrowingInstructions(code);
+ if (rewriteThrowNull) {
+ rewriteThrowNullPointerException(code);
+ }
+ return CodeRewriterResult.NONE;
}
// Rewrite 'throw new NullPointerException()' to 'throw null'.
- public void rewriteThrowNullPointerException(IRCode code) {
+ private void rewriteThrowNullPointerException(IRCode code) {
+ boolean hasChanged = false;
boolean shouldRemoveUnreachableBlocks = false;
for (BasicBlock block : code.blocks) {
InstructionListIterator it = block.listIterator(code);
@@ -64,7 +89,7 @@
if (appView
.dexItemFactory()
.objectsMethods
- .isRequireNonNullMethod(code.method().getReference())) {
+ .isRequireNonNullMethod(code.context().getReference())) {
continue;
}
@@ -126,6 +151,7 @@
valueIsNullTarget,
throwInstruction.getPosition());
shouldRemoveUnreachableBlocks = true;
+ hasChanged = true;
}
// Check for 'new-instance NullPointerException' with 2 users, not declaring a local and
@@ -172,6 +198,7 @@
// Replace them with 'const 0' and 'throw'.
it.add(nullPointer);
it.add(throwInstruction);
+ hasChanged = true;
}
}
}
@@ -186,13 +213,16 @@
new TypeAnalysis(appView).narrowing(affectedValues);
}
}
+ if (hasChanged) {
+ code.removeRedundantBlocks();
+ }
assert code.isConsistentSSA(appView);
}
// Find all instructions that always throw, split the block after each such instruction and follow
// it with a block throwing a null value (which should result in NPE). Note that this throw is not
// expected to be ever reached, but is intended to satisfy verifier.
- public void optimizeAlwaysThrowingInstructions(IRCode code) {
+ private void optimizeAlwaysThrowingInstructions(IRCode code) {
Set<Value> affectedValues = Sets.newIdentityHashSet();
Set<BasicBlock> blocksToRemove = Sets.newIdentityHashSet();
ListIterator<BasicBlock> blockIterator = code.listIterator();
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/result/CodeRewriterResult.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/result/CodeRewriterResult.java
index 68d5c0d..1af288a 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/result/CodeRewriterResult.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/result/CodeRewriterResult.java
@@ -5,6 +5,7 @@
package com.android.tools.r8.ir.conversion.passes.result;
import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.ir.conversion.passes.BranchSimplifier.ControlFlowSimplificationResult;
public interface CodeRewriterResult {
@@ -37,4 +38,8 @@
}
boolean hasChanged();
+
+ default ControlFlowSimplificationResult asControlFlowSimplificationResult() {
+ throw new Unreachable("Not a control flow simplification result.");
+ }
}
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 e696879..19f053f 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
@@ -21,11 +21,9 @@
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.code.Assume;
import com.android.tools.r8.ir.code.BasicBlock;
-import com.android.tools.r8.ir.code.ConstNumber;
import com.android.tools.r8.ir.code.ConstString;
import com.android.tools.r8.ir.code.DebugLocalWrite;
import com.android.tools.r8.ir.code.DebugLocalsChange;
-import com.android.tools.r8.ir.code.DominatorTree;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.If;
import com.android.tools.r8.ir.code.IfType;
@@ -40,7 +38,6 @@
import com.android.tools.r8.ir.code.StaticGet;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator;
-import com.android.tools.r8.utils.LazyBox;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.Sets;
import com.google.common.collect.Streams;
@@ -51,11 +48,7 @@
import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
import it.unimi.dsi.fastutil.ints.IntOpenHashSet;
import it.unimi.dsi.fastutil.ints.IntSet;
-import it.unimi.dsi.fastutil.longs.Long2ReferenceMap;
-import it.unimi.dsi.fastutil.longs.Long2ReferenceOpenHashMap;
-import java.util.ArrayList;
import java.util.List;
-import java.util.ListIterator;
import java.util.Set;
public class CodeRewriter {
@@ -210,242 +203,6 @@
}
/**
- * This optimization exploits that we can sometimes learn the constant value of an SSA value that
- * flows into an if-eq of if-neq instruction.
- *
- * <p>Consider the following example:
- *
- * <pre>
- * 1. if (obj != null) {
- * 2. return doStuff();
- * 3. }
- * 4. return null;
- * </pre>
- *
- * <p>Since we know that `obj` is null in all blocks that are dominated by the false-target of the
- * if-instruction in line 1, we can safely replace the null-constant in line 4 by `obj`, and
- * thereby save a const-number instruction.
- */
- public void redundantConstNumberRemoval(IRCode code) {
- if (appView.options().canHaveDalvikIntUsedAsNonIntPrimitiveTypeBug()
- && !appView.options().testing.forceRedundantConstNumberRemoval) {
- // See also b/124152497.
- return;
- }
-
- if (!code.metadata().mayHaveConstNumber()) {
- return;
- }
-
- LazyBox<Long2ReferenceMap<List<ConstNumber>>> constantsByValue =
- new LazyBox<>(() -> getConstantsByValue(code));
- LazyBox<DominatorTree> dominatorTree = new LazyBox<>(() -> new DominatorTree(code));
-
- boolean changed = false;
- for (BasicBlock block : code.blocks) {
- Instruction lastInstruction = block.getInstructions().getLast();
- if (!lastInstruction.isIf()) {
- continue;
- }
-
- If ifInstruction = lastInstruction.asIf();
- IfType type = ifInstruction.getType();
-
- Value lhs = ifInstruction.inValues().get(0);
- Value rhs = !ifInstruction.isZeroTest() ? ifInstruction.inValues().get(1) : null;
-
- if (!ifInstruction.isZeroTest() && !lhs.isConstNumber() && !rhs.isConstNumber()) {
- // We can only conclude anything from an if-instruction if it is a zero-test or if one of
- // the two operands is a constant.
- continue;
- }
-
- // If the type is neither EQ nor NE, we cannot conclude anything about any of the in-values
- // of the if-instruction from the outcome of the if-instruction.
- if (type != IfType.EQ && type != IfType.NE) {
- continue;
- }
-
- BasicBlock trueTarget, falseTarget;
- if (type == IfType.EQ) {
- trueTarget = ifInstruction.getTrueTarget();
- falseTarget = ifInstruction.fallthroughBlock();
- } else {
- falseTarget = ifInstruction.getTrueTarget();
- trueTarget = ifInstruction.fallthroughBlock();
- }
-
- if (ifInstruction.isZeroTest()) {
- changed |=
- replaceDominatedConstNumbers(0, lhs, trueTarget, constantsByValue, code, dominatorTree);
- if (lhs.knownToBeBoolean()) {
- changed |=
- replaceDominatedConstNumbers(
- 1, lhs, falseTarget, constantsByValue, code, dominatorTree);
- }
- } else {
- assert rhs != null;
- if (lhs.isConstNumber()) {
- ConstNumber lhsAsNumber = lhs.getConstInstruction().asConstNumber();
- changed |=
- replaceDominatedConstNumbers(
- lhsAsNumber.getRawValue(),
- rhs,
- trueTarget,
- constantsByValue,
- code,
- dominatorTree);
- if (lhs.knownToBeBoolean() && rhs.knownToBeBoolean()) {
- changed |=
- replaceDominatedConstNumbers(
- negateBoolean(lhsAsNumber),
- rhs,
- falseTarget,
- constantsByValue,
- code,
- dominatorTree);
- }
- } else {
- assert rhs.isConstNumber();
- ConstNumber rhsAsNumber = rhs.getConstInstruction().asConstNumber();
- changed |=
- replaceDominatedConstNumbers(
- rhsAsNumber.getRawValue(),
- lhs,
- trueTarget,
- constantsByValue,
- code,
- dominatorTree);
- if (lhs.knownToBeBoolean() && rhs.knownToBeBoolean()) {
- changed |=
- replaceDominatedConstNumbers(
- negateBoolean(rhsAsNumber),
- lhs,
- falseTarget,
- constantsByValue,
- code,
- dominatorTree);
- }
- }
- }
-
- if (constantsByValue.computeIfAbsent().isEmpty()) {
- break;
- }
- }
-
- if (changed) {
- code.removeAllDeadAndTrivialPhis();
- }
- assert code.isConsistentSSA(appView);
- }
-
- private static Long2ReferenceMap<List<ConstNumber>> getConstantsByValue(IRCode code) {
- // A map from the raw value of constants in `code` to the const number instructions that define
- // the given raw value (irrespective of the type of the raw value).
- Long2ReferenceMap<List<ConstNumber>> constantsByValue = new Long2ReferenceOpenHashMap<>();
-
- // Initialize `constantsByValue`.
- for (Instruction instruction : code.instructions()) {
- if (instruction.isConstNumber()) {
- ConstNumber constNumber = instruction.asConstNumber();
- if (constNumber.outValue().hasLocalInfo()) {
- // Not necessarily constant, because it could be changed in the debugger.
- continue;
- }
- long rawValue = constNumber.getRawValue();
- if (constantsByValue.containsKey(rawValue)) {
- constantsByValue.get(rawValue).add(constNumber);
- } else {
- List<ConstNumber> list = new ArrayList<>();
- list.add(constNumber);
- constantsByValue.put(rawValue, list);
- }
- }
- }
- return constantsByValue;
- }
-
- private static int negateBoolean(ConstNumber number) {
- assert number.outValue().knownToBeBoolean();
- return number.getRawValue() == 0 ? 1 : 0;
- }
-
- private boolean replaceDominatedConstNumbers(
- long withValue,
- Value newValue,
- BasicBlock dominator,
- LazyBox<Long2ReferenceMap<List<ConstNumber>>> constantsByValueSupplier,
- IRCode code,
- LazyBox<DominatorTree> dominatorTree) {
- if (newValue.hasLocalInfo()) {
- // We cannot replace a constant with a value that has local info, because that could change
- // debugging behavior.
- return false;
- }
-
- Long2ReferenceMap<List<ConstNumber>> constantsByValue =
- constantsByValueSupplier.computeIfAbsent();
- List<ConstNumber> constantsWithValue = constantsByValue.get(withValue);
- if (constantsWithValue == null || constantsWithValue.isEmpty()) {
- return false;
- }
-
- boolean changed = false;
-
- ListIterator<ConstNumber> constantWithValueIterator = constantsWithValue.listIterator();
- while (constantWithValueIterator.hasNext()) {
- ConstNumber constNumber = constantWithValueIterator.next();
- Value value = constNumber.outValue();
- assert !value.hasLocalInfo();
- assert constNumber.getRawValue() == withValue;
-
- BasicBlock block = constNumber.getBlock();
-
- // If the following condition does not hold, then the if-instruction does not dominate the
- // block containing the constant, although the true or false target does.
- if (block == dominator && block.getPredecessors().size() != 1) {
- // This should generally not happen, but it is possible to write bytecode where it does.
- assert false;
- continue;
- }
-
- if (value.knownToBeBoolean() && !newValue.knownToBeBoolean()) {
- // We cannot replace a boolean by a none-boolean since that can lead to verification
- // errors. For example, the following code fails with "register v1 has type Imprecise
- // Constant: 127 but expected Boolean return-1nr".
- //
- // public boolean convertIntToBoolean(int v1) {
- // const/4 v0, 0x1
- // if-eq v1, v0, :eq_true
- // const/4 v1, 0x0
- // :eq_true
- // return v1
- // }
- continue;
- }
-
- if (dominatorTree.computeIfAbsent().dominatedBy(block, dominator)) {
- if (newValue.getType().lessThanOrEqual(value.getType(), appView)) {
- value.replaceUsers(newValue);
- block.listIterator(code, constNumber).removeOrReplaceByDebugLocalRead();
- constantWithValueIterator.remove();
- changed = true;
- } else if (value.getType().isNullType()) {
- // TODO(b/120257211): Need a mechanism to determine if `newValue` can be used at all of
- // the use sites of `value` without introducing a type error.
- }
- }
- }
-
- if (constantsWithValue.isEmpty()) {
- constantsByValue.remove(withValue);
- }
-
- return changed;
- }
-
- /**
* Remove moves that are not actually used by instructions in exiting paths. These moves can arise
* due to debug local info needing a particular value and the live-interval for it then moves it
* back into the properly assigned register. If the register is only used for debug purposes, it
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 e9b180c..94fabb7 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
@@ -60,11 +60,15 @@
removeDeadInstructions(worklist, code, block, valueIsDeadAnalysis);
removeDeadPhis(worklist, block, valueIsDeadAnalysis);
}
- } while (branchSimplifier.simplifyIf(code).anySimplifications()
+ } while (branchSimplifier
+ .simplifyIf(code)
+ .asControlFlowSimplificationResult()
+ .anySimplifications()
|| removeUnneededCatchHandlers(code));
code.removeRedundantBlocks();
assert code.isConsistentSSA(appView);
+ assert verifyNoDeadCode(code);
timing.end();
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java
index d3d2a08..b46d0a5 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java
@@ -252,7 +252,7 @@
new TrivialCheckCastAndInstanceOfRemover(appView)
.run(code, methodProcessor, methodProcessingContext, Timing.empty());
// If a method was inlined we may be able to prune additional branches.
- new BranchSimplifier(appView).simplifyBranches(code);
+ new BranchSimplifier(appView).run(code, Timing.empty());
// If a method was inlined we may see more trivial computation/conversion of String.
boolean isDebugMode =
appView.options().debug || method.getOrComputeReachabilitySensitive(appView);
diff --git a/src/main/java/com/android/tools/r8/shaking/EnqueuerDeferredTracingImpl.java b/src/main/java/com/android/tools/r8/shaking/EnqueuerDeferredTracingImpl.java
index 1c0d3de..f7cf0b5 100644
--- a/src/main/java/com/android/tools/r8/shaking/EnqueuerDeferredTracingImpl.java
+++ b/src/main/java/com/android/tools/r8/shaking/EnqueuerDeferredTracingImpl.java
@@ -270,7 +270,7 @@
rewriter.rewriteCode(ir, initializedClassesWithContexts, prunedFields);
// Run dead code elimination.
- new ThrowCatchOptimizer(appView).optimizeAlwaysThrowingInstructions(ir);
+ new ThrowCatchOptimizer(appView).run(ir, Timing.empty());
rewriter.getDeadCodeRemover().run(ir, Timing.empty());
// Finalize to class files or dex.
