Limit the aliases for escape analysis based on root types.
Bug: 134745277
Change-Id: I9d775f536ba3a800b06fb4685013da9e72a7155c
diff --git a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
index 4b2cb70..f9dcc57 100644
--- a/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
+++ b/src/main/java/com/android/tools/r8/graph/AppInfoWithSubtyping.java
@@ -753,4 +753,8 @@
}
return lubType;
}
+
+ public boolean inDifferentHierarchy(DexType type1, DexType type2) {
+ return !isSubtype(type1, type2) && !isSubtype(type2, type1);
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysis.java
index b77c1f9..466edeb 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysis.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysis.java
@@ -144,14 +144,22 @@
}
}
// Track aliased value.
- if (user.couldIntroduceAnAlias()) {
+ boolean couldIntroduceTrackedValueAlias = false;
+ for (Value trackedValue : trackedValues) {
+ if (user.couldIntroduceAnAlias(appView, trackedValue)) {
+ couldIntroduceTrackedValueAlias = true;
+ break;
+ }
+ }
+ if (couldIntroduceTrackedValueAlias) {
Value outValue = user.outValue();
- assert outValue != null;
+ assert outValue != null && outValue.getTypeLattice().isReference();
addToWorklist(outValue);
}
// Track propagated values through which the value of interest can escape indirectly.
Value propagatedValue = getPropagatedSubject(alias, user);
if (propagatedValue != null && propagatedValue != alias) {
+ assert propagatedValue.getTypeLattice().isReference();
addToWorklist(propagatedValue);
}
}
@@ -187,9 +195,15 @@
}
return true;
}
- // Storing to the argument array.
+ // Storing to non-local array.
if (instr.isArrayPut()) {
- return instr.asArrayPut().array().isArgument();
+ Value array = instr.asArrayPut().array().getAliasedValue();
+ return array.isPhi() || !array.definition.isCreatingArray();
+ }
+ // Storing to non-local instance.
+ if (instr.isInstancePut()) {
+ Value instance = instr.asInstancePut().object().getAliasedValue();
+ return instance.isPhi() || !instance.definition.isNewInstance();
}
return false;
}
@@ -199,14 +213,6 @@
}
private static Value getPropagatedSubject(Value src, Instruction instr) {
- // We may need to bind array index if we want to track array-get precisely:
- // array-put arr, idx1, x
- // y <- array-get arr, idx2 // y is not what we want to track.
- // z <- array-get arr, idx1 // but, z is.
- // For now, we don't distinguish such cases, which is conservative.
- if (instr.isArrayGet()) {
- return instr.asArrayGet().dest();
- }
if (instr.isArrayPut()) {
return instr.asArrayPut().array();
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java b/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
index 045acf6..98aa687 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayGet.java
@@ -62,6 +62,13 @@
}
@Override
+ public boolean couldIntroduceAnAlias(AppView<?> appView, Value root) {
+ assert root != null && root.getTypeLattice().isReference();
+ assert outValue != null;
+ return outValue.getTypeLattice().isReference();
+ }
+
+ @Override
public void buildDex(DexBuilder builder) {
int dest = builder.allocatedRegister(dest(), getNumber());
int array = builder.allocatedRegister(array(), getNumber());
diff --git a/src/main/java/com/android/tools/r8/ir/code/Assume.java b/src/main/java/com/android/tools/r8/ir/code/Assume.java
index 5593a7d..823e3d0 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Assume.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Assume.java
@@ -29,6 +29,7 @@
super(dest, src);
assert assumption != null;
assert assumption.verifyCorrectnessOfValues(dest, src, appView);
+ assert dest != null;
this.assumption = assumption;
this.origin = origin;
}
@@ -120,13 +121,31 @@
}
@Override
- public boolean isIntroducingAnAlias() {
- return true;
+ public boolean couldIntroduceAnAlias(AppView<?> appView, Value root) {
+ assert root != null && root.getTypeLattice().isReference();
+ assert outValue != null;
+ TypeLatticeElement outType = outValue.getTypeLattice();
+ if (outType.isPrimitive()) {
+ return false;
+ }
+ if (assumption.isAssumeDynamicType()) {
+ outType = asAssumeDynamicType().assumption.getType();
+ }
+ if (appView.appInfo().hasSubtyping()) {
+ if (outType.isClassType()
+ && root.getTypeLattice().isClassType()
+ && appView.appInfo().withSubtyping().inDifferentHierarchy(
+ outType.asClassTypeLatticeElement().getClassType(),
+ root.getTypeLattice().asClassTypeLatticeElement().getClassType())) {
+ return false;
+ }
+ }
+ return outType.isReference();
}
@Override
- public boolean couldIntroduceAnAlias() {
- return outValue != null && outValue.getTypeLattice().isReference();
+ public boolean isIntroducingAnAlias() {
+ return true;
}
@Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java b/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
index 8859225..da70d9f 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstanceGet.java
@@ -63,8 +63,10 @@
}
@Override
- public boolean couldIntroduceAnAlias() {
- return outValue != null && outValue.getTypeLattice().isReference();
+ public boolean couldIntroduceAnAlias(AppView<?> appView, Value root) {
+ assert root != null && root.getTypeLattice().isReference();
+ assert outValue != null;
+ return outValue.getTypeLattice().isReference();
}
@Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/Instruction.java b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
index d8e7f10..7fc61aa 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Instruction.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Instruction.java
@@ -1211,7 +1211,7 @@
* <p>This is a conservative version of {@link #isIntroducingAnAlias()} so that other analyses,
* e.g., escape analysis, can propagate or track aliased values in a conservative manner.
*/
- public boolean couldIntroduceAnAlias() {
+ public boolean couldIntroduceAnAlias(AppView<?> appView, Value root) {
return false;
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Invoke.java b/src/main/java/com/android/tools/r8/ir/code/Invoke.java
index 44864f6..ec77df1 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Invoke.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Invoke.java
@@ -182,8 +182,25 @@
}
@Override
- public boolean couldIntroduceAnAlias() {
- return outValue != null && outValue.getTypeLattice().isReference();
+ public boolean couldIntroduceAnAlias(AppView<?> appView, Value root) {
+ assert root != null && root.getTypeLattice().isReference();
+ if (outValue == null) {
+ return false;
+ }
+ TypeLatticeElement outType = outValue.getTypeLattice();
+ if (outType.isPrimitive()) {
+ return false;
+ }
+ if (appView.appInfo().hasSubtyping()) {
+ if (outType.isClassType()
+ && root.getTypeLattice().isClassType()
+ && appView.appInfo().withSubtyping().inDifferentHierarchy(
+ outType.asClassTypeLatticeElement().getClassType(),
+ root.getTypeLattice().asClassTypeLatticeElement().getClassType())) {
+ return false;
+ }
+ }
+ return outType.isReference();
}
@Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/Move.java b/src/main/java/com/android/tools/r8/ir/code/Move.java
index 821b67d..9eeaf3e 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Move.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Move.java
@@ -37,8 +37,8 @@
}
@Override
- public boolean couldIntroduceAnAlias() {
- return outValue != null && outValue.getTypeLattice().isReference();
+ public boolean couldIntroduceAnAlias(AppView<?> appView, Value root) {
+ throw new Unreachable("as long as we're analyzing SSA IR.");
}
@Override
diff --git a/src/main/java/com/android/tools/r8/ir/code/StaticGet.java b/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
index b4cc421..0f7b49e 100644
--- a/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
+++ b/src/main/java/com/android/tools/r8/ir/code/StaticGet.java
@@ -51,8 +51,23 @@
}
@Override
- public boolean couldIntroduceAnAlias() {
- return outValue != null && outValue.getTypeLattice().isReference();
+ public boolean couldIntroduceAnAlias(AppView<?> appView, Value root) {
+ assert root != null && root.getTypeLattice().isReference();
+ assert outValue != null;
+ TypeLatticeElement outType = outValue.getTypeLattice();
+ if (outType.isPrimitive()) {
+ return false;
+ }
+ if (appView.appInfo().hasSubtyping()) {
+ if (outType.isClassType()
+ && root.getTypeLattice().isClassType()
+ && appView.appInfo().withSubtyping().inDifferentHierarchy(
+ outType.asClassTypeLatticeElement().getClassType(),
+ root.getTypeLattice().asClassTypeLatticeElement().getClassType())) {
+ return false;
+ }
+ }
+ return outType.isReference();
}
@Override
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
index 1ea8b3e..f421fc1 100644
--- 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
@@ -719,17 +719,6 @@
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++;
@@ -742,51 +731,11 @@
EscapeAnalysis escapeAnalysis,
Instruction escapeRoute,
DexMethod context) {
- boolean legitimate;
- if (escapeRoute.isReturn()) {
- legitimate = isUsingToStringAlias(escapeAnalysis, escapeRoute.asReturn().returnValue());
- logEscapingRoute(legitimate);
- return legitimate;
+ if (escapeRoute.isReturn() || escapeRoute.isThrow() || escapeRoute.isStaticPut()) {
+ logEscapingRoute(false);
+ return false;
}
- if (escapeRoute.isThrow()) {
- legitimate = isUsingToStringAlias(escapeAnalysis, escapeRoute.asThrow().exception());
- logEscapingRoute(legitimate);
- return legitimate;
- }
- if (escapeRoute.isStaticPut()) {
- legitimate = isUsingToStringAlias(escapeAnalysis, escapeRoute.asStaticPut().value());
- 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.
@@ -801,7 +750,6 @@
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;
}
@@ -820,7 +768,6 @@
&& outUser.asInvokeMethodWithReceiver().getInvokedMethod()
== factory.stringMethods.intern) {
numberOfBuildersWhoseResultIsInterned++;
- logEscapingRoute(false);
return false;
}
}
@@ -833,7 +780,6 @@
// Seeing any of them indicates that this code is not trivial.
if (!optimizationConfiguration.isAppendMethod(invokedMethod)) {
numberOfBuildersWithNonTrivialStateChange++;
- logEscapingRoute(false);
return false;
}
if (!optimizationConfiguration.isSupportedAppendMethod(invoke)) {
@@ -843,7 +789,18 @@
// Reaching here means that this invocation is part of trivial patterns we're looking for.
return true;
}
-
+ if (escapeRoute.isArrayPut()) {
+ Value array = escapeRoute.asArrayPut().array().getAliasedValue();
+ boolean legitimate = !array.isPhi() && array.definition.isCreatingArray();
+ logEscapingRoute(legitimate);
+ return legitimate;
+ }
+ if (escapeRoute.isInstancePut()) {
+ Value instance = escapeRoute.asInstancePut().object().getAliasedValue();
+ boolean legitimate = !instance.isPhi() && instance.definition.isNewInstance();
+ logEscapingRoute(legitimate);
+ return legitimate;
+ }
// All other cases are not legitimate.
logEscapingRoute(false);
return false;
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
index 549eb70..de33a67 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/string/StringOptimizer.java
@@ -409,7 +409,7 @@
}
}
- public static class StringOptimizerEscapeAnalysisConfiguration
+ static class StringOptimizerEscapeAnalysisConfiguration
implements EscapeAnalysisConfiguration {
private static final StringOptimizerEscapeAnalysisConfiguration INSTANCE =
@@ -447,7 +447,12 @@
return false;
}
if (escapeRoute.isArrayPut()) {
- return !escapeRoute.asArrayPut().array().isArgument();
+ Value array = escapeRoute.asArrayPut().array().getAliasedValue();
+ return !array.isPhi() && array.definition.isCreatingArray();
+ }
+ if (escapeRoute.isInstancePut()) {
+ Value instance = escapeRoute.asInstancePut().object().getAliasedValue();
+ return !instance.isPhi() && instance.definition.isNewInstance();
}
// All other cases are not legitimate.
return false;
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysisForNameReflectionTest.java b/src/test/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysisForNameReflectionTest.java
index 1fde43a..c337379 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysisForNameReflectionTest.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/escape/EscapeAnalysisForNameReflectionTest.java
@@ -10,7 +10,6 @@
import com.android.tools.r8.TestParameters;
import com.android.tools.r8.TestParametersCollection;
-import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.ir.analysis.AnalysisTestBase;
@@ -19,7 +18,6 @@
import com.android.tools.r8.ir.code.InvokeVirtual;
import com.android.tools.r8.ir.code.NewInstance;
import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.ir.optimize.string.StringOptimizer;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
@@ -75,7 +73,7 @@
instr ->
instr.isThrow()
|| (instr.isInvokeDirect()
- && invokesMethodWithName("<init>").test(instr))));
+ && invokesMethodWithName("<init>").test(instr))));
});
}
@@ -85,22 +83,35 @@
}
@Test
- public void testEscapeViaInstancePut() throws Exception {
+ public void testEscapeViaInstancePut_local() throws Exception {
buildAndCheckIR(
- "escapeViaInstancePut",
+ "escapeViaInstancePut_local",
checkEscapingName(true, invokesMethodWithName("namingInterfaceConsumer")));
}
@Test
- public void testEscapeViaArrayPut() throws Exception {
+ public void testEscapeViaArrayPut_local() throws Exception {
buildAndCheckIR(
- "escapeViaArrayPut",
+ "escapeViaArrayPut_local",
checkEscapingName(true, invokesMethodWithName("namingInterfacesConsumer")));
}
@Test
- public void testEscapeViaArrayArgumentPut() throws Exception {
- buildAndCheckIR("escapeViaArrayArgumentPut", checkEscapingName(true, Instruction::isArrayPut));
+ public void testEscapeViaArrayPut_heap() throws Exception {
+ buildAndCheckIR(
+ "escapeViaArrayPut_heap",
+ checkEscapingName(
+ true,
+ i -> i.isArrayPut() || invokesMethodWithName("namingInterfacesConsumer").test(i)));
+ }
+
+ @Test
+ public void testEscapeViaArrayPut_argument() throws Exception {
+ buildAndCheckIR(
+ "escapeViaArrayPut_argument",
+ checkEscapingName(
+ true,
+ i -> i.isArrayPut() || invokesMethodWithName("namingInterfacesConsumer").test(i)));
}
@Test
@@ -179,7 +190,12 @@
return false;
}
if (escapeRoute.isArrayPut()) {
- return !escapeRoute.asArrayPut().array().isArgument();
+ Value array = escapeRoute.asArrayPut().array().getAliasedValue();
+ return !array.isPhi() && array.definition.isCreatingArray();
+ }
+ if (escapeRoute.isInstancePut()) {
+ Value instance = escapeRoute.asInstancePut().object().getAliasedValue();
+ return !instance.isPhi() && instance.definition.isNewInstance();
}
// All other cases are not legitimate.
return false;
@@ -241,6 +257,8 @@
}
static class TestClass implements NamingInterface {
+ private static NamingInterface[] ARRAY = new NamingInterface[1];
+
static String tag;
String id;
@@ -280,13 +298,13 @@
tag = TestClass.class.getSimpleName();
}
- public static void escapeViaInstancePut() {
+ public static void escapeViaInstancePut_local() {
TestClass instance = new TestClass();
instance.id = instance.getClass().getSimpleName();
Helper.namingInterfaceConsumer(instance);
}
- public static void escapeViaArrayPut() {
+ public static void escapeViaArrayPut_local() {
TestClass instance = new TestClass();
instance.id = instance.getClass().getSimpleName();
NamingInterface[] array = new NamingInterface[1];
@@ -294,7 +312,14 @@
Helper.namingInterfacesConsumer(array);
}
- public static void escapeViaArrayArgumentPut(NamingInterface[] array) {
+ public static void escapeViaArrayPut_heap() {
+ TestClass instance = new TestClass();
+ instance.id = instance.getClass().getSimpleName();
+ ARRAY[0] = instance;
+ Helper.namingInterfacesConsumer(ARRAY);
+ }
+
+ public static void escapeViaArrayPut_argument(NamingInterface[] array) {
TestClass instance = new TestClass();
instance.id = instance.getClass().getSimpleName();
array[0] = instance;
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 856dd81..fc87c72 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
@@ -154,7 +154,9 @@
.addOptionsModification(this::configure)
.run(parameters.getRuntime(), MAIN)
.assertSuccessWithOutput(JAVA_OUTPUT);
- test(result, 1, 4, 3);
+ // TODO(b/114002137): The lack of subtyping made the escape analysis to regard
+ // StringBuilder#toString as an alias-introducing instruction.
+ test(result, 3, 4, 3);
}
@Test
