Local Type Analysis.
Stolen from https://r8-review.googlesource.com/c/r8/+/4140
and then reinterpreted and fixed a couple nits.
Bug: 69964136
Change-Id: I84590d61325486d78312cfe4583391d283385c1f
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 e920751..d4a2ef9 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -174,6 +174,7 @@
public final DexType enumType = createType(enumDescriptor);
public final DexType annotationType = createType(annotationDescriptor);
public final DexType throwableType = createType(throwableDescriptor);
+ public final DexType classType = createType(classDescriptor);
public final DexType stringBuilderType = createType(stringBuilderDescriptor);
public final DexType stringBufferType = createType(stringBufferDescriptor);
diff --git a/src/main/java/com/android/tools/r8/graph/DexType.java b/src/main/java/com/android/tools/r8/graph/DexType.java
index a9689e5..9983f29 100644
--- a/src/main/java/com/android/tools/r8/graph/DexType.java
+++ b/src/main/java/com/android/tools/r8/graph/DexType.java
@@ -348,7 +348,7 @@
}
}
- private int getNumberOfLeadingSquareBrackets() {
+ public int getNumberOfLeadingSquareBrackets() {
int leadingSquareBrackets = 0;
while (descriptor.content[leadingSquareBrackets] == '[') {
leadingSquareBrackets++;
@@ -468,4 +468,51 @@
assert hierarchyLevel != UNKNOWN_LEVEL;
return type.directSubtypes.contains(this);
}
+
+ public DexType computeLeastUpperBound(AppInfoWithSubtyping appInfo, DexType other) {
+ DexType objectType = appInfo.dexItemFactory.objectType;
+ // If either one is interface,
+ // 1) one of them is a super type of the other
+ // 2) otherwise, the object type is the least upper bound.
+ if (isInterface() || other.isInterface()) {
+ if (isSubtypeOf(other, appInfo)) {
+ return other;
+ }
+ if (other.isSubtypeOf(this, appInfo)) {
+ return this;
+ }
+ return objectType;
+ }
+ // To make the logic simple, change the role if the other is lower than this.
+ if (other.hierarchyLevel < this.hierarchyLevel) {
+ return other.computeLeastUpperBound(appInfo, this);
+ }
+ DexClass dexClass;
+ // Make both of other and this in the same level.
+ while (other.hierarchyLevel > this.hierarchyLevel) {
+ dexClass = appInfo.definitionFor(other);
+ if (dexClass == null) {
+ return objectType;
+ }
+ other = dexClass.superType;
+ }
+ // At this point, they are at the same level.
+ // lub starts from this, and will move up; other starts from itself, and will move up, too.
+ // They move up in their own hierarchy tree, and will repeat the process until they meet.
+ // (It will stop at anytime when either one's definition is not found.)
+ DexType lub = this;
+ while (other != lub) {
+ dexClass = appInfo.definitionFor(other);
+ if (dexClass == null) {
+ return objectType;
+ }
+ other = dexClass.superType;
+ dexClass = appInfo.definitionFor(lub);
+ if (dexClass == null) {
+ return objectType;
+ }
+ lub = dexClass.superType;
+ }
+ return lub;
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ArrayTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ArrayTypeLatticeElement.java
new file mode 100644
index 0000000..c388ec5
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ArrayTypeLatticeElement.java
@@ -0,0 +1,65 @@
+// Copyright (c) 2017, 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.analysis.type;
+
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexType;
+import com.google.common.base.Strings;
+
+public class ArrayTypeLatticeElement extends TypeLatticeElement {
+ final DexType elementType;
+ final int nesting;
+
+ ArrayTypeLatticeElement(DexType elementType, int nesting, boolean isNullable) {
+ super(isNullable);
+ this.elementType = elementType;
+ this.nesting = nesting;
+ }
+
+ @Override
+ TypeLatticeElement asNullable() {
+ return isNullable() ? this : new ArrayTypeLatticeElement(elementType, nesting, true);
+ }
+
+ @Override
+ public TypeLatticeElement arrayGet(AppInfoWithSubtyping appInfo) {
+ if (nesting == 1) {
+ return fromDexType(appInfo, elementType, true);
+ }
+ return new ArrayTypeLatticeElement(elementType, nesting - 1, true);
+ }
+
+ @Override
+ public TypeLatticeElement checkCast(AppInfoWithSubtyping appInfo, DexType castType) {
+ if (castType.getNumberOfLeadingSquareBrackets() == nesting) {
+ DexType base = castType.toBaseType(appInfo.dexItemFactory);
+ if (elementType.isSubtypeOf(base, appInfo)) {
+ return this;
+ }
+ }
+ return super.checkCast(appInfo, castType);
+ }
+
+ @Override
+ public String toString() {
+ return isNullableString() + elementType.toString() + Strings.repeat("[]", nesting);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!super.equals(o)) {
+ return false;
+ }
+ ArrayTypeLatticeElement other = (ArrayTypeLatticeElement) o;
+ return nesting == other.nesting && elementType == other.elementType;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ result = 31 * result + elementType.hashCode();
+ result = 31 * result + nesting;
+ return result;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/Bottom.java b/src/main/java/com/android/tools/r8/ir/analysis/type/Bottom.java
new file mode 100644
index 0000000..3de4233
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/Bottom.java
@@ -0,0 +1,31 @@
+// Copyright (c) 2017, 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.analysis.type;
+
+public class Bottom extends TypeLatticeElement {
+ private static final Bottom INSTANCE = new Bottom();
+
+ private Bottom() {
+ super(true);
+ }
+
+ @Override
+ TypeLatticeElement asNullable() {
+ return this;
+ }
+
+ static Bottom getInstance() {
+ return INSTANCE;
+ }
+
+ @Override
+ boolean isBottom() {
+ return true;
+ }
+
+ @Override
+ public String toString() {
+ return "BOTTOM (empty)";
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeLatticeElement.java
new file mode 100644
index 0000000..2120669
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ClassTypeLatticeElement.java
@@ -0,0 +1,56 @@
+// Copyright (c) 2017, 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.analysis.type;
+
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexType;
+
+public class ClassTypeLatticeElement extends TypeLatticeElement {
+ final DexType classType;
+
+ ClassTypeLatticeElement(DexType classType, boolean isNullable) {
+ super(isNullable);
+ assert classType.isClassType();
+ this.classType = classType;
+ }
+
+ @Override
+ TypeLatticeElement asNullable() {
+ return isNullable() ? this : new ClassTypeLatticeElement(classType, true);
+ }
+
+ @Override
+ public TypeLatticeElement arrayGet(AppInfoWithSubtyping appInfo) {
+ return objectType(appInfo, true);
+ }
+
+ @Override
+ public TypeLatticeElement checkCast(AppInfoWithSubtyping appInfo, DexType castType) {
+ if (classType.isSubtypeOf(castType, appInfo)) {
+ return this;
+ }
+ return fromDexType(appInfo, castType, isNullable());
+ }
+
+ @Override
+ public String toString() {
+ return isNullableString() + classType.toString();
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!super.equals(o)) {
+ return false;
+ }
+ ClassTypeLatticeElement other = (ClassTypeLatticeElement) o;
+ return classType == other.classType;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ result = 31 * result + classType.hashCode();
+ return result;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/NullLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/NullLatticeElement.java
new file mode 100644
index 0000000..18ffad3
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/NullLatticeElement.java
@@ -0,0 +1,26 @@
+// Copyright (c) 2017, 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.analysis.type;
+
+public class NullLatticeElement extends TypeLatticeElement {
+ private static final NullLatticeElement INSTANCE = new NullLatticeElement();
+
+ private NullLatticeElement() {
+ super(true);
+ }
+
+ @Override
+ TypeLatticeElement asNullable() {
+ return this;
+ }
+
+ static NullLatticeElement getInstance() {
+ return INSTANCE;
+ }
+
+ @Override
+ public String toString() {
+ return "NULL";
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveArrayTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveArrayTypeLatticeElement.java
new file mode 100644
index 0000000..d92e891
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveArrayTypeLatticeElement.java
@@ -0,0 +1,50 @@
+// Copyright (c) 2017, 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.analysis.type;
+
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.google.common.base.Strings;
+
+public class PrimitiveArrayTypeLatticeElement extends TypeLatticeElement {
+ final int nesting;
+
+ PrimitiveArrayTypeLatticeElement(int nesting, boolean isNullable) {
+ super(isNullable);
+ this.nesting = nesting;
+ }
+
+ @Override
+ TypeLatticeElement asNullable() {
+ return isNullable() ? this : new PrimitiveArrayTypeLatticeElement(nesting, true);
+ }
+
+ @Override
+ public TypeLatticeElement arrayGet(AppInfoWithSubtyping appInfo) {
+ if (nesting == 1) {
+ return PrimitiveTypeLatticeElement.getInstance();
+ }
+ return new PrimitiveArrayTypeLatticeElement(nesting - 1, true);
+ }
+
+ @Override
+ public String toString() {
+ return isNullableString() + "PRIMITIVE" + Strings.repeat("[]", nesting);
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (!super.equals(o)) {
+ return false;
+ }
+ PrimitiveArrayTypeLatticeElement other = (PrimitiveArrayTypeLatticeElement) o;
+ return nesting == other.nesting;
+ }
+
+ @Override
+ public int hashCode() {
+ int result = super.hashCode();
+ result = 31 * result + nesting;
+ return result;
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveTypeLatticeElement.java
new file mode 100644
index 0000000..ea06862
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/PrimitiveTypeLatticeElement.java
@@ -0,0 +1,31 @@
+// Copyright (c) 2017, 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.analysis.type;
+
+/**
+ * A {@link TypeLatticeElement} that represents all primitive types, such as int, long, etc.
+ * All primitives are aggregated, since the main use of this type analysis is to help
+ * better understanding of the type of object references.
+ */
+public class PrimitiveTypeLatticeElement extends TypeLatticeElement {
+ private static final PrimitiveTypeLatticeElement INSTANCE = new PrimitiveTypeLatticeElement();
+
+ private PrimitiveTypeLatticeElement() {
+ super(false);
+ }
+
+ @Override
+ TypeLatticeElement asNullable() {
+ return Top.getInstance();
+ }
+
+ public static PrimitiveTypeLatticeElement getInstance() {
+ return INSTANCE;
+ }
+
+ @Override
+ public String toString() {
+ return "PRIMITIVE";
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/Top.java b/src/main/java/com/android/tools/r8/ir/analysis/type/Top.java
new file mode 100644
index 0000000..6b4745d
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/Top.java
@@ -0,0 +1,31 @@
+// Copyright (c) 2017, 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.analysis.type;
+
+public class Top extends TypeLatticeElement {
+ private static final Top INSTANCE = new Top();
+
+ private Top() {
+ super(true);
+ }
+
+ @Override
+ TypeLatticeElement asNullable() {
+ return this;
+ }
+
+ static Top getInstance() {
+ return INSTANCE;
+ }
+
+ @Override
+ boolean isTop() {
+ return true;
+ }
+
+ @Override
+ public String toString() {
+ return "TOP (everything)";
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
new file mode 100644
index 0000000..91d53a2
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeAnalysis.java
@@ -0,0 +1,138 @@
+// Copyright (c) 2017, 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.analysis.type;
+
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.Argument;
+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.Phi;
+import com.android.tools.r8.ir.code.Value;
+import com.google.common.annotations.VisibleForTesting;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+
+import java.util.ArrayDeque;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.BiFunction;
+
+public class TypeAnalysis {
+ private final AppInfoWithSubtyping appInfo;
+ private final DexEncodedMethod encodedMethod;
+ private final IRCode code;
+
+ private final Deque<BasicBlock> worklist = new ArrayDeque<>();
+ private final Map<Value, TypeLatticeElement> typeMap = Maps.newHashMap();
+ private final Map<Value, Set<BasicBlock>> users = Maps.newHashMap();
+
+ public TypeAnalysis(AppInfoWithSubtyping appInfo, DexEncodedMethod encodedMethod, IRCode code) {
+ this.appInfo = appInfo;
+ this.encodedMethod = encodedMethod;
+ this.code = code;
+ }
+
+ public void run() {
+ BasicBlock[] basicBlocks = code.topologicallySortedBlocks();
+ if (basicBlocks.length <= 0) {
+ return;
+ }
+ worklist.addAll(Arrays.asList(basicBlocks));
+ while (!worklist.isEmpty()) {
+ processBasicBlock(worklist.poll());
+ }
+ }
+
+ private void addToWorklist(BasicBlock block) {
+ if (!worklist.contains(block)) {
+ worklist.add(block);
+ }
+ }
+
+ private void processBasicBlock(BasicBlock block) {
+ int argumentsSeen = encodedMethod.accessFlags.isStatic() ? 0 : -1;
+ for (Instruction instruction : block.getInstructions()) {
+ TypeLatticeElement derived = Bottom.getInstance();
+ Value outValue = instruction.outValue();
+ // Argument, a quasi instruction, needs to be handled specially:
+ // 1) We can derive its type from the method signature; and
+ // 2) It does not have an out value, so we can skip the env updating.
+ if (instruction instanceof Argument) {
+ if (argumentsSeen < 0) {
+ derived = TypeLatticeElement.fromDexType(appInfo, encodedMethod.method.holder, false);
+ } else {
+ DexType argType = encodedMethod.method.proto.parameters.values[argumentsSeen];
+ derived = TypeLatticeElement.fromDexType(appInfo, argType, true);
+ }
+ argumentsSeen++;
+ } else {
+ // Register this block as a user for in values to revisit this if in values are updated.
+ instruction.inValues()
+ .forEach(v -> registerAsUserOfValue(v, block, Sets.newIdentityHashSet()));
+ if (outValue != null) {
+ derived = instruction.evaluate(appInfo, this::getLatticeElement);
+ }
+ }
+ if (outValue != null) {
+ TypeLatticeElement current = getLatticeElement(outValue);
+ if (!current.equals(derived)) {
+ updateTypeOfValue(outValue, derived);
+ }
+ }
+ }
+ }
+
+ private void registerAsUserOfValue(Value value, BasicBlock block, Set<Value> seenPhis) {
+ if (value.isPhi() && seenPhis.add(value)) {
+ for (Value operand : value.asPhi().getOperands()) {
+ registerAsUserOfValue(operand, block, seenPhis);
+ }
+ } else {
+ users.computeIfAbsent(value, k -> Sets.newIdentityHashSet()).add(block);
+ }
+ }
+
+ private void updateTypeOfValue(Value value, TypeLatticeElement type) {
+ setLatticeElement(value, type);
+ // Revisit the blocks that use the value whose type binding has just been updated.
+ users.getOrDefault(value, Collections.emptySet()).forEach(this::addToWorklist);
+ // Propagate the type change to phi users if any.
+ for (Phi phi : value.uniquePhiUsers()) {
+ TypeLatticeElement phiType = computePhiType(phi);
+ if (!getLatticeElement(phi).equals(phiType)) {
+ updateTypeOfValue(phi, phiType);
+ }
+ }
+ }
+
+ private TypeLatticeElement computePhiType(Phi phi) {
+ // Type of phi(v1, v2, ..., vn) is the least upper bound of all those n operands.
+ BiFunction<TypeLatticeElement, TypeLatticeElement, TypeLatticeElement> joiner =
+ TypeLatticeElement.joiner(appInfo);
+ return phi.getOperands().stream().reduce(
+ Bottom.getInstance(),
+ (acc, value) -> joiner.apply(acc, getLatticeElement(value)),
+ joiner::apply);
+ }
+
+ private void setLatticeElement(Value value, TypeLatticeElement type) {
+ typeMap.put(value, type);
+ }
+
+ TypeLatticeElement getLatticeElement(Value value) {
+ return typeMap.getOrDefault(value, Bottom.getInstance());
+ }
+
+ @VisibleForTesting
+ void forEach(BiConsumer<Value, TypeLatticeElement> consumer) {
+ typeMap.forEach(consumer);
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/TypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeLatticeElement.java
new file mode 100644
index 0000000..3d5738f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/TypeLatticeElement.java
@@ -0,0 +1,214 @@
+// Copyright (c) 2017, 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.analysis.type;
+
+import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.Value;
+import java.util.function.BiFunction;
+
+/**
+ * The base abstraction of lattice elements for local type analysis.
+ */
+abstract public class TypeLatticeElement {
+ private final boolean isNullable;
+
+ TypeLatticeElement(boolean isNullable) {
+ this.isNullable = isNullable;
+ }
+
+ boolean isNullable() {
+ return isNullable;
+ }
+
+ /**
+ * Defines how to join with null.
+ *
+ * @return {@link TypeLatticeElement} a result of joining with null.
+ */
+ abstract TypeLatticeElement asNullable();
+
+ String isNullableString() {
+ return isNullable() ? "" : "@NonNull ";
+ }
+
+ /**
+ * Computes the least upper bound of the current and the other elements.
+ *
+ * @param appInfo {@link AppInfoWithSubtyping} that contains subtype info.
+ * @param l1 {@link TypeLatticeElement} to join.
+ * @param l2 {@link TypeLatticeElement} to join.
+ * @return {@link TypeLatticeElement}, a least upper bound of {@param l1} and {@param l2}.
+ */
+ static TypeLatticeElement join(
+ AppInfoWithSubtyping appInfo, TypeLatticeElement l1, TypeLatticeElement l2) {
+ if (l1.isBottom()) {
+ return l2;
+ }
+ if (l2.isBottom()) {
+ return l1;
+ }
+ if (l1.isTop() || l2.isTop()) {
+ return Top.getInstance();
+ }
+ if (l1 instanceof NullLatticeElement) {
+ return l2.asNullable();
+ }
+ if (l2 instanceof NullLatticeElement) {
+ return l1.asNullable();
+ }
+ if (l1 instanceof PrimitiveTypeLatticeElement) {
+ return l2 instanceof PrimitiveTypeLatticeElement ? l1 : Top.getInstance();
+ }
+ if (l2 instanceof PrimitiveTypeLatticeElement) {
+ // !(l1 instanceof PrimitiveTypeLatticeElement)
+ return Top.getInstance();
+ }
+ // From now on, l1 and l2 are either PrimitiveArrayType, ArrayType, or ClassType.
+ boolean isNullable = l1.isNullable() || l2.isNullable();
+ if (l1.getClass() != l2.getClass()) {
+ return objectType(appInfo, isNullable);
+ }
+ // From now on, l1.getClass() == l2.getClass()
+ if (l1 instanceof PrimitiveArrayTypeLatticeElement) {
+ PrimitiveArrayTypeLatticeElement a1 = (PrimitiveArrayTypeLatticeElement) l1;
+ PrimitiveArrayTypeLatticeElement a2 = (PrimitiveArrayTypeLatticeElement) l2;
+ if (a1.nesting != a2.nesting) {
+ int min = Math.min(a1.nesting, a2.nesting);
+ if (min > 1) {
+ return objectArrayType(appInfo, min - 1, isNullable);
+ } else {
+ return objectType(appInfo, isNullable);
+ }
+ } else {
+ return l1;
+ }
+ }
+ if (l1 instanceof ArrayTypeLatticeElement) {
+ ArrayTypeLatticeElement a1 = (ArrayTypeLatticeElement) l1;
+ ArrayTypeLatticeElement a2 = (ArrayTypeLatticeElement) l2;
+ if (a1.nesting != a2.nesting) {
+ int min = Math.min(a1.nesting, a2.nesting);
+ return objectArrayType(appInfo, min, isNullable);
+ } else {
+ // Same nesting, same base type.
+ if (a1.elementType == a2.elementType) {
+ return a1.isNullable() ? a1 : a2;
+ } else if (a1.elementType.isClassType() && a2.elementType.isClassType()) {
+ // For different class element types, compute the least upper bound of element types.
+ DexType lub = a1.elementType.computeLeastUpperBound(appInfo, a2.elementType);
+ return new ArrayTypeLatticeElement(lub, a1.nesting, isNullable);
+ }
+ // Otherwise, fall through to the end, where TOP will be returned.
+ }
+ }
+ if (l1 instanceof ClassTypeLatticeElement) {
+ ClassTypeLatticeElement c1 = (ClassTypeLatticeElement) l1;
+ ClassTypeLatticeElement c2 = (ClassTypeLatticeElement) l2;
+ if (c1.classType == c2.classType) {
+ return c1.isNullable() ? c1 : c2;
+ } else {
+ DexType lub = c1.classType.computeLeastUpperBound(appInfo, c2.classType);
+ return new ClassTypeLatticeElement(lub, isNullable);
+ }
+ }
+ throw new Unreachable("unless a new type lattice is introduced.");
+ }
+
+ static BiFunction<TypeLatticeElement, TypeLatticeElement, TypeLatticeElement> joiner(
+ AppInfoWithSubtyping appInfo) {
+ return (l1, l2) -> join(appInfo, l1, l2);
+ }
+
+ /**
+ * Represents a type that can be everything.
+ *
+ * @return true if the corresponding {@link Value} could be any kinds.
+ */
+ boolean isTop() {
+ return false;
+ }
+
+ /**
+ * Represents an empty type.
+ *
+ * @return true if the type of corresponding {@link Value} is not determined yet.
+ */
+ boolean isBottom() {
+ return false;
+ }
+
+ static ClassTypeLatticeElement objectType(AppInfo appInfo, boolean isNullable) {
+ return new ClassTypeLatticeElement(appInfo.dexItemFactory.objectType, isNullable);
+ }
+
+ static ArrayTypeLatticeElement objectArrayType(AppInfo appInfo, int nesting, boolean isNullable) {
+ return new ArrayTypeLatticeElement(appInfo.dexItemFactory.objectType, nesting, isNullable);
+ }
+
+ public static TypeLatticeElement fromDexType(
+ AppInfoWithSubtyping appInfo, DexType type, boolean isNullable) {
+ if (type.isPrimitiveType()) {
+ return PrimitiveTypeLatticeElement.getInstance();
+ }
+ if (type.isPrimitiveArrayType()) {
+ return new PrimitiveArrayTypeLatticeElement(
+ type.getNumberOfLeadingSquareBrackets(), isNullable);
+ }
+ if (type.isClassType()) {
+ return new ClassTypeLatticeElement(type, isNullable);
+ }
+ assert type.isArrayType();
+ return new ArrayTypeLatticeElement(
+ type.toBaseType(appInfo.dexItemFactory),
+ type.getNumberOfLeadingSquareBrackets(),
+ isNullable);
+ }
+
+ public static TypeLatticeElement newArray(
+ AppInfoWithSubtyping appInfo, DexType arrayType, boolean isNullable) {
+ DexType baseType = arrayType.toBaseType(appInfo.dexItemFactory);
+ assert baseType != arrayType;
+ int nesting = arrayType.getNumberOfLeadingSquareBrackets();
+ if (baseType.isClassType()) {
+ return new ArrayTypeLatticeElement(baseType, nesting, isNullable);
+ } else {
+ return newPrimitiveArray(nesting, isNullable);
+ }
+ }
+
+ public static TypeLatticeElement newPrimitiveArray(int nesting, boolean isNullable) {
+ return new PrimitiveArrayTypeLatticeElement(nesting, isNullable);
+ }
+
+ public TypeLatticeElement arrayGet(AppInfoWithSubtyping appInfo) {
+ return Top.getInstance();
+ }
+
+ public TypeLatticeElement checkCast(AppInfoWithSubtyping appInfo, DexType castType) {
+ return fromDexType(appInfo, castType, isNullable());
+ }
+
+ @Override
+ abstract public String toString();
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o == null || o.getClass() != this.getClass()) {
+ return false;
+ }
+ TypeLatticeElement otherElement = (TypeLatticeElement) o;
+ return otherElement.isNullable() == isNullable;
+ }
+
+ @Override
+ public int hashCode() {
+ return isNullable ? 1 : 0;
+ }
+}
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 b226b70..2380ea2 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
@@ -16,11 +16,13 @@
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
import com.android.tools.r8.ir.regalloc.RegisterAllocator;
import java.util.Arrays;
+import java.util.function.Function;
public class ArrayGet extends Instruction {
@@ -142,4 +144,10 @@
public void buildCf(CfBuilder builder) {
builder.add(new CfArrayLoad(type));
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return getLatticeElement.apply(array()).arrayGet(appInfo);
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java b/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
index 742ccb5..f7689ab 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ArrayLength.java
@@ -9,10 +9,13 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
import com.android.tools.r8.ir.regalloc.RegisterAllocator;
+import java.util.function.Function;
public class ArrayLength extends Instruction {
@@ -101,4 +104,10 @@
public void buildCf(CfBuilder builder) {
builder.add(new CfArrayLength());
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return PrimitiveTypeLatticeElement.getInstance();
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Binop.java b/src/main/java/com/android/tools/r8/ir/code/Binop.java
index 8473f71..55b3ba5 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Binop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Binop.java
@@ -11,9 +11,12 @@
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
import com.android.tools.r8.ir.regalloc.RegisterAllocator;
+import java.util.function.Function;
public abstract class Binop extends Instruction {
@@ -132,4 +135,10 @@
public void buildCf(CfBuilder builder) {
builder.add(new CfBinop(getCfOpcode()));
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return PrimitiveTypeLatticeElement.getInstance();
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/CheckCast.java b/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
index 90723b2..f0e4d44 100644
--- a/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
+++ b/src/main/java/com/android/tools/r8/ir/code/CheckCast.java
@@ -9,8 +9,10 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
public class CheckCast extends Instruction {
@@ -101,4 +103,10 @@
public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
return Constraint.classIsVisible(invocationContext, type, info);
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return getLatticeElement.apply(object()).checkCast(appInfo, type);
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstClass.java b/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
index bab1c2f..16239e2 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstClass.java
@@ -7,9 +7,11 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
import com.android.tools.r8.utils.InternalOptions;
+import java.util.function.Function;
public class ConstClass extends ConstInstruction {
@@ -94,4 +96,10 @@
public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
return Constraint.classIsVisible(invocationContext, clazz, info);
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return TypeLatticeElement.fromDexType(appInfo, appInfo.dexItemFactory.classType, false);
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java b/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
index f990d90..1c6161b 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstNumber.java
@@ -16,10 +16,13 @@
import com.android.tools.r8.code.ConstWide32;
import com.android.tools.r8.code.ConstWideHigh16;
import com.android.tools.r8.dex.Constants;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.ir.analysis.constant.Bottom;
import com.android.tools.r8.ir.analysis.constant.ConstLatticeElement;
import com.android.tools.r8.ir.analysis.constant.LatticeElement;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.utils.NumberUtils;
@@ -263,4 +266,10 @@
}
return new ConstLatticeElement(this);
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return PrimitiveTypeLatticeElement.getInstance();
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/ConstString.java b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
index a3a730d..9ff7fe4 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ConstString.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ConstString.java
@@ -7,12 +7,15 @@
import com.android.tools.r8.cf.TypeVerificationHelper;
import com.android.tools.r8.cf.code.CfConstString;
import com.android.tools.r8.dex.Constants;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexString;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.utils.InternalOptions;
import java.io.UTFDataFormatException;
+import java.util.function.Function;
public class ConstString extends ConstInstruction {
@@ -120,4 +123,10 @@
public DexType computeVerificationType(TypeVerificationHelper helper) {
return helper.getFactory().stringType;
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return TypeLatticeElement.fromDexType(appInfo, appInfo.dexItemFactory.stringType, false);
+ }
}
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 e1bc063..ddf2969 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
@@ -14,10 +14,13 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexEncodedField;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.DexBuilder;
+import java.util.function.Function;
public class InstanceGet extends FieldInstruction {
@@ -121,4 +124,10 @@
public String toString() {
return super.toString() + "; field: " + field.toSourceString();
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return TypeLatticeElement.fromDexType(appInfo, field.type, true);
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java b/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
index 995a35e..0985ad1 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InstanceOf.java
@@ -7,8 +7,11 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
public class InstanceOf extends Instruction {
@@ -77,4 +80,10 @@
public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
return Constraint.classIsVisible(invocationContext, type, info);
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return PrimitiveTypeLatticeElement.getInstance();
+ }
}
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 70ffe8a..cf5190a 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
@@ -13,6 +13,7 @@
import com.android.tools.r8.ir.analysis.constant.Bottom;
import com.android.tools.r8.ir.analysis.constant.ConstRangeLatticeElement;
import com.android.tools.r8.ir.analysis.constant.LatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
@@ -1018,4 +1019,10 @@
}
return Bottom.getInstance();
}
+
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ assert outValue == null;
+ throw new Unreachable("Instructions without outValue have no type.");
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
index 9e1494e..17b7b64 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMethod.java
@@ -5,16 +5,19 @@
import com.android.tools.r8.cf.LoadStoreHelper;
import com.android.tools.r8.cf.TypeVerificationHelper;
+import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexMethod;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
import com.android.tools.r8.ir.optimize.Inliner.InlineAction;
import com.android.tools.r8.ir.optimize.InliningOracle;
import java.util.Collection;
import java.util.List;
+import java.util.function.Function;
public abstract class InvokeMethod extends Invoke {
@@ -144,4 +147,14 @@
public DexType computeVerificationType(TypeVerificationHelper helper) {
return getInvokedMethod().proto.returnType;
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ DexType returnType = method.proto.returnType;
+ if (returnType.isVoidType()) {
+ throw new Unreachable("void methods have no type.");
+ }
+ return TypeLatticeElement.fromDexType(appInfo, returnType, true);
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java b/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
index 440574a..f075633 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeNewArray.java
@@ -8,9 +8,11 @@
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexEncodedMethod;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
import java.util.List;
+import java.util.function.Function;
public class InvokeNewArray extends Invoke {
@@ -104,4 +106,10 @@
public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
return Constraint.classIsVisible(invocationContext, type, info);
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return TypeLatticeElement.newArray(appInfo, type, false);
+ }
}
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 9d27eab..4187cab 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
@@ -7,8 +7,10 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
public class Move extends Instruction {
@@ -84,4 +86,10 @@
public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
return Constraint.ALWAYS;
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return getLatticeElement.apply(src());
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/MoveException.java b/src/main/java/com/android/tools/r8/ir/code/MoveException.java
index 8bfdcd2..dda7a30 100644
--- a/src/main/java/com/android/tools/r8/ir/code/MoveException.java
+++ b/src/main/java/com/android/tools/r8/ir/code/MoveException.java
@@ -8,6 +8,7 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
@@ -15,6 +16,7 @@
import java.util.HashSet;
import java.util.List;
import java.util.Set;
+import java.util.function.Function;
public class MoveException extends Instruction {
@@ -105,4 +107,10 @@
}
return helper.join(exceptionTypes);
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return TypeLatticeElement.fromDexType(appInfo, appInfo.dexItemFactory.throwableType, false);
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
index 8d32ca9..2c15de7 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewArrayEmpty.java
@@ -10,9 +10,11 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
public class NewArrayEmpty extends Instruction {
@@ -101,4 +103,10 @@
assert type.isArrayType();
builder.add(new CfNewArray(type));
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return TypeLatticeElement.newArray(appInfo, type, false);
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java b/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
index 765251f..4b53afb 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewArrayFilledData.java
@@ -8,10 +8,12 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
import com.android.tools.r8.utils.InternalOptions;
import java.util.Arrays;
+import java.util.function.Function;
public class NewArrayFilledData extends Instruction {
@@ -102,4 +104,10 @@
public Constraint inliningConstraint(AppInfoWithSubtyping info, DexType invocationContext) {
return Constraint.ALWAYS;
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return TypeLatticeElement.newPrimitiveArray(1, false);
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
index b00eef0..6b45990 100644
--- a/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
+++ b/src/main/java/com/android/tools/r8/ir/code/NewInstance.java
@@ -9,9 +9,11 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
public class NewInstance extends Instruction {
@@ -95,4 +97,10 @@
public DexType computeVerificationType(TypeVerificationHelper helper) {
return clazz;
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return TypeLatticeElement.fromDexType(appInfo, clazz, false);
+ }
}
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 32871b3..acb8977 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
@@ -16,11 +16,14 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexEncodedField;
import com.android.tools.r8.graph.DexField;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.conversion.DexBuilder;
+import java.util.function.Function;
public class StaticGet extends FieldInstruction {
@@ -135,4 +138,10 @@
public DexType computeVerificationType(TypeVerificationHelper helper) {
return field.type;
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return TypeLatticeElement.fromDexType(appInfo, field.type, true);
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/Unop.java b/src/main/java/com/android/tools/r8/ir/code/Unop.java
index f161635..f1189b9 100644
--- a/src/main/java/com/android/tools/r8/ir/code/Unop.java
+++ b/src/main/java/com/android/tools/r8/ir/code/Unop.java
@@ -8,8 +8,11 @@
import com.android.tools.r8.dex.Constants;
import com.android.tools.r8.graph.AppInfoWithSubtyping;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.PrimitiveTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.conversion.CfBuilder;
import com.android.tools.r8.ir.optimize.Inliner.Constraint;
+import java.util.function.Function;
abstract public class Unop extends Instruction {
@@ -62,4 +65,10 @@
public void buildCf(CfBuilder builder) {
builder.add(new CfUnop(getCfOpcode()));
}
+
+ @Override
+ public TypeLatticeElement evaluate(
+ AppInfoWithSubtyping appInfo, Function<Value, TypeLatticeElement> getLatticeElement) {
+ return PrimitiveTypeLatticeElement.getInstance();
+ }
}
diff --git a/src/test/java/com/android/tools/r8/ToolHelper.java b/src/test/java/com/android/tools/r8/ToolHelper.java
index a6ab7e9..cf5e451 100644
--- a/src/test/java/com/android/tools/r8/ToolHelper.java
+++ b/src/test/java/com/android/tools/r8/ToolHelper.java
@@ -72,6 +72,7 @@
public static final String EXAMPLES_ANDROID_O_BUILD_DIR = TESTS_BUILD_DIR + "examplesAndroidO/";
public static final String EXAMPLES_ANDROID_P_BUILD_DIR = TESTS_BUILD_DIR + "examplesAndroidP/";
public static final String EXAMPLES_JAVA9_BUILD_DIR = TESTS_BUILD_DIR + "examplesJava9/";
+ public static final String SMALI_DIR = TESTS_DIR + "smali/";
public static final String SMALI_BUILD_DIR = TESTS_BUILD_DIR + "smali/";
public static final String LINE_SEPARATOR = StringUtils.LINE_SEPARATOR;
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java
new file mode 100644
index 0000000..da8772f
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/NullabilityTest.java
@@ -0,0 +1,257 @@
+// Copyright (c) 2017, 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.analysis.type;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.dex.ApplicationReader;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexApplication;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.smali.SmaliBuilder;
+import com.android.tools.r8.smali.SmaliBuilder.MethodSignature;
+import com.android.tools.r8.smali.SmaliTestBase;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.DexInspector;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.Timing;
+import com.google.common.collect.ImmutableList;
+import java.util.function.BiConsumer;
+import org.junit.Test;
+
+public class NullabilityTest extends SmaliTestBase {
+ private final String CLASS_NAME = "Example";
+ private static final InternalOptions TEST_OPTIONS = new InternalOptions();
+
+ private void buildAndTest(
+ SmaliBuilder builder,
+ MethodSignature signature,
+ BiConsumer<AppInfoWithSubtyping, TypeAnalysis> inspector)
+ throws Exception {
+ AndroidApp app = builder.build();
+ DexApplication dexApplication =
+ new ApplicationReader(app, TEST_OPTIONS, new Timing("NullabilityTest.appReader"))
+ .read().toDirect();
+ AppInfoWithSubtyping appInfo = new AppInfoWithSubtyping(dexApplication);
+ DexInspector dexInspector = new DexInspector(appInfo.app);
+ DexEncodedMethod foo = dexInspector.clazz(CLASS_NAME).method(signature).getMethod();
+ IRCode irCode = foo.buildIR(TEST_OPTIONS);
+ TypeAnalysis analysis = new TypeAnalysis(appInfo, foo, irCode);
+ analysis.run();
+ inspector.accept(appInfo, analysis);
+ }
+
+ @Test
+ public void nonNullAfterSafeInvokes() throws Exception {
+ SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+ MethodSignature signature =
+ builder.addInstanceMethod("void", "foo", ImmutableList.of("java.lang.String"), 1,
+ "invoke-virtual {p1}, Ljava/lang/String;->toString()Ljava/lang/String;",
+ // Successful invocation above means p1 is not null.
+ "if-nez p1, :not_null",
+ "new-instance v0, Ljava/lang/AssertionError;",
+ "throw v0",
+ ":not_null",
+ "return-void"
+ );
+ buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+ typeAnalysis.forEach((v, l) -> {
+ assertTrue(l instanceof ClassTypeLatticeElement);
+ ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+ if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+ // TODO(b/70795205): Can be refined by using control-flow info.
+ // parameter
+ assertTrue(lattice.isNullable());
+ } else {
+ // holder and newly created assertion error.
+ assertFalse(lattice.isNullable());
+ }
+ });
+ });
+ }
+
+ @Test
+ public void stillNullAfterExceptionCatch_invoke() throws Exception {
+ SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+ MethodSignature signature =
+ builder.addInstanceMethod("void", "foo", ImmutableList.of("java.lang.String"), 1,
+ ":try_start",
+ "invoke-virtual {p1}, Ljava/lang/String;->toString()Ljava/lang/String;",
+ "if-nez p1, :return",
+ "new-instance v0, Ljava/lang/AssertionError;",
+ "throw v0",
+ ":try_end",
+ ".catch Ljava/lang/Throwable; {:try_start .. :try_end} :return",
+ ":return",
+ // p1 could be still null at the outside of try-catch.
+ "invoke-virtual {p1}, Ljava/lang/String;->hashCode()I",
+ "return-void"
+ );
+ buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+ typeAnalysis.forEach((v, l) -> {
+ assertTrue(l instanceof ClassTypeLatticeElement);
+ ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+ if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+ // parameter
+ assertTrue(lattice.isNullable());
+ } else {
+ // holder and newly created assertion error.
+ assertFalse(lattice.isNullable());
+ }
+ });
+ });
+ }
+
+ @Test
+ public void nonNullAfterSafeArrayAccess() throws Exception {
+ SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+ MethodSignature signature =
+ builder.addInstanceMethod("void", "foo", ImmutableList.of("java.lang.String[]"), 1,
+ "const/4 v0, 0",
+ "aget-object v0, p1, v0",
+ // Successful array access above means p1 is not null.
+ "if-nez p1, :not_null",
+ "new-instance v0, Ljava/lang/AssertionError;",
+ "throw v0",
+ ":not_null",
+ "return-void"
+ );
+ buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+ typeAnalysis.forEach((v, l) -> {
+ if (l instanceof ArrayTypeLatticeElement) {
+ ArrayTypeLatticeElement lattice = (ArrayTypeLatticeElement) l;
+ assertEquals(appInfo.dexItemFactory.stringType, lattice.elementType);
+ // TODO(b/70795205): Can be refined by using control-flow info.
+ assertTrue(l.isNullable());
+ }
+ if (l instanceof ClassTypeLatticeElement) {
+ ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+ if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+ // An element inside a non-null array could be null.
+ assertTrue(lattice.isNullable());
+ } else {
+ // holder and newly created assertion error.
+ assertFalse(lattice.isNullable());
+ }
+ }
+ });
+ });
+ }
+
+ @Test
+ public void stillNullAfterExceptionCatch_aget() throws Exception {
+ SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+ MethodSignature signature =
+ builder.addInstanceMethod("void", "foo", ImmutableList.of("java.lang.String[]"), 1,
+ ":try_start",
+ "const/4 v0, 0",
+ "aget-object v0, p1, v0",
+ "if-nez p1, :return",
+ "new-instance v0, Ljava/lang/AssertionError;",
+ "throw v0",
+ ":try_end",
+ ".catch Ljava/lang/Throwable; {:try_start .. :try_end} :return",
+ ":return",
+ // p1 could be still null at the outside of try-catch.
+ "invoke-virtual {p1}, [Ljava/lang/String;->hashCode()I",
+ "return-void"
+ );
+ buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+ typeAnalysis.forEach((v, l) -> {
+ if (l instanceof ArrayTypeLatticeElement) {
+ ArrayTypeLatticeElement lattice = (ArrayTypeLatticeElement) l;
+ assertEquals(appInfo.dexItemFactory.stringType, lattice.elementType);
+ assertTrue(l.isNullable());
+ }
+ if (l instanceof ClassTypeLatticeElement) {
+ ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+ if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+ // An element inside a non-null array could be null.
+ assertTrue(lattice.isNullable());
+ } else {
+ // holder and newly created assertion error.
+ assertFalse(lattice.isNullable());
+ }
+ }
+ });
+ });
+ }
+
+ @Test
+ public void nonNullAfterSafeFieldAccess() throws Exception {
+ SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+ MethodSignature signature =
+ builder.addInstanceMethod("void", "foo", ImmutableList.of("Test"), 1,
+ "iget-object v0, p1, LTest;->bar:Ljava/lang/String;",
+ // Successful field access above means p1 is not null.
+ "if-nez p1, :not_null",
+ "new-instance v0, Ljava/lang/AssertionError;",
+ "throw v0",
+ ":not_null",
+ "return-void"
+ );
+ builder.addClass("Test");
+ builder.addInstanceField("bar", "Ljava/lang/String;");
+ buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+ DexType testType = appInfo.dexItemFactory.createType("LTest;");
+ typeAnalysis.forEach((v, l) -> {
+ assertTrue(l instanceof ClassTypeLatticeElement);
+ ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+ if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+ // instance may not be initialized.
+ assertTrue(lattice.isNullable());
+ } else if (lattice.classType.equals(testType)) {
+ // TODO(b/70795205): Can be refined by using control-flow info.
+ // parameter
+ assertTrue(lattice.isNullable());
+ } else {
+ // holder and newly created assertion error.
+ assertFalse(lattice.isNullable());
+ }
+ });
+ });
+ }
+
+ @Test
+ public void stillNullAfterExceptionCatch_iget() throws Exception {
+ SmaliBuilder builder = new SmaliBuilder(CLASS_NAME);
+ MethodSignature signature =
+ builder.addInstanceMethod("void", "foo", ImmutableList.of("Test"), 1,
+ ":try_start",
+ "iget-object v0, p1, LTest;->bar:Ljava/lang/String;",
+ "if-nez p1, :return",
+ "new-instance v0, Ljava/lang/AssertionError;",
+ "throw v0",
+ ":try_end",
+ ".catch Ljava/lang/Throwable; {:try_start .. :try_end} :return",
+ ":return",
+ // p1 could be still null at the outside of try-catch.
+ "invoke-virtual {p1}, LTest;->hashCode()I",
+ "return-void"
+ );
+ builder.addClass("Test");
+ builder.addInstanceField("bar", "Ljava/lang/String;");
+ buildAndTest(builder, signature, (appInfo, typeAnalysis) -> {
+ DexType testType = appInfo.dexItemFactory.createType("LTest;");
+ typeAnalysis.forEach((v, l) -> {
+ assertTrue(l instanceof ClassTypeLatticeElement);
+ ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+ if (lattice.classType.equals(appInfo.dexItemFactory.stringType)) {
+ // instance may not be initialized.
+ assertTrue(lattice.isNullable());
+ } else if (lattice.classType.equals(testType)) {
+ // parameter
+ assertTrue(lattice.isNullable());
+ } else {
+ // holder and newly created assertion error.
+ assertFalse(lattice.isNullable());
+ }
+ });
+ });
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTest.java
new file mode 100644
index 0000000..9bd8af6
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTest.java
@@ -0,0 +1,345 @@
+// Copyright (c) 2017, 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.analysis.type;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.fail;
+
+import com.android.tools.r8.ApiLevelException;
+import com.android.tools.r8.ToolHelper;
+import com.android.tools.r8.dex.ApplicationReader;
+import com.android.tools.r8.graph.AppInfoWithSubtyping;
+import com.android.tools.r8.graph.DexApplication;
+import com.android.tools.r8.graph.DexEncodedMethod;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.code.ArrayLength;
+import com.android.tools.r8.ir.code.CheckCast;
+import com.android.tools.r8.ir.code.ConstNumber;
+import com.android.tools.r8.ir.code.ConstString;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.InstanceOf;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InstructionIterator;
+import com.android.tools.r8.ir.code.InvokeNewArray;
+import com.android.tools.r8.ir.code.NewArrayEmpty;
+import com.android.tools.r8.ir.code.NewInstance;
+import com.android.tools.r8.ir.code.StaticGet;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.naming.MemberNaming.MethodSignature;
+import com.android.tools.r8.origin.Origin;
+import com.android.tools.r8.smali.SmaliTestBase;
+import com.android.tools.r8.utils.AndroidApp;
+import com.android.tools.r8.utils.DexInspector;
+import com.android.tools.r8.utils.InternalOptions;
+import com.android.tools.r8.utils.Smali;
+import com.android.tools.r8.utils.Timing;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Maps;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameters;
+import java.nio.charset.StandardCharsets;
+import java.nio.file.Files;
+import java.nio.file.Path;
+import java.nio.file.Paths;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.function.Consumer;
+
+@RunWith(Parameterized.class)
+public class TypeAnalysisTest extends SmaliTestBase {
+ private static final InternalOptions TEST_OPTIONS = new InternalOptions();
+ private static final TypeLatticeElement PRIMITIVE = PrimitiveTypeLatticeElement.getInstance();
+
+ private final String dirName;
+ private final String smaliFileName;
+ private final Consumer<AppInfoWithSubtyping> inspection;
+
+ public TypeAnalysisTest(String test, Consumer<AppInfoWithSubtyping> inspection) {
+ dirName = test.substring(0, test.lastIndexOf('/'));
+ smaliFileName = test.substring(test.lastIndexOf('/') + 1) + ".smali";
+ this.inspection = inspection;
+ }
+
+ @Parameters(name = "{0}")
+ public static Collection<Object[]> data() throws Exception {
+ List<String> tests = Arrays.asList(
+ "arithmetic/Arithmetic",
+ "fibonacci/Fibonacci",
+ "fill-array-data/FillArrayData",
+ "filled-new-array/FilledNewArray",
+ "infinite-loop/InfiniteLoop1",
+ "try-catch/TryCatch",
+ "type-confusion-regression/TestObject",
+ "type-confusion-regression5/TestObject"
+ );
+
+ Map<String, Consumer<AppInfoWithSubtyping>> inspections = new HashMap<>();
+ inspections.put("arithmetic/Arithmetic", TypeAnalysisTest::arithmetic);
+ inspections.put("fibonacci/Fibonacci", TypeAnalysisTest::fibonacci);
+ inspections.put("fill-array-data/FillArrayData", TypeAnalysisTest::fillArrayData);
+ inspections.put("filled-new-array/FilledNewArray", TypeAnalysisTest::filledNewArray);
+ inspections.put("infinite-loop/InfiniteLoop1", TypeAnalysisTest::infiniteLoop);
+ inspections.put("try-catch/TryCatch", TypeAnalysisTest::tryCatch);
+ inspections.put("type-confusion-regression/TestObject", TypeAnalysisTest::typeConfusion);
+ inspections.put("type-confusion-regression5/TestObject", TypeAnalysisTest::typeConfusion5);
+
+ List<Object[]> testCases = new ArrayList<>();
+ for (String test : tests) {
+ Consumer<AppInfoWithSubtyping> inspection = inspections.get(test);
+ testCases.add(new Object[]{test, inspection});
+ }
+ return testCases;
+ }
+
+ @Test
+ public void typeAnalysisTest() throws Exception {
+ Path smaliPath = Paths.get(ToolHelper.SMALI_DIR, dirName, smaliFileName);
+ StringBuilder smaliStringBuilder = new StringBuilder();
+ Files.lines(smaliPath, StandardCharsets.UTF_8)
+ .forEach(s -> smaliStringBuilder.append(s).append(System.lineSeparator()));
+ byte[] content = Smali.compile(smaliStringBuilder.toString());
+ AndroidApp app = AndroidApp.builder().addDexProgramData(content, Origin.unknown()).build();
+ DexApplication dexApplication =
+ new ApplicationReader(app, TEST_OPTIONS, new Timing("TypeAnalysisTest.appReader"))
+ .read().toDirect();
+ inspection.accept(new AppInfoWithSubtyping(dexApplication));
+ }
+
+ // Simple one path with a lot of arithmetic operations.
+ private static void arithmetic(AppInfoWithSubtyping appInfo) {
+ DexInspector inspector = new DexInspector(appInfo.app);
+ DexEncodedMethod subtract =
+ inspector.clazz("Test")
+ .method(
+ new MethodSignature("subtractConstants8bitRegisters", "int", ImmutableList.of()))
+ .getMethod();
+ try {
+ IRCode irCode = subtract.buildIR(TEST_OPTIONS);
+ TypeAnalysis analysis = new TypeAnalysis(appInfo, subtract, irCode);
+ analysis.run();
+ analysis.forEach((v, l) -> {
+ assertEquals(l, PRIMITIVE);
+ });
+ } catch (ApiLevelException e) {
+ fail(e.getMessage());
+ }
+ }
+
+ // A couple branches, along with some recursive calls.
+ private static void fibonacci(AppInfoWithSubtyping appInfo) {
+ DexInspector inspector = new DexInspector(appInfo.app);
+ DexEncodedMethod fib =
+ inspector.clazz("Test")
+ .method(new MethodSignature("fibonacci", "int", ImmutableList.of("int")))
+ .getMethod();
+ try {
+ IRCode irCode = fib.buildIR(TEST_OPTIONS);
+ TypeAnalysis analysis = new TypeAnalysis(appInfo, fib, irCode);
+ analysis.run();
+ analysis.forEach((v, l) -> {
+ assertEquals(l, PRIMITIVE);
+ });
+ } catch (ApiLevelException e) {
+ fail(e.getMessage());
+ }
+ }
+
+ // fill-array-data
+ private static void fillArrayData(AppInfoWithSubtyping appInfo) {
+ DexInspector inspector = new DexInspector(appInfo.app);
+ DexEncodedMethod test1 =
+ inspector.clazz("Test")
+ .method(new MethodSignature("test1", "int[]", ImmutableList.of()))
+ .getMethod();
+ try {
+ IRCode irCode = test1.buildIR(TEST_OPTIONS);
+ TypeAnalysis analysis = new TypeAnalysis(appInfo, test1, irCode);
+ analysis.run();
+ Value array = null;
+ InstructionIterator iterator = irCode.instructionIterator();
+ while (iterator.hasNext()) {
+ Instruction instruction = iterator.next();
+ if (instruction instanceof NewArrayEmpty) {
+ array = instruction.outValue();
+ break;
+ }
+ }
+ assertNotNull(array);
+ final Value finalArray = array;
+ analysis.forEach((v, l) -> {
+ if (v == finalArray) {
+ assertTrue(l instanceof PrimitiveArrayTypeLatticeElement);
+ PrimitiveArrayTypeLatticeElement lattice = (PrimitiveArrayTypeLatticeElement) l;
+ assertEquals(1, lattice.nesting);
+ assertFalse(l.isNullable());
+ }
+ });
+ } catch (ApiLevelException e) {
+ fail(e.getMessage());
+ }
+ }
+
+ // filled-new-array
+ private static void filledNewArray(AppInfoWithSubtyping appInfo) {
+ DexInspector inspector = new DexInspector(appInfo.app);
+ DexEncodedMethod test4 =
+ inspector.clazz("Test")
+ .method(new MethodSignature("test4", "int[]", ImmutableList.of()))
+ .getMethod();
+ try {
+ IRCode irCode = test4.buildIR(TEST_OPTIONS);
+ TypeAnalysis analysis = new TypeAnalysis(appInfo, test4, irCode);
+ analysis.run();
+ Value array = null;
+ InstructionIterator iterator = irCode.instructionIterator();
+ while (iterator.hasNext()) {
+ Instruction instruction = iterator.next();
+ if (instruction instanceof InvokeNewArray) {
+ array = instruction.outValue();
+ break;
+ }
+ }
+ assertNotNull(array);
+ final Value finalArray = array;
+ analysis.forEach((v, l) -> {
+ if (v == finalArray) {
+ assertTrue(l instanceof PrimitiveArrayTypeLatticeElement);
+ PrimitiveArrayTypeLatticeElement lattice = (PrimitiveArrayTypeLatticeElement) l;
+ assertEquals(1, lattice.nesting);
+ assertFalse(l.isNullable());
+ }
+ });
+ } catch (ApiLevelException e) {
+ fail(e.getMessage());
+ }
+ }
+
+ // Make sure the analysis does not hang.
+ private static void infiniteLoop(AppInfoWithSubtyping appInfo) {
+ DexInspector inspector = new DexInspector(appInfo.app);
+ DexEncodedMethod loop2 =
+ inspector.clazz("Test")
+ .method(new MethodSignature("loop2", "void", ImmutableList.of()))
+ .getMethod();
+ try {
+ IRCode irCode = loop2.buildIR(TEST_OPTIONS);
+ TypeAnalysis analysis = new TypeAnalysis(appInfo, loop2, irCode);
+ analysis.run();
+ analysis.forEach((v, l) -> {
+ if (l instanceof ClassTypeLatticeElement) {
+ ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+ assertEquals("Ljava/io/PrintStream;", lattice.classType.toDescriptorString());
+ // TODO(b/70795205): Can be refined by using control-flow info.
+ assertTrue(l.isNullable());
+ }
+ });
+ } catch (ApiLevelException e) {
+ fail(e.getMessage());
+ }
+ }
+
+ // move-exception
+ private static void tryCatch(AppInfoWithSubtyping appInfo) {
+ DexInspector inspector = new DexInspector(appInfo.app);
+ DexEncodedMethod test2 =
+ inspector.clazz("Test")
+ .method(new MethodSignature("test2_throw", "int", ImmutableList.of()))
+ .getMethod();
+ try {
+ IRCode irCode = test2.buildIR(TEST_OPTIONS);
+ TypeAnalysis analysis = new TypeAnalysis(appInfo, test2, irCode);
+ analysis.run();
+ analysis.forEach((v, l) -> {
+ if (l instanceof ClassTypeLatticeElement) {
+ ClassTypeLatticeElement lattice = (ClassTypeLatticeElement) l;
+ assertEquals("Ljava/lang/Throwable;", lattice.classType.toDescriptorString());
+ assertFalse(l.isNullable());
+ }
+ });
+ } catch (ApiLevelException e) {
+ fail(e.getMessage());
+ }
+ }
+
+ // One very complicated example.
+ private static void typeConfusion(AppInfoWithSubtyping appInfo) {
+ DexInspector inspector = new DexInspector(appInfo.app);
+ DexEncodedMethod method =
+ inspector.clazz("TestObject")
+ .method(
+ new MethodSignature("a", "void",
+ ImmutableList.of("Test", "Test", "Test", "Test")))
+ .getMethod();
+
+ DexType test = appInfo.dexItemFactory.createType("LTest;");
+ Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = Maps.newHashMap();
+ expectedLattices.put(ArrayLength.class, PRIMITIVE);
+ expectedLattices.put(ConstNumber.class, PRIMITIVE);
+ expectedLattices.put(
+ ConstString.class, new ClassTypeLatticeElement(appInfo.dexItemFactory.stringType, false));
+ expectedLattices.put(CheckCast.class, new ClassTypeLatticeElement(test, true));
+ expectedLattices.put(NewInstance.class, new ClassTypeLatticeElement(test, false));
+
+ try {
+ IRCode irCode = method.buildIR(TEST_OPTIONS);
+ TypeAnalysis analysis = new TypeAnalysis(appInfo, method, irCode);
+ analysis.run();
+ analysis.forEach((v, l) -> {
+ if (v.definition == null) {
+ return;
+ }
+ TypeLatticeElement expected = expectedLattices.get(v.definition.getClass());
+ if (expected != null) {
+ assertEquals(expected, l);
+ }
+ });
+ } catch (ApiLevelException e) {
+ fail(e.getMessage());
+ }
+ }
+
+ // One more complicated example.
+ private static void typeConfusion5(AppInfoWithSubtyping appInfo) {
+ DexInspector inspector = new DexInspector(appInfo.app);
+ DexEncodedMethod method =
+ inspector.clazz("TestObject")
+ .method(
+ new MethodSignature("onClick", "void", ImmutableList.of("Test")))
+ .getMethod();
+
+ DexType test = appInfo.dexItemFactory.createType("LTest;");
+ Map<Class<? extends Instruction>, TypeLatticeElement> expectedLattices = Maps.newHashMap();
+ expectedLattices.put(ConstNumber.class, PRIMITIVE);
+ expectedLattices.put(
+ ConstString.class, new ClassTypeLatticeElement(appInfo.dexItemFactory.stringType, false));
+ expectedLattices.put(InstanceOf.class, PRIMITIVE);
+ expectedLattices.put(StaticGet.class, new ClassTypeLatticeElement(test, true));
+
+ try {
+ IRCode irCode = method.buildIR(TEST_OPTIONS);
+ TypeAnalysis analysis = new TypeAnalysis(appInfo, method, irCode);
+ analysis.run();
+ analysis.forEach((v, l) -> {
+ if (v.definition == null) {
+ return;
+ }
+ TypeLatticeElement expected = expectedLattices.get(v.definition.getClass());
+ if (expected != null) {
+ assertEquals(expected, l);
+ }
+ });
+ } catch (ApiLevelException e) {
+ fail(e.getMessage());
+ }
+ }
+}
diff --git a/src/test/java/com/android/tools/r8/utils/DexInspector.java b/src/test/java/com/android/tools/r8/utils/DexInspector.java
index 56ba5a5..bbd6fb5 100644
--- a/src/test/java/com/android/tools/r8/utils/DexInspector.java
+++ b/src/test/java/com/android/tools/r8/utils/DexInspector.java
@@ -63,6 +63,7 @@
import com.android.tools.r8.naming.MemberNaming.FieldSignature;
import com.android.tools.r8.naming.MemberNaming.MethodSignature;
import com.android.tools.r8.naming.MemberNaming.Signature;
+import com.android.tools.r8.smali.SmaliBuilder;
import com.google.common.collect.BiMap;
import com.google.common.collect.ImmutableList;
import java.io.IOException;
@@ -286,6 +287,11 @@
return method(signature.type, signature.name, ImmutableList.copyOf(signature.parameters));
}
+ public MethodSubject method(SmaliBuilder.MethodSignature signature) {
+ return method(
+ signature.returnType, signature.name, ImmutableList.copyOf(signature.parameterTypes));
+ }
+
public abstract void forAllFields(Consumer<FoundFieldSubject> inspection);
public abstract FieldSubject field(String type, String name);
diff --git a/src/test/smali/try-catch/TryCatch.smali b/src/test/smali/try-catch/TryCatch.smali
index 2becd5f..8e06c5a 100644
--- a/src/test/smali/try-catch/TryCatch.smali
+++ b/src/test/smali/try-catch/TryCatch.smali
@@ -32,6 +32,23 @@
return v0
.end method
+.method public static test2_throw()I
+ .locals 1
+ const v0, 1
+ :try_start
+ invoke-static {}, Ltest/X;->f()V
+ const v0, 0
+ goto :return
+ :try_end
+ .catch Ljava/lang/Exception; {:try_start .. :try_end} :return
+ .catch Ljava/lang/Throwable; {:try_start .. :try_end} :error
+ :error
+ move-exception v0
+ throw v0
+ :return
+ return v0
+.end method
+
# Dead catch block.
.method public test3()I
.locals 1
