Redesign array type lattice element.
Previously, array type lattice has DexType as array type, and join was
using that to compute the least upper bound of base types. However, if
participated base type is interface and class, we lose the accuracy.
To use pair-wise class/interface join, array type lattice should have
either array or element type as type lattice, not DexType.
In this CL, we chose a nested structure: ArrayTypeLatticeElement is
composed of element type lattice, which could be array type lattice in
a recursive way.
One caveat is to distinguish int[] v.s. (boolean|byte|short|char)[]
because those smaller types were merged to IntTypeLatticeElement.
This CL introduces smaller type lattice elements only for array
element type, and ensure that they are never assigned to SSA value.
Bug: 119181813, 119042956, 72693244, 117414337
Change-Id: I4c67db06485c0d0e3fc5245c8525370141587936
diff --git a/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java b/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
index 16a03e2..53907db 100644
--- a/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
+++ b/src/main/java/com/android/tools/r8/cf/TypeVerificationHelper.java
@@ -193,7 +193,7 @@
if (result.isClassType()) {
return result.asClassTypeLatticeElement().getClassType();
} else if (result.isArrayType()) {
- return result.asArrayTypeLatticeElement().getArrayType();
+ return result.asArrayTypeLatticeElement().getArrayType(factory);
}
throw new CompilationError("Unexpected join " + result + " of types: " +
String.join(", ",
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 9383bcc..8139a414 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -18,10 +18,12 @@
import com.android.tools.r8.ir.analysis.type.ArrayTypeLatticeElement;
import com.android.tools.r8.ir.analysis.type.ClassTypeLatticeElement;
import com.android.tools.r8.ir.analysis.type.ReferenceTypeLatticeElement;
+import com.android.tools.r8.ir.analysis.type.TypeLatticeElement;
import com.android.tools.r8.ir.code.Position;
import com.android.tools.r8.kotlin.Kotlin;
import com.android.tools.r8.naming.NamingLens;
import com.android.tools.r8.utils.ArrayUtils;
+import com.android.tools.r8.utils.LRUCacheTable;
import com.google.common.base.Strings;
import com.google.common.collect.BiMap;
import com.google.common.collect.HashBiMap;
@@ -66,6 +68,8 @@
// ReferenceTypeLattice canonicalization.
private final ConcurrentHashMap<DexType, ReferenceTypeLatticeElement>
referenceTypeLatticeElements = new ConcurrentHashMap<>();
+ public static final LRUCacheTable<Set<DexType>, Set<DexType>, Set<DexType>>
+ leastUpperBoundOfInterfacesTable = LRUCacheTable.create(8, 8);
boolean sorted = false;
@@ -995,7 +999,10 @@
}
} else {
assert type.isArrayType();
- typeLattice = new ArrayTypeLatticeElement(type, isNullable);
+ DexType elementType = type.toArrayElementType(this);
+ TypeLatticeElement elementTypeLattice =
+ TypeLatticeElement.fromDexType(elementType, true, appInfo, true);
+ typeLattice = new ArrayTypeLatticeElement(elementTypeLattice, isNullable);
}
referenceTypeLatticeElements.put(type, typeLattice);
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java b/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java
index 96227c4..0da99ae 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/TypeChecker.java
@@ -70,24 +70,22 @@
instruction.isInstancePut()
? instruction.asInstancePut().value()
: instruction.asStaticPut().inValue();
- TypeLatticeElement fieldType =
- TypeLatticeElement.fromDexType(instruction.getField().type, true, appInfo);
TypeLatticeElement valueType = value.getTypeLattice();
+ TypeLatticeElement fieldType = TypeLatticeElement.fromDexType(
+ instruction.getField().type, valueType.isNullable(), appInfo);
return isSubtypeOf(valueType, fieldType);
}
public boolean check(Throw instruction) {
- TypeLatticeElement throwableType =
- TypeLatticeElement.fromDexType(appInfo.dexItemFactory.throwableType, true, appInfo);
TypeLatticeElement valueType = instruction.exception().getTypeLattice();
+ TypeLatticeElement throwableType = TypeLatticeElement.fromDexType(
+ appInfo.dexItemFactory.throwableType, valueType.isNullable(), appInfo);
return isSubtypeOf(valueType, throwableType);
}
private boolean isSubtypeOf(
TypeLatticeElement expectedSubtype, TypeLatticeElement expectedSupertype) {
return expectedSubtype.lessThanOrEqual(expectedSupertype, appInfo)
- || expectedSubtype.isBasedOnMissingClass(appInfo)
- // TODO(b/119181813): Remove this relaxation when the join of array types is fixed.
- || (expectedSubtype.isArrayType() && expectedSupertype.isArrayType());
+ || expectedSubtype.isBasedOnMissingClass(appInfo);
}
}
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
index 4ff54d3..6bb13a7 100644
--- 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
@@ -9,25 +9,49 @@
public class ArrayTypeLatticeElement extends ReferenceTypeLatticeElement {
- public ArrayTypeLatticeElement(DexType type, boolean isNullable) {
- super(type, isNullable);
- assert type.isArrayType();
+ private final TypeLatticeElement memberTypeLattice;
+
+ public ArrayTypeLatticeElement(TypeLatticeElement memberTypeLattice, boolean isNullable) {
+ super(isNullable, null);
+ this.memberTypeLattice = memberTypeLattice;
}
- public DexType getArrayType() {
- return type;
+ public DexType getArrayType(DexItemFactory factory) {
+ TypeLatticeElement baseTypeLattice = getArrayBaseTypeLattice();
+ DexType baseType;
+ if (baseTypeLattice.isPrimitive()) {
+ baseType = baseTypeLattice.asPrimitiveTypeLatticeElement().toDexType(factory);
+ } else {
+ assert baseTypeLattice.isClassType();
+ baseType = baseTypeLattice.asClassTypeLatticeElement().getClassType();
+ }
+ return factory.createArrayType(getNesting(), baseType);
}
- public int getNesting() {
- return type.getNumberOfLeadingSquareBrackets();
+ int getNesting() {
+ int nesting = 1;
+ TypeLatticeElement member = getArrayMemberTypeAsMemberType();
+ while (member.isArrayType()) {
+ ++nesting;
+ member = member.asArrayTypeLatticeElement().getArrayMemberTypeAsMemberType();
+ }
+ return nesting;
}
- public DexType getArrayElementType(DexItemFactory factory) {
- return type.toArrayElementType(factory);
+ TypeLatticeElement getArrayMemberTypeAsMemberType() {
+ return memberTypeLattice;
}
- public DexType getArrayBaseType(DexItemFactory factory) {
- return type.toBaseType(factory);
+ public TypeLatticeElement getArrayMemberTypeAsValueType() {
+ return memberTypeLattice.isFineGrainedType() ? INT : memberTypeLattice;
+ }
+
+ private TypeLatticeElement getArrayBaseTypeLattice() {
+ TypeLatticeElement base = getArrayMemberTypeAsMemberType();
+ while (base.isArrayType()) {
+ base = base.asArrayTypeLatticeElement().getArrayMemberTypeAsMemberType();
+ }
+ return base;
}
@Override
@@ -37,7 +61,8 @@
}
synchronized (this) {
if (dual == null) {
- ArrayTypeLatticeElement dual = new ArrayTypeLatticeElement(type, !isNullable());
+ ArrayTypeLatticeElement dual =
+ new ArrayTypeLatticeElement(memberTypeLattice, !isNullable());
linkDualLattice(this, dual);
}
}
@@ -56,7 +81,7 @@
@Override
public boolean isBasedOnMissingClass(AppInfo appInfo) {
- return getArrayBaseType(appInfo.dexItemFactory).isMissingOrHasMissingSuperType(appInfo);
+ return memberTypeLattice.isBasedOnMissingClass(appInfo);
}
@Override
@@ -70,13 +95,55 @@
}
@Override
- public TypeLatticeElement arrayGet(AppInfo appInfo) {
- return fromDexType(getArrayElementType(appInfo.dexItemFactory), true, appInfo);
+ public String toString() {
+ return memberTypeLattice.toString() + "[]";
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (!(o instanceof ArrayTypeLatticeElement)) {
+ return false;
+ }
+ ArrayTypeLatticeElement other = (ArrayTypeLatticeElement) o;
+ if (isNullable() != other.isNullable()) {
+ return false;
+ }
+ if (type != null && other.type != null && !type.equals(other.type)) {
+ return false;
+ }
+ return memberTypeLattice.equals(other.memberTypeLattice);
}
@Override
public int hashCode() {
- return (isNullable() ? 1 : -1) * type.hashCode();
+ return (isNullable() ? 1 : -1) * memberTypeLattice.hashCode();
+ }
+
+ ReferenceTypeLatticeElement join(ArrayTypeLatticeElement other, AppInfo appInfo) {
+ TypeLatticeElement aMember = getArrayMemberTypeAsMemberType();
+ TypeLatticeElement bMember = other.getArrayMemberTypeAsMemberType();
+ if (aMember.equals(bMember)) {
+ // Return null indicating the join is the same as the member to avoid object allocation.
+ return null;
+ }
+ boolean isNullable = isNullable() || other.isNullable();
+ if (aMember.isArrayType() && bMember.isArrayType()) {
+ ReferenceTypeLatticeElement join =
+ aMember.asArrayTypeLatticeElement().join(bMember.asArrayTypeLatticeElement(), appInfo);
+ return join == null ? null : new ArrayTypeLatticeElement(join, isNullable);
+ }
+ if (aMember.isClassType() && bMember.isClassType()) {
+ ClassTypeLatticeElement join =
+ aMember.asClassTypeLatticeElement().join(bMember.asClassTypeLatticeElement(), appInfo);
+ return join == null ? null : new ArrayTypeLatticeElement(join, isNullable);
+ }
+ if (aMember.isPrimitive() || bMember.isPrimitive()) {
+ return objectClassType(appInfo, isNullable);
+ }
+ return objectArrayType(appInfo, isNullable);
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/BooleanTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/BooleanTypeLatticeElement.java
new file mode 100644
index 0000000..abcdb9e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/BooleanTypeLatticeElement.java
@@ -0,0 +1,32 @@
+// 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.analysis.type;
+
+public class BooleanTypeLatticeElement extends PrimitiveTypeLatticeElement {
+ private static final BooleanTypeLatticeElement INSTANCE = new BooleanTypeLatticeElement();
+
+ static BooleanTypeLatticeElement getInstance() {
+ return INSTANCE;
+ }
+
+ @Override
+ boolean isBoolean() {
+ return true;
+ }
+
+ @Override
+ public String toString() {
+ return "BOOLEAN";
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ return this == o;
+ }
+
+ @Override
+ public int hashCode() {
+ return System.identityHashCode(INSTANCE);
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/BottomTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/BottomTypeLatticeElement.java
index 6931b46..e86d66f 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/BottomTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/BottomTypeLatticeElement.java
@@ -28,11 +28,6 @@
}
@Override
- public TypeLatticeElement arrayGet(AppInfo appInfo) {
- return this;
- }
-
- @Override
public TypeLatticeElement checkCast(AppInfo appInfo, DexType castType) {
return this;
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ByteTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ByteTypeLatticeElement.java
new file mode 100644
index 0000000..d05c25e
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ByteTypeLatticeElement.java
@@ -0,0 +1,32 @@
+// 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.analysis.type;
+
+public class ByteTypeLatticeElement extends PrimitiveTypeLatticeElement {
+ private static final ByteTypeLatticeElement INSTANCE = new ByteTypeLatticeElement();
+
+ static ByteTypeLatticeElement getInstance() {
+ return INSTANCE;
+ }
+
+ @Override
+ boolean isByte() {
+ return true;
+ }
+
+ @Override
+ public String toString() {
+ return "BYTE";
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ return this == o;
+ }
+
+ @Override
+ public int hashCode() {
+ return System.identityHashCode(INSTANCE);
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/CharTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/CharTypeLatticeElement.java
new file mode 100644
index 0000000..27834aa
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/CharTypeLatticeElement.java
@@ -0,0 +1,32 @@
+// 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.analysis.type;
+
+public class CharTypeLatticeElement extends PrimitiveTypeLatticeElement {
+ private static final CharTypeLatticeElement INSTANCE = new CharTypeLatticeElement();
+
+ static CharTypeLatticeElement getInstance() {
+ return INSTANCE;
+ }
+
+ @Override
+ boolean isChar() {
+ return true;
+ }
+
+ @Override
+ public String toString() {
+ return "BYTE";
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ return this == o;
+ }
+
+ @Override
+ public int hashCode() {
+ return System.identityHashCode(INSTANCE);
+ }
+}
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
index 84146a2..c25395d 100644
--- 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
@@ -4,7 +4,14 @@
package com.android.tools.r8.ir.analysis.type;
import com.android.tools.r8.graph.AppInfo;
+import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexType;
+import com.google.common.collect.ImmutableSet;
+import java.util.ArrayDeque;
+import java.util.HashSet;
+import java.util.IdentityHashMap;
+import java.util.Map;
+import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;
@@ -23,7 +30,7 @@
private ClassTypeLatticeElement(
DexType classType, boolean isNullable, Set<DexType> interfaces, AppInfo appInfo) {
- super(classType, isNullable);
+ super(isNullable, classType);
assert classType.isClassType();
appInfoForLazyInterfacesComputation = appInfo;
lazyInterfaces = interfaces;
@@ -42,8 +49,7 @@
if (lazyInterfaces == null) {
Set<DexType> itfs = type.implementedInterfaces(appInfoForLazyInterfacesComputation);
lazyInterfaces =
- TypeLatticeElement.computeLeastUpperBoundOfInterfaces(
- appInfoForLazyInterfacesComputation, itfs, itfs);
+ computeLeastUpperBoundOfInterfaces(appInfoForLazyInterfacesComputation, itfs, itfs);
appInfoForLazyInterfacesComputation = null;
}
}
@@ -96,10 +102,10 @@
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append(super.toString());
- builder.append(" [");
+ builder.append(" {");
builder.append(
getInterfaces().stream().map(DexType::toString).collect(Collectors.joining(", ")));
- builder.append("]");
+ builder.append("}");
return builder.toString();
}
@@ -108,4 +114,115 @@
// The interfaces of a type do not contribute to its hashCode as they are lazily computed.
return (isNullable() ? 1 : -1) * type.hashCode();
}
+
+ ClassTypeLatticeElement join(ClassTypeLatticeElement other, AppInfo appInfo) {
+ DexType lubType = getClassType().computeLeastUpperBoundOfClasses(appInfo, other.getClassType());
+ Set<DexType> c1lubItfs = getInterfaces();
+ Set<DexType> c2lubItfs = other.getInterfaces();
+ Set<DexType> lubItfs = null;
+ if (c1lubItfs.size() == c2lubItfs.size() && c1lubItfs.containsAll(c2lubItfs)) {
+ lubItfs = c1lubItfs;
+ }
+ if (lubItfs == null) {
+ lubItfs = computeLeastUpperBoundOfInterfaces(appInfo, c1lubItfs, c2lubItfs);
+ }
+ boolean isNullable = isNullable() || other.isNullable();
+ return new ClassTypeLatticeElement(lubType, isNullable, lubItfs);
+ }
+
+ private enum InterfaceMarker {
+ LEFT,
+ RIGHT
+ }
+
+ private static class InterfaceWithMarker {
+ final DexType itf;
+ final InterfaceMarker marker;
+
+ InterfaceWithMarker(DexType itf, InterfaceMarker marker) {
+ this.itf = itf;
+ this.marker = marker;
+ }
+ }
+
+ static Set<DexType> computeLeastUpperBoundOfInterfaces(
+ AppInfo appInfo, Set<DexType> s1, Set<DexType> s2) {
+ Set<DexType> cached = appInfo.dexItemFactory.leastUpperBoundOfInterfacesTable.get(s1, s2);
+ if (cached != null) {
+ return cached;
+ }
+ cached = appInfo.dexItemFactory.leastUpperBoundOfInterfacesTable.get(s2, s1);
+ if (cached != null) {
+ return cached;
+ }
+ Map<DexType, Set<InterfaceMarker>> seen = new IdentityHashMap<>();
+ Queue<InterfaceWithMarker> worklist = new ArrayDeque<>();
+ for (DexType itf1 : s1) {
+ worklist.add(new InterfaceWithMarker(itf1, InterfaceMarker.LEFT));
+ }
+ for (DexType itf2 : s2) {
+ worklist.add(new InterfaceWithMarker(itf2, InterfaceMarker.RIGHT));
+ }
+ while (!worklist.isEmpty()) {
+ InterfaceWithMarker item = worklist.poll();
+ DexType itf = item.itf;
+ InterfaceMarker marker = item.marker;
+ Set<InterfaceMarker> markers = seen.computeIfAbsent(itf, k -> new HashSet<>());
+ // If this interface is a lower one in this set, skip.
+ if (markers.contains(marker)) {
+ continue;
+ }
+ // If this interface is already visited by the other set, add marker for this set and skip.
+ if (markers.size() == 1) {
+ markers.add(marker);
+ continue;
+ }
+ // Otherwise, this type is freshly visited.
+ markers.add(marker);
+ // Put super interfaces into the worklist.
+ DexClass itfClass = appInfo.definitionFor(itf);
+ if (itfClass != null) {
+ for (DexType superItf : itfClass.interfaces.values) {
+ markers = seen.computeIfAbsent(superItf, k -> new HashSet<>());
+ if (!markers.contains(marker)) {
+ worklist.add(new InterfaceWithMarker(superItf, marker));
+ }
+ }
+ }
+ }
+
+ ImmutableSet.Builder<DexType> commonBuilder = ImmutableSet.builder();
+ for (Map.Entry<DexType, Set<InterfaceMarker>> entry : seen.entrySet()) {
+ // Keep commonly visited interfaces only
+ if (entry.getValue().size() < 2) {
+ continue;
+ }
+ commonBuilder.add(entry.getKey());
+ }
+ Set<DexType> commonlyVisited = commonBuilder.build();
+
+ ImmutableSet.Builder<DexType> lubBuilder = ImmutableSet.builder();
+ for (DexType itf : commonlyVisited) {
+ // If there is a strict sub interface of this interface, it is not the least element.
+ boolean notTheLeast = false;
+ for (DexType other : commonlyVisited) {
+ if (other.isStrictSubtypeOf(itf, appInfo)) {
+ notTheLeast = true;
+ break;
+ }
+ }
+ if (notTheLeast) {
+ continue;
+ }
+ lubBuilder.add(itf);
+ }
+ Set<DexType> lub = lubBuilder.build();
+ // Cache the computation result only if the given two sets of interfaces are different.
+ if (s1.size() != s2.size() || !s1.containsAll(s2)) {
+ synchronized (appInfo.dexItemFactory.leastUpperBoundOfInterfacesTable) {
+ appInfo.dexItemFactory.leastUpperBoundOfInterfacesTable.put(s1, s2, lub);
+ }
+ }
+ return lub;
+ }
}
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
index 51097d8..4c633f5 100644
--- 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
@@ -5,6 +5,7 @@
import com.android.tools.r8.errors.InternalCompilerError;
import com.android.tools.r8.errors.Unreachable;
+import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.ir.code.NumericType;
@@ -32,17 +33,62 @@
return this;
}
- public static PrimitiveTypeLatticeElement fromDexType(DexType type) {
+ static PrimitiveTypeLatticeElement fromDexType(DexType type, boolean asArrayElementType) {
assert type.isPrimitiveType();
- return fromTypeDescriptorChar((char) type.descriptor.content[0]);
+ return fromTypeDescriptorChar((char) type.descriptor.content[0], asArrayElementType);
}
- public static PrimitiveTypeLatticeElement fromTypeDescriptorChar(char descriptor) {
+ DexType toDexType(DexItemFactory factory) {
+ if (isBoolean()) {
+ return factory.booleanType;
+ }
+ if (isByte()) {
+ return factory.byteType;
+ }
+ if (isShort()) {
+ return factory.shortType;
+ }
+ if (isChar()) {
+ return factory.charType;
+ }
+ if (isInt()) {
+ return factory.intType;
+ }
+ if (isFloat()) {
+ return factory.floatType;
+ }
+ if (isLong()) {
+ return factory.longType;
+ }
+ if (isDouble()) {
+ return factory.doubleType;
+ }
+ throw new Unreachable("Imprecise primitive type '" + toString() + "'");
+ }
+
+ private static PrimitiveTypeLatticeElement fromTypeDescriptorChar(
+ char descriptor, boolean asArrayElementType) {
switch (descriptor) {
case 'Z':
+ if (asArrayElementType) {
+ return TypeLatticeElement.BOOLEAN;
+ }
+ // fall through
case 'B':
+ if (asArrayElementType) {
+ return TypeLatticeElement.BYTE;
+ }
+ // fall through
case 'S':
+ if (asArrayElementType) {
+ return TypeLatticeElement.SHORT;
+ }
+ // fall through
case 'C':
+ if (asArrayElementType) {
+ return TypeLatticeElement.CHAR;
+ }
+ // fall through
case 'I':
return TypeLatticeElement.INT;
case 'F':
@@ -76,23 +122,22 @@
}
}
- public static TypeLatticeElement join(
- PrimitiveTypeLatticeElement t1, PrimitiveTypeLatticeElement t2) {
- if (t1 == t2) {
- return t1;
+ TypeLatticeElement join(PrimitiveTypeLatticeElement other) {
+ if (this == other) {
+ return this;
}
- if (t1.isSingle()) {
- if (t2.isSingle()) {
+ if (isSingle()) {
+ if (other.isSingle()) {
return TypeLatticeElement.SINGLE;
}
- assert t2.isWide();
+ assert other.isWide();
return TypeLatticeElement.TOP;
}
- assert t1.isWide();
- if (t2.isWide()) {
+ assert isWide();
+ if (other.isWide()) {
return TypeLatticeElement.WIDE;
}
- assert t2.isSingle();
+ assert other.isSingle();
return TypeLatticeElement.TOP;
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ReferenceTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ReferenceTypeLatticeElement.java
index 423c8cc..e7282e1 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/ReferenceTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ReferenceTypeLatticeElement.java
@@ -11,8 +11,9 @@
public class ReferenceTypeLatticeElement extends TypeLatticeElement {
private static final ReferenceTypeLatticeElement NULL_INSTANCE =
- new ReferenceTypeLatticeElement(DexItemFactory.nullValueType, true);
+ new ReferenceTypeLatticeElement(true, DexItemFactory.nullValueType);
+ // TODO(b/72693244): Consider moving this to ClassTypeLatticeElement.
final DexType type;
// Link between maybe-null and definitely-not-null reference type lattices.
@@ -28,7 +29,7 @@
t2.dual = t1;
}
- ReferenceTypeLatticeElement(DexType type, boolean isNullable) {
+ ReferenceTypeLatticeElement(boolean isNullable, DexType type) {
super(isNullable);
this.type = type;
}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/ShortTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/ShortTypeLatticeElement.java
new file mode 100644
index 0000000..6b56f08
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/ShortTypeLatticeElement.java
@@ -0,0 +1,32 @@
+// 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.analysis.type;
+
+public class ShortTypeLatticeElement extends PrimitiveTypeLatticeElement {
+ private static final ShortTypeLatticeElement INSTANCE = new ShortTypeLatticeElement();
+
+ static ShortTypeLatticeElement getInstance() {
+ return INSTANCE;
+ }
+
+ @Override
+ boolean isShort() {
+ return true;
+ }
+
+ @Override
+ public String toString() {
+ return "SHORT";
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ return this == o;
+ }
+
+ @Override
+ public int hashCode() {
+ return System.identityHashCode(INSTANCE);
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/analysis/type/TopTypeLatticeElement.java b/src/main/java/com/android/tools/r8/ir/analysis/type/TopTypeLatticeElement.java
index 4ffe7b1..5221ae3 100644
--- a/src/main/java/com/android/tools/r8/ir/analysis/type/TopTypeLatticeElement.java
+++ b/src/main/java/com/android/tools/r8/ir/analysis/type/TopTypeLatticeElement.java
@@ -28,11 +28,6 @@
}
@Override
- public TypeLatticeElement arrayGet(AppInfo appInfo) {
- return this;
- }
-
- @Override
public TypeLatticeElement checkCast(AppInfo appInfo, DexType castType) {
return this;
}
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
index 7b1e28a..b29cd31 100644
--- 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
@@ -5,19 +5,10 @@
import com.android.tools.r8.errors.Unreachable;
import com.android.tools.r8.graph.AppInfo;
-import com.android.tools.r8.graph.DexClass;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.ir.code.NumericType;
import com.android.tools.r8.ir.code.Value;
-import com.android.tools.r8.utils.LRUCacheTable;
-import com.google.common.collect.ImmutableSet;
-import java.util.ArrayDeque;
-import java.util.HashSet;
-import java.util.IdentityHashMap;
-import java.util.Map;
-import java.util.Queue;
-import java.util.Set;
/**
* The base abstraction of lattice elements for local type analysis.
@@ -25,6 +16,10 @@
public abstract class TypeLatticeElement {
public static final BottomTypeLatticeElement BOTTOM = BottomTypeLatticeElement.getInstance();
public static final TopTypeLatticeElement TOP = TopTypeLatticeElement.getInstance();
+ static final BooleanTypeLatticeElement BOOLEAN = BooleanTypeLatticeElement.getInstance();
+ static final ByteTypeLatticeElement BYTE = ByteTypeLatticeElement.getInstance();
+ static final ShortTypeLatticeElement SHORT = ShortTypeLatticeElement.getInstance();
+ static final CharTypeLatticeElement CHAR = CharTypeLatticeElement.getInstance();
public static final IntTypeLatticeElement INT = IntTypeLatticeElement.getInstance();
public static final FloatTypeLatticeElement FLOAT = FloatTypeLatticeElement.getInstance();
public static final SingleTypeLatticeElement SINGLE = SingleTypeLatticeElement.getInstance();
@@ -34,8 +29,6 @@
public static final ReferenceTypeLatticeElement NULL =
ReferenceTypeLatticeElement.getNullTypeLatticeElement();
- private static final LRUCacheTable<Set<DexType>, Set<DexType>, Set<DexType>>
- leastUpperBoundOfInterfacesTable = LRUCacheTable.create(8, 8);
// TODO(b/72693244): Switch to NullLatticeElement.
private final boolean isNullable;
@@ -106,8 +99,7 @@
}
if (isPrimitive()) {
return other.isPrimitive()
- ? PrimitiveTypeLatticeElement.join(
- asPrimitiveTypeLatticeElement(), other.asPrimitiveTypeLatticeElement())
+ ? asPrimitiveTypeLatticeElement().join(other.asPrimitiveTypeLatticeElement())
: TOP;
}
if (other.isPrimitive()) {
@@ -124,157 +116,17 @@
// From now on, getClass() == other.getClass()
if (isArrayType()) {
assert other.isArrayType();
- ArrayTypeLatticeElement a1 = asArrayTypeLatticeElement();
- ArrayTypeLatticeElement a2 = other.asArrayTypeLatticeElement();
- // Identical types are the same elements
- if (a1.getArrayType() == a2.getArrayType()) {
- return a1.isNullable() ? a1 : a2;
- }
- // If non-equal, find the inner-most reference types for each.
- DexType a1BaseReferenceType = a1.getArrayBaseType(appInfo.dexItemFactory);
- int a1Nesting = a1.getNesting();
- if (a1BaseReferenceType.isPrimitiveType()) {
- a1Nesting--;
- a1BaseReferenceType = appInfo.dexItemFactory.objectType;
- }
- DexType a2BaseReferenceType = a2.getArrayBaseType(appInfo.dexItemFactory);
- int a2Nesting = a2.getNesting();
- if (a2BaseReferenceType.isPrimitiveType()) {
- a2Nesting--;
- a2BaseReferenceType = appInfo.dexItemFactory.objectType;
- }
- assert a1BaseReferenceType.isClassType() && a2BaseReferenceType.isClassType();
- // If any nestings hit zero object is the join.
- if (a1Nesting == 0 || a2Nesting == 0) {
- return objectClassType(appInfo, isNullable);
- }
- // If the nestings differ the join is the smallest nesting level.
- if (a1Nesting != a2Nesting) {
- int min = Math.min(a1Nesting, a2Nesting);
- return objectArrayType(appInfo, min, isNullable);
- }
- // For different class element types, compute the least upper bound of element types.
- DexType baseTypeLub =
- a1BaseReferenceType.computeLeastUpperBoundOfClasses(appInfo, a2BaseReferenceType);
- // Create the full array type.
- DexType arrayTypeLub = appInfo.dexItemFactory.createArrayType(a1Nesting, baseTypeLub);
- return fromDexType(arrayTypeLub, isNullable, appInfo);
+ TypeLatticeElement join =
+ asArrayTypeLatticeElement().join(other.asArrayTypeLatticeElement(), appInfo);
+ return join != null ? join : (isNullable() ? this : other);
}
if (isClassType()) {
assert other.isClassType();
- ClassTypeLatticeElement c1 = asClassTypeLatticeElement();
- ClassTypeLatticeElement c2 = other.asClassTypeLatticeElement();
- DexType lubType =
- c1.getClassType().computeLeastUpperBoundOfClasses(appInfo, c2.getClassType());
- Set<DexType> c1lubItfs = c1.getInterfaces();
- Set<DexType> c2lubItfs = c2.getInterfaces();
- Set<DexType> lubItfs = null;
- if (c1lubItfs.size() == c2lubItfs.size() && c1lubItfs.containsAll(c2lubItfs)) {
- lubItfs = c1lubItfs;
- }
- if (lubItfs == null) {
- lubItfs = computeLeastUpperBoundOfInterfaces(appInfo, c1lubItfs, c2lubItfs);
- }
- return new ClassTypeLatticeElement(lubType, isNullable, lubItfs);
+ return asClassTypeLatticeElement().join(other.asClassTypeLatticeElement(), appInfo);
}
throw new Unreachable("unless a new type lattice is introduced.");
}
- private enum InterfaceMarker {
- LEFT,
- RIGHT
- }
-
- private static class InterfaceWithMarker {
- final DexType itf;
- final InterfaceMarker marker;
-
- InterfaceWithMarker(DexType itf, InterfaceMarker marker) {
- this.itf = itf;
- this.marker = marker;
- }
- }
-
- public static Set<DexType> computeLeastUpperBoundOfInterfaces(
- AppInfo appInfo, Set<DexType> s1, Set<DexType> s2) {
- Set<DexType> cached = leastUpperBoundOfInterfacesTable.get(s1, s2);
- if (cached != null) {
- return cached;
- }
- cached = leastUpperBoundOfInterfacesTable.get(s2, s1);
- if (cached != null) {
- return cached;
- }
- Map<DexType, Set<InterfaceMarker>> seen = new IdentityHashMap<>();
- Queue<InterfaceWithMarker> worklist = new ArrayDeque<>();
- for (DexType itf1 : s1) {
- worklist.add(new InterfaceWithMarker(itf1, InterfaceMarker.LEFT));
- }
- for (DexType itf2 : s2) {
- worklist.add(new InterfaceWithMarker(itf2, InterfaceMarker.RIGHT));
- }
- while (!worklist.isEmpty()) {
- InterfaceWithMarker item = worklist.poll();
- DexType itf = item.itf;
- InterfaceMarker marker = item.marker;
- Set<InterfaceMarker> markers = seen.computeIfAbsent(itf, k -> new HashSet<>());
- // If this interface is a lower one in this set, skip.
- if (markers.contains(marker)) {
- continue;
- }
- // If this interface is already visited by the other set, add marker for this set and skip.
- if (markers.size() == 1) {
- markers.add(marker);
- continue;
- }
- // Otherwise, this type is freshly visited.
- markers.add(marker);
- // Put super interfaces into the worklist.
- DexClass itfClass = appInfo.definitionFor(itf);
- if (itfClass != null) {
- for (DexType superItf : itfClass.interfaces.values) {
- markers = seen.computeIfAbsent(superItf, k -> new HashSet<>());
- if (!markers.contains(marker)) {
- worklist.add(new InterfaceWithMarker(superItf, marker));
- }
- }
- }
- }
-
- ImmutableSet.Builder<DexType> commonBuilder = ImmutableSet.builder();
- for (Map.Entry<DexType, Set<InterfaceMarker>> entry : seen.entrySet()) {
- // Keep commonly visited interfaces only
- if (entry.getValue().size() < 2) {
- continue;
- }
- commonBuilder.add(entry.getKey());
- }
- Set<DexType> commonlyVisited = commonBuilder.build();
-
- ImmutableSet.Builder<DexType> lubBuilder = ImmutableSet.builder();
- for (DexType itf : commonlyVisited) {
- // If there is a strict sub interface of this interface, it is not the least element.
- boolean notTheLeast = false;
- for (DexType other : commonlyVisited) {
- if (other.isStrictSubtypeOf(itf, appInfo)) {
- notTheLeast = true;
- break;
- }
- }
- if (notTheLeast) {
- continue;
- }
- lubBuilder.add(itf);
- }
- Set<DexType> lub = lubBuilder.build();
- // Cache the computation result only if the given two sets of interfaces are different.
- if (s1.size() != s2.size() || !s1.containsAll(s2)) {
- synchronized (leastUpperBoundOfInterfacesTable) {
- leastUpperBoundOfInterfacesTable.put(s1, s2, lub);
- }
- }
- return lub;
- }
public static TypeLatticeElement join(
Iterable<TypeLatticeElement> typeLattices, AppInfo appInfo) {
@@ -383,6 +235,22 @@
return false;
}
+ boolean isBoolean() {
+ return false;
+ }
+
+ boolean isByte() {
+ return false;
+ }
+
+ boolean isShort() {
+ return false;
+ }
+
+ boolean isChar() {
+ return false;
+ }
+
public boolean isInt() {
return false;
}
@@ -410,6 +278,13 @@
|| isBottom();
}
+ public boolean isFineGrainedType() {
+ return isBoolean()
+ || isByte()
+ || isShort()
+ || isChar();
+ }
+
/**
* Should use {@link #isConstantNull()} or {@link #isDefinitelyNull()} instead.
*/
@@ -444,14 +319,17 @@
return isWide() ? 2 : 1;
}
- static TypeLatticeElement objectClassType(AppInfo appInfo, boolean isNullable) {
- return fromDexType(appInfo.dexItemFactory.objectType, isNullable, appInfo);
+ static ClassTypeLatticeElement objectClassType(AppInfo appInfo, boolean isNullable) {
+ return fromDexType(appInfo.dexItemFactory.objectType, isNullable, appInfo)
+ .asClassTypeLatticeElement();
}
- static TypeLatticeElement objectArrayType(AppInfo appInfo, int nesting, boolean isNullable) {
+ static ArrayTypeLatticeElement objectArrayType(AppInfo appInfo, boolean isNullable) {
return fromDexType(
- appInfo.dexItemFactory.createArrayType(nesting, appInfo.dexItemFactory.objectType),
- isNullable, appInfo);
+ appInfo.dexItemFactory.createArrayType(1, appInfo.dexItemFactory.objectType),
+ isNullable,
+ appInfo)
+ .asArrayTypeLatticeElement();
}
public static TypeLatticeElement classClassType(AppInfo appInfo) {
@@ -463,11 +341,16 @@
}
public static TypeLatticeElement fromDexType(DexType type, boolean isNullable, AppInfo appInfo) {
+ return fromDexType(type, isNullable, appInfo, false);
+ }
+
+ public static TypeLatticeElement fromDexType(
+ DexType type, boolean isNullable, AppInfo appInfo, boolean asArrayElementType) {
if (type == DexItemFactory.nullValueType) {
return NULL;
}
if (type.isPrimitiveType()) {
- return PrimitiveTypeLatticeElement.fromDexType(type);
+ return PrimitiveTypeLatticeElement.fromDexType(type, asArrayElementType);
}
return appInfo.dexItemFactory.createReferenceTypeLatticeElement(type, isNullable, appInfo);
}
@@ -496,14 +379,6 @@
|| (isWide() && other.isWide());
}
- public static TypeLatticeElement newArray(DexType arrayType, boolean isNullable) {
- return new ArrayTypeLatticeElement(arrayType, isNullable);
- }
-
- public TypeLatticeElement arrayGet(AppInfo appInfo) {
- return BOTTOM;
- }
-
public TypeLatticeElement checkCast(AppInfo appInfo, DexType castType) {
TypeLatticeElement castTypeLattice = fromDexType(castType, isNullable(), appInfo);
if (lessThanOrEqual(castTypeLattice, appInfo)) {
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 2549eaa..3879639 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
@@ -19,6 +19,7 @@
import com.android.tools.r8.graph.AppInfo;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.ir.analysis.type.ArrayTypeLatticeElement;
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;
@@ -170,29 +171,47 @@
@Override
public TypeLatticeElement evaluate(AppInfo appInfo) {
+ ArrayTypeLatticeElement arrayTypeLattice = array().getTypeLattice().isArrayType()
+ ? array().getTypeLattice().asArrayTypeLatticeElement()
+ : null;
switch (getMemberType()) {
case OBJECT:
// If the out-type of the array is bottom (the input array must be definitely null), then
// the instruction cannot return. For now we return NULL as the type to ensure we have a
// type consistent witness for the out-value type. We could consider returning bottom in
// this case as the value is indeed empty, i.e., the instruction will always fail.
- TypeLatticeElement outType = array().getTypeLattice().arrayGet(appInfo);
- return outType.isBottom() ? TypeLatticeElement.NULL : outType;
+ TypeLatticeElement valueType = arrayTypeLattice == null
+ ? TypeLatticeElement.NULL
+ : arrayTypeLattice.getArrayMemberTypeAsValueType();
+ assert valueType.isReference();
+ return valueType;
case BOOLEAN:
case BYTE:
case CHAR:
case SHORT:
case INT:
+ assert arrayTypeLattice == null
+ || arrayTypeLattice.getArrayMemberTypeAsValueType().isInt();
return TypeLatticeElement.INT;
case FLOAT:
+ assert arrayTypeLattice == null
+ || arrayTypeLattice.getArrayMemberTypeAsValueType().isFloat();
return TypeLatticeElement.FLOAT;
case LONG:
+ assert arrayTypeLattice == null
+ || arrayTypeLattice.getArrayMemberTypeAsValueType().isLong();
return TypeLatticeElement.LONG;
case DOUBLE:
+ assert arrayTypeLattice == null
+ || arrayTypeLattice.getArrayMemberTypeAsValueType().isDouble();
return TypeLatticeElement.DOUBLE;
case INT_OR_FLOAT:
+ assert arrayTypeLattice == null
+ || arrayTypeLattice.getArrayMemberTypeAsValueType().isSingle();
return checkConstraint(dest(), ValueTypeConstraint.INT_OR_FLOAT);
case LONG_OR_DOUBLE:
+ assert arrayTypeLattice == null
+ || arrayTypeLattice.getArrayMemberTypeAsValueType().isWide();
return checkConstraint(dest(), ValueTypeConstraint.LONG_OR_DOUBLE);
default:
throw new Unreachable("Unexpected member type: " + getMemberType());
diff --git a/src/main/java/com/android/tools/r8/ir/code/IRCode.java b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
index e11f1bd..6022b6d 100644
--- a/src/main/java/com/android/tools/r8/ir/code/IRCode.java
+++ b/src/main/java/com/android/tools/r8/ir/code/IRCode.java
@@ -679,6 +679,7 @@
return verifySSATypeLattice(
v -> {
assert v.getTypeLattice().isPreciseType();
+ assert !v.getTypeLattice().isFineGrainedType();
// For now we assume no bottom types on IR values. We may want to reconsider this for
// representing unreachable code.
assert !v.getTypeLattice().isBottom();
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 3738542..a008185 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
@@ -1208,7 +1208,7 @@
DexType outBaseType =
outTypeLatticeElement
.asArrayTypeLatticeElement()
- .getArrayType()
+ .getArrayType(appInfo.dexItemFactory)
.toBaseType(appInfo.dexItemFactory);
assert graphLense.lookupType(outBaseType) == outBaseType;
} else if (outTypeLatticeElement.isClassType()) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java b/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
index cfd3b1d..2f28110 100644
--- a/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
+++ b/src/main/java/com/android/tools/r8/ir/code/InvokeMultiNewArray.java
@@ -67,7 +67,7 @@
@Override
public TypeLatticeElement evaluate(AppInfo appInfo) {
- return TypeLatticeElement.newArray(type, false);
+ return TypeLatticeElement.fromDexType(type, false, appInfo);
}
@Override
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 df74e17..c49650a 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
@@ -97,7 +97,7 @@
@Override
public TypeLatticeElement evaluate(AppInfo appInfo) {
- return TypeLatticeElement.newArray(type, false);
+ return TypeLatticeElement.fromDexType(type, false, appInfo);
}
@Override
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 95a9225..09ea5af 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
@@ -107,6 +107,6 @@
@Override
public TypeLatticeElement evaluate(AppInfo appInfo) {
- return TypeLatticeElement.newArray(type, false);
+ return TypeLatticeElement.fromDexType(type, false, appInfo);
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/code/ValueTypeConstraint.java b/src/main/java/com/android/tools/r8/ir/code/ValueTypeConstraint.java
index 8371375..9c376fb 100644
--- a/src/main/java/com/android/tools/r8/ir/code/ValueTypeConstraint.java
+++ b/src/main/java/com/android/tools/r8/ir/code/ValueTypeConstraint.java
@@ -134,7 +134,7 @@
if (typeLatticeElement.isReference()) {
return OBJECT;
}
- if (typeLatticeElement.isInt()) {
+ if (typeLatticeElement.isFineGrainedType() || typeLatticeElement.isInt()) {
return INT;
}
if (typeLatticeElement.isFloat()) {
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/TypeConstraintResolver.java b/src/main/java/com/android/tools/r8/ir/conversion/TypeConstraintResolver.java
index f2fe507..1ed85c4 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/TypeConstraintResolver.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/TypeConstraintResolver.java
@@ -180,8 +180,7 @@
if (array.getTypeLattice().isArrayType()) {
// If the array type is known it uniquely defines the actual member type.
ArrayTypeLatticeElement arrayType = array.getTypeLattice().asArrayTypeLatticeElement();
- constraint =
- ValueTypeConstraint.fromDexType(arrayType.getArrayElementType(builder.getFactory()));
+ constraint = ValueTypeConstraint.fromTypeLattice(arrayType.getArrayMemberTypeAsValueType());
} else {
// If not, e.g., the array input is null, the canonical value determines the final type.
constraint = getCanonicalTypeConstraint(canonical, true);
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 553eaa2..3424431 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
@@ -1955,7 +1955,7 @@
}
DexType type = inType.isClassType()
? inType.asClassTypeLatticeElement().getClassType()
- : inType.asArrayTypeLatticeElement().getArrayType();
+ : inType.asArrayTypeLatticeElement().getArrayType(appInfo.dexItemFactory);
DexType baseType = type.toBaseType(appInfo.dexItemFactory);
// Make sure base type is a class type.
if (!baseType.isClassType()) {
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/ArrayTypeTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/ArrayTypeTest.java
index ac73d7d..8e38855 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/ArrayTypeTest.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/ArrayTypeTest.java
@@ -5,15 +5,18 @@
package com.android.tools.r8.ir.analysis.type;
import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.FLOAT;
+import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.INT;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import com.android.tools.r8.graph.AppInfo;
import com.android.tools.r8.ir.code.ArrayGet;
import com.android.tools.r8.ir.code.ArrayPut;
+import com.android.tools.r8.ir.code.BasicBlock;
import com.android.tools.r8.ir.code.ConstNumber;
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 java.util.function.Consumer;
import org.junit.Test;
@@ -34,6 +37,13 @@
buildAndCheckIR("nestedArrayTest", nestedArrayTestInspector(appInfo));
}
+ @Test
+ public void testJoinOfArraysForPrimitivesSmallerThanInt() throws Exception {
+ buildAndCheckIR(
+ "joinOfArraysForPrimitivesSmallerThanInt",
+ joinOfArraysForPrimitivesSmallerThanInt(appInfo));
+ }
+
private static Consumer<IRCode> arrayTestInspector(AppInfo appInfo) {
return code -> {
Iterable<Instruction> instructions = code::instructionIterator;
@@ -53,9 +63,7 @@
assertTrue(array.getTypeLattice().isArrayType());
ArrayTypeLatticeElement arrayType = array.getTypeLattice().asArrayTypeLatticeElement();
- TypeLatticeElement elementType =
- TypeLatticeElement.fromDexType(
- arrayType.getArrayElementType(appInfo.dexItemFactory), true, appInfo);
+ TypeLatticeElement elementType = arrayType.getArrayMemberTypeAsMemberType();
assertEquals(FLOAT, elementType);
assertEquals(FLOAT, value.getTypeLattice());
@@ -75,9 +83,7 @@
assertTrue(array.getTypeLattice().isArrayType());
ArrayTypeLatticeElement arrayType = array.getTypeLattice().asArrayTypeLatticeElement();
- TypeLatticeElement elementType =
- TypeLatticeElement.fromDexType(
- arrayType.getArrayElementType(appInfo.dexItemFactory), true, appInfo);
+ TypeLatticeElement elementType = arrayType.getArrayMemberTypeAsMemberType();
assertEquals(FLOAT, elementType);
assertEquals(FLOAT, value.getTypeLattice());
@@ -94,6 +100,19 @@
};
}
+ private static Consumer<IRCode> joinOfArraysForPrimitivesSmallerThanInt(AppInfo appInfo) {
+ return code -> {
+ int phiCount = 0;
+ for (BasicBlock block : code.blocks) {
+ for (Phi phi : block.getPhis()) {
+ phiCount++;
+ assertEquals(INT, phi.getTypeLattice());
+ }
+ }
+ assertEquals(2, phiCount);
+ };
+ }
+
static class TestClass {
public static void arrayTest() {
@@ -119,5 +138,14 @@
float x = 1f;
array[0][0] = x;
}
+
+ public static void joinOfArraysForPrimitivesSmallerThanInt(
+ boolean predicate, byte[] bs, char[] cs) {
+ char s = (char) (predicate ? bs[0] : cs[0]);
+ byte b = (predicate ? bs[0] : bs[0]);
+ if (s == b) {
+ System.out.println("Meh, just to use variables.");
+ }
+ }
}
}
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
index bd0f8fb..35ebae5 100644
--- 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
@@ -158,9 +158,12 @@
forEachOutValue(irCode, (v, l) -> {
if (l.isArrayType()) {
ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
+ assertEquals(1, lattice.getNesting());
+ TypeLatticeElement elementTypeLattice = lattice.getArrayMemberTypeAsMemberType();
+ assertTrue(elementTypeLattice.isClassType());
assertEquals(
appInfo.dexItemFactory.stringType,
- lattice.getArrayElementType(appInfo.dexItemFactory));
+ elementTypeLattice.asClassTypeLatticeElement().getClassType());
assertEquals(v.definition.isArgument(), l.isNullable());
} else if (l.isClassType()) {
verifyClassTypeLattice(expectedLattices, mainClass, v, l);
@@ -184,9 +187,12 @@
forEachOutValue(irCode, (v, l) -> {
if (l.isArrayType()) {
ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
+ assertEquals(1, lattice.getNesting());
+ TypeLatticeElement elementTypeLattice = lattice.getArrayMemberTypeAsMemberType();
+ assertTrue(elementTypeLattice.isClassType());
assertEquals(
appInfo.dexItemFactory.stringType,
- lattice.getArrayElementType(appInfo.dexItemFactory));
+ elementTypeLattice.asClassTypeLatticeElement().getClassType());
assertEquals(v.definition.isArgument(), l.isNullable());
} else if (l.isClassType()) {
verifyClassTypeLattice(expectedLattices, mainClass, v, l);
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
index e0d7f71..09f6a01 100644
--- 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
@@ -189,7 +189,7 @@
if (v == finalArray) {
assertTrue(l.isArrayType());
ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
- assertTrue(lattice.getArrayType().isPrimitiveArrayType());
+ assertTrue(lattice.getArrayMemberTypeAsMemberType().isPrimitive());
assertEquals(1, lattice.getNesting());
assertFalse(lattice.isNullable());
}
@@ -222,7 +222,7 @@
if (v == finalArray) {
assertTrue(l.isArrayType());
ArrayTypeLatticeElement lattice = l.asArrayTypeLatticeElement();
- assertTrue(lattice.getArrayType().isPrimitiveArrayType());
+ assertTrue(lattice.getArrayMemberTypeAsMemberType().isPrimitive());
assertEquals(1, lattice.getNesting());
assertFalse(lattice.isNullable());
}
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTestBase.java b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTestBase.java
index e444e93..5cd64b9 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTestBase.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeAnalysisTestBase.java
@@ -22,7 +22,7 @@
import java.util.function.Predicate;
import org.junit.Before;
-public class TypeAnalysisTestBase extends TestBase {
+public abstract class TypeAnalysisTestBase extends TestBase {
private final AndroidApp app;
private final String className;
diff --git a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
index d1b3f9e..fbfc09b 100644
--- a/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
+++ b/src/test/java/com/android/tools/r8/ir/analysis/type/TypeLatticeTest.java
@@ -3,7 +3,7 @@
// BSD-style license that can be found in the LICENSE file.
package com.android.tools.r8.ir.analysis.type;
-import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.computeLeastUpperBoundOfInterfaces;
+import static com.android.tools.r8.ir.analysis.type.ClassTypeLatticeElement.computeLeastUpperBoundOfInterfaces;
import static com.android.tools.r8.ir.analysis.type.TypeLatticeElement.fromDexType;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
@@ -293,9 +293,41 @@
@Test
public void joinInterfaceArrayAndImplementerArray() {
+ DexType queue = factory.createType("Ljava/util/Queue;");
+ DexType arrayDeque = factory.createType("Ljava/util/ArrayDeque;");
assertEquals(
- // TODO(b/119181813): This should be array(1, charSequence)
- array(1, factory.objectType),
+ array(1, queue),
+ join(
+ array(1, queue),
+ array(1, arrayDeque)));
+ assertEquals(
+ array(2, queue),
+ join(
+ array(2, arrayDeque),
+ array(2, queue)));
+
+ DexType type = factory.createType("Ljava/lang/reflect/Type;");
+ DexType wType = factory.createType("Ljava/lang/reflect/WildcardType;");
+ DexType pType = factory.createType("Ljava/lang/reflect/ParameterizedType;");
+ assertEquals(
+ array(1, type),
+ join(
+ array(1, wType),
+ array(1, pType)));
+ assertEquals(
+ array(2, type),
+ join(
+ array(2, wType),
+ array(2, factory.classType)));
+ assertEquals(
+ array(1, type),
+ join(
+ array(1, wType),
+ array(1, pType),
+ array(1, factory.classType)));
+
+ assertEquals(
+ array(1, factory.charSequenceType),
join(
array(1, factory.charSequenceType),
array(1, factory.stringType)));
@@ -347,6 +379,18 @@
join(
array(1, factory.longType),
array(1, factory.intType)));
+
+ // Test primitive types smaller than int.
+ assertEquals(
+ element(factory.objectType),
+ join(
+ array(1, factory.intType),
+ array(1, factory.byteType)));
+ assertEquals(
+ element(factory.objectType),
+ join(
+ array(1, factory.charType),
+ array(1, factory.shortType)));
}
@Test
@@ -397,10 +441,10 @@
@Test
public void joinDistinctTypesClassArrays() {
assertEquals(
- array(3, factory.objectType),
+ array(3, factory.serializableType),
join(
array(3, factory.stringType),
- array(3, factory.stringBuilderType)));
+ array(3, factory.classType)));
}
@Test
diff --git a/src/test/java/com/android/tools/r8/shaking/FieldTypeTest.java b/src/test/java/com/android/tools/r8/shaking/FieldTypeTest.java
index 128b2ac..f8d8e7c 100644
--- a/src/test/java/com/android/tools/r8/shaking/FieldTypeTest.java
+++ b/src/test/java/com/android/tools/r8/shaking/FieldTypeTest.java
@@ -12,8 +12,6 @@
import com.android.tools.r8.TestBase;
import com.android.tools.r8.ToolHelper;
-import com.android.tools.r8.ToolHelper.DexVm;
-import com.android.tools.r8.ToolHelper.DexVm.Version;
import com.android.tools.r8.ToolHelper.ProcessResult;
import com.android.tools.r8.VmTestRunner;
import com.android.tools.r8.jasmin.JasminBuilder;
@@ -203,24 +201,25 @@
assertEquals(0, javaResult.exitCode);
assertThat(javaResult.stdout, containsString(impl2.name));
- AndroidApp processedApp = compileWithR8(jasminBuilder.build(), proguardConfig,
- // Disable inlining to avoid the (short) tested method from being inlined and then removed.
- internalOptions -> internalOptions.enableInlining = false);
+ AndroidApp processedApp = compileWithR8(
+ jasminBuilder.build(),
+ proguardConfig,
+ internalOptions -> {
+ // Disable inlining to avoid the (short) tested method from being inlined and then
+ // removed.
+ internalOptions.enableInlining = false;
+ internalOptions.testing.allowTypeErrors = true;
+ });
// Run processed (output) program on ART
ProcessResult artResult = runOnArtRaw(processedApp, mainClassName);
assertNotEquals(0, artResult.exitCode);
- assertEquals(-1, artResult.stderr.indexOf("DoFieldPut"));
- DexVm.Version currentVersion = ToolHelper.getDexVm().getVersion();
- String errorMessage =
- currentVersion.isNewerThan(Version.V4_4_4)
- ? "type Precise Reference: Impl1[] but expected Reference: Itf1[]"
- : "storing type '[LImpl1;' into field type '[LItf1;'";
- assertThat(artResult.stderr, containsString(errorMessage));
+ assertThat(artResult.stderr, containsString("java.lang.NullPointerException"));
+ assertThat(artResult.stderr, not(containsString("DoFieldPut")));
CodeInspector inspector = new CodeInspector(processedApp);
ClassSubject itf1Subject = inspector.clazz(itf1.name);
- assertThat(itf1Subject, isPresent());
+ assertThat(itf1Subject, not(isPresent()));
}
}
