Merge commit 'c04eb1d97999bd1208d389ddab8534928305a141' into dev-release
diff --git a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
index 073cc8d..3d5f387 100644
--- a/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
+++ b/src/main/java/com/android/tools/r8/dex/ApplicationWriter.java
@@ -325,8 +325,7 @@
List<DexString> forcedStrings,
Timing timing)
throws ExecutionException {
- TimingMerger merger =
- timing.beginMerger("Write files", ThreadUtils.getNumberOfThreads(executorService));
+ TimingMerger merger = timing.beginMerger("Write files", executorService);
Collection<Timing> timings =
ThreadUtils.processItemsWithResults(
virtualFiles,
@@ -395,8 +394,7 @@
{
// Compute offsets and rewrite jumbo strings so that code offsets are fixed.
- TimingMerger merger =
- timing.beginMerger("Pre-write phase", ThreadUtils.getNumberOfThreads(executorService));
+ TimingMerger merger = timing.beginMerger("Pre-write phase", executorService);
Collection<Timing> timings =
rewriteJumboStringsAndComputeDebugRepresentation(
executorService, virtualFiles, lazyDexStrings);
diff --git a/src/main/java/com/android/tools/r8/dex/ApplicationWriterExperimental.java b/src/main/java/com/android/tools/r8/dex/ApplicationWriterExperimental.java
index 853d01e..8324c91 100644
--- a/src/main/java/com/android/tools/r8/dex/ApplicationWriterExperimental.java
+++ b/src/main/java/com/android/tools/r8/dex/ApplicationWriterExperimental.java
@@ -96,8 +96,7 @@
List<VirtualFile> virtualFiles,
List<DexString> forcedStrings,
Timing timing) {
- TimingMerger merger =
- timing.beginMerger("Write files", ThreadUtils.getNumberOfThreads(executorService));
+ TimingMerger merger = timing.beginMerger("Write files", executorService);
Collection<Timing> timings;
// TODO(b/249922554): Current limitations for the experimental flag.
assert globalsSyntheticsConsumer == null;
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index d72358a..9b3ea7c 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -833,7 +833,8 @@
.forEach(
(key, value) -> {
assert value == 1;
- assert value <= basicBlockNumberGenerator.peek();
+ assert key >= 0;
+ assert key <= basicBlockNumberGenerator.peek();
});
return true;
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Inc.java b/src/main/java/com/android/tools/r8/ir/code/Inc.java
index 72b2bf2..5d3a877 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Inc.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Inc.java
@@ -33,6 +33,10 @@
return Opcodes.INC;
}
+ public int getIncrement() {
+ return increment;
+ }
+
@Override
public <T> T accept(InstructionVisitor<T> visitor) {
return visitor.visit(this);
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
index 81f5c14..16fa00c 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/CfBuilder.java
@@ -52,7 +52,7 @@
import com.android.tools.r8.ir.code.UninitializedThisLocalRead;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.code.Xor;
-import com.android.tools.r8.ir.optimize.CodeRewriter;
+import com.android.tools.r8.ir.conversion.passes.TrivialGotosCollapser;
import com.android.tools.r8.ir.optimize.DeadCodeRemover;
import com.android.tools.r8.ir.optimize.PeepholeOptimizer;
import com.android.tools.r8.ir.optimize.PhiOptimizations;
@@ -193,10 +193,11 @@
loadStoreHelper.insertPhiMoves(registerAllocator);
timing.end();
+ TrivialGotosCollapser trivialGotosCollapser = new TrivialGotosCollapser(appView);
timing.begin("BasicBlock peephole optimizations");
if (code.getConversionOptions().isPeepholeOptimizationsEnabled()) {
for (int i = 0; i < PEEPHOLE_OPTIMIZATION_PASSES; i++) {
- CodeRewriter.collapseTrivialGotos(appView, code);
+ trivialGotosCollapser.run(code.context(), code, timing);
PeepholeOptimizer.removeIdenticalPredecessorBlocks(code, registerAllocator);
PeepholeOptimizer.shareIdenticalBlockSuffix(
code, registerAllocator, SUFFIX_SHARING_OVERHEAD);
@@ -206,7 +207,7 @@
timing.time("Rewrite Iinc patterns", this::rewriteIincPatterns);
- CodeRewriter.collapseTrivialGotos(appView, code);
+ trivialGotosCollapser.run(code.context(), code, timing);
timing.begin("Remove redundant debug positions");
DexBuilder.removeRedundantDebugPositions(code);
timing.end();
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
index cd7b5b9..1ddfeac 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/DexBuilder.java
@@ -63,7 +63,7 @@
import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.ir.code.Return;
import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.optimize.CodeRewriter;
+import com.android.tools.r8.ir.conversion.passes.TrivialGotosCollapser;
import com.android.tools.r8.ir.regalloc.RegisterAllocator;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.InternalOutputMode;
@@ -401,7 +401,7 @@
}
if (allMatch) {
currentBlock.removeInstruction(debugPosition);
- CodeRewriter.unlinkTrivialGotoBlock(currentBlock, exit.getTarget());
+ TrivialGotosCollapser.unlinkTrivialGotoBlock(currentBlock, exit.getTarget());
code.removeBlocks(Collections.singleton(currentBlock));
// Having removed the block at blockIndex, the previous block may now be a trivial
// fallthrough from an if/switch. Rewind to that point and retry. This avoids iterating to
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 7636cbd..55c6a06 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
@@ -27,10 +27,14 @@
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.conversion.passes.ArrayConstructionSimplifier;
import com.android.tools.r8.ir.conversion.passes.BinopRewriter;
+import com.android.tools.r8.ir.conversion.passes.BranchSimplifier;
import com.android.tools.r8.ir.conversion.passes.CommonSubexpressionElimination;
import com.android.tools.r8.ir.conversion.passes.ParentConstructorHoistingCodeRewriter;
import com.android.tools.r8.ir.conversion.passes.SplitBranch;
+import com.android.tools.r8.ir.conversion.passes.TrivialCheckCastAndInstanceOfRemover;
+import com.android.tools.r8.ir.conversion.passes.TrivialPhiSimplifier;
import com.android.tools.r8.ir.desugar.CfInstructionDesugaringCollection;
import com.android.tools.r8.ir.desugar.CovariantReturnTypeAnnotationTransformer;
import com.android.tools.r8.ir.optimize.AssertionErrorTwoArgsConstructorRewriter;
@@ -538,7 +542,7 @@
if (options.canHaveArtStringNewInitBug()) {
timing.begin("Check for new-init issue");
- CodeRewriter.ensureDirectStringNewToInit(code, appView.dexItemFactory());
+ TrivialPhiSimplifier.ensureDirectStringNewToInit(code, appView.dexItemFactory());
timing.end();
}
@@ -726,8 +730,8 @@
assert code.verifyTypes(appView);
timing.begin("Remove trivial type checks/casts");
- codeRewriter.removeTrivialCheckCastAndInstanceOfInstructions(
- code, context, methodProcessor, methodProcessingContext);
+ new TrivialCheckCastAndInstanceOfRemover(appView)
+ .run(code, context, methodProcessor, methodProcessingContext);
timing.end();
if (enumValueOptimizer != null) {
@@ -750,9 +754,7 @@
timing.end();
}
commonSubexpressionElimination.run(context, code, timing);
- timing.begin("Simplify arrays");
- codeRewriter.simplifyArrayConstruction(code);
- timing.end();
+ new ArrayConstructionSimplifier(appView).run(context, code, timing);
timing.begin("Rewrite move result");
codeRewriter.rewriteMoveResult(code);
timing.end();
@@ -771,10 +773,10 @@
codeRewriter.optimizeAlwaysThrowingInstructions(code);
timing.end();
timing.begin("Simplify control flow");
- if (codeRewriter.simplifyControlFlow(code)) {
+ if (new BranchSimplifier(appView).simplifyBranches(code)) {
timing.begin("Remove trivial type checks/casts");
- codeRewriter.removeTrivialCheckCastAndInstanceOfInstructions(
- code, context, methodProcessor, methodProcessingContext);
+ new TrivialCheckCastAndInstanceOfRemover(appView)
+ .run(code, context, methodProcessor, methodProcessingContext);
timing.end();
}
timing.end();
@@ -829,7 +831,6 @@
assert options.inlinerOptions().enableInlining && inliner != null;
classInliner.processMethodCode(
appView.withLiveness(),
- codeRewriter,
stringOptimizer,
enumValueOptimizer,
code.context(),
@@ -877,7 +878,7 @@
if (!options.isGeneratingClassFiles()) {
timing.begin("Canonicalize constants");
ConstantCanonicalizer constantCanonicalizer =
- new ConstantCanonicalizer(appView, codeRewriter, context, code);
+ new ConstantCanonicalizer(appView, context, code);
constantCanonicalizer.canonicalize();
timing.end();
previous = printMethod(code, "IR after constant canonicalization (SSA)", previous);
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRToDexFinalizer.java b/src/main/java/com/android/tools/r8/ir/conversion/IRToDexFinalizer.java
index 06f3da8..ddcd9ac 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRToDexFinalizer.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRToDexFinalizer.java
@@ -9,6 +9,7 @@
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.bytecodemetadata.BytecodeMetadataProvider;
import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.conversion.passes.TrivialGotosCollapser;
import com.android.tools.r8.ir.desugar.nest.D8NestBasedAccessDesugaring;
import com.android.tools.r8.ir.optimize.CodeRewriter;
import com.android.tools.r8.ir.optimize.DeadCodeRemover;
@@ -22,13 +23,10 @@
public class IRToDexFinalizer extends IRFinalizer<DexCode> {
private static final int PEEPHOLE_OPTIMIZATION_PASSES = 2;
-
- private final CodeRewriter codeRewriter;
private final InternalOptions options;
public IRToDexFinalizer(AppView<?> appView, DeadCodeRemover deadCodeRemover) {
super(appView, deadCodeRemover);
- this.codeRewriter = deadCodeRemover.getCodeRewriter();
this.options = appView.options();
}
@@ -44,7 +42,7 @@
// Workaround massive dex2oat memory use for self-recursive methods.
RuntimeWorkaroundCodeRewriter.workaroundDex2OatInliningIssue(appView, code);
// Workaround MAX_INT switch issue.
- RuntimeWorkaroundCodeRewriter.workaroundSwitchMaxIntBug(code, codeRewriter, options);
+ RuntimeWorkaroundCodeRewriter.workaroundSwitchMaxIntBug(code, appView);
RuntimeWorkaroundCodeRewriter.workaroundDex2OatLinkedListBug(code, options);
RuntimeWorkaroundCodeRewriter.workaroundForwardingInitializerBug(code, options);
RuntimeWorkaroundCodeRewriter.workaroundExceptionTargetingLoopHeaderBug(code, options);
@@ -62,17 +60,18 @@
LinearScanRegisterAllocator registerAllocator = new LinearScanRegisterAllocator(appView, code);
registerAllocator.allocateRegisters();
timing.end();
+ TrivialGotosCollapser trivialGotosCollapser = new TrivialGotosCollapser(appView);
if (code.getConversionOptions().isPeepholeOptimizationsEnabled()) {
timing.begin("Peephole optimize");
for (int i = 0; i < PEEPHOLE_OPTIMIZATION_PASSES; i++) {
- CodeRewriter.collapseTrivialGotos(appView, code);
+ trivialGotosCollapser.run(code.context(), code, timing);
PeepholeOptimizer.optimize(appView, code, registerAllocator);
}
timing.end();
}
timing.begin("Clean up");
CodeRewriter.removeUnneededMovesOnExitingPaths(code, registerAllocator);
- CodeRewriter.collapseTrivialGotos(appView, code);
+ trivialGotosCollapser.run(code.context(), code, timing);
timing.end();
return registerAllocator;
}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
index 1efe772..4c15125 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/LensCodeRewriter.java
@@ -104,7 +104,7 @@
import com.android.tools.r8.ir.code.UnusedArgument;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.code.ValueType;
-import com.android.tools.r8.ir.optimize.CodeRewriter;
+import com.android.tools.r8.ir.conversion.passes.TrivialPhiSimplifier;
import com.android.tools.r8.ir.optimize.enums.EnumUnboxer;
import com.android.tools.r8.optimize.MemberRebindingAnalysis;
import com.android.tools.r8.optimize.argumentpropagation.lenscoderewriter.NullCheckInserter;
@@ -231,7 +231,7 @@
if (unusedArgument.outValue().hasPhiUsers()) {
// See b/240282988: We can end up in situations where the second round of IR processing
// introduce phis for irreducible control flow, we need to resolve them.
- CodeRewriter.replaceUnusedArgumentTrivialPhis(unusedArgument);
+ TrivialPhiSimplifier.replaceUnusedArgumentTrivialPhis(unusedArgument);
}
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java b/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java
index fe3085a..ab073dd 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/PostMethodProcessor.java
@@ -178,8 +178,7 @@
ExecutorService executorService,
Timing timing)
throws ExecutionException {
- TimingMerger merger =
- timing.beginMerger("secondary-processor", ThreadUtils.getNumberOfThreads(executorService));
+ TimingMerger merger = timing.beginMerger("secondary-processor", executorService);
while (!waves.isEmpty()) {
wave = waves.removeFirst();
assert !wave.isEmpty();
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java b/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java
index 9da34d4..45450f9 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/PrimaryMethodProcessor.java
@@ -129,8 +129,7 @@
Timing timing,
ExecutorService executorService)
throws ExecutionException {
- TimingMerger merger =
- timing.beginMerger("primary-processor", ThreadUtils.getNumberOfThreads(executorService));
+ TimingMerger merger = timing.beginMerger("primary-processor", executorService);
while (!waves.isEmpty()) {
processorContext = appView.createProcessorContext();
wave = waves.removeFirst();
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/callgraph/CallSiteInformation.java b/src/main/java/com/android/tools/r8/ir/conversion/callgraph/CallSiteInformation.java
index c2e13af..e412ed7 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/callgraph/CallSiteInformation.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/callgraph/CallSiteInformation.java
@@ -13,6 +13,8 @@
import com.android.tools.r8.utils.classhierarchy.MethodOverridesCollector;
import com.android.tools.r8.utils.collections.ProgramMethodSet;
import com.google.common.collect.Sets;
+import java.util.IdentityHashMap;
+import java.util.Map;
import java.util.Set;
public abstract class CallSiteInformation {
@@ -23,6 +25,14 @@
* <p>For pinned methods (methods kept through Proguard keep rules) this will always answer <code>
* false</code>.
*/
+ public abstract boolean hasSingleCallSite(ProgramMethod method, ProgramMethod context);
+
+ /**
+ * Checks if the given method only has a single call without considering context.
+ *
+ * <p>For pinned methods (methods kept through Proguard keep rules) and methods that override a
+ * library method this always returns false.
+ */
public abstract boolean hasSingleCallSite(ProgramMethod method);
public abstract boolean isMultiCallerInlineCandidate(ProgramMethod method);
@@ -38,6 +48,11 @@
private static final EmptyCallSiteInformation EMPTY_INFO = new EmptyCallSiteInformation();
@Override
+ public boolean hasSingleCallSite(ProgramMethod method, ProgramMethod context) {
+ return false;
+ }
+
+ @Override
public boolean hasSingleCallSite(ProgramMethod method) {
return false;
}
@@ -55,7 +70,9 @@
static class CallGraphBasedCallSiteInformation extends CallSiteInformation {
- private final Set<DexMethod> singleCallerMethods = Sets.newIdentityHashSet();
+ // Single callers track their calling context to ensure that the predicate is stable after
+ // inlining of the caller.
+ private final Map<DexMethod, DexMethod> singleCallerMethods = new IdentityHashMap<>();
private final Set<DexMethod> multiCallerInlineCandidates = Sets.newIdentityHashSet();
CallGraphBasedCallSiteInformation(AppView<AppInfoWithLiveness> appView, CallGraph graph) {
@@ -94,7 +111,16 @@
int numberOfCallSites = node.getNumberOfCallSites();
if (numberOfCallSites == 1) {
- singleCallerMethods.add(reference);
+ Set<Node> callersWithDeterministicOrder = node.getCallersWithDeterministicOrder();
+ DexMethod caller = reference;
+ // We can have recursive methods where the recursive call is the only call site. We do
+ // not track callers for these.
+ if (!callersWithDeterministicOrder.isEmpty()) {
+ assert callersWithDeterministicOrder.size() == 1;
+ caller = callersWithDeterministicOrder.iterator().next().getMethod().getReference();
+ }
+ DexMethod existing = singleCallerMethods.put(reference, caller);
+ assert existing == null;
} else if (numberOfCallSites > 1) {
multiCallerInlineCandidates.add(reference);
}
@@ -102,14 +128,25 @@
}
/**
- * Checks if the given method only has a single call site.
+ * Checks if the given method only has a single call site with the given context.
+ *
+ * <p>For pinned methods (methods kept through Proguard keep rules) and methods that override a
+ * library method this always returns false.
+ */
+ @Override
+ public boolean hasSingleCallSite(ProgramMethod method, ProgramMethod context) {
+ return singleCallerMethods.get(method.getReference()) == context.getReference();
+ }
+
+ /**
+ * Checks if the given method only has a single call without considering context.
*
* <p>For pinned methods (methods kept through Proguard keep rules) and methods that override a
* library method this always returns false.
*/
@Override
public boolean hasSingleCallSite(ProgramMethod method) {
- return singleCallerMethods.contains(method.getReference());
+ return singleCallerMethods.containsKey(method.getReference());
}
/**
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/ArrayConstructionSimplifier.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/ArrayConstructionSimplifier.java
new file mode 100644
index 0000000..bc8f8fb
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/ArrayConstructionSimplifier.java
@@ -0,0 +1,474 @@
+// 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.graph.DexClass;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.analysis.type.ArrayTypeElement;
+import com.android.tools.r8.ir.analysis.type.TypeElement;
+import com.android.tools.r8.ir.code.ArrayPut;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeNewArray;
+import com.android.tools.r8.ir.code.LinearFlowInstructionListIterator;
+import com.android.tools.r8.ir.code.NewArrayEmpty;
+import com.android.tools.r8.ir.code.NewArrayFilledData;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.InternalOptions.RewriteArrayOptions;
+import com.android.tools.r8.utils.SetUtils;
+import com.android.tools.r8.utils.WorkList;
+import com.google.common.collect.Sets;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * Replace new-array followed by stores of constants to all entries with new-array and
+ * fill-array-data / filled-new-array.
+ *
+ * <p>The format of the new-array and its puts must be of the form:
+ *
+ * <pre>
+ * v0 <- new-array T vSize
+ * ...
+ * array-put v0 vValue1 vIndex1
+ * ...
+ * array-put v0 vValueN vIndexN
+ * </pre>
+ *
+ * <p>The flow between the array v0 and its puts must be linear with no other uses of v0 besides the
+ * array-put instructions, thus any no intermediate instruction (... above) must use v0 and also
+ * cannot have catch handlers that would transfer out control (those could then have uses of v0).
+ *
+ * <p>The allocation of the new-array can itself have catch handlers, in which case, those are to
+ * remain active on the translated code. Translated code can have two forms.
+ *
+ * <p>The first is using the original array allocation and filling in its data if it can be encoded:
+ *
+ * <pre>
+ * v0 <- new-array T vSize
+ * filled-array-data v0
+ * ...
+ * ...
+ * </pre>
+ *
+ * The data payload is encoded directly in the instruction so no dependencies are needed for filling
+ * the data array. Thus, the fill is inserted at the point of the allocation. If the allocation has
+ * catch handlers its block must be split and the handlers put on the fill instruction too. This is
+ * correct only because there are no exceptional transfers in (...) that could observe the early
+ * initialization of the data.
+ *
+ * <p>The second is using filled-new-array and has the form:
+ *
+ * <pre>
+ * ...
+ * ...
+ * v0 <- filled-new-array T vValue1 ... vValueN
+ * </pre>
+ *
+ * Here the correctness relies on no exceptional transfers in (...) that could observe the missing
+ * allocation of the array. The late allocation ensures that the values are available at allocation
+ * time. If the original allocation has catch handlers then the new allocation needs to link those
+ * too. In general that may require splitting the block twice so that the new allocation is the
+ * single throwing instruction in its block.
+ */
+public class ArrayConstructionSimplifier extends CodeRewriterPass<AppInfo> {
+
+ private final DexItemFactory dexItemFactory;
+
+ public ArrayConstructionSimplifier(AppView<?> appView) {
+ super(appView);
+ this.dexItemFactory = appView.dexItemFactory();
+ }
+
+ @Override
+ String getTimingId() {
+ return "ArrayConstructionSimplifier";
+ }
+
+ @Override
+ void rewriteCode(ProgramMethod method, IRCode code) {
+ WorkList<BasicBlock> worklist = WorkList.newIdentityWorkList(code.blocks);
+ while (worklist.hasNext()) {
+ BasicBlock block = worklist.next();
+ simplifyArrayConstructionBlock(block, worklist, code, appView.options());
+ }
+ }
+
+ @Override
+ boolean shouldRewriteCode(ProgramMethod method, IRCode code) {
+ return appView.options().isGeneratingDex();
+ }
+
+ private void simplifyArrayConstructionBlock(
+ BasicBlock block, WorkList<BasicBlock> worklist, IRCode code, InternalOptions options) {
+ RewriteArrayOptions rewriteOptions = options.rewriteArrayOptions();
+ InstructionListIterator it = block.listIterator(code);
+ while (it.hasNext()) {
+ FilledArrayCandidate candidate = computeFilledArrayCandidate(it.next(), rewriteOptions);
+ if (candidate == null) {
+ continue;
+ }
+ FilledArrayConversionInfo info =
+ computeConversionInfo(
+ candidate, new LinearFlowInstructionListIterator(code, block, it.nextIndex()));
+ if (info == null) {
+ continue;
+ }
+
+ Instruction instructionAfterCandidate = it.peekNext();
+ NewArrayEmpty newArrayEmpty = candidate.newArrayEmpty;
+ DexType arrayType = newArrayEmpty.type;
+ int size = candidate.size;
+ Set<Instruction> instructionsToRemove = SetUtils.newIdentityHashSet(size + 1);
+ if (candidate.useFilledNewArray()) {
+ assert newArrayEmpty.getLocalInfo() == null;
+ Instruction lastArrayPut = info.lastArrayPutIterator.peekPrevious();
+ Value invokeValue = code.createValue(newArrayEmpty.getOutType(), null);
+ InvokeNewArray invoke =
+ new InvokeNewArray(arrayType, invokeValue, Arrays.asList(info.values));
+ invoke.setPosition(lastArrayPut.getPosition());
+ for (Value value : newArrayEmpty.inValues()) {
+ value.removeUser(newArrayEmpty);
+ }
+ newArrayEmpty.outValue().replaceUsers(invokeValue);
+ instructionsToRemove.add(newArrayEmpty);
+
+ boolean originalAllocationPointHasHandlers = block.hasCatchHandlers();
+ boolean insertionPointHasHandlers = lastArrayPut.getBlock().hasCatchHandlers();
+
+ if (!insertionPointHasHandlers && !originalAllocationPointHasHandlers) {
+ info.lastArrayPutIterator.add(invoke);
+ } else {
+ BasicBlock insertionBlock = info.lastArrayPutIterator.split(code);
+ if (originalAllocationPointHasHandlers) {
+ if (!insertionBlock.isTrivialGoto()) {
+ BasicBlock blockAfterInsertion = insertionBlock.listIterator(code).split(code);
+ assert insertionBlock.isTrivialGoto();
+ worklist.addIfNotSeen(blockAfterInsertion);
+ }
+ insertionBlock.moveCatchHandlers(block);
+ } else {
+ worklist.addIfNotSeen(insertionBlock);
+ }
+ insertionBlock.listIterator(code).add(invoke);
+ }
+ } else {
+ assert candidate.useFilledArrayData();
+ int elementSize = arrayType.elementSizeForPrimitiveArrayType();
+ short[] contents = computeArrayFilledData(info.values, size, elementSize);
+ if (contents == null) {
+ continue;
+ }
+ // fill-array-data requires the new-array-empty instruction to remain, as it does not
+ // itself create an array.
+ NewArrayFilledData fillArray =
+ new NewArrayFilledData(newArrayEmpty.outValue(), elementSize, size, contents);
+ fillArray.setPosition(newArrayEmpty.getPosition());
+ BasicBlock newBlock =
+ it.addThrowingInstructionToPossiblyThrowingBlock(code, null, fillArray, options);
+ if (newBlock != null) {
+ worklist.addIfNotSeen(newBlock);
+ }
+ }
+
+ instructionsToRemove.addAll(info.arrayPutsToRemove);
+ Set<BasicBlock> visitedBlocks = Sets.newIdentityHashSet();
+ for (Instruction instruction : instructionsToRemove) {
+ BasicBlock ownerBlock = instruction.getBlock();
+ // If owner block is null, then the instruction has been removed already. We can't rely on
+ // just having the block pointer nulled, so the visited blocks guards reprocessing.
+ if (ownerBlock != null && visitedBlocks.add(ownerBlock)) {
+ InstructionListIterator removeIt = ownerBlock.listIterator(code);
+ while (removeIt.hasNext()) {
+ if (instructionsToRemove.contains(removeIt.next())) {
+ removeIt.removeOrReplaceByDebugLocalRead();
+ }
+ }
+ }
+ }
+
+ // The above has invalidated the block iterator so reset it and continue.
+ it = block.listIterator(code, instructionAfterCandidate);
+ }
+ }
+
+ private short[] computeArrayFilledData(Value[] values, int size, int elementSize) {
+ for (Value v : values) {
+ if (!v.isConstant()) {
+ return null;
+ }
+ }
+ if (elementSize == 1) {
+ short[] result = new short[(size + 1) / 2];
+ for (int i = 0; i < size; i += 2) {
+ short value =
+ (short) (values[i].getConstInstruction().asConstNumber().getIntValue() & 0xFF);
+ if (i + 1 < size) {
+ value |=
+ (short)
+ ((values[i + 1].getConstInstruction().asConstNumber().getIntValue() & 0xFF) << 8);
+ }
+ result[i / 2] = value;
+ }
+ return result;
+ }
+ assert elementSize == 2 || elementSize == 4 || elementSize == 8;
+ int shortsPerConstant = elementSize / 2;
+ short[] result = new short[size * shortsPerConstant];
+ for (int i = 0; i < size; i++) {
+ long value = values[i].getConstInstruction().asConstNumber().getRawValue();
+ for (int part = 0; part < shortsPerConstant; part++) {
+ result[i * shortsPerConstant + part] = (short) ((value >> (16 * part)) & 0xFFFFL);
+ }
+ }
+ return result;
+ }
+
+ private static class FilledArrayConversionInfo {
+
+ Value[] values;
+ List<ArrayPut> arrayPutsToRemove;
+ LinearFlowInstructionListIterator lastArrayPutIterator;
+
+ public FilledArrayConversionInfo(int size) {
+ values = new Value[size];
+ arrayPutsToRemove = new ArrayList<>(size);
+ }
+ }
+
+ private FilledArrayConversionInfo computeConversionInfo(
+ FilledArrayCandidate candidate, LinearFlowInstructionListIterator it) {
+ NewArrayEmpty newArrayEmpty = candidate.newArrayEmpty;
+ assert it.peekPrevious() == newArrayEmpty;
+ Value arrayValue = newArrayEmpty.outValue();
+ int size = candidate.size;
+
+ // aput-object allows any object for arrays of interfaces, but new-filled-array fails to verify
+ // if types require a cast.
+ // TODO(b/246971330): Check if adding a checked-cast would have the same observable result. E.g.
+ // if aput-object throws a ClassCastException if given an object that does not implement the
+ // desired interface, then we could add check-cast instructions for arguments we're not sure
+ // about.
+ DexType elementType = newArrayEmpty.type.toDimensionMinusOneType(dexItemFactory);
+ boolean needsTypeCheck =
+ !elementType.isPrimitiveType() && elementType != dexItemFactory.objectType;
+
+ FilledArrayConversionInfo info = new FilledArrayConversionInfo(size);
+ Value[] values = info.values;
+ int remaining = size;
+ Set<Instruction> users = newArrayEmpty.outValue().uniqueUsers();
+ while (it.hasNext()) {
+ Instruction instruction = it.next();
+ BasicBlock block = instruction.getBlock();
+ // If we encounter an instruction that can throw an exception we need to bail out of the
+ // optimization so that we do not transform half-initialized arrays into fully initialized
+ // arrays on exceptional edges. If the block has no handlers it is not observable so
+ // we perform the rewriting.
+ if (block.hasCatchHandlers() && instruction.instructionInstanceCanThrow()) {
+ return null;
+ }
+ if (!users.contains(instruction)) {
+ // If any instruction can transfer control between the new-array and the last array put
+ // then it is not safe to move the new array to the point of the last put.
+ if (block.hasCatchHandlers() && instruction.instructionTypeCanThrow()) {
+ return null;
+ }
+ continue;
+ }
+ ArrayPut arrayPut = instruction.asArrayPut();
+ // If the initialization sequence is broken by another use we cannot use a fill-array-data
+ // instruction.
+ if (arrayPut == null || arrayPut.array() != arrayValue) {
+ return null;
+ }
+ if (!arrayPut.index().isConstNumber()) {
+ return null;
+ }
+ if (arrayPut.instructionInstanceCanThrow()) {
+ assert false;
+ return null;
+ }
+ int index = arrayPut.index().getConstInstruction().asConstNumber().getIntValue();
+ if (index < 0 || index >= values.length) {
+ return null;
+ }
+ if (values[index] != null) {
+ return null;
+ }
+ Value value = arrayPut.value();
+ if (needsTypeCheck && !value.isAlwaysNull(appView)) {
+ DexType valueDexType = value.getType().asReferenceType().toDexType(dexItemFactory);
+ if (elementType.isArrayType()) {
+ if (elementType != valueDexType) {
+ return null;
+ }
+ } else if (valueDexType.isArrayType()) {
+ // isSubtype asserts for this case.
+ return null;
+ } else if (valueDexType.isNullValueType()) {
+ // Assume instructions can cause value.isAlwaysNull() == false while the DexType is null.
+ // TODO(b/246971330): Figure out how to write a test in SimplifyArrayConstructionTest
+ // that hits this case.
+ } else {
+ // TODO(b/246971330): When in d8 mode, we might still be able to see if this is true for
+ // library types (which this helper does not do).
+ if (appView.isSubtype(valueDexType, elementType).isPossiblyFalse()) {
+ return null;
+ }
+ }
+ }
+ info.arrayPutsToRemove.add(arrayPut);
+ values[index] = value;
+ --remaining;
+ if (remaining == 0) {
+ info.lastArrayPutIterator = it;
+ return info;
+ }
+ }
+ return null;
+ }
+
+ private static class FilledArrayCandidate {
+
+ final NewArrayEmpty newArrayEmpty;
+ final int size;
+ final boolean encodeAsFilledNewArray;
+
+ public FilledArrayCandidate(
+ NewArrayEmpty newArrayEmpty, int size, boolean encodeAsFilledNewArray) {
+ assert size > 0;
+ this.newArrayEmpty = newArrayEmpty;
+ this.size = size;
+ this.encodeAsFilledNewArray = encodeAsFilledNewArray;
+ }
+
+ public boolean useFilledNewArray() {
+ return encodeAsFilledNewArray;
+ }
+
+ public boolean useFilledArrayData() {
+ return !useFilledNewArray();
+ }
+ }
+
+ private FilledArrayCandidate computeFilledArrayCandidate(
+ Instruction instruction, RewriteArrayOptions options) {
+ NewArrayEmpty newArrayEmpty = instruction.asNewArrayEmpty();
+ if (newArrayEmpty == null) {
+ return null;
+ }
+ if (instruction.getLocalInfo() != null) {
+ return null;
+ }
+ if (!newArrayEmpty.size().isConstant()) {
+ return null;
+ }
+ int size = newArrayEmpty.size().getConstInstruction().asConstNumber().getIntValue();
+ if (!options.isPotentialSize(size)) {
+ return null;
+ }
+ DexType arrayType = newArrayEmpty.type;
+ boolean encodeAsFilledNewArray = canUseFilledNewArray(arrayType, size, options);
+ if (!encodeAsFilledNewArray && !canUseFilledArrayData(arrayType, size, options)) {
+ return null;
+ }
+ // Check that all arguments to the array is the array type or that the array is type Object[].
+ if (!options.canUseSubTypesInFilledNewArray()
+ && arrayType != dexItemFactory.objectArrayType
+ && !arrayType.isPrimitiveArrayType()) {
+ DexType elementType = arrayType.toArrayElementType(dexItemFactory);
+ for (Instruction uniqueUser : newArrayEmpty.outValue().uniqueUsers()) {
+ if (uniqueUser.isArrayPut()
+ && uniqueUser.asArrayPut().array() == newArrayEmpty.outValue()
+ && !checkTypeOfArrayPut(uniqueUser.asArrayPut(), elementType)) {
+ return null;
+ }
+ }
+ }
+ return new FilledArrayCandidate(newArrayEmpty, size, encodeAsFilledNewArray);
+ }
+
+ private boolean checkTypeOfArrayPut(ArrayPut arrayPut, DexType elementType) {
+ TypeElement valueType = arrayPut.value().getType();
+ if (!valueType.isPrimitiveType() && elementType == dexItemFactory.objectType) {
+ return true;
+ }
+ if (valueType.isNullType() && !elementType.isPrimitiveType()) {
+ return true;
+ }
+ if (elementType.isArrayType()) {
+ if (valueType.isNullType()) {
+ return true;
+ }
+ ArrayTypeElement arrayTypeElement = valueType.asArrayType();
+ if (arrayTypeElement == null
+ || arrayTypeElement.getNesting() != elementType.getNumberOfLeadingSquareBrackets()) {
+ return false;
+ }
+ valueType = arrayTypeElement.getBaseType();
+ elementType = elementType.toBaseType(dexItemFactory);
+ }
+ assert !valueType.isArrayType();
+ assert !elementType.isArrayType();
+ if (valueType.isPrimitiveType() && !elementType.isPrimitiveType()) {
+ return false;
+ }
+ if (valueType.isPrimitiveType()) {
+ return true;
+ }
+ DexClass clazz = appView.definitionFor(elementType);
+ if (clazz == null) {
+ return false;
+ }
+ return clazz.isInterface() || valueType.isClassType(elementType);
+ }
+
+ private boolean canUseFilledNewArray(DexType arrayType, int size, RewriteArrayOptions options) {
+ if (size < options.minSizeForFilledNewArray) {
+ return false;
+ }
+ // filled-new-array is implemented only for int[] and Object[].
+ // For int[], using filled-new-array is usually smaller than filled-array-data.
+ // filled-new-array supports up to 5 registers before it's filled-new-array/range.
+ if (!arrayType.isPrimitiveArrayType()) {
+ if (size > options.maxSizeForFilledNewArrayOfReferences) {
+ return false;
+ }
+ if (arrayType == dexItemFactory.stringArrayType) {
+ return options.canUseFilledNewArrayOfStrings();
+ }
+ if (!options.canUseFilledNewArrayOfNonStringObjects()) {
+ return false;
+ }
+ if (!options.canUseFilledNewArrayOfArrays()
+ && arrayType.getNumberOfLeadingSquareBrackets() > 1) {
+ return false;
+ }
+ return true;
+ }
+ if (arrayType == dexItemFactory.intArrayType) {
+ return size <= options.maxSizeForFilledNewArrayOfInts;
+ }
+ return false;
+ }
+
+ private boolean canUseFilledArrayData(DexType arrayType, int size, RewriteArrayOptions options) {
+ // If there is only one element it is typically smaller to generate the array put
+ // instruction instead of fill array data.
+ if (size < options.minSizeForFilledArrayData || size > options.maxSizeForFilledArrayData) {
+ return false;
+ }
+ return arrayType.isPrimitiveArrayType();
+ }
+}
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
new file mode 100644
index 0000000..199df62
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/BranchSimplifier.java
@@ -0,0 +1,1231 @@
+// 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.AppView;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexEncodedField;
+import com.android.tools.r8.graph.FieldResolutionResult.SingleProgramFieldResolutionResult;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.horizontalclassmerging.HorizontalClassMergerUtils;
+import com.android.tools.r8.ir.analysis.equivalence.BasicBlockBehavioralSubsumption;
+import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
+import com.android.tools.r8.ir.analysis.value.AbstractValue;
+import com.android.tools.r8.ir.analysis.value.ConstantOrNonConstantNumberValue;
+import com.android.tools.r8.ir.analysis.value.SingleConstClassValue;
+import com.android.tools.r8.ir.analysis.value.SingleFieldValue;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.ConstNumber;
+import com.android.tools.r8.ir.code.Goto;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.IRMetadata;
+import com.android.tools.r8.ir.code.If;
+import com.android.tools.r8.ir.code.IfType;
+import com.android.tools.r8.ir.code.InstanceGet;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionIterator;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.IntSwitch;
+import com.android.tools.r8.ir.code.NumericType;
+import com.android.tools.r8.ir.code.Phi;
+import com.android.tools.r8.ir.code.Position;
+import com.android.tools.r8.ir.code.Switch;
+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.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;
+import com.google.common.collect.ImmutableSet;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
+import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
+import it.unimi.dsi.fastutil.ints.IntArrayList;
+import it.unimi.dsi.fastutil.ints.IntIterator;
+import it.unimi.dsi.fastutil.ints.IntList;
+import it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.PriorityQueue;
+import java.util.Set;
+
+public class BranchSimplifier {
+
+ private final AppView<?> appView;
+ private final InternalOptions options;
+
+ public BranchSimplifier(AppView<?> appView) {
+ this.appView = appView;
+ this.options = appView.options();
+ }
+
+ public boolean simplifyBranches(IRCode code) {
+ boolean anyAffectedValues = rewriteSwitch(code);
+ anyAffectedValues |= simplifyIf(code).anyAffectedValues();
+ return anyAffectedValues;
+ }
+
+ public ControlFlowSimplificationResult simplifyIf(IRCode code) {
+ BasicBlockBehavioralSubsumption behavioralSubsumption =
+ new BasicBlockBehavioralSubsumption(appView, code);
+ boolean simplified = false;
+ for (BasicBlock block : code.blocks) {
+ // Skip removed (= unreachable) blocks.
+ if (block.getNumber() != 0 && block.getPredecessors().isEmpty()) {
+ continue;
+ }
+ if (block.exit().isIf()) {
+ flipIfBranchesIfNeeded(code, block);
+ if (rewriteIfWithConstZero(code, block)) {
+ simplified = true;
+ }
+
+ if (simplifyKnownBooleanCondition(code, block)) {
+ simplified = true;
+ if (!block.exit().isIf()) {
+ continue;
+ }
+ }
+
+ // Simplify if conditions when possible.
+ If theIf = block.exit().asIf();
+ if (theIf.isZeroTest()) {
+ if (simplifyIfZeroTest(code, block, theIf)) {
+ simplified = true;
+ continue;
+ }
+ } else {
+ if (simplifyNonIfZeroTest(code, block, theIf)) {
+ simplified = true;
+ continue;
+ }
+ }
+
+ // Unable to determine which branch will be taken. Check if the true target can safely be
+ // rewritten to the false target.
+ if (behavioralSubsumption.isSubsumedBy(
+ theIf.inValues().get(0), theIf.getTrueTarget(), theIf.fallthroughBlock())) {
+ simplifyIfWithKnownCondition(code, block, theIf, theIf.fallthroughBlock());
+ simplified = true;
+ }
+ }
+ }
+ Set<Value> affectedValues = code.removeUnreachableBlocks();
+ if (!affectedValues.isEmpty()) {
+ new TypeAnalysis(appView).narrowing(affectedValues);
+ }
+ assert code.isConsistentSSA(appView);
+ return new ControlFlowSimplificationResult(!affectedValues.isEmpty(), simplified);
+ }
+
+ public static class ControlFlowSimplificationResult {
+
+ private final boolean anyAffectedValues;
+ private final boolean anySimplifications;
+
+ private ControlFlowSimplificationResult(boolean anyAffectedValues, boolean anySimplifications) {
+ assert !anyAffectedValues || anySimplifications;
+ this.anyAffectedValues = anyAffectedValues;
+ this.anySimplifications = anySimplifications;
+ }
+
+ public boolean anyAffectedValues() {
+ return anyAffectedValues;
+ }
+
+ public boolean anySimplifications() {
+ return anySimplifications;
+ }
+ }
+
+ private boolean simplifyIfZeroTest(IRCode code, BasicBlock block, If theIf) {
+ Value lhs = theIf.lhs();
+ Value lhsRoot = lhs.getAliasedValue();
+ if (lhsRoot.isConstNumber()) {
+ ConstNumber cond = lhsRoot.getConstInstruction().asConstNumber();
+ BasicBlock target = theIf.targetFromCondition(cond);
+ simplifyIfWithKnownCondition(code, block, theIf, target);
+ return true;
+ }
+
+ if (theIf.isNullTest()) {
+ assert theIf.getType() == IfType.EQ || theIf.getType() == IfType.NE;
+
+ if (lhs.isAlwaysNull(appView)) {
+ simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromNullObject());
+ return true;
+ }
+
+ if (lhs.isNeverNull()) {
+ simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromNonNullObject());
+ return true;
+ }
+ }
+
+ if (theIf.getType() == IfType.EQ || theIf.getType() == IfType.NE) {
+ AbstractValue lhsAbstractValue = lhs.getAbstractValue(appView, code.context());
+ if (lhsAbstractValue.isConstantOrNonConstantNumberValue()
+ && !lhsAbstractValue.asConstantOrNonConstantNumberValue().containsInt(0)) {
+ // Value doesn't contain zero at all.
+ simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromCondition(1));
+ return true;
+ }
+ }
+
+ if (lhs.hasValueRange()) {
+ LongInterval interval = lhs.getValueRange();
+ if (!interval.containsValue(0)) {
+ // Interval doesn't contain zero at all.
+ int sign = Long.signum(interval.getMin());
+ simplifyIfWithKnownCondition(code, block, theIf, sign);
+ return true;
+ }
+
+ // Interval contains zero.
+ switch (theIf.getType()) {
+ case GE:
+ case LT:
+ // [a, b] >= 0 is always true if a >= 0.
+ // [a, b] < 0 is always false if a >= 0.
+ // In both cases a zero condition takes the right branch.
+ if (interval.getMin() == 0) {
+ simplifyIfWithKnownCondition(code, block, theIf, 0);
+ return true;
+ }
+ break;
+
+ case LE:
+ case GT:
+ // [a, b] <= 0 is always true if b <= 0.
+ // [a, b] > 0 is always false if b <= 0.
+ // In both cases a zero condition takes the right branch.
+ if (interval.getMax() == 0) {
+ simplifyIfWithKnownCondition(code, block, theIf, 0);
+ return true;
+ }
+ break;
+
+ case EQ:
+ case NE:
+ // Only a single element interval [0, 0] can be dealt with here.
+ // Such intervals should have been replaced by constants.
+ assert !interval.isSingleValue();
+ break;
+ }
+ }
+ return false;
+ }
+
+ private boolean simplifyNonIfZeroTest(IRCode code, BasicBlock block, If theIf) {
+ Value lhs = theIf.lhs();
+ Value lhsRoot = lhs.getAliasedValue();
+ Value rhs = theIf.rhs();
+ Value rhsRoot = rhs.getAliasedValue();
+ if (lhsRoot == rhsRoot) {
+ // Comparing the same value.
+ simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromCondition(0));
+ return true;
+ }
+
+ if (lhsRoot.isDefinedByInstructionSatisfying(Instruction::isCreatingInstanceOrArray)
+ && rhsRoot.isDefinedByInstructionSatisfying(Instruction::isCreatingInstanceOrArray)) {
+ // Comparing two newly created objects.
+ assert theIf.getType() == IfType.EQ || theIf.getType() == IfType.NE;
+ simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromCondition(1));
+ return true;
+ }
+
+ if (lhsRoot.isConstNumber() && rhsRoot.isConstNumber()) {
+ // Zero test with a constant of comparison between between two constants.
+ ConstNumber left = lhsRoot.getConstInstruction().asConstNumber();
+ ConstNumber right = rhsRoot.getConstInstruction().asConstNumber();
+ BasicBlock target = theIf.targetFromCondition(left, right);
+ simplifyIfWithKnownCondition(code, block, theIf, target);
+ return true;
+ }
+
+ if (theIf.getType() == IfType.EQ || theIf.getType() == IfType.NE) {
+ AbstractValue lhsAbstractValue = lhs.getAbstractValue(appView, code.context());
+ AbstractValue rhsAbstractValue = rhs.getAbstractValue(appView, code.context());
+ if (lhsAbstractValue.isConstantOrNonConstantNumberValue()
+ && rhsAbstractValue.isConstantOrNonConstantNumberValue()) {
+ ConstantOrNonConstantNumberValue lhsNumberValue =
+ lhsAbstractValue.asConstantOrNonConstantNumberValue();
+ ConstantOrNonConstantNumberValue rhsNumberValue =
+ rhsAbstractValue.asConstantOrNonConstantNumberValue();
+ if (!lhsNumberValue.mayOverlapWith(rhsNumberValue)) {
+ // No overlap.
+ simplifyIfWithKnownCondition(code, block, theIf, 1);
+ return true;
+ }
+ }
+ }
+
+ if (lhs.hasValueRange() && rhs.hasValueRange()) {
+ // Zero test with a value range, or comparison between between two values,
+ // each with a value ranges.
+ LongInterval leftRange = lhs.getValueRange();
+ LongInterval rightRange = rhs.getValueRange();
+ // Two overlapping ranges. Check for single point overlap.
+ if (!leftRange.overlapsWith(rightRange)) {
+ // No overlap.
+ int cond = Long.signum(leftRange.getMin() - rightRange.getMin());
+ simplifyIfWithKnownCondition(code, block, theIf, cond);
+ return true;
+ }
+
+ // The two intervals overlap. We can simplify if they overlap at the end points.
+ switch (theIf.getType()) {
+ case LT:
+ case GE:
+ // [a, b] < [c, d] is always false when a == d.
+ // [a, b] >= [c, d] is always true when a == d.
+ // In both cases 0 condition will choose the right branch.
+ if (leftRange.getMin() == rightRange.getMax()) {
+ simplifyIfWithKnownCondition(code, block, theIf, 0);
+ return true;
+ }
+ break;
+ case GT:
+ case LE:
+ // [a, b] > [c, d] is always false when b == c.
+ // [a, b] <= [c, d] is always true when b == c.
+ // In both cases 0 condition will choose the right branch.
+ if (leftRange.getMax() == rightRange.getMin()) {
+ simplifyIfWithKnownCondition(code, block, theIf, 0);
+ return true;
+ }
+ break;
+ case EQ:
+ case NE:
+ // Since there is overlap EQ and NE cannot be determined.
+ break;
+ }
+ }
+
+ if (theIf.getType() == IfType.EQ || theIf.getType() == IfType.NE) {
+ ProgramMethod context = code.context();
+ AbstractValue abstractValue = lhs.getAbstractValue(appView, context);
+ if (abstractValue.isSingleConstClassValue()) {
+ AbstractValue otherAbstractValue = rhs.getAbstractValue(appView, context);
+ if (otherAbstractValue.isSingleConstClassValue()) {
+ SingleConstClassValue singleConstClassValue = abstractValue.asSingleConstClassValue();
+ SingleConstClassValue otherSingleConstClassValue =
+ otherAbstractValue.asSingleConstClassValue();
+ simplifyIfWithKnownCondition(
+ code,
+ block,
+ theIf,
+ BooleanUtils.intValue(
+ singleConstClassValue.getType() != otherSingleConstClassValue.getType()));
+ return true;
+ }
+ return false;
+ }
+
+ if (abstractValue.isSingleFieldValue()) {
+ AbstractValue otherAbstractValue = rhs.getAbstractValue(appView, context);
+ if (otherAbstractValue.isSingleFieldValue()) {
+ SingleFieldValue singleFieldValue = abstractValue.asSingleFieldValue();
+ SingleFieldValue otherSingleFieldValue = otherAbstractValue.asSingleFieldValue();
+ if (singleFieldValue.getField() == otherSingleFieldValue.getField()) {
+ simplifyIfWithKnownCondition(code, block, theIf, 0);
+ return true;
+ }
+
+ DexClass holder = appView.definitionForHolder(singleFieldValue.getField());
+ DexEncodedField field = singleFieldValue.getField().lookupOnClass(holder);
+ if (field != null && field.isEnum()) {
+ DexClass otherHolder = appView.definitionForHolder(otherSingleFieldValue.getField());
+ DexEncodedField otherField =
+ otherSingleFieldValue.getField().lookupOnClass(otherHolder);
+ if (otherField != null && otherField.isEnum()) {
+ simplifyIfWithKnownCondition(code, block, theIf, 1);
+ return true;
+ }
+ }
+ }
+ }
+ }
+
+ return false;
+ }
+
+ private void simplifyIfWithKnownCondition(
+ IRCode code, BasicBlock block, If theIf, BasicBlock target) {
+ BasicBlock deadTarget =
+ target == theIf.getTrueTarget() ? theIf.fallthroughBlock() : theIf.getTrueTarget();
+ rewriteIfToGoto(code, block, theIf, target, deadTarget);
+ }
+
+ private void simplifyIfWithKnownCondition(IRCode code, BasicBlock block, If theIf, int cond) {
+ simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromCondition(cond));
+ }
+
+ /* Identify simple diamond shapes converting boolean true/false to 1/0. We consider the forms:
+ *
+ * (1)
+ *
+ * [dbg pos x] [dbg pos x]
+ * ifeqz booleanValue ifnez booleanValue
+ * / \ / \
+ * [dbg pos x][dbg pos x] [dbg pos x][dbg pos x]
+ * [const 0] [const 1] [const 1] [const 0]
+ * goto goto goto goto
+ * \ / \ /
+ * phi(0, 1) phi(1, 0)
+ *
+ * which can be replaced by a fallthrough and the phi value can be replaced
+ * with the boolean value itself.
+ *
+ * (2)
+ *
+ * [dbg pos x] [dbg pos x]
+ * ifeqz booleanValue ifnez booleanValue
+ * / \ / \
+ * [dbg pos x][dbg pos x] [dbg pos x][dbg pos x]
+ * [const 1] [const 0] [const 0] [const 1]
+ * goto goto goto goto
+ * \ / \ /
+ * phi(1, 0) phi(0, 1)
+ *
+ * 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, BasicBlock block) {
+ If theIf = block.exit().asIf();
+ Value testValue = theIf.inValues().get(0);
+ if (theIf.isZeroTest() && testValue.knownToBeBoolean()) {
+ BasicBlock trueBlock = theIf.getTrueTarget();
+ BasicBlock falseBlock = theIf.fallthroughBlock();
+ if (isBlockSupportedBySimplifyKnownBooleanCondition(trueBlock)
+ && isBlockSupportedBySimplifyKnownBooleanCondition(falseBlock)
+ && trueBlock.getSuccessors().get(0) == falseBlock.getSuccessors().get(0)) {
+ BasicBlock targetBlock = trueBlock.getSuccessors().get(0);
+ if (targetBlock.getPredecessors().size() == 2) {
+ int trueIndex = targetBlock.getPredecessors().indexOf(trueBlock);
+ int falseIndex = trueIndex == 0 ? 1 : 0;
+ int deadPhis = 0;
+ // Locate the phis that have the same value as the boolean and replace them
+ // by the boolean in all users.
+ for (Phi phi : targetBlock.getPhis()) {
+ Value trueValue = phi.getOperand(trueIndex);
+ Value falseValue = phi.getOperand(falseIndex);
+ if (trueValue.isConstNumber() && falseValue.isConstNumber()) {
+ ConstNumber trueNumber = trueValue.getConstInstruction().asConstNumber();
+ ConstNumber falseNumber = falseValue.getConstInstruction().asConstNumber();
+ if ((theIf.getType() == IfType.EQ
+ && trueNumber.isIntegerZero()
+ && falseNumber.isIntegerOne())
+ || (theIf.getType() == IfType.NE
+ && trueNumber.isIntegerOne()
+ && falseNumber.isIntegerZero())) {
+ phi.replaceUsers(testValue);
+ deadPhis++;
+ } else if ((theIf.getType() == IfType.NE
+ && trueNumber.isIntegerZero()
+ && falseNumber.isIntegerOne())
+ || (theIf.getType() == IfType.EQ
+ && trueNumber.isIntegerOne()
+ && falseNumber.isIntegerZero())) {
+ Value newOutValue = code.createValue(phi.getType(), phi.getLocalInfo());
+ ConstNumber cstToUse = trueNumber.isIntegerOne() ? trueNumber : falseNumber;
+ BasicBlock phiBlock = phi.getBlock();
+ Position phiPosition = phiBlock.getPosition();
+ int insertIndex = 0;
+ if (cstToUse.getBlock() == trueBlock || cstToUse.getBlock() == falseBlock) {
+ // The constant belongs to the block to remove, create a new one.
+ cstToUse = ConstNumber.copyOf(code, cstToUse);
+ cstToUse.setBlock(phiBlock);
+ cstToUse.setPosition(phiPosition);
+ phiBlock.getInstructions().add(insertIndex++, cstToUse);
+ }
+ phi.replaceUsers(newOutValue);
+ Instruction newInstruction =
+ Xor.create(NumericType.INT, newOutValue, testValue, cstToUse.outValue());
+ newInstruction.setBlock(phiBlock);
+ // The xor is replacing a phi so it does not have an actual position.
+ newInstruction.setPosition(phiPosition);
+ phiBlock.listIterator(code, insertIndex).add(newInstruction);
+ deadPhis++;
+ }
+ }
+ }
+ // 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(code, block, theIf, trueBlock, falseBlock);
+ return true;
+ }
+ return deadPhis > 0;
+ }
+ }
+ }
+ return false;
+ }
+
+ private boolean isBlockSupportedBySimplifyKnownBooleanCondition(BasicBlock b) {
+ if (b.isTrivialGoto()) {
+ return true;
+ }
+
+ int instructionSize = b.getInstructions().size();
+ if (b.exit().isGoto() && (instructionSize == 2 || instructionSize == 3)) {
+ Instruction constInstruction = b.getInstructions().get(instructionSize - 2);
+ if (constInstruction.isConstNumber()) {
+ if (!constInstruction.asConstNumber().isIntegerOne()
+ && !constInstruction.asConstNumber().isIntegerZero()) {
+ return false;
+ }
+ if (instructionSize == 2) {
+ return true;
+ }
+ Instruction firstInstruction = b.getInstructions().getFirst();
+ if (firstInstruction.isDebugPosition()) {
+ assert b.getPredecessors().size() == 1;
+ BasicBlock predecessorBlock = b.getPredecessors().get(0);
+ InstructionIterator it = predecessorBlock.iterator(predecessorBlock.exit());
+ Instruction previousPosition = null;
+ while (it.hasPrevious() && !(previousPosition = it.previous()).isDebugPosition()) {
+ // Intentionally empty.
+ }
+ if (previousPosition != null) {
+ return previousPosition.getPosition() == firstInstruction.getPosition();
+ }
+ }
+ }
+ }
+
+ return false;
+ }
+
+ private void rewriteIfToGoto(
+ IRCode code, BasicBlock block, If theIf, BasicBlock target, BasicBlock deadTarget) {
+ deadTarget.unlinkSinglePredecessorSiblingsAllowed();
+ assert theIf == block.exit();
+ block.replaceLastInstruction(new Goto(), code);
+ assert block.exit().isGoto();
+ assert block.exit().asGoto().getTarget() == target;
+ }
+
+ private boolean rewriteIfWithConstZero(IRCode code, BasicBlock block) {
+ If theIf = block.exit().asIf();
+ if (theIf.isZeroTest()) {
+ return false;
+ }
+
+ Value leftValue = theIf.lhs();
+ Value rightValue = theIf.rhs();
+ if (leftValue.isConstNumber() || rightValue.isConstNumber()) {
+ if (leftValue.isConstNumber()) {
+ if (leftValue.getConstInstruction().asConstNumber().isZero()) {
+ If ifz = new If(theIf.getType().forSwappedOperands(), rightValue);
+ block.replaceLastInstruction(ifz, code);
+ assert block.exit() == ifz;
+ return true;
+ }
+ } else if (rightValue.getConstInstruction().asConstNumber().isZero()) {
+ If ifz = new If(theIf.getType(), leftValue);
+ block.replaceLastInstruction(ifz, code);
+ assert block.exit() == ifz;
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ private boolean flipIfBranchesIfNeeded(IRCode code, BasicBlock block) {
+ If theIf = block.exit().asIf();
+ BasicBlock trueTarget = theIf.getTrueTarget();
+ BasicBlock fallthrough = theIf.fallthroughBlock();
+ assert trueTarget != fallthrough;
+
+ if (!fallthrough.isSimpleAlwaysThrowingPath() || trueTarget.isSimpleAlwaysThrowingPath()) {
+ return false;
+ }
+
+ // In case fall-through block always throws there is a good chance that it
+ // is created for error checks and 'trueTarget' represents most more common
+ // non-error case. Flipping the if in this case may result in faster code
+ // on older Android versions.
+ List<Value> inValues = theIf.inValues();
+ If newIf = new If(theIf.getType().inverted(), inValues);
+ block.replaceLastInstruction(newIf, code);
+ block.swapSuccessors(trueTarget, fallthrough);
+ return true;
+ }
+
+ private boolean rewriteSwitch(IRCode code) {
+ return rewriteSwitch(code, SwitchCaseAnalyzer.getInstance());
+ }
+
+ private boolean rewriteSwitch(IRCode code, SwitchCaseAnalyzer switchCaseAnalyzer) {
+ if (!options.isSwitchRewritingEnabled()) {
+ return false;
+ }
+ if (!code.metadata().mayHaveSwitch()) {
+ return false;
+ }
+ return rewriteSwitchFull(code, switchCaseAnalyzer);
+ }
+
+ private boolean rewriteSwitchFull(IRCode code, SwitchCaseAnalyzer switchCaseAnalyzer) {
+ boolean needToRemoveUnreachableBlocks = false;
+ ListIterator<BasicBlock> blocksIterator = code.listIterator();
+ while (blocksIterator.hasNext()) {
+ BasicBlock block = blocksIterator.next();
+ InstructionListIterator iterator = block.listIterator(code);
+ while (iterator.hasNext()) {
+ Instruction instruction = iterator.next();
+ if (instruction.isSwitch()) {
+ Switch theSwitch = instruction.asSwitch();
+ if (options.testing.enableDeadSwitchCaseElimination) {
+ SwitchCaseEliminator eliminator =
+ removeUnnecessarySwitchCases(code, theSwitch, iterator, switchCaseAnalyzer);
+ if (eliminator.mayHaveIntroducedUnreachableBlocks()) {
+ needToRemoveUnreachableBlocks = true;
+ }
+
+ iterator.previous();
+ instruction = iterator.next();
+ if (instruction.isGoto()) {
+ continue;
+ }
+
+ assert instruction.isSwitch();
+ theSwitch = instruction.asSwitch();
+ }
+ if (theSwitch.isIntSwitch()) {
+ rewriteIntSwitch(code, blocksIterator, block, iterator, theSwitch.asIntSwitch());
+ }
+ }
+ }
+ }
+
+ // Rewriting of switches introduces new branching structure. It relies on critical edges
+ // being split on the way in but does not maintain this property. We therefore split
+ // critical edges at exit.
+ code.splitCriticalEdges();
+
+ Set<Value> affectedValues =
+ needToRemoveUnreachableBlocks ? code.removeUnreachableBlocks() : ImmutableSet.of();
+ if (!affectedValues.isEmpty()) {
+ new TypeAnalysis(appView).narrowing(affectedValues);
+ }
+ assert code.isConsistentSSA(appView);
+ return !affectedValues.isEmpty();
+ }
+
+ public void rewriteSingleKeySwitchToIf(
+ IRCode code, BasicBlock block, InstructionListIterator iterator, IntSwitch theSwitch) {
+ // Rewrite the switch to an if.
+ int fallthroughBlockIndex = theSwitch.getFallthroughBlockIndex();
+ int caseBlockIndex = theSwitch.targetBlockIndices()[0];
+ if (fallthroughBlockIndex < caseBlockIndex) {
+ block.swapSuccessorsByIndex(fallthroughBlockIndex, caseBlockIndex);
+ }
+ If replacement;
+ if (theSwitch.isIntSwitch() && theSwitch.asIntSwitch().getFirstKey() == 0) {
+ replacement = new If(IfType.EQ, theSwitch.value());
+ } else {
+ Instruction labelConst = theSwitch.materializeFirstKey(appView, code);
+ labelConst.setPosition(theSwitch.getPosition());
+ iterator.previous();
+ iterator.add(labelConst);
+ Instruction dummy = iterator.next();
+ assert dummy == theSwitch;
+ replacement = new If(IfType.EQ, ImmutableList.of(theSwitch.value(), labelConst.outValue()));
+ }
+ iterator.replaceCurrentInstruction(replacement);
+ }
+
+ private void rewriteIntSwitch(
+ IRCode code,
+ ListIterator<BasicBlock> blockIterator,
+ BasicBlock block,
+ InstructionListIterator iterator,
+ IntSwitch theSwitch) {
+ if (disableSwitchToIfRewritingForClassIdComparisons(theSwitch)) {
+ return;
+ }
+
+ if (theSwitch.numberOfKeys() == 1) {
+ rewriteSingleKeySwitchToIf(code, block, iterator, theSwitch);
+ return;
+ }
+
+ // If there are more than 1 key, we use the following algorithm to find keys to combine.
+ // First, scan through the keys forward and combine each packed interval with the
+ // previous interval if it gives a net saving.
+ // Secondly, go through all created intervals and combine the ones without a saving into
+ // a single interval and keep a max number of packed switches.
+ // Finally, go through all intervals and check if the switch or part of the switch
+ // should be transformed to ifs.
+
+ // Phase 1: Combine packed intervals.
+ InternalOutputMode mode = options.getInternalOutputMode();
+ int[] keys = theSwitch.getKeys();
+ int maxNumberOfIfsOrSwitches = 10;
+ PriorityQueue<Interval> biggestPackedSavings =
+ new PriorityQueue<>((x, y) -> Long.compare(y.packedSavings(mode), x.packedSavings(mode)));
+ Set<Interval> biggestPackedSet = new HashSet<>();
+ List<Interval> intervals = new ArrayList<>();
+ int previousKey = keys[0];
+ IntList currentKeys = new IntArrayList();
+ currentKeys.add(previousKey);
+ Interval previousInterval = null;
+ for (int i = 1; i < keys.length; i++) {
+ int key = keys[i];
+ if (((long) key - (long) previousKey) > 1) {
+ Interval current = new Interval(currentKeys);
+ Interval added = combineOrAddInterval(intervals, previousInterval, current);
+ if (added != current && biggestPackedSet.contains(previousInterval)) {
+ biggestPackedSet.remove(previousInterval);
+ biggestPackedSavings.remove(previousInterval);
+ }
+ tryAddToBiggestSavings(
+ biggestPackedSet, biggestPackedSavings, added, maxNumberOfIfsOrSwitches);
+ previousInterval = added;
+ currentKeys = new IntArrayList();
+ }
+ currentKeys.add(key);
+ previousKey = key;
+ }
+ Interval current = new Interval(currentKeys);
+ Interval added = combineOrAddInterval(intervals, previousInterval, current);
+ if (added != current && biggestPackedSet.contains(previousInterval)) {
+ biggestPackedSet.remove(previousInterval);
+ biggestPackedSavings.remove(previousInterval);
+ }
+ tryAddToBiggestSavings(biggestPackedSet, biggestPackedSavings, added, maxNumberOfIfsOrSwitches);
+
+ // Phase 2: combine sparse intervals into a single bin.
+ // Check if we should save a space for a sparse switch, if so, remove the switch with
+ // the smallest savings.
+ if (biggestPackedSet.size() == maxNumberOfIfsOrSwitches
+ && maxNumberOfIfsOrSwitches < intervals.size()) {
+ biggestPackedSet.remove(biggestPackedSavings.poll());
+ }
+ Interval sparse = null;
+ List<Interval> newSwitches = new ArrayList<>(maxNumberOfIfsOrSwitches);
+ for (int i = 0; i < intervals.size(); i++) {
+ Interval interval = intervals.get(i);
+ if (biggestPackedSet.contains(interval)) {
+ newSwitches.add(interval);
+ } else if (sparse == null) {
+ sparse = interval;
+ newSwitches.add(sparse);
+ } else {
+ sparse.addInterval(interval);
+ }
+ }
+
+ // Phase 3: at this point we are guaranteed to have the biggest saving switches
+ // in newIntervals, potentially with a switch combining the remaining intervals.
+ // Now we check to see if we can create any if's to reduce size.
+ IntList outliers = new IntArrayList();
+ int outliersAsIfSize =
+ options.testing.enableSwitchToIfRewriting
+ ? findIfsForCandidates(newSwitches, theSwitch, outliers)
+ : 0;
+
+ long newSwitchesSize = 0;
+ List<IntList> newSwitchSequences = new ArrayList<>(newSwitches.size());
+ for (Interval interval : newSwitches) {
+ newSwitchesSize += interval.estimatedSize(mode);
+ newSwitchSequences.add(interval.keys);
+ }
+
+ long currentSize = IntSwitch.estimatedSize(mode, theSwitch.getKeys());
+ if (newSwitchesSize + outliersAsIfSize + codeUnitMargin() < currentSize) {
+ convertSwitchToSwitchAndIfs(
+ code, blockIterator, block, iterator, theSwitch, newSwitchSequences, outliers);
+ }
+ }
+
+ // TODO(b/181732463): We currently disable switch-to-if rewritings for switches on $r8$classId
+ // field values (from horizontal class merging. See bug for more details.
+ private boolean disableSwitchToIfRewritingForClassIdComparisons(IntSwitch theSwitch) {
+ Value switchValue = theSwitch.value().getAliasedValue();
+ if (!switchValue.isDefinedByInstructionSatisfying(Instruction::isInstanceGet)) {
+ return false;
+ }
+ AppInfoWithLiveness appInfo = appView.appInfoWithLiveness();
+ if (appInfo == null) {
+ return false;
+ }
+ InstanceGet instanceGet = switchValue.getDefinition().asInstanceGet();
+ SingleProgramFieldResolutionResult resolutionResult =
+ appInfo.resolveField(instanceGet.getField()).asSingleProgramFieldResolutionResult();
+ if (resolutionResult == null) {
+ return false;
+ }
+ DexEncodedField resolvedField = resolutionResult.getResolvedField();
+ return HorizontalClassMergerUtils.isClassIdField(appView, resolvedField);
+ }
+
+ private SwitchCaseEliminator removeUnnecessarySwitchCases(
+ IRCode code,
+ Switch theSwitch,
+ InstructionListIterator iterator,
+ SwitchCaseAnalyzer switchCaseAnalyzer) {
+ BasicBlock defaultTarget = theSwitch.fallthroughBlock();
+ SwitchCaseEliminator eliminator = new SwitchCaseEliminator(theSwitch, iterator);
+ BasicBlockBehavioralSubsumption behavioralSubsumption =
+ new BasicBlockBehavioralSubsumption(appView, code);
+
+ // Compute the set of switch cases that can be removed.
+ boolean hasSwitchCaseToDefaultRewrite = false;
+ AbstractValue switchAbstractValue = theSwitch.value().getAbstractValue(appView, code.context());
+ for (int i = 0; i < theSwitch.numberOfKeys(); i++) {
+ BasicBlock targetBlock = theSwitch.targetBlock(i);
+
+ if (switchCaseAnalyzer.switchCaseIsAlwaysHit(theSwitch, i)) {
+ eliminator.markSwitchCaseAsAlwaysHit(i);
+ break;
+ }
+
+ // This switch case can be removed if the behavior of the target block is equivalent to the
+ // behavior of the default block, or if the switch case is unreachable.
+ if (switchCaseAnalyzer.switchCaseIsUnreachable(theSwitch, switchAbstractValue, i)) {
+ eliminator.markSwitchCaseForRemoval(i);
+ } else if (behavioralSubsumption.isSubsumedBy(
+ theSwitch.value(), targetBlock, defaultTarget)) {
+ eliminator.markSwitchCaseForRemoval(i);
+ hasSwitchCaseToDefaultRewrite = true;
+ }
+ }
+
+ if (eliminator.isFallthroughLive()
+ && !hasSwitchCaseToDefaultRewrite
+ && switchCaseAnalyzer.switchFallthroughIsNeverHit(theSwitch, switchAbstractValue)) {
+ eliminator.markSwitchFallthroughAsNeverHit();
+ }
+
+ eliminator.optimize();
+ return eliminator;
+ }
+
+ private static class Interval {
+
+ private final IntList keys = new IntArrayList();
+
+ public Interval(IntList... allKeys) {
+ assert allKeys.length > 0;
+ for (IntList keys : allKeys) {
+ assert keys.size() > 0;
+ this.keys.addAll(keys);
+ }
+ }
+
+ public int getMin() {
+ return keys.getInt(0);
+ }
+
+ public int getMax() {
+ return keys.getInt(keys.size() - 1);
+ }
+
+ public void addInterval(Interval other) {
+ assert getMax() < other.getMin();
+ keys.addAll(other.keys);
+ }
+
+ public long packedSavings(InternalOutputMode mode) {
+ long packedTargets = (long) getMax() - (long) getMin() + 1;
+ if (!IntSwitch.canBePacked(mode, packedTargets)) {
+ return Long.MIN_VALUE + 1;
+ }
+ long sparseCost =
+ IntSwitch.baseSparseSize(mode) + IntSwitch.sparsePayloadSize(mode, keys.size());
+ long packedCost =
+ IntSwitch.basePackedSize(mode) + IntSwitch.packedPayloadSize(mode, packedTargets);
+ return sparseCost - packedCost;
+ }
+
+ public long estimatedSize(InternalOutputMode mode) {
+ return IntSwitch.estimatedSize(mode, keys.toIntArray());
+ }
+ }
+
+ private Interval combineOrAddInterval(
+ List<Interval> intervals, Interval previous, Interval current) {
+ // As a first iteration, we only combine intervals if their packed size is less than their
+ // sparse counterpart. In CF we will have to add a load and a jump which add to the
+ // stack map table (1 is the size of a same entry).
+ InternalOutputMode mode = options.getInternalOutputMode();
+ int penalty = mode.isGeneratingClassFiles() ? 3 + 1 : 0;
+ if (previous == null) {
+ intervals.add(current);
+ return current;
+ }
+ Interval combined = new Interval(previous.keys, current.keys);
+ long packedSavings = combined.packedSavings(mode);
+ if (packedSavings <= 0
+ || packedSavings < previous.estimatedSize(mode) + current.estimatedSize(mode) - penalty) {
+ intervals.add(current);
+ return current;
+ } else {
+ intervals.set(intervals.size() - 1, combined);
+ return combined;
+ }
+ }
+
+ private void tryAddToBiggestSavings(
+ Set<Interval> biggestPackedSet,
+ PriorityQueue<Interval> intervals,
+ Interval toAdd,
+ int maximumNumberOfSwitches) {
+ assert !biggestPackedSet.contains(toAdd);
+ long savings = toAdd.packedSavings(options.getInternalOutputMode());
+ if (savings <= 0) {
+ return;
+ }
+ if (intervals.size() < maximumNumberOfSwitches) {
+ intervals.add(toAdd);
+ biggestPackedSet.add(toAdd);
+ } else if (savings > intervals.peek().packedSavings(options.getInternalOutputMode())) {
+ intervals.add(toAdd);
+ biggestPackedSet.add(toAdd);
+ biggestPackedSet.remove(intervals.poll());
+ }
+ }
+
+ private int codeUnitMargin() {
+ return options.getInternalOutputMode().isGeneratingClassFiles() ? 3 : 1;
+ }
+
+ private int findIfsForCandidates(
+ List<Interval> newSwitches, IntSwitch theSwitch, IntList outliers) {
+ Set<Interval> switchesToRemove = new HashSet<>();
+ InternalOutputMode mode = options.getInternalOutputMode();
+ int outliersAsIfSize = 0;
+ // The candidateForIfs is either an index to a switch that can be eliminated totally or a sparse
+ // where removing a key may produce a greater saving. It is only if keys are small in the packed
+ // switch that removing the keys makes sense (size wise).
+ for (Interval candidate : newSwitches) {
+ int maxIfBudget = 10;
+ long switchSize = candidate.estimatedSize(mode);
+ int sizeOfAllKeysAsIf = sizeForKeysWrittenAsIfs(theSwitch.value().outType(), candidate.keys);
+ if (candidate.keys.size() <= maxIfBudget
+ && sizeOfAllKeysAsIf < switchSize - codeUnitMargin()) {
+ outliersAsIfSize += sizeOfAllKeysAsIf;
+ switchesToRemove.add(candidate);
+ outliers.addAll(candidate.keys);
+ continue;
+ }
+ // One could do something clever here, but we use a simple algorithm that use the fact that
+ // all keys are sorted in ascending order and that the smallest absolute value will give the
+ // best saving.
+ IntList candidateKeys = candidate.keys;
+ int smallestPosition = -1;
+ long smallest = Long.MAX_VALUE;
+ for (int i = 0; i < candidateKeys.size(); i++) {
+ long current = Math.abs((long) candidateKeys.getInt(i));
+ if (current < smallest) {
+ smallestPosition = i;
+ smallest = current;
+ }
+ }
+ // Add as many keys forward and backward as we have budget and we decrease in size.
+ IntList ifKeys = new IntArrayList();
+ ifKeys.add(candidateKeys.getInt(smallestPosition));
+ long previousSavings = 0;
+ long currentSavings =
+ switchSize
+ - sizeForKeysWrittenAsIfs(theSwitch.value().outType(), ifKeys)
+ - IntSwitch.estimatedSparseSize(mode, candidateKeys.size() - ifKeys.size());
+ int minIndex = smallestPosition - 1;
+ int maxIndex = smallestPosition + 1;
+ while (ifKeys.size() < maxIfBudget && currentSavings > previousSavings) {
+ if (minIndex >= 0 && maxIndex < candidateKeys.size()) {
+ long valMin = Math.abs((long) candidateKeys.getInt(minIndex));
+ int valMax = Math.abs(candidateKeys.getInt(maxIndex));
+ if (valMax <= valMin) {
+ ifKeys.add(candidateKeys.getInt(maxIndex++));
+ } else {
+ ifKeys.add(candidateKeys.getInt(minIndex--));
+ }
+ } else if (minIndex >= 0) {
+ ifKeys.add(candidateKeys.getInt(minIndex--));
+ } else if (maxIndex < candidateKeys.size()) {
+ ifKeys.add(candidateKeys.getInt(maxIndex++));
+ } else {
+ // No more elements to add as if's.
+ break;
+ }
+ previousSavings = currentSavings;
+ currentSavings =
+ switchSize
+ - sizeForKeysWrittenAsIfs(theSwitch.value().outType(), ifKeys)
+ - IntSwitch.estimatedSparseSize(mode, candidateKeys.size() - ifKeys.size());
+ }
+ if (previousSavings >= currentSavings) {
+ // Remove the last added key since it did not contribute to savings.
+ int lastKey = ifKeys.getInt(ifKeys.size() - 1);
+ ifKeys.removeInt(ifKeys.size() - 1);
+ if (lastKey == candidateKeys.getInt(minIndex + 1)) {
+ minIndex++;
+ } else {
+ maxIndex--;
+ }
+ }
+ // Adjust pointers into the candidate keys.
+ minIndex++;
+ maxIndex--;
+ if (ifKeys.size() > 0) {
+ int ifsSize = sizeForKeysWrittenAsIfs(theSwitch.value().outType(), ifKeys);
+ long newSwitchSize =
+ IntSwitch.estimatedSparseSize(mode, candidateKeys.size() - ifKeys.size());
+ if (newSwitchSize + ifsSize + codeUnitMargin() < switchSize) {
+ candidateKeys.removeElements(minIndex, maxIndex);
+ outliers.addAll(ifKeys);
+ outliersAsIfSize += ifsSize;
+ }
+ }
+ }
+ newSwitches.removeAll(switchesToRemove);
+ return outliersAsIfSize;
+ }
+
+ private int sizeForKeysWrittenAsIfs(ValueType type, Collection<Integer> keys) {
+ int ifsSize = If.estimatedSize(options.getInternalOutputMode()) * keys.size();
+ // In Cf we also require a load as well (and a stack map entry)
+ if (options.getInternalOutputMode().isGeneratingClassFiles()) {
+ ifsSize += keys.size() * (3 + 1);
+ }
+ for (int k : keys) {
+ if (k != 0) {
+ ifsSize += ConstNumber.estimatedSize(options.getInternalOutputMode(), type, k);
+ }
+ }
+ return ifsSize;
+ }
+
+ /**
+ * Covert the switch instruction to a sequence of if instructions checking for a specified set of
+ * keys, followed by a new switch with the remaining keys.
+ */
+ // TODO(b/270398965): Replace LinkedList.
+ @SuppressWarnings("JdkObsolete")
+ public void convertSwitchToSwitchAndIfs(
+ IRCode code,
+ ListIterator<BasicBlock> blocksIterator,
+ BasicBlock originalBlock,
+ InstructionListIterator iterator,
+ IntSwitch theSwitch,
+ List<IntList> switches,
+ IntList keysToRemove) {
+
+ Position position = theSwitch.getPosition();
+
+ // Extract the information from the switch before removing it.
+ Int2ReferenceSortedMap<BasicBlock> keyToTarget = theSwitch.getKeyToTargetMap();
+
+ // Keep track of the current fallthrough, starting with the original.
+ BasicBlock fallthroughBlock = theSwitch.fallthroughBlock();
+
+ // Split the switch instruction into its own block and remove it.
+ iterator.previous();
+ BasicBlock originalSwitchBlock = iterator.split(code, blocksIterator);
+ assert !originalSwitchBlock.hasCatchHandlers();
+ assert originalSwitchBlock.getInstructions().size() == 1;
+ assert originalBlock.exit().isGoto();
+ theSwitch.moveDebugValues(originalBlock.exit());
+ blocksIterator.remove();
+ theSwitch.getBlock().detachAllSuccessors();
+ BasicBlock block = theSwitch.getBlock().unlinkSinglePredecessor();
+ assert theSwitch.getBlock().getPredecessors().size() == 0;
+ assert theSwitch.getBlock().getSuccessors().size() == 0;
+ assert block == originalBlock;
+
+ // Collect the new blocks for adding to the block list.
+ LinkedList<BasicBlock> newBlocks = new LinkedList<>();
+
+ // Build the switch-blocks backwards, to always have the fallthrough block in hand.
+ for (int i = switches.size() - 1; i >= 0; i--) {
+ SwitchBuilder switchBuilder = new SwitchBuilder(position);
+ switchBuilder.setValue(theSwitch.value());
+ IntList keys = switches.get(i);
+ for (int j = 0; j < keys.size(); j++) {
+ int key = keys.getInt(j);
+ switchBuilder.addKeyAndTarget(key, keyToTarget.get(key));
+ }
+ switchBuilder.setFallthrough(fallthroughBlock).setBlockNumber(code.getNextBlockNumber());
+ BasicBlock newSwitchBlock = switchBuilder.build(code.metadata());
+ newBlocks.addFirst(newSwitchBlock);
+ fallthroughBlock = newSwitchBlock;
+ }
+
+ // Build the if-blocks backwards, to always have the fallthrough block in hand.
+ for (int i = keysToRemove.size() - 1; i >= 0; i--) {
+ int key = keysToRemove.getInt(i);
+ BasicBlock peeledOffTarget = keyToTarget.get(key);
+ IfBuilder ifBuilder = new IfBuilder(position, code);
+ ifBuilder
+ .setLeft(theSwitch.value())
+ .setRight(key)
+ .setTarget(peeledOffTarget)
+ .setFallthrough(fallthroughBlock)
+ .setBlockNumber(code.getNextBlockNumber());
+ BasicBlock ifBlock = ifBuilder.build();
+ newBlocks.addFirst(ifBlock);
+ fallthroughBlock = ifBlock;
+ }
+
+ // Finally link the block before the original switch to the new block sequence.
+ originalBlock.link(fallthroughBlock);
+
+ // Finally add the blocks.
+ newBlocks.forEach(blocksIterator::add);
+ }
+
+ // TODO(sgjesse); Move this somewhere else, and reuse it for some of the other switch rewritings.
+ private abstract static class InstructionBuilder<T> {
+
+ int blockNumber;
+ final Position position;
+
+ InstructionBuilder(Position position) {
+ this.position = position;
+ }
+
+ abstract T self();
+
+ T setBlockNumber(int blockNumber) {
+ this.blockNumber = blockNumber;
+ return self();
+ }
+ }
+
+ private static class SwitchBuilder extends InstructionBuilder<SwitchBuilder> {
+
+ private Value value;
+ private final Int2ReferenceSortedMap<BasicBlock> keyToTarget = new Int2ReferenceAVLTreeMap<>();
+ private BasicBlock fallthrough;
+
+ SwitchBuilder(Position position) {
+ super(position);
+ }
+
+ @Override
+ SwitchBuilder self() {
+ return this;
+ }
+
+ SwitchBuilder setValue(Value value) {
+ this.value = value;
+ return this;
+ }
+
+ SwitchBuilder addKeyAndTarget(int key, BasicBlock target) {
+ keyToTarget.put(key, target);
+ return this;
+ }
+
+ SwitchBuilder setFallthrough(BasicBlock fallthrough) {
+ this.fallthrough = fallthrough;
+ return this;
+ }
+
+ BasicBlock build(IRMetadata metadata) {
+ final int NOT_FOUND = -1;
+ Object2IntMap<BasicBlock> targetToSuccessorIndex = new Object2IntLinkedOpenHashMap<>();
+ targetToSuccessorIndex.defaultReturnValue(NOT_FOUND);
+
+ int[] keys = new int[keyToTarget.size()];
+ int[] targetBlockIndices = new int[keyToTarget.size()];
+ // Sort keys descending.
+ int count = 0;
+ IntIterator iter = keyToTarget.keySet().iterator();
+ while (iter.hasNext()) {
+ int key = iter.nextInt();
+ BasicBlock target = keyToTarget.get(key);
+ Integer targetIndex =
+ targetToSuccessorIndex.computeIfAbsent(target, b -> targetToSuccessorIndex.size());
+ keys[count] = key;
+ targetBlockIndices[count] = targetIndex;
+ count++;
+ }
+ Integer fallthroughIndex =
+ targetToSuccessorIndex.computeIfAbsent(fallthrough, b -> targetToSuccessorIndex.size());
+ IntSwitch newSwitch = new IntSwitch(value, keys, targetBlockIndices, fallthroughIndex);
+ newSwitch.setPosition(position);
+ BasicBlock newSwitchBlock = BasicBlock.createSwitchBlock(blockNumber, newSwitch, metadata);
+ for (BasicBlock successor : targetToSuccessorIndex.keySet()) {
+ newSwitchBlock.link(successor);
+ }
+ return newSwitchBlock;
+ }
+ }
+
+ private static class IfBuilder extends InstructionBuilder<IfBuilder> {
+
+ private final IRCode code;
+ private Value left;
+ private int right;
+ private BasicBlock target;
+ private BasicBlock fallthrough;
+
+ IfBuilder(Position position, IRCode code) {
+ super(position);
+ this.code = code;
+ }
+
+ @Override
+ IfBuilder self() {
+ return this;
+ }
+
+ IfBuilder setLeft(Value left) {
+ this.left = left;
+ return this;
+ }
+
+ IfBuilder setRight(int right) {
+ this.right = right;
+ return this;
+ }
+
+ IfBuilder setTarget(BasicBlock target) {
+ this.target = target;
+ return this;
+ }
+
+ IfBuilder setFallthrough(BasicBlock fallthrough) {
+ this.fallthrough = fallthrough;
+ return this;
+ }
+
+ BasicBlock build() {
+ assert target != null;
+ assert fallthrough != null;
+ If newIf;
+ BasicBlock ifBlock;
+ if (right != 0) {
+ ConstNumber rightConst = code.createIntConstant(right);
+ rightConst.setPosition(position);
+ newIf = new If(IfType.EQ, ImmutableList.of(left, rightConst.dest()));
+ ifBlock = BasicBlock.createIfBlock(blockNumber, newIf, code.metadata(), rightConst);
+ } else {
+ newIf = new If(IfType.EQ, left);
+ ifBlock = BasicBlock.createIfBlock(blockNumber, newIf, code.metadata());
+ }
+ newIf.setPosition(position);
+ ifBlock.link(target);
+ ifBlock.link(fallthrough);
+ return ifBlock;
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/SwitchCaseEliminator.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/SwitchCaseEliminator.java
similarity index 99%
rename from src/main/java/com/android/tools/r8/ir/optimize/SwitchCaseEliminator.java
rename to src/main/java/com/android/tools/r8/ir/conversion/passes/SwitchCaseEliminator.java
index 11e0b51..cbda630 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/SwitchCaseEliminator.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/SwitchCaseEliminator.java
@@ -2,7 +2,7 @@
// 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.optimize;
+package com.android.tools.r8.ir.conversion.passes;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.ir.code.BasicBlock;
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialCheckCastAndInstanceOfRemover.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialCheckCastAndInstanceOfRemover.java
new file mode 100644
index 0000000..e19b963
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialCheckCastAndInstanceOfRemover.java
@@ -0,0 +1,384 @@
+// 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 static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
+
+import com.android.tools.r8.contexts.CompilationContext.MethodProcessingContext;
+import com.android.tools.r8.graph.AccessControl;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.analysis.type.DynamicTypeWithUpperBound;
+import com.android.tools.r8.ir.analysis.type.Nullability;
+import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
+import com.android.tools.r8.ir.analysis.type.TypeElement;
+import com.android.tools.r8.ir.analysis.type.TypeUtils;
+import com.android.tools.r8.ir.code.CheckCast;
+import com.android.tools.r8.ir.code.ConstNumber;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.IRMetadata;
+import com.android.tools.r8.ir.code.InstanceOf;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionListIterator;
+import com.android.tools.r8.ir.code.InvokeStatic;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.conversion.MethodProcessor;
+import com.android.tools.r8.ir.optimize.CodeRewriter;
+import com.android.tools.r8.ir.optimize.UtilityMethodsForCodeOptimizations;
+import com.android.tools.r8.ir.optimize.UtilityMethodsForCodeOptimizations.UtilityMethodForCodeOptimizations;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.InternalOptions;
+import com.google.common.collect.Sets;
+import java.util.Set;
+
+public class TrivialCheckCastAndInstanceOfRemover {
+
+ private final AppView<?> appView;
+ private final InternalOptions options;
+ private final DexItemFactory dexItemFactory;
+
+ public TrivialCheckCastAndInstanceOfRemover(AppView<?> appView) {
+ this.appView = appView;
+ this.options = appView.options();
+ this.dexItemFactory = appView.dexItemFactory();
+ }
+
+ public void run(
+ IRCode code,
+ ProgramMethod context,
+ MethodProcessor methodProcessor,
+ MethodProcessingContext methodProcessingContext) {
+ if (!appView.enableWholeProgramOptimizations()) {
+ return;
+ }
+
+ assert appView.appInfo().hasLiveness();
+ AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
+
+ if (!appView.options().testing.enableCheckCastAndInstanceOfRemoval) {
+ return;
+ }
+
+ IRMetadata metadata = code.metadata();
+ if (!metadata.mayHaveCheckCast() && !metadata.mayHaveInstanceOf()) {
+ return;
+ }
+
+ // If we can remove a CheckCast it is due to us having at least as much information about the
+ // type as the CheckCast gives. We then need to propagate that information to the users of
+ // the CheckCast to ensure further optimizations and removals of CheckCast:
+ //
+ // : 1: NewArrayEmpty v2 <- v1(1) java.lang.String[] <-- v2 = String[]
+ // ...
+ // : 2: CheckCast v5 <- v2; java.lang.Object[] <-- v5 = Object[]
+ // ...
+ // : 3: ArrayGet v7 <- v5, v6(0) <-- v7 = Object
+ // : 4: CheckCast v8 <- v7; java.lang.String <-- v8 = String
+ // ...
+ //
+ // When looking at line 2 we can conclude that the CheckCast is trivial because v2 is String[]
+ // and remove it. However, v7 is still only known to be Object and we cannot remove the
+ // CheckCast at line 4 unless we update v7 with the most precise information by narrowing the
+ // affected values of v5. We therefore have to run the type analysis after each CheckCast
+ // removal.
+ TypeAnalysis typeAnalysis = new TypeAnalysis(appView);
+ Set<Value> affectedValues = Sets.newIdentityHashSet();
+ InstructionListIterator it = code.instructionListIterator();
+ boolean needToRemoveTrivialPhis = false;
+ while (it.hasNext()) {
+ Instruction current = it.next();
+ if (current.isCheckCast()) {
+ boolean hasPhiUsers = current.outValue().hasPhiUsers();
+ RemoveCheckCastInstructionIfTrivialResult removeResult =
+ removeCheckCastInstructionIfTrivial(
+ appViewWithLiveness,
+ current.asCheckCast(),
+ it,
+ code,
+ context,
+ affectedValues,
+ methodProcessor,
+ methodProcessingContext);
+ if (removeResult != RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS) {
+ assert removeResult == RemoveCheckCastInstructionIfTrivialResult.REMOVED_CAST_DO_NARROW;
+ needToRemoveTrivialPhis |= hasPhiUsers;
+ typeAnalysis.narrowing(affectedValues);
+ affectedValues.clear();
+ }
+ } else if (current.isInstanceOf()) {
+ boolean hasPhiUsers = current.outValue().hasPhiUsers();
+ if (removeInstanceOfInstructionIfTrivial(
+ appViewWithLiveness, current.asInstanceOf(), it, code)) {
+ needToRemoveTrivialPhis |= hasPhiUsers;
+ }
+ }
+ }
+ // ... v1
+ // ...
+ // v2 <- check-cast v1, T
+ // v3 <- phi(v1, v2)
+ // Removing check-cast may result in a trivial phi:
+ // v3 <- phi(v1, v1)
+ if (needToRemoveTrivialPhis) {
+ code.removeAllDeadAndTrivialPhis(affectedValues);
+ if (!affectedValues.isEmpty()) {
+ typeAnalysis.narrowing(affectedValues);
+ }
+ }
+ assert code.isConsistentSSA(appView);
+ }
+
+ enum RemoveCheckCastInstructionIfTrivialResult {
+ NO_REMOVALS,
+ REMOVED_CAST_DO_NARROW
+ }
+
+ private enum InstanceOfResult {
+ UNKNOWN,
+ TRUE,
+ FALSE
+ }
+
+ // Returns true if the given check-cast instruction was removed.
+ private RemoveCheckCastInstructionIfTrivialResult removeCheckCastInstructionIfTrivial(
+ AppView<AppInfoWithLiveness> appViewWithLiveness,
+ CheckCast checkCast,
+ InstructionListIterator it,
+ IRCode code,
+ ProgramMethod context,
+ Set<Value> affectedValues,
+ MethodProcessor methodProcessor,
+ MethodProcessingContext methodProcessingContext) {
+ Value inValue = checkCast.object();
+ Value outValue = checkCast.outValue();
+ DexType castType = checkCast.getType();
+ DexType baseCastType = castType.toBaseType(dexItemFactory);
+
+ // If the cast type is not accessible in the current context, we should not remove the cast
+ // in order to preserve runtime errors. Note that JVM and ART behave differently: see
+ // {@link com.android.tools.r8.ir.optimize.checkcast.IllegalAccessErrorTest}.
+ if (baseCastType.isClassType()) {
+ DexClass baseCastClass = appView.definitionFor(baseCastType);
+ if (baseCastClass == null
+ || AccessControl.isClassAccessible(baseCastClass, code.context(), appViewWithLiveness)
+ .isPossiblyFalse()) {
+ return RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS;
+ }
+ }
+
+ if (!appView
+ .getOpenClosedInterfacesCollection()
+ .isDefinitelyInstanceOfStaticType(appViewWithLiveness, inValue)) {
+ return RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS;
+ }
+
+ // If the in-value is `null` and the cast-type is a float-array type, then trivial check-cast
+ // elimination may lead to verification errors. See b/123269162.
+ if (options.canHaveArtCheckCastVerifierBug()) {
+ if (inValue.getType().isNullType()
+ && castType.isArrayType()
+ && castType.toBaseType(dexItemFactory).isFloatType()) {
+ return RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS;
+ }
+ }
+
+ // If casting to an array of an interface type elimination may lead to verification errors.
+ // See b/132420510 and b/223424356.
+ if (options.canHaveIncorrectJoinForArrayOfInterfacesBug()) {
+ if (castType.isArrayType()) {
+ DexType baseType = castType.toBaseType(dexItemFactory);
+ if (baseType.isClassType() && baseType.isInterface(appViewWithLiveness)) {
+ return RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS;
+ }
+ }
+ }
+
+ TypeElement inTypeLattice = inValue.getType();
+ TypeElement outTypeLattice = outValue.getType();
+ TypeElement castTypeLattice = castType.toTypeElement(appView, inTypeLattice.nullability());
+
+ assert inTypeLattice.nullability().lessThanOrEqual(outTypeLattice.nullability());
+
+ if (inTypeLattice.lessThanOrEqual(castTypeLattice, appView)) {
+ // 1) Trivial cast.
+ // A a = ...
+ // A a' = (A) a;
+ // 2) Up-cast: we already have finer type info.
+ // A < B
+ // A a = ...
+ // B b = (B) a;
+ assert inTypeLattice.lessThanOrEqual(outTypeLattice, appView);
+ // The removeOrReplaceByDebugLocalWrite will propagate the incoming value for the CheckCast
+ // to the users of the CheckCast's out value.
+ //
+ // v2 = CheckCast A v1 ~~> DebugLocalWrite $v0 <- v1
+ //
+ // The DebugLocalWrite is not a user of the outvalue, we therefore have to wait and take the
+ // CheckCast invalue users that includes the potential DebugLocalWrite.
+ CodeRewriter.removeOrReplaceByDebugLocalWrite(checkCast, it, inValue, outValue);
+ affectedValues.addAll(inValue.affectedValues());
+ return RemoveCheckCastInstructionIfTrivialResult.REMOVED_CAST_DO_NARROW;
+ }
+
+ // If values of cast type are guaranteed to be null, then the out-value must be null if the cast
+ // succeeds. After removing all usages of the out-value, the check-cast instruction is replaced
+ // by a call to throwClassCastExceptionIfNotNull() to allow dead code elimination of the cast
+ // type.
+ if (castType.isClassType()
+ && castType.isAlwaysNull(appViewWithLiveness)
+ && !outValue.hasDebugUsers()) {
+ // Replace all usages of the out-value by null.
+ it.previous();
+ Value nullValue = it.insertConstNullInstruction(code, options);
+ it.next();
+ checkCast.outValue().replaceUsers(nullValue);
+ affectedValues.addAll(nullValue.affectedValues());
+
+ // Replace the check-cast instruction by throwClassCastExceptionIfNotNull().
+ UtilityMethodForCodeOptimizations throwClassCastExceptionIfNotNullMethod =
+ UtilityMethodsForCodeOptimizations.synthesizeThrowClassCastExceptionIfNotNullMethod(
+ appView, methodProcessor.getEventConsumer(), methodProcessingContext);
+ throwClassCastExceptionIfNotNullMethod.optimize(methodProcessor);
+ InvokeStatic replacement =
+ InvokeStatic.builder()
+ .setMethod(throwClassCastExceptionIfNotNullMethod.getMethod())
+ .setSingleArgument(checkCast.object())
+ .setPosition(checkCast)
+ .build();
+ it.replaceCurrentInstruction(replacement);
+ assert replacement.lookupSingleTarget(appView, context) != null;
+ return RemoveCheckCastInstructionIfTrivialResult.REMOVED_CAST_DO_NARROW;
+ }
+
+ // If the cast is guaranteed to succeed and only there to ensure the program type checks, then
+ // check if the program would still type check after removing the cast.
+ if (checkCast.isSafeCheckCast()
+ || checkCast
+ .getFirstOperand()
+ .getDynamicType(appViewWithLiveness)
+ .getDynamicUpperBoundType()
+ .lessThanOrEqualUpToNullability(castTypeLattice, appView)) {
+ TypeElement useType =
+ TypeUtils.computeUseType(appViewWithLiveness, context, checkCast.outValue());
+ if (inTypeLattice.lessThanOrEqualUpToNullability(useType, appView)) {
+ return RemoveCheckCastInstructionIfTrivialResult.REMOVED_CAST_DO_NARROW;
+ }
+ }
+
+ // Otherwise, keep the checkcast to preserve verification errors. E.g., down-cast:
+ // A < B < C
+ // c = ... // Even though we know c is of type A,
+ // a' = (B) c; // (this could be removed, since chained below.)
+ // a'' = (A) a'; // this should remain for runtime verification.
+ assert !inTypeLattice.isDefinitelyNull() || (inValue.isPhi() && !inTypeLattice.isNullType());
+ assert outTypeLattice.equalUpToNullability(castTypeLattice);
+ return RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS;
+ }
+
+ // Returns true if the given instance-of instruction was removed.
+ private boolean removeInstanceOfInstructionIfTrivial(
+ AppView<AppInfoWithLiveness> appViewWithLiveness,
+ InstanceOf instanceOf,
+ InstructionListIterator it,
+ IRCode code) {
+ ProgramMethod context = code.context();
+
+ // If the instance-of type is not accessible in the current context, we should not remove the
+ // instance-of instruction in order to preserve IllegalAccessError.
+ DexType instanceOfBaseType = instanceOf.type().toBaseType(dexItemFactory);
+ if (instanceOfBaseType.isClassType()) {
+ DexClass instanceOfClass = appView.definitionFor(instanceOfBaseType);
+ if (instanceOfClass == null
+ || AccessControl.isClassAccessible(instanceOfClass, context, appViewWithLiveness)
+ .isPossiblyFalse()) {
+ return false;
+ }
+ }
+
+ Value inValue = instanceOf.value();
+ if (!appView
+ .getOpenClosedInterfacesCollection()
+ .isDefinitelyInstanceOfStaticType(appViewWithLiveness, inValue)) {
+ return false;
+ }
+
+ TypeElement inType = inValue.getType();
+ TypeElement instanceOfType =
+ TypeElement.fromDexType(instanceOf.type(), inType.nullability(), appView);
+ Value aliasValue = inValue.getAliasedValue();
+
+ InstanceOfResult result = InstanceOfResult.UNKNOWN;
+ if (inType.isDefinitelyNull()) {
+ result = InstanceOfResult.FALSE;
+ } else if (inType.lessThanOrEqual(instanceOfType, appView) && !inType.isNullable()) {
+ result = InstanceOfResult.TRUE;
+ } else if (!aliasValue.isPhi()
+ && aliasValue.definition.isCreatingInstanceOrArray()
+ && instanceOfType.strictlyLessThan(inType, appView)) {
+ result = InstanceOfResult.FALSE;
+ } else if (appView.appInfo().hasLiveness()) {
+ if (instanceOf.type().isClassType()
+ && isNeverInstantiatedDirectlyOrIndirectly(instanceOf.type())) {
+ // The type of the instance-of instruction is a program class, and is never instantiated
+ // directly or indirectly. Thus, the in-value must be null, meaning that the instance-of
+ // instruction will always evaluate to false.
+ result = InstanceOfResult.FALSE;
+ }
+
+ if (result == InstanceOfResult.UNKNOWN) {
+ if (inType.isClassType()
+ && isNeverInstantiatedDirectlyOrIndirectly(inType.asClassType().getClassType())) {
+ // The type of the in-value is a program class, and is never instantiated directly or
+ // indirectly. This, the in-value must be null, meaning that the instance-of instruction
+ // will always evaluate to false.
+ result = InstanceOfResult.FALSE;
+ }
+ }
+
+ if (result == InstanceOfResult.UNKNOWN) {
+ Value aliasedValue =
+ inValue.getSpecificAliasedValue(
+ value ->
+ value.isDefinedByInstructionSatisfying(
+ Instruction::isAssumeWithDynamicTypeAssumption));
+ if (aliasedValue != null) {
+ DynamicTypeWithUpperBound dynamicType =
+ aliasedValue.getDefinition().asAssume().getDynamicTypeAssumption().getDynamicType();
+ Nullability nullability = dynamicType.getNullability();
+ if (nullability.isDefinitelyNull()) {
+ result = InstanceOfResult.FALSE;
+ } else if (dynamicType.getDynamicUpperBoundType().lessThanOrEqual(instanceOfType, appView)
+ && (!inType.isNullable() || !nullability.isNullable())) {
+ result = InstanceOfResult.TRUE;
+ }
+ }
+ }
+ }
+ if (result != InstanceOfResult.UNKNOWN) {
+ ConstNumber newInstruction =
+ new ConstNumber(
+ new Value(
+ code.valueNumberGenerator.next(),
+ TypeElement.getInt(),
+ instanceOf.outValue().getLocalInfo()),
+ result == InstanceOfResult.TRUE ? 1 : 0);
+ it.replaceCurrentInstruction(newInstruction);
+ return true;
+ }
+ return false;
+ }
+
+ private boolean isNeverInstantiatedDirectlyOrIndirectly(DexType type) {
+ assert appView.appInfo().hasLiveness();
+ assert type.isClassType();
+ DexProgramClass clazz = asProgramClassOrNull(appView.definitionFor(type));
+ return clazz != null
+ && !appView.appInfo().withLiveness().isInstantiatedDirectlyOrIndirectly(clazz);
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialGotosCollapser.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialGotosCollapser.java
new file mode 100644
index 0000000..7c9b4d0
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialGotosCollapser.java
@@ -0,0 +1,204 @@
+// 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.graph.ProgramMethod;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.If;
+import com.android.tools.r8.ir.code.Switch;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Set;
+
+/**
+ * Rewrite all branch targets to the destination of trivial goto chains when possible. Does not
+ * rewrite fallthrough targets as that would require block reordering and the transformation only
+ * makes sense after SSA destruction where there are no phis.
+ */
+public class TrivialGotosCollapser extends CodeRewriterPass<AppInfo> {
+
+ public TrivialGotosCollapser(AppView<?> appView) {
+ super(appView);
+ }
+
+ @Override
+ String getTimingId() {
+ return "TrivialGotosCollapser";
+ }
+
+ @Override
+ void rewriteCode(ProgramMethod method, IRCode code) {
+ assert code.isConsistentGraph(appView);
+ List<BasicBlock> blocksToRemove = new ArrayList<>();
+ // Rewrite all non-fallthrough targets to the end of trivial goto chains and remove
+ // first round of trivial goto blocks.
+ ListIterator<BasicBlock> iterator = code.listIterator();
+ assert iterator.hasNext();
+ BasicBlock block = iterator.next();
+ BasicBlock nextBlock;
+
+ do {
+ nextBlock = iterator.hasNext() ? iterator.next() : null;
+ if (block.isTrivialGoto()) {
+ collapseTrivialGoto(code, block, nextBlock, blocksToRemove);
+ }
+ if (block.exit().isIf()) {
+ collapseIfTrueTarget(block);
+ }
+ if (block.exit().isSwitch()) {
+ collapseNonFallthroughSwitchTargets(block);
+ }
+ block = nextBlock;
+ } while (nextBlock != null);
+ code.removeBlocks(blocksToRemove);
+ // Get rid of gotos to the next block.
+ while (!blocksToRemove.isEmpty()) {
+ blocksToRemove = new ArrayList<>();
+ iterator = code.listIterator();
+ block = iterator.next();
+ do {
+ nextBlock = iterator.hasNext() ? iterator.next() : null;
+ if (block.isTrivialGoto()) {
+ collapseTrivialGoto(code, block, nextBlock, blocksToRemove);
+ }
+ block = nextBlock;
+ } while (block != null);
+ code.removeBlocks(blocksToRemove);
+ }
+ assert removedTrivialGotos(code);
+ assert code.isConsistentGraph(appView);
+ }
+
+ @Override
+ boolean shouldRewriteCode(ProgramMethod method, IRCode code) {
+ return true;
+ }
+
+ public static void unlinkTrivialGotoBlock(BasicBlock block, BasicBlock target) {
+ assert block.isTrivialGoto();
+ for (BasicBlock pred : block.getPredecessors()) {
+ pred.replaceSuccessor(block, target);
+ }
+ for (BasicBlock succ : block.getSuccessors()) {
+ succ.getMutablePredecessors().remove(block);
+ }
+ for (BasicBlock pred : block.getPredecessors()) {
+ if (!target.getPredecessors().contains(pred)) {
+ target.getMutablePredecessors().add(pred);
+ }
+ }
+ }
+
+ private boolean isFallthroughBlock(BasicBlock block) {
+ for (BasicBlock pred : block.getPredecessors()) {
+ if (pred.exit().fallthroughBlock() == block) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ private boolean removedTrivialGotos(IRCode code) {
+ ListIterator<BasicBlock> iterator = code.listIterator();
+ assert iterator.hasNext();
+ BasicBlock block = iterator.next();
+ BasicBlock nextBlock;
+ do {
+ nextBlock = iterator.hasNext() ? iterator.next() : null;
+ // Trivial goto block are only kept if they are self-targeting or are targeted by
+ // fallthroughs.
+ BasicBlock blk = block; // Additional local for lambda below.
+ assert !block.isTrivialGoto()
+ || block.exit().asGoto().getTarget() == block
+ || code.entryBlock() == block
+ || block.getPredecessors().stream().anyMatch((b) -> b.exit().fallthroughBlock() == blk);
+ // Trivial goto blocks never target the next block (in that case there should just be a
+ // fallthrough).
+ assert !block.isTrivialGoto() || block.exit().asGoto().getTarget() != nextBlock;
+ block = nextBlock;
+ } while (block != null);
+ return true;
+ }
+
+ private void collapseTrivialGoto(
+ IRCode code, BasicBlock block, BasicBlock nextBlock, List<BasicBlock> blocksToRemove) {
+
+ // This is the base case for GOTO loops.
+ if (block.exit().asGoto().getTarget() == block) {
+ return;
+ }
+
+ BasicBlock target = block.endOfGotoChain();
+
+ boolean needed = false;
+
+ if (target == null) {
+ // This implies we are in a loop of GOTOs. In that case, we will iteratively remove each
+ // trivial GOTO one-by-one until the above base case (one block targeting itself) is left.
+ target = block.exit().asGoto().getTarget();
+ }
+
+ if (target != nextBlock) {
+ // Not targeting the fallthrough block, determine if we need this goto. We need it if
+ // a fallthrough can hit this block. That is the case if the block is the entry block
+ // or if one of the predecessors fall through to the block.
+ needed = code.entryBlock() == block || isFallthroughBlock(block);
+ }
+
+ if (!needed) {
+ blocksToRemove.add(block);
+ unlinkTrivialGotoBlock(block, target);
+ }
+ }
+
+ private void collapseIfTrueTarget(BasicBlock block) {
+ If insn = block.exit().asIf();
+ BasicBlock target = insn.getTrueTarget();
+ BasicBlock newTarget = target.endOfGotoChain();
+ BasicBlock fallthrough = insn.fallthroughBlock();
+ BasicBlock newFallthrough = fallthrough.endOfGotoChain();
+ if (newTarget != null && target != newTarget) {
+ insn.getBlock().replaceSuccessor(target, newTarget);
+ target.getMutablePredecessors().remove(block);
+ if (!newTarget.getPredecessors().contains(block)) {
+ newTarget.getMutablePredecessors().add(block);
+ }
+ }
+ if (block.exit().isIf()) {
+ insn = block.exit().asIf();
+ if (insn.getTrueTarget() == newFallthrough) {
+ // Replace if with the same true and fallthrough target with a goto to the fallthrough.
+ block.replaceSuccessor(insn.getTrueTarget(), fallthrough);
+ assert block.exit().isGoto();
+ assert block.exit().asGoto().getTarget() == fallthrough;
+ }
+ }
+ }
+
+ private void collapseNonFallthroughSwitchTargets(BasicBlock block) {
+ Switch insn = block.exit().asSwitch();
+ BasicBlock fallthroughBlock = insn.fallthroughBlock();
+ Set<BasicBlock> replacedBlocks = new HashSet<>();
+ for (int j = 0; j < insn.targetBlockIndices().length; j++) {
+ BasicBlock target = insn.targetBlock(j);
+ if (target != fallthroughBlock) {
+ BasicBlock newTarget = target.endOfGotoChain();
+ if (newTarget != null && target != newTarget && !replacedBlocks.contains(target)) {
+ insn.getBlock().replaceSuccessor(target, newTarget);
+ target.getMutablePredecessors().remove(block);
+ if (!newTarget.getPredecessors().contains(block)) {
+ newTarget.getMutablePredecessors().add(block);
+ }
+ replacedBlocks.add(target);
+ }
+ }
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialPhiSimplifier.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialPhiSimplifier.java
new file mode 100644
index 0000000..6c4c66f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/TrivialPhiSimplifier.java
@@ -0,0 +1,113 @@
+// 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.algorithms.scc.SCC;
+import com.android.tools.r8.errors.CompilationError;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InvokeDirect;
+import com.android.tools.r8.ir.code.NewInstance;
+import com.android.tools.r8.ir.code.Phi;
+import com.android.tools.r8.ir.code.UnusedArgument;
+import com.android.tools.r8.ir.code.Value;
+import com.google.common.collect.Sets;
+import java.util.List;
+import java.util.Set;
+
+public class TrivialPhiSimplifier {
+
+ public static void replaceUnusedArgumentTrivialPhis(UnusedArgument unusedArgument) {
+ replaceTrivialPhis(unusedArgument.outValue());
+ for (Phi phiUser : unusedArgument.outValue().uniquePhiUsers()) {
+ phiUser.removeTrivialPhi();
+ }
+ assert !unusedArgument.outValue().hasPhiUsers();
+ }
+
+ public static void ensureDirectStringNewToInit(IRCode code, DexItemFactory dexItemFactory) {
+ for (Instruction instruction : code.instructions()) {
+ if (instruction.isInvokeDirect()) {
+ InvokeDirect invoke = instruction.asInvokeDirect();
+ DexMethod method = invoke.getInvokedMethod();
+ if (dexItemFactory.isConstructor(method)
+ && method.holder == dexItemFactory.stringType
+ && invoke.getReceiver().isPhi()) {
+ NewInstance newInstance = findNewInstance(invoke.getReceiver().asPhi());
+ replaceTrivialPhis(newInstance.outValue());
+ if (invoke.getReceiver().isPhi()) {
+ throw new CompilationError(
+ "Failed to remove trivial phis between new-instance and <init>");
+ }
+ newInstance.markNoSpilling();
+ }
+ }
+ }
+ }
+
+ private static NewInstance findNewInstance(Phi phi) {
+ Set<Phi> seen = Sets.newIdentityHashSet();
+ Set<Value> values = Sets.newIdentityHashSet();
+ recursiveAddOperands(phi, seen, values);
+ if (values.size() != 1) {
+ throw new CompilationError("Failed to identify unique new-instance for <init>");
+ }
+ Value newInstanceValue = values.iterator().next();
+ if (newInstanceValue.definition == null || !newInstanceValue.definition.isNewInstance()) {
+ throw new CompilationError("Invalid defining value for call to <init>");
+ }
+ return newInstanceValue.definition.asNewInstance();
+ }
+
+ private static void recursiveAddOperands(Phi phi, Set<Phi> seen, Set<Value> values) {
+ for (Value operand : phi.getOperands()) {
+ if (!operand.isPhi()) {
+ values.add(operand);
+ } else {
+ Phi phiOp = operand.asPhi();
+ if (seen.add(phiOp)) {
+ recursiveAddOperands(phiOp, seen, values);
+ }
+ }
+ }
+ }
+
+ // We compute the set of strongly connected phis making use of the out value and replace all
+ // trivial ones by the out value.
+ // This is a simplified variant of the removeRedundantPhis algorithm in Section 3.2 of:
+ // http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf
+ private static void replaceTrivialPhis(Value outValue) {
+ List<Set<Value>> components = new SCC<Value>(Value::uniquePhiUsers).computeSCC(outValue);
+ for (int i = components.size() - 1; i >= 0; i--) {
+ Set<Value> component = components.get(i);
+ if (component.size() == 1 && component.iterator().next() == outValue) {
+ continue;
+ }
+ Set<Phi> trivialPhis = Sets.newIdentityHashSet();
+ for (Value value : component) {
+ boolean isTrivial = true;
+ Phi p = value.asPhi();
+ for (Value op : p.getOperands()) {
+ if (op != outValue && !component.contains(op)) {
+ isTrivial = false;
+ break;
+ }
+ }
+ if (isTrivial) {
+ trivialPhis.add(p);
+ }
+ }
+ for (Phi trivialPhi : trivialPhis) {
+ for (Value op : trivialPhi.getOperands()) {
+ op.removePhiUser(trivialPhi);
+ }
+ trivialPhi.replaceUsers(outValue);
+ trivialPhi.getBlock().removePhi(trivialPhi);
+ }
+ }
+ }
+}
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 26da1f1..4ad6534 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
@@ -4,7 +4,6 @@
package com.android.tools.r8.ir.optimize;
-import static com.android.tools.r8.graph.DexProgramClass.asProgramClassOrNull;
import static com.android.tools.r8.ir.analysis.type.Nullability.definitelyNotNull;
import static com.android.tools.r8.ir.analysis.type.Nullability.maybeNull;
import static com.android.tools.r8.ir.code.Opcodes.CONST_CLASS;
@@ -14,47 +13,29 @@
import static com.android.tools.r8.ir.code.Opcodes.INSTANCE_GET;
import static com.android.tools.r8.ir.code.Opcodes.STATIC_GET;
-import com.android.tools.r8.algorithms.scc.SCC;
-import com.android.tools.r8.contexts.CompilationContext.MethodProcessingContext;
-import com.android.tools.r8.errors.CompilationError;
import com.android.tools.r8.errors.Unreachable;
-import com.android.tools.r8.graph.AccessControl;
import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DebugLocalInfo;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexClassAndMethod;
-import com.android.tools.r8.graph.DexEncodedField;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexMethod;
-import com.android.tools.r8.graph.DexProgramClass;
import com.android.tools.r8.graph.DexProto;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.graph.FieldResolutionResult.SingleProgramFieldResolutionResult;
import com.android.tools.r8.graph.ProgramMethod;
-import com.android.tools.r8.horizontalclassmerging.HorizontalClassMergerUtils;
-import com.android.tools.r8.ir.analysis.equivalence.BasicBlockBehavioralSubsumption;
-import com.android.tools.r8.ir.analysis.type.ArrayTypeElement;
-import com.android.tools.r8.ir.analysis.type.DynamicTypeWithUpperBound;
-import com.android.tools.r8.ir.analysis.type.Nullability;
import com.android.tools.r8.ir.analysis.type.TypeAnalysis;
import com.android.tools.r8.ir.analysis.type.TypeElement;
-import com.android.tools.r8.ir.analysis.type.TypeUtils;
import com.android.tools.r8.ir.analysis.value.AbstractValue;
-import com.android.tools.r8.ir.analysis.value.ConstantOrNonConstantNumberValue;
-import com.android.tools.r8.ir.analysis.value.SingleConstClassValue;
-import com.android.tools.r8.ir.analysis.value.SingleFieldValue;
import com.android.tools.r8.ir.code.ArrayLength;
-import com.android.tools.r8.ir.code.ArrayPut;
import com.android.tools.r8.ir.code.Assume;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.BasicBlockIterator;
import com.android.tools.r8.ir.code.Binop;
import com.android.tools.r8.ir.code.CatchHandlers;
import com.android.tools.r8.ir.code.CatchHandlers.CatchHandler;
-import com.android.tools.r8.ir.code.CheckCast;
import com.android.tools.r8.ir.code.ConstClass;
import com.android.tools.r8.ir.code.ConstNumber;
import com.android.tools.r8.ir.code.ConstString;
@@ -64,85 +45,51 @@
import com.android.tools.r8.ir.code.DominatorTree;
import com.android.tools.r8.ir.code.Goto;
import com.android.tools.r8.ir.code.IRCode;
-import com.android.tools.r8.ir.code.IRMetadata;
import com.android.tools.r8.ir.code.If;
import com.android.tools.r8.ir.code.IfType;
import com.android.tools.r8.ir.code.InstanceFieldInstruction;
import com.android.tools.r8.ir.code.InstanceGet;
-import com.android.tools.r8.ir.code.InstanceOf;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.Instruction.SideEffectAssumption;
import com.android.tools.r8.ir.code.InstructionIterator;
import com.android.tools.r8.ir.code.InstructionListIterator;
import com.android.tools.r8.ir.code.InstructionOrPhi;
-import com.android.tools.r8.ir.code.IntSwitch;
import com.android.tools.r8.ir.code.Invoke;
import com.android.tools.r8.ir.code.InvokeDirect;
import com.android.tools.r8.ir.code.InvokeInterface;
import com.android.tools.r8.ir.code.InvokeMethod;
import com.android.tools.r8.ir.code.InvokeMethodWithReceiver;
-import com.android.tools.r8.ir.code.InvokeNewArray;
-import com.android.tools.r8.ir.code.InvokeStatic;
import com.android.tools.r8.ir.code.InvokeVirtual;
-import com.android.tools.r8.ir.code.LinearFlowInstructionListIterator;
import com.android.tools.r8.ir.code.Move;
-import com.android.tools.r8.ir.code.NewArrayEmpty;
-import com.android.tools.r8.ir.code.NewArrayFilledData;
import com.android.tools.r8.ir.code.NewInstance;
-import com.android.tools.r8.ir.code.NumericType;
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.ir.code.Position.SyntheticPosition;
import com.android.tools.r8.ir.code.StaticGet;
-import com.android.tools.r8.ir.code.Switch;
import com.android.tools.r8.ir.code.Throw;
-import com.android.tools.r8.ir.code.UnusedArgument;
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.MethodProcessor;
-import com.android.tools.r8.ir.optimize.UtilityMethodsForCodeOptimizations.UtilityMethodForCodeOptimizations;
-import com.android.tools.r8.ir.optimize.controlflow.SwitchCaseAnalyzer;
import com.android.tools.r8.ir.optimize.info.MethodOptimizationInfo;
import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator;
-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.InternalOptions.RewriteArrayOptions;
-import com.android.tools.r8.utils.InternalOutputMode;
import com.android.tools.r8.utils.LazyBox;
-import com.android.tools.r8.utils.LongInterval;
-import com.android.tools.r8.utils.SetUtils;
-import com.android.tools.r8.utils.WorkList;
import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;
import com.google.common.collect.Streams;
import it.unimi.dsi.fastutil.ints.Int2IntMap;
import it.unimi.dsi.fastutil.ints.Int2IntOpenHashMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap.Entry;
import it.unimi.dsi.fastutil.ints.Int2ReferenceOpenHashMap;
-import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
-import it.unimi.dsi.fastutil.ints.IntArrayList;
-import it.unimi.dsi.fastutil.ints.IntIterator;
-import it.unimi.dsi.fastutil.ints.IntList;
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 it.unimi.dsi.fastutil.objects.Object2IntLinkedOpenHashMap;
-import it.unimi.dsi.fastutil.objects.Object2IntMap;
import it.unimi.dsi.fastutil.objects.Reference2IntMap;
import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
import java.util.ArrayList;
-import java.util.Arrays;
import java.util.BitSet;
-import java.util.Collection;
import java.util.Collections;
-import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
@@ -150,18 +97,11 @@
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
-import java.util.PriorityQueue;
import java.util.Set;
import java.util.function.Predicate;
public class CodeRewriter {
- private enum InstanceOfResult {
- UNKNOWN,
- TRUE,
- FALSE
- }
-
// This constant was determined by experimentation.
private static final int STOP_SHARED_CONSTANT_THRESHOLD = 50;
@@ -233,28 +173,6 @@
assert Streams.stream(code.instructions()).noneMatch(Instruction::isAssume);
}
- private static boolean removedTrivialGotos(IRCode code) {
- ListIterator<BasicBlock> iterator = code.listIterator();
- assert iterator.hasNext();
- BasicBlock block = iterator.next();
- BasicBlock nextBlock;
- do {
- nextBlock = iterator.hasNext() ? iterator.next() : null;
- // Trivial goto block are only kept if they are self-targeting or are targeted by
- // fallthroughs.
- BasicBlock blk = block; // Additional local for lambda below.
- assert !block.isTrivialGoto()
- || block.exit().asGoto().getTarget() == block
- || code.entryBlock() == block
- || block.getPredecessors().stream().anyMatch((b) -> b.exit().fallthroughBlock() == blk);
- // Trivial goto blocks never target the next block (in that case there should just be a
- // fallthrough).
- assert !block.isTrivialGoto() || block.exit().asGoto().getTarget() != nextBlock;
- block = nextBlock;
- } while (block != null);
- return true;
- }
-
// Rewrite 'throw new NullPointerException()' to 'throw null'.
public void rewriteThrowNullPointerException(IRCode code) {
boolean shouldRemoveUnreachableBlocks = false;
@@ -395,815 +313,6 @@
assert code.isConsistentSSA(appView);
}
- public static boolean isFallthroughBlock(BasicBlock block) {
- for (BasicBlock pred : block.getPredecessors()) {
- if (pred.exit().fallthroughBlock() == block) {
- return true;
- }
- }
- return false;
- }
-
- private static void collapseTrivialGoto(
- IRCode code, BasicBlock block, BasicBlock nextBlock, List<BasicBlock> blocksToRemove) {
-
- // This is the base case for GOTO loops.
- if (block.exit().asGoto().getTarget() == block) {
- return;
- }
-
- BasicBlock target = block.endOfGotoChain();
-
- boolean needed = false;
-
- if (target == null) {
- // This implies we are in a loop of GOTOs. In that case, we will iteratively remove each
- // trivial GOTO one-by-one until the above base case (one block targeting itself) is left.
- target = block.exit().asGoto().getTarget();
- }
-
- if (target != nextBlock) {
- // Not targeting the fallthrough block, determine if we need this goto. We need it if
- // a fallthrough can hit this block. That is the case if the block is the entry block
- // or if one of the predecessors fall through to the block.
- needed = code.entryBlock() == block || isFallthroughBlock(block);
- }
-
- if (!needed) {
- blocksToRemove.add(block);
- unlinkTrivialGotoBlock(block, target);
- }
- }
-
- public static void unlinkTrivialGotoBlock(BasicBlock block, BasicBlock target) {
- assert block.isTrivialGoto();
- for (BasicBlock pred : block.getPredecessors()) {
- pred.replaceSuccessor(block, target);
- }
- for (BasicBlock succ : block.getSuccessors()) {
- succ.getMutablePredecessors().remove(block);
- }
- for (BasicBlock pred : block.getPredecessors()) {
- if (!target.getPredecessors().contains(pred)) {
- target.getMutablePredecessors().add(pred);
- }
- }
- }
-
- private static void collapseIfTrueTarget(BasicBlock block) {
- If insn = block.exit().asIf();
- BasicBlock target = insn.getTrueTarget();
- BasicBlock newTarget = target.endOfGotoChain();
- BasicBlock fallthrough = insn.fallthroughBlock();
- BasicBlock newFallthrough = fallthrough.endOfGotoChain();
- if (newTarget != null && target != newTarget) {
- insn.getBlock().replaceSuccessor(target, newTarget);
- target.getMutablePredecessors().remove(block);
- if (!newTarget.getPredecessors().contains(block)) {
- newTarget.getMutablePredecessors().add(block);
- }
- }
- if (block.exit().isIf()) {
- insn = block.exit().asIf();
- if (insn.getTrueTarget() == newFallthrough) {
- // Replace if with the same true and fallthrough target with a goto to the fallthrough.
- block.replaceSuccessor(insn.getTrueTarget(), fallthrough);
- assert block.exit().isGoto();
- assert block.exit().asGoto().getTarget() == fallthrough;
- }
- }
- }
-
- private static void collapseNonFallthroughSwitchTargets(BasicBlock block) {
- Switch insn = block.exit().asSwitch();
- BasicBlock fallthroughBlock = insn.fallthroughBlock();
- Set<BasicBlock> replacedBlocks = new HashSet<>();
- for (int j = 0; j < insn.targetBlockIndices().length; j++) {
- BasicBlock target = insn.targetBlock(j);
- if (target != fallthroughBlock) {
- BasicBlock newTarget = target.endOfGotoChain();
- if (newTarget != null && target != newTarget && !replacedBlocks.contains(target)) {
- insn.getBlock().replaceSuccessor(target, newTarget);
- target.getMutablePredecessors().remove(block);
- if (!newTarget.getPredecessors().contains(block)) {
- newTarget.getMutablePredecessors().add(block);
- }
- replacedBlocks.add(target);
- }
- }
- }
- }
-
- // TODO(sgjesse); Move this somewhere else, and reuse it for some of the other switch rewritings.
- public abstract static class InstructionBuilder<T> {
-
- protected int blockNumber;
- protected final Position position;
-
- protected InstructionBuilder(Position position) {
- this.position = position;
- }
-
- public abstract T self();
-
- public T setBlockNumber(int blockNumber) {
- this.blockNumber = blockNumber;
- return self();
- }
- }
-
- public static class SwitchBuilder extends InstructionBuilder<SwitchBuilder> {
-
- private Value value;
- private final Int2ReferenceSortedMap<BasicBlock> keyToTarget = new Int2ReferenceAVLTreeMap<>();
- private BasicBlock fallthrough;
-
- public SwitchBuilder(Position position) {
- super(position);
- }
-
- @Override
- public SwitchBuilder self() {
- return this;
- }
-
- public SwitchBuilder setValue(Value value) {
- this.value = value;
- return this;
- }
-
- public SwitchBuilder addKeyAndTarget(int key, BasicBlock target) {
- keyToTarget.put(key, target);
- return this;
- }
-
- public SwitchBuilder setFallthrough(BasicBlock fallthrough) {
- this.fallthrough = fallthrough;
- return this;
- }
-
- public BasicBlock build(IRMetadata metadata) {
- final int NOT_FOUND = -1;
- Object2IntMap<BasicBlock> targetToSuccessorIndex = new Object2IntLinkedOpenHashMap<>();
- targetToSuccessorIndex.defaultReturnValue(NOT_FOUND);
-
- int[] keys = new int[keyToTarget.size()];
- int[] targetBlockIndices = new int[keyToTarget.size()];
- // Sort keys descending.
- int count = 0;
- IntIterator iter = keyToTarget.keySet().iterator();
- while (iter.hasNext()) {
- int key = iter.nextInt();
- BasicBlock target = keyToTarget.get(key);
- Integer targetIndex =
- targetToSuccessorIndex.computeIfAbsent(target, b -> targetToSuccessorIndex.size());
- keys[count] = key;
- targetBlockIndices[count] = targetIndex;
- count++;
- }
- Integer fallthroughIndex =
- targetToSuccessorIndex.computeIfAbsent(fallthrough, b -> targetToSuccessorIndex.size());
- IntSwitch newSwitch = new IntSwitch(value, keys, targetBlockIndices, fallthroughIndex);
- newSwitch.setPosition(position);
- BasicBlock newSwitchBlock = BasicBlock.createSwitchBlock(blockNumber, newSwitch, metadata);
- for (BasicBlock successor : targetToSuccessorIndex.keySet()) {
- newSwitchBlock.link(successor);
- }
- return newSwitchBlock;
- }
- }
-
- public static class IfBuilder extends InstructionBuilder<IfBuilder> {
-
- private final IRCode code;
- private Value left;
- private int right;
- private BasicBlock target;
- private BasicBlock fallthrough;
-
- public IfBuilder(Position position, IRCode code) {
- super(position);
- this.code = code;
- }
-
- @Override
- public IfBuilder self() {
- return this;
- }
-
- public IfBuilder setLeft(Value left) {
- this.left = left;
- return this;
- }
-
- public IfBuilder setRight(int right) {
- this.right = right;
- return this;
- }
-
- public IfBuilder setTarget(BasicBlock target) {
- this.target = target;
- return this;
- }
-
- public IfBuilder setFallthrough(BasicBlock fallthrough) {
- this.fallthrough = fallthrough;
- return this;
- }
-
- public BasicBlock build() {
- assert target != null;
- assert fallthrough != null;
- If newIf;
- BasicBlock ifBlock;
- if (right != 0) {
- ConstNumber rightConst = code.createIntConstant(right);
- rightConst.setPosition(position);
- newIf = new If(IfType.EQ, ImmutableList.of(left, rightConst.dest()));
- ifBlock = BasicBlock.createIfBlock(blockNumber, newIf, code.metadata(), rightConst);
- } else {
- newIf = new If(IfType.EQ, left);
- ifBlock = BasicBlock.createIfBlock(blockNumber, newIf, code.metadata());
- }
- newIf.setPosition(position);
- ifBlock.link(target);
- ifBlock.link(fallthrough);
- return ifBlock;
- }
- }
-
- /**
- * Covert the switch instruction to a sequence of if instructions checking for a specified set of
- * keys, followed by a new switch with the remaining keys.
- */
- // TODO(b/270398965): Replace LinkedList.
- @SuppressWarnings("JdkObsolete")
- void convertSwitchToSwitchAndIfs(
- IRCode code,
- ListIterator<BasicBlock> blocksIterator,
- BasicBlock originalBlock,
- InstructionListIterator iterator,
- IntSwitch theSwitch,
- List<IntList> switches,
- IntList keysToRemove) {
-
- Position position = theSwitch.getPosition();
-
- // Extract the information from the switch before removing it.
- Int2ReferenceSortedMap<BasicBlock> keyToTarget = theSwitch.getKeyToTargetMap();
-
- // Keep track of the current fallthrough, starting with the original.
- BasicBlock fallthroughBlock = theSwitch.fallthroughBlock();
-
- // Split the switch instruction into its own block and remove it.
- iterator.previous();
- BasicBlock originalSwitchBlock = iterator.split(code, blocksIterator);
- assert !originalSwitchBlock.hasCatchHandlers();
- assert originalSwitchBlock.getInstructions().size() == 1;
- assert originalBlock.exit().isGoto();
- theSwitch.moveDebugValues(originalBlock.exit());
- blocksIterator.remove();
- theSwitch.getBlock().detachAllSuccessors();
- BasicBlock block = theSwitch.getBlock().unlinkSinglePredecessor();
- assert theSwitch.getBlock().getPredecessors().size() == 0;
- assert theSwitch.getBlock().getSuccessors().size() == 0;
- assert block == originalBlock;
-
- // Collect the new blocks for adding to the block list.
- LinkedList<BasicBlock> newBlocks = new LinkedList<>();
-
- // Build the switch-blocks backwards, to always have the fallthrough block in hand.
- for (int i = switches.size() - 1; i >= 0; i--) {
- SwitchBuilder switchBuilder = new SwitchBuilder(position);
- switchBuilder.setValue(theSwitch.value());
- IntList keys = switches.get(i);
- for (int j = 0; j < keys.size(); j++) {
- int key = keys.getInt(j);
- switchBuilder.addKeyAndTarget(key, keyToTarget.get(key));
- }
- switchBuilder.setFallthrough(fallthroughBlock).setBlockNumber(code.getNextBlockNumber());
- BasicBlock newSwitchBlock = switchBuilder.build(code.metadata());
- newBlocks.addFirst(newSwitchBlock);
- fallthroughBlock = newSwitchBlock;
- }
-
- // Build the if-blocks backwards, to always have the fallthrough block in hand.
- for (int i = keysToRemove.size() - 1; i >= 0; i--) {
- int key = keysToRemove.getInt(i);
- BasicBlock peeledOffTarget = keyToTarget.get(key);
- IfBuilder ifBuilder = new IfBuilder(position, code);
- ifBuilder
- .setLeft(theSwitch.value())
- .setRight(key)
- .setTarget(peeledOffTarget)
- .setFallthrough(fallthroughBlock)
- .setBlockNumber(code.getNextBlockNumber());
- BasicBlock ifBlock = ifBuilder.build();
- newBlocks.addFirst(ifBlock);
- fallthroughBlock = ifBlock;
- }
-
- // Finally link the block before the original switch to the new block sequence.
- originalBlock.link(fallthroughBlock);
-
- // Finally add the blocks.
- newBlocks.forEach(blocksIterator::add);
- }
-
- private static class Interval {
-
- private final IntList keys = new IntArrayList();
-
- public Interval(IntList... allKeys) {
- assert allKeys.length > 0;
- for (IntList keys : allKeys) {
- assert keys.size() > 0;
- this.keys.addAll(keys);
- }
- }
-
- public int getMin() {
- return keys.getInt(0);
- }
-
- public int getMax() {
- return keys.getInt(keys.size() - 1);
- }
-
- public void addInterval(Interval other) {
- assert getMax() < other.getMin();
- keys.addAll(other.keys);
- }
-
- public long packedSavings(InternalOutputMode mode) {
- long packedTargets = (long) getMax() - (long) getMin() + 1;
- if (!IntSwitch.canBePacked(mode, packedTargets)) {
- return Long.MIN_VALUE + 1;
- }
- long sparseCost =
- IntSwitch.baseSparseSize(mode) + IntSwitch.sparsePayloadSize(mode, keys.size());
- long packedCost =
- IntSwitch.basePackedSize(mode) + IntSwitch.packedPayloadSize(mode, packedTargets);
- return sparseCost - packedCost;
- }
-
- public long estimatedSize(InternalOutputMode mode) {
- return IntSwitch.estimatedSize(mode, keys.toIntArray());
- }
- }
-
- private Interval combineOrAddInterval(
- List<Interval> intervals, Interval previous, Interval current) {
- // As a first iteration, we only combine intervals if their packed size is less than their
- // sparse counterpart. In CF we will have to add a load and a jump which add to the
- // stack map table (1 is the size of a same entry).
- InternalOutputMode mode = options.getInternalOutputMode();
- int penalty = mode.isGeneratingClassFiles() ? 3 + 1 : 0;
- if (previous == null) {
- intervals.add(current);
- return current;
- }
- Interval combined = new Interval(previous.keys, current.keys);
- long packedSavings = combined.packedSavings(mode);
- if (packedSavings <= 0
- || packedSavings < previous.estimatedSize(mode) + current.estimatedSize(mode) - penalty) {
- intervals.add(current);
- return current;
- } else {
- intervals.set(intervals.size() - 1, combined);
- return combined;
- }
- }
-
- private void tryAddToBiggestSavings(
- Set<Interval> biggestPackedSet,
- PriorityQueue<Interval> intervals,
- Interval toAdd,
- int maximumNumberOfSwitches) {
- assert !biggestPackedSet.contains(toAdd);
- long savings = toAdd.packedSavings(options.getInternalOutputMode());
- if (savings <= 0) {
- return;
- }
- if (intervals.size() < maximumNumberOfSwitches) {
- intervals.add(toAdd);
- biggestPackedSet.add(toAdd);
- } else if (savings > intervals.peek().packedSavings(options.getInternalOutputMode())) {
- intervals.add(toAdd);
- biggestPackedSet.add(toAdd);
- biggestPackedSet.remove(intervals.poll());
- }
- }
-
- private int sizeForKeysWrittenAsIfs(ValueType type, Collection<Integer> keys) {
- int ifsSize = If.estimatedSize(options.getInternalOutputMode()) * keys.size();
- // In Cf we also require a load as well (and a stack map entry)
- if (options.getInternalOutputMode().isGeneratingClassFiles()) {
- ifsSize += keys.size() * (3 + 1);
- }
- for (int k : keys) {
- if (k != 0) {
- ifsSize += ConstNumber.estimatedSize(options.getInternalOutputMode(), type, k);
- }
- }
- return ifsSize;
- }
-
- private int codeUnitMargin() {
- return options.getInternalOutputMode().isGeneratingClassFiles() ? 3 : 1;
- }
-
- private int findIfsForCandidates(
- List<Interval> newSwitches, IntSwitch theSwitch, IntList outliers) {
- Set<Interval> switchesToRemove = new HashSet<>();
- InternalOutputMode mode = options.getInternalOutputMode();
- int outliersAsIfSize = 0;
- // The candidateForIfs is either an index to a switch that can be eliminated totally or a sparse
- // where removing a key may produce a greater saving. It is only if keys are small in the packed
- // switch that removing the keys makes sense (size wise).
- for (Interval candidate : newSwitches) {
- int maxIfBudget = 10;
- long switchSize = candidate.estimatedSize(mode);
- int sizeOfAllKeysAsIf = sizeForKeysWrittenAsIfs(theSwitch.value().outType(), candidate.keys);
- if (candidate.keys.size() <= maxIfBudget
- && sizeOfAllKeysAsIf < switchSize - codeUnitMargin()) {
- outliersAsIfSize += sizeOfAllKeysAsIf;
- switchesToRemove.add(candidate);
- outliers.addAll(candidate.keys);
- continue;
- }
- // One could do something clever here, but we use a simple algorithm that use the fact that
- // all keys are sorted in ascending order and that the smallest absolute value will give the
- // best saving.
- IntList candidateKeys = candidate.keys;
- int smallestPosition = -1;
- long smallest = Long.MAX_VALUE;
- for (int i = 0; i < candidateKeys.size(); i++) {
- long current = Math.abs((long) candidateKeys.getInt(i));
- if (current < smallest) {
- smallestPosition = i;
- smallest = current;
- }
- }
- // Add as many keys forward and backward as we have budget and we decrease in size.
- IntList ifKeys = new IntArrayList();
- ifKeys.add(candidateKeys.getInt(smallestPosition));
- long previousSavings = 0;
- long currentSavings =
- switchSize
- - sizeForKeysWrittenAsIfs(theSwitch.value().outType(), ifKeys)
- - IntSwitch.estimatedSparseSize(mode, candidateKeys.size() - ifKeys.size());
- int minIndex = smallestPosition - 1;
- int maxIndex = smallestPosition + 1;
- while (ifKeys.size() < maxIfBudget && currentSavings > previousSavings) {
- if (minIndex >= 0 && maxIndex < candidateKeys.size()) {
- long valMin = Math.abs((long) candidateKeys.getInt(minIndex));
- int valMax = Math.abs(candidateKeys.getInt(maxIndex));
- if (valMax <= valMin) {
- ifKeys.add(candidateKeys.getInt(maxIndex++));
- } else {
- ifKeys.add(candidateKeys.getInt(minIndex--));
- }
- } else if (minIndex >= 0) {
- ifKeys.add(candidateKeys.getInt(minIndex--));
- } else if (maxIndex < candidateKeys.size()) {
- ifKeys.add(candidateKeys.getInt(maxIndex++));
- } else {
- // No more elements to add as if's.
- break;
- }
- previousSavings = currentSavings;
- currentSavings =
- switchSize
- - sizeForKeysWrittenAsIfs(theSwitch.value().outType(), ifKeys)
- - IntSwitch.estimatedSparseSize(mode, candidateKeys.size() - ifKeys.size());
- }
- if (previousSavings >= currentSavings) {
- // Remove the last added key since it did not contribute to savings.
- int lastKey = ifKeys.getInt(ifKeys.size() - 1);
- ifKeys.removeInt(ifKeys.size() - 1);
- if (lastKey == candidateKeys.getInt(minIndex + 1)) {
- minIndex++;
- } else {
- maxIndex--;
- }
- }
- // Adjust pointers into the candidate keys.
- minIndex++;
- maxIndex--;
- if (ifKeys.size() > 0) {
- int ifsSize = sizeForKeysWrittenAsIfs(theSwitch.value().outType(), ifKeys);
- long newSwitchSize =
- IntSwitch.estimatedSparseSize(mode, candidateKeys.size() - ifKeys.size());
- if (newSwitchSize + ifsSize + codeUnitMargin() < switchSize) {
- candidateKeys.removeElements(minIndex, maxIndex);
- outliers.addAll(ifKeys);
- outliersAsIfSize += ifsSize;
- }
- }
- }
- newSwitches.removeAll(switchesToRemove);
- return outliersAsIfSize;
- }
-
- public boolean rewriteSwitch(IRCode code) {
- return rewriteSwitch(code, SwitchCaseAnalyzer.getInstance());
- }
-
- private boolean rewriteSwitch(IRCode code, SwitchCaseAnalyzer switchCaseAnalyzer) {
- if (!options.isSwitchRewritingEnabled()) {
- return false;
- }
- if (!code.metadata().mayHaveSwitch()) {
- return false;
- }
- return rewriteSwitchFull(code, switchCaseAnalyzer);
- }
-
- private boolean rewriteSwitchFull(IRCode code, SwitchCaseAnalyzer switchCaseAnalyzer) {
- boolean needToRemoveUnreachableBlocks = false;
- ListIterator<BasicBlock> blocksIterator = code.listIterator();
- while (blocksIterator.hasNext()) {
- BasicBlock block = blocksIterator.next();
- InstructionListIterator iterator = block.listIterator(code);
- while (iterator.hasNext()) {
- Instruction instruction = iterator.next();
- if (instruction.isSwitch()) {
- Switch theSwitch = instruction.asSwitch();
- if (options.testing.enableDeadSwitchCaseElimination) {
- SwitchCaseEliminator eliminator =
- removeUnnecessarySwitchCases(code, theSwitch, iterator, switchCaseAnalyzer);
- if (eliminator.mayHaveIntroducedUnreachableBlocks()) {
- needToRemoveUnreachableBlocks = true;
- }
-
- iterator.previous();
- instruction = iterator.next();
- if (instruction.isGoto()) {
- continue;
- }
-
- assert instruction.isSwitch();
- theSwitch = instruction.asSwitch();
- }
- if (theSwitch.isIntSwitch()) {
- rewriteIntSwitch(code, blocksIterator, block, iterator, theSwitch.asIntSwitch());
- }
- }
- }
- }
-
- // Rewriting of switches introduces new branching structure. It relies on critical edges
- // being split on the way in but does not maintain this property. We therefore split
- // critical edges at exit.
- code.splitCriticalEdges();
-
- Set<Value> affectedValues =
- needToRemoveUnreachableBlocks ? code.removeUnreachableBlocks() : ImmutableSet.of();
- if (!affectedValues.isEmpty()) {
- new TypeAnalysis(appView).narrowing(affectedValues);
- }
- assert code.isConsistentSSA(appView);
- return !affectedValues.isEmpty();
- }
-
- void rewriteSingleKeySwitchToIf(
- IRCode code, BasicBlock block, InstructionListIterator iterator, IntSwitch theSwitch) {
- // Rewrite the switch to an if.
- int fallthroughBlockIndex = theSwitch.getFallthroughBlockIndex();
- int caseBlockIndex = theSwitch.targetBlockIndices()[0];
- if (fallthroughBlockIndex < caseBlockIndex) {
- block.swapSuccessorsByIndex(fallthroughBlockIndex, caseBlockIndex);
- }
- If replacement;
- if (theSwitch.isIntSwitch() && theSwitch.asIntSwitch().getFirstKey() == 0) {
- replacement = new If(IfType.EQ, theSwitch.value());
- } else {
- Instruction labelConst = theSwitch.materializeFirstKey(appView, code);
- labelConst.setPosition(theSwitch.getPosition());
- iterator.previous();
- iterator.add(labelConst);
- Instruction dummy = iterator.next();
- assert dummy == theSwitch;
- replacement = new If(IfType.EQ, ImmutableList.of(theSwitch.value(), labelConst.outValue()));
- }
- iterator.replaceCurrentInstruction(replacement);
- }
-
- private void rewriteIntSwitch(
- IRCode code,
- ListIterator<BasicBlock> blockIterator,
- BasicBlock block,
- InstructionListIterator iterator,
- IntSwitch theSwitch) {
- if (disableSwitchToIfRewritingForClassIdComparisons(theSwitch)) {
- return;
- }
-
- if (theSwitch.numberOfKeys() == 1) {
- rewriteSingleKeySwitchToIf(code, block, iterator, theSwitch);
- return;
- }
-
- // If there are more than 1 key, we use the following algorithm to find keys to combine.
- // First, scan through the keys forward and combine each packed interval with the
- // previous interval if it gives a net saving.
- // Secondly, go through all created intervals and combine the ones without a saving into
- // a single interval and keep a max number of packed switches.
- // Finally, go through all intervals and check if the switch or part of the switch
- // should be transformed to ifs.
-
- // Phase 1: Combine packed intervals.
- InternalOutputMode mode = options.getInternalOutputMode();
- int[] keys = theSwitch.getKeys();
- int maxNumberOfIfsOrSwitches = 10;
- PriorityQueue<Interval> biggestPackedSavings =
- new PriorityQueue<>((x, y) -> Long.compare(y.packedSavings(mode), x.packedSavings(mode)));
- Set<Interval> biggestPackedSet = new HashSet<>();
- List<Interval> intervals = new ArrayList<>();
- int previousKey = keys[0];
- IntList currentKeys = new IntArrayList();
- currentKeys.add(previousKey);
- Interval previousInterval = null;
- for (int i = 1; i < keys.length; i++) {
- int key = keys[i];
- if (((long) key - (long) previousKey) > 1) {
- Interval current = new Interval(currentKeys);
- Interval added = combineOrAddInterval(intervals, previousInterval, current);
- if (added != current && biggestPackedSet.contains(previousInterval)) {
- biggestPackedSet.remove(previousInterval);
- biggestPackedSavings.remove(previousInterval);
- }
- tryAddToBiggestSavings(
- biggestPackedSet, biggestPackedSavings, added, maxNumberOfIfsOrSwitches);
- previousInterval = added;
- currentKeys = new IntArrayList();
- }
- currentKeys.add(key);
- previousKey = key;
- }
- Interval current = new Interval(currentKeys);
- Interval added = combineOrAddInterval(intervals, previousInterval, current);
- if (added != current && biggestPackedSet.contains(previousInterval)) {
- biggestPackedSet.remove(previousInterval);
- biggestPackedSavings.remove(previousInterval);
- }
- tryAddToBiggestSavings(biggestPackedSet, biggestPackedSavings, added, maxNumberOfIfsOrSwitches);
-
- // Phase 2: combine sparse intervals into a single bin.
- // Check if we should save a space for a sparse switch, if so, remove the switch with
- // the smallest savings.
- if (biggestPackedSet.size() == maxNumberOfIfsOrSwitches
- && maxNumberOfIfsOrSwitches < intervals.size()) {
- biggestPackedSet.remove(biggestPackedSavings.poll());
- }
- Interval sparse = null;
- List<Interval> newSwitches = new ArrayList<>(maxNumberOfIfsOrSwitches);
- for (int i = 0; i < intervals.size(); i++) {
- Interval interval = intervals.get(i);
- if (biggestPackedSet.contains(interval)) {
- newSwitches.add(interval);
- } else if (sparse == null) {
- sparse = interval;
- newSwitches.add(sparse);
- } else {
- sparse.addInterval(interval);
- }
- }
-
- // Phase 3: at this point we are guaranteed to have the biggest saving switches
- // in newIntervals, potentially with a switch combining the remaining intervals.
- // Now we check to see if we can create any if's to reduce size.
- IntList outliers = new IntArrayList();
- int outliersAsIfSize =
- appView.options().testing.enableSwitchToIfRewriting
- ? findIfsForCandidates(newSwitches, theSwitch, outliers)
- : 0;
-
- long newSwitchesSize = 0;
- List<IntList> newSwitchSequences = new ArrayList<>(newSwitches.size());
- for (Interval interval : newSwitches) {
- newSwitchesSize += interval.estimatedSize(mode);
- newSwitchSequences.add(interval.keys);
- }
-
- long currentSize = IntSwitch.estimatedSize(mode, theSwitch.getKeys());
- if (newSwitchesSize + outliersAsIfSize + codeUnitMargin() < currentSize) {
- convertSwitchToSwitchAndIfs(
- code, blockIterator, block, iterator, theSwitch, newSwitchSequences, outliers);
- }
- }
-
- // TODO(b/181732463): We currently disable switch-to-if rewritings for switches on $r8$classId
- // field values (from horizontal class merging. See bug for more details.
- private boolean disableSwitchToIfRewritingForClassIdComparisons(IntSwitch theSwitch) {
- Value switchValue = theSwitch.value().getAliasedValue();
- if (!switchValue.isDefinedByInstructionSatisfying(Instruction::isInstanceGet)) {
- return false;
- }
- AppInfoWithLiveness appInfo = appView.appInfoWithLiveness();
- if (appInfo == null) {
- return false;
- }
- InstanceGet instanceGet = switchValue.getDefinition().asInstanceGet();
- SingleProgramFieldResolutionResult resolutionResult =
- appInfo.resolveField(instanceGet.getField()).asSingleProgramFieldResolutionResult();
- if (resolutionResult == null) {
- return false;
- }
- DexEncodedField resolvedField = resolutionResult.getResolvedField();
- return HorizontalClassMergerUtils.isClassIdField(appView, resolvedField);
- }
-
- private SwitchCaseEliminator removeUnnecessarySwitchCases(
- IRCode code,
- Switch theSwitch,
- InstructionListIterator iterator,
- SwitchCaseAnalyzer switchCaseAnalyzer) {
- BasicBlock defaultTarget = theSwitch.fallthroughBlock();
- SwitchCaseEliminator eliminator = new SwitchCaseEliminator(theSwitch, iterator);
- BasicBlockBehavioralSubsumption behavioralSubsumption =
- new BasicBlockBehavioralSubsumption(appView, code);
-
- // Compute the set of switch cases that can be removed.
- boolean hasSwitchCaseToDefaultRewrite = false;
- AbstractValue switchAbstractValue = theSwitch.value().getAbstractValue(appView, code.context());
- for (int i = 0; i < theSwitch.numberOfKeys(); i++) {
- BasicBlock targetBlock = theSwitch.targetBlock(i);
-
- if (switchCaseAnalyzer.switchCaseIsAlwaysHit(theSwitch, i)) {
- eliminator.markSwitchCaseAsAlwaysHit(i);
- break;
- }
-
- // This switch case can be removed if the behavior of the target block is equivalent to the
- // behavior of the default block, or if the switch case is unreachable.
- if (switchCaseAnalyzer.switchCaseIsUnreachable(theSwitch, switchAbstractValue, i)) {
- eliminator.markSwitchCaseForRemoval(i);
- } else if (behavioralSubsumption.isSubsumedBy(
- theSwitch.value(), targetBlock, defaultTarget)) {
- eliminator.markSwitchCaseForRemoval(i);
- hasSwitchCaseToDefaultRewrite = true;
- }
- }
-
- if (eliminator.isFallthroughLive()
- && !hasSwitchCaseToDefaultRewrite
- && switchCaseAnalyzer.switchFallthroughIsNeverHit(theSwitch, switchAbstractValue)) {
- eliminator.markSwitchFallthroughAsNeverHit();
- }
-
- eliminator.optimize();
- return eliminator;
- }
-
- /**
- * Rewrite all branch targets to the destination of trivial goto chains when possible. Does not
- * rewrite fallthrough targets as that would require block reordering and the transformation only
- * makes sense after SSA destruction where there are no phis.
- */
- public static void collapseTrivialGotos(AppView<?> appView, IRCode code) {
- assert code.isConsistentGraph(appView);
- List<BasicBlock> blocksToRemove = new ArrayList<>();
- // Rewrite all non-fallthrough targets to the end of trivial goto chains and remove
- // first round of trivial goto blocks.
- ListIterator<BasicBlock> iterator = code.listIterator();
- assert iterator.hasNext();
- BasicBlock block = iterator.next();
- BasicBlock nextBlock;
-
- do {
- nextBlock = iterator.hasNext() ? iterator.next() : null;
- if (block.isTrivialGoto()) {
- collapseTrivialGoto(code, block, nextBlock, blocksToRemove);
- }
- if (block.exit().isIf()) {
- collapseIfTrueTarget(block);
- }
- if (block.exit().isSwitch()) {
- collapseNonFallthroughSwitchTargets(block);
- }
- block = nextBlock;
- } while (nextBlock != null);
- code.removeBlocks(blocksToRemove);
- // Get rid of gotos to the next block.
- while (!blocksToRemove.isEmpty()) {
- blocksToRemove = new ArrayList<>();
- iterator = code.listIterator();
- block = iterator.next();
- do {
- nextBlock = iterator.hasNext() ? iterator.next() : null;
- if (block.isTrivialGoto()) {
- collapseTrivialGoto(code, block, nextBlock, blocksToRemove);
- }
- block = nextBlock;
- } while (block != null);
- code.removeBlocks(blocksToRemove);
- }
- assert removedTrivialGotos(code);
- assert code.isConsistentGraph(appView);
- }
-
private boolean checkArgumentType(InvokeMethod invoke, int argumentIndex) {
// TODO(sgjesse): Insert cast if required.
TypeElement returnType =
@@ -1309,333 +418,6 @@
return changed;
}
- enum RemoveCheckCastInstructionIfTrivialResult {
- NO_REMOVALS,
- REMOVED_CAST_DO_NARROW
- }
-
- public void removeTrivialCheckCastAndInstanceOfInstructions(
- IRCode code,
- ProgramMethod context,
- MethodProcessor methodProcessor,
- MethodProcessingContext methodProcessingContext) {
- if (!appView.enableWholeProgramOptimizations()) {
- return;
- }
-
- assert appView.appInfo().hasLiveness();
- AppView<AppInfoWithLiveness> appViewWithLiveness = appView.withLiveness();
-
- if (!appView.options().testing.enableCheckCastAndInstanceOfRemoval) {
- return;
- }
-
- IRMetadata metadata = code.metadata();
- if (!metadata.mayHaveCheckCast() && !metadata.mayHaveInstanceOf()) {
- return;
- }
-
- // If we can remove a CheckCast it is due to us having at least as much information about the
- // type as the CheckCast gives. We then need to propagate that information to the users of
- // the CheckCast to ensure further optimizations and removals of CheckCast:
- //
- // : 1: NewArrayEmpty v2 <- v1(1) java.lang.String[] <-- v2 = String[]
- // ...
- // : 2: CheckCast v5 <- v2; java.lang.Object[] <-- v5 = Object[]
- // ...
- // : 3: ArrayGet v7 <- v5, v6(0) <-- v7 = Object
- // : 4: CheckCast v8 <- v7; java.lang.String <-- v8 = String
- // ...
- //
- // When looking at line 2 we can conclude that the CheckCast is trivial because v2 is String[]
- // and remove it. However, v7 is still only known to be Object and we cannot remove the
- // CheckCast at line 4 unless we update v7 with the most precise information by narrowing the
- // affected values of v5. We therefore have to run the type analysis after each CheckCast
- // removal.
- TypeAnalysis typeAnalysis = new TypeAnalysis(appView);
- Set<Value> affectedValues = Sets.newIdentityHashSet();
- InstructionListIterator it = code.instructionListIterator();
- boolean needToRemoveTrivialPhis = false;
- while (it.hasNext()) {
- Instruction current = it.next();
- if (current.isCheckCast()) {
- boolean hasPhiUsers = current.outValue().hasPhiUsers();
- RemoveCheckCastInstructionIfTrivialResult removeResult =
- removeCheckCastInstructionIfTrivial(
- appViewWithLiveness,
- current.asCheckCast(),
- it,
- code,
- context,
- affectedValues,
- methodProcessor,
- methodProcessingContext);
- if (removeResult != RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS) {
- assert removeResult == RemoveCheckCastInstructionIfTrivialResult.REMOVED_CAST_DO_NARROW;
- needToRemoveTrivialPhis |= hasPhiUsers;
- typeAnalysis.narrowing(affectedValues);
- affectedValues.clear();
- }
- } else if (current.isInstanceOf()) {
- boolean hasPhiUsers = current.outValue().hasPhiUsers();
- if (removeInstanceOfInstructionIfTrivial(
- appViewWithLiveness, current.asInstanceOf(), it, code)) {
- needToRemoveTrivialPhis |= hasPhiUsers;
- }
- }
- }
- // ... v1
- // ...
- // v2 <- check-cast v1, T
- // v3 <- phi(v1, v2)
- // Removing check-cast may result in a trivial phi:
- // v3 <- phi(v1, v1)
- if (needToRemoveTrivialPhis) {
- code.removeAllDeadAndTrivialPhis(affectedValues);
- if (!affectedValues.isEmpty()) {
- typeAnalysis.narrowing(affectedValues);
- }
- }
- assert code.isConsistentSSA(appView);
- }
-
- // Returns true if the given check-cast instruction was removed.
- private RemoveCheckCastInstructionIfTrivialResult removeCheckCastInstructionIfTrivial(
- AppView<AppInfoWithLiveness> appViewWithLiveness,
- CheckCast checkCast,
- InstructionListIterator it,
- IRCode code,
- ProgramMethod context,
- Set<Value> affectedValues,
- MethodProcessor methodProcessor,
- MethodProcessingContext methodProcessingContext) {
- Value inValue = checkCast.object();
- Value outValue = checkCast.outValue();
- DexType castType = checkCast.getType();
- DexType baseCastType = castType.toBaseType(dexItemFactory);
-
- // If the cast type is not accessible in the current context, we should not remove the cast
- // in order to preserve runtime errors. Note that JVM and ART behave differently: see
- // {@link com.android.tools.r8.ir.optimize.checkcast.IllegalAccessErrorTest}.
- if (baseCastType.isClassType()) {
- DexClass baseCastClass = appView.definitionFor(baseCastType);
- if (baseCastClass == null
- || AccessControl.isClassAccessible(baseCastClass, code.context(), appViewWithLiveness)
- .isPossiblyFalse()) {
- return RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS;
- }
- }
-
- if (!appView
- .getOpenClosedInterfacesCollection()
- .isDefinitelyInstanceOfStaticType(appViewWithLiveness, inValue)) {
- return RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS;
- }
-
- // If the in-value is `null` and the cast-type is a float-array type, then trivial check-cast
- // elimination may lead to verification errors. See b/123269162.
- if (options.canHaveArtCheckCastVerifierBug()) {
- if (inValue.getType().isNullType()
- && castType.isArrayType()
- && castType.toBaseType(dexItemFactory).isFloatType()) {
- return RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS;
- }
- }
-
- // If casting to an array of an interface type elimination may lead to verification errors.
- // See b/132420510 and b/223424356.
- if (options.canHaveIncorrectJoinForArrayOfInterfacesBug()) {
- if (castType.isArrayType()) {
- DexType baseType = castType.toBaseType(dexItemFactory);
- if (baseType.isClassType() && baseType.isInterface(appViewWithLiveness)) {
- return RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS;
- }
- }
- }
-
- TypeElement inTypeLattice = inValue.getType();
- TypeElement outTypeLattice = outValue.getType();
- TypeElement castTypeLattice = castType.toTypeElement(appView, inTypeLattice.nullability());
-
- assert inTypeLattice.nullability().lessThanOrEqual(outTypeLattice.nullability());
-
- if (inTypeLattice.lessThanOrEqual(castTypeLattice, appView)) {
- // 1) Trivial cast.
- // A a = ...
- // A a' = (A) a;
- // 2) Up-cast: we already have finer type info.
- // A < B
- // A a = ...
- // B b = (B) a;
- assert inTypeLattice.lessThanOrEqual(outTypeLattice, appView);
- // The removeOrReplaceByDebugLocalWrite will propagate the incoming value for the CheckCast
- // to the users of the CheckCast's out value.
- //
- // v2 = CheckCast A v1 ~~> DebugLocalWrite $v0 <- v1
- //
- // The DebugLocalWrite is not a user of the outvalue, we therefore have to wait and take the
- // CheckCast invalue users that includes the potential DebugLocalWrite.
- removeOrReplaceByDebugLocalWrite(checkCast, it, inValue, outValue);
- affectedValues.addAll(inValue.affectedValues());
- return RemoveCheckCastInstructionIfTrivialResult.REMOVED_CAST_DO_NARROW;
- }
-
- // If values of cast type are guaranteed to be null, then the out-value must be null if the cast
- // succeeds. After removing all usages of the out-value, the check-cast instruction is replaced
- // by a call to throwClassCastExceptionIfNotNull() to allow dead code elimination of the cast
- // type.
- if (castType.isClassType()
- && castType.isAlwaysNull(appViewWithLiveness)
- && !outValue.hasDebugUsers()) {
- // Replace all usages of the out-value by null.
- it.previous();
- Value nullValue = it.insertConstNullInstruction(code, options);
- it.next();
- checkCast.outValue().replaceUsers(nullValue);
- affectedValues.addAll(nullValue.affectedValues());
-
- // Replace the check-cast instruction by throwClassCastExceptionIfNotNull().
- UtilityMethodForCodeOptimizations throwClassCastExceptionIfNotNullMethod =
- UtilityMethodsForCodeOptimizations.synthesizeThrowClassCastExceptionIfNotNullMethod(
- appView, methodProcessor.getEventConsumer(), methodProcessingContext);
- throwClassCastExceptionIfNotNullMethod.optimize(methodProcessor);
- InvokeStatic replacement =
- InvokeStatic.builder()
- .setMethod(throwClassCastExceptionIfNotNullMethod.getMethod())
- .setSingleArgument(checkCast.object())
- .setPosition(checkCast)
- .build();
- it.replaceCurrentInstruction(replacement);
- assert replacement.lookupSingleTarget(appView, context) != null;
- return RemoveCheckCastInstructionIfTrivialResult.REMOVED_CAST_DO_NARROW;
- }
-
- // If the cast is guaranteed to succeed and only there to ensure the program type checks, then
- // check if the program would still type check after removing the cast.
- if (checkCast.isSafeCheckCast()
- || checkCast
- .getFirstOperand()
- .getDynamicType(appViewWithLiveness)
- .getDynamicUpperBoundType()
- .lessThanOrEqualUpToNullability(castTypeLattice, appView)) {
- TypeElement useType =
- TypeUtils.computeUseType(appViewWithLiveness, context, checkCast.outValue());
- if (inTypeLattice.lessThanOrEqualUpToNullability(useType, appView)) {
- return RemoveCheckCastInstructionIfTrivialResult.REMOVED_CAST_DO_NARROW;
- }
- }
-
- // Otherwise, keep the checkcast to preserve verification errors. E.g., down-cast:
- // A < B < C
- // c = ... // Even though we know c is of type A,
- // a' = (B) c; // (this could be removed, since chained below.)
- // a'' = (A) a'; // this should remain for runtime verification.
- assert !inTypeLattice.isDefinitelyNull() || (inValue.isPhi() && !inTypeLattice.isNullType());
- assert outTypeLattice.equalUpToNullability(castTypeLattice);
- return RemoveCheckCastInstructionIfTrivialResult.NO_REMOVALS;
- }
-
- // Returns true if the given instance-of instruction was removed.
- private boolean removeInstanceOfInstructionIfTrivial(
- AppView<AppInfoWithLiveness> appViewWithLiveness,
- InstanceOf instanceOf,
- InstructionListIterator it,
- IRCode code) {
- ProgramMethod context = code.context();
-
- // If the instance-of type is not accessible in the current context, we should not remove the
- // instance-of instruction in order to preserve IllegalAccessError.
- DexType instanceOfBaseType = instanceOf.type().toBaseType(dexItemFactory);
- if (instanceOfBaseType.isClassType()) {
- DexClass instanceOfClass = appView.definitionFor(instanceOfBaseType);
- if (instanceOfClass == null
- || AccessControl.isClassAccessible(instanceOfClass, context, appViewWithLiveness)
- .isPossiblyFalse()) {
- return false;
- }
- }
-
- Value inValue = instanceOf.value();
- if (!appView
- .getOpenClosedInterfacesCollection()
- .isDefinitelyInstanceOfStaticType(appViewWithLiveness, inValue)) {
- return false;
- }
-
- TypeElement inType = inValue.getType();
- TypeElement instanceOfType =
- TypeElement.fromDexType(instanceOf.type(), inType.nullability(), appView);
- Value aliasValue = inValue.getAliasedValue();
-
- InstanceOfResult result = InstanceOfResult.UNKNOWN;
- if (inType.isDefinitelyNull()) {
- result = InstanceOfResult.FALSE;
- } else if (inType.lessThanOrEqual(instanceOfType, appView) && !inType.isNullable()) {
- result = InstanceOfResult.TRUE;
- } else if (!aliasValue.isPhi()
- && aliasValue.definition.isCreatingInstanceOrArray()
- && instanceOfType.strictlyLessThan(inType, appView)) {
- result = InstanceOfResult.FALSE;
- } else if (appView.appInfo().hasLiveness()) {
- if (instanceOf.type().isClassType()
- && isNeverInstantiatedDirectlyOrIndirectly(instanceOf.type())) {
- // The type of the instance-of instruction is a program class, and is never instantiated
- // directly or indirectly. Thus, the in-value must be null, meaning that the instance-of
- // instruction will always evaluate to false.
- result = InstanceOfResult.FALSE;
- }
-
- if (result == InstanceOfResult.UNKNOWN) {
- if (inType.isClassType()
- && isNeverInstantiatedDirectlyOrIndirectly(inType.asClassType().getClassType())) {
- // The type of the in-value is a program class, and is never instantiated directly or
- // indirectly. This, the in-value must be null, meaning that the instance-of instruction
- // will always evaluate to false.
- result = InstanceOfResult.FALSE;
- }
- }
-
- if (result == InstanceOfResult.UNKNOWN) {
- Value aliasedValue =
- inValue.getSpecificAliasedValue(
- value ->
- value.isDefinedByInstructionSatisfying(
- Instruction::isAssumeWithDynamicTypeAssumption));
- if (aliasedValue != null) {
- DynamicTypeWithUpperBound dynamicType =
- aliasedValue.getDefinition().asAssume().getDynamicTypeAssumption().getDynamicType();
- Nullability nullability = dynamicType.getNullability();
- if (nullability.isDefinitelyNull()) {
- result = InstanceOfResult.FALSE;
- } else if (dynamicType.getDynamicUpperBoundType().lessThanOrEqual(instanceOfType, appView)
- && (!inType.isNullable() || !nullability.isNullable())) {
- result = InstanceOfResult.TRUE;
- }
- }
- }
- }
- if (result != InstanceOfResult.UNKNOWN) {
- ConstNumber newInstruction =
- new ConstNumber(
- new Value(
- code.valueNumberGenerator.next(),
- TypeElement.getInt(),
- instanceOf.outValue().getLocalInfo()),
- result == InstanceOfResult.TRUE ? 1 : 0);
- it.replaceCurrentInstruction(newInstruction);
- return true;
- }
- return false;
- }
-
- private boolean isNeverInstantiatedDirectlyOrIndirectly(DexType type) {
- assert appView.appInfo().hasLiveness();
- assert type.isClassType();
- DexProgramClass clazz = asProgramClassOrNull(appView.definitionFor(type));
- return clazz != null
- && !appView.appInfo().withLiveness().isInstantiatedDirectlyOrIndirectly(clazz);
- }
-
public static void removeOrReplaceByDebugLocalWrite(
Instruction currentInstruction, InstructionListIterator it, Value inValue, Value outValue) {
if (outValue.hasLocalInfo() && outValue.getLocalInfo() != inValue.getLocalInfo()) {
@@ -1688,6 +470,53 @@
assert code.isConsistentSSA(appView);
}
+ public void rewriteKnownArrayLengthCalls(IRCode code) {
+ InstructionListIterator iterator = code.instructionListIterator();
+ while (iterator.hasNext()) {
+ Instruction current = iterator.next();
+ if (!current.isArrayLength()) {
+ continue;
+ }
+
+ ArrayLength arrayLength = current.asArrayLength();
+ if (arrayLength.hasOutValue() && arrayLength.outValue().hasLocalInfo()) {
+ continue;
+ }
+
+ Value array = arrayLength.array().getAliasedValue();
+ if (array.isPhi() || !arrayLength.array().isNeverNull() || array.hasLocalInfo()) {
+ continue;
+ }
+
+ AbstractValue abstractValue = array.getAbstractValue(appView, code.context());
+ if (!abstractValue.hasKnownArrayLength() && !array.isNeverNull()) {
+ continue;
+ }
+ Instruction arrayDefinition = array.getDefinition();
+ assert arrayDefinition != null;
+
+ Set<Phi> phiUsers = arrayLength.outValue().uniquePhiUsers();
+ if (arrayDefinition.isNewArrayEmpty()) {
+ Value size = arrayDefinition.asNewArrayEmpty().size();
+ arrayLength.outValue().replaceUsers(size);
+ iterator.removeOrReplaceByDebugLocalRead();
+ } else if (arrayDefinition.isNewArrayFilledData()) {
+ long size = arrayDefinition.asNewArrayFilledData().size;
+ if (size > Integer.MAX_VALUE) {
+ continue;
+ }
+ iterator.replaceCurrentInstructionWithConstInt(code, (int) size);
+ } else if (abstractValue.hasKnownArrayLength()) {
+ iterator.replaceCurrentInstructionWithConstInt(code, abstractValue.getKnownArrayLength());
+ } else {
+ continue;
+ }
+
+ phiUsers.forEach(Phi::removeTrivialPhi);
+ }
+ assert code.isConsistentSSA(appView);
+ }
+
/**
* If an instruction is known to be a binop/lit8 or binop//lit16 instruction, update the
* instruction to use its own constant that will be defined just before the instruction. This
@@ -2105,431 +934,6 @@
}
}
- private short[] computeArrayFilledData(Value[] values, int size, int elementSize) {
- for (Value v : values) {
- if (!v.isConstant()) {
- return null;
- }
- }
- if (elementSize == 1) {
- short[] result = new short[(size + 1) / 2];
- for (int i = 0; i < size; i += 2) {
- short value =
- (short) (values[i].getConstInstruction().asConstNumber().getIntValue() & 0xFF);
- if (i + 1 < size) {
- value |=
- (short)
- ((values[i + 1].getConstInstruction().asConstNumber().getIntValue() & 0xFF) << 8);
- }
- result[i / 2] = value;
- }
- return result;
- }
- assert elementSize == 2 || elementSize == 4 || elementSize == 8;
- int shortsPerConstant = elementSize / 2;
- short[] result = new short[size * shortsPerConstant];
- for (int i = 0; i < size; i++) {
- long value = values[i].getConstInstruction().asConstNumber().getRawValue();
- for (int part = 0; part < shortsPerConstant; part++) {
- result[i * shortsPerConstant + part] = (short) ((value >> (16 * part)) & 0xFFFFL);
- }
- }
- return result;
- }
-
- private static class FilledArrayConversionInfo {
-
- Value[] values;
- List<ArrayPut> arrayPutsToRemove;
- LinearFlowInstructionListIterator lastArrayPutIterator;
-
- public FilledArrayConversionInfo(int size) {
- values = new Value[size];
- arrayPutsToRemove = new ArrayList<>(size);
- }
- }
-
- private FilledArrayConversionInfo computeConversionInfo(
- FilledArrayCandidate candidate, LinearFlowInstructionListIterator it) {
- NewArrayEmpty newArrayEmpty = candidate.newArrayEmpty;
- assert it.peekPrevious() == newArrayEmpty;
- Value arrayValue = newArrayEmpty.outValue();
- int size = candidate.size;
-
- // aput-object allows any object for arrays of interfaces, but new-filled-array fails to verify
- // if types require a cast.
- // TODO(b/246971330): Check if adding a checked-cast would have the same observable result. E.g.
- // if aput-object throws a ClassCastException if given an object that does not implement the
- // desired interface, then we could add check-cast instructions for arguments we're not sure
- // about.
- DexType elementType = newArrayEmpty.type.toDimensionMinusOneType(dexItemFactory);
- boolean needsTypeCheck =
- !elementType.isPrimitiveType() && elementType != dexItemFactory.objectType;
-
- FilledArrayConversionInfo info = new FilledArrayConversionInfo(size);
- Value[] values = info.values;
- int remaining = size;
- Set<Instruction> users = newArrayEmpty.outValue().uniqueUsers();
- while (it.hasNext()) {
- Instruction instruction = it.next();
- BasicBlock block = instruction.getBlock();
- // If we encounter an instruction that can throw an exception we need to bail out of the
- // optimization so that we do not transform half-initialized arrays into fully initialized
- // arrays on exceptional edges. If the block has no handlers it is not observable so
- // we perform the rewriting.
- if (block.hasCatchHandlers() && instruction.instructionInstanceCanThrow()) {
- return null;
- }
- if (!users.contains(instruction)) {
- // If any instruction can transfer control between the new-array and the last array put
- // then it is not safe to move the new array to the point of the last put.
- if (block.hasCatchHandlers() && instruction.instructionTypeCanThrow()) {
- return null;
- }
- continue;
- }
- ArrayPut arrayPut = instruction.asArrayPut();
- // If the initialization sequence is broken by another use we cannot use a fill-array-data
- // instruction.
- if (arrayPut == null || arrayPut.array() != arrayValue) {
- return null;
- }
- if (!arrayPut.index().isConstNumber()) {
- return null;
- }
- if (arrayPut.instructionInstanceCanThrow()) {
- assert false;
- return null;
- }
- int index = arrayPut.index().getConstInstruction().asConstNumber().getIntValue();
- if (index < 0 || index >= values.length) {
- return null;
- }
- if (values[index] != null) {
- return null;
- }
- Value value = arrayPut.value();
- if (needsTypeCheck && !value.isAlwaysNull(appView)) {
- DexType valueDexType = value.getType().asReferenceType().toDexType(dexItemFactory);
- if (elementType.isArrayType()) {
- if (elementType != valueDexType) {
- return null;
- }
- } else if (valueDexType.isArrayType()) {
- // isSubtype asserts for this case.
- return null;
- } else if (valueDexType.isNullValueType()) {
- // Assume instructions can cause value.isAlwaysNull() == false while the DexType is null.
- // TODO(b/246971330): Figure out how to write a test in SimplifyArrayConstructionTest
- // that hits this case.
- } else {
- // TODO(b/246971330): When in d8 mode, we might still be able to see if this is true for
- // library types (which this helper does not do).
- if (appView.isSubtype(valueDexType, elementType).isPossiblyFalse()) {
- return null;
- }
- }
- }
- info.arrayPutsToRemove.add(arrayPut);
- values[index] = value;
- --remaining;
- if (remaining == 0) {
- info.lastArrayPutIterator = it;
- return info;
- }
- }
- return null;
- }
-
- private static class FilledArrayCandidate {
-
- final NewArrayEmpty newArrayEmpty;
- final int size;
- final boolean encodeAsFilledNewArray;
-
- public FilledArrayCandidate(
- NewArrayEmpty newArrayEmpty, int size, boolean encodeAsFilledNewArray) {
- assert size > 0;
- this.newArrayEmpty = newArrayEmpty;
- this.size = size;
- this.encodeAsFilledNewArray = encodeAsFilledNewArray;
- }
-
- public boolean useFilledNewArray() {
- return encodeAsFilledNewArray;
- }
-
- public boolean useFilledArrayData() {
- return !useFilledNewArray();
- }
- }
-
- private FilledArrayCandidate computeFilledArrayCandidate(
- Instruction instruction, RewriteArrayOptions options) {
- NewArrayEmpty newArrayEmpty = instruction.asNewArrayEmpty();
- if (newArrayEmpty == null) {
- return null;
- }
- if (instruction.getLocalInfo() != null) {
- return null;
- }
- if (!newArrayEmpty.size().isConstant()) {
- return null;
- }
- int size = newArrayEmpty.size().getConstInstruction().asConstNumber().getIntValue();
- if (!options.isPotentialSize(size)) {
- return null;
- }
- DexType arrayType = newArrayEmpty.type;
- boolean encodeAsFilledNewArray = canUseFilledNewArray(arrayType, size, options);
- if (!encodeAsFilledNewArray && !canUseFilledArrayData(arrayType, size, options)) {
- return null;
- }
- // Check that all arguments to the array is the array type or that the array is type Object[].
- if (!options.canUseSubTypesInFilledNewArray()
- && arrayType != dexItemFactory.objectArrayType
- && !arrayType.isPrimitiveArrayType()) {
- DexType elementType = arrayType.toArrayElementType(dexItemFactory);
- for (Instruction uniqueUser : newArrayEmpty.outValue().uniqueUsers()) {
- if (uniqueUser.isArrayPut()
- && uniqueUser.asArrayPut().array() == newArrayEmpty.outValue()
- && !checkTypeOfArrayPut(uniqueUser.asArrayPut(), elementType)) {
- return null;
- }
- }
- }
- return new FilledArrayCandidate(newArrayEmpty, size, encodeAsFilledNewArray);
- }
-
- private boolean checkTypeOfArrayPut(ArrayPut arrayPut, DexType elementType) {
- TypeElement valueType = arrayPut.value().getType();
- if (!valueType.isPrimitiveType() && elementType == dexItemFactory.objectType) {
- return true;
- }
- if (valueType.isNullType() && !elementType.isPrimitiveType()) {
- return true;
- }
- if (elementType.isArrayType()) {
- if (valueType.isNullType()) {
- return true;
- }
- ArrayTypeElement arrayTypeElement = valueType.asArrayType();
- if (arrayTypeElement == null
- || arrayTypeElement.getNesting() != elementType.getNumberOfLeadingSquareBrackets()) {
- return false;
- }
- valueType = arrayTypeElement.getBaseType();
- elementType = elementType.toBaseType(dexItemFactory);
- }
- assert !valueType.isArrayType();
- assert !elementType.isArrayType();
- if (valueType.isPrimitiveType() && !elementType.isPrimitiveType()) {
- return false;
- }
- if (valueType.isPrimitiveType()) {
- return true;
- }
- DexClass clazz = appView.definitionFor(elementType);
- if (clazz == null) {
- return false;
- }
- return clazz.isInterface() || valueType.isClassType(elementType);
- }
-
- private boolean canUseFilledNewArray(DexType arrayType, int size, RewriteArrayOptions options) {
- if (size < options.minSizeForFilledNewArray) {
- return false;
- }
- // filled-new-array is implemented only for int[] and Object[].
- // For int[], using filled-new-array is usually smaller than filled-array-data.
- // filled-new-array supports up to 5 registers before it's filled-new-array/range.
- if (!arrayType.isPrimitiveArrayType()) {
- if (size > options.maxSizeForFilledNewArrayOfReferences) {
- return false;
- }
- if (arrayType == dexItemFactory.stringArrayType) {
- return options.canUseFilledNewArrayOfStrings();
- }
- if (!options.canUseFilledNewArrayOfNonStringObjects()) {
- return false;
- }
- if (!options.canUseFilledNewArrayOfArrays()
- && arrayType.getNumberOfLeadingSquareBrackets() > 1) {
- return false;
- }
- return true;
- }
- if (arrayType == dexItemFactory.intArrayType) {
- return size <= options.maxSizeForFilledNewArrayOfInts;
- }
- return false;
- }
-
- private boolean canUseFilledArrayData(DexType arrayType, int size, RewriteArrayOptions options) {
- // If there is only one element it is typically smaller to generate the array put
- // instruction instead of fill array data.
- if (size < options.minSizeForFilledArrayData || size > options.maxSizeForFilledArrayData) {
- return false;
- }
- return arrayType.isPrimitiveArrayType();
- }
-
- /**
- * Replace new-array followed by stores of constants to all entries with new-array and
- * fill-array-data / filled-new-array.
- *
- * <p>The format of the new-array and its puts must be of the form:
- *
- * <pre>
- * v0 <- new-array T vSize
- * ...
- * array-put v0 vValue1 vIndex1
- * ...
- * array-put v0 vValueN vIndexN
- * </pre>
- *
- * <p>The flow between the array v0 and its puts must be linear with no other uses of v0 besides
- * the array-put instructions, thus any no intermediate instruction (... above) must use v0 and
- * also cannot have catch handlers that would transfer out control (those could then have uses of
- * v0).
- *
- * <p>The allocation of the new-array can itself have catch handlers, in which case, those are to
- * remain active on the translated code. Translated code can have two forms.
- *
- * <p>The first is using the original array allocation and filling in its data if it can be
- * encoded:
- *
- * <pre>
- * v0 <- new-array T vSize
- * filled-array-data v0
- * ...
- * ...
- * </pre>
- *
- * The data payload is encoded directly in the instruction so no dependencies are needed for
- * filling the data array. Thus, the fill is inserted at the point of the allocation. If the
- * allocation has catch handlers its block must be split and the handlers put on the fill
- * instruction too. This is correct only because there are no exceptional transfers in (...) that
- * could observe the early initialization of the data.
- *
- * <p>The second is using filled-new-array and has the form:
- *
- * <pre>
- * ...
- * ...
- * v0 <- filled-new-array T vValue1 ... vValueN
- * </pre>
- *
- * Here the correctness relies on no exceptional transfers in (...) that could observe the missing
- * allocation of the array. The late allocation ensures that the values are available at
- * allocation time. If the original allocation has catch handlers then the new allocation needs to
- * link those too. In general that may require splitting the block twice so that the new
- * allocation is the single throwing instruction in its block.
- */
- public void simplifyArrayConstruction(IRCode code) {
- if (options.isGeneratingClassFiles()) {
- return;
- }
- WorkList<BasicBlock> worklist = WorkList.newIdentityWorkList(code.blocks);
- while (worklist.hasNext()) {
- BasicBlock block = worklist.next();
- simplifyArrayConstructionBlock(block, worklist, code, options);
- }
- }
-
- private void simplifyArrayConstructionBlock(
- BasicBlock block, WorkList<BasicBlock> worklist, IRCode code, InternalOptions options) {
- RewriteArrayOptions rewriteOptions = options.rewriteArrayOptions();
- InstructionListIterator it = block.listIterator(code);
- while (it.hasNext()) {
- FilledArrayCandidate candidate = computeFilledArrayCandidate(it.next(), rewriteOptions);
- if (candidate == null) {
- continue;
- }
- FilledArrayConversionInfo info =
- computeConversionInfo(
- candidate, new LinearFlowInstructionListIterator(code, block, it.nextIndex()));
- if (info == null) {
- continue;
- }
-
- Instruction instructionAfterCandidate = it.peekNext();
- NewArrayEmpty newArrayEmpty = candidate.newArrayEmpty;
- DexType arrayType = newArrayEmpty.type;
- int size = candidate.size;
- Set<Instruction> instructionsToRemove = SetUtils.newIdentityHashSet(size + 1);
- if (candidate.useFilledNewArray()) {
- assert newArrayEmpty.getLocalInfo() == null;
- Instruction lastArrayPut = info.lastArrayPutIterator.peekPrevious();
- Value invokeValue = code.createValue(newArrayEmpty.getOutType(), null);
- InvokeNewArray invoke =
- new InvokeNewArray(arrayType, invokeValue, Arrays.asList(info.values));
- invoke.setPosition(lastArrayPut.getPosition());
- for (Value value : newArrayEmpty.inValues()) {
- value.removeUser(newArrayEmpty);
- }
- newArrayEmpty.outValue().replaceUsers(invokeValue);
- instructionsToRemove.add(newArrayEmpty);
-
- boolean originalAllocationPointHasHandlers = block.hasCatchHandlers();
- boolean insertionPointHasHandlers = lastArrayPut.getBlock().hasCatchHandlers();
-
- if (!insertionPointHasHandlers && !originalAllocationPointHasHandlers) {
- info.lastArrayPutIterator.add(invoke);
- } else {
- BasicBlock insertionBlock = info.lastArrayPutIterator.split(code);
- if (originalAllocationPointHasHandlers) {
- if (!insertionBlock.isTrivialGoto()) {
- BasicBlock blockAfterInsertion = insertionBlock.listIterator(code).split(code);
- assert insertionBlock.isTrivialGoto();
- worklist.addIfNotSeen(blockAfterInsertion);
- }
- insertionBlock.moveCatchHandlers(block);
- } else {
- worklist.addIfNotSeen(insertionBlock);
- }
- insertionBlock.listIterator(code).add(invoke);
- }
- } else {
- assert candidate.useFilledArrayData();
- int elementSize = arrayType.elementSizeForPrimitiveArrayType();
- short[] contents = computeArrayFilledData(info.values, size, elementSize);
- if (contents == null) {
- continue;
- }
- // fill-array-data requires the new-array-empty instruction to remain, as it does not
- // itself create an array.
- NewArrayFilledData fillArray =
- new NewArrayFilledData(newArrayEmpty.outValue(), elementSize, size, contents);
- fillArray.setPosition(newArrayEmpty.getPosition());
- BasicBlock newBlock =
- it.addThrowingInstructionToPossiblyThrowingBlock(code, null, fillArray, options);
- if (newBlock != null) {
- worklist.addIfNotSeen(newBlock);
- }
- }
-
- instructionsToRemove.addAll(info.arrayPutsToRemove);
- Set<BasicBlock> visitedBlocks = Sets.newIdentityHashSet();
- for (Instruction instruction : instructionsToRemove) {
- BasicBlock ownerBlock = instruction.getBlock();
- // If owner block is null, then the instruction has been removed already. We can't rely on
- // just having the block pointer nulled, so the visited blocks guards reprocessing.
- if (ownerBlock != null && visitedBlocks.add(ownerBlock)) {
- InstructionListIterator removeIt = ownerBlock.listIterator(code);
- while (removeIt.hasNext()) {
- if (instructionsToRemove.contains(removeIt.next())) {
- removeIt.removeOrReplaceByDebugLocalRead();
- }
- }
- }
- }
-
- // The above has invalidated the block iterator so reset it and continue.
- it = block.listIterator(code, instructionAfterCandidate);
- }
- }
-
// TODO(mikaelpeltier) Manage that from and to instruction do not belong to the same block.
private static boolean hasLocalOrLineChangeBetween(
Instruction from, Instruction to, DexString localVar) {
@@ -2597,309 +1001,6 @@
}
}
- static class ControlFlowSimplificationResult {
-
- private boolean anyAffectedValues;
- private boolean anySimplifications;
-
- private ControlFlowSimplificationResult(boolean anyAffectedValues, boolean anySimplifications) {
- assert !anyAffectedValues || anySimplifications;
- this.anyAffectedValues = anyAffectedValues;
- this.anySimplifications = anySimplifications;
- }
-
- public boolean anyAffectedValues() {
- return anyAffectedValues;
- }
-
- public boolean anySimplifications() {
- return anySimplifications;
- }
- }
-
- public boolean simplifyControlFlow(IRCode code) {
- boolean anyAffectedValues = rewriteSwitch(code);
- anyAffectedValues |= simplifyIf(code).anyAffectedValues();
- return anyAffectedValues;
- }
-
- public ControlFlowSimplificationResult simplifyIf(IRCode code) {
- BasicBlockBehavioralSubsumption behavioralSubsumption =
- new BasicBlockBehavioralSubsumption(appView, code);
- boolean simplified = false;
- for (BasicBlock block : code.blocks) {
- // Skip removed (= unreachable) blocks.
- if (block.getNumber() != 0 && block.getPredecessors().isEmpty()) {
- continue;
- }
- if (block.exit().isIf()) {
- flipIfBranchesIfNeeded(code, block);
- if (rewriteIfWithConstZero(code, block)) {
- simplified = true;
- }
-
- if (simplifyKnownBooleanCondition(code, block)) {
- simplified = true;
- if (!block.exit().isIf()) {
- continue;
- }
- }
-
- // Simplify if conditions when possible.
- If theIf = block.exit().asIf();
- if (theIf.isZeroTest()) {
- if (simplifyIfZeroTest(code, block, theIf)) {
- simplified = true;
- continue;
- }
- } else {
- if (simplifyNonIfZeroTest(code, block, theIf)) {
- simplified = true;
- continue;
- }
- }
-
- // Unable to determine which branch will be taken. Check if the true target can safely be
- // rewritten to the false target.
- if (behavioralSubsumption.isSubsumedBy(
- theIf.inValues().get(0), theIf.getTrueTarget(), theIf.fallthroughBlock())) {
- simplifyIfWithKnownCondition(code, block, theIf, theIf.fallthroughBlock());
- simplified = true;
- }
- }
- }
- Set<Value> affectedValues = code.removeUnreachableBlocks();
- if (!affectedValues.isEmpty()) {
- new TypeAnalysis(appView).narrowing(affectedValues);
- }
- assert code.isConsistentSSA(appView);
- return new ControlFlowSimplificationResult(!affectedValues.isEmpty(), simplified);
- }
-
- private boolean simplifyIfZeroTest(IRCode code, BasicBlock block, If theIf) {
- Value lhs = theIf.lhs();
- Value lhsRoot = lhs.getAliasedValue();
- if (lhsRoot.isConstNumber()) {
- ConstNumber cond = lhsRoot.getConstInstruction().asConstNumber();
- BasicBlock target = theIf.targetFromCondition(cond);
- simplifyIfWithKnownCondition(code, block, theIf, target);
- return true;
- }
-
- if (theIf.isNullTest()) {
- assert theIf.getType() == IfType.EQ || theIf.getType() == IfType.NE;
-
- if (lhs.isAlwaysNull(appView)) {
- simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromNullObject());
- return true;
- }
-
- if (lhs.isNeverNull()) {
- simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromNonNullObject());
- return true;
- }
- }
-
- if (theIf.getType() == IfType.EQ || theIf.getType() == IfType.NE) {
- AbstractValue lhsAbstractValue = lhs.getAbstractValue(appView, code.context());
- if (lhsAbstractValue.isConstantOrNonConstantNumberValue()
- && !lhsAbstractValue.asConstantOrNonConstantNumberValue().containsInt(0)) {
- // Value doesn't contain zero at all.
- simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromCondition(1));
- return true;
- }
- }
-
- if (lhs.hasValueRange()) {
- LongInterval interval = lhs.getValueRange();
- if (!interval.containsValue(0)) {
- // Interval doesn't contain zero at all.
- int sign = Long.signum(interval.getMin());
- simplifyIfWithKnownCondition(code, block, theIf, sign);
- return true;
- }
-
- // Interval contains zero.
- switch (theIf.getType()) {
- case GE:
- case LT:
- // [a, b] >= 0 is always true if a >= 0.
- // [a, b] < 0 is always false if a >= 0.
- // In both cases a zero condition takes the right branch.
- if (interval.getMin() == 0) {
- simplifyIfWithKnownCondition(code, block, theIf, 0);
- return true;
- }
- break;
-
- case LE:
- case GT:
- // [a, b] <= 0 is always true if b <= 0.
- // [a, b] > 0 is always false if b <= 0.
- // In both cases a zero condition takes the right branch.
- if (interval.getMax() == 0) {
- simplifyIfWithKnownCondition(code, block, theIf, 0);
- return true;
- }
- break;
-
- case EQ:
- case NE:
- // Only a single element interval [0, 0] can be dealt with here.
- // Such intervals should have been replaced by constants.
- assert !interval.isSingleValue();
- break;
- }
- }
- return false;
- }
-
- private boolean simplifyNonIfZeroTest(IRCode code, BasicBlock block, If theIf) {
- Value lhs = theIf.lhs();
- Value lhsRoot = lhs.getAliasedValue();
- Value rhs = theIf.rhs();
- Value rhsRoot = rhs.getAliasedValue();
- if (lhsRoot == rhsRoot) {
- // Comparing the same value.
- simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromCondition(0));
- return true;
- }
-
- if (lhsRoot.isDefinedByInstructionSatisfying(Instruction::isCreatingInstanceOrArray)
- && rhsRoot.isDefinedByInstructionSatisfying(Instruction::isCreatingInstanceOrArray)) {
- // Comparing two newly created objects.
- assert theIf.getType() == IfType.EQ || theIf.getType() == IfType.NE;
- simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromCondition(1));
- return true;
- }
-
- if (lhsRoot.isConstNumber() && rhsRoot.isConstNumber()) {
- // Zero test with a constant of comparison between between two constants.
- ConstNumber left = lhsRoot.getConstInstruction().asConstNumber();
- ConstNumber right = rhsRoot.getConstInstruction().asConstNumber();
- BasicBlock target = theIf.targetFromCondition(left, right);
- simplifyIfWithKnownCondition(code, block, theIf, target);
- return true;
- }
-
- if (theIf.getType() == IfType.EQ || theIf.getType() == IfType.NE) {
- AbstractValue lhsAbstractValue = lhs.getAbstractValue(appView, code.context());
- AbstractValue rhsAbstractValue = rhs.getAbstractValue(appView, code.context());
- if (lhsAbstractValue.isConstantOrNonConstantNumberValue()
- && rhsAbstractValue.isConstantOrNonConstantNumberValue()) {
- ConstantOrNonConstantNumberValue lhsNumberValue =
- lhsAbstractValue.asConstantOrNonConstantNumberValue();
- ConstantOrNonConstantNumberValue rhsNumberValue =
- rhsAbstractValue.asConstantOrNonConstantNumberValue();
- if (!lhsNumberValue.mayOverlapWith(rhsNumberValue)) {
- // No overlap.
- simplifyIfWithKnownCondition(code, block, theIf, 1);
- return true;
- }
- }
- }
-
- if (lhs.hasValueRange() && rhs.hasValueRange()) {
- // Zero test with a value range, or comparison between between two values,
- // each with a value ranges.
- LongInterval leftRange = lhs.getValueRange();
- LongInterval rightRange = rhs.getValueRange();
- // Two overlapping ranges. Check for single point overlap.
- if (!leftRange.overlapsWith(rightRange)) {
- // No overlap.
- int cond = Long.signum(leftRange.getMin() - rightRange.getMin());
- simplifyIfWithKnownCondition(code, block, theIf, cond);
- return true;
- }
-
- // The two intervals overlap. We can simplify if they overlap at the end points.
- switch (theIf.getType()) {
- case LT:
- case GE:
- // [a, b] < [c, d] is always false when a == d.
- // [a, b] >= [c, d] is always true when a == d.
- // In both cases 0 condition will choose the right branch.
- if (leftRange.getMin() == rightRange.getMax()) {
- simplifyIfWithKnownCondition(code, block, theIf, 0);
- return true;
- }
- break;
- case GT:
- case LE:
- // [a, b] > [c, d] is always false when b == c.
- // [a, b] <= [c, d] is always true when b == c.
- // In both cases 0 condition will choose the right branch.
- if (leftRange.getMax() == rightRange.getMin()) {
- simplifyIfWithKnownCondition(code, block, theIf, 0);
- return true;
- }
- break;
- case EQ:
- case NE:
- // Since there is overlap EQ and NE cannot be determined.
- break;
- }
- }
-
- if (theIf.getType() == IfType.EQ || theIf.getType() == IfType.NE) {
- ProgramMethod context = code.context();
- AbstractValue abstractValue = lhs.getAbstractValue(appView, context);
- if (abstractValue.isSingleConstClassValue()) {
- AbstractValue otherAbstractValue = rhs.getAbstractValue(appView, context);
- if (otherAbstractValue.isSingleConstClassValue()) {
- SingleConstClassValue singleConstClassValue = abstractValue.asSingleConstClassValue();
- SingleConstClassValue otherSingleConstClassValue =
- otherAbstractValue.asSingleConstClassValue();
- simplifyIfWithKnownCondition(
- code,
- block,
- theIf,
- BooleanUtils.intValue(
- singleConstClassValue.getType() != otherSingleConstClassValue.getType()));
- return true;
- }
- return false;
- }
-
- if (abstractValue.isSingleFieldValue()) {
- AbstractValue otherAbstractValue = rhs.getAbstractValue(appView, context);
- if (otherAbstractValue.isSingleFieldValue()) {
- SingleFieldValue singleFieldValue = abstractValue.asSingleFieldValue();
- SingleFieldValue otherSingleFieldValue = otherAbstractValue.asSingleFieldValue();
- if (singleFieldValue.getField() == otherSingleFieldValue.getField()) {
- simplifyIfWithKnownCondition(code, block, theIf, 0);
- return true;
- }
-
- DexClass holder = appView.definitionForHolder(singleFieldValue.getField());
- DexEncodedField field = singleFieldValue.getField().lookupOnClass(holder);
- if (field != null && field.isEnum()) {
- DexClass otherHolder = appView.definitionForHolder(otherSingleFieldValue.getField());
- DexEncodedField otherField =
- otherSingleFieldValue.getField().lookupOnClass(otherHolder);
- if (otherField != null && otherField.isEnum()) {
- simplifyIfWithKnownCondition(code, block, theIf, 1);
- return true;
- }
- }
- }
- }
- }
-
- return false;
- }
-
- private void simplifyIfWithKnownCondition(
- IRCode code, BasicBlock block, If theIf, BasicBlock target) {
- BasicBlock deadTarget =
- target == theIf.getTrueTarget() ? theIf.fallthroughBlock() : theIf.getTrueTarget();
- rewriteIfToGoto(code, block, theIf, target, deadTarget);
- }
-
- private void simplifyIfWithKnownCondition(IRCode code, BasicBlock block, If theIf, int cond) {
- simplifyIfWithKnownCondition(code, block, theIf, theIf.targetFromCondition(cond));
- }
-
/**
* 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.
@@ -3380,152 +1481,6 @@
assert code.isConsistentSSA(appView);
}
- /* Identify simple diamond shapes converting boolean true/false to 1/0. We consider the forms:
- *
- * (1)
- *
- * [dbg pos x] [dbg pos x]
- * ifeqz booleanValue ifnez booleanValue
- * / \ / \
- * [dbg pos x][dbg pos x] [dbg pos x][dbg pos x]
- * [const 0] [const 1] [const 1] [const 0]
- * goto goto goto goto
- * \ / \ /
- * phi(0, 1) phi(1, 0)
- *
- * which can be replaced by a fallthrough and the phi value can be replaced
- * with the boolean value itself.
- *
- * (2)
- *
- * [dbg pos x] [dbg pos x]
- * ifeqz booleanValue ifnez booleanValue
- * / \ / \
- * [dbg pos x][dbg pos x] [dbg pos x][dbg pos x]
- * [const 1] [const 0] [const 0] [const 1]
- * goto goto goto goto
- * \ / \ /
- * phi(1, 0) phi(0, 1)
- *
- * 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, BasicBlock block) {
- If theIf = block.exit().asIf();
- Value testValue = theIf.inValues().get(0);
- if (theIf.isZeroTest() && testValue.knownToBeBoolean()) {
- BasicBlock trueBlock = theIf.getTrueTarget();
- BasicBlock falseBlock = theIf.fallthroughBlock();
- if (isBlockSupportedBySimplifyKnownBooleanCondition(trueBlock) &&
- isBlockSupportedBySimplifyKnownBooleanCondition(falseBlock) &&
- trueBlock.getSuccessors().get(0) == falseBlock.getSuccessors().get(0)) {
- BasicBlock targetBlock = trueBlock.getSuccessors().get(0);
- if (targetBlock.getPredecessors().size() == 2) {
- int trueIndex = targetBlock.getPredecessors().indexOf(trueBlock);
- int falseIndex = trueIndex == 0 ? 1 : 0;
- int deadPhis = 0;
- // Locate the phis that have the same value as the boolean and replace them
- // by the boolean in all users.
- for (Phi phi : targetBlock.getPhis()) {
- Value trueValue = phi.getOperand(trueIndex);
- Value falseValue = phi.getOperand(falseIndex);
- if (trueValue.isConstNumber() && falseValue.isConstNumber()) {
- ConstNumber trueNumber = trueValue.getConstInstruction().asConstNumber();
- ConstNumber falseNumber = falseValue.getConstInstruction().asConstNumber();
- if ((theIf.getType() == IfType.EQ
- && trueNumber.isIntegerZero()
- && falseNumber.isIntegerOne())
- || (theIf.getType() == IfType.NE
- && trueNumber.isIntegerOne()
- && falseNumber.isIntegerZero())) {
- phi.replaceUsers(testValue);
- deadPhis++;
- } else if ((theIf.getType() == IfType.NE
- && trueNumber.isIntegerZero()
- && falseNumber.isIntegerOne())
- || (theIf.getType() == IfType.EQ
- && trueNumber.isIntegerOne()
- && falseNumber.isIntegerZero())) {
- Value newOutValue = code.createValue(phi.getType(), phi.getLocalInfo());
- ConstNumber cstToUse = trueNumber.isIntegerOne() ? trueNumber : falseNumber;
- BasicBlock phiBlock = phi.getBlock();
- Position phiPosition = phiBlock.getPosition();
- int insertIndex = 0;
- if (cstToUse.getBlock() == trueBlock || cstToUse.getBlock() == falseBlock) {
- // The constant belongs to the block to remove, create a new one.
- cstToUse = ConstNumber.copyOf(code, cstToUse);
- cstToUse.setBlock(phiBlock);
- cstToUse.setPosition(phiPosition);
- phiBlock.getInstructions().add(insertIndex++, cstToUse);
- }
- phi.replaceUsers(newOutValue);
- Instruction newInstruction =
- Xor.create(NumericType.INT, newOutValue, testValue, cstToUse.outValue());
- newInstruction.setBlock(phiBlock);
- // The xor is replacing a phi so it does not have an actual position.
- newInstruction.setPosition(phiPosition);
- phiBlock.listIterator(code, insertIndex).add(newInstruction);
- deadPhis++;
- }
- }
- }
- // 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(code, block, theIf, trueBlock, falseBlock);
- return true;
- }
- return deadPhis > 0;
- }
- }
- }
- return false;
- }
-
- private boolean isBlockSupportedBySimplifyKnownBooleanCondition(BasicBlock b) {
- if (b.isTrivialGoto()) {
- return true;
- }
-
- int instructionSize = b.getInstructions().size();
- if (b.exit().isGoto() && (instructionSize == 2 || instructionSize == 3)) {
- Instruction constInstruction = b.getInstructions().get(instructionSize - 2);
- if (constInstruction.isConstNumber()) {
- if (!constInstruction.asConstNumber().isIntegerOne() &&
- !constInstruction.asConstNumber().isIntegerZero()) {
- return false;
- }
- if (instructionSize == 2) {
- return true;
- }
- Instruction firstInstruction = b.getInstructions().getFirst();
- if (firstInstruction.isDebugPosition()) {
- assert b.getPredecessors().size() == 1;
- BasicBlock predecessorBlock = b.getPredecessors().get(0);
- InstructionIterator it = predecessorBlock.iterator(predecessorBlock.exit());
- Instruction previousPosition = null;
- while (it.hasPrevious() && !(previousPosition = it.previous()).isDebugPosition()) {
- // Intentionally empty.
- }
- if (previousPosition != null) {
- return previousPosition.getPosition() == firstInstruction.getPosition();
- }
- }
- }
- }
-
- return false;
- }
-
- private void rewriteIfToGoto(
- IRCode code, BasicBlock block, If theIf, BasicBlock target, BasicBlock deadTarget) {
- deadTarget.unlinkSinglePredecessorSiblingsAllowed();
- assert theIf == block.exit();
- block.replaceLastInstruction(new Goto(), code);
- assert block.exit().isGoto();
- assert block.exit().asGoto().getTarget() == target;
- }
-
private void insertNotNullCheck(
BasicBlock block,
InstructionListIterator iterator,
@@ -3547,101 +1502,6 @@
assert block.exit().asGoto().getTarget() == target;
}
- private boolean rewriteIfWithConstZero(IRCode code, BasicBlock block) {
- If theIf = block.exit().asIf();
- if (theIf.isZeroTest()) {
- return false;
- }
-
- Value leftValue = theIf.lhs();
- Value rightValue = theIf.rhs();
- if (leftValue.isConstNumber() || rightValue.isConstNumber()) {
- if (leftValue.isConstNumber()) {
- if (leftValue.getConstInstruction().asConstNumber().isZero()) {
- If ifz = new If(theIf.getType().forSwappedOperands(), rightValue);
- block.replaceLastInstruction(ifz, code);
- assert block.exit() == ifz;
- return true;
- }
- } else if (rightValue.getConstInstruction().asConstNumber().isZero()) {
- If ifz = new If(theIf.getType(), leftValue);
- block.replaceLastInstruction(ifz, code);
- assert block.exit() == ifz;
- return true;
- }
- }
-
- return false;
- }
-
- private boolean flipIfBranchesIfNeeded(IRCode code, BasicBlock block) {
- If theIf = block.exit().asIf();
- BasicBlock trueTarget = theIf.getTrueTarget();
- BasicBlock fallthrough = theIf.fallthroughBlock();
- assert trueTarget != fallthrough;
-
- if (!fallthrough.isSimpleAlwaysThrowingPath() || trueTarget.isSimpleAlwaysThrowingPath()) {
- return false;
- }
-
- // In case fall-through block always throws there is a good chance that it
- // is created for error checks and 'trueTarget' represents most more common
- // non-error case. Flipping the if in this case may result in faster code
- // on older Android versions.
- List<Value> inValues = theIf.inValues();
- If newIf = new If(theIf.getType().inverted(), inValues);
- block.replaceLastInstruction(newIf, code);
- block.swapSuccessors(trueTarget, fallthrough);
- return true;
- }
-
- public void rewriteKnownArrayLengthCalls(IRCode code) {
- InstructionListIterator iterator = code.instructionListIterator();
- while (iterator.hasNext()) {
- Instruction current = iterator.next();
- if (!current.isArrayLength()) {
- continue;
- }
-
- ArrayLength arrayLength = current.asArrayLength();
- if (arrayLength.hasOutValue() && arrayLength.outValue().hasLocalInfo()) {
- continue;
- }
-
- Value array = arrayLength.array().getAliasedValue();
- if (array.isPhi() || !arrayLength.array().isNeverNull() || array.hasLocalInfo()) {
- continue;
- }
-
- AbstractValue abstractValue = array.getAbstractValue(appView, code.context());
- if (!abstractValue.hasKnownArrayLength() && !array.isNeverNull()) {
- continue;
- }
- Instruction arrayDefinition = array.getDefinition();
- assert arrayDefinition != null;
-
- Set<Phi> phiUsers = arrayLength.outValue().uniquePhiUsers();
- if (arrayDefinition.isNewArrayEmpty()) {
- Value size = arrayDefinition.asNewArrayEmpty().size();
- arrayLength.outValue().replaceUsers(size);
- iterator.removeOrReplaceByDebugLocalRead();
- } else if (arrayDefinition.isNewArrayFilledData()) {
- long size = arrayDefinition.asNewArrayFilledData().size;
- if (size > Integer.MAX_VALUE) {
- continue;
- }
- iterator.replaceCurrentInstructionWithConstInt(code, (int) size);
- } else if (abstractValue.hasKnownArrayLength()) {
- iterator.replaceCurrentInstructionWithConstInt(code, abstractValue.getKnownArrayLength());
- } else {
- continue;
- }
-
- phiUsers.forEach(Phi::removeTrivialPhi);
- }
- assert code.isConsistentSSA(appView);
- }
-
/**
* 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
@@ -3891,34 +1751,6 @@
iterator.add(new InvokeVirtual(printLn, null, ImmutableList.of(out, empty)));
}
- public static void replaceUnusedArgumentTrivialPhis(UnusedArgument unusedArgument) {
- replaceTrivialPhis(unusedArgument.outValue());
- for (Phi phiUser : unusedArgument.outValue().uniquePhiUsers()) {
- phiUser.removeTrivialPhi();
- }
- assert !unusedArgument.outValue().hasPhiUsers();
- }
-
- public static void ensureDirectStringNewToInit(IRCode code, DexItemFactory dexItemFactory) {
- for (Instruction instruction : code.instructions()) {
- if (instruction.isInvokeDirect()) {
- InvokeDirect invoke = instruction.asInvokeDirect();
- DexMethod method = invoke.getInvokedMethod();
- if (dexItemFactory.isConstructor(method)
- && method.holder == dexItemFactory.stringType
- && invoke.getReceiver().isPhi()) {
- NewInstance newInstance = findNewInstance(invoke.getReceiver().asPhi());
- replaceTrivialPhis(newInstance.outValue());
- if (invoke.getReceiver().isPhi()) {
- throw new CompilationError(
- "Failed to remove trivial phis between new-instance and <init>");
- }
- newInstance.markNoSpilling();
- }
- }
- }
- }
-
// The javac fix for JDK-8272564 has to be rewritten back to invoke-virtual on Object if the
// method with an Object signature is not defined on the interface. See
// https://bugs.openjdk.java.net/browse/JDK-8272564
@@ -3943,66 +1775,4 @@
}
}
}
-
- private static NewInstance findNewInstance(Phi phi) {
- Set<Phi> seen = Sets.newIdentityHashSet();
- Set<Value> values = Sets.newIdentityHashSet();
- recursiveAddOperands(phi, seen, values);
- if (values.size() != 1) {
- throw new CompilationError("Failed to identify unique new-instance for <init>");
- }
- Value newInstanceValue = values.iterator().next();
- if (newInstanceValue.definition == null || !newInstanceValue.definition.isNewInstance()) {
- throw new CompilationError("Invalid defining value for call to <init>");
- }
- return newInstanceValue.definition.asNewInstance();
- }
-
- private static void recursiveAddOperands(Phi phi, Set<Phi> seen, Set<Value> values) {
- for (Value operand : phi.getOperands()) {
- if (!operand.isPhi()) {
- values.add(operand);
- } else {
- Phi phiOp = operand.asPhi();
- if (seen.add(phiOp)) {
- recursiveAddOperands(phiOp, seen, values);
- }
- }
- }
- }
-
- // We compute the set of strongly connected phis making use of the out value and replace all
- // trivial ones by the out value.
- // This is a simplified variant of the removeRedundantPhis algorithm in Section 3.2 of:
- // http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf
- private static void replaceTrivialPhis(Value outValue) {
- List<Set<Value>> components = new SCC<Value>(Value::uniquePhiUsers).computeSCC(outValue);
- for (int i = components.size() - 1; i >= 0; i--) {
- Set<Value> component = components.get(i);
- if (component.size() == 1 && component.iterator().next() == outValue) {
- continue;
- }
- Set<Phi> trivialPhis = Sets.newIdentityHashSet();
- for (Value value : component) {
- boolean isTrivial = true;
- Phi p = value.asPhi();
- for (Value op : p.getOperands()) {
- if (op != outValue && !component.contains(op)) {
- isTrivial = false;
- break;
- }
- }
- if (isTrivial) {
- trivialPhis.add(p);
- }
- }
- for (Phi trivialPhi : trivialPhis) {
- for (Value op : trivialPhi.getOperands()) {
- op.removePhiUser(trivialPhi);
- }
- trivialPhi.replaceUsers(outValue);
- trivialPhi.getBlock().removePhi(trivialPhi);
- }
- }
- }
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java b/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
index 677da9c..b4fa5a6 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ConstantCanonicalizer.java
@@ -41,6 +41,7 @@
import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.ir.code.StaticGet;
import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.conversion.passes.BranchSimplifier;
import com.android.tools.r8.utils.OptionalBool;
import com.android.tools.r8.utils.WorkList;
import com.google.common.collect.Sets;
@@ -65,17 +66,16 @@
private static final int MAX_CANONICALIZED_CONSTANT = 22;
private final AppView<?> appView;
- private final CodeRewriter codeRewriter;
+ private final BranchSimplifier branchSimplifier;
private final ProgramMethod context;
private final IRCode code;
private OptionalBool isAccessingVolatileField = OptionalBool.unknown();
private Set<InstanceGet> ineligibleInstanceGetInstructions;
- public ConstantCanonicalizer(
- AppView<?> appView, CodeRewriter codeRewriter, ProgramMethod context, IRCode code) {
+ public ConstantCanonicalizer(AppView<?> appView, ProgramMethod context, IRCode code) {
this.appView = appView;
- this.codeRewriter = codeRewriter;
+ this.branchSimplifier = new BranchSimplifier(appView);
this.context = context;
this.code = code;
}
@@ -288,7 +288,7 @@
shouldSimplifyIfs |= code.removeAllDeadAndTrivialPhis();
if (shouldSimplifyIfs) {
- codeRewriter.simplifyIf(code);
+ branchSimplifier.simplifyIf(code);
}
assert code.isConsistentSSA(appView);
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 b7d7b10..fcefb79 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
@@ -20,6 +20,7 @@
import com.android.tools.r8.ir.code.Phi;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.code.ValueIsDeadAnalysis;
+import com.android.tools.r8.ir.conversion.passes.BranchSimplifier;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
import com.android.tools.r8.utils.Box;
import com.android.tools.r8.utils.IterableUtils;
@@ -50,6 +51,8 @@
codeRewriter.rewriteMoveResult(code);
+ BranchSimplifier branchSimplifier = new BranchSimplifier(appView);
+
// We may encounter unneeded catch handlers after each iteration, e.g., if a dead instruction
// is the only throwing instruction in a block. Removing unneeded catch handlers can lead to
// more dead instructions.
@@ -62,7 +65,7 @@
removeDeadInstructions(worklist, code, block, valueIsDeadAnalysis);
removeDeadPhis(worklist, block, valueIsDeadAnalysis);
}
- } while (codeRewriter.simplifyIf(code).anySimplifications()
+ } while (branchSimplifier.simplifyIf(code).anySimplifications()
|| removeUnneededCatchHandlers(code));
assert code.isConsistentSSA(appView);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/MultiCallerInliner.java b/src/main/java/com/android/tools/r8/ir/optimize/MultiCallerInliner.java
index 54c8f61..4b5f0c9 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/MultiCallerInliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/MultiCallerInliner.java
@@ -147,12 +147,11 @@
// We track up to n call sites, where n is the size of multiCallerInliningInstructionLimits.
if (callers.size() > multiCallerInliningInstructionLimits.length) {
stopTrackingCallSitesForMethodIfDefinitelyIneligibleForMultiCallerInlining(
- method, singleTarget, methodProcessor, callers);
+ singleTarget, methodProcessor, callers);
}
}
private void stopTrackingCallSitesForMethodIfDefinitelyIneligibleForMultiCallerInlining(
- ProgramMethod method,
ProgramMethod singleTarget,
MethodProcessor methodProcessor,
ProgramMethodMultiset callers) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/RuntimeWorkaroundCodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/RuntimeWorkaroundCodeRewriter.java
index afed4c2..370a5d7 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/RuntimeWorkaroundCodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/RuntimeWorkaroundCodeRewriter.java
@@ -22,6 +22,7 @@
import com.android.tools.r8.ir.code.InvokeStatic;
import com.android.tools.r8.ir.code.NumericType;
import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.conversion.passes.BranchSimplifier;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.LazyBox;
import com.google.common.collect.ImmutableList;
@@ -68,6 +69,58 @@
}
}
+ public static void workaroundSwitchMaxIntBug(IRCode code, AppView<?> appView) {
+ if (appView.options().canHaveSwitchMaxIntBug() && code.metadata().mayHaveSwitch()) {
+ // Always rewrite for workaround switch bug.
+ rewriteSwitchForMaxIntOnly(code, appView);
+ }
+ }
+
+ private static void rewriteSwitchForMaxIntOnly(IRCode code, AppView<?> appView) {
+ boolean needToSplitCriticalEdges = false;
+ BranchSimplifier branchSimplifier = new BranchSimplifier(appView);
+ ListIterator<BasicBlock> blocksIterator = code.listIterator();
+ while (blocksIterator.hasNext()) {
+ BasicBlock block = blocksIterator.next();
+ InstructionListIterator iterator = block.listIterator(code);
+ while (iterator.hasNext()) {
+ Instruction instruction = iterator.next();
+ assert !instruction.isStringSwitch();
+ if (instruction.isIntSwitch()) {
+ IntSwitch intSwitch = instruction.asIntSwitch();
+ if (intSwitch.getKey(intSwitch.numberOfKeys() - 1) == Integer.MAX_VALUE) {
+ if (intSwitch.numberOfKeys() == 1) {
+ branchSimplifier.rewriteSingleKeySwitchToIf(code, block, iterator, intSwitch);
+ } else {
+ IntList newSwitchSequences = new IntArrayList(intSwitch.numberOfKeys() - 1);
+ for (int i = 0; i < intSwitch.numberOfKeys() - 1; i++) {
+ newSwitchSequences.add(intSwitch.getKey(i));
+ }
+ IntList outliers = new IntArrayList(1);
+ outliers.add(Integer.MAX_VALUE);
+ branchSimplifier.convertSwitchToSwitchAndIfs(
+ code,
+ blocksIterator,
+ block,
+ iterator,
+ intSwitch,
+ ImmutableList.of(newSwitchSequences),
+ outliers);
+ }
+ needToSplitCriticalEdges = true;
+ }
+ }
+ }
+ }
+
+ // Rewriting of switches introduces new branching structure. It relies on critical edges
+ // being split on the way in but does not maintain this property. We therefore split
+ // critical edges at exit.
+ if (needToSplitCriticalEdges) {
+ code.splitCriticalEdges();
+ }
+ }
+
/**
* For each block, we look to see if the header matches:
*
@@ -192,58 +245,6 @@
}
}
- public static void workaroundSwitchMaxIntBug(
- IRCode code, CodeRewriter codeRewriter, InternalOptions options) {
- if (options.canHaveSwitchMaxIntBug() && code.metadata().mayHaveSwitch()) {
- // Always rewrite for workaround switch bug.
- rewriteSwitchForMaxIntOnly(code, codeRewriter);
- }
- }
-
- private static void rewriteSwitchForMaxIntOnly(IRCode code, CodeRewriter codeRewriter) {
- boolean needToSplitCriticalEdges = false;
- ListIterator<BasicBlock> blocksIterator = code.listIterator();
- while (blocksIterator.hasNext()) {
- BasicBlock block = blocksIterator.next();
- InstructionListIterator iterator = block.listIterator(code);
- while (iterator.hasNext()) {
- Instruction instruction = iterator.next();
- assert !instruction.isStringSwitch();
- if (instruction.isIntSwitch()) {
- IntSwitch intSwitch = instruction.asIntSwitch();
- if (intSwitch.getKey(intSwitch.numberOfKeys() - 1) == Integer.MAX_VALUE) {
- if (intSwitch.numberOfKeys() == 1) {
- codeRewriter.rewriteSingleKeySwitchToIf(code, block, iterator, intSwitch);
- } else {
- IntList newSwitchSequences = new IntArrayList(intSwitch.numberOfKeys() - 1);
- for (int i = 0; i < intSwitch.numberOfKeys() - 1; i++) {
- newSwitchSequences.add(intSwitch.getKey(i));
- }
- IntList outliers = new IntArrayList(1);
- outliers.add(Integer.MAX_VALUE);
- codeRewriter.convertSwitchToSwitchAndIfs(
- code,
- blocksIterator,
- block,
- iterator,
- intSwitch,
- ImmutableList.of(newSwitchSequences),
- outliers);
- }
- needToSplitCriticalEdges = true;
- }
- }
- }
- }
-
- // Rewriting of switches introduces new branching structure. It relies on critical edges
- // being split on the way in but does not maintain this property. We therefore split
- // critical edges at exit.
- if (needToSplitCriticalEdges) {
- code.splitCriticalEdges();
- }
- }
-
// See comment for InternalOptions.canHaveNumberConversionRegisterAllocationBug().
public static void workaroundNumberConversionRegisterAllocationBug(
IRCode code, InternalOptions options) {
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 7607596..889a434 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
@@ -19,8 +19,9 @@
import com.android.tools.r8.ir.code.InstructionOrPhi;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.conversion.MethodProcessor;
+import com.android.tools.r8.ir.conversion.passes.BranchSimplifier;
+import com.android.tools.r8.ir.conversion.passes.TrivialCheckCastAndInstanceOfRemover;
import com.android.tools.r8.ir.optimize.AssumeRemover;
-import com.android.tools.r8.ir.optimize.CodeRewriter;
import com.android.tools.r8.ir.optimize.Inliner;
import com.android.tools.r8.ir.optimize.InliningOracle;
import com.android.tools.r8.ir.optimize.classinliner.InlineCandidateProcessor.IllegalClassInlinerStateException;
@@ -126,7 +127,6 @@
//
public final void processMethodCode(
AppView<AppInfoWithLiveness> appView,
- CodeRewriter codeRewriter,
StringOptimizer stringOptimizer,
EnumValueOptimizer enumValueOptimizer,
ProgramMethod method,
@@ -247,10 +247,10 @@
// If a method was inlined we may be able to remove check-cast instructions because we may
// have more information about the types of the arguments at the call site. This is
// particularly important for bridge methods.
- codeRewriter.removeTrivialCheckCastAndInstanceOfInstructions(
- code, method, methodProcessor, methodProcessingContext);
+ new TrivialCheckCastAndInstanceOfRemover(appView)
+ .run(code, method, methodProcessor, methodProcessingContext);
// If a method was inlined we may be able to prune additional branches.
- codeRewriter.simplifyControlFlow(code);
+ new BranchSimplifier(appView).simplifyBranches(code);
// 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/ir/optimize/inliner/DefaultInliningReasonStrategy.java b/src/main/java/com/android/tools/r8/ir/optimize/inliner/DefaultInliningReasonStrategy.java
index 537150e..02d13dd 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/inliner/DefaultInliningReasonStrategy.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/inliner/DefaultInliningReasonStrategy.java
@@ -53,7 +53,7 @@
// program.
return Reason.SIMPLE;
}
- if (isSingleCallerInliningTarget(target)) {
+ if (isSingleCallerInliningTarget(target, context)) {
return Reason.SINGLE_CALLER;
}
if (isMultiCallerInlineCandidate(invoke, target, oracle, methodProcessor)) {
@@ -64,8 +64,8 @@
return Reason.SIMPLE;
}
- private boolean isSingleCallerInliningTarget(ProgramMethod method) {
- if (!callSiteInformation.hasSingleCallSite(method)) {
+ private boolean isSingleCallerInliningTarget(ProgramMethod method, ProgramMethod context) {
+ if (!callSiteInformation.hasSingleCallSite(method, context)) {
return false;
}
if (appView.appInfo().isNeverInlineDueToSingleCallerMethod(method)) {
diff --git a/src/main/java/com/android/tools/r8/naming/ComposingBuilder.java b/src/main/java/com/android/tools/r8/naming/ComposingBuilder.java
index d87e036..502f120 100644
--- a/src/main/java/com/android/tools/r8/naming/ComposingBuilder.java
+++ b/src/main/java/com/android/tools/r8/naming/ComposingBuilder.java
@@ -1306,7 +1306,7 @@
}
newMappingInformation.forEach(
info -> {
- if (!nonCompasableNewInfos.contains(info)) {
+ if (!nonCompasableNewInfos.contains(info) && !info.isFileNameInformation()) {
consumer.accept(info);
}
});
diff --git a/src/main/java/com/android/tools/r8/retrace/internal/ProguardMapPartitionerOnClassNameToText.java b/src/main/java/com/android/tools/r8/retrace/internal/ProguardMapPartitionerOnClassNameToText.java
index 3af7dff..4fdc94a 100644
--- a/src/main/java/com/android/tools/r8/retrace/internal/ProguardMapPartitionerOnClassNameToText.java
+++ b/src/main/java/com/android/tools/r8/retrace/internal/ProguardMapPartitionerOnClassNameToText.java
@@ -273,7 +273,7 @@
extends ProguardMapPartitionerBuilderImpl {
private MappingPartitionKeyStrategy mappingPartitionKeyStrategy =
- MappingPartitionKeyStrategy.OBFUSCATED_TYPE_NAME_AS_KEY_WITH_PARTITIONS;
+ MappingPartitionKeyStrategy.getDefaultStrategy();
public ProguardMapPartitionerBuilderImplInternal(DiagnosticsHandler diagnosticsHandler) {
super(diagnosticsHandler);
diff --git a/src/main/java/com/android/tools/r8/utils/DescriptorUtils.java b/src/main/java/com/android/tools/r8/utils/DescriptorUtils.java
index 2c6f535..19b4d38 100644
--- a/src/main/java/com/android/tools/r8/utils/DescriptorUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/DescriptorUtils.java
@@ -456,8 +456,8 @@
* @return java package name i.e. "java.lang"
*/
public static String getPackageNameFromTypeName(String typeName) {
- return getPackageNameFromBinaryName(
- getClassBinaryNameFromDescriptor(javaTypeToDescriptor(typeName)));
+ int packageEndIndex = typeName.lastIndexOf(JAVA_PACKAGE_SEPARATOR);
+ return (packageEndIndex < 0) ? "" : typeName.substring(0, packageEndIndex);
}
/**
diff --git a/src/main/java/com/android/tools/r8/utils/Timing.java b/src/main/java/com/android/tools/r8/utils/Timing.java
index 1e61b88..143bc2f 100644
--- a/src/main/java/com/android/tools/r8/utils/Timing.java
+++ b/src/main/java/com/android/tools/r8/utils/Timing.java
@@ -19,6 +19,7 @@
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
+import java.util.concurrent.ExecutorService;
public class Timing {
@@ -373,6 +374,10 @@
}
}
+ public final TimingMerger beginMerger(String title, ExecutorService executorService) {
+ return beginMerger(title, ThreadUtils.getNumberOfThreads(executorService));
+ }
+
public TimingMerger beginMerger(String title, int numberOfThreads) {
return new TimingMerger(title, numberOfThreads, this);
}
diff --git a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/jdktests/Jdk11StreamAbstractTests.java b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/jdktests/Jdk11StreamAbstractTests.java
index 5822d2f..9ff2346 100644
--- a/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/jdktests/Jdk11StreamAbstractTests.java
+++ b/src/test/java/com/android/tools/r8/desugar/desugaredlibrary/jdktests/Jdk11StreamAbstractTests.java
@@ -115,12 +115,17 @@
public static final String[] SUCCESSFUL_RUNNABLE_TESTS_ON_JDK11_AND_V7 =
new String[] {
// Require the virtual method isDefault() in class java/lang/reflect/Method.
- "org/openjdk/tests/java/util/stream/WhileOpTest.java",
"org/openjdk/tests/java/util/stream/WhileOpStatefulTest.java",
// Require a Random method not present before Android 7 and not desugared.
"org/openjdk/tests/java/util/stream/IntPrimitiveOpsTests.java"
};
+ public static final String[] LONG_RUNNING_SUCCESSFUL_RUNNABLE_TESTS_ON_JDK11_AND_V7 =
+ new String[] {
+ // Require the virtual method isDefault() in class java/lang/reflect/Method.
+ "org/openjdk/tests/java/util/stream/WhileOpTest.java",
+ };
+
// Disabled because time to run > 1 min for each test.
// Can be used for experimentation/testing purposes.
private static String[] LONG_RUNNING_TESTS =
diff --git a/src/test/java/com/android/tools/r8/desugaring/interfacemethods/InvokeSuperInDefaultInterfaceMethodToNonImmediateInterfaceTest.java b/src/test/java/com/android/tools/r8/desugaring/interfacemethods/InvokeSuperInDefaultInterfaceMethodToNonImmediateInterfaceTest.java
index f4fec42..d743010 100644
--- a/src/test/java/com/android/tools/r8/desugaring/interfacemethods/InvokeSuperInDefaultInterfaceMethodToNonImmediateInterfaceTest.java
+++ b/src/test/java/com/android/tools/r8/desugaring/interfacemethods/InvokeSuperInDefaultInterfaceMethodToNonImmediateInterfaceTest.java
@@ -7,117 +7,132 @@
import static org.junit.Assert.assertEquals;
import com.android.tools.r8.TestBase;
-import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.ToolHelper.DexVm.Version;
-import com.android.tools.r8.origin.Origin;
-import com.android.tools.r8.smali.SmaliBuilder;
+import com.android.tools.r8.TestParameters;
import com.android.tools.r8.utils.AndroidApiLevel;
-import com.android.tools.r8.utils.AndroidApp;
import com.android.tools.r8.utils.BooleanUtils;
import com.android.tools.r8.utils.StringUtils;
import com.google.common.collect.ImmutableList;
-import org.junit.Ignore;
+import java.io.IOException;
+import java.util.List;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
+import org.objectweb.asm.Opcodes;
@RunWith(Parameterized.class)
public class InvokeSuperInDefaultInterfaceMethodToNonImmediateInterfaceTest extends TestBase {
+ private final TestParameters parameters;
private final boolean includeInterfaceMethodOnJ;
- @Parameterized.Parameters(name = "Include interface method on J: {0}")
- public static Boolean[] data() {
- return BooleanUtils.values();
+ // Note that the expected output is independent of the presence of J.m().
+ private static final String EXPECTED = StringUtils.lines("I.m()", "JImpl.m()");
+
+ @Parameterized.Parameters(name = "{0}, J.m(): {1}")
+ public static List<Object[]> data() {
+ return buildParameters(
+ TestParameters.builder()
+ .withCfRuntimes()
+ .enableApiLevelsForCf()
+ .withDexRuntimes()
+ .withApiLevel(AndroidApiLevel.B)
+ .build(),
+ BooleanUtils.values());
}
public InvokeSuperInDefaultInterfaceMethodToNonImmediateInterfaceTest(
- boolean includeInterfaceMethodOnJ) {
+ TestParameters parameters, boolean includeInterfaceMethodOnJ) {
+ this.parameters = parameters;
this.includeInterfaceMethodOnJ = includeInterfaceMethodOnJ;
}
@Test
- @Ignore("b/197494749 and b/120130831")
- // TODO(b/197494749): Update this test now that desugaring is moved up. In particular this must
- // be rewritten with CF based transformers as R8 does not support interface desugaring on DEX.
- // TODO(b/120130831): With the move of desugaring this issue should be resolved. The bug indicates
- // that a workaround for issues related to the IR implementation can now be reverted.
- public void test() throws Exception {
- // Note that the expected output is independent of the presence of J.m().
- String expectedOutput = StringUtils.lines("I.m()", "JImpl.m()");
-
- byte[] dex = buildProgramDexFileData();
- if (ToolHelper.getDexVm().getVersion().isNewerThan(Version.V6_0_1)) {
- AndroidApp app =
- AndroidApp.builder()
- .addDexProgramData(buildProgramDexFileData(), Origin.unknown())
- .build();
- assertEquals(expectedOutput, runOnArt(app, "TestClass"));
- }
-
- testForR8(Backend.DEX)
- .addProgramDexFileData(dex)
- .addKeepMainRule("TestClass")
- .setMinApi(AndroidApiLevel.M)
- .run("TestClass")
- .assertSuccessWithOutput(expectedOutput);
+ public void testJvm() throws Exception {
+ // The rewritten input is invalid on JVM.
+ parameters.assumeJvmTestParameters();
+ testForJvm(parameters)
+ .addProgramClasses(getClasses())
+ .addProgramClassFileData(getTransformedClasses())
+ .run(parameters.getRuntime(), TestClass.class)
+ .assertFailureWithErrorThatThrows(VerifyError.class);
}
- // Using Smali instead of Jasmin because interfaces are broken in Jasmin.
- private byte[] buildProgramDexFileData() throws Exception {
- SmaliBuilder smaliBuilder = new SmaliBuilder();
- smaliBuilder.setMinApi(AndroidApiLevel.N);
+ @Test
+ public void testD8() throws Exception {
+ // Notice that desugaring will map out of the invalid invoke.
+ testForD8(parameters.getBackend())
+ .addProgramClasses(getClasses())
+ .addProgramClassFileData(getTransformedClasses())
+ .setMinApi(parameters)
+ .run(parameters.getRuntime(), TestClass.class)
+ .assertSuccessWithOutput(EXPECTED);
+ }
- smaliBuilder.addClass("TestClass");
+ @Test
+ public void testR8() throws Exception {
+ // Notice that desugaring will map out of the invalid invoke.
+ testForR8(parameters.getBackend())
+ .addProgramClasses(getClasses())
+ .addProgramClassFileData(getTransformedClasses())
+ .addKeepMainRule(TestClass.class)
+ .setMinApi(parameters)
+ .run(parameters.getRuntime(), TestClass.class)
+ .assertSuccessWithOutput(EXPECTED);
+ }
- // public void main(String[] args) { new JImpl().m(); }
- smaliBuilder.addMainMethod(
- 1,
- "new-instance v0, LJImpl;",
- "invoke-direct {v0}, LJImpl;-><init>()V",
- "invoke-virtual {v0}, LJImpl;->m()V",
- "return-void");
+ private List<Class<?>> getClasses() {
+ return ImmutableList.of(TestClass.class, I.class);
+ }
- smaliBuilder.addInterface("I");
+ private List<byte[]> getTransformedClasses() throws IOException {
+ return ImmutableList.of(
+ transformer(JImpl.class)
+ .transformMethodInsnInMethod(
+ "m",
+ (opcode, owner, name, descriptor, isInterface, visitor) -> {
+ if (opcode == Opcodes.INVOKESPECIAL) {
+ assertEquals(owner, binaryName(J.class));
+ owner = binaryName(I.class);
+ }
+ visitor.visitMethodInsn(opcode, owner, name, descriptor, isInterface);
+ })
+ .transform(),
+ transformer(J.class)
+ .removeMethods(
+ (access, name, descriptor, signature, exceptions) ->
+ !includeInterfaceMethodOnJ && name.equals("m"))
+ .transform());
+ }
- // default void m() { System.out.println("In I.m()"); }
- smaliBuilder.addInstanceMethod(
- "void",
- "m",
- 2,
- "sget-object v0, Ljava/lang/System;->out:Ljava/io/PrintStream;",
- "const-string v1, \"I.m()\"",
- "invoke-virtual {v0, v1}, Ljava/io/PrintStream;->println(Ljava/lang/String;)V",
- "return-void");
+ static class TestClass {
- smaliBuilder.addInterface("J", "java.lang.Object", ImmutableList.of("I"));
- if (includeInterfaceMethodOnJ) {
- smaliBuilder.addInstanceMethod(
- "void",
- "m",
- 2,
- "invoke-super {p0}, LI;->m()V",
- "sget-object v0, Ljava/lang/System;->out:Ljava/io/PrintStream;",
- "const-string v1, \"J.m()\"",
- "invoke-virtual {v0, v1}, Ljava/io/PrintStream;->println(Ljava/lang/String;)V",
- "return-void");
+ public static void main(String[] args) {
+ new JImpl().m();
}
+ }
- smaliBuilder.addClass("JImpl", "java.lang.Object", ImmutableList.of("J"));
- smaliBuilder.addDefaultConstructor();
+ interface I {
- // default void m() { I.super.m(); System.out.println("In JImpl.m()"); }
- smaliBuilder.addInstanceMethod(
- "void",
- "m",
- 2,
- // Note: invoke-super instruction to the non-immediate interface I.
- "invoke-super {p0}, LI;->m()V",
- "sget-object v0, Ljava/lang/System;->out:Ljava/io/PrintStream;",
- "const-string v1, \"JImpl.m()\"",
- "invoke-virtual {v0, v1}, Ljava/io/PrintStream;->println(Ljava/lang/String;)V",
- "return-void");
+ default void m() {
+ System.out.println("I.m()");
+ }
+ }
- return smaliBuilder.compile();
+ interface J extends I {
+
+ @Override
+ default void m() {
+ I.super.m();
+ System.out.println("J.m()");
+ }
+ }
+
+ static class JImpl implements J {
+
+ @Override
+ public void m() {
+ J.super.m(); // Will be rewritten to non-immediate interface: I.super.m();
+ System.out.println("JImpl.m()");
+ }
}
}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java
index 019431d..8a8ab51 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/TrivialGotoEliminationTest.java
@@ -29,6 +29,7 @@
import com.android.tools.r8.ir.code.Throw;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.conversion.MethodConversionOptions.MutableMethodConversionOptions;
+import com.android.tools.r8.ir.conversion.passes.TrivialGotosCollapser;
import com.android.tools.r8.origin.Origin;
import com.android.tools.r8.utils.AndroidApp;
import com.android.tools.r8.utils.InternalOptions;
@@ -107,7 +108,7 @@
IRMetadata.unknown(),
Origin.unknown(),
new MutableMethodConversionOptions(options));
- CodeRewriter.collapseTrivialGotos(appView, code);
+ new TrivialGotosCollapser(appView).run(code.context(), code);
assertTrue(code.entryBlock().isTrivialGoto());
assertTrue(blocks.contains(block0));
assertTrue(blocks.contains(block1));
@@ -196,7 +197,7 @@
IRMetadata.unknown(),
Origin.unknown(),
new MutableMethodConversionOptions(options));
- CodeRewriter.collapseTrivialGotos(appView, code);
+ new TrivialGotosCollapser(appView).run(code.context(), code);
assertTrue(block0.getInstructions().get(1).isIf());
assertEquals(block1, block0.getInstructions().get(1).asIf().fallthroughBlock());
assertTrue(blocks.containsAll(ImmutableList.of(block0, block1, block2, block3)));
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/inliner/SingleTargetAfterInliningTest.java b/src/test/java/com/android/tools/r8/ir/optimize/inliner/SingleTargetAfterInliningTest.java
index f5b5a47..706f8f0 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/inliner/SingleTargetAfterInliningTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/inliner/SingleTargetAfterInliningTest.java
@@ -75,13 +75,15 @@
ClassSubject aClassSubject = inspector.clazz(A.class);
assertThat(aClassSubject, isPresent());
- // B.foo() should be absent if the max inlining depth is 1, because indirection() has been
- // inlined into main(), which makes B.foo() eligible for inlining into main().
+ // B.foo() could potentially be absent if the max inlining depth is 1, because indirection() has
+ // been inlined into main(), which makes B.foo() eligible for inlining into main() since we can
+ // compute a single target. However, because indirection() can be inlined into multiple callers
+ // we cannot trust the single caller predicate. If indirection() also has a singler caller we
+ // could propagate the single call site property to B.foo().
ClassSubject bClassSubject = inspector.clazz(B.class);
assertThat(bClassSubject, isPresent());
- assertThat(
- bClassSubject.uniqueMethodWithOriginalName("foo"),
- notIf(isPresent(), maxInliningDepth == 1));
+ // TODO(b/286058449): We could inline this.
+ assertThat(bClassSubject.uniqueMethodWithOriginalName("foo"), isPresent());
// B.bar() should always be inlined because it is marked as @AlwaysInline.
assertThat(
diff --git a/src/test/java/com/android/tools/r8/mappingcompose/ComposeSourceFileTest.java b/src/test/java/com/android/tools/r8/mappingcompose/ComposeSourceFileTest.java
index b07c55c..434c494 100644
--- a/src/test/java/com/android/tools/r8/mappingcompose/ComposeSourceFileTest.java
+++ b/src/test/java/com/android/tools/r8/mappingcompose/ComposeSourceFileTest.java
@@ -31,22 +31,32 @@
private static final String mappingFoo =
StringUtils.unixLines(
- "# {'id':'com.android.tools.r8.mapping','version':'experimental'}",
- "com.foo -> a:",
- " # {'id':'sourceFile','fileName':'Foo.kt'}");
+ "# {'id':'com.android.tools.r8.mapping','version':'2.2'}",
+ "com.foo -> A:",
+ " # {'id':'sourceFile','fileName':'Foo.kt'}",
+ "com.bar -> B:",
+ " # {'id':'sourceFile','fileName':'Bar.kt'}",
+ "com.baz -> C:");
private static final String mappingBar =
StringUtils.unixLines(
- "# {'id':'com.android.tools.r8.mapping','version':'experimental'}",
- "com.bar -> c:",
- " # {'id':'sourceFile','fileName':'Bar.kt'}",
- "a -> b:");
+ "# {'id':'com.android.tools.r8.mapping','version':'2.2'}",
+ "A -> a:",
+ " # {'id':'sourceFile','fileName':'some-hash-inserted-into-source-file'}",
+ "B -> b:",
+ "C -> c:",
+ " # {'id':'sourceFile','fileName':'some-other-hash-inserted-into-source-file'}",
+ "com.qux -> d:",
+ " # {'id':'sourceFile','fileName':'Qux.kt'}");
private static final String mappingResult =
StringUtils.unixLines(
- "# {'id':'com.android.tools.r8.mapping','version':'experimental'}",
- "com.bar -> c:",
+ "# {'id':'com.android.tools.r8.mapping','version':'2.2'}",
+ "com.bar -> b:",
"# {'id':'sourceFile','fileName':'Bar.kt'}",
- "com.foo -> b:",
- "# {'id':'sourceFile','fileName':'Foo.kt'}");
+ "com.baz -> c:",
+ "com.foo -> a:",
+ "# {'id':'sourceFile','fileName':'Foo.kt'}",
+ "com.qux -> d:",
+ "# {'id':'sourceFile','fileName':'Qux.kt'}");
@Test
public void testCompose() throws Exception {
diff --git a/src/test/java/com/android/tools/r8/retrace/partition/RetracePartitionWithPrimitiveNameTest.java b/src/test/java/com/android/tools/r8/retrace/partition/RetracePartitionWithPrimitiveNameTest.java
new file mode 100644
index 0000000..e848753
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/retrace/partition/RetracePartitionWithPrimitiveNameTest.java
@@ -0,0 +1,77 @@
+// 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.retrace.partition;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestDiagnosticMessagesImpl;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.retrace.MappingPartitionMetadata;
+import com.android.tools.r8.retrace.PartitionMappingSupplier;
+import com.android.tools.r8.retrace.ProguardMapProducer;
+import com.android.tools.r8.retrace.RetraceOptions;
+import com.android.tools.r8.retrace.RetraceStackFrameAmbiguousResultWithContext;
+import com.android.tools.r8.retrace.RetraceStackTraceContext;
+import com.android.tools.r8.retrace.StringRetrace;
+import com.android.tools.r8.retrace.internal.MappingPartitionKeyStrategy;
+import com.android.tools.r8.retrace.internal.ProguardMapPartitionerOnClassNameToText.ProguardMapPartitionerBuilderImplInternal;
+import com.android.tools.r8.utils.StringUtils;
+import java.util.HashMap;
+import java.util.Map;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+/** Regression test for b/286001537. */
+@RunWith(Parameterized.class)
+public class RetracePartitionWithPrimitiveNameTest extends TestBase {
+
+ @Parameters(name = "{0}")
+ public static TestParametersCollection data() {
+ return getTestParameters().withNoneRuntime().build();
+ }
+
+ public RetracePartitionWithPrimitiveNameTest(TestParameters parameters) {
+ parameters.assertNoneRuntime();
+ }
+
+ public final String mapping =
+ StringUtils.unixLines(
+ "# { id: 'com.android.tools.r8.mapping', version: '2.0' }",
+ "some.class1 -> int:",
+ " void method() -> a");
+
+ @Test
+ public void testPartitionAndRetrace() throws Exception {
+ ProguardMapProducer proguardMapProducer = ProguardMapProducer.fromString(mapping);
+ TestDiagnosticMessagesImpl diagnosticsHandler = new TestDiagnosticMessagesImpl();
+ Map<String, byte[]> partitions = new HashMap<>();
+ MappingPartitionMetadata metadata =
+ new ProguardMapPartitionerBuilderImplInternal(diagnosticsHandler)
+ .setMappingPartitionKeyStrategy(MappingPartitionKeyStrategy.getDefaultStrategy())
+ .setProguardMapProducer(proguardMapProducer)
+ .setPartitionConsumer(
+ partition -> partitions.put(partition.getKey(), partition.getPayload()))
+ .build()
+ .run();
+
+ PartitionMappingSupplier mappingSupplier =
+ PartitionMappingSupplier.builder()
+ .setMetadata(metadata.getBytes())
+ .setMappingPartitionFromKeySupplier(partitions::get)
+ .build();
+
+ StringRetrace retracer =
+ StringRetrace.create(RetraceOptions.builder().setMappingSupplier(mappingSupplier).build());
+ RetraceStackFrameAmbiguousResultWithContext<String> result =
+ retracer.retraceFrame(" at int.a()", RetraceStackTraceContext.empty());
+ StringBuilder sb = new StringBuilder();
+ result.forEach(frames -> frames.forEach(sb::append));
+ assertEquals(" at some.class1.method(class1.java)", sb.toString());
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/rewrite/arrays/ArrayWithDataLengthRewriteTest.java b/src/test/java/com/android/tools/r8/rewrite/arrays/ArrayWithDataLengthRewriteTest.java
index bcacbe7..a09de37 100644
--- a/src/test/java/com/android/tools/r8/rewrite/arrays/ArrayWithDataLengthRewriteTest.java
+++ b/src/test/java/com/android/tools/r8/rewrite/arrays/ArrayWithDataLengthRewriteTest.java
@@ -13,7 +13,7 @@
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
-import com.android.tools.r8.ir.optimize.CodeRewriter;
+import com.android.tools.r8.ir.conversion.passes.ArrayConstructionSimplifier;
import com.android.tools.r8.utils.codeinspector.ClassSubject;
import com.android.tools.r8.utils.codeinspector.CodeInspector;
import com.android.tools.r8.utils.codeinspector.InstructionSubject;
@@ -64,7 +64,7 @@
}
private void transformArray(IRCode irCode, AppView<?> appView) {
- new CodeRewriter(appView).simplifyArrayConstruction(irCode);
+ new ArrayConstructionSimplifier(appView).run(irCode.context(), irCode);
String name = irCode.context().getReference().getName().toString();
if (name.contains("filledArrayData")) {
assertTrue(irCode.streamInstructions().anyMatch(Instruction::isNewArrayFilledData));
diff --git a/src/test/java/com/android/tools/r8/startup/SingleCallerBridgeStartupTest.java b/src/test/java/com/android/tools/r8/startup/SingleCallerBridgeStartupTest.java
index 4a27e0f..1cb68de 100644
--- a/src/test/java/com/android/tools/r8/startup/SingleCallerBridgeStartupTest.java
+++ b/src/test/java/com/android/tools/r8/startup/SingleCallerBridgeStartupTest.java
@@ -4,6 +4,9 @@
package com.android.tools.r8.startup;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
+
import com.android.tools.r8.TestBase;
import com.android.tools.r8.TestParameters;
import com.android.tools.r8.TestParametersCollection;
@@ -12,6 +15,7 @@
import com.android.tools.r8.startup.profile.ExternalStartupItem;
import com.android.tools.r8.startup.profile.ExternalStartupMethod;
import com.android.tools.r8.startup.utils.StartupTestingUtils;
+import com.android.tools.r8.utils.codeinspector.ClassSubject;
import com.google.common.collect.ImmutableList;
import java.util.Collection;
import org.junit.Test;
@@ -55,9 +59,16 @@
(appView, inlinee, inliningDepth) ->
inlinee.getMethodReference().equals(barMethod))
.setMinApi(parameters)
+ .compile()
+ .inspect(
+ inspector -> {
+ // Assert that foo is not inlined.
+ ClassSubject A = inspector.clazz(A.class);
+ assertThat(A, isPresent());
+ assertThat(A.uniqueMethodWithOriginalName("foo"), isPresent());
+ })
.run(parameters.getRuntime(), Main.class)
- // TODO(b/285021603): We should not fail here.
- .assertFailureWithErrorThatThrows(NoSuchMethodError.class);
+ .assertSuccessWithOutputLines("A::foo", "A::foo");
}
static class Main {
diff --git a/tools/create_maven_release.py b/tools/create_maven_release.py
index ee68e1e..1ca239e 100755
--- a/tools/create_maven_release.py
+++ b/tools/create_maven_release.py
@@ -124,6 +124,12 @@
help='Build desugar library configuration (original JDK-8)')
group.add_argument('--desugar-configuration-jdk11-legacy', action='store_true',
help='Build desugar library configuration (JDK-11 legacy)')
+ group.add_argument('--desugar-configuration-jdk11-minimal', action='store_true',
+ help='Build desugar library configuration (JDK-11 minimal)')
+ group.add_argument('--desugar-configuration-jdk11', action='store_true',
+ help='Build desugar library configuration (JDK-11)')
+ group.add_argument('--desugar-configuration-jdk11-nio', action='store_true',
+ help='Build desugar library configuration (JDK-11 nio)')
return result.parse_args(argv)
def determine_version():
@@ -369,7 +375,7 @@
with zipfile.ZipFile(conversions, 'r') as conversions_zip:
conversions_zip.extractall(tmp_dir)
- # Add configuration
+ # Add configuration.
configuration_dir = join(tmp_dir, 'META-INF', 'desugar', 'd8')
makedirs(configuration_dir)
copyfile(configuration, join(configuration_dir, 'desugar.json'))
@@ -388,6 +394,9 @@
utils.PrintCmd(cmd)
subprocess.check_call(cmd)
+ # Add LICENSE file.
+ copyfile(join(utils.REPO_ROOT, 'LICENSE'), join(tmp_dir, 'LICENSE'))
+
make_archive(destination, 'zip', tmp_dir)
move(destination + '.zip', destination)
@@ -435,11 +444,34 @@
'Need to supply output zip with --out.')
if options.desugar_configuration or options.desugar_configuration_jdk8:
generate_desugar_configuration_maven_zip(
- options.out, utils.DESUGAR_CONFIGURATION, utils.DESUGAR_IMPLEMENTATION)
+ options.out,
+ utils.DESUGAR_CONFIGURATION,
+ utils.DESUGAR_IMPLEMENTATION,
+ utils.LIBRARY_DESUGAR_CONVERSIONS_LEGACY_ZIP)
elif options.desugar_configuration_jdk11_legacy:
generate_desugar_configuration_maven_zip(
- options.out, utils.DESUGAR_CONFIGURATION_JDK11_LEGACY,
- utils.DESUGAR_IMPLEMENTATION_JDK11)
+ options.out,
+ utils.DESUGAR_CONFIGURATION_JDK11_LEGACY,
+ utils.DESUGAR_IMPLEMENTATION_JDK11,
+ utils.LIBRARY_DESUGAR_CONVERSIONS_LEGACY_ZIP)
+ elif options.desugar_configuration_jdk11_minimal:
+ generate_desugar_configuration_maven_zip(
+ options.out,
+ utils.DESUGAR_CONFIGURATION_JDK11_MINIMAL,
+ utils.DESUGAR_IMPLEMENTATION_JDK11,
+ utils.LIBRARY_DESUGAR_CONVERSIONS_ZIP)
+ elif options.desugar_configuration_jdk11:
+ generate_desugar_configuration_maven_zip(
+ options.out,
+ utils.DESUGAR_CONFIGURATION_JDK11,
+ utils.DESUGAR_IMPLEMENTATION_JDK11,
+ utils.LIBRARY_DESUGAR_CONVERSIONS_ZIP)
+ elif options.desugar_configuration_jdk11_nio:
+ generate_desugar_configuration_maven_zip(
+ options.out,
+ utils.DESUGAR_CONFIGURATION_JDK11_NIO,
+ utils.DESUGAR_IMPLEMENTATION_JDK11,
+ utils.LIBRARY_DESUGAR_CONVERSIONS_ZIP)
else:
generate_r8_maven_zip(options.out, options.r8lib)
