Value-based worklist in type analysis.
Bug: 69964136, 72693244
Change-Id: I32c8f41a362ea74ae77813c3a2bc6d5d88aefa68
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
index 4138b8c..ba08ebb 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
@@ -6,7 +6,6 @@
import com.android.tools.r8.graph.AppInfo;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexType;
-import com.android.tools.r8.ir.code.Argument;
import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.Instruction;
@@ -15,22 +14,18 @@
import com.android.tools.r8.ir.code.Value;
import com.google.common.annotations.VisibleForTesting;
import com.google.common.collect.Maps;
-import com.google.common.collect.Sets;
import java.util.ArrayDeque;
-import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.Map;
-import java.util.Set;
import java.util.function.BiConsumer;
public class TypeAnalysis implements TypeEnvironment {
private final AppInfo appInfo;
private final DexEncodedMethod encodedMethod;
- private final Deque<BasicBlock> worklist = new ArrayDeque<>();
+ private final Deque<Value> worklist = new ArrayDeque<>();
private final Map<Value, TypeLatticeElement> typeMap = Maps.newHashMap();
- private final Map<Value, Set<BasicBlock>> users = Maps.newHashMap();
public TypeAnalysis(AppInfo appInfo, DexEncodedMethod encodedMethod, IRCode code) {
this.appInfo = appInfo;
@@ -41,27 +36,30 @@
@Override
public void analyzeBlocks(List<BasicBlock> blocks) {
assert worklist.isEmpty();
- worklist.addAll(blocks);
+ for (BasicBlock block : blocks) {
+ processBasicBlock(block);
+ }
while (!worklist.isEmpty()) {
- processBasicBlock(worklist.poll());
+ processValue(worklist.poll());
}
}
- private void addToWorklist(BasicBlock block) {
- if (!worklist.contains(block)) {
- worklist.add(block);
+ private void addToWorklist(Value v) {
+ assert v != null;
+ if (!worklist.contains(v)) {
+ worklist.add(v);
}
}
private void processBasicBlock(BasicBlock block) {
int argumentsSeen = encodedMethod.accessFlags.isStatic() ? 0 : -1;
for (Instruction instruction : block.getInstructions()) {
- TypeLatticeElement derived = Bottom.getInstance();
Value outValue = instruction.outValue();
// Argument, a quasi instruction, needs to be handled specially:
// 1) We can derive its type from the method signature; and
// 2) It does not have an out value, so we can skip the env updating.
- if (instruction instanceof Argument) {
+ if (instruction.isArgument()) {
+ TypeLatticeElement derived;
if (argumentsSeen < 0) {
// Receiver
derived = TypeLatticeElement.fromDexType(encodedMethod.method.holder, false);
@@ -70,49 +68,46 @@
derived = TypeLatticeElement.fromDexType(argType, true);
}
argumentsSeen++;
+ assert outValue != null;
+ updateTypeOfValue(outValue, derived);
} else {
- // Register this block as a user for in values to revisit this if in values are updated.
- instruction.inValues()
- .forEach(v -> registerAsUserOfValue(v, block, Sets.newIdentityHashSet()));
if (outValue != null) {
- derived = instruction.evaluate(appInfo, this::getLatticeElement);
- }
- }
- if (outValue != null) {
- TypeLatticeElement current = getLatticeElement(outValue);
- if (!current.equals(derived)) {
- updateTypeOfValue(outValue, derived);
+ addToWorklist(outValue);
}
}
}
for (Phi phi : block.getPhis()) {
- TypeLatticeElement phiType = computePhiType(phi);
- if (!getLatticeElement(phi).equals(phiType)) {
- updateTypeOfValue(phi, phiType);
- }
+ addToWorklist(phi);
}
}
- private void registerAsUserOfValue(Value value, BasicBlock block, Set<Value> seenPhis) {
- if (value.isPhi() && seenPhis.add(value)) {
- for (Value operand : value.asPhi().getOperands()) {
- registerAsUserOfValue(operand, block, seenPhis);
- }
- } else {
- users.computeIfAbsent(value, k -> Sets.newIdentityHashSet()).add(block);
- }
+ private void processValue(Value value) {
+ TypeLatticeElement derived =
+ value.isPhi()
+ ? computePhiType(value.asPhi())
+ : value.definition.evaluate(appInfo, this::getLatticeElement);
+ updateTypeOfValue(value, derived);
}
private void updateTypeOfValue(Value value, TypeLatticeElement type) {
+ TypeLatticeElement current = getLatticeElement(value);
+ if (current.equals(type)) {
+ return;
+ }
+ // TODO(b/72693244): attach type lattice directly to Value.
setLatticeElement(value, type);
- // Revisit the blocks that use the value whose type binding has just been updated.
- users.getOrDefault(value, Collections.emptySet()).forEach(this::addToWorklist);
+ // propagate the type change to (instruction) users if any.
+ for (Instruction instruction : value.uniqueUsers()) {
+ Value outValue = instruction.outValue();
+ if (outValue != null) {
+ // TODO(b/72693244): processValue instead of queueing.
+ addToWorklist(outValue);
+ }
+ }
// Propagate the type change to phi users if any.
for (Phi phi : value.uniquePhiUsers()) {
- TypeLatticeElement phiType = computePhiType(phi);
- if (!getLatticeElement(phi).equals(phiType)) {
- updateTypeOfValue(phi, phiType);
- }
+ // TODO(b/72693244): processValue instead of queueing.
+ addToWorklist(phi);
}
}
