StringBuilder optimization, part 1.
This CL is collecting locally built builders and filtering out
non-trivial builder patterns that are out of scope.
Bug: 114002137, 113859361, 129200243
Change-Id: I5b8ba4251b892c9e5f1b190321d51439a086c009
diff --git a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
index c2633d3..85cf68a 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -156,6 +156,7 @@
public final DexString valueOfMethodName = createString("valueOf");
public final DexString toStringMethodName = createString("toString");
+ public final DexString internMethodName = createString("intern");
public final DexString getClassMethodName = createString("getClass");
public final DexString finalizeMethodName = createString("finalize");
@@ -767,6 +768,7 @@
public final DexMethod valueOf;
public final DexMethod toString;
+ public final DexMethod intern;
private StringMethods() {
isEmpty = createMethod(
@@ -810,6 +812,8 @@
stringDescriptor, valueOfMethodName, stringDescriptor, needsOneObject);
toString = createMethod(
stringDescriptor, toStringMethodName, stringDescriptor, DexString.EMPTY_ARRAY);
+ intern = createMethod(
+ stringDescriptor, internMethodName, stringDescriptor, DexString.EMPTY_ARRAY);
}
}
@@ -832,12 +836,12 @@
public final DexMethod defaultConstructor;
public final DexMethod intConstructor;
public final DexMethod stringConstructor;
+ public final DexMethod toString;
private final Set<DexMethod> appendMethods;
private final Set<DexMethod> constructorMethods;
private StringBuildingMethods(DexType receiver) {
- DexType sbufType = createType(createString("Ljava/lang/StringBuffer;"));
DexString append = createString("append");
appendBoolean = createMethod(receiver, createProto(receiver, booleanType), append);
@@ -854,7 +858,7 @@
appendLong = createMethod(receiver, createProto(receiver, longType), append);
appendObject = createMethod(receiver, createProto(receiver, objectType), append);
appendString = createMethod(receiver, createProto(receiver, stringType), append);
- appendStringBuffer = createMethod(receiver, createProto(receiver, sbufType), append);
+ appendStringBuffer = createMethod(receiver, createProto(receiver, stringBufferType), append);
charSequenceConstructor =
createMethod(receiver, createProto(voidType, charSequenceType), constructorMethodName);
@@ -863,6 +867,7 @@
createMethod(receiver, createProto(voidType, intType), constructorMethodName);
stringConstructor =
createMethod(receiver, createProto(voidType, stringType), constructorMethodName);
+ toString = createMethod(receiver, createProto(stringType), toStringMethodName);
appendMethods =
ImmutableSet.of(
@@ -1186,7 +1191,9 @@
return new DexCallSite(methodName, methodProto, bootstrapMethod, bootstrapArgs);
}
- public DexMethod createMethod(DexString clazzDescriptor, DexString name,
+ public DexMethod createMethod(
+ DexString clazzDescriptor,
+ DexString name,
DexString returnTypeDescriptor,
DexString[] parameterDescriptors) {
assert !sorted;
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
index ec6da10..e082fb4 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java
@@ -68,6 +68,7 @@
import com.android.tools.r8.ir.optimize.classinliner.ClassInliner;
import com.android.tools.r8.ir.optimize.lambda.LambdaMerger;
import com.android.tools.r8.ir.optimize.staticizer.ClassStaticizer;
+import com.android.tools.r8.ir.optimize.string.StringBuilderOptimizer;
import com.android.tools.r8.ir.optimize.string.StringOptimizer;
import com.android.tools.r8.ir.regalloc.LinearScanRegisterAllocator;
import com.android.tools.r8.ir.regalloc.RegisterAllocator;
@@ -142,6 +143,7 @@
private final Devirtualizer devirtualizer;
private final CovariantReturnTypeAnnotationTransformer covariantReturnTypeAnnotationTransformer;
private final StringOptimizer stringOptimizer;
+ private final StringBuilderOptimizer stringBuilderOptimizer;
private final UninstantiatedTypeOptimization uninstantiatedTypeOptimization;
private final TypeChecker typeChecker;
private final IdempotentFunctionCallCanonicalizer idempotentFunctionCallCanonicalizer;
@@ -193,6 +195,7 @@
? new CovariantReturnTypeAnnotationTransformer(this, appView.dexItemFactory())
: null;
this.stringOptimizer = new StringOptimizer(appView);
+ this.stringBuilderOptimizer = new StringBuilderOptimizer(appView);
this.nonNullTracker = options.enableNonNullTracking ? new NonNullTracker(appView) : null;
if (appView.enableWholeProgramOptimizations()) {
assert appView.appInfo().hasLiveness();
@@ -624,6 +627,9 @@
if (uninstantiatedTypeOptimization != null) {
uninstantiatedTypeOptimization.logResults();
}
+ if (stringBuilderOptimizer != null) {
+ stringBuilderOptimizer.logResults();
+ }
}
// Check if what we've added to the application builder as synthesized classes are same as
@@ -1004,6 +1010,13 @@
codeRewriter.commonSubexpressionElimination(code);
codeRewriter.simplifyArrayConstruction(code);
codeRewriter.rewriteMoveResult(code);
+ // TODO(b/114002137): for now, string concatenation depends on rewriteMoveResult.
+ if (options.enableStringConcatenationOptimization
+ && !isDebugMode
+ && options.isGeneratingDex()) {
+ stringBuilderOptimizer.computeTrivialStringConcatenation(code);
+ }
+
codeRewriter.splitRangeInvokeConstants(code);
new SparseConditionalConstantPropagation(code).run();
codeRewriter.rewriteSwitch(code);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizationConfiguration.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizationConfiguration.java
new file mode 100644
index 0000000..80dd16f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizationConfiguration.java
@@ -0,0 +1,20 @@
+// Copyright (c) 2019, 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.graph.DexMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.InvokeMethod;
+
+interface StringBuilderOptimizationConfiguration {
+ boolean isBuilderType(DexType type);
+
+ boolean isBuilderInit(DexType builderType, DexMethod method);
+
+ boolean isAppendMethod(DexMethod method);
+
+ boolean isSupportedAppendMethod(InvokeMethod invoke);
+
+ boolean isToStringMethod(DexMethod method);
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizer.java
new file mode 100644
index 0000000..5e6f735
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizer.java
@@ -0,0 +1,418 @@
+// Copyright (c) 2019, 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.graph.AppInfo;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexItemFactory;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.escape.EscapeAnalysis;
+import com.android.tools.r8.ir.analysis.escape.EscapeAnalysisConfiguration;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.logging.Log;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+import it.unimi.dsi.fastutil.objects.Object2IntArrayMap;
+import it.unimi.dsi.fastutil.objects.Object2IntMap;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+// This optimization attempts to replace all builder.toString() calls with a constant string.
+// TODO(b/114002137): for now, the analysis depends on rewriteMoveResult.
+// Consider the following example:
+//
+// StringBuilder builder;
+// if (...) {
+// builder.append("X");
+// } else {
+// builder.append("Y");
+// }
+// builder.toString();
+//
+// Its corresponding IR looks like:
+// block0:
+// b <- new-instance StringBuilder
+// if ... block2 // Otherwise, fallthrough
+// block1:
+// c1 <- "X"
+// b1 <- invoke-virtual b, c1, ...append
+// goto block3
+// block2:
+// c2 <- "Y"
+// b2 <- invoke-virtual b, c2, ...append
+// goto block3
+// block3:
+// invoke-virtual b, ...toString
+//
+// After rewriteMoveResult, aliased out values, b1 and b2, are gone. So the analysis can focus on
+// single SSA values, assuming it's flow-sensitive (which is not true in general).
+public class StringBuilderOptimizer {
+
+ private final AppView<?> appView;
+ private final DexItemFactory factory;
+ private final StringBuilderOptimizationConfiguration optimizationConfiguration;
+
+ private int numberOfBuildersWithMultipleToString = 0;
+ private int numberOfBuildersWithoutToString = 0;
+ private int numberOfBuildersThatEscape = 0;
+ private int numberOfBuildersWhoseResultIsInterned = 0;
+ private int numberOfBuildersWithNonTrivialStateChange = 0;
+ private int numberOfBuildersWithNonStringArg = 0;
+
+ @VisibleForTesting
+ StringBuilderOptimizer(
+ AppView<? extends AppInfo> appView, StringBuilderOptimizationConfiguration configuration) {
+ this.appView = appView;
+ this.factory = appView.dexItemFactory();
+ this.optimizationConfiguration = configuration;
+ }
+
+ public StringBuilderOptimizer(AppView<? extends AppInfo> appView) {
+ this.appView = appView;
+ this.factory = appView.dexItemFactory();
+ this.optimizationConfiguration = new DefaultStringBuilderOptimizationConfiguration();
+ }
+
+ public void logResults() {
+ assert Log.ENABLED;
+ Log.info(getClass(),
+ "# builders w/ multiple toString(): %s", numberOfBuildersWithMultipleToString);
+ Log.info(getClass(),
+ "# builders w/o toString(): %s", numberOfBuildersWithoutToString);
+ Log.info(getClass(),
+ "# builders that escape: %s", numberOfBuildersThatEscape);
+ Log.info(getClass(),
+ "# builders whose result is interned: %s", numberOfBuildersWhoseResultIsInterned);
+ Log.info(getClass(),
+ "# builders w/ non-trivial state change: %s", numberOfBuildersWithNonTrivialStateChange);
+ Log.info(getClass(),
+ "# builders w/ non-string arg: %s", numberOfBuildersWithNonStringArg);
+ }
+
+ public Set<Value> computeTrivialStringConcatenation(IRCode code) {
+ StringConcatenationAnalysis analysis = new StringConcatenationAnalysis(code);
+ Set<Value> builders =
+ analysis.findAllLocalBuilders()
+ .stream()
+ .filter(analysis::canBeOptimized)
+ .collect(Collectors.toSet());
+ // TODO(b/114002137): compute const-string for candidate builders.
+ return builders;
+ }
+
+ class StringConcatenationAnalysis {
+
+ // Inspired by {@link JumboStringTest}. Some code intentionally may have too many append(...).
+ private static final int CONCATENATION_THRESHOLD = 200;
+
+ private final IRCode code;
+
+ // A map from SSA Value of StringBuilder type to its toString() counts.
+ // Reused (e.g., concatenated, toString, concatenated more, toString) builders are out of scope.
+ // TODO(b/114002137): some of those toString could have constant string states.
+ final Object2IntMap<Value> builderToStringCounts = new Object2IntArrayMap<>();
+
+ StringConcatenationAnalysis(IRCode code) {
+ this.code = code;
+ }
+
+ // This optimization focuses on builders that are created and used locally.
+ // In the first step, we collect builders that are created in the current method.
+ // In the next step, we will filter out builders that cannot be optimized. To avoid multiple
+ // iterations per builder, we're collecting # of uses of those builders by iterating the code
+ // twice in this step.
+ private Set<Value> findAllLocalBuilders() {
+ // During the first iteration, collect builders that are locally created.
+ // TODO(b/114002137): Make sure new-instance is followed by <init> before any other calls.
+ for (Instruction instr : code.instructions()) {
+ if (instr.isNewInstance()
+ && optimizationConfiguration.isBuilderType(instr.asNewInstance().clazz)) {
+ Value builder = instr.asNewInstance().dest();
+ assert !builderToStringCounts.containsKey(builder);
+ builderToStringCounts.put(builder, 0);
+ }
+ }
+ if (builderToStringCounts.isEmpty()) {
+ return ImmutableSet.of();
+ }
+ int concatenationCount = 0;
+ // During the second iteration, count builders' usage.
+ for (Instruction instr : code.instructions()) {
+ if (!instr.isInvokeVirtual()) {
+ continue;
+ }
+ InvokeVirtual invoke = instr.asInvokeVirtual();
+ DexMethod invokedMethod = invoke.getInvokedMethod();
+ if (optimizationConfiguration.isAppendMethod(invokedMethod)) {
+ concatenationCount++;
+ // The analysis might be overwhelmed.
+ if (concatenationCount > CONCATENATION_THRESHOLD) {
+ return ImmutableSet.of();
+ }
+ } else if (optimizationConfiguration.isToStringMethod(invokedMethod)) {
+ assert invoke.inValues().size() == 1;
+ Value receiver = invoke.getReceiver().getAliasedValue();
+ for (Value builder : collectAllLinkedBuilders(receiver)) {
+ if (builderToStringCounts.containsKey(builder)) {
+ int count = builderToStringCounts.getInt(builder);
+ builderToStringCounts.put(builder, count + 1);
+ }
+ }
+ }
+ }
+ return builderToStringCounts.keySet();
+ }
+
+ private Set<Value> collectAllLinkedBuilders(Value builder) {
+ Set<Value> builders = Sets.newIdentityHashSet();
+ Set<Value> visited = Sets.newIdentityHashSet();
+ collectAllLinkedBuilders(builder, builders, visited);
+ return builders;
+ }
+
+ private void collectAllLinkedBuilders(Value builder, Set<Value> builders, Set<Value> visited) {
+ if (!visited.add(builder)) {
+ return;
+ }
+ if (builder.isPhi()) {
+ for (Value operand : builder.asPhi().getOperands()) {
+ collectAllLinkedBuilders(operand, builders, visited);
+ }
+ } else {
+ builders.add(builder);
+ }
+ }
+
+ private boolean canBeOptimized(Value builder) {
+ // If the builder is definitely null, it may be handled by other optimizations.
+ // E.g., any further operations, such as append, will raise NPE.
+ // But, as we collect local builders, it should never be null.
+ assert !builder.isAlwaysNull(appView);
+ // Before checking the builder usage, make sure we have its usage count.
+ assert builderToStringCounts.containsKey(builder);
+ // If a builder is reused, chances are the code is not trivial, e.g., building a prefix
+ // at some point; appending different suffices in different conditions; and building again.
+ if (builderToStringCounts.getInt(builder) > 1) {
+ numberOfBuildersWithMultipleToString++;
+ return false;
+ }
+ // If a builder is not used, i.e., never converted to string, it doesn't make sense to
+ // attempt to compute its compile-time constant string.
+ if (builderToStringCounts.getInt(builder) < 1) {
+ numberOfBuildersWithoutToString++;
+ return false;
+ }
+ // Make sure builder is neither phi nor coming from outside of the method.
+ assert !builder.isPhi() && builder.definition.isNewInstance();
+ assert builder.getTypeLattice().isClassType();
+ DexType builderType = builder.getTypeLattice().asClassTypeLatticeElement().getClassType();
+ assert optimizationConfiguration.isBuilderType(builderType);
+ EscapeAnalysis escapeAnalysis =
+ new EscapeAnalysis(
+ appView, new StringBuilderOptimizerEscapeAnalysisConfiguration(builder));
+ return !escapeAnalysis.isEscaping(code, builder);
+ }
+ }
+
+ class DefaultStringBuilderOptimizationConfiguration
+ implements StringBuilderOptimizationConfiguration {
+ @Override
+ public boolean isBuilderType(DexType type) {
+ return type == factory.stringBuilderType
+ || type == factory.stringBufferType;
+ }
+
+ @Override
+ public boolean isBuilderInit(DexType builderType, DexMethod method) {
+ return builderType == method.holder
+ && factory.isConstructor(method);
+ }
+
+ @Override
+ public boolean isAppendMethod(DexMethod method) {
+ return factory.stringBuilderMethods.isAppendMethod(method)
+ || factory.stringBufferMethods.isAppendMethod(method);
+ }
+
+ @Override
+ public boolean isSupportedAppendMethod(InvokeMethod invoke) {
+ DexMethod invokedMethod = invoke.getInvokedMethod();
+ assert isAppendMethod(invokedMethod);
+ // Any methods other than append(arg) are not trivial since they may change the builder
+ // state not monotonically.
+ if (invoke.inValues().size() > 2) {
+ numberOfBuildersWithNonTrivialStateChange++;
+ return false;
+ }
+ for (DexType argType : invokedMethod.proto.parameters.values) {
+ if (!canHandleArgumentType(argType)) {
+ numberOfBuildersWithNonStringArg++;
+ return false;
+ }
+ }
+ return true;
+ }
+
+ @Override
+ public boolean isToStringMethod(DexMethod method) {
+ return method == factory.stringBuilderMethods.toString
+ || method == factory.stringBufferMethods.toString;
+ }
+
+ private boolean canHandleArgumentType(DexType argType) {
+ // TODO(b/113859361): passed to another builder should be an eligible case.
+ // TODO(b/114002137): Improve arg extraction and type conversion.
+ // For now, skip any append(arg) that receives non-string types.
+ return argType != factory.stringType && argType != factory.charSequenceType;
+ }
+ }
+
+ class StringBuilderOptimizerEscapeAnalysisConfiguration implements EscapeAnalysisConfiguration {
+ final Value builder;
+ final DexType builderType;
+
+ private StringBuilderOptimizerEscapeAnalysisConfiguration(Value builder) {
+ this.builder = builder;
+ assert builder.getTypeLattice().isClassType();
+ builderType = builder.getTypeLattice().asClassTypeLatticeElement().getClassType();
+ }
+
+ // Use of Builder#toString is legitimate.
+ // TODO(b/134745277): but, the escape analysis can be filtered this out by types.
+ private boolean isUsingToStringAlias(EscapeAnalysis analysis, Value alias) {
+ if (!alias.isPhi() && alias.definition.isInvokeMethod()) {
+ DexMethod invokedMethod = alias.definition.asInvokeMethod().getInvokedMethod();
+ return optimizationConfiguration.isToStringMethod(invokedMethod)
+ && alias.definition.inValues().stream().anyMatch(analysis::isValueOfInterestOrAlias);
+ }
+ return false;
+ }
+
+ private void logEscapingRoute(boolean legitimate) {
+ if (!legitimate) {
+ numberOfBuildersThatEscape++;
+ }
+ }
+
+ @Override
+ public boolean isLegitimateEscapeRoute(
+ AppView<?> appView,
+ EscapeAnalysis escapeAnalysis,
+ Instruction escapeRoute,
+ DexMethod context) {
+ boolean legitimate;
+ if (escapeRoute.isReturn()) {
+ legitimate = isUsingToStringAlias(escapeAnalysis, escapeRoute.asReturn().returnValue());
+ logEscapingRoute(legitimate);
+ return legitimate;
+ }
+ if (escapeRoute.isThrow()) {
+ legitimate = isUsingToStringAlias(escapeAnalysis, escapeRoute.asThrow().exception());
+ logEscapingRoute(legitimate);
+ return legitimate;
+ }
+ if (escapeRoute.isStaticPut()) {
+ legitimate = isUsingToStringAlias(escapeAnalysis, escapeRoute.asStaticPut().inValue());
+ logEscapingRoute(legitimate);
+ return legitimate;
+ }
+ if (escapeRoute.isArrayPut()) {
+ if (escapeRoute.asArrayPut().array().isArgument()) {
+ legitimate = isUsingToStringAlias(escapeAnalysis, escapeRoute.asArrayPut().value());
+ logEscapingRoute(legitimate);
+ return legitimate;
+ }
+ // Putting the builder (or aliases) into a local array is legitimate.
+ // If that local array is used again with array-get, the escape analysis will pick up the
+ // out-value of that instruction and keep tracing the value uses anyway.
+ return true;
+ }
+
+ if (escapeRoute.isInvokeMethod()) {
+ boolean useBuilder = false;
+ boolean useToStringAlias = false;
+ for (Value arg : escapeRoute.asInvokeMethod().inValues()) {
+ // Direct use of the builder should be caught and examined later.
+ if (arg == builder) {
+ useBuilder = true;
+ break;
+ }
+ useToStringAlias |= isUsingToStringAlias(escapeAnalysis, arg);
+ }
+ // It's legitimate if a call doesn't use the builder directly, but use aliased values of
+ // Builder#toString.
+ if (!useBuilder && useToStringAlias) {
+ return true;
+ }
+
+ // Program class may call String#intern(). Only allow library calls.
+ // TODO(b/114002137): For now, we allow only library calls to avoid a case like
+ // identity(Builder.toString()).intern(); but it's too restrictive.
+ DexClass holderClass =
+ appView.definitionFor(escapeRoute.asInvokeMethod().getInvokedMethod().holder);
+ if (holderClass != null && !holderClass.isLibraryClass()) {
+ logEscapingRoute(false);
+ return false;
+ }
+
+ InvokeMethod invoke = escapeRoute.asInvokeMethod();
+ DexMethod invokedMethod = invoke.getInvokedMethod();
+ // Make sure builder's uses are local, i.e., not escaping from the current method.
+ if (invokedMethod.holder != builderType) {
+ numberOfBuildersThatEscape++;
+ logEscapingRoute(false);
+ return false;
+ }
+ // <init> is legitimate.
+ if (optimizationConfiguration.isBuilderInit(builderType, invokedMethod)) {
+ return true;
+ }
+ if (optimizationConfiguration.isToStringMethod(invokedMethod)) {
+ Value out = escapeRoute.outValue();
+ if (out != null) {
+ // If Builder#toString is interned, it could be used for equality check.
+ // Replacing builder-based runtime result with a compile time constant may change
+ // the program's runtime behavior.
+ for (Instruction outUser : out.uniqueUsers()) {
+ if (outUser.isInvokeMethodWithReceiver()
+ && outUser.asInvokeMethodWithReceiver().getInvokedMethod()
+ == factory.stringMethods.intern) {
+ numberOfBuildersWhoseResultIsInterned++;
+ logEscapingRoute(false);
+ return false;
+ }
+ }
+ }
+ // Otherwise, use of Builder#toString is legitimate.
+ return true;
+ }
+ // Even though all invocations belong to the builder type, there are some methods other
+ // than append/toString, e.g., setCharAt, setLength, subSequence, etc.
+ // Seeing any of them indicates that this code is not trivial.
+ if (!optimizationConfiguration.isAppendMethod(invokedMethod)) {
+ numberOfBuildersWithNonTrivialStateChange++;
+ logEscapingRoute(false);
+ return false;
+ }
+ if (!optimizationConfiguration.isSupportedAppendMethod(invoke)) {
+ return false;
+ }
+
+ // Reaching here means that this invocation is part of trivial patterns we're looking for.
+ return true;
+ }
+
+ // All other cases are not legitimate.
+ logEscapingRoute(false);
+ return false;
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
index adf737c..78cf79e 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -167,6 +167,8 @@
public boolean enableServiceLoaderRewriting = true;
// TODO(b/120138731): Enable this when it is worthwhile, e.g., combined with Class#forName.
public boolean enableNameReflectionOptimization = false;
+ // TODO(b/114002137): Enable this when it is worthwhile, e.g., support non-String args.
+ public boolean enableStringConcatenationOptimization = false;
public boolean enableTreeShakingOfLibraryMethodOverrides = false;
// This defines the max depth threshold for the cycle eliminator. If the length of a call chain
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizerAnalysisTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizerAnalysisTest.java
new file mode 100644
index 0000000..6995a33
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringBuilderOptimizerAnalysisTest.java
@@ -0,0 +1,154 @@
+// Copyright (c) 2019, 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 org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.AnalysisTestBase;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.InvokeMethod;
+import com.android.tools.r8.ir.code.Value;
+import java.util.Set;
+import java.util.function.Consumer;
+import org.junit.Test;
+
+public class StringBuilderOptimizerAnalysisTest extends AnalysisTestBase {
+
+ public StringBuilderOptimizerAnalysisTest() throws Exception {
+ super(StringConcatenationTestClass.class.getTypeName(), StringConcatenationTestClass.class);
+ }
+
+ @Test
+ public void testTrivialSequence() throws Exception {
+ buildAndCheckIR("trivialSequence", checkBuilderDetection(builders -> {
+ assertEquals(1, builders.size());
+ }));
+ }
+
+ @Test
+ public void testNonStringArgs() throws Exception {
+ buildAndCheckIR("nonStringArgs", checkBuilderDetection(builders -> {
+ // TODO(b/114002137): Improve arg extraction and type conversion.
+ assertEquals(0, builders.size());
+ }));
+ }
+
+ @Test
+ public void testTypeConversion() throws Exception {
+ buildAndCheckIR("typeConversion", checkBuilderDetection(builders -> {
+ // TODO(b/114002137): Improve arg extraction and type conversion.
+ assertEquals(0, builders.size());
+ }));
+ }
+
+ @Test
+ public void testNestedBuilders_appendBuilderItself() throws Exception {
+ buildAndCheckIR("nestedBuilders_appendBuilderItself", checkBuilderDetection(builders -> {
+ assertEquals(1, builders.size());
+ }));
+ }
+
+ @Test
+ public void testNestedBuilders_appendBuilderResult() throws Exception {
+ buildAndCheckIR("nestedBuilders_appendBuilderResult", checkBuilderDetection(builders -> {
+ assertEquals(2, builders.size());
+ }));
+ }
+
+ @Test
+ public void testSimplePhi() throws Exception {
+ buildAndCheckIR("simplePhi", checkBuilderDetection(builders -> {
+ // TODO(b/114002137): Improve arg extraction and type conversion.
+ assertEquals(0, builders.size());
+ }));
+ }
+
+ @Test
+ public void testPhiAtInit() throws Exception {
+ buildAndCheckIR("phiAtInit", checkBuilderDetection(builders -> {
+ assertEquals(2, builders.size());
+ }));
+ }
+
+ @Test
+ public void testPhiWithDifferentInits() throws Exception {
+ buildAndCheckIR("phiWithDifferentInits", checkBuilderDetection(builders -> {
+ assertEquals(2, builders.size());
+ }));
+ }
+
+ @Test
+ public void testLoop() throws Exception {
+ buildAndCheckIR("loop", checkBuilderDetection(builders -> {
+ assertEquals(2, builders.size());
+ }));
+ }
+
+ @Test
+ public void testLoopWithBuilder() throws Exception {
+ buildAndCheckIR("loopWithBuilder", checkBuilderDetection(builders -> {
+ assertEquals(1, builders.size());
+ }));
+ }
+
+ // TODO(b/114002137): later, test what const-string is computed for builders.
+ private Consumer<IRCode> checkBuilderDetection(Consumer<Set<Value>> builderConsumer) {
+ return code -> {
+ StringBuilderOptimizer optimizer =
+ new StringBuilderOptimizer(
+ appView, new StringBuilderOptimizationConfigurationForTesting());
+ Set<Value> builders = optimizer.computeTrivialStringConcatenation(code);
+ builderConsumer.accept(builders);
+ };
+ }
+
+ class StringBuilderOptimizationConfigurationForTesting
+ implements StringBuilderOptimizationConfiguration {
+ @Override
+ public boolean isBuilderType(DexType type) {
+ String descriptor = type.toDescriptorString();
+ return descriptor.equals(appView.dexItemFactory().stringBuilderType.toDescriptorString())
+ || descriptor.equals(appView.dexItemFactory().stringBufferType.toDescriptorString());
+ }
+
+ @Override
+ public boolean isBuilderInit(DexType builderType, DexMethod method) {
+ return builderType == method.holder
+ && method.name.toString().equals("<init>");
+ }
+
+ @Override
+ public boolean isAppendMethod(DexMethod method) {
+ return isBuilderType(method.holder) && method.name.toString().equals("append");
+ }
+
+ @Override
+ public boolean isSupportedAppendMethod(InvokeMethod invoke) {
+ DexMethod invokedMethod = invoke.getInvokedMethod();
+ assert isAppendMethod(invokedMethod);
+ if (invoke.inValues().size() > 2) {
+ return false;
+ }
+ for (DexType argType : invokedMethod.proto.parameters.values) {
+ if (!canHandleArgumentType(argType)) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ @Override
+ public boolean isToStringMethod(DexMethod method) {
+ return isBuilderType(method.holder) && method.name.toString().equals("toString");
+ }
+
+ private boolean canHandleArgumentType(DexType argType) {
+ String descriptor = argType.toDescriptorString();
+ return descriptor.equals(appView.dexItemFactory().stringType.toDescriptorString())
+ || descriptor.equals(appView.dexItemFactory().charSequenceType.toDescriptorString());
+ }
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatenationTest.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatenationTest.java
index b0c07a7..3d3c010 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatenationTest.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatenationTest.java
@@ -14,6 +14,7 @@
import com.android.tools.r8.TestParameters;
import com.android.tools.r8.TestParametersCollection;
import com.android.tools.r8.TestRunResult;
+import com.android.tools.r8.utils.InternalOptions;
import com.android.tools.r8.utils.StringUtils;
import com.android.tools.r8.utils.codeinspector.ClassSubject;
import com.android.tools.r8.utils.codeinspector.CodeInspector;
@@ -35,6 +36,8 @@
"Hello,R8",
"Hello,",
"Hello,D8",
+ "Hello,R8",
+ "Hello,R8",
"na;na;na;na;na;na;na;na;Batman!",
"na;na;na;na;na;na;na;na;Batman!"
);
@@ -60,7 +63,10 @@
}
private void test(
- TestRunResult result, int expectedStringCount1, int expectedStringCount2)
+ TestRunResult result,
+ int expectedStringCount1,
+ int expectedStringCount2,
+ int expectedStringCount3)
throws Exception {
CodeInspector codeInspector = result.inspector();
ClassSubject mainClass = codeInspector.clazz(MAIN);
@@ -93,7 +99,7 @@
assertThat(method, isPresent());
count = Streams.stream(method.iterateInstructions(
i -> i.isConstString(JumboStringMode.ALLOW))).count();
- assertEquals(expectedStringCount2, count);
+ assertEquals(expectedStringCount3, count);
method = mainClass.uniqueMethodWithName("simplePhi");
assertThat(method, isPresent());
@@ -101,6 +107,18 @@
i -> i.isConstString(JumboStringMode.ALLOW))).count();
assertEquals(5, count);
+ method = mainClass.uniqueMethodWithName("phiAtInit");
+ assertThat(method, isPresent());
+ count = Streams.stream(method.iterateInstructions(
+ i -> i.isConstString(JumboStringMode.ALLOW))).count();
+ assertEquals(3, count);
+
+ method = mainClass.uniqueMethodWithName("phiWithDifferentInits");
+ assertThat(method, isPresent());
+ count = Streams.stream(method.iterateInstructions(
+ i -> i.isConstString(JumboStringMode.ALLOW))).count();
+ assertEquals(3, count);
+
method = mainClass.uniqueMethodWithName("loop");
assertThat(method, isPresent());
count = Streams.stream(method.iterateInstructions(
@@ -123,34 +141,44 @@
.debug()
.addProgramClasses(MAIN)
.setMinApi(parameters.getRuntime())
+ .addOptionsModification(this::configure)
.run(parameters.getRuntime(), MAIN)
.assertSuccessWithOutput(JAVA_OUTPUT);
- test(result, 3, 4);
+ test(result, 3, 4, 4);
result =
testForD8()
.release()
.addProgramClasses(MAIN)
.setMinApi(parameters.getRuntime())
+ .addOptionsModification(this::configure)
.run(parameters.getRuntime(), MAIN)
.assertSuccessWithOutput(JAVA_OUTPUT);
- // TODO(b/114002137): could be 1 and 3.
- test(result, 3, 4);
+ // TODO(b/114002137): could be 1, 4, and 3.
+ test(result, 3, 4, 4);
}
@Test
public void testR8() throws Exception {
+ assumeTrue("CF does not canonicalize constants.", parameters.isDexRuntime());
+
R8TestRunResult result =
testForR8(parameters.getBackend())
.addProgramClasses(MAIN)
.enableInliningAnnotations()
.addKeepMainRule(MAIN)
- .setMinApi(parameters.getRuntime())
.noMinification()
+ .setMinApi(parameters.getRuntime())
+ .addOptionsModification(this::configure)
.run(parameters.getRuntime(), MAIN)
.assertSuccessWithOutput(JAVA_OUTPUT);
- // TODO(b/114002137): could be 1 and 3.
- test(result, 3, 4);
+ // TODO(b/114002137): could be 1, 4, and 3.
+ test(result, 3, 4, 4);
+ }
+
+ // TODO(b/114002137): Once enabled, remove this test-specific setting.
+ private void configure(InternalOptions options) {
+ options.enableStringConcatenationOptimization = true;
}
}
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatenationTestClass.java b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatenationTestClass.java
index 3cfb5de..9a5856d 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatenationTestClass.java
+++ b/src/test/java/com/android/tools/r8/ir/optimize/string/StringConcatenationTestClass.java
@@ -84,6 +84,24 @@
}
@NeverInline
+ public static void phiAtInit() {
+ // TODO(b/114002137): Use ASM to test two new-instance calls flow into the same <init>
+ StringBuilder builder =
+ System.currentTimeMillis() > 0 ? new StringBuilder("Hello") : new StringBuilder("Hi");
+ builder.append(",R8");
+ System.out.println(builder.toString());
+ }
+
+ @NeverInline
+ public static void phiWithDifferentInits() {
+ StringBuilder b1 = new StringBuilder("Hello");
+ StringBuilder b2 = new StringBuilder("Hi");
+ StringBuilder builder = System.currentTimeMillis() > 0 ? b1 : b2;
+ builder.append(",R8");
+ System.out.println(builder.toString());
+ }
+
+ @NeverInline
public static void loop() {
String r = "";
for (int i = 0; i < 8; i++) {
@@ -109,6 +127,8 @@
nestedBuilders_appendBuilderItself();
nestedBuilders_appendBuilderResult();
simplePhi();
+ phiAtInit();
+ phiWithDifferentInits();
loop();
loopWithBuilder();
}
