Optimize instance-of instructions
Change-Id: I1b537278438537f618f849f500c17b1339b6604f
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 3c657ec..c7cd614 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
@@ -793,7 +793,7 @@
assert code.verifyTypes(appInfo);
- codeRewriter.removeCasts(code);
+ codeRewriter.removeTrivialCheckCastAndInstanceOfInstructions(code);
codeRewriter.rewriteLongCompareAndRequireNonNull(code, options);
codeRewriter.commonSubexpressionElimination(code);
codeRewriter.simplifyArrayConstruction(code);
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
index 93df273..a624c6a 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/CodeRewriter.java
@@ -53,6 +53,7 @@
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.If;
import com.android.tools.r8.ir.code.If.Type;
+import com.android.tools.r8.ir.code.InstanceOf;
import com.android.tools.r8.ir.code.InstancePut;
import com.android.tools.r8.ir.code.Instruction;
import com.android.tools.r8.ir.code.InstructionIterator;
@@ -1617,72 +1618,20 @@
return converter.definitionFor(type);
}
- public void removeCasts(IRCode code) {
+ public void removeTrivialCheckCastAndInstanceOfInstructions(IRCode code) {
InstructionIterator it = code.instructionIterator();
boolean needToRemoveTrivialPhis = false;
while (it.hasNext()) {
Instruction current = it.next();
- if (!current.isCheckCast()) {
- continue;
- }
- CheckCast checkCast = current.asCheckCast();
- Value inValue = checkCast.object();
- Value outValue = checkCast.outValue();
- DexType castType = checkCast.getType();
-
- // If the cast type is not accessible in the current context, we should not remove the cast
- // in order to preserve IllegalAccessError. Note that JVM and ART behave differently: see
- // {@link com.android.tools.r8.ir.optimize.checkcast.IllegalAccessErrorTest}.
- DexType baseCastType = castType.toBaseType(appInfo.dexItemFactory);
- DexClass castClass = definitionFor(baseCastType);
- if (castClass != null) {
- ConstraintWithTarget classVisibility = ConstraintWithTarget.deriveConstraint(
- code.method.method.getHolder(), baseCastType, castClass.accessFlags, appInfo);
- if (classVisibility == ConstraintWithTarget.NEVER) {
- continue;
+ if (current.isCheckCast()) {
+ boolean hasPhiUsers = current.outValue().numberOfPhiUsers() != 0;
+ if (removeCheckCastInstructionIfTrivial(current.asCheckCast(), it, code)) {
+ needToRemoveTrivialPhis |= hasPhiUsers;
}
- }
-
- // We might see chains of casts on subtypes. It suffices to cast to the lowest subtype,
- // as that will fail if a cast on a supertype would have failed.
- Predicate<Instruction> isCheckcastToSubtype =
- user -> user.isCheckCast() && user.asCheckCast().getType().isSubtypeOf(castType, appInfo);
- if (!checkCast.getBlock().hasCatchHandlers()
- && outValue.isUsed()
- && outValue.numberOfPhiUsers() == 0
- && outValue.uniqueUsers().stream().allMatch(isCheckcastToSubtype)) {
- removeOrReplaceByDebugLocalWrite(checkCast, it, inValue, outValue);
- continue;
- }
-
- TypeLatticeElement inTypeLattice = inValue.getTypeLattice();
- // TODO(b/72693244): Soon, there won't be a value with imprecise type at this point.
- if (inTypeLattice.isPreciseType() || inTypeLattice.isNull()) {
- TypeLatticeElement outTypeLattice = outValue.getTypeLattice();
- TypeLatticeElement castTypeLattice =
- TypeLatticeElement.fromDexType(castType, inTypeLattice.isNullable(), appInfo);
-
- assert inTypeLattice.nullElement().lessThanOrEqual(outTypeLattice.nullElement());
-
- if (inTypeLattice.lessThanOrEqual(castTypeLattice, appInfo)) {
- // 1) Trivial cast.
- // A a = ...
- // A a' = (A) a;
- // 2) Up-cast: we already have finer type info.
- // A < B
- // A a = ...
- // B b = (B) a;
- assert inTypeLattice.lessThanOrEqual(outTypeLattice, appInfo);
- needToRemoveTrivialPhis = needToRemoveTrivialPhis || outValue.numberOfPhiUsers() != 0;
- removeOrReplaceByDebugLocalWrite(checkCast, it, inValue, outValue);
- } else {
- // Otherwise, keep the checkcast to preserve verification errors. E.g., down-cast:
- // A < B < C
- // c = ... // Even though we know c is of type A,
- // a' = (B) c; // (this could be removed, since chained below.)
- // a'' = (A) a'; // this should remain for runtime verification.
- assert !inTypeLattice.isNull();
- assert outTypeLattice.asNullable().equals(castTypeLattice.asNullable());
+ } else if (current.isInstanceOf()) {
+ boolean hasPhiUsers = current.outValue().numberOfPhiUsers() != 0;
+ if (removeInstanceOfInstructionIfTrivial(current.asInstanceOf(), it, code)) {
+ needToRemoveTrivialPhis |= hasPhiUsers;
}
}
}
@@ -1698,6 +1647,121 @@
assert code.isConsistentSSA();
}
+ // Returns true if the given check-cast instruction was removed.
+ private boolean removeCheckCastInstructionIfTrivial(
+ CheckCast checkCast, InstructionIterator it, IRCode code) {
+ Value inValue = checkCast.object();
+ Value outValue = checkCast.outValue();
+ DexType castType = checkCast.getType();
+
+ // If the cast type is not accessible in the current context, we should not remove the cast
+ // in order to preserve IllegalAccessError. Note that JVM and ART behave differently: see
+ // {@link com.android.tools.r8.ir.optimize.checkcast.IllegalAccessErrorTest}.
+ if (isTypeInaccessibleInCurrentContext(castType, code.method)) {
+ return false;
+ }
+
+ // We might see chains of casts on subtypes. It suffices to cast to the lowest subtype,
+ // as that will fail if a cast on a supertype would have failed.
+ Predicate<Instruction> isCheckcastToSubtype =
+ user -> user.isCheckCast() && user.asCheckCast().getType().isSubtypeOf(castType, appInfo);
+ if (!checkCast.getBlock().hasCatchHandlers()
+ && outValue.isUsed()
+ && outValue.numberOfPhiUsers() == 0
+ && outValue.uniqueUsers().stream().allMatch(isCheckcastToSubtype)) {
+ removeOrReplaceByDebugLocalWrite(checkCast, it, inValue, outValue);
+ return true;
+ }
+
+ TypeLatticeElement inTypeLattice = inValue.getTypeLattice();
+ // TODO(b/72693244): Soon, there won't be a value with imprecise type at this point.
+ if (!inTypeLattice.isPreciseType() && !inTypeLattice.isNull()) {
+ return false;
+ }
+
+ TypeLatticeElement outTypeLattice = outValue.getTypeLattice();
+ TypeLatticeElement castTypeLattice =
+ TypeLatticeElement.fromDexType(castType, inTypeLattice.isNullable(), appInfo);
+
+ assert inTypeLattice.nullElement().lessThanOrEqual(outTypeLattice.nullElement());
+
+ if (inTypeLattice.lessThanOrEqual(castTypeLattice, appInfo)) {
+ // 1) Trivial cast.
+ // A a = ...
+ // A a' = (A) a;
+ // 2) Up-cast: we already have finer type info.
+ // A < B
+ // A a = ...
+ // B b = (B) a;
+ assert inTypeLattice.lessThanOrEqual(outTypeLattice, appInfo);
+ removeOrReplaceByDebugLocalWrite(checkCast, it, inValue, outValue);
+ return true;
+ }
+
+ // Otherwise, keep the checkcast to preserve verification errors. E.g., down-cast:
+ // A < B < C
+ // c = ... // Even though we know c is of type A,
+ // a' = (B) c; // (this could be removed, since chained below.)
+ // a'' = (A) a'; // this should remain for runtime verification.
+ assert !inTypeLattice.isNull();
+ assert outTypeLattice.asNullable().equals(castTypeLattice.asNullable());
+ return false;
+ }
+
+ private boolean isTypeInaccessibleInCurrentContext(DexType type, DexEncodedMethod context) {
+ DexType baseType = type.toBaseType(appInfo.dexItemFactory);
+ DexClass clazz = definitionFor(baseType);
+ if (clazz == null) {
+ // Conservatively say yes.
+ return true;
+ }
+ ConstraintWithTarget classVisibility =
+ ConstraintWithTarget.deriveConstraint(
+ context.method.getHolder(), baseType, clazz.accessFlags, appInfo);
+ return classVisibility == ConstraintWithTarget.NEVER;
+ }
+
+ // Returns true if the given instance-of instruction was removed.
+ private boolean removeInstanceOfInstructionIfTrivial(
+ InstanceOf instanceOf, InstructionIterator it, IRCode code) {
+ // If the instance-of type is not accessible in the current context, we should not remove the
+ // instance-of instruction in order to preserve IllegalAccessError.
+ if (isTypeInaccessibleInCurrentContext(instanceOf.type(), code.method)) {
+ return false;
+ }
+
+ Value inValue = instanceOf.value();
+ TypeLatticeElement inType = inValue.getTypeLattice();
+ // TODO(b/72693244): Soon, there won't be a value with imprecise type at this point.
+ if (!inType.isPreciseType() && !inType.isNull()) {
+ return false;
+ }
+
+ TypeLatticeElement instanceOfType =
+ TypeLatticeElement.fromDexType(instanceOf.type(), inType.isNullable(), appInfo);
+
+ boolean result;
+ if (inType.isNull()) {
+ result = false;
+ } else if (inType.lessThanOrEqual(instanceOfType, appInfo) && !inType.isNullable()) {
+ result = true;
+ } else if (!inValue.isPhi()
+ && inValue.definition.isNewInstance()
+ && instanceOfType.strictlyLessThan(inType, appInfo)) {
+ result = false;
+ } else {
+ return false;
+ }
+ it.replaceCurrentInstruction(
+ new ConstNumber(
+ new Value(
+ code.valueNumberGenerator.next(),
+ TypeLatticeElement.INT,
+ instanceOf.outValue().getLocalInfo()),
+ result ? 1 : 0));
+ return true;
+ }
+
private void removeOrReplaceByDebugLocalWrite(
Instruction currentInstruction, InstructionIterator it, Value inValue, Value outValue) {
if (outValue.hasLocalInfo() && outValue.getLocalInfo() != inValue.getLocalInfo()) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
index e7b6ca8..e1f541f 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/Devirtualizer.java
@@ -103,7 +103,8 @@
//
// ~>
//
- // i <- check-cast I o // could be removed by {@link CodeRewriter#removeCasts}.
+ // i <- check-cast I o // could be removed by {@link
+ // CodeRewriter#removeTrivialCheckCastAndInstanceOfInstructions}.
// a <- check-cast A i // Otherwise ART verification error.
// (out <-) invoke-virtual a, ... A#foo
if (holderType != invoke.getInvokedMethod().getHolder()) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java
index 6999f9a..4d60f53 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/classinliner/ClassInliner.java
@@ -184,7 +184,7 @@
// If a method was inlined we may be able to remove check-cast instructions because we may
// have more information about the types of the arguments at the call site. This is
// particularly important for bridge methods.
- codeRewriter.removeCasts(code);
+ codeRewriter.removeTrivialCheckCastAndInstanceOfInstructions(code);
// If a method was inlined we may be able to prune additional branches.
codeRewriter.simplifyIf(code);
}
diff --git a/src/test/java/com/android/tools/r8/TestRunResult.java b/src/test/java/com/android/tools/r8/TestRunResult.java
index 462ca1f..fcaed49 100644
--- a/src/test/java/com/android/tools/r8/TestRunResult.java
+++ b/src/test/java/com/android/tools/r8/TestRunResult.java
@@ -32,9 +32,10 @@
return this;
}
- public void assertSuccessWithOutput(String expected) {
+ public TestRunResult assertSuccessWithOutput(String expected) {
assertSuccess();
assertEquals(errorMessage("Run std output incorrect."), expected, result.stdout);
+ return this;
}
public CodeInspector inspector() throws IOException, ExecutionException {
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/instanceofremoval/InstanceOfRemovalTest.java b/src/test/java/com/android/tools/r8/ir/optimize/instanceofremoval/InstanceOfRemovalTest.java
new file mode 100644
index 0000000..f078262
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/optimize/instanceofremoval/InstanceOfRemovalTest.java
@@ -0,0 +1,139 @@
+// Copyright (c) 2018, 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.instanceofremoval;
+
+import static org.junit.Assert.assertEquals;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
+import com.android.tools.r8.utils.codeinspector.InstructionSubject;
+import com.android.tools.r8.utils.codeinspector.MethodSubject;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Streams;
+import java.util.Iterator;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class InstanceOfRemovalTest extends TestBase {
+
+ static class A {}
+
+ static class B extends A {}
+
+ static class TestClass {
+
+ public static void main(String[] args) {
+ foo();
+ bar();
+ }
+
+ @NeverInline
+ private static void foo() {
+ System.out.println("A instanceof A: " + (getAForFoo() instanceof A));
+ System.out.println("A instanceof B: " + (getAForFoo() instanceof B));
+ System.out.println("B instanceof A: " + (getBForFoo() instanceof A));
+ System.out.println("B instanceof B: " + (getBForFoo() instanceof B));
+ System.out.println("null instanceof A: " + (getNullForFoo() instanceof A));
+ System.out.println("null instanceof B: " + (getNullForFoo() instanceof B));
+ }
+
+ public static A getAForFoo() {
+ return new A();
+ }
+
+ public static A getBForFoo() {
+ return new B();
+ }
+
+ public static A getNullForFoo() { return null; }
+
+ @NeverInline
+ private static void bar() {
+ System.out.println("A instanceof A: " + (getAForBar() instanceof A));
+ System.out.println("A instanceof B: " + (getAForBar() instanceof B));
+ System.out.println("B instanceof A: " + (getBForBar() instanceof A));
+ System.out.println("B instanceof B: " + (getBForBar() instanceof B));
+ System.out.println("null instanceof A: " + (getNullForBar(true) instanceof A));
+ System.out.print("null instanceof B: " + (getNullForBar(true) instanceof B));
+ }
+
+ @NeverInline
+ public static A getAForBar() {
+ return new A();
+ }
+
+ @NeverInline
+ public static A getBForBar() {
+ return new B();
+ }
+
+ @NeverInline
+ public static A getNullForBar(boolean returnNull) {
+ // Avoid `return null` since we will then use the fact that getNullForBar() always returns
+ // null at the call site.
+ return returnNull ? null : new A();
+ }
+ }
+
+ @Parameters(name = "Backend: {0}")
+ public static Backend[] data() {
+ return Backend.values();
+ }
+
+ private final Backend backend;
+
+ public InstanceOfRemovalTest(Backend backend) {
+ this.backend = backend;
+ }
+
+ @Test
+ public void test() throws Exception {
+ String expected =
+ StringUtils.joinLines(
+ "A instanceof A: true",
+ "A instanceof B: false",
+ "B instanceof A: true",
+ "B instanceof B: true",
+ "null instanceof A: false",
+ "null instanceof B: false",
+ "A instanceof A: true",
+ "A instanceof B: false",
+ "B instanceof A: true",
+ "B instanceof B: true",
+ "null instanceof A: false",
+ "null instanceof B: false");
+
+ testForJvm().addTestClasspath().run(TestClass.class).assertSuccessWithOutput(expected);
+
+ CodeInspector inspector =
+ testForR8(backend)
+ .addProgramClasses(A.class, B.class, TestClass.class)
+ .addKeepMainRule(TestClass.class)
+ .addKeepAllClassesRule()
+ .enableInliningAnnotations()
+ .run(TestClass.class)
+ .assertSuccessWithOutput(expected)
+ .inspector();
+
+ // With inlining we can prove that all instance-of checks succeed or fail.
+ MethodSubject fooMethodSubject =
+ inspector.clazz(TestClass.class).method("void", "foo", ImmutableList.of());
+ Iterator<InstructionSubject> fooInstructionIterator =
+ fooMethodSubject.iterateInstructions(InstructionSubject::isInstanceOf);
+ assertEquals(0, Streams.stream(fooInstructionIterator).count());
+
+ // Without inlining we cannot prove any of the instance-of checks to be trivial.
+ MethodSubject barMethodSubject =
+ inspector.clazz(TestClass.class).method("void", "bar", ImmutableList.of());
+ Iterator<InstructionSubject> barInstructionIterator =
+ barMethodSubject.iterateInstructions(InstructionSubject::isInstanceOf);
+ assertEquals(6, Streams.stream(barInstructionIterator).count());
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java
index 067280a..ce183bd 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/CfInstructionSubject.java
@@ -12,6 +12,7 @@
import com.android.tools.r8.cf.code.CfGoto;
import com.android.tools.r8.cf.code.CfIf;
import com.android.tools.r8.cf.code.CfIfCmp;
+import com.android.tools.r8.cf.code.CfInstanceOf;
import com.android.tools.r8.cf.code.CfInstruction;
import com.android.tools.r8.cf.code.CfInvoke;
import com.android.tools.r8.cf.code.CfInvokeDynamic;
@@ -164,6 +165,11 @@
}
@Override
+ public boolean isInstanceOf() {
+ return instruction instanceof CfInstanceOf;
+ }
+
+ @Override
public boolean isIf() {
return instruction instanceof CfIf || instruction instanceof CfIfCmp;
}
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java
index ca9ce6a..236eefe 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/DexInstructionSubject.java
@@ -28,6 +28,7 @@
import com.android.tools.r8.code.IgetObject;
import com.android.tools.r8.code.IgetShort;
import com.android.tools.r8.code.IgetWide;
+import com.android.tools.r8.code.InstanceOf;
import com.android.tools.r8.code.Instruction;
import com.android.tools.r8.code.InvokeDirect;
import com.android.tools.r8.code.InvokeDirectRange;
@@ -246,6 +247,11 @@
return isCheckCast() && ((CheckCast) instruction).getType().toString().equals(type);
}
+ @Override
+ public boolean isInstanceOf() {
+ return instruction instanceof InstanceOf;
+ }
+
public boolean isConst4() {
return instruction instanceof Const4;
}
diff --git a/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java b/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java
index 6890684..72abefa 100644
--- a/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java
+++ b/src/test/java/com/android/tools/r8/utils/codeinspector/InstructionSubject.java
@@ -60,6 +60,8 @@
boolean isCheckCast(String type);
+ boolean isInstanceOf();
+
boolean isIf(); // Also include CF/if_cmp* instructions.
boolean isPackedSwitch();
