Explicit transfer of exceptional control flow in analysis framework
Bug: b/236244240
Bug: b/214496607
Change-Id: I1cfa296b6e33d0fde231c115576756112adffe40
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java b/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java
index 932a283..248cf1c 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfInstruction.java
@@ -343,6 +343,11 @@
return false;
}
+ @Override
+ public final boolean instructionTypeCanThrow() {
+ return canThrow();
+ }
+
public abstract void buildIR(IRBuilder builder, CfState state, CfSourceCode code);
/** Return true if this instruction directly emits IR instructions. */
diff --git a/src/main/java/com/android/tools/r8/dex/code/CfOrDexInstruction.java b/src/main/java/com/android/tools/r8/dex/code/CfOrDexInstruction.java
index 7bd1e7a..8d7ef16 100644
--- a/src/main/java/com/android/tools/r8/dex/code/CfOrDexInstruction.java
+++ b/src/main/java/com/android/tools/r8/dex/code/CfOrDexInstruction.java
@@ -5,8 +5,9 @@
package com.android.tools.r8.dex.code;
import com.android.tools.r8.cf.code.CfInstruction;
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.AbstractInstruction;
-public interface CfOrDexInstruction {
+public interface CfOrDexInstruction extends AbstractInstruction {
CfInstruction asCfInstruction();
diff --git a/src/main/java/com/android/tools/r8/dex/code/DexInstruction.java b/src/main/java/com/android/tools/r8/dex/code/DexInstruction.java
index cc35c46..5efe526 100644
--- a/src/main/java/com/android/tools/r8/dex/code/DexInstruction.java
+++ b/src/main/java/com/android/tools/r8/dex/code/DexInstruction.java
@@ -415,4 +415,9 @@
public boolean canThrow() {
return false;
}
+
+ @Override
+ public final boolean instructionTypeCanThrow() {
+ return canThrow();
+ }
}
diff --git a/src/main/java/com/android/tools/r8/graph/CfCode.java b/src/main/java/com/android/tools/r8/graph/CfCode.java
index bac72e9..99c43b7 100644
--- a/src/main/java/com/android/tools/r8/graph/CfCode.java
+++ b/src/main/java/com/android/tools/r8/graph/CfCode.java
@@ -281,6 +281,10 @@
return tryCatchRanges;
}
+ public CfInstruction getInstruction(int index) {
+ return instructions.get(index);
+ }
+
public List<CfInstruction> getInstructions() {
return Collections.unmodifiableList(instructions);
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/AbstractInstruction.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/AbstractInstruction.java
new file mode 100644
index 0000000..d68129f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/AbstractInstruction.java
@@ -0,0 +1,10 @@
+// Copyright (c) 2022, 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.analysis.framework.intraprocedural;
+
+public interface AbstractInstruction {
+
+ boolean instructionTypeCanThrow();
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/AbstractTransferFunction.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/AbstractTransferFunction.java
index 697dbb9..57e5b6b 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/AbstractTransferFunction.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/AbstractTransferFunction.java
@@ -11,18 +11,44 @@
public interface AbstractTransferFunction<
Block, Instruction, StateType extends AbstractState<StateType>> {
+ /** Applies the effect of the given instruction on the given abstract state. */
TransferFunctionResult<StateType> apply(Instruction instruction, StateType state);
default TransferFunctionResult<StateType> applyBlock(Block block, StateType state) {
return state;
}
+ /**
+ * Computes the analysis state for the method entry point, i.e., the state prior to the first
+ * instruction.
+ */
default StateType computeInitialState(Block entryBlock, StateType bottom) {
return bottom;
}
+ /** Transfers the state from predecessor block to its successor block. */
default StateType computeBlockEntryState(
Block block, Block predecessor, StateType predecessorExitState) {
return predecessorExitState;
}
+
+ /**
+ * Returns true if (a function of) the abstract state at the given (throwing) instruction should
+ * be transferred to the active catch handlers.
+ */
+ default boolean shouldTransferExceptionalControlFlowFromInstruction(
+ Block throwBlock, Instruction throwInstruction) {
+ return true;
+ }
+
+ /**
+ * Transfers the state from the given (throwing) instruction to its catch handler.
+ *
+ * <p>Only called if {@link #shouldTransferExceptionalControlFlowFromInstruction} has returned
+ * true.
+ */
+ default StateType computeExceptionalBlockEntryState(
+ Block block, Block throwBlock, Instruction throwInstruction, StateType throwState) {
+ return throwState;
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/ControlFlowGraph.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/ControlFlowGraph.java
index db0d7ca..ecf6287 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/ControlFlowGraph.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/ControlFlowGraph.java
@@ -14,10 +14,32 @@
Block getEntryBlock();
+ default Block getUniquePredecessor(Block block) {
+ assert hasUniquePredecessor(block);
+ return TraversalUtils.getFirst(collector -> traversePredecessors(block, collector));
+ }
+
+ default Block getUniqueSuccessor(Block block) {
+ assert hasUniqueSuccessor(block);
+ return TraversalUtils.getFirst(collector -> traverseSuccessors(block, collector));
+ }
+
+ default boolean hasExceptionalPredecessors(Block block) {
+ return TraversalUtils.hasNext(counter -> traverseExceptionalPredecessors(block, counter));
+ }
+
+ default boolean hasExceptionalSuccessors(Block block) {
+ return TraversalUtils.hasNext(counter -> traverseExceptionalSuccessors(block, counter));
+ }
+
default boolean hasUniquePredecessor(Block block) {
return TraversalUtils.isSingleton(counter -> traversePredecessors(block, counter));
}
+ default boolean hasUniquePredecessorWithUniqueSuccessor(Block block) {
+ return hasUniquePredecessor(block) && hasUniqueSuccessor(getUniquePredecessor(block));
+ }
+
default boolean hasUniqueSuccessor(Block block) {
return TraversalUtils.isSingleton(counter -> traverseSuccessors(block, counter));
}
@@ -26,11 +48,6 @@
return hasUniqueSuccessor(block) && hasUniquePredecessor(getUniqueSuccessor(block));
}
- default Block getUniqueSuccessor(Block block) {
- assert hasUniqueSuccessor(block);
- return TraversalUtils.getFirst(collector -> traverseSuccessors(block, collector));
- }
-
// Block traversal.
default <BT, CT> TraversalContinuation<BT, CT> traversePredecessors(
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraProceduralDataflowAnalysisBase.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraProceduralDataflowAnalysisBase.java
index b70c08f..dbd2a45 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraProceduralDataflowAnalysisBase.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraProceduralDataflowAnalysisBase.java
@@ -25,7 +25,7 @@
* FailedDataflowAnalysisResult}.
*/
public class IntraProceduralDataflowAnalysisBase<
- Block, Instruction, StateType extends AbstractState<StateType>> {
+ Block, Instruction extends AbstractInstruction, StateType extends AbstractState<StateType>> {
final StateType bottom;
@@ -34,13 +34,16 @@
// The transfer function that defines the abstract semantics for each instruction.
final AbstractTransferFunction<Block, Instruction, StateType> transfer;
- // The state of the analysis.
- final Map<Block, StateType> blockExitStates = new IdentityHashMap<>();
-
// The entry states for each block that satisfies the predicate
// shouldCacheBlockEntryStateFor(block). These entry states can be computed from the exit states
// of the predecessors, but doing so can be expensive when a block has many predecessors.
- final Map<Block, StateType> blockEntryStatesCache = new IdentityHashMap<>();
+ final Map<Block, StateType> blockEntryStates = new IdentityHashMap<>();
+
+ // The state of the analysis.
+ final Map<Block, StateType> blockExitStates = new IdentityHashMap<>();
+
+ // The entry states for exceptional blocks.
+ final Map<Block, StateType> exceptionalBlockEntryStates = new IdentityHashMap<>();
final IntraProceduralDataflowAnalysisOptions options;
@@ -81,10 +84,19 @@
timing.begin("Compute transfers");
do {
+ Block currentBlock = block;
+ boolean hasExceptionalSuccessors = cfg.hasExceptionalSuccessors(block);
TraversalContinuation<FailedDataflowAnalysisResult, StateType> traversalContinuation =
cfg.traverseInstructions(
block,
(instruction, previousState) -> {
+ if (instruction.instructionTypeCanThrow()
+ && hasExceptionalSuccessors
+ && transfer.shouldTransferExceptionalControlFlowFromInstruction(
+ currentBlock, instruction)) {
+ updateBlockEntryStateCacheForExceptionalSuccessors(
+ currentBlock, instruction, previousState);
+ }
TransferFunctionResult<StateType> transferResult =
transfer.apply(instruction, previousState);
if (transferResult.isFailedTransferResult()) {
@@ -99,10 +111,7 @@
return traversalContinuation.asBreak().getValue();
}
state = traversalContinuation.asContinue().getValue();
- if (cfg.hasUniqueSuccessorWithUniquePredecessor(block)) {
- if (!options.isCollapsingOfTrivialEdgesEnabled()) {
- setBlockExitState(block, state);
- }
+ if (isBlockWithIntermediateSuccessorBlock(block)) {
block = cfg.getUniqueSuccessor(block);
} else {
end = block;
@@ -117,27 +126,42 @@
cfg.forEachSuccessor(end, worklist::addIgnoringSeenSet);
}
- // Add the computed exit state to the entry state of each successor that satisfies the
+ // Add the computed exit state to the entry state of each normal successor that satisfies the
// predicate shouldCacheBlockEntryStateFor(successor).
- updateBlockEntryStateCacheForSuccessors(end, state);
+ updateBlockEntryStateCacheForNormalSuccessors(end, state);
}
return new SuccessfulDataflowAnalysisResult<>(blockExitStates);
}
public StateType computeBlockEntryState(Block block) {
if (block == cfg.getEntryBlock()) {
- return transfer.computeInitialState(block, bottom);
+ return transfer
+ .computeInitialState(block, bottom)
+ .join(computeBlockEntryStateForNormalBlock(block));
}
- if (shouldCacheBlockEntryStateFor(block)) {
- return blockEntryStatesCache.getOrDefault(block, bottom);
+ if (cfg.hasExceptionalPredecessors(block)) {
+ return exceptionalBlockEntryStates.getOrDefault(block, bottom).clone();
}
+ return computeBlockEntryStateForNormalBlock(block);
+ }
+
+ private StateType computeBlockEntryStateForNormalBlock(Block block) {
+ if (shouldCacheBlockEntryStateForNormalBlock(block)) {
+ return blockEntryStates.getOrDefault(block, bottom).clone();
+ }
+ return computeBlockEntryStateFromPredecessorExitStates(block);
+ }
+
+ private StateType computeBlockEntryStateFromPredecessorExitStates(Block block) {
TraversalContinuation<?, StateType> traversalContinuation =
- cfg.traversePredecessors(
+ cfg.traverseNormalPredecessors(
block,
(predecessor, entryState) -> {
StateType edgeState =
transfer.computeBlockEntryState(
- block, predecessor, blockExitStates.getOrDefault(predecessor, bottom));
+ block,
+ predecessor,
+ blockExitStates.getOrDefault(predecessor, bottom).clone());
return TraversalContinuation.doContinue(entryState.join(edgeState));
},
bottom);
@@ -145,26 +169,54 @@
}
boolean setBlockExitState(Block block, StateType state) {
- assert !cfg.hasUniqueSuccessorWithUniquePredecessor(block)
- || !options.isCollapsingOfTrivialEdgesEnabled();
+ assert !isBlockWithIntermediateSuccessorBlock(block);
StateType previous = blockExitStates.put(block, state);
assert previous == null || state.isGreaterThanOrEquals(previous);
return !state.equals(previous);
}
- void updateBlockEntryStateCacheForSuccessors(Block block, StateType state) {
- cfg.forEachSuccessor(
+ void updateBlockEntryStateCacheForNormalSuccessors(Block block, StateType state) {
+ cfg.forEachNormalSuccessor(
block,
successor -> {
- if (shouldCacheBlockEntryStateFor(successor)) {
+ if (shouldCacheBlockEntryStateForNormalBlock(successor)) {
StateType edgeState = transfer.computeBlockEntryState(successor, block, state);
- StateType previous = blockEntryStatesCache.getOrDefault(successor, bottom);
- blockEntryStatesCache.put(successor, previous.join(edgeState));
+ updateBlockEntryStateForBlock(successor, edgeState, blockEntryStates);
}
});
}
- boolean shouldCacheBlockEntryStateFor(Block block) {
+ void updateBlockEntryStateCacheForExceptionalSuccessors(
+ Block block, Instruction instruction, StateType state) {
+ cfg.forEachExceptionalSuccessor(
+ block,
+ exceptionalSuccessor -> {
+ StateType edgeState =
+ transfer.computeExceptionalBlockEntryState(
+ exceptionalSuccessor, block, instruction, state);
+ updateBlockEntryStateForBlock(
+ exceptionalSuccessor, edgeState, exceptionalBlockEntryStates);
+ });
+ }
+
+ private void updateBlockEntryStateForBlock(
+ Block block, StateType edgeState, Map<Block, StateType> states) {
+ StateType previous = states.getOrDefault(block, bottom);
+ states.put(block, previous.join(edgeState));
+ }
+
+ public boolean isIntermediateBlock(Block block) {
+ return options.isCollapsingOfTrivialEdgesEnabled()
+ && cfg.hasUniquePredecessorWithUniqueSuccessor(block)
+ && block != cfg.getEntryBlock()
+ && !cfg.hasExceptionalPredecessors(block);
+ }
+
+ public boolean isBlockWithIntermediateSuccessorBlock(Block block) {
+ return cfg.hasUniqueSuccessor(block) && isIntermediateBlock(cfg.getUniqueSuccessor(block));
+ }
+
+ boolean shouldCacheBlockEntryStateForNormalBlock(Block block) {
return TraversalUtils.isSizeGreaterThan(counter -> cfg.traversePredecessors(block, counter), 2);
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java
index 4918dfe..9f3ea94 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/IntraproceduralDataflowAnalysis.java
@@ -19,7 +19,7 @@
}
@Override
- boolean shouldCacheBlockEntryStateFor(BasicBlock block) {
+ boolean shouldCacheBlockEntryStateForNormalBlock(BasicBlock block) {
return block.getPredecessors().size() > 2;
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfBlock.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfBlock.java
index 357ff33..942cb97 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfBlock.java
@@ -6,6 +6,7 @@
import com.android.tools.r8.cf.code.CfInstruction;
import com.android.tools.r8.graph.CfCode;
+import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.SetUtils;
import java.util.ArrayList;
import java.util.Collection;
@@ -90,10 +91,14 @@
this.lastInstructionIndex = lastInstructionIndex;
}
- boolean validate() {
+ boolean validate(CfControlFlowGraph cfg, InternalOptions options) {
assert 0 <= firstInstructionIndex;
assert firstInstructionIndex <= lastInstructionIndex;
assert SetUtils.newIdentityHashSet(predecessors).size() == predecessors.size();
+ assert this == cfg.getEntryBlock()
+ || !predecessors.isEmpty()
+ || !exceptionalPredecessors.isEmpty()
+ || options.getCfCodeAnalysisOptions().isUnreachableCfBlocksAllowed();
return true;
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfControlFlowGraph.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfControlFlowGraph.java
index ff69065..4fe4724 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfControlFlowGraph.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfControlFlowGraph.java
@@ -12,12 +12,17 @@
import com.android.tools.r8.graph.CfCode;
import com.android.tools.r8.ir.analysis.framework.intraprocedural.ControlFlowGraph;
import com.android.tools.r8.ir.analysis.framework.intraprocedural.cf.CfBlock.MutableCfBlock;
-import com.android.tools.r8.utils.IterableUtils;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.TraversalUtils;
+import it.unimi.dsi.fastutil.objects.Reference2IntMap;
+import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
+import java.util.ArrayDeque;
import java.util.ArrayList;
-import java.util.Collections;
+import java.util.Deque;
import java.util.IdentityHashMap;
+import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
@@ -48,8 +53,8 @@
return new Builder(code);
}
- public static CfControlFlowGraph create(CfCode code) {
- return builder(code).build();
+ public static CfControlFlowGraph create(CfCode code, InternalOptions options) {
+ return builder(code).build(options);
}
private CfBlock getBlock(CfInstruction blockEntry) {
@@ -127,7 +132,7 @@
this.code = code;
}
- CfControlFlowGraph build() {
+ CfControlFlowGraph build(InternalOptions options) {
// Perform an initial pass over the CfCode to identify all instructions that start a new
// block.
createBlocks();
@@ -137,9 +142,11 @@
// identified all block entries up front.
processBlocks();
- assert blocks.values().stream().allMatch(MutableCfBlock::validate);
+ removeBlockForTrailingLabel();
- return new CfControlFlowGraph(blocks, code);
+ CfControlFlowGraph cfg = new CfControlFlowGraph(blocks, code);
+ assert blocks.values().stream().allMatch(block -> block.validate(cfg, options));
+ return cfg;
}
private void createBlocks() {
@@ -158,6 +165,11 @@
? instructions.get(fallthroughInstructionIndex)
: null;
instruction.forEachNormalTarget(this::createBlockIfAbsent, fallthroughInstruction);
+
+ // Also create a block for the fallthrough instruction, though it may be unreachable.
+ if (!instruction.asJump().hasFallthrough() && fallthroughInstruction != null) {
+ createBlockIfAbsent(fallthroughInstruction);
+ }
}
}
@@ -173,19 +185,25 @@
}
private void processBlocks() {
- // A collection of active catch handlers. The catch handlers are stored in a map where the key
- // is the label at which the catch handlers end.
- Map<CfLabel, List<CfTryCatch>> activeUntilCatchHandlers = new IdentityHashMap<>();
+ // A collection of active catch handlers. The most recently added catch handlers take
+ // precedence over catch handlers added before them.
+ Deque<CfTryCatch> activeCatchHandlers = new ArrayDeque<>();
// A collection of inactive catch handlers. The catch handlers are stored in a map where the
// key is the label at which the catch handlers start.
Map<CfLabel, List<CfTryCatch>> inactiveUntilCatchHandlers = new IdentityHashMap<>();
// Initialize all catch handlers to be inactive.
+ Reference2IntMap<CfLabel> labelIndices = computeLabelToInstructionIndexMapForTesting();
for (CfTryCatch tryCatch : code.getTryCatchRanges()) {
- inactiveUntilCatchHandlers
- .computeIfAbsent(tryCatch.getStart(), ignoreKey(ArrayList::new))
- .add(tryCatch);
+ List<CfTryCatch> inactiveCatchHandlersUntilStart =
+ inactiveUntilCatchHandlers.computeIfAbsent(
+ tryCatch.getStart(), ignoreKey(ArrayList::new));
+ // Catch handlers that come before others are expected to end first.
+ assert inactiveCatchHandlersUntilStart.isEmpty()
+ || labelIndices.getInt(tryCatch.getEnd())
+ >= labelIndices.getInt(ListUtils.last(inactiveCatchHandlersUntilStart).getEnd());
+ inactiveCatchHandlersUntilStart.add(tryCatch);
}
// Process each instruction.
@@ -199,40 +217,55 @@
instruction,
instructionIndex,
block,
- activeUntilCatchHandlers,
+ activeCatchHandlers,
inactiveUntilCatchHandlers);
}
}
- assert activeUntilCatchHandlers.isEmpty();
+ assert activeCatchHandlers.isEmpty();
assert inactiveUntilCatchHandlers.isEmpty();
}
+ private Reference2IntMap<CfLabel> computeLabelToInstructionIndexMapForTesting() {
+ if (!InternalOptions.assertionsEnabled()) {
+ return null;
+ }
+ Reference2IntMap<CfLabel> result = new Reference2IntOpenHashMap<>();
+ List<CfInstruction> instructions = code.getInstructions();
+ for (int instructionIndex = 0; instructionIndex < instructions.size(); instructionIndex++) {
+ CfInstruction instruction = instructions.get(instructionIndex);
+ if (instruction.isLabel()) {
+ result.put(instruction.asLabel(), instructionIndex);
+ }
+ }
+ return result;
+ }
+
private int processBlock(
CfInstruction instruction,
int instructionIndex,
MutableCfBlock block,
- Map<CfLabel, List<CfTryCatch>> activeUntilCatchHandlers,
+ Deque<CfTryCatch> activeCatchHandlers,
Map<CfLabel, List<CfTryCatch>> inactiveUntilCatchHandlers) {
// Record the index of the first instruction of the block.
block.setFirstInstructionIndex(instructionIndex);
if (instruction.isLabel()) {
- updateCatchHandlers(
- instruction.asLabel(), activeUntilCatchHandlers, inactiveUntilCatchHandlers);
+ updateCatchHandlers(instruction.asLabel(), activeCatchHandlers, inactiveUntilCatchHandlers);
}
// Visit each instruction belonging to the current block.
Set<CfLabel> exceptionalSuccessors = new LinkedHashSet<>();
+ Iterator<CfTryCatch> activeCatchHandlerIterator = activeCatchHandlers.descendingIterator();
+ while (activeCatchHandlerIterator.hasNext()) {
+ CfTryCatch activeCatchHandler = activeCatchHandlerIterator.next();
+ activeCatchHandler.forEachTarget(exceptionalSuccessors::add);
+ }
+
do {
assert !instruction.isLabel()
|| verifyCatchHandlersUnchanged(
- instruction.asLabel(), activeUntilCatchHandlers, inactiveUntilCatchHandlers);
- if (instruction.canThrow()) {
- for (CfTryCatch tryCatch : IterableUtils.flatten(activeUntilCatchHandlers.values())) {
- exceptionalSuccessors.addAll(tryCatch.getTargets());
- }
- }
+ instruction.asLabel(), activeCatchHandlers, inactiveUntilCatchHandlers);
if (isBlockExit(instructionIndex)) {
break;
}
@@ -258,6 +291,13 @@
return instructionIndex;
}
+ private void removeBlockForTrailingLabel() {
+ CfInstruction lastInstruction = code.getInstruction(code.getInstructions().size() - 1);
+ if (lastInstruction.isLabel() && isBlockEntry(lastInstruction)) {
+ blocks.remove(lastInstruction);
+ }
+ }
+
private boolean isBlockEntry(CfInstruction instruction) {
return blocks.containsKey(instruction);
}
@@ -273,26 +313,31 @@
private void updateCatchHandlers(
CfLabel instruction,
- Map<CfLabel, List<CfTryCatch>> activeUntilCatchHandlers,
+ Deque<CfTryCatch> activeCatchHandlers,
Map<CfLabel, List<CfTryCatch>> inactiveUntilCatchHandlers) {
// Remove active catch handlers that have expired at the current instruction.
- activeUntilCatchHandlers.remove(instruction);
+ while (!activeCatchHandlers.isEmpty()
+ && activeCatchHandlers.peekLast().getEnd() == instruction) {
+ activeCatchHandlers.removeLast();
+ }
// Promote inactive catch handlers that is activated at the current instruction to active.
- for (CfTryCatch tryCatch :
- inactiveUntilCatchHandlers.getOrDefault(instruction, Collections.emptyList())) {
- assert tryCatch.getEnd() != tryCatch.getStart();
- activeUntilCatchHandlers
- .computeIfAbsent(tryCatch.getEnd(), ignoreKey(ArrayList::new))
- .add(tryCatch);
+ List<CfTryCatch> newlyActiveCatchHandlers = inactiveUntilCatchHandlers.remove(instruction);
+ if (newlyActiveCatchHandlers != null) {
+ for (int i = newlyActiveCatchHandlers.size() - 1; i >= 0; i--) {
+ CfTryCatch newlyActiveCatchHandler = newlyActiveCatchHandlers.get(i);
+ assert newlyActiveCatchHandler.getEnd() != newlyActiveCatchHandler.getStart();
+ activeCatchHandlers.addLast(newlyActiveCatchHandler);
+ }
}
}
private boolean verifyCatchHandlersUnchanged(
CfLabel instruction,
- Map<CfLabel, List<CfTryCatch>> activeUntilCatchHandlers,
+ Deque<CfTryCatch> activeCatchHandlers,
Map<CfLabel, List<CfTryCatch>> inactiveUntilCatchHandlers) {
- assert !activeUntilCatchHandlers.containsKey(instruction);
+ assert activeCatchHandlers.isEmpty()
+ || activeCatchHandlers.peekLast().getEnd() != instruction;
assert !inactiveUntilCatchHandlers.containsKey(instruction);
return true;
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index feaca12..7cb6f50 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -22,6 +22,7 @@
import com.android.tools.r8.ir.analysis.fieldvalueanalysis.AbstractFieldSet;
import com.android.tools.r8.ir.analysis.fieldvalueanalysis.EmptyFieldSet;
import com.android.tools.r8.ir.analysis.fieldvalueanalysis.UnknownFieldSet;
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.AbstractInstruction;
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.analysis.value.AbstractValue;
import com.android.tools.r8.ir.analysis.value.UnknownValue;
@@ -46,7 +47,8 @@
import java.util.function.Function;
import java.util.function.Predicate;
-public abstract class Instruction implements InstructionOrPhi, TypeAndLocalInfoSupplier {
+public abstract class Instruction
+ implements AbstractInstruction, InstructionOrPhi, TypeAndLocalInfoSupplier {
protected Value outValue = null;
protected final List<Value> inValues = new ArrayList<>();
@@ -604,9 +606,8 @@
return false;
}
- /**
- * Returns true if this instruction may throw an exception.
- */
+ /** Returns true if this instruction may throw an exception. */
+ @Override
public boolean instructionTypeCanThrow() {
return false;
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/TransferFunction.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/TransferFunction.java
index e4bbb6c..a955882 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/TransferFunction.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/analysis/TransferFunction.java
@@ -149,6 +149,15 @@
return predecessorExitState;
}
+ @Override
+ public ParameterUsages computeExceptionalBlockEntryState(
+ BasicBlock block,
+ BasicBlock throwBlock,
+ Instruction throwInstruction,
+ ParameterUsages throwState) {
+ return throwState;
+ }
+
private ParameterUsages analyzeArgument(Argument argument, ParameterUsages state) {
// Only consider arguments that could store an instance eligible for class inlining. Note that
// we can't ignore parameters with a library type, since instances of program classes could
diff --git a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysis.java b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysis.java
index 33e4cf2..121b5ab 100644
--- a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysis.java
+++ b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfOpenClosedInterfacesAnalysis.java
@@ -5,6 +5,7 @@
package com.android.tools.r8.optimize.interfaces.analysis;
import com.android.tools.r8.cf.code.CfInstruction;
+import com.android.tools.r8.errors.Unimplemented;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.CfCode;
import com.android.tools.r8.graph.Code;
@@ -44,7 +45,7 @@
}
CfCode cfCode = code.asCfCode();
- CfControlFlowGraph cfg = CfControlFlowGraph.create(cfCode);
+ CfControlFlowGraph cfg = CfControlFlowGraph.create(cfCode, appView.options());
CfIntraproceduralDataflowAnalysis<CfFrameState> analysis =
new CfIntraproceduralDataflowAnalysis<>(
CfFrameState.bottom(), cfg, new TransferFunction(method));
@@ -97,5 +98,15 @@
CfBlock block, CfBlock predecessor, CfFrameState predecessorExitState) {
return predecessorExitState;
}
+
+ @Override
+ public CfFrameState computeExceptionalBlockEntryState(
+ CfBlock block,
+ CfBlock throwBlock,
+ CfInstruction throwInstruction,
+ CfFrameState throwState) {
+ // TODO(b/214496607): Handle exceptional control flow.
+ throw new Unimplemented();
+ }
}
}
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index 14dd120..71e92a3 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -808,6 +808,7 @@
private final CallSiteOptimizationOptions callSiteOptimizationOptions =
new CallSiteOptimizationOptions();
+ private final CfCodeAnalysisOptions cfCodeAnalysisOptions = new CfCodeAnalysisOptions();
private final ClassInlinerOptions classInlinerOptions = new ClassInlinerOptions();
private final InlinerOptions inlinerOptions = new InlinerOptions();
private final HorizontalClassMergerOptions horizontalClassMergerOptions =
@@ -867,6 +868,10 @@
return desugarSpecificOptions;
}
+ public CfCodeAnalysisOptions getCfCodeAnalysisOptions() {
+ return cfCodeAnalysisOptions;
+ }
+
public OpenClosedInterfacesOptions getOpenClosedInterfacesOptions() {
return openClosedInterfacesOptions;
}
@@ -1399,6 +1404,19 @@
}
}
+ public static class CfCodeAnalysisOptions {
+
+ public boolean allowUnreachableCfBlocks = true;
+
+ public boolean isUnreachableCfBlocksAllowed() {
+ return allowUnreachableCfBlocks;
+ }
+
+ public void setAllowUnreachableCfBlocks(boolean allowUnreachableCfBlocks) {
+ this.allowUnreachableCfBlocks = allowUnreachableCfBlocks;
+ }
+ }
+
public class ClassInlinerOptions {
public int classInliningInstructionAllowance = -1;
diff --git a/src/main/java/com/android/tools/r8/utils/TraversalUtils.java b/src/main/java/com/android/tools/r8/utils/TraversalUtils.java
index 25e1be0..b705d02 100644
--- a/src/main/java/com/android/tools/r8/utils/TraversalUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/TraversalUtils.java
@@ -18,6 +18,16 @@
return traversal.apply(TraversalContinuation::doBreak).asBreak().getValue();
}
+ public static <BT, CT> boolean hasNext(
+ Consumer<Function<CT, TraversalContinuation<BT, CT>>> traversal) {
+ return !isEmpty(traversal);
+ }
+
+ public static <BT, CT> boolean isEmpty(
+ Consumer<Function<CT, TraversalContinuation<BT, CT>>> traversal) {
+ return isSizeExactly(traversal, 0);
+ }
+
public static <BT, CT> boolean isSingleton(
Consumer<Function<CT, TraversalContinuation<BT, CT>>> traversal) {
return isSizeExactly(traversal, 1);
diff --git a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
index d7a6cc2..7956f69 100644
--- a/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
+++ b/src/test/java/com/android/tools/r8/TestCompilerBuilder.java
@@ -11,7 +11,6 @@
import com.android.tools.r8.TestBase.Backend;
import com.android.tools.r8.benchmarks.BenchmarkResults;
import com.android.tools.r8.debug.DebugTestConfig;
-import com.android.tools.r8.desugar.desugaredlibrary.DesugaredLibraryTestBase.KeepRuleConsumer;
import com.android.tools.r8.optimize.argumentpropagation.ArgumentPropagatorEventConsumer;
import com.android.tools.r8.optimize.argumentpropagation.codescanner.MethodStateCollectionByReference;
import com.android.tools.r8.testing.AndroidBuildVersion;
@@ -59,6 +58,7 @@
options.testing.reportUnusedProguardConfigurationRules = true;
options.horizontalClassMergerOptions().enable();
options.horizontalClassMergerOptions().setEnableInterfaceMerging();
+ options.getCfCodeAnalysisOptions().setAllowUnreachableCfBlocks(false);
options.getOpenClosedInterfacesOptions().disallowOpenInterfaces();
};
