Revert "Better side effect analysis for StringConcat optimizations"
This reverts commit 1ed138a3e738b79b3e904a13eb110d8a1d1c452b.
Reason for revert: Possibly blocking R8 roll to studio-main due to test failure: //tools/base/build-system/integration-test/connected:MinifyInstrumentLibConnectedTest
Original change's description:
> Better side effect analysis for StringConcat optimizations
>
> Chrome size with enableStringConcatInstruction:
> before: 21875128
> after: 21875080
>
> Bug: 467374229
> Change-Id: Ib17972b385c8d0507ef069d7a9bbc0852286c144
Bug: 467374229
Change-Id: I469ffcfed1aee58b8207e3b52168f86f28e8a005
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index 9ac375a..73930b4 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -1576,62 +1576,6 @@
}
/**
- * Visits all instructions between from & to (non-inclusive) and returns whether the predicate
- * returned true for any of them.
- *
- * <p>This assumes that {@code from} dominates {@code to}.
- */
- public boolean anyInstructionBetween(
- Instruction from, Instruction to, Predicate<Instruction> predicate) {
- BasicBlock fromBlock = from.getBlock();
- BasicBlock toBlock = to.getBlock();
- if (fromBlock == toBlock) {
- assert from.comesBefore(to);
- for (Instruction cur = from.getNext(); cur != to; cur = cur.getNext()) {
- if (predicate.test(cur)) {
- return true;
- }
- }
- return false;
- }
-
- for (Instruction cur = from.getNext(); cur != null; cur = cur.getNext()) {
- if (predicate.test(cur)) {
- return true;
- }
- }
-
- for (Instruction cur = to.getPrev(); cur != null; cur = cur.getPrev()) {
- if (predicate.test(cur)) {
- return true;
- }
- }
-
- int color = reserveMarkingColor();
- try {
- fromBlock.mark(color);
- toBlock.mark(color);
- Deque<BasicBlock> worklist = new ArrayDeque<>(toBlock.getPredecessors());
-
- while (!worklist.isEmpty()) {
- BasicBlock block = worklist.poll();
- if (block.isMarked(color)) {
- continue;
- }
- for (Instruction unused : block.getInstructions(predicate)) {
- return true;
- }
- block.mark(color);
- worklist.addAll(block.getPredecessors());
- }
- } finally {
- returnMarkingColor(color);
- }
-
- return false;
- }
-
- /**
* Returns the set of blocks that are reachable from the given source. The source itself is only
* included if there is a path from the given block to itself.
*/
diff --git a/src/main/java/com/android/tools/r8/ir/code/StringConcat.java b/src/main/java/com/android/tools/r8/ir/code/StringConcat.java
index 93d8732..60e7a82 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StringConcat.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StringConcat.java
@@ -17,7 +17,6 @@
import com.android.tools.r8.ir.optimize.Inliner;
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.InliningConstraints;
-import com.android.tools.r8.ir.optimize.library.sideeffects.JavaLangObjectsSideEffectCollection;
import com.android.tools.r8.lightir.LirBuilder;
import com.android.tools.r8.utils.internal.exceptions.Unreachable;
import java.util.Arrays;
@@ -38,8 +37,6 @@
// It's invalid for two constants to be adjacent (they should have been merged in this case).
private List<DexString> argConstants;
- private Boolean cachedMightCallToStringWithSideEffects;
-
private StringConcat(
Value outValue, List<Value> inValues, DexType[] argTypes, List<DexString> argConstants) {
super(outValue, inValues);
@@ -119,7 +116,6 @@
inValues.addAll(newInValues);
argTypes = newArgTypes;
argConstants = newArgConstants;
- cachedMightCallToStringWithSideEffects = null;
assertValidState();
}
@@ -186,19 +182,22 @@
return true;
}
+ public static boolean toStringMayHaveSideEffects(
+ DexItemFactory dexItemFactory, TypeElement type) {
+ // TODO(467374229): Inspect the actual toString() for side effects.
+ return type.isClassType()
+ && !type.isStringType(dexItemFactory)
+ && dexItemFactory.getPrimitiveFromBoxed(type.toDexType(dexItemFactory)) == null;
+ }
+
public boolean mightCallToStringWithSideEffects(AppView<?> appView) {
- if (cachedMightCallToStringWithSideEffects != null) {
- return cachedMightCallToStringWithSideEffects;
- }
- boolean ret = false;
+ // TODO(agrieve): check if the toString method of each argType may have side effects.
for (Value value : inValues) {
- if (JavaLangObjectsSideEffectCollection.toStringMayHaveSideEffects(appView, value)) {
- ret = true;
- break;
+ if (toStringMayHaveSideEffects(appView.dexItemFactory(), value.getType())) {
+ return true;
}
}
- cachedMightCallToStringWithSideEffects = ret;
- return ret;
+ return false;
}
@Override
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/StringConcatOptimizer.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/StringConcatOptimizer.java
index ebb15c1..3f00f2b 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/StringConcatOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/StringConcatOptimizer.java
@@ -21,10 +21,8 @@
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.ir.conversion.MethodProcessor;
import com.android.tools.r8.ir.conversion.passes.result.CodeRewriterResult;
-import com.android.tools.r8.ir.optimize.library.sideeffects.JavaLangObjectsSideEffectCollection;
import com.android.tools.r8.utils.ValueUtils;
import com.android.tools.r8.utils.internal.exceptions.Unreachable;
-import it.unimi.dsi.fastutil.ints.IntArrayList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
@@ -65,10 +63,11 @@
Instruction current = iterator.next();
StringConcat stringConcat = current.asStringConcat();
if (stringConcat != null) {
- if (mergeStringConcats(stringConcat, code)) {
+ if (mergeStringConcats(stringConcat)) {
hasChanged = true;
}
if (!stringConcat.hasUsedOutValue()) {
+ // TODO: Might be worth an option to assume all toString() overloads are side-effect free.
// TODO: Maybe should replace with directly toString() calls rather than concatenating
// (concatenation is likely smaller size once outlined).
removeAllSideEffectFreeInValues(stringConcat, dexItemFactory);
@@ -81,50 +80,33 @@
return CodeRewriterResult.hasChanged(hasChanged);
}
- private boolean hasAnyStringConcatOperands(StringConcat stringConcat) {
+ private boolean hasMergableStringConcats(StringConcat stringConcat) {
for (Value value : stringConcat.inValues()) {
if (value.getAliasedValue().isDefinedByInstructionSatisfying(Instruction::isStringConcat)
&& value.hasSingleUniqueUserAndNoOtherUsers()) {
return true;
}
}
-
return false;
}
/**
- * If any inValue is from a StringConcat, merges it into this instance if its safe to do so.
+ * If any inValue is from a StringConcat, merges it into this instance.
*
* @return Whether any instructions were merged.
*/
- private boolean mergeStringConcats(StringConcat stringConcat, IRCode code) {
- if (!hasAnyStringConcatOperands(stringConcat)) {
- return false;
- }
- // Since the order of operands does not necessarily align with the order of their defining
- // instructions, any side effect could impact other values. Rather than trying to check the
- // order of the operands, just bail out in this case.
- if (stringConcat.mightCallToStringWithSideEffects(appView)) {
+ public boolean mergeStringConcats(StringConcat stringConcat) {
+ if (!hasMergableStringConcats(stringConcat)) {
return false;
}
- IntArrayList indicesToMerge = computeMergableConcats(stringConcat, code);
- if (indicesToMerge.isEmpty()) {
- return false;
- }
-
- mergeConcats(stringConcat, indicesToMerge);
- return true;
- }
-
- private void mergeConcats(StringConcat stringConcat, IntArrayList toMergeIndices) {
DexType[] argTypes = stringConcat.getArgTypes();
List<DexString> argConstants = stringConcat.getArgConstants();
List<Value> inValues = stringConcat.inValues();
+
StringConcatBuilder builder = new StringConcatBuilder();
- int inValueIdx = -1;
- int numMerged = 0;
- int nextMergeValueIdx = toMergeIndices.getInt(numMerged);
+
+ int inValueIdx = 0;
for (int argIdx = 0; argIdx < argTypes.length; ++argIdx) {
DexString curString = argConstants.get(argIdx);
if (curString != null) {
@@ -132,12 +114,23 @@
continue;
}
- Value value = inValues.get(++inValueIdx);
- if (inValueIdx != nextMergeValueIdx) {
+ Value value = inValues.get(inValueIdx++);
+ boolean safeToMerge =
+ value.isDefinedByInstructionSatisfying(Instruction::isStringConcat)
+ && value.hasSingleUniqueUserAndNoOtherUsers();
+
+ StringConcat otherStringConcat = null;
+ if (safeToMerge) {
+ // TODO(467374229): We could also allow this if we verify that the order of the toString()
+ // calls does not change when merged.
+ otherStringConcat = value.getDefinition().asStringConcat();
+ safeToMerge = !otherStringConcat.mightCallToStringWithSideEffects(appView);
+ }
+
+ if (!safeToMerge) {
builder.addValue(value, argTypes[argIdx]);
continue;
}
- StringConcat otherStringConcat = value.getDefinition().asStringConcat();
value.clearUsers();
DexType[] otherTypes = otherStringConcat.getArgTypes();
List<DexString> otherConstants = otherStringConcat.getArgConstants();
@@ -156,43 +149,10 @@
}
}
otherStringConcat.removeOrReplaceByDebugLocalRead();
-
- numMerged += 1;
- if (numMerged < toMergeIndices.size()) {
- nextMergeValueIdx = toMergeIndices.getInt(numMerged);
- }
}
builder.apply(stringConcat);
- }
-
- private IntArrayList computeMergableConcats(StringConcat stringConcat, IRCode code) {
- DexType[] argTypes = stringConcat.getArgTypes();
- List<DexString> argConstants = stringConcat.getArgConstants();
- List<Value> inValues = stringConcat.inValues();
- IntArrayList toMergeIndices = new IntArrayList();
-
- int inValueIdx = -1;
- for (int argIdx = 0; argIdx < argTypes.length; ++argIdx) {
- DexString curString = argConstants.get(argIdx);
- if (curString != null) {
- continue;
- }
- Value value = inValues.get(++inValueIdx);
-
- // No need to check getAliasedValue since StringConcat are always @NonNull.
- if (value.isDefinedByInstructionSatisfying(Instruction::isStringConcat)
- && value.hasSingleUniqueUserAndNoOtherUsers()) {
- StringConcat other = value.getDefinition().asStringConcat();
- if (!code.anyInstructionBetween(
- other,
- stringConcat,
- ins -> ins.instructionMayHaveSideEffects(appView, code.context()))) {
- toMergeIndices.add(inValueIdx);
- }
- }
- }
- return toMergeIndices;
+ return true;
}
private boolean canSimplifyArgs(StringConcat stringConcat) {
@@ -256,16 +216,15 @@
Instruction instruction = aliasedValue.getDefinition();
// Translate foo.toString() -> foo.
+ // Check for non-null since null.toString() throws, but "" + null == "null".
if (isToStringInvoke(instruction)) {
Value receiver = instruction.getFirstOperand();
// TODO(467374229): We could also allow this if we verify that the order of the
// toString() call does not change.
Value aliasedReceiver = receiver.getAliasedValue();
if (!aliasedReceiver.isPhi()
- // Check for non-null since null.toString() throws, but "" + null == "null".
&& receiver.isNeverNull()
- && !JavaLangObjectsSideEffectCollection.toStringMayHaveSideEffects(
- appView, receiver)) {
+ && !StringConcat.toStringMayHaveSideEffects(dexItemFactory, receiver.getType())) {
ValueUtils.removeAliasChain(value, aliasedValue);
if (!aliasedValue.hasAnyUsers()) {
// Remove the toString() instruction.
@@ -353,7 +312,7 @@
List<Value> inValues = stringConcat.inValues();
List<Value> newInValues = new ArrayList<>(inValues.size());
for (Value value : inValues) {
- if (JavaLangObjectsSideEffectCollection.toStringMayHaveSideEffects(appView, value)) {
+ if (StringConcat.toStringMayHaveSideEffects(dexItemFactory, value.getType())) {
newInValues.add(value);
} else {
value.removeUser(stringConcat);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/library/sideeffects/JavaLangObjectsSideEffectCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/library/sideeffects/JavaLangObjectsSideEffectCollection.java
index 3fc4def..0c65d04 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/library/sideeffects/JavaLangObjectsSideEffectCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/library/sideeffects/JavaLangObjectsSideEffectCollection.java
@@ -13,25 +13,15 @@
import com.android.tools.r8.ir.analysis.type.TypeElement;
import com.android.tools.r8.ir.code.Value;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
-import java.util.Collections;
import java.util.List;
public class JavaLangObjectsSideEffectCollection {
- public static boolean toStringMayHaveSideEffects(AppView<?> appView, Value value) {
- return toStringMayHaveSideEffects(appView, Collections.singletonList(value));
- }
-
- /** Returns whether String.valueOf(value) might have side-effects. */
public static boolean toStringMayHaveSideEffects(AppView<?> appView, List<Value> arguments) {
// Calling toString() on an array does not call toString() on the array elements.
DexItemFactory dexItemFactory = appView.dexItemFactory();
- Value value = arguments.get(0);
- TypeElement type = value.getType();
- if (type.isPrimitiveType()
- || type.isStringType(dexItemFactory)
- || type.isArrayType()
- || value.isAlwaysNull(appView)) {
+ TypeElement type = arguments.get(0).getType();
+ if (type.isArrayType() || type.isNullType()) {
return false;
}
diff --git a/src/test/java11/com/android/tools/r8/jdk11/string/StringConcatTest.java b/src/test/java11/com/android/tools/r8/jdk11/string/StringConcatTest.java
index 84a8fa5..a5c0eaa 100644
--- a/src/test/java11/com/android/tools/r8/jdk11/string/StringConcatTest.java
+++ b/src/test/java11/com/android/tools/r8/jdk11/string/StringConcatTest.java
@@ -4,8 +4,9 @@
package com.android.tools.r8.jdk11.string;
+import static com.android.tools.r8.utils.codeinspector.Matchers.isPresent;
+import static org.hamcrest.MatcherAssert.assertThat;
import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertTrue;
import com.android.tools.r8.Jdk9TestUtils;
@@ -190,10 +191,10 @@
method = mainClass.uniqueMethodWithOriginalName("mergeStringsWithSideEffects_sameOrder");
assertTrue(method.isPresent());
- assertEquals(2, countStringBuilderOrInvokeDynamic(method));
+ assertEquals(3, countStringBuilderOrInvokeDynamic(method));
method = mainClass.uniqueMethodWithOriginalName("noOutValues_noSideEffects");
- assertFalse("Empty method should be removed.", method.isPresent());
+ assertThat("Empty method should be removed.", method, isPresent());
}
static class Main {
