Extend cf analysis to cover exceptional control flow
Bug: b/236240410
Change-Id: I5c715a71a34c87c1178105c5422172adf255e43d
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 a0a7ba0..51e185c 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
@@ -8,6 +8,7 @@
import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.TraversalUtils;
import com.android.tools.r8.utils.TriFunction;
+import java.util.Collection;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Consumer;
@@ -15,6 +16,8 @@
public interface ControlFlowGraph<Block, Instruction> {
+ Collection<? extends Block> getBlocks();
+
Block getEntryBlock();
default Block getUniquePredecessor(Block block) {
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 7986623..dc0c539 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
@@ -9,6 +9,7 @@
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.SetUtils;
+import com.android.tools.r8.utils.StringUtils;
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
@@ -22,6 +23,9 @@
// The CfCode instruction index of the block's first instruction.
int firstInstructionIndex = -1;
+ // The CfCode instruction index of the block's first throwing instruction.
+ int firstThrowingInstructionIndex = -1;
+
// The CfCode instruction index of the block's last instruction.
int lastInstructionIndex = -1;
@@ -46,6 +50,14 @@
return firstInstructionIndex;
}
+ public boolean hasThrowingInstruction() {
+ return firstThrowingInstructionIndex >= 0;
+ }
+
+ public int getFirstThrowingInstructionIndex() {
+ return firstThrowingInstructionIndex;
+ }
+
public CfInstruction getLastInstruction(CfCode code) {
return code.getInstructions().get(lastInstructionIndex);
}
@@ -66,6 +78,22 @@
return exceptionalSuccessors;
}
+ @Override
+ public String toString() {
+ List<String> predecessorStrings = new ArrayList<>();
+ predecessors.forEach(p -> predecessorStrings.add(p.getRangeString()));
+ exceptionalPredecessors.forEach(p -> predecessorStrings.add("*" + p.getRangeString()));
+ return "CfBlock(range="
+ + getRangeString()
+ + ", predecessors="
+ + StringUtils.join(", ", predecessorStrings)
+ + ")";
+ }
+
+ private String getRangeString() {
+ return firstInstructionIndex + "->" + lastInstructionIndex;
+ }
+
// A mutable interface for block construction.
static class MutableCfBlock extends CfBlock {
@@ -86,6 +114,10 @@
this.firstInstructionIndex = firstInstructionIndex;
}
+ void setFirstThrowingInstructionIndex(int firstThrowingInstructionIndex) {
+ this.firstThrowingInstructionIndex = firstThrowingInstructionIndex;
+ }
+
void setLastInstructionIndex(int lastInstructionIndex) {
this.lastInstructionIndex = lastInstructionIndex;
}
@@ -93,6 +125,10 @@
boolean validate(CfControlFlowGraph cfg, InternalOptions options) {
assert 0 <= firstInstructionIndex;
assert firstInstructionIndex <= lastInstructionIndex;
+ assert firstThrowingInstructionIndex < 0
+ || firstInstructionIndex <= firstThrowingInstructionIndex;
+ assert firstThrowingInstructionIndex < 0
+ || firstThrowingInstructionIndex <= lastInstructionIndex;
assert SetUtils.newIdentityHashSet(predecessors).size() == predecessors.size();
assert this == cfg.getEntryBlock()
|| !predecessors.isEmpty()
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 2b58157..7069adb 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
@@ -22,6 +22,7 @@
import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap;
import java.util.ArrayDeque;
import java.util.ArrayList;
+import java.util.Collection;
import java.util.Deque;
import java.util.IdentityHashMap;
import java.util.Iterator;
@@ -64,6 +65,11 @@
}
@Override
+ public Collection<? extends CfBlock> getBlocks() {
+ return blocks.values();
+ }
+
+ @Override
public CfBlock getEntryBlock() {
return getBlock(code.getInstruction(0));
}
@@ -270,6 +276,9 @@
assert !instruction.isLabel()
|| verifyCatchHandlersUnchanged(
instruction.asLabel(), activeCatchHandlers, inactiveUntilCatchHandlers);
+ if (instruction.instructionTypeCanThrow() && !block.hasThrowingInstruction()) {
+ block.setFirstThrowingInstructionIndex(instructionIndex);
+ }
if (isBlockExit(instructionIndex)) {
break;
}
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 409d050..dbcd9be 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
@@ -1364,6 +1364,7 @@
}
}
+ @Override
public LinkedList<BasicBlock> getBlocks() {
return blocks;
}
diff --git a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/BottomCfFrameState.java b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/BottomCfFrameState.java
index 6ffdfef..98e576b 100644
--- a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/BottomCfFrameState.java
+++ b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/BottomCfFrameState.java
@@ -100,6 +100,11 @@
}
@Override
+ public CfFrameState pushException(CfAnalysisConfig config, DexType guard) {
+ return this;
+ }
+
+ @Override
public CfFrameState readLocal(
AppView<?> appView,
int localIndex,
diff --git a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfFrameState.java b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfFrameState.java
index 239cb8e..c14a235 100644
--- a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfFrameState.java
+++ b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/CfFrameState.java
@@ -291,6 +291,8 @@
return push(config, valueType.toDexType(appView.dexItemFactory()));
}
+ public abstract CfFrameState pushException(CfAnalysisConfig config, DexType guard);
+
public abstract CfFrameState readLocal(
AppView<?> appView,
int localIndex,
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 b21c294..a6d436c 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,7 +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.cf.code.frame.FrameType;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.CfCode;
import com.android.tools.r8.graph.Code;
@@ -56,12 +56,15 @@
private class TransferFunction
implements AbstractTransferFunction<CfBlock, CfInstruction, CfFrameState> {
+ private final CfCode code;
private final CfAnalysisConfig config;
+ private final ProgramMethod context;
TransferFunction(ProgramMethod context) {
CfCode code = context.getDefinition().getCode().asCfCode();
int maxLocals = code.getMaxLocals();
int maxStack = code.getMaxStack();
+ this.code = code;
this.config =
new CfAnalysisConfig() {
@@ -85,6 +88,7 @@
return type == context.getHolder().getSuperType();
}
};
+ this.context = context;
}
@Override
@@ -94,20 +98,51 @@
}
@Override
+ public CfFrameState computeInitialState(CfBlock entryBlock, CfFrameState bottom) {
+ CfFrameState initialState = new ConcreteCfFrameState();
+ int localIndex = 0;
+ if (context.getDefinition().isInstance()) {
+ if (context.getDefinition().isInstanceInitializer()) {
+ initialState = initialState.storeLocal(localIndex, FrameType.uninitializedThis(), config);
+ } else {
+ initialState =
+ initialState.storeLocal(
+ localIndex, FrameType.initialized(context.getHolderType()), config);
+ }
+ localIndex++;
+ }
+ for (DexType parameter : context.getParameters()) {
+ initialState =
+ initialState.storeLocal(localIndex, FrameType.initialized(parameter), config);
+ localIndex += parameter.getRequiredRegisters();
+ }
+ return initialState;
+ }
+
+ @Override
public CfFrameState computeBlockEntryState(
CfBlock block, CfBlock predecessor, CfFrameState predecessorExitState) {
return predecessorExitState;
}
@Override
+ public boolean shouldTransferExceptionalControlFlowFromInstruction(
+ CfBlock throwBlock, CfInstruction throwInstruction) {
+ // All locals defined after the first throwing instruction cannot be accessed in the catch
+ // handler. Therefore, we only propagate the state from the first throwing instruction to the
+ // catch handler.
+ assert throwBlock.hasThrowingInstruction();
+ return throwInstruction == code.getInstruction(throwBlock.getFirstThrowingInstructionIndex());
+ }
+
+ @Override
public CfFrameState computeExceptionalBlockEntryState(
CfBlock block,
DexType guard,
CfBlock throwBlock,
CfInstruction throwInstruction,
CfFrameState throwState) {
- // TODO(b/214496607): Handle exceptional control flow.
- throw new Unimplemented();
+ return throwState.pushException(config, guard);
}
}
}
diff --git a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/ConcreteCfFrameState.java b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/ConcreteCfFrameState.java
index b5df6e6..acc1f3d 100644
--- a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/ConcreteCfFrameState.java
+++ b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/ConcreteCfFrameState.java
@@ -262,6 +262,15 @@
}
@Override
+ public CfFrameState pushException(CfAnalysisConfig config, DexType guard) {
+ Int2ObjectAVLTreeMap<FrameType> newLocals = new Int2ObjectAVLTreeMap<>(locals);
+ ArrayDeque<PreciseFrameType> newStack = new ArrayDeque<>();
+ int newStackHeight = 0;
+ return new ConcreteCfFrameState(newLocals, newStack, newStackHeight)
+ .push(config, FrameType.initialized(guard));
+ }
+
+ @Override
public CfFrameState readLocal(
AppView<?> appView,
int localIndex,
diff --git a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/ErroneousCfFrameState.java b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/ErroneousCfFrameState.java
index 892d57b..eda488a 100644
--- a/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/ErroneousCfFrameState.java
+++ b/src/main/java/com/android/tools/r8/optimize/interfaces/analysis/ErroneousCfFrameState.java
@@ -185,6 +185,11 @@
}
@Override
+ public CfFrameState pushException(CfAnalysisConfig config, DexType guard) {
+ return this;
+ }
+
+ @Override
public CfFrameState readLocal(
AppView<?> appView,
int localIndex,
