| // 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 static com.android.tools.r8.utils.FunctionUtils.ignoreArgument; |
| |
| import com.android.tools.r8.graph.AppInfo; |
| 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.IntraProceduralDataflowAnalysisOptions; |
| 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.analysis.type.TypeElement; |
| 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.InstructionListIterator; |
| import com.android.tools.r8.ir.code.InvokeMethodWithReceiver; |
| import com.android.tools.r8.ir.code.InvokeStatic; |
| import com.android.tools.r8.ir.code.Phi; |
| import com.android.tools.r8.ir.code.Value; |
| import com.android.tools.r8.ir.conversion.MethodProcessor; |
| import com.android.tools.r8.ir.conversion.passes.CodeRewriterPass; |
| import com.android.tools.r8.ir.conversion.passes.result.CodeRewriterResult; |
| import com.android.tools.r8.ir.optimize.AffectedValues; |
| import com.android.tools.r8.ir.optimize.string.StringBuilderNode.AppendNode; |
| 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.InitOrAppendNode; |
| import com.android.tools.r8.ir.optimize.string.StringBuilderNode.LoopNode; |
| import com.android.tools.r8.ir.optimize.string.StringBuilderNode.NewInstanceNode; |
| import com.android.tools.r8.ir.optimize.string.StringBuilderNode.SplitReferenceNode; |
| import com.android.tools.r8.ir.optimize.string.StringBuilderNodeMuncher.MunchingState; |
| import com.android.tools.r8.ir.optimize.string.StringBuilderOracle.DefaultStringBuilderOracle; |
| import com.android.tools.r8.utils.DepthFirstSearchWorkListBase.DepthFirstSearchWorkList; |
| import com.android.tools.r8.utils.DepthFirstSearchWorkListBase.StatefulDepthFirstSearchWorkList; |
| import com.android.tools.r8.utils.TraversalContinuation; |
| import com.android.tools.r8.utils.WorkList; |
| import com.google.common.collect.Sets; |
| import it.unimi.dsi.fastutil.objects.Reference2IntLinkedOpenHashMap; |
| import it.unimi.dsi.fastutil.objects.Reference2IntMap; |
| import it.unimi.dsi.fastutil.objects.Reference2IntMap.Entry; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.IdentityHashMap; |
| import java.util.LinkedHashMap; |
| import java.util.LinkedHashSet; |
| 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 extends CodeRewriterPass<AppInfo> { |
| |
| private final StringBuilderOracle oracle; |
| private static final int NUMBER_OF_MUNCHING_PASSES = 3; |
| |
| public StringBuilderAppendOptimizer(AppView<?> appView) { |
| super(appView); |
| oracle = new DefaultStringBuilderOracle(appView.dexItemFactory()); |
| } |
| |
| @Override |
| protected String getRewriterId() { |
| return "StringBuilderAppendOptimizer"; |
| } |
| |
| @Override |
| protected boolean shouldRewriteCode(IRCode code, MethodProcessor methodProcessor) { |
| return options.enableStringConcatenationOptimization |
| && !isDebugMode(code.context()) |
| && (code.metadata().mayHaveNewInstance() |
| || code.metadata().mayHaveInvokeMethodWithReceiver()); |
| } |
| |
| @Override |
| protected CodeRewriterResult rewriteCode(IRCode code) { |
| Map<Value, StringBuilderNode> stringBuilderGraphs = computeStringBuilderGraphs(code); |
| Map<Instruction, StringBuilderAction> actions = optimizeOnGraphs(code, stringBuilderGraphs); |
| if (actions.isEmpty()) { |
| return CodeRewriterResult.NO_CHANGE; |
| } |
| AffectedValues affectedValues = new AffectedValues(); |
| InstructionListIterator it = code.instructionListIterator(); |
| while (it.hasNext()) { |
| Instruction instruction = it.next(); |
| StringBuilderAction stringBuilderAction = actions.get(instruction); |
| if (stringBuilderAction != null) { |
| stringBuilderAction.perform(appView, code, it, instruction, affectedValues, oracle); |
| } |
| } |
| affectedValues.narrowingWithAssumeRemoval(appView, code); |
| code.removeAllDeadAndTrivialPhis(); |
| code.removeRedundantBlocks(); |
| return CodeRewriterResult.HAS_CHANGED; |
| } |
| |
| 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(IRCode code) { |
| StringBuilderEscapeTransferFunction transferFunction = |
| new StringBuilderEscapeTransferFunction(oracle); |
| IntraproceduralDataflowAnalysis<StringBuilderEscapeState> analysis = |
| new IntraproceduralDataflowAnalysis<>( |
| appView, |
| StringBuilderEscapeState.bottom(), |
| code, |
| transferFunction, |
| IntraProceduralDataflowAnalysisOptions.getNoCollapseInstance()); |
| 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 LinkedHashMap<>(); |
| 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)) { |
| boolean seenEscaped = |
| visitAllAliasing( |
| phi, |
| previousState, |
| value -> {}, |
| alias -> |
| addNodeToRootAndTail( |
| currentRoots, currentTails, alias, createEscapeNode())); |
| if (seenEscaped) { |
| addNodeToRootAndTail(currentRoots, currentTails, phi, createEscapeNode()); |
| } |
| } |
| } |
| 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) -> |
| addNodeToRootAndTail(currentRoots, currentTails, 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 void addNodeToRootAndTail( |
| Map<Value, StringBuilderNode> currentRoots, |
| Map<Value, StringBuilderNode> currentTails, |
| Value value, |
| StringBuilderNode node) { |
| StringBuilderNode currentTail = currentTails.get(value); |
| if (currentTail == null) { |
| currentRoots.put(value, node); |
| currentTails.put(value, node); |
| } else if (shouldAddNodeToGraph(currentTail, node)) { |
| currentTail.addSuccessor(node); |
| currentTails.put(value, node); |
| } |
| } |
| |
| 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(); |
| } else if (insertedNode.isEscapeNode()) { |
| return !newNode.isEscapeNode(); |
| } |
| 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, escapeState::isLiveStringBuilder)) { |
| 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())); |
| } |
| } |
| } |
| } |
| |
| @SuppressWarnings("ReferenceEquality") |
| 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 if (instruction.isInvokeMethodWithReceiver()) { |
| InvokeMethodWithReceiver invoke = instruction.asInvokeMethodWithReceiver(); |
| Value receiver = invoke.getReceiver(); |
| if (oracle.isInit(instruction)) { |
| InitNode initNode = createInitNode(instruction.asInvokeDirect()); |
| String constantArgument = oracle.getConstantArgument(instruction); |
| initNode.setConstantArgument(constantArgument); |
| if (constantArgument == null |
| && oracle.isStringConstructor(instruction) |
| && invoke.getFirstNonReceiverArgument().isNeverNull()) { |
| initNode.setNonConstantArgument(invoke.getFirstNonReceiverArgument()); |
| } |
| 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()); |
| String constantArgument = oracle.getConstantArgument(instruction); |
| appendNode.setConstantArgument(constantArgument); |
| Value arg = invoke.getFirstNonReceiverArgument(); |
| if (constantArgument == null |
| && oracle.isAppendString(instruction) |
| && arg.isNeverNull()) { |
| appendNode.setNonConstantArgument(arg); |
| } |
| if (oracle.hasStringBuilderType(arg.getAliasedValue())) { |
| insertImplicitToStringNode( |
| arg, instruction, appendNode, escapeState, nodeConsumer); |
| } |
| visitStringBuilderValues( |
| receiver, |
| escapeState, |
| actual -> nodeConsumer.accept(actual, appendNode), |
| escaped -> nodeConsumer.accept(escaped, createMutateNode())); |
| } else if (oracle.isToString(instruction, receiver)) { |
| 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))); |
| } |
| } else { |
| assert instruction.isInvokeStatic(); |
| InvokeStatic invoke = instruction.asInvokeStatic(); |
| assert invoke.getInvokedMethod() |
| == appView.dexItemFactory().objectsMethods.toStringWithObject; |
| visitStringBuilderValues( |
| invoke.getFirstOperand(), |
| escapeState, |
| actual -> |
| nodeConsumer.accept(actual, createToStringNode(instruction.asInvokeMethod())), |
| escaped -> nodeConsumer.accept(escaped, createInspectionNode(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, |
| InitOrAppendNode 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(); |
| Reference2IntMap<Value> rootsInChildStateCounts = |
| new Reference2IntLinkedOpenHashMap<>(); |
| for (DFSNodeWithState<BasicBlock, StringBuilderGraphState> childState : childStates) { |
| StringBuilderGraphState childGraphState = childState.getState(); |
| childGraphState.roots.forEach( |
| (value, sbNode) -> { |
| rootsInChildStateCounts.put(value, rootsInChildStateCounts.getInt(value) + 1); |
| 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; |
| } |
| } |
| // To ensure that we account for control flow correctly, we insert split reference nodes |
| // for all roots we've seen in only a subset of child states. |
| for (Entry<Value> valueEntry : rootsInChildStateCounts.reference2IntEntrySet()) { |
| assert valueEntry.getIntValue() <= childStates.size(); |
| if (valueEntry.getIntValue() < childStates.size()) { |
| SplitReferenceNode splitNode = StringBuilderNode.createSplitReferenceNode(); |
| StringBuilderNode tail = state.tails.get(valueEntry.getKey()); |
| assert tail != null; |
| splitNode.addPredecessor(tail); |
| tail.addSuccessor(splitNode); |
| } |
| } |
| if (state.isPartOfLoop) { |
| state.roots.replaceAll( |
| (value, currentRoot) -> { |
| LoopNode loopNode = StringBuilderNode.createLoopNode(); |
| loopNode.addSuccessor(currentRoot); |
| return loopNode; |
| }); |
| } |
| return TraversalContinuation.doContinue(state); |
| } |
| }.run(code.entryBlock()); |
| |
| return graphResult.shouldBreak() |
| ? Collections.emptyMap() |
| : graphResult.asContinue().getValue().roots; |
| } |
| |
| /** |
| * optimizeOnGraphs will compute some state that will make munching easier. When computing the |
| * state the search will also do a topological sort over string builder references such that |
| * string builders without a direct dependency on another string builder will be computed first. |
| * |
| * <p>In general, this would not really matter since we munch over all graphs, but we are limiting |
| * the munching and care about performance. |
| */ |
| private Map<Instruction, StringBuilderAction> optimizeOnGraphs( |
| IRCode code, Map<Value, StringBuilderNode> stringBuilderGraphs) { |
| Map<Instruction, StringBuilderAction> actions = new IdentityHashMap<>(); |
| // Build state to allow munching over the string builder graphs. |
| Map<StringBuilderNode, NewInstanceNode> newInstances = new IdentityHashMap<>(); |
| Set<StringBuilderNode> inspectingCapacity = Sets.newIdentityHashSet(); |
| Set<StringBuilderNode> looping = Sets.newIdentityHashSet(); |
| Map<StringBuilderNode, Set<StringBuilderNode>> materializing = new IdentityHashMap<>(); |
| Set<StringBuilderNode> escaping = Sets.newIdentityHashSet(); |
| |
| Map<StringBuilderNode, StringBuilderNode> nodeToRoots = new IdentityHashMap<>(); |
| Map<StringBuilderNode, Set<StringBuilderNode>> stringBuilderDependencies = |
| new IdentityHashMap<>(); |
| |
| stringBuilderGraphs.forEach( |
| (value, root) -> { |
| WorkList<StringBuilderNode> workList = WorkList.newIdentityWorkList(root); |
| Set<StringBuilderNode> materializingInstructions = Sets.newIdentityHashSet(); |
| materializing.put(root, materializingInstructions); |
| while (workList.hasNext()) { |
| StringBuilderNode next = workList.next(); |
| nodeToRoots.put(next, root); |
| if (next.isNewInstanceNode()) { |
| StringBuilderNode existing = newInstances.put(root, next.asNewInstanceNode()); |
| assert existing == null; |
| } |
| if (next.isInitOrAppend()) { |
| ImplicitToStringNode dependency = next.asInitOrAppend().getImplicitToStringNode(); |
| if (dependency != null) { |
| stringBuilderDependencies |
| .computeIfAbsent(root, ignoreArgument(Sets::newIdentityHashSet)) |
| .add(dependency); |
| } |
| } |
| if (next.isLoopNode()) { |
| looping.add(root); |
| } |
| if (next.isEscapeNode()) { |
| inspectingCapacity.add(root); |
| escaping.add(root); |
| } |
| if (next.isToStringNode() || next.isImplicitToStringNode()) { |
| materializingInstructions.add(next); |
| } |
| if (next.isInspectingNode()) { |
| inspectingCapacity.add(root); |
| } |
| next.getSuccessors().forEach(workList::addFirstIfNotSeen); |
| } |
| }); |
| |
| MunchingState munchingState = |
| new MunchingState( |
| actions, |
| escaping, |
| inspectingCapacity, |
| looping, |
| materializing, |
| newInstances, |
| oracle, |
| () -> code.createValue(TypeElement.stringClassType(appView))); |
| |
| boolean keepMunching = true; |
| for (int i = 0; i < NUMBER_OF_MUNCHING_PASSES && keepMunching; i++) { |
| keepMunching = false; |
| for (StringBuilderNode root : |
| computeProcessingOrder(stringBuilderGraphs, stringBuilderDependencies, nodeToRoots)) { |
| WorkList<StringBuilderNode> workList = WorkList.newIdentityWorkList(root); |
| while (workList.hasNext()) { |
| StringBuilderNode next = workList.next(); |
| keepMunching |= StringBuilderNodeMuncher.optimize(root, next, munchingState); |
| next.getSuccessors().forEach(workList::addFirstIfNotSeen); |
| } |
| } |
| } |
| return actions; |
| } |
| |
| private Collection<StringBuilderNode> computeProcessingOrder( |
| Map<Value, StringBuilderNode> stringBuilderGraphs, |
| Map<StringBuilderNode, Set<StringBuilderNode>> stringBuilderDependencies, |
| Map<StringBuilderNode, StringBuilderNode> nodeToRoots) { |
| // Make a topological sort to ensure we visit all nodes in the best order for optimizing nested |
| // string builders. |
| Set<StringBuilderNode> processingOrder = new LinkedHashSet<>(); |
| new DepthFirstSearchWorkList<StringBuilderNode, Void, Void>() { |
| |
| @Override |
| @SuppressWarnings("ReturnValueIgnored") |
| protected TraversalContinuation<Void, Void> process( |
| DFSNode<StringBuilderNode> node, |
| Function<StringBuilderNode, DFSNode<StringBuilderNode>> childNodeConsumer) { |
| StringBuilderNode root = node.getNode(); |
| Set<StringBuilderNode> stringBuilderNodes = stringBuilderDependencies.get(root); |
| if (stringBuilderNodes != null) { |
| for (StringBuilderNode dependency : stringBuilderNodes) { |
| childNodeConsumer.apply(nodeToRoots.get(dependency)); |
| } |
| } |
| return TraversalContinuation.doContinue(); |
| } |
| |
| @Override |
| protected List<Void> getFinalStateForRoots(Collection<? extends StringBuilderNode> roots) { |
| return null; |
| } |
| |
| @Override |
| public TraversalContinuation<Void, Void> joiner(DFSNode<StringBuilderNode> node) { |
| StringBuilderNode node1 = node.getNode(); |
| processingOrder.add(node1); |
| return TraversalContinuation.doContinue(); |
| } |
| }.run(stringBuilderGraphs.values()); |
| return processingOrder; |
| } |
| } |
