Instantiate existing dataflow analysis framework for cf code
Change-Id: I7a0a4bbb4a083bfc175fa587fc7194dd88a84b71
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfGoto.java b/src/main/java/com/android/tools/r8/cf/code/CfGoto.java
index fa3a8a5..07f135e 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfGoto.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfGoto.java
@@ -19,7 +19,9 @@
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.InliningConstraints;
import com.android.tools.r8.naming.NamingLens;
+import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.structural.CompareToVisitor;
+import java.util.function.BiFunction;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
@@ -63,6 +65,14 @@
}
@Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseNormalTargets(
+ BiFunction<? super CfInstruction, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CfInstruction fallthroughInstruction,
+ CT initialValue) {
+ return fn.apply(target, initialValue);
+ }
+
+ @Override
public void write(
AppView<?> appView,
ProgramMethod context,
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfIf.java b/src/main/java/com/android/tools/r8/cf/code/CfIf.java
index 833ac44..d1f2eb1 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfIf.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfIf.java
@@ -23,7 +23,9 @@
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.InliningConstraints;
import com.android.tools.r8.naming.NamingLens;
+import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.structural.CompareToVisitor;
+import java.util.function.BiFunction;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
@@ -66,6 +68,16 @@
return target;
}
+ @Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseNormalTargets(
+ BiFunction<? super CfInstruction, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CfInstruction fallthroughInstruction,
+ CT initialValue) {
+ return fn.apply(target, initialValue)
+ .ifContinueThen(
+ continuation -> fn.apply(fallthroughInstruction, continuation.getValueOrDefault(null)));
+ }
+
public int getOpcode() {
switch (kind) {
case EQ:
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfIfCmp.java b/src/main/java/com/android/tools/r8/cf/code/CfIfCmp.java
index c8129a6..37b1c2b 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfIfCmp.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfIfCmp.java
@@ -24,7 +24,9 @@
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.InliningConstraints;
import com.android.tools.r8.naming.NamingLens;
+import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.structural.CompareToVisitor;
+import java.util.function.BiFunction;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
@@ -67,6 +69,16 @@
return target;
}
+ @Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseNormalTargets(
+ BiFunction<? super CfInstruction, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CfInstruction fallthroughInstruction,
+ CT initialValue) {
+ return fn.apply(target, initialValue)
+ .ifContinueThen(
+ continuation -> fn.apply(fallthroughInstruction, continuation.getValueOrDefault(null)));
+ }
+
public int getOpcode() {
switch (kind) {
case EQ:
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 40b9737..58c8280 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
@@ -25,8 +25,11 @@
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.InliningConstraints;
import com.android.tools.r8.naming.NamingLens;
+import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.structural.CompareToVisitor;
import java.util.ListIterator;
+import java.util.function.BiFunction;
+import java.util.function.Consumer;
import org.objectweb.asm.MethodVisitor;
public abstract class CfInstruction implements CfOrDexInstruction {
@@ -106,6 +109,26 @@
return null;
}
+ public final void forEachNormalTarget(
+ Consumer<? super CfInstruction> consumer, CfInstruction fallthroughInstruction) {
+ traverseNormalTargets(
+ (target, ignore) -> {
+ consumer.accept(target);
+ return TraversalContinuation.doContinue();
+ },
+ fallthroughInstruction,
+ null);
+ }
+
+ public <BT, CT> TraversalContinuation<BT, CT> traverseNormalTargets(
+ BiFunction<? super CfInstruction, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CfInstruction fallthroughInstruction,
+ CT initialValue) {
+ // The method is overridden in each jump instruction.
+ assert !isJump();
+ return fn.apply(fallthroughInstruction, initialValue);
+ }
+
@Override
public CfInstruction asCfInstruction() {
return this;
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfReturn.java b/src/main/java/com/android/tools/r8/cf/code/CfReturn.java
index d06db87..134e4d2 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfReturn.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfReturn.java
@@ -22,7 +22,9 @@
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.InliningConstraints;
import com.android.tools.r8.naming.NamingLens;
+import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.structural.CompareToVisitor;
+import java.util.function.BiFunction;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
@@ -72,6 +74,14 @@
}
@Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseNormalTargets(
+ BiFunction<? super CfInstruction, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CfInstruction fallthroughInstruction,
+ CT initialValue) {
+ return TraversalContinuation.doContinue(initialValue);
+ }
+
+ @Override
public boolean isJump() {
return true;
}
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfReturnVoid.java b/src/main/java/com/android/tools/r8/cf/code/CfReturnVoid.java
index d492b04..56eab9b 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfReturnVoid.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfReturnVoid.java
@@ -19,13 +19,23 @@
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.InliningConstraints;
import com.android.tools.r8.naming.NamingLens;
+import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.structural.CompareToVisitor;
+import java.util.function.BiFunction;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
public class CfReturnVoid extends CfInstruction {
@Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseNormalTargets(
+ BiFunction<? super CfInstruction, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CfInstruction fallthroughInstruction,
+ CT initialValue) {
+ return TraversalContinuation.doContinue(initialValue);
+ }
+
+ @Override
public boolean isJump() {
return true;
}
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfSwitch.java b/src/main/java/com/android/tools/r8/cf/code/CfSwitch.java
index a86bcd1..7e2564c 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfSwitch.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfSwitch.java
@@ -21,9 +21,12 @@
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.InliningConstraints;
import com.android.tools.r8.naming.NamingLens;
+import com.android.tools.r8.utils.TraversalContinuation;
+import com.android.tools.r8.utils.TraversalUtils;
import com.android.tools.r8.utils.structural.CompareToVisitor;
import it.unimi.dsi.fastutil.ints.IntArrayList;
import java.util.List;
+import java.util.function.BiFunction;
import org.objectweb.asm.Label;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
@@ -47,6 +50,16 @@
}
@Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseNormalTargets(
+ BiFunction<? super CfInstruction, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CfInstruction fallthroughInstruction,
+ CT initialValue) {
+ return TraversalUtils.traverseIterable(targets, fn, initialValue)
+ .ifContinueThen(
+ continuation -> fn.apply(defaultTarget, continuation.getValueOrDefault(null)));
+ }
+
+ @Override
public int getCompareToId() {
return kind == Kind.LOOKUP ? Opcodes.LOOKUPSWITCH : Opcodes.TABLESWITCH;
}
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfThrow.java b/src/main/java/com/android/tools/r8/cf/code/CfThrow.java
index 6e5eb78..6498e4f 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfThrow.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfThrow.java
@@ -20,13 +20,23 @@
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.InliningConstraints;
import com.android.tools.r8.naming.NamingLens;
+import com.android.tools.r8.utils.TraversalContinuation;
import com.android.tools.r8.utils.structural.CompareToVisitor;
+import java.util.function.BiFunction;
import org.objectweb.asm.MethodVisitor;
import org.objectweb.asm.Opcodes;
public class CfThrow extends CfInstruction {
@Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseNormalTargets(
+ BiFunction<? super CfInstruction, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CfInstruction fallthroughInstruction,
+ CT initialValue) {
+ return TraversalContinuation.doContinue(initialValue);
+ }
+
+ @Override
public boolean isJump() {
return true;
}
diff --git a/src/main/java/com/android/tools/r8/cf/code/CfTryCatch.java b/src/main/java/com/android/tools/r8/cf/code/CfTryCatch.java
index 2f821be..22aac9a 100644
--- a/src/main/java/com/android/tools/r8/cf/code/CfTryCatch.java
+++ b/src/main/java/com/android/tools/r8/cf/code/CfTryCatch.java
@@ -13,6 +13,7 @@
import com.android.tools.r8.utils.structural.CompareToVisitor;
import java.util.ArrayList;
import java.util.List;
+import java.util.function.Consumer;
public class CfTryCatch {
public final CfLabel start;
@@ -28,6 +29,22 @@
assert verifyAllNonNull(guards);
}
+ public void forEachTarget(Consumer<CfLabel> consumer) {
+ targets.forEach(consumer);
+ }
+
+ public CfLabel getStart() {
+ return start;
+ }
+
+ public CfLabel getEnd() {
+ return end;
+ }
+
+ public List<CfLabel> getTargets() {
+ return targets;
+ }
+
private static boolean verifyAllNonNull(List<DexType> types) {
for (DexType type : types) {
assert type != null;
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
new file mode 100644
index 0000000..b86915c
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfBlock.java
@@ -0,0 +1,97 @@
+// 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.cf;
+
+import com.android.tools.r8.cf.code.CfInstruction;
+import com.android.tools.r8.graph.CfCode;
+import com.android.tools.r8.utils.SetUtils;
+import java.util.ArrayList;
+import java.util.List;
+
+/** A basic block for {@link com.android.tools.r8.graph.CfCode}. */
+public class CfBlock {
+
+ // The CfCode instruction index of the block's first instruction.
+ int firstInstructionIndex = -1;
+
+ // The CfCode instruction index of the block's last instruction.
+ int lastInstructionIndex = -1;
+
+ // The predecessors of the block. These are stored explicitly (unlike the successors) since they
+ // cannot efficiently be computed from the block.
+ final List<CfBlock> predecessors = new ArrayList<>();
+
+ // The exceptional predecessors of the block.
+ final List<CfBlock> exceptionalPredecessors = new ArrayList<>();
+
+ // The exceptional successors of the block (i.e., the catch handlers of the block).
+ final List<CfBlock> exceptionalSuccessors = new ArrayList<>();
+
+ public CfInstruction getFallthroughInstruction(CfCode code) {
+ int fallthroughInstructionIndex = getLastInstructionIndex() + 1;
+ return fallthroughInstructionIndex < code.getInstructions().size()
+ ? code.getInstructions().get(fallthroughInstructionIndex)
+ : null;
+ }
+
+ public int getFirstInstructionIndex() {
+ return firstInstructionIndex;
+ }
+
+ public CfInstruction getLastInstruction(CfCode code) {
+ return code.getInstructions().get(lastInstructionIndex);
+ }
+
+ public int getLastInstructionIndex() {
+ return lastInstructionIndex;
+ }
+
+ public List<CfBlock> getPredecessors() {
+ return predecessors;
+ }
+
+ // TODO(b/214496607): This currently only encodes the graph, but we likely need to include the
+ // guard types here.
+ public List<CfBlock> getExceptionalPredecessors() {
+ return exceptionalPredecessors;
+ }
+
+ // TODO(b/214496607): This currently only encodes the graph, but we likely need to include the
+ // guard types here.
+ public List<CfBlock> getExceptionalSuccessors() {
+ return exceptionalSuccessors;
+ }
+
+ // A mutable interface for block construction.
+ static class MutableCfBlock extends CfBlock {
+
+ void addPredecessor(CfBlock block) {
+ predecessors.add(block);
+ }
+
+ void addExceptionalPredecessor(CfBlock block) {
+ exceptionalPredecessors.add(block);
+ }
+
+ void addExceptionalSuccessor(CfBlock block) {
+ exceptionalSuccessors.add(block);
+ }
+
+ void setFirstInstructionIndex(int firstInstructionIndex) {
+ this.firstInstructionIndex = firstInstructionIndex;
+ }
+
+ void setLastInstructionIndex(int lastInstructionIndex) {
+ this.lastInstructionIndex = lastInstructionIndex;
+ }
+
+ boolean validate() {
+ assert 0 <= firstInstructionIndex;
+ assert firstInstructionIndex <= lastInstructionIndex;
+ assert SetUtils.newIdentityHashSet(predecessors).size() == predecessors.size();
+ 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
new file mode 100644
index 0000000..878d32d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfControlFlowGraph.java
@@ -0,0 +1,110 @@
+// 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.cf;
+
+import com.android.tools.r8.cf.code.CfInstruction;
+import com.android.tools.r8.errors.Unimplemented;
+import com.android.tools.r8.graph.CfCode;
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.ControlFlowGraph;
+import com.android.tools.r8.utils.TraversalContinuation;
+import com.android.tools.r8.utils.TraversalUtils;
+import java.util.Map;
+import java.util.function.BiFunction;
+
+/**
+ * The following provides a control flow graph for a piece of {@link CfCode}.
+ *
+ * <p>In the {@link CfControlFlowGraph}, each instruction that is the target of a jump (including
+ * fallthrough targets following jumps) starts a new basic block. The first instruction in {@link
+ * CfCode} also starts a new block.
+ *
+ * <p>Each block is identified by the first instruction of the block.
+ */
+public class CfControlFlowGraph implements ControlFlowGraph<CfBlock, CfInstruction> {
+
+ // Mapping from block entry instructions to cf blocks.
+ private final Map<CfInstruction, ? extends CfBlock> blocks;
+ private final CfCode code;
+
+ private CfControlFlowGraph(Map<CfInstruction, ? extends CfBlock> blocks, CfCode code) {
+ this.blocks = blocks;
+ this.code = code;
+ }
+
+ private static Builder builder() {
+ return new Builder();
+ }
+
+ public static CfControlFlowGraph create(CfCode code) {
+ return builder().build(code);
+ }
+
+ private CfBlock getBlock(CfInstruction blockEntry) {
+ assert blocks.containsKey(blockEntry);
+ return blocks.get(blockEntry);
+ }
+
+ @Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseNormalPredecessors(
+ CfBlock block,
+ BiFunction<? super CfBlock, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CT initialValue) {
+ return TraversalUtils.traverseIterable(block.getPredecessors(), fn, initialValue);
+ }
+
+ @Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseExceptionalPredecessors(
+ CfBlock block,
+ BiFunction<? super CfBlock, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CT initialValue) {
+ return TraversalUtils.traverseIterable(block.getExceptionalPredecessors(), fn, initialValue);
+ }
+
+ @Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseNormalSuccessors(
+ CfBlock block,
+ BiFunction<? super CfBlock, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CT initialValue) {
+ CfInstruction blockExit = block.getLastInstruction(code);
+ CfInstruction fallthroughInstruction = block.getFallthroughInstruction(code);
+ return blockExit.traverseNormalTargets(
+ (target, value) -> fn.apply(getBlock(target), value), fallthroughInstruction, initialValue);
+ }
+
+ @Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseExceptionalSuccessors(
+ CfBlock block,
+ BiFunction<? super CfBlock, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CT initialValue) {
+ return TraversalUtils.traverseIterable(block.getExceptionalSuccessors(), fn, initialValue);
+ }
+
+ @Override
+ public <BT, CT> TraversalContinuation<BT, CT> traverseInstructions(
+ CfBlock block,
+ BiFunction<CfInstruction, CT, TraversalContinuation<BT, CT>> fn,
+ CT initialValue) {
+ TraversalContinuation<BT, CT> traversalContinuation =
+ TraversalContinuation.doContinue(initialValue);
+ for (int instructionIndex = block.getFirstInstructionIndex();
+ instructionIndex <= block.getLastInstructionIndex();
+ instructionIndex++) {
+ CfInstruction instruction = code.getInstructions().get(instructionIndex);
+ traversalContinuation = fn.apply(instruction, traversalContinuation.asContinue().getValue());
+ if (traversalContinuation.shouldBreak()) {
+ break;
+ }
+ }
+ return traversalContinuation;
+ }
+
+ private static class Builder {
+
+ CfControlFlowGraph build(CfCode code) {
+ // TODO(b/214496607): Implement cfg construction.
+ throw new Unimplemented();
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfIntraproceduralDataflowAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfIntraproceduralDataflowAnalysis.java
new file mode 100644
index 0000000..b4ca696
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/framework/intraprocedural/cf/CfIntraproceduralDataflowAnalysis.java
@@ -0,0 +1,21 @@
+// 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.cf;
+
+import com.android.tools.r8.cf.code.CfInstruction;
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.AbstractState;
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.AbstractTransferFunction;
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.IntraProceduralDataflowAnalysisBase;
+
+public class CfIntraproceduralDataflowAnalysis<StateType extends AbstractState<StateType>>
+ extends IntraProceduralDataflowAnalysisBase<CfBlock, CfInstruction, StateType> {
+
+ public CfIntraproceduralDataflowAnalysis(
+ StateType bottom,
+ CfControlFlowGraph cfg,
+ AbstractTransferFunction<CfBlock, CfInstruction, StateType> transfer) {
+ super(bottom, cfg, transfer);
+ }
+}
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 c24769a..25e1be0 100644
--- a/src/main/java/com/android/tools/r8/utils/TraversalUtils.java
+++ b/src/main/java/com/android/tools/r8/utils/TraversalUtils.java
@@ -6,6 +6,7 @@
import static com.android.tools.r8.utils.FunctionUtils.ignoreArgument;
+import java.util.function.BiFunction;
import java.util.function.Consumer;
import java.util.function.Function;
@@ -37,4 +38,20 @@
ignoreArgument(() -> TraversalContinuation.breakIf(counter.incrementAndGet() > value)));
return counter.get() > value;
}
+
+ public static <S, BT, CT> TraversalContinuation<BT, CT> traverseIterable(
+ Iterable<S> iterable,
+ BiFunction<? super S, ? super CT, TraversalContinuation<BT, CT>> fn,
+ CT initialValue) {
+ TraversalContinuation<BT, CT> traversalContinuation =
+ TraversalContinuation.doContinue(initialValue);
+ for (S element : iterable) {
+ traversalContinuation =
+ fn.apply(element, traversalContinuation.asContinue().getValueOrDefault(null));
+ if (traversalContinuation.isBreak()) {
+ break;
+ }
+ }
+ return traversalContinuation;
+ }
}
