Build string builder graphs from escape state
Bug: 190489514
Bug: 219455761
Bug: 113859361
Bug: 114002137
Bug: 222437581
Bug: 154899065
Change-Id: Ia823071f8ebc93791a25c8ec594ae5b19d11ff34
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java
new file mode 100644
index 0000000..576c156
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderAppendOptimizer.java
@@ -0,0 +1,426 @@
+// 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.optimize.string;
+
+import static com.android.tools.r8.ir.optimize.string.StringBuilderHelper.canMutate;
+import static com.android.tools.r8.ir.optimize.string.StringBuilderNode.createAppendNode;
+import static com.android.tools.r8.ir.optimize.string.StringBuilderNode.createEscapeNode;
+import static com.android.tools.r8.ir.optimize.string.StringBuilderNode.createImplicitToStringNode;
+import static com.android.tools.r8.ir.optimize.string.StringBuilderNode.createInitNode;
+import static com.android.tools.r8.ir.optimize.string.StringBuilderNode.createInspectionNode;
+import static com.android.tools.r8.ir.optimize.string.StringBuilderNode.createMutateNode;
+import static com.android.tools.r8.ir.optimize.string.StringBuilderNode.createNewInstanceNode;
+import static com.android.tools.r8.ir.optimize.string.StringBuilderNode.createOtherStringBuilderNode;
+import static com.android.tools.r8.ir.optimize.string.StringBuilderNode.createToStringNode;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.DataflowAnalysisResult.SuccessfulDataflowAnalysisResult;
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.IntraproceduralDataflowAnalysis;
+import com.android.tools.r8.ir.analysis.framework.intraprocedural.TransferFunctionResult;
+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.InvokeMethodWithReceiver;
+import com.android.tools.r8.ir.code.Phi;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.optimize.string.StringBuilderNode.AppendNode;
+import com.android.tools.r8.ir.optimize.string.StringBuilderNode.EscapeNode;
+import com.android.tools.r8.ir.optimize.string.StringBuilderNode.ImplicitToStringNode;
+import com.android.tools.r8.ir.optimize.string.StringBuilderNode.InitNode;
+import com.android.tools.r8.ir.optimize.string.StringBuilderNode.InitOrAppend;
+import com.android.tools.r8.ir.optimize.string.StringBuilderNode.LoopNode;
+import com.android.tools.r8.ir.optimize.string.StringBuilderOracle.DefaultStringBuilderOracle;
+import com.android.tools.r8.utils.DepthFirstSearchWorkListBase.StatefulDepthFirstSearchWorkList;
+import com.android.tools.r8.utils.TraversalContinuation;
+import com.android.tools.r8.utils.WorkList;
+import java.util.Collections;
+import java.util.IdentityHashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+import java.util.function.Function;
+
+/**
+ * {@link StringBuilderAppendOptimizer} will try to optimize string builders by joining appends with
+ * constant arguments and materializing toStrings into constant strings to be able to remove entire
+ * StringBuilders (or StringBuffers).
+ *
+ * <p>The algorithm works by producing graphs for all string builders of a method. The graphs follow
+ * the control flow of the method, thus, if a string builder is assigned a value in two blocks from
+ * a certain point, and there is no linear path between the two assignments, they will show up in a
+ * graph as two successor nodes to a common predecessor. StringBuilder graphs are not tracked
+ * through phis, instead a phi and subsequent uses of that phi will also occur as a graph.
+ *
+ * <p>When all graphs are constructed the graphs are optimized by running a munching algorithm on
+ * them.
+ *
+ * <p>Finally, based on all optimizations, the IR is updated to reflect the optimizations.
+ */
+public class StringBuilderAppendOptimizer {
+
+ private final AppView<?> appView;
+ private final StringBuilderOracle oracle;
+ private final IRCode code;
+
+ private StringBuilderAppendOptimizer(AppView<?> appView, IRCode code) {
+ this.appView = appView;
+ this.code = code;
+ oracle = new DefaultStringBuilderOracle(appView.dexItemFactory());
+ }
+
+ public static void run(AppView<?> appView, IRCode code) {
+ new StringBuilderAppendOptimizer(appView, code).run();
+ }
+
+ private void run() {
+ Map<Value, StringBuilderNode> stringBuilderGraphs = computeStringBuilderGraphs();
+ // TODO(b/219455761): Update with actions on the graphs.
+ assert stringBuilderGraphs != null;
+ }
+
+ private static class StringBuilderGraphState {
+
+ private final Map<Value, StringBuilderNode> roots;
+ private final Map<Value, StringBuilderNode> tails;
+ private boolean isPartOfLoop;
+
+ private StringBuilderGraphState(
+ Map<Value, StringBuilderNode> roots, Map<Value, StringBuilderNode> tails) {
+ this.roots = roots;
+ this.tails = tails;
+ }
+ }
+
+ /***
+ * This will compute a collection of graphs from StringBuilders and return a map from value to
+ * the root of the string builder graph.
+ *
+ * The graphs are constructed by doing a DFS traversel and computing all string builder actions
+ * inside a block. The flow here is known to be linear. When backtracking, the linear collection
+ * of nodes (represented by root and tail) are then combined in a way that ensure the control flow
+ * of the method is maintained in the graph.
+ *
+ * To ensure that we correctly compute when a string builder escapes and when it can be mutated
+ * we first compute a {@link StringBuilderEscapeState} by using a flow analysis, enabling us to
+ * answer, for a given instruction, is a string builder value escaping and all escaped values
+ * at the instruction.
+ */
+ private Map<Value, StringBuilderNode> computeStringBuilderGraphs() {
+ StringBuilderEscapeTransferFunction transferFunction =
+ new StringBuilderEscapeTransferFunction(oracle);
+ IntraproceduralDataflowAnalysis<StringBuilderEscapeState> analysis =
+ new IntraproceduralDataflowAnalysis<>(
+ StringBuilderEscapeState.bottom(), code, transferFunction);
+ SuccessfulDataflowAnalysisResult<?, StringBuilderEscapeState> stringBuilderEscapeResult =
+ analysis.run(code.entryBlock()).asSuccessfulAnalysisResult();
+
+ if (stringBuilderEscapeResult == null) {
+ return Collections.emptyMap();
+ }
+
+ TraversalContinuation<Void, StringBuilderGraphState> graphResult =
+ new StatefulDepthFirstSearchWorkList<BasicBlock, StringBuilderGraphState, Void>() {
+
+ @Override
+ @SuppressWarnings("ReturnValueIgnored")
+ protected TraversalContinuation<Void, StringBuilderGraphState> process(
+ DFSNodeWithState<BasicBlock, StringBuilderGraphState> node,
+ Function<BasicBlock, DFSNodeWithState<BasicBlock, StringBuilderGraphState>>
+ childNodeConsumer) {
+ Map<Value, StringBuilderNode> currentRoots = new IdentityHashMap<>();
+ Map<Value, StringBuilderNode> currentTails = new IdentityHashMap<>();
+ BasicBlock block = node.getNode();
+ StringBuilderEscapeState previousState = analysis.computeBlockEntryState(block);
+ TransferFunctionResult<StringBuilderEscapeState> result =
+ transferFunction.applyBlock(block, previousState);
+ if (result.isFailedTransferResult()) {
+ assert false : "Computing the state should never fail";
+ return TraversalContinuation.doBreak();
+ }
+ previousState = result.asAbstractState();
+ for (Phi phi : block.getPhis()) {
+ if (previousState.isLiveStringBuilder(phi)) {
+ visitAllAliasing(
+ phi,
+ previousState,
+ value -> {},
+ alias -> {
+ EscapeNode escapeNode = new EscapeNode();
+ currentRoots.put(alias, escapeNode);
+ currentTails.put(alias, escapeNode);
+ });
+ }
+ }
+ for (Instruction instruction : block.getInstructions()) {
+ result = transferFunction.apply(instruction, previousState);
+ if (result.isFailedTransferResult()) {
+ assert false : "Computing the state should never fail";
+ return TraversalContinuation.doBreak();
+ }
+ previousState = result.asAbstractState();
+ createNodesForInstruction(
+ instruction,
+ previousState,
+ (value, sbNode) -> {
+ StringBuilderNode currentTail = currentTails.get(value);
+ if (currentTail == null) {
+ currentRoots.put(value, sbNode);
+ currentTails.put(value, sbNode);
+ } else if (shouldAddNodeToGraph(currentTail, sbNode)) {
+ currentTail.addSuccessor(sbNode);
+ currentTails.put(value, sbNode);
+ }
+ });
+ }
+ assert currentRoots.keySet().equals(currentTails.keySet());
+ assert previousState.getLiveStringBuilders().containsAll(currentRoots.keySet())
+ : "Seen root that is not a live string builder";
+ node.setState(new StringBuilderGraphState(currentRoots, currentTails));
+ for (BasicBlock successor : block.getSuccessors()) {
+ childNodeConsumer.apply(successor);
+ }
+ return TraversalContinuation.doContinue();
+ }
+
+ private boolean shouldAddNodeToGraph(
+ StringBuilderNode insertedNode, StringBuilderNode newNode) {
+ // No need for multiple mutating nodes or inspecting nodes.
+ if (insertedNode.isMutateNode()) {
+ return !newNode.isMutateNode() && !newNode.isInspectingNode();
+ } else if (insertedNode.isInspectingNode()) {
+ return !newNode.isInspectingNode();
+ }
+ return true;
+ }
+
+ private void createNodesForInstruction(
+ Instruction instruction,
+ StringBuilderEscapeState escapeState,
+ BiConsumer<Value, StringBuilderNode> nodeConsumer) {
+ // Do not build nodes for assume values.
+ if (instruction.isAssume()) {
+ return;
+ }
+ if (oracle.isModeledStringBuilderInstruction(instruction)) {
+ createNodesForStringBuilderInstruction(instruction, escapeState, nodeConsumer);
+ } else {
+ for (Value newEscapedValue : escapeState.getNewlyEscaped()) {
+ visitStringBuilderValues(
+ newEscapedValue,
+ escapeState,
+ nonAlias -> nodeConsumer.accept(nonAlias, createEscapeNode()),
+ alias -> nodeConsumer.accept(alias, createEscapeNode()));
+ }
+ if (canMutate(instruction)) {
+ for (Value escapedStringBuilder : escapeState.getEscaping()) {
+ visitStringBuilderValues(
+ escapedStringBuilder,
+ escapeState,
+ nonAlias -> nodeConsumer.accept(nonAlias, createMutateNode()),
+ alias -> nodeConsumer.accept(alias, createMutateNode()));
+ }
+ }
+ }
+ }
+
+ private void createNodesForStringBuilderInstruction(
+ Instruction instruction,
+ StringBuilderEscapeState escapeState,
+ BiConsumer<Value, StringBuilderNode> nodeConsumer) {
+ if (instruction.isNewInstance()) {
+ Value newInstanceValue = instruction.outValue();
+ assert newInstanceValue != null;
+ nodeConsumer.accept(
+ newInstanceValue, createNewInstanceNode(instruction.asNewInstance()));
+ } else {
+ InvokeMethodWithReceiver invoke = instruction.asInvokeMethodWithReceiver();
+ Value receiver = invoke.getReceiver();
+ if (oracle.isInit(instruction)) {
+ InitNode initNode = createInitNode(instruction.asInvokeDirect());
+ initNode.setConstantArgument(oracle.getConstantArgument(instruction));
+ if (invoke.arguments().size() == 2) {
+ Value arg = invoke.getOperand(1);
+ if (oracle.hasStringBuilderType(arg)) {
+ insertImplicitToStringNode(
+ arg, instruction, initNode, escapeState, nodeConsumer);
+ }
+ }
+ visitStringBuilderValues(
+ receiver,
+ escapeState,
+ actual -> nodeConsumer.accept(actual, initNode),
+ escaped -> nodeConsumer.accept(escaped, createInspectionNode(instruction)));
+ } else if (oracle.isAppend(instruction)) {
+ AppendNode appendNode = createAppendNode(instruction.asInvokeVirtual());
+ appendNode.setConstantArgument(oracle.getConstantArgument(instruction));
+ Value arg = invoke.getOperand(1).getAliasedValue();
+ if (oracle.hasStringBuilderType(arg)) {
+ insertImplicitToStringNode(
+ arg, instruction, appendNode, escapeState, nodeConsumer);
+ }
+ visitStringBuilderValues(
+ receiver,
+ escapeState,
+ actual -> nodeConsumer.accept(actual, appendNode),
+ escaped -> nodeConsumer.accept(escaped, createMutateNode()));
+ } else if (oracle.isToString(instruction)) {
+ visitStringBuilderValues(
+ receiver,
+ escapeState,
+ actual ->
+ nodeConsumer.accept(
+ actual, createToStringNode(instruction.asInvokeVirtual())),
+ escaped -> nodeConsumer.accept(escaped, createInspectionNode(instruction)));
+ } else if (oracle.isInspecting(instruction)) {
+ visitStringBuilderValues(
+ receiver,
+ escapeState,
+ actual -> nodeConsumer.accept(actual, createInspectionNode(instruction)),
+ escaped -> nodeConsumer.accept(escaped, createInspectionNode(instruction)));
+ } else {
+ visitStringBuilderValues(
+ receiver,
+ escapeState,
+ actual ->
+ nodeConsumer.accept(actual, createOtherStringBuilderNode(instruction)),
+ escaped ->
+ nodeConsumer.accept(escaped, createOtherStringBuilderNode(instruction)));
+ }
+ }
+ }
+
+ // For tracking propagating constant string builder values through append or init we
+ // build a link between the two graphs.
+ private void insertImplicitToStringNode(
+ Value value,
+ Instruction instruction,
+ InitOrAppend node,
+ StringBuilderEscapeState escapeState,
+ BiConsumer<Value, StringBuilderNode> nodeConsumer) {
+ assert escapeState.isLiveStringBuilder(value);
+ ImplicitToStringNode implicitToStringNode = createImplicitToStringNode(node);
+ visitStringBuilderValues(
+ value,
+ escapeState,
+ actual -> nodeConsumer.accept(actual, implicitToStringNode),
+ escaped -> nodeConsumer.accept(escaped, createInspectionNode(instruction)));
+ node.setImplicitToStringNode(implicitToStringNode);
+ }
+
+ private void visitStringBuilderValues(
+ Value value,
+ StringBuilderEscapeState state,
+ Consumer<Value> actualConsumer,
+ Consumer<Value> aliasAndEscapedConsumer) {
+ assert state.isLiveStringBuilder(value);
+ boolean seenEscaped =
+ visitAllAliasing(value, state, actualConsumer, aliasAndEscapedConsumer);
+ seenEscaped |= visitAllAliases(value, state, aliasAndEscapedConsumer);
+ if (seenEscaped) {
+ for (Value escapingValue : state.getEscaping()) {
+ aliasAndEscapedConsumer.accept(escapingValue);
+ }
+ }
+ }
+
+ private boolean visitAllAliasing(
+ Value value,
+ StringBuilderEscapeState state,
+ Consumer<Value> nonAliasConsumer,
+ Consumer<Value> aliasAndEscapedConsumer) {
+ WorkList<Value> valueWorkList = WorkList.newIdentityWorkList(value);
+ boolean seenUnknownAlias = false;
+ boolean seenEscaped = false;
+ while (valueWorkList.hasNext()) {
+ Value next = valueWorkList.next();
+ seenEscaped |= state.isEscaped(next);
+ Set<Value> aliasing =
+ state.getAliasesToDefinitions().getOrDefault(next, Collections.emptySet());
+ valueWorkList.addIfNotSeen(aliasing);
+ // Check if we have a direct alias such as Assume, CheckCast or StringBuilder.append.
+ if (aliasing.size() != 1 || next.isPhi()) {
+ if (!seenUnknownAlias) {
+ nonAliasConsumer.accept(next);
+ seenUnknownAlias = true;
+ } else {
+ aliasAndEscapedConsumer.accept(next);
+ }
+ }
+ }
+ return seenEscaped;
+ }
+
+ private boolean visitAllAliases(
+ Value value, StringBuilderEscapeState state, Consumer<Value> aliasConsumer) {
+ Map<Value, Set<Value>> escapedDefinitionsToKnown = state.getDefinitionsToAliases();
+ WorkList<Value> valueWorkList =
+ WorkList.newIdentityWorkList(
+ escapedDefinitionsToKnown.getOrDefault(value, Collections.emptySet()));
+ boolean seenEscaped = false;
+ while (valueWorkList.hasNext()) {
+ Value next = valueWorkList.next();
+ seenEscaped |= state.isEscaped(next);
+ if (next.isPhi()) {
+ aliasConsumer.accept(next);
+ }
+ valueWorkList.addIfNotSeen(
+ escapedDefinitionsToKnown.getOrDefault(next, Collections.emptySet()));
+ }
+ return seenEscaped;
+ }
+
+ @Override
+ protected TraversalContinuation<Void, StringBuilderGraphState> joiner(
+ DFSNodeWithState<BasicBlock, StringBuilderGraphState> node,
+ List<DFSNodeWithState<BasicBlock, StringBuilderGraphState>> childStates) {
+ StringBuilderGraphState state = node.getState();
+ for (DFSNodeWithState<BasicBlock, StringBuilderGraphState> childState : childStates) {
+ StringBuilderGraphState childGraphState = childState.getState();
+ childGraphState.roots.forEach(
+ (value, sbNode) -> {
+ StringBuilderNode currentRoot = state.roots.get(value);
+ StringBuilderNode currentTail = state.tails.get(value);
+ if (currentRoot == null) {
+ assert currentTail == null;
+ if (childStates.size() == 1) {
+ state.roots.put(value, sbNode);
+ state.tails.put(value, sbNode);
+ return;
+ }
+ // We are adding a value coming only from a child state and not defined here.
+ // To ensure proper ordering we add a sentinel node. If it turns out there is
+ // only a single reference, we rely on munching to remove it.
+ currentRoot = StringBuilderNode.createSplitReferenceNode();
+ currentTail = currentRoot;
+ state.roots.put(value, currentRoot);
+ state.tails.put(value, currentTail);
+ }
+ assert currentTail != null;
+ // Link next node from successor
+ currentTail.addSuccessor(sbNode);
+ sbNode.addPredecessor(currentTail);
+ });
+ if (childState.seenAndNotProcessed()) {
+ childGraphState.isPartOfLoop = true;
+ }
+ }
+ if (state.isPartOfLoop) {
+ for (Value value : state.roots.keySet()) {
+ LoopNode loopNode = StringBuilderNode.createLoopNode();
+ loopNode.addSuccessor(state.roots.get(value));
+ state.roots.put(value, loopNode);
+ }
+ }
+ return TraversalContinuation.doContinue(state);
+ }
+ }.run(code.entryBlock());
+
+ return graphResult.shouldBreak()
+ ? Collections.emptyMap()
+ : graphResult.asContinue().getValue().roots;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderEscapeTransferFunction.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderEscapeTransferFunction.java
index 898442f..ff4a62a 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderEscapeTransferFunction.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderEscapeTransferFunction.java
@@ -53,7 +53,7 @@
public TransferFunctionResult<StringBuilderEscapeState> apply(
Instruction instruction, StringBuilderEscapeState state) {
StringBuilderEscapeState.Builder builder = state.builder();
- boolean isStringBuilderInstruction = oracle.isStringBuilderInstruction(instruction);
+ boolean isStringBuilderInstruction = oracle.isModeledStringBuilderInstruction(instruction);
if (!isStringBuilderInstruction && isEscapingInstructionForInValues(instruction)) {
for (Value inValue : instruction.inValues()) {
if (isLiveStringBuilder(builder, inValue)) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderHelper.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderHelper.java
index a56b3e7..a795308 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderHelper.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderHelper.java
@@ -30,6 +30,12 @@
|| instruction.isCheckCast();
}
+ static boolean canMutate(Instruction instruction) {
+ return instruction.isInvoke()
+ || instruction.isFieldInstruction()
+ || instruction.isNewInstance();
+ }
+
static boolean isInstructionThatIntroducesDefiniteAlias(
Instruction instruction, StringBuilderOracle oracle) {
return instruction.isAssume() || instruction.isCheckCast() || oracle.isAppend(instruction);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderNode.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderNode.java
new file mode 100644
index 0000000..acd5c47
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderNode.java
@@ -0,0 +1,606 @@
+// 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.optimize.string;
+
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InvokeDirect;
+import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.NewInstance;
+import com.google.common.collect.Sets;
+import java.util.Set;
+
+/**
+ * StringBuilderNode defines a single point where a string builder operation occur or some abstract
+ * state changes. The node can be assembled into a graph by defining predecessors and successors.
+ */
+class StringBuilderNode {
+
+ interface StringBuilderInstruction {
+
+ Instruction getInstruction();
+
+ boolean isStringBuilderInstructionNode();
+
+ StringBuilderInstruction asStringBuilderInstructionNode();
+ }
+
+ interface InitOrAppend extends StringBuilderInstruction {
+
+ boolean hasConstantArgument();
+
+ String getConstantArgument();
+
+ void setConstantArgument(String constantArgument);
+
+ void setImplicitToStringNode(ImplicitToStringNode node);
+
+ ImplicitToStringNode getImplicitToStringNode();
+ }
+
+ private final Set<StringBuilderNode> successors = Sets.newIdentityHashSet();
+ private final Set<StringBuilderNode> predecessors = Sets.newIdentityHashSet();
+
+ // Field uses to ensure that munching will not operate on the same value multiple times. If all
+ // peep holes would look in the same direction, this field could be removed.
+ private boolean isDead = false;
+
+ private StringBuilderNode() {}
+
+ boolean isEscapeNode() {
+ return false;
+ }
+
+ boolean isMutateNode() {
+ return false;
+ }
+
+ boolean isSplitReferenceNode() {
+ return false;
+ }
+
+ boolean isLoopNode() {
+ return false;
+ }
+
+ boolean isNewInstanceNode() {
+ return false;
+ }
+
+ boolean isInitNode() {
+ return false;
+ }
+
+ boolean isAppendNode() {
+ return false;
+ }
+
+ boolean isInitOrAppend() {
+ return false;
+ }
+
+ boolean isToStringNode() {
+ return false;
+ }
+
+ boolean isInspectingNode() {
+ return false;
+ }
+
+ boolean isOtherStringBuilderNode() {
+ return false;
+ }
+
+ boolean isImplicitToStringNode() {
+ return false;
+ }
+
+ boolean isStringBuilderInstructionNode() {
+ return false;
+ }
+
+ NewInstanceNode asNewInstanceNode() {
+ return null;
+ }
+
+ InitNode asInitNode() {
+ return null;
+ }
+
+ AppendNode asAppendNode() {
+ return null;
+ }
+
+ InitOrAppend asInitOrAppend() {
+ return null;
+ }
+
+ ToStringNode asToStringNode() {
+ return null;
+ }
+
+ InspectingNode asInspectingNode() {
+ return null;
+ }
+
+ OtherStringBuilderNode asOtherStringBuilderNode() {
+ return null;
+ }
+
+ ImplicitToStringNode asImplicitToStringNode() {
+ return null;
+ }
+
+ StringBuilderInstruction asStringBuilderInstructionNode() {
+ return null;
+ }
+
+ boolean isDead() {
+ return isDead;
+ }
+
+ boolean hasSingleSuccessor() {
+ return successors.size() == 1;
+ }
+
+ StringBuilderNode getSingleSuccessor() {
+ assert hasSingleSuccessor();
+ return successors.iterator().next();
+ }
+
+ void addSuccessor(StringBuilderNode successor) {
+ successors.add(successor);
+ successor.predecessors.add(this);
+ }
+
+ Set<StringBuilderNode> getSuccessors() {
+ return successors;
+ }
+
+ boolean hasSinglePredecessor() {
+ return predecessors.size() == 1;
+ }
+
+ StringBuilderNode getSinglePredecessor() {
+ assert hasSinglePredecessor();
+ return predecessors.iterator().next();
+ }
+
+ Set<StringBuilderNode> getPredecessors() {
+ return predecessors;
+ }
+
+ void addPredecessor(StringBuilderNode predecessor) {
+ predecessors.add(predecessor);
+ }
+
+ void removeNode() {
+ for (StringBuilderNode successor : this.getSuccessors()) {
+ successor.getPredecessors().remove(this);
+ successor.getPredecessors().addAll(this.getPredecessors());
+ }
+ for (StringBuilderNode predecessor : this.getPredecessors()) {
+ predecessor.getSuccessors().remove(this);
+ predecessor.getSuccessors().addAll(this.getSuccessors());
+ }
+ isDead = true;
+ }
+
+ /** EscapeNode is used to explicitly define an escape point for a StringBuilder. */
+ static class EscapeNode extends StringBuilderNode {
+
+ @Override
+ boolean isEscapeNode() {
+ return true;
+ }
+ }
+
+ /**
+ * MutateNode defines if a string builder could be possibly mutated or inspected. An example could
+ * be:
+ *
+ * <pre>
+ * sb = new StringBuilder();
+ * escape(sb);
+ * sb.append("foo");
+ * canMutate(); <-- This is represented by a MutateNode.
+ * sb.append("bar");
+ * </pre>
+ */
+ static class MutateNode extends StringBuilderNode {
+
+ @Override
+ boolean isMutateNode() {
+ return true;
+ }
+ }
+
+ /**
+ * SplitReferenceNodes are synthetic nodes inserted when a string builder is used in multiple
+ * successor blocks.
+ */
+ static class SplitReferenceNode extends StringBuilderNode {
+
+ @Override
+ boolean isSplitReferenceNode() {
+ return true;
+ }
+ }
+
+ /**
+ * LoopNode is a node indicating that all successor paths are part of a loop. LoopNode's are only
+ * inserted once ensuring there are no loops in a StringBuilderGraph.
+ */
+ static class LoopNode extends StringBuilderNode {
+
+ @Override
+ boolean isLoopNode() {
+ return true;
+ }
+ }
+
+ /** A NewInstanceNode is a new instance of either StringBuilder or StringBuffer. */
+ static class NewInstanceNode extends StringBuilderNode implements StringBuilderInstruction {
+
+ private final NewInstance instruction;
+
+ private NewInstanceNode(NewInstance instruction) {
+ this.instruction = instruction;
+ }
+
+ @Override
+ boolean isNewInstanceNode() {
+ return true;
+ }
+
+ @Override
+ NewInstanceNode asNewInstanceNode() {
+ return this;
+ }
+
+ @Override
+ public Instruction getInstruction() {
+ return instruction;
+ }
+
+ @Override
+ public boolean isStringBuilderInstructionNode() {
+ return true;
+ }
+
+ @Override
+ public StringBuilderInstruction asStringBuilderInstructionNode() {
+ return this;
+ }
+ }
+
+ /** An initNode is where a StringBuilder/StringBuffer is initialized. */
+ static class InitNode extends StringBuilderNode
+ implements InitOrAppend, StringBuilderInstruction {
+
+ private final InvokeDirect instruction;
+ private ImplicitToStringNode implicitToStringNode;
+ private String constantArgument;
+
+ private InitNode(InvokeDirect instruction) {
+ this.instruction = instruction;
+ }
+
+ @Override
+ boolean isInitNode() {
+ return true;
+ }
+
+ @Override
+ boolean isInitOrAppend() {
+ return true;
+ }
+
+ @Override
+ InitNode asInitNode() {
+ return this;
+ }
+
+ @Override
+ InitOrAppend asInitOrAppend() {
+ return this;
+ }
+
+ @Override
+ public Instruction getInstruction() {
+ return instruction;
+ }
+
+ @Override
+ public boolean isStringBuilderInstructionNode() {
+ return true;
+ }
+
+ @Override
+ public StringBuilderInstruction asStringBuilderInstructionNode() {
+ return this;
+ }
+
+ @Override
+ public void setConstantArgument(String constantArgument) {
+ this.constantArgument = constantArgument;
+ }
+
+ @Override
+ public void setImplicitToStringNode(ImplicitToStringNode node) {
+ implicitToStringNode = node;
+ }
+
+ @Override
+ public ImplicitToStringNode getImplicitToStringNode() {
+ return implicitToStringNode;
+ }
+
+ @Override
+ public String getConstantArgument() {
+ return constantArgument;
+ }
+
+ @Override
+ public boolean hasConstantArgument() {
+ return constantArgument != null;
+ }
+ }
+
+ /** AppendNodes are StringBuilder.append or StringBuffer.append. */
+ static class AppendNode extends StringBuilderNode
+ implements InitOrAppend, StringBuilderInstruction {
+
+ private final InvokeVirtual instruction;
+ private ImplicitToStringNode implicitToStringNode;
+ private String constantArgument;
+
+ private AppendNode(InvokeVirtual instruction) {
+ this.instruction = instruction;
+ }
+
+ @Override
+ boolean isAppendNode() {
+ return true;
+ }
+
+ @Override
+ boolean isInitOrAppend() {
+ return true;
+ }
+
+ @Override
+ AppendNode asAppendNode() {
+ return this;
+ }
+
+ @Override
+ InitOrAppend asInitOrAppend() {
+ return this;
+ }
+
+ @Override
+ public Instruction getInstruction() {
+ return instruction;
+ }
+
+ @Override
+ public boolean isStringBuilderInstructionNode() {
+ return true;
+ }
+
+ @Override
+ public StringBuilderInstruction asStringBuilderInstructionNode() {
+ return this;
+ }
+
+ @Override
+ public void setConstantArgument(String constantArgument) {
+ this.constantArgument = constantArgument;
+ }
+
+ @Override
+ public void setImplicitToStringNode(ImplicitToStringNode node) {
+ implicitToStringNode = node;
+ }
+
+ @Override
+ public ImplicitToStringNode getImplicitToStringNode() {
+ return implicitToStringNode;
+ }
+
+ @Override
+ public String getConstantArgument() {
+ return constantArgument;
+ }
+
+ @Override
+ public boolean hasConstantArgument() {
+ return constantArgument != null;
+ }
+ }
+
+ /**
+ * ToStringNodes marked a point where a StringBuilder/StringBuffer is materialized to a string.
+ */
+ static class ToStringNode extends StringBuilderNode implements StringBuilderInstruction {
+
+ private final InvokeVirtual instruction;
+
+ private ToStringNode(InvokeVirtual instruction) {
+ this.instruction = instruction;
+ }
+
+ @Override
+ boolean isToStringNode() {
+ return true;
+ }
+
+ @Override
+ ToStringNode asToStringNode() {
+ return this;
+ }
+
+ @Override
+ public Instruction getInstruction() {
+ return instruction;
+ }
+
+ @Override
+ public boolean isStringBuilderInstructionNode() {
+ return true;
+ }
+
+ @Override
+ public StringBuilderInstruction asStringBuilderInstructionNode() {
+ return this;
+ }
+ }
+
+ /**
+ * InspectingNode is inserted if there is inspection of the capacity of a
+ * StringBuilder/StringBuffer. Special care needs to be taken since we try to ensure that capacity
+ * will be the same after optimizations.
+ */
+ static class InspectingNode extends StringBuilderNode implements StringBuilderInstruction {
+
+ private final Instruction instruction;
+
+ private InspectingNode(Instruction instruction) {
+ this.instruction = instruction;
+ }
+
+ @Override
+ boolean isInspectingNode() {
+ return true;
+ }
+
+ @Override
+ InspectingNode asInspectingNode() {
+ return this;
+ }
+
+ @Override
+ public Instruction getInstruction() {
+ return instruction;
+ }
+
+ @Override
+ public boolean isStringBuilderInstructionNode() {
+ return true;
+ }
+
+ @Override
+ public StringBuilderInstruction asStringBuilderInstructionNode() {
+ return this;
+ }
+ }
+
+ /** OtherStringBuilderNode marks operations on string builders we do not model. */
+ static class OtherStringBuilderNode extends StringBuilderNode
+ implements StringBuilderInstruction {
+
+ private final Instruction instruction;
+
+ private OtherStringBuilderNode(Instruction instruction) {
+ this.instruction = instruction;
+ }
+
+ @Override
+ boolean isOtherStringBuilderNode() {
+ return true;
+ }
+
+ @Override
+ OtherStringBuilderNode asOtherStringBuilderNode() {
+ return this;
+ }
+
+ @Override
+ public Instruction getInstruction() {
+ return instruction;
+ }
+
+ @Override
+ public boolean isStringBuilderInstructionNode() {
+ return true;
+ }
+
+ @Override
+ public StringBuilderInstruction asStringBuilderInstructionNode() {
+ return this;
+ }
+ }
+
+ /**
+ * ImplicitToStringNode are placed a StringBuilder/StringBuffer is appended to another
+ * StringBuilder/StringBuffer.
+ */
+ static class ImplicitToStringNode extends StringBuilderNode {
+
+ private final InitOrAppend initOrAppend;
+
+ ImplicitToStringNode(InitOrAppend initOrAppend) {
+ this.initOrAppend = initOrAppend;
+ }
+
+ public InitOrAppend getInitOrAppend() {
+ return initOrAppend;
+ }
+
+ @Override
+ boolean isImplicitToStringNode() {
+ return true;
+ }
+
+ @Override
+ ImplicitToStringNode asImplicitToStringNode() {
+ return this;
+ }
+ }
+
+ static EscapeNode createEscapeNode() {
+ return new EscapeNode();
+ }
+
+ static MutateNode createMutateNode() {
+ return new MutateNode();
+ }
+
+ static SplitReferenceNode createSplitReferenceNode() {
+ return new SplitReferenceNode();
+ }
+
+ static LoopNode createLoopNode() {
+ return new LoopNode();
+ }
+
+ static NewInstanceNode createNewInstanceNode(NewInstance instruction) {
+ return new NewInstanceNode(instruction);
+ }
+
+ static InitNode createInitNode(InvokeDirect instruction) {
+ return new InitNode(instruction);
+ }
+
+ static AppendNode createAppendNode(InvokeVirtual instruction) {
+ return new AppendNode(instruction);
+ }
+
+ static ToStringNode createToStringNode(InvokeVirtual instruction) {
+ return new ToStringNode(instruction);
+ }
+
+ static InspectingNode createInspectionNode(Instruction instruction) {
+ return new InspectingNode(instruction);
+ }
+
+ static OtherStringBuilderNode createOtherStringBuilderNode(Instruction instruction) {
+ return new OtherStringBuilderNode(instruction);
+ }
+
+ static ImplicitToStringNode createImplicitToStringNode(InitOrAppend otherNode) {
+ return new ImplicitToStringNode(otherNode);
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOracle.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOracle.java
index 26eb12b..b6c0b4f 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOracle.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOracle.java
@@ -23,7 +23,7 @@
*/
interface StringBuilderOracle {
- boolean isStringBuilderInstruction(Instruction instruction);
+ boolean isModeledStringBuilderInstruction(Instruction instruction);
boolean hasStringBuilderType(Value value);
@@ -50,7 +50,7 @@
}
@Override
- public boolean isStringBuilderInstruction(Instruction instruction) {
+ public boolean isModeledStringBuilderInstruction(Instruction instruction) {
if (instruction.isNewInstance()) {
return isStringBuilderType(instruction.asNewInstance().getType());
} else if (instruction.isInvokeMethod()) {
@@ -157,7 +157,7 @@
@Override
public boolean canObserveStringBuilderCall(Instruction instruction) {
- assert isStringBuilderInstruction(instruction);
+ assert isModeledStringBuilderInstruction(instruction);
if (!instruction.isInvokeMethod()) {
assert false : "Expecting a call to string builder";
return true;
