diff options
Diffstat (limited to 'src/main/java/com')
27 files changed, 529 insertions, 483 deletions
diff --git a/src/main/java/com/android/tools/r8/compatdx/CompatDx.java b/src/main/java/com/android/tools/r8/compatdx/CompatDx.java index a547d126e..b77493f59 100644 --- a/src/main/java/com/android/tools/r8/compatdx/CompatDx.java +++ b/src/main/java/com/android/tools/r8/compatdx/CompatDx.java @@ -294,9 +294,12 @@ public class CompatDx { multiDex = options.has(spec.multiDex); mainDexList = options.valueOf(spec.mainDexList); minimalMainDex = options.has(spec.minimalMainDex); - minApiLevel = options.has(spec.minApiLevel) - ? options.valueOf(spec.minApiLevel) - : Constants.DEFAULT_ANDROID_API; + if (options.has(spec.minApiLevel)) { + List<Integer> allMinApiLevels = options.valuesOf(spec.minApiLevel); + minApiLevel = allMinApiLevels.get(allMinApiLevels.size() - 1); + } else { + minApiLevel = Constants.DEFAULT_ANDROID_API; + } inputList = options.valueOf(spec.inputList); inputs = ImmutableList.copyOf(options.valuesOf(spec.inputs)); maxIndexNumber = options.valueOf(spec.maxIndexNumber); diff --git a/src/main/java/com/android/tools/r8/graph/Code.java b/src/main/java/com/android/tools/r8/graph/Code.java index dca5e02e9..84d6d5da6 100644 --- a/src/main/java/com/android/tools/r8/graph/Code.java +++ b/src/main/java/com/android/tools/r8/graph/Code.java @@ -34,15 +34,15 @@ public abstract class Code extends CanonicalizedDexItem { } public DexCode asDexCode() { - throw new Unreachable(); + throw new Unreachable(getClass().getCanonicalName() + ".asDexCode()"); } public JarCode asJarCode() { - throw new Unreachable(); + throw new Unreachable(getClass().getCanonicalName() + ".asJarCode()"); } public OutlineCode asOutlineCode() { - throw new Unreachable(); + throw new Unreachable(getClass().getCanonicalName() + ".asOutlineCode()"); } @Override diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotation.java b/src/main/java/com/android/tools/r8/graph/DexAnnotation.java index 55aa9868a..1afd77ea3 100644 --- a/src/main/java/com/android/tools/r8/graph/DexAnnotation.java +++ b/src/main/java/com/android/tools/r8/graph/DexAnnotation.java @@ -16,19 +16,6 @@ import java.util.ArrayList; import java.util.List; public class DexAnnotation extends DexItem { - // Dex system annotations. - // See https://source.android.com/devices/tech/dalvik/dex-format.html#system-annotation - private static final String ANNOTATION_DEFAULT_DESCRIPTOR = - "Ldalvik/annotation/AnnotationDefault;"; - private static final String ENCLOSING_CLASS_DESCRIPTOR = "Ldalvik/annotation/EnclosingClass;"; - private static final String ENCLOSING_METHOD_DESCRIPTOR = "Ldalvik/annotation/EnclosingMethod;"; - private static final String INNER_CLASS_DESCRIPTOR = "Ldalvik/annotation/InnerClass;"; - private static final String MEMBER_CLASSES_DESCRIPTOR = "Ldalvik/annotation/MemberClasses;"; - private static final String METHOD_PARAMETERS_DESCRIPTOR = "Ldalvik/annotation/MethodParameters;"; - private static final String SIGNATURE_DESCRIPTOR = "Ldalvik/annotation/Signature;"; - private static final String SOURCE_DEBUG_EXTENSION = "Ldalvik/annotation/SourceDebugExtension;"; - private static final String THROWS_DESCRIPTOR = "Ldalvik/annotation/Throws;"; - public static final int VISIBILITY_BUILD = 0x00; public static final int VISIBILITY_RUNTIME = 0x01; public static final int VISIBILITY_SYSTEM = 0x02; @@ -74,37 +61,36 @@ public class DexAnnotation extends DexItem { public static DexAnnotation createEnclosingClassAnnotation(DexType enclosingClass, DexItemFactory factory) { - return createSystemValueAnnotation(ENCLOSING_CLASS_DESCRIPTOR, factory, + return createSystemValueAnnotation(factory.annotationEnclosingClass, factory, new DexValueType(enclosingClass)); } public static DexAnnotation createEnclosingMethodAnnotation(DexMethod enclosingMethod, DexItemFactory factory) { - return createSystemValueAnnotation(ENCLOSING_METHOD_DESCRIPTOR, factory, + return createSystemValueAnnotation(factory.annotationEnclosingMethod, factory, new DexValueMethod(enclosingMethod)); } - public static boolean isEnclosingClassAnnotation(DexAnnotation annotation) { - return annotation.annotation.type.toDescriptorString().equals(ENCLOSING_CLASS_DESCRIPTOR); - } - - public static boolean isEnclosingMethodAnnotation(DexAnnotation annotation) { - return annotation.annotation.type.toDescriptorString().equals(ENCLOSING_METHOD_DESCRIPTOR); + public static boolean isEnclosingClassAnnotation(DexAnnotation annotation, + DexItemFactory factory) { + return annotation.annotation.type == factory.annotationEnclosingClass; } - public static boolean isEnclosingAnnotation(DexAnnotation annotation) { - return isEnclosingClassAnnotation(annotation) || isEnclosingMethodAnnotation(annotation); + public static boolean isEnclosingMethodAnnotation(DexAnnotation annotation, + DexItemFactory factory) { + return annotation.annotation.type == factory.annotationEnclosingMethod; } - public static boolean isInnerClassesAnnotation(DexAnnotation annotation) { - return annotation.annotation.type.toDescriptorString().equals(MEMBER_CLASSES_DESCRIPTOR) - || annotation.annotation.type.toDescriptorString().equals(INNER_CLASS_DESCRIPTOR); + public static boolean isInnerClassesAnnotation(DexAnnotation annotation, + DexItemFactory factory) { + return annotation.annotation.type == factory.annotationMemberClasses + || annotation.annotation.type == factory.annotationInnerClass; } public static DexAnnotation createInnerClassAnnotation(String clazz, int access, DexItemFactory factory) { return new DexAnnotation(VISIBILITY_SYSTEM, - new DexEncodedAnnotation(factory.createType(INNER_CLASS_DESCRIPTOR), + new DexEncodedAnnotation(factory.annotationInnerClass, new DexAnnotationElement[]{ new DexAnnotationElement( factory.createString("accessFlags"), @@ -123,14 +109,14 @@ public class DexAnnotation extends DexItem { for (int i = 0; i < classes.size(); i++) { values[i] = new DexValueType(classes.get(i)); } - return createSystemValueAnnotation(MEMBER_CLASSES_DESCRIPTOR, factory, + return createSystemValueAnnotation(factory.annotationMemberClasses, factory, new DexValueArray(values)); } public static DexAnnotation createSourceDebugExtensionAnnotation(DexValue value, DexItemFactory factory) { return new DexAnnotation(VISIBILITY_SYSTEM, - new DexEncodedAnnotation(factory.createType(SOURCE_DEBUG_EXTENSION), + new DexEncodedAnnotation(factory.annotationSourceDebugExtension, new DexAnnotationElement[] { new DexAnnotationElement(factory.createString("value"), value) })); @@ -140,7 +126,7 @@ public class DexAnnotation extends DexItem { DexValue[] accessFlags, DexItemFactory factory) { assert names.length == accessFlags.length; return new DexAnnotation(VISIBILITY_SYSTEM, - new DexEncodedAnnotation(factory.createType(METHOD_PARAMETERS_DESCRIPTOR), + new DexEncodedAnnotation(factory.annotationMethodParameters, new DexAnnotationElement[]{ new DexAnnotationElement( factory.createString("names"), @@ -153,7 +139,7 @@ public class DexAnnotation extends DexItem { public static DexAnnotation createAnnotationDefaultAnnotation(DexType type, List<DexAnnotationElement> defaults, DexItemFactory factory) { - return createSystemValueAnnotation(ANNOTATION_DEFAULT_DESCRIPTOR, factory, + return createSystemValueAnnotation(factory.annotationDefault, factory, new DexValueAnnotation( new DexEncodedAnnotation(type, defaults.toArray(new DexAnnotationElement[defaults.size()]))) @@ -161,34 +147,38 @@ public class DexAnnotation extends DexItem { } public static DexAnnotation createSignatureAnnotation(String signature, DexItemFactory factory) { - return createSystemValueAnnotation(SIGNATURE_DESCRIPTOR, factory, + return createSystemValueAnnotation(factory.annotationSignature, factory, compressSignature(signature, factory)); } public static DexAnnotation createThrowsAnnotation(DexValue[] exceptions, DexItemFactory factory) { - return createSystemValueAnnotation(THROWS_DESCRIPTOR, factory, new DexValueArray(exceptions)); + return createSystemValueAnnotation(factory.annotationThrows, factory, + new DexValueArray(exceptions)); } - private static DexAnnotation createSystemValueAnnotation(String desc, DexItemFactory factory, + private static DexAnnotation createSystemValueAnnotation(DexType type, DexItemFactory factory, DexValue value) { return new DexAnnotation(VISIBILITY_SYSTEM, - new DexEncodedAnnotation(factory.createType(desc), new DexAnnotationElement[] { + new DexEncodedAnnotation(type, new DexAnnotationElement[]{ new DexAnnotationElement(factory.createString("value"), value) })); } - public static boolean isThrowingAnnotation(DexAnnotation annotation) { - return annotation.annotation.type.toDescriptorString().equals(THROWS_DESCRIPTOR); + public static boolean isThrowingAnnotation(DexAnnotation annotation, + DexItemFactory factory) { + return annotation.annotation.type == factory.annotationThrows; } - public static boolean isSignatureAnnotation(DexAnnotation annotation) { - return annotation.annotation.type.toDescriptorString().equals(SIGNATURE_DESCRIPTOR); + public static boolean isSignatureAnnotation(DexAnnotation annotation, + DexItemFactory factory) { + return annotation.annotation.type == factory.annotationSignature; } - public static boolean isSourceDebugExtension(DexAnnotation annotation) { - return annotation.annotation.type.toDescriptorString().equals(SOURCE_DEBUG_EXTENSION); + public static boolean isSourceDebugExtension(DexAnnotation annotation, + DexItemFactory factory) { + return annotation.annotation.type == factory.annotationSourceDebugExtension; } /** diff --git a/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java b/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java index 04e94d7ea..e91e1f009 100644 --- a/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java +++ b/src/main/java/com/android/tools/r8/graph/DexAnnotationSet.java @@ -68,6 +68,15 @@ public class DexAnnotationSet extends DexItem { sorted = hashCode(); } + public DexAnnotation getFirstMatching(DexType type) { + for (DexAnnotation annotation : annotations) { + if (annotation.annotation.type == type) { + return annotation; + } + } + return null; + } + private int sortedHashCode() { int hashCode = hashCode(); return hashCode == UNSORTED ? 1 : hashCode; diff --git a/src/main/java/com/android/tools/r8/graph/DexApplication.java b/src/main/java/com/android/tools/r8/graph/DexApplication.java index ca702fe3a..d84dd8c76 100644 --- a/src/main/java/com/android/tools/r8/graph/DexApplication.java +++ b/src/main/java/com/android/tools/r8/graph/DexApplication.java @@ -25,7 +25,6 @@ import java.util.ArrayList; import java.util.Collection; import java.util.Collections; import java.util.Comparator; -import java.util.Hashtable; import java.util.IdentityHashMap; import java.util.List; import java.util.Map; @@ -87,7 +86,8 @@ public class DexApplication { } public List<DexProgramClass> classes() { - List<DexProgramClass> classes = programClasses.collectLoadedClasses(); + programClasses.forceLoad(type -> true); + List<DexProgramClass> classes = programClasses.getAllClasses(); assert reorderClasses(classes); return classes; } @@ -110,16 +110,16 @@ public class DexApplication { // program classes are supposed to be loaded, but force-loading them is no-op. programClasses.forceLoad(type -> true); - programClasses.collectLoadedClasses().forEach(clazz -> loaded.put(clazz.type, clazz)); + programClasses.getAllClasses().forEach(clazz -> loaded.put(clazz.type, clazz)); if (classpathClasses != null) { classpathClasses.forceLoad(type -> !loaded.containsKey(type)); - classpathClasses.collectLoadedClasses().forEach(clazz -> loaded.put(clazz.type, clazz)); + classpathClasses.getAllClasses().forEach(clazz -> loaded.putIfAbsent(clazz.type, clazz)); } if (libraryClasses != null) { libraryClasses.forceLoad(type -> !loaded.containsKey(type)); - libraryClasses.collectLoadedClasses().forEach(clazz -> loaded.put(clazz.type, clazz)); + libraryClasses.getAllClasses().forEach(clazz -> loaded.putIfAbsent(clazz.type, clazz)); } return loaded; @@ -192,7 +192,7 @@ public class DexApplication { * <p>If no directory is provided everything is written to System.out. */ public void disassemble(Path outputDir, InternalOptions options) { - for (DexProgramClass clazz : programClasses.collectLoadedClasses()) { + for (DexProgramClass clazz : programClasses.getAllClasses()) { for (DexEncodedMethod method : clazz.virtualMethods()) { if (options.methodMatchesFilter(method)) { disassemble(method, getProguardMap(), outputDir); @@ -246,7 +246,7 @@ public class DexApplication { * Write smali source for the application code on the provided PrintStream. */ public void smali(InternalOptions options, PrintStream ps) { - List<DexProgramClass> classes = programClasses.collectLoadedClasses(); + List<DexProgramClass> classes = programClasses.getAllClasses(); classes.sort(Comparator.comparing(DexProgramClass::toSourceString)); boolean firstClass = true; for (DexClass clazz : classes) { @@ -322,7 +322,7 @@ public class DexApplication { } public Builder(DexApplication application) { - programClasses = application.programClasses.collectLoadedClasses(); + programClasses = application.programClasses.getAllClasses(); classpathClasses = application.classpathClasses; libraryClasses = application.libraryClasses; proguardMap = application.proguardMap; diff --git a/src/main/java/com/android/tools/r8/graph/DexClass.java b/src/main/java/com/android/tools/r8/graph/DexClass.java index 023cfb0e4..5b1b0f3f8 100644 --- a/src/main/java/com/android/tools/r8/graph/DexClass.java +++ b/src/main/java/com/android/tools/r8/graph/DexClass.java @@ -10,6 +10,7 @@ import com.android.tools.r8.errors.Unreachable; import com.google.common.base.MoreObjects; +import java.util.Arrays; import java.util.function.Consumer; public abstract class DexClass extends DexItem { @@ -83,6 +84,17 @@ public abstract class DexClass extends DexItem { } } + public DexEncodedMethod[] allMethodsSorted() { + int vLen = virtualMethods().length; + int dLen = directMethods().length; + DexEncodedMethod[] result = new DexEncodedMethod[vLen+dLen]; + System.arraycopy(virtualMethods(), 0, result, 0, vLen); + System.arraycopy(directMethods(), 0, result, vLen, dLen); + Arrays.sort(result, + (DexEncodedMethod a, DexEncodedMethod b) -> a.method.slowCompareTo(b.method)); + return result; + } + public DexEncodedField[] staticFields() { return MoreObjects.firstNonNull(staticFields, NO_FIELDS); } diff --git a/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java b/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java index dd5efbbd0..036b8bc74 100644 --- a/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java +++ b/src/main/java/com/android/tools/r8/graph/DexClasspathClass.java @@ -7,8 +7,9 @@ import com.android.tools.r8.Resource; import com.android.tools.r8.dex.IndexedItemCollection; import com.android.tools.r8.dex.MixedSectionCollection; import com.android.tools.r8.errors.Unreachable; +import java.util.function.Supplier; -public class DexClasspathClass extends DexClass { +public class DexClasspathClass extends DexClass implements Supplier<DexClasspathClass> { public DexClasspathClass(DexType type, Resource.Kind origin, DexAccessFlags accessFlags, DexType superType, DexTypeList interfaces, DexString sourceFile, DexAnnotationSet annotations, @@ -43,4 +44,9 @@ public class DexClasspathClass extends DexClass { public DexClasspathClass asClasspathClass() { return this; } + + @Override + public DexClasspathClass get() { + return this; + } } 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 5dff4b432..36d732d8d 100644 --- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java +++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java @@ -129,8 +129,8 @@ public class DexItemFactory { public DexType annotationType = createType(annotationDescriptor); public DexType throwableType = createType(throwableDescriptor); - public DexType stringBuilderType = createType(createString("Ljava/lang/StringBuilder;")); - public DexType stringBufferType = createType(createString("Ljava/lang/StringBuffer;")); + public DexType stringBuilderType = createType("Ljava/lang/StringBuilder;"); + public DexType stringBufferType = createType("Ljava/lang/StringBuffer;"); public StringBuildingMethods stringBuilderMethods = new StringBuildingMethods(stringBuilderType); public StringBuildingMethods stringBufferMethods = new StringBuildingMethods(stringBufferType); @@ -140,6 +140,21 @@ public class DexItemFactory { public ThrowableMethods throwableMethods = new ThrowableMethods(); public ClassMethods classMethods = new ClassMethods(); + // Dex system annotations. + // See https://source.android.com/devices/tech/dalvik/dex-format.html#system-annotation + public final DexType annotationDefault = createType("Ldalvik/annotation/AnnotationDefault;"); + public final DexType annotationEnclosingClass = createType("Ldalvik/annotation/EnclosingClass;"); + public final DexType annotationEnclosingMethod = createType( + "Ldalvik/annotation/EnclosingMethod;"); + public final DexType annotationInnerClass = createType("Ldalvik/annotation/InnerClass;"); + public final DexType annotationMemberClasses = createType("Ldalvik/annotation/MemberClasses;"); + public final DexType annotationMethodParameters = createType( + "Ldalvik/annotation/MethodParameters;"); + public final DexType annotationSignature = createType("Ldalvik/annotation/Signature;"); + public final DexType annotationSourceDebugExtension = createType( + "Ldalvik/annotation/SourceDebugExtension;"); + public final DexType annotationThrows = createType("Ldalvik/annotation/Throws;"); + public void clearSubtypeInformation() { types.values().forEach(DexType::clearSubtypeInformation); } diff --git a/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java b/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java index c1b9205e1..0c8ce8cf5 100644 --- a/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java +++ b/src/main/java/com/android/tools/r8/graph/DexLibraryClass.java @@ -7,8 +7,9 @@ import com.android.tools.r8.Resource; import com.android.tools.r8.dex.IndexedItemCollection; import com.android.tools.r8.dex.MixedSectionCollection; import com.android.tools.r8.errors.Unreachable; +import java.util.function.Supplier; -public class DexLibraryClass extends DexClass { +public class DexLibraryClass extends DexClass implements Supplier<DexLibraryClass> { public DexLibraryClass(DexType type, Resource.Kind origin, DexAccessFlags accessFlags, DexType superType, DexTypeList interfaces, DexString sourceFile, DexAnnotationSet annotations, @@ -48,4 +49,9 @@ public class DexLibraryClass extends DexClass { public DexLibraryClass asLibraryClass() { return this; } + + @Override + public DexLibraryClass get() { + return this; + } } diff --git a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java index f93a7da59..a38c9cb99 100644 --- a/src/main/java/com/android/tools/r8/graph/DexProgramClass.java +++ b/src/main/java/com/android/tools/r8/graph/DexProgramClass.java @@ -7,8 +7,9 @@ import com.android.tools.r8.Resource; import com.android.tools.r8.dex.IndexedItemCollection; import com.android.tools.r8.dex.MixedSectionCollection; import java.util.Arrays; +import java.util.function.Supplier; -public class DexProgramClass extends DexClass { +public class DexProgramClass extends DexClass implements Supplier<DexProgramClass> { private DexEncodedArray staticValues; @@ -152,4 +153,9 @@ public class DexProgramClass extends DexClass { directMethods = Arrays.copyOf(directMethods, directMethods.length + 1); directMethods[directMethods.length - 1] = staticMethod; } + + @Override + public DexProgramClass get() { + return this; + } } diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java index a6b3fd0d7..c65b3709a 100644 --- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java +++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionIterator.java @@ -428,7 +428,11 @@ public class BasicBlockInstructionIterator implements InstructionIterator, Instr } // Insert inlinee blocks into the IR code. - inlinee.blocks.forEach(blocksIterator::add); + int blockNumber = code.getHighestBlockNumber() + 1; + for (BasicBlock bb : inlinee.blocks) { + bb.setNumber(blockNumber++); + blocksIterator.add(bb); + } // If the invoke block had catch handlers copy those down to all inlined blocks. if (invokeBlock.hasCatchHandlers()) { 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 c96bf92fa..e1e9a99ba 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 @@ -17,6 +17,7 @@ import java.util.LinkedList; import java.util.List; import java.util.ListIterator; import java.util.Set; +import java.util.stream.Collectors; public class IRCode { @@ -135,6 +136,7 @@ public class IRCode { } public boolean isConsistentGraph() { + assert consistentBlockNumbering(); assert consistentPredecessorSuccessors(); assert consistentCatchHandlers(); assert consistentBlockInstructions(); @@ -263,6 +265,12 @@ public class IRCode { return true; } + public boolean consistentBlockNumbering() { + return blocks.stream() + .collect(Collectors.groupingBy(BasicBlock::getNumber, Collectors.counting())) + .entrySet().stream().noneMatch((bb2count) -> bb2count.getValue() > 1); + } + private boolean consistentBlockInstructions() { for (BasicBlock block : blocks) { for (Instruction instruction : block.getInstructions()) { @@ -378,4 +386,8 @@ public class IRCode { public ConstNumber createFalse() { return new ConstNumber(ConstType.INT, createValue(MoveType.SINGLE), 0); } + + public final int getHighestBlockNumber() { + return blocks.stream().max(Comparator.comparingInt(BasicBlock::getNumber)).get().getNumber(); + } } diff --git a/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java b/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java index 4d8eee148..f4406c0b8 100644 --- a/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java +++ b/src/main/java/com/android/tools/r8/ir/conversion/CallGraph.java @@ -19,9 +19,9 @@ import com.android.tools.r8.ir.code.Invoke.Type; import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness; import com.google.common.collect.Sets; import java.util.ArrayList; -import java.util.Collections; +import java.util.Arrays; import java.util.HashMap; -import java.util.IdentityHashMap; +import java.util.HashSet; import java.util.LinkedHashMap; import java.util.LinkedHashSet; import java.util.List; @@ -52,10 +52,10 @@ public class CallGraph { private boolean isSelfRecursive = false; // Outgoing calls from this method. - public final Set<Node> callees = new LinkedHashSet<>(); + private final Set<Node> callees = new LinkedHashSet<>(); // Incoming calls to this method. - public final Set<Node> callers = new LinkedHashSet<>(); + private final Set<Node> callers = new LinkedHashSet<>(); private Node(DexEncodedMethod method) { this.method = method; @@ -81,10 +81,6 @@ public class CallGraph { return callees.isEmpty(); } - int callDegree() { - return callees.size(); - } - @Override public int hashCode() { return method.hashCode(); @@ -133,75 +129,35 @@ public class CallGraph { } } - public class Leaves { - - private final List<DexEncodedMethod> leaves; - private final boolean brokeCycles; - private final Map<DexEncodedMethod, Set<DexEncodedMethod>> cycleBreakingCalls; - - private Leaves(List<DexEncodedMethod> leaves, boolean brokeCycles, - Map<DexEncodedMethod, Set<DexEncodedMethod>> cycleBreakingCalls) { - this.leaves = leaves; - this.brokeCycles = brokeCycles; - this.cycleBreakingCalls = cycleBreakingCalls; - assert brokeCycles == (cycleBreakingCalls.size() != 0); - } - - public int size() { - return leaves.size(); - } - - public List<DexEncodedMethod> getLeaves() { - return leaves; - } - - public boolean hasBrokeCycles() { - return brokeCycles; - } - - /** - * Calls that were broken to produce the leaves. - * - * If {@link Leaves#breakCycles()} return <code>true</code> this provides the calls for each - * leaf that were broken. - * - * NOTE: The broken calls are not confined to the set of leaves. - */ - public Map<DexEncodedMethod, Set<DexEncodedMethod>> getCycleBreakingCalls() { - return cycleBreakingCalls; - } - - @Override - public String toString() { - StringBuilder builder = new StringBuilder(); - builder.append("Leaves: "); - builder.append(leaves.size()); - builder.append("\n"); - builder.append(brokeCycles ? "Call cycles broken" : "No call cycles broken"); - return builder.toString(); - } - } - private final Map<DexEncodedMethod, Node> nodes = new LinkedHashMap<>(); private final Map<DexEncodedMethod, Set<DexEncodedMethod>> breakers = new HashMap<>(); + // Returns whether the method->callee edge has been removed from the call graph + // to break a cycle in the call graph. + public boolean isBreaker(DexEncodedMethod method, DexEncodedMethod callee) { + Set<DexEncodedMethod> value = breakers.get(method); + return (value != null) && value.contains(callee); + } + private List<Node> leaves = null; private Set<DexEncodedMethod> singleCallSite = Sets.newIdentityHashSet(); private Set<DexEncodedMethod> doubleCallSite = Sets.newIdentityHashSet(); public static CallGraph build(DexApplication application, AppInfoWithSubtyping appInfo, GraphLense graphLense) { - CallGraph graph = new CallGraph(); - for (DexClass clazz : application.classes()) { - clazz.forEachMethod( method -> { + DexClass[] classes = application.classes().toArray(new DexClass[application.classes().size()]); + Arrays.sort(classes, (DexClass a, DexClass b) -> a.type.slowCompareTo(b.type)); + for (DexClass clazz : classes) { + for (DexEncodedMethod method : clazz.allMethodsSorted()) { Node node = graph.ensureMethodNode(method); InvokeExtractor extractor = new InvokeExtractor(appInfo, graphLense, node, graph); method.registerReachableDefinitions(extractor); - }); + } } - assert allMethodsExists(application, graph); + graph.breakCycles(); + assert graph.breakCycles() == 0; // This time the cycles should be gone. graph.fillCallSiteSets(appInfo); graph.fillInitialLeaves(); return graph; @@ -258,7 +214,6 @@ public class CallGraph { /** * Remove all leaves (nodes with an call (outgoing) degree of 0). - * <p> * * @return List of {@link DexEncodedMethod} of the leaves removed. */ @@ -282,73 +237,62 @@ public class CallGraph { * leave is returned if the graph is not empty. * <p> * - * @return object with the leaves as a List of {@link DexEncodedMethod} and <code>boolean</code> - * indication of whether cycles were broken to produce leaves. <code>null</code> if the graph is - * empty. + * @return List of {@link DexEncodedMethod}. */ - public Leaves pickLeaves() { - boolean cyclesBroken = false; - Map<DexEncodedMethod, Set<DexEncodedMethod>> brokenCalls = Collections.emptyMap(); + List<DexEncodedMethod> extractLeaves() { if (isEmpty()) { return null; } List<DexEncodedMethod> leaves = removeLeaves(); - if (leaves.size() == 0) { - // The graph had no more leaves, so break cycles to construct leaves. - brokenCalls = breakCycles(); - cyclesBroken = true; - leaves = removeLeaves(); - } assert leaves.size() > 0; - for (DexEncodedMethod leaf : leaves) { - assert !leaf.isProcessed(); - } - return new Leaves(leaves, cyclesBroken, brokenCalls); + leaves.forEach( leaf -> { assert !leaf.isProcessed(); }); + return leaves; } - /** - * Break some cycles in the graph by removing edges. - * <p> - * This will find the lowest call (outgoing) degree in the graph. Then go through all nodes with - * that call (outgoing) degree, and remove all call (outgoing) edges from nodes with that call - * (outgoing) degree. - * <p> - * It will avoid removing edges from bridge-methods if possible. - * <p> - * Returns the calls that were broken. - */ - private Map<DexEncodedMethod, Set<DexEncodedMethod>> breakCycles() { - Map<DexEncodedMethod, Set<DexEncodedMethod>> brokenCalls = new IdentityHashMap<>(); - // Break non bridges with degree 1. - int minDegree = nodes.size(); - for (Node node : nodes.values()) { - // Break cycles and add all leaves created in the process. - if (!node.isBridge() && node.callDegree() <= 1) { - assert node.callDegree() == 1; - Set<DexEncodedMethod> calls = removeAllCalls(node); - leaves.add(node); - brokenCalls.put(node.method, calls); - } else { - minDegree = Integer.min(minDegree, node.callDegree()); + private int traverse(Node node, HashSet<Node> stack, HashSet<Node> marked) { + int numberOfCycles = 0; + if (!marked.contains(node)) { + assert !stack.contains(node); + stack.add(node); + ArrayList<Node> toBeRemoved = null; + // Sort the callees before calling traverse recursively. + // This will ensure cycles are broken the same way across + // multiple invocations of the R8 compiler. + Node[] callees = node.callees.toArray(new Node[node.callees.size()]); + Arrays.sort(callees, (Node a, Node b) -> a.method.method.slowCompareTo(b.method.method)); + for (Node callee : callees) { + if (stack.contains(callee)) { + if (toBeRemoved == null) { + toBeRemoved = new ArrayList<>(); + } + // We have a cycle; break it by removing node->callee. + toBeRemoved.add(callee); + callee.callers.remove(node); + breakers.computeIfAbsent(node.method, ignore -> new HashSet<>()).add(callee.method); + } else { + numberOfCycles += traverse(callee, stack, marked); + } } + if (toBeRemoved != null) { + numberOfCycles += toBeRemoved.size(); + node.callees.removeAll(toBeRemoved); + } + stack.remove(node); + marked.add(node); } + return numberOfCycles; + } - // Return if new leaves were created. - if (leaves.size() > 0) { - return brokenCalls; - } - - // Break methods with the found minimum degree and add all leaves created in the process. - for (Node node : nodes.values()) { - if (node.callDegree() <= minDegree) { - assert node.callDegree() == minDegree; - Set<DexEncodedMethod> calls = removeAllCalls(node); - leaves.add(node); - brokenCalls.put(node.method, calls); - } + private int breakCycles() { + // Break cycles in this call graph by removing edges causing cycles. + // The remove edges are stored in @breakers. + int numberOfCycles = 0; + HashSet<Node> stack = new HashSet<>(); + HashSet<Node> marked = new HashSet<>(); + for(Node node : nodes.values()) { + numberOfCycles += traverse(node, stack, marked); } - assert leaves.size() > 0; - return brokenCalls; + return numberOfCycles; } synchronized private Node ensureMethodNode(DexEncodedMethod method) { @@ -367,16 +311,6 @@ public class CallGraph { callee.invokeCount++; } - private Set<DexEncodedMethod> removeAllCalls(Node node) { - Set<DexEncodedMethod> calls = Sets.newIdentityHashSet(); - for (Node call : node.callees) { - calls.add(call.method); - call.callers.remove(node); - } - node.callees.clear(); - return calls; - } - private void remove(Node node, List<Node> leaves) { assert node != null; for (Node caller : node.callers) { diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java index 4ce2c4ce4..ba63d804a 100644 --- a/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java +++ b/src/main/java/com/android/tools/r8/ir/conversion/IRBuilder.java @@ -270,6 +270,8 @@ public class IRBuilder { private List<Value> debugLocalReads = new ArrayList<>(); private List<Value> debugLocalEnds = new ArrayList<>(); + private int nextBlockNumber = 0; + public IRBuilder(DexEncodedMethod method, SourceCode source, InternalOptions options) { this(method, source, new ValueNumberGenerator(), options); } @@ -350,15 +352,14 @@ public class IRBuilder { // Process normal blocks reachable from the entry block using a worklist of reachable // blocks. - int blockNumber = 0; addToWorklist(currentBlock, 0); - blockNumber = processWorklist(blockNumber); + processWorklist(); // Check that the last block is closed and does not fall off the end. assert currentBlock == null; // Handle where a catch handler hits the same block as the fallthrough. - blockNumber = handleFallthroughToCatchBlock(blockNumber); + handleFallthroughToCatchBlock(); // Verify that we have properly filled all blocks // Must be after handle-catch (which has delayed edges), @@ -366,7 +367,7 @@ public class IRBuilder { assert verifyFilledPredecessors(); // If there are multiple returns create an exit block. - blockNumber = handleExitBlock(blockNumber); + handleExitBlock(); // Clear all reaching definitions to free up memory (and avoid invalid use). for (BasicBlock block : blocks) { @@ -437,14 +438,14 @@ public class IRBuilder { return true; } - private int processWorklist(int blockNumber) { + private void processWorklist() { for (WorklistItem item = ssaWorklist.poll(); item != null; item = ssaWorklist.poll()) { if (item.block.isFilled()) { continue; } setCurrentBlock(item.block); blocks.add(currentBlock); - currentBlock.setNumber(blockNumber++); + currentBlock.setNumber(nextBlockNumber++); // Build IR for each dex instruction in the block. for (int i = item.firstInstructionIndex; i < source.instructionCount(); ++i) { if (currentBlock == null) { @@ -461,7 +462,6 @@ public class IRBuilder { source.buildInstruction(this, i); } } - return blockNumber; } // Helper to resolve switch payloads and build switch instructions (dex code only). @@ -1536,6 +1536,7 @@ public class IRBuilder { return; } BasicBlock block = new BasicBlock(); + block.setNumber(nextBlockNumber++); blocks.add(block); block.incrementUnfilledPredecessorCount(); int freshOffset = INITIAL_BLOCK_OFFSET - 1; @@ -1721,7 +1722,7 @@ public class IRBuilder { closeCurrentBlock(); } - int handleExitBlock(int blockNumber) { + void handleExitBlock() { if (exitBlocks.size() > 0) { // Create and populate the exit block if needed (eg, synchronized support for jar). setCurrentBlock(new BasicBlock()); @@ -1730,11 +1731,11 @@ public class IRBuilder { if (currentBlock.getInstructions().isEmpty() && exitBlocks.size() == 1) { normalExitBlock = exitBlocks.get(0); setCurrentBlock(null); - return blockNumber; + return; } // Commit to creating the new exit block. normalExitBlock = currentBlock; - normalExitBlock.setNumber(blockNumber++); + normalExitBlock.setNumber(nextBlockNumber++); blocks.add(normalExitBlock); // Add the return instruction possibly creating a phi of return values. Return origReturn = exitBlocks.get(0).exit().asReturn(); @@ -1776,10 +1777,9 @@ public class IRBuilder { phi.addOperands(operands); } } - return blockNumber; } - private int handleFallthroughToCatchBlock(int blockNumber) { + private void handleFallthroughToCatchBlock() { // When a catch handler for a block goes to the same block as the fallthrough for that // block the graph only has one edge there. In these cases we add an additional block so the // catch edge goes through that and then make the fallthrough go through a new direct edge. @@ -1788,7 +1788,7 @@ public class IRBuilder { BasicBlock target = pair.second; // New block with one unfilled predecessor. - BasicBlock newBlock = BasicBlock.createGotoBlock(target, blockNumber++); + BasicBlock newBlock = BasicBlock.createGotoBlock(target, nextBlockNumber++); blocks.add(newBlock); newBlock.incrementUnfilledPredecessorCount(); @@ -1808,7 +1808,6 @@ public class IRBuilder { } target.filledPredecessor(this); } - return blockNumber; } /** diff --git a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java index 98a261914..a345ddfa4 100644 --- a/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java +++ b/src/main/java/com/android/tools/r8/ir/conversion/IRConverter.java @@ -37,7 +37,7 @@ import com.android.tools.r8.utils.DescriptorUtils; import com.android.tools.r8.utils.InternalOptions; import com.android.tools.r8.utils.ThreadUtils; import com.android.tools.r8.utils.Timing; -import com.google.common.collect.ImmutableList; + import com.google.common.collect.ImmutableSet; import java.util.ArrayList; import java.util.List; @@ -277,50 +277,21 @@ public class IRConverter { // Process the application identifying outlining candidates. timing.begin("IR conversion phase 1"); OptimizationFeedback directFeedback = new OptimizationFeedbackDirect(); - OptimizationFeedbackDelayed delayedFeedback = new OptimizationFeedbackDelayed(); while (!callGraph.isEmpty()) { - CallGraph.Leaves leaves = callGraph.pickLeaves(); - List<DexEncodedMethod> methods = leaves.getLeaves(); + List<DexEncodedMethod> methods = callGraph.extractLeaves(); assert methods.size() > 0; - List<Future<?>> futures = new ArrayList<>(); - // For testing we have the option to determine the processing order of the methods. if (options.testing.irOrdering != null) { - methods = options.testing.irOrdering.apply(methods, leaves); + methods = options.testing.irOrdering.apply(methods); } - - while (methods.size() > 0) { - // Process the methods on multiple threads. If cycles where broken collect the - // optimization feedback to reprocess methods affected by it. This is required to get - // deterministic behaviour, as the processing order within each set of leaves is - // non-deterministic. - - // Due to a race condition, we serialize processing of methods if cycles are broken. - // TODO(bak) - if (leaves.hasBrokeCycles()) { - for (DexEncodedMethod method : methods) { - processMethod(method, - leaves.hasBrokeCycles() ? delayedFeedback : directFeedback, - outliner == null ? Outliner::noProcessing : outliner::identifyCandidates); - } - } else { - for (DexEncodedMethod method : methods) { - futures.add(executorService.submit(() -> { - processMethod(method, - leaves.hasBrokeCycles() ? delayedFeedback : directFeedback, - outliner == null ? Outliner::noProcessing : outliner::identifyCandidates); - })); - } - ThreadUtils.awaitFutures(futures); - } - if (leaves.hasBrokeCycles()) { - // If cycles in the call graph were broken, then re-process all methods which are - // affected by the optimization feedback of other methods in this group. - methods = delayedFeedback.applyAndClear(methods, leaves); - } else { - methods = ImmutableList.of(); - } + List<Future<?>> futures = new ArrayList<>(); + for (DexEncodedMethod method : methods) { + futures.add(executorService.submit(() -> { + processMethod(method, directFeedback, + outliner == null ? Outliner::noProcessing : outliner::identifyCandidates); + })); } + ThreadUtils.awaitFutures(futures); } timing.end(); @@ -550,7 +521,7 @@ public class IRConverter { feedback.markProcessed(method, state); } - private void updateHighestSortingStrings(DexEncodedMethod method) { + private synchronized void updateHighestSortingStrings(DexEncodedMethod method) { DexString highestSortingReferencedString = method.getCode().asDexCode().highestSortingString; if (highestSortingReferencedString != null) { if (highestSortingString == null diff --git a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java b/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java deleted file mode 100644 index a8c81ef75..000000000 --- a/src/main/java/com/android/tools/r8/ir/conversion/OptimizationFeedbackDelayed.java +++ /dev/null @@ -1,116 +0,0 @@ -// 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.conversion; - -import com.android.tools.r8.graph.DexEncodedMethod; -import com.android.tools.r8.ir.optimize.Inliner.Constraint; -import com.google.common.collect.Maps; -import com.google.common.collect.Sets; -import it.unimi.dsi.fastutil.objects.Reference2IntMap; -import it.unimi.dsi.fastutil.objects.Reference2IntOpenHashMap; -import it.unimi.dsi.fastutil.objects.Reference2LongMap; -import it.unimi.dsi.fastutil.objects.Reference2LongOpenHashMap; -import java.util.ArrayList; -import java.util.List; -import java.util.Map; -import java.util.Set; - -public class OptimizationFeedbackDelayed implements OptimizationFeedback { - - private Reference2IntMap<DexEncodedMethod> returnsArgument = new Reference2IntOpenHashMap<>(); - private Reference2LongMap<DexEncodedMethod> returnsConstant = new Reference2LongOpenHashMap<>(); - private Set<DexEncodedMethod> neverReturnsNull = Sets.newIdentityHashSet(); - private Map<DexEncodedMethod, Constraint> inliningConstraints = Maps.newIdentityHashMap(); - - @Override - synchronized public void methodReturnsArgument(DexEncodedMethod method, int argument) { - if (method.getOptimizationInfo().returnsArgument()) { - assert method.getOptimizationInfo().getReturnedArgument() == argument; - return; - } - assert !returnsArgument.containsKey(method); - returnsArgument.put(method, argument); - } - - @Override - synchronized public void methodReturnsConstant(DexEncodedMethod method, long value) { - if (method.getOptimizationInfo().returnsConstant()) { - assert method.getOptimizationInfo().getReturnedConstant() == value; - return; - } - assert !returnsConstant.containsKey(method); - returnsConstant.put(method, value); - } - - @Override - synchronized public void methodNeverReturnsNull(DexEncodedMethod method) { - if (method.getOptimizationInfo().neverReturnsNull()) { - return; - } - assert !neverReturnsNull.contains(method); - neverReturnsNull.add(method); - } - - @Override - public void markProcessed(DexEncodedMethod method, Constraint state) { - if (state == Constraint.NEVER) { - assert method.cannotInline(); - method.markProcessed(state); - } else { - inliningConstraints.put(method, state); - } - } - - private <T> boolean setsOverlap(Set<T> set1, Set<T> set2) { - for (T element : set1) { - if (set2.contains(element)) { - return true; - } - } - return false; - } - - /** - * Apply the optimization feedback. - * - * Returns the methods from the passed in list that could be affected by applying the - * optimization feedback. - */ - public List<DexEncodedMethod> applyAndClear( - List<DexEncodedMethod> processed, CallGraph.Leaves leaves) { - returnsArgument.forEach(DexEncodedMethod::markReturnsArgument); - returnsConstant.forEach(DexEncodedMethod::markReturnsConstant); - neverReturnsNull.forEach(DexEncodedMethod::markNeverReturnsNull); - - // Collect all methods affected by the optimization feedback applied. - Set<DexEncodedMethod> all = Sets.newIdentityHashSet(); - all.addAll(returnsArgument.keySet()); - all.addAll(returnsConstant.keySet()); - all.addAll(neverReturnsNull); - inliningConstraints.forEach((method, constraint) -> { - boolean changed = method.markProcessed(constraint); - if (changed) { - all.add(method); - } - }); - - // Collect the processed methods which could be affected by the applied optimization feedback. - List<DexEncodedMethod> result = new ArrayList<>(); - for (DexEncodedMethod method : processed) { - Set<DexEncodedMethod> calls = leaves.getCycleBreakingCalls().get(method); - if (setsOverlap(calls, all)) { - result.add(method); - } - } - - // Clear the collected optimization feedback. - returnsArgument.clear(); - returnsConstant.clear(); - neverReturnsNull.clear(); - inliningConstraints.clear(); - - return result; - } -} diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java index 6d6981757..4ede5a839 100644 --- a/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java +++ b/src/main/java/com/android/tools/r8/ir/optimize/Inliner.java @@ -284,6 +284,10 @@ public class Inliner { if (block.hasCatchHandlers() && inlinee.getNormalExitBlock() == null) { continue; } + if (callGraph.isBreaker(method, target)) { + // Make sure we don't inline a call graph breaker. + continue; + } // If this code did not go through the full pipeline, apply inlining to make sure // that force inline targets get processed. if (!target.isProcessed()) { diff --git a/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java b/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java index 4b93d8d77..446b75a63 100644 --- a/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java +++ b/src/main/java/com/android/tools/r8/ir/optimize/InliningOracle.java @@ -66,6 +66,7 @@ public class InliningOracle { assert !candidate.getOptimizationInfo().forceInline(); return null; } + if (candidate.accessFlags.isSynchronized()) { // Don't inline if target is synchronized. if (info != null) { @@ -73,6 +74,12 @@ public class InliningOracle { } return null; } + + if (callGraph.isBreaker(method, candidate)) { + // Cycle breaker so abort to preserve compilation order. + return null; + } + if (!inliner.hasInliningAccess(method, candidate)) { if (info != null) { info.exclude(invoke, "Inlinee candidate does not have right access flags"); @@ -154,6 +161,11 @@ public class InliningOracle { return null; } + if (callGraph.isBreaker(method, target)) { + // Cycle breaker so abort to preserve compilation order. + return null; + } + // Abort inlining attempt if method -> target access is not right. if (!inliner.hasInliningAccess(method, target)) { if (info != null) { diff --git a/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java b/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java index de81dfeff..9a7086453 100644 --- a/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java +++ b/src/main/java/com/android/tools/r8/ir/optimize/PeepholeOptimizer.java @@ -42,6 +42,7 @@ public class PeepholeOptimizer { private static void shareIdenticalBlockSuffix(IRCode code, RegisterAllocator allocator) { Collection<BasicBlock> blocks = code.blocks; do { + int startNumberOfNewBlock = code.getHighestBlockNumber() + 1; Map<BasicBlock, BasicBlock> newBlocks = new IdentityHashMap<>(); for (BasicBlock block : blocks) { InstructionEquivalence equivalence = new InstructionEquivalence(allocator); @@ -79,7 +80,7 @@ public class PeepholeOptimizer { commonSuffixSize, sharedSuffixSizeExcludingExit(firstPred, pred, allocator)); } assert commonSuffixSize >= 1; - int blockNumber = code.blocks.size() + newBlocks.size(); + int blockNumber = startNumberOfNewBlock + newBlocks.size(); BasicBlock newBlock = createAndInsertBlockForSuffix( blockNumber, commonSuffixSize, predsWithSameLastInstruction, block); newBlocks.put(predsWithSameLastInstruction.get(0), newBlock); diff --git a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java index 7c12590b3..9f26fb51f 100644 --- a/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java +++ b/src/main/java/com/android/tools/r8/naming/ClassNameMinifier.java @@ -3,14 +3,17 @@ // BSD-style license that can be found in the LICENSE file. package com.android.tools.r8.naming; +import com.android.tools.r8.graph.DexAnnotation; import com.android.tools.r8.graph.DexClass; -import com.android.tools.r8.graph.DexMethod; +import com.android.tools.r8.graph.DexProgramClass; import com.android.tools.r8.graph.DexString; import com.android.tools.r8.graph.DexType; +import com.android.tools.r8.graph.DexValue; +import com.android.tools.r8.graph.DexValue.DexValueType; import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness; import com.android.tools.r8.shaking.RootSetBuilder.RootSet; +import com.android.tools.r8.utils.DescriptorUtils; import com.android.tools.r8.utils.StringUtils; -import com.google.common.collect.ImmutableSet; import com.google.common.collect.Maps; import com.google.common.collect.Sets; import java.util.Collections; @@ -29,30 +32,31 @@ public class ClassNameMinifier { private final Map<DexType, DexString> renaming = Maps.newIdentityHashMap(); private final Map<String, NamingState> states = new HashMap<>(); - final List<String> dictionary; + private final List<String> dictionary; + private final boolean keepInnerClassStructure; public ClassNameMinifier(AppInfoWithLiveness appInfo, RootSet rootSet, String packagePrefix, - List<String> dictionary) { + List<String> dictionary, boolean keepInnerClassStructure) { this.appInfo = appInfo; this.rootSet = rootSet; this.packagePrefix = packagePrefix; this.dictionary = dictionary; + this.keepInnerClassStructure = keepInnerClassStructure; } public Map<DexType, DexString> computeRenaming() { + Iterable<DexProgramClass> classes = appInfo.classes(); // Collect names we have to keep. for (DexClass clazz : appInfo.classes()) { if (rootSet.noObfuscation.contains(clazz)) { assert !renaming.containsKey(clazz.type); - renaming.put(clazz.type, clazz.type.descriptor); - usedTypeNames.add(clazz.type.descriptor); + registerClassAsUsed(clazz.type); } } for (DexClass clazz : appInfo.classes()) { if (!renaming.containsKey(clazz.type)) { - String packageName = getPackageNameFor(clazz); - NamingState state = getStateFor(packageName); - renaming.put(clazz.type, state.nextTypeName()); + DexString renamed = computeName(clazz); + renaming.put(clazz.type, renamed); } } appInfo.dexItemFactory.forAllTypes(this::renameArrayTypeIfNeeded); @@ -60,6 +64,63 @@ public class ClassNameMinifier { return Collections.unmodifiableMap(renaming); } + /** + * Registers the given type as used. + * <p> + * When {@link #keepInnerClassStructure} is true, keeping the name of an inner class will + * automatically also keep the name of the outer class, as otherwise the structure would be + * invalidated. + */ + private void registerClassAsUsed(DexType type) { + renaming.put(type, type.descriptor); + usedTypeNames.add(type.descriptor); + if (keepInnerClassStructure) { + DexType outerClass = getOutClassForType(type); + if (outerClass != null) { + if (!renaming.containsKey(outerClass)) { + // The outer class was not previously kept. We have to do this now. + registerClassAsUsed(outerClass); + } + } + } + } + + private DexType getOutClassForType(DexType type) { + DexClass clazz = appInfo.definitionFor(type); + if (clazz == null) { + return null; + } + DexAnnotation annotation = + clazz.annotations.getFirstMatching(appInfo.dexItemFactory.annotationEnclosingClass); + if (annotation != null) { + assert annotation.annotation.elements.length == 1; + DexValue value = annotation.annotation.elements[0].value; + return ((DexValueType) value).value; + } + // We do not need to preserve the names for local or anonymous classes, as they do not result + // in a member type declaration and hence cannot be referenced as nested classes in + // method signatures. + // See https://docs.oracle.com/javase/specs/jls/se7/html/jls-8.html#jls-8.5. + return null; + } + + private DexString computeName(DexClass clazz) { + NamingState state = null; + if (keepInnerClassStructure) { + // When keeping the nesting structure of inner classes, we have to insert the name + // of the outer class for the $ prefix. + DexType outerClass = getOutClassForType(clazz.type); + if (outerClass != null) { + state = getStateForOuterClass(outerClass); + } + } + if (state == null) { + String packageName = getPackageNameFor(clazz); + state = getStateFor(packageName); + } + return state.nextTypeName(); + } + private String getPackageNameFor(DexClass clazz) { if ((packagePrefix == null) || rootSet.keepPackageName.contains(clazz)) { return clazz.type.getPackageDescriptor(); @@ -72,6 +133,27 @@ public class ClassNameMinifier { return states.computeIfAbsent(packageName, NamingState::new); } + private NamingState getStateForOuterClass(DexType outer) { + String prefix = DescriptorUtils + .getClassBinaryNameFromDescriptor(outer.toDescriptorString()); + return states.computeIfAbsent(prefix, k -> { + // Create a naming state with this classes renaming as prefix. + DexString renamed = renaming.get(outer); + if (renamed == null) { + // The outer class has not been renamed yet, so rename the outer class first. + DexClass outerClass = appInfo.definitionFor(outer); + if (outerClass == null) { + renamed = outer.descriptor; + } else { + renamed = computeName(outerClass); + renaming.put(outer, renamed); + } + } + String binaryName = DescriptorUtils.getClassBinaryNameFromDescriptor(renamed.toString()); + return new NamingState(binaryName, "$"); + }); + } + private void renameArrayTypeIfNeeded(DexType type) { if (type.isArrayType()) { DexType base = type.toBaseType(appInfo.dexItemFactory); @@ -92,11 +174,18 @@ public class ClassNameMinifier { private class NamingState { private final char[] packagePrefix; + private final String separator; private int typeCounter = 1; private Iterator<String> dictionaryIterator; NamingState(String packageName) { - this.packagePrefix = ("L" + packageName + (packageName.isEmpty() ? "" : "/")).toCharArray(); + this(packageName, "/"); + } + + NamingState(String packageName, String separator) { + this.packagePrefix = ("L" + packageName + (packageName.isEmpty() ? "" : separator)) + .toCharArray(); + this.separator = separator; this.dictionaryIterator = dictionary.iterator(); } diff --git a/src/main/java/com/android/tools/r8/naming/Minifier.java b/src/main/java/com/android/tools/r8/naming/Minifier.java index 9e8110278..025002dbf 100644 --- a/src/main/java/com/android/tools/r8/naming/Minifier.java +++ b/src/main/java/com/android/tools/r8/naming/Minifier.java @@ -42,7 +42,8 @@ public class Minifier { timing.begin("MinifyClasses"); Map<DexType, DexString> classRenaming = new ClassNameMinifier( - appInfo, rootSet, options.packagePrefix, options.classObfuscationDictionary) + appInfo, rootSet, options.packagePrefix, options.classObfuscationDictionary, + options.attributeRemoval.signature) .computeRenaming(); timing.end(); timing.begin("MinifyMethods"); diff --git a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java index e60f241c9..3ab231cb0 100644 --- a/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java +++ b/src/main/java/com/android/tools/r8/shaking/AnnotationRemover.java @@ -9,6 +9,7 @@ import com.android.tools.r8.graph.DexAnnotationSet; import com.android.tools.r8.graph.DexAnnotationSetRefList; import com.android.tools.r8.graph.DexEncodedField; import com.android.tools.r8.graph.DexEncodedMethod; +import com.android.tools.r8.graph.DexItemFactory; import com.android.tools.r8.graph.DexProgramClass; import com.android.tools.r8.shaking.Enqueuer.AppInfoWithLiveness; import com.android.tools.r8.utils.InternalOptions; @@ -42,21 +43,24 @@ public class AnnotationRemover { case DexAnnotation.VISIBILITY_SYSTEM: // EnclosingClass and InnerClass are used in Dalvik to represent the InnerClasses // attribute section from class files. - if (keep.innerClasses && - (DexAnnotation.isInnerClassesAnnotation(annotation) || - DexAnnotation.isEnclosingClassAnnotation(annotation))) { + DexItemFactory factory = appInfo.dexItemFactory; + if (keep.innerClasses + && (DexAnnotation.isInnerClassesAnnotation(annotation, factory) || + DexAnnotation.isEnclosingClassAnnotation(annotation, factory))) { return true; } - if (keep.enclosingMethod && DexAnnotation.isEnclosingMethodAnnotation(annotation)) { + if (keep.enclosingMethod + && DexAnnotation.isEnclosingMethodAnnotation(annotation, factory)) { return true; } - if (keep.exceptions && DexAnnotation.isThrowingAnnotation(annotation)) { + if (keep.exceptions && DexAnnotation.isThrowingAnnotation(annotation, factory)) { return true; } - if (keep.signature && DexAnnotation.isSignatureAnnotation(annotation)) { + if (keep.signature && DexAnnotation.isSignatureAnnotation(annotation, factory)) { return true; } - if (keep.sourceDebugExtension && DexAnnotation.isSourceDebugExtension(annotation)) { + if (keep.sourceDebugExtension + && DexAnnotation.isSourceDebugExtension(annotation, factory)) { return true; } return false; diff --git a/src/main/java/com/android/tools/r8/utils/ClassMap.java b/src/main/java/com/android/tools/r8/utils/ClassMap.java index 91adca4c8..9677473dc 100644 --- a/src/main/java/com/android/tools/r8/utils/ClassMap.java +++ b/src/main/java/com/android/tools/r8/utils/ClassMap.java @@ -4,17 +4,19 @@ package com.android.tools.r8.utils; import com.android.tools.r8.errors.CompilationError; +import com.android.tools.r8.errors.Unreachable; import com.android.tools.r8.graph.ClassKind; import com.android.tools.r8.graph.DexClass; import com.android.tools.r8.graph.DexType; import com.google.common.collect.Sets; import java.util.ArrayList; -import java.util.Collection; import java.util.IdentityHashMap; +import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Set; import java.util.function.Predicate; +import java.util.function.Supplier; /** * Represents a collection of classes. Collection can be fully loaded, @@ -25,13 +27,17 @@ public abstract class ClassMap<T extends DexClass> { // resources provided by different resource providers. // // NOTE: all access must be synchronized on `classes`. - private final Map<DexType, Value<T>> classes; + private final Map<DexType, Supplier<T>> classes; - // Class provider if available. In case it's `null`, all classes of - // the collection must be pre-populated in `classes`. - private final ClassProvider<T> classProvider; + // Class provider if available. + // + // If the class provider is `null` it indicates that all classes are already present + // in a map referenced by `classes` and thus the collection is fully loaded. + // + // NOTE: all access must be synchronized on `classes`. + private ClassProvider<T> classProvider; - ClassMap(Map<DexType, Value<T>> classes, ClassProvider<T> classProvider) { + ClassMap(Map<DexType, Supplier<T>> classes, ClassProvider<T> classProvider) { this.classes = classes == null ? new IdentityHashMap<>() : classes; this.classProvider = classProvider; assert this.classProvider == null || this.classProvider.getClassKind() == getClassKind(); @@ -40,6 +46,9 @@ public abstract class ClassMap<T extends DexClass> { /** Resolves a class conflict by selecting a class, may generate compilation error. */ abstract T resolveClassConflict(T a, T b); + /** Return supplier for preloaded class. */ + abstract Supplier<T> getTransparentSupplier(T clazz); + /** Kind of the classes supported by this collection. */ abstract ClassKind getClassKind(); @@ -53,115 +62,175 @@ public abstract class ClassMap<T extends DexClass> { /** Returns a definition for a class or `null` if there is no such class in the collection. */ public T get(DexType type) { - final Value<T> value = getOrCreateValue(type); + Supplier<T> supplier; - if (value == null) { - return null; - } - - if (!value.ready) { - // Load the value in a context synchronized on value instance. This way - // we avoid locking the whole collection during expensive resource loading - // and classes construction operations. - synchronized (value) { - if (!value.ready) { - assert classProvider != null : "getOrCreateValue() created " - + "Value for missing type when there is no classProvider."; - classProvider.collectClass(type, clazz -> { - assert clazz != null; - assert getClassKind().isOfKind(clazz); - assert !value.ready; - - if (clazz.type != type) { - throw new CompilationError("Class content provided for type descriptor " - + type.toSourceString() + " actually defines class " + clazz.type - .toSourceString()); - } - - if (value.clazz == null) { - value.clazz = clazz; - } else { - // The class resolution *may* generate a compilation error as one of - // possible resolutions. In this case we leave `value` in (false, null) - // state so in rare case of another thread trying to get the same class - // before this error is propagated it will get the same conflict. - T oldClass = value.clazz; - value.clazz = null; - value.clazz = resolveClassConflict(oldClass, clazz); - } - }); - value.ready = true; + synchronized (classes) { + supplier = classes.get(type); + + // Get class supplier, create it if it does not + // exist and the collection is NOT fully loaded. + if (supplier == null) { + if (classProvider == null) { + // There is no supplier, but the collection is fully loaded. + return null; } + + supplier = new ConcurrentClassLoader<>(this, this.classProvider, type); + classes.put(type, supplier); } } - assert value.ready; - return value.clazz; + return supplier.get(); } - private Value<T> getOrCreateValue(DexType type) { + /** Returns all classes from the collection. The collection must be force-loaded. */ + public List<T> getAllClasses() { + List<T> loadedClasses = new ArrayList<>(); synchronized (classes) { - Value<T> value = classes.get(type); - if (value == null && classProvider != null) { - value = new Value<>(); - classes.put(type, value); + if (classProvider != null) { + throw new Unreachable("Getting all classes from not fully loaded collection."); + } + for (Supplier<T> supplier : classes.values()) { + // Since the class map is fully loaded, all suppliers must be + // loaded and non-null. + T clazz = supplier.get(); + assert clazz != null; + loadedClasses.add(clazz); } - return value; } + return loadedClasses; } /** - * Returns currently loaded classes. + * Forces loading of all the classes satisfying the criteria specified. * - * Method is assumed to be called when the collection is fully loaded, - * otherwise only a subset of potentially loaded classes may be returned. + * NOTE: after this method finishes, the class map is considered to be fully-loaded + * and thus sealed. This has one side-effect: if we filter out some of the classes + * with `load` predicate, these classes will never be loaded. */ - public List<T> collectLoadedClasses() { - List<T> loadedClasses = new ArrayList<>(); + public void forceLoad(Predicate<DexType> load) { + Set<DexType> knownClasses; + ClassProvider<T> classProvider; + synchronized (classes) { - for (Value<T> value : classes.values()) { - // NOTE: value mutations are NOT synchronized on `classes`, here we actually - // can see value which is not ready yet. Since everything that exists should - // be guaranteed by the caller to be loaded at this point, this can only happen - // if the code references classes that do not exist. Therefore, if the value is - // not ready here, we know that the loaded value will be 'null' once it is ready. - if (value.ready && value.clazz != null) { - loadedClasses.add(value.clazz); - } + classProvider = this.classProvider; + if (classProvider == null) { + return; } + + // Collects the types which might be represented in fully loaded class map. + knownClasses = Sets.newIdentityHashSet(); + knownClasses.addAll(classes.keySet()); } - return loadedClasses; - } - /** Forces loading of all the classes satisfying the criteria specified. */ - public void forceLoad(Predicate<DexType> load) { - if (classProvider != null) { - Set<DexType> loaded = Sets.newIdentityHashSet(); - synchronized (classes) { - loaded.addAll(classes.keySet()); + // Add all types the class provider provides. Note that it may take time for class + // provider to collect these types, so ve do it outside synchronized context. + knownClasses.addAll(classProvider.collectTypes()); + + // Make sure all the types in `knownClasses` are loaded. + // + // We just go and touch every class, thus triggering their loading if they + // are not loaded so far. In case the class has already been loaded, + // touching the class will be a no-op with minimal overhead. + for (DexType type : knownClasses) { + if (load.test(type)) { + get(type); } - Collection<DexType> types = classProvider.collectTypes(); - for (DexType type : types) { - if (load.test(type) && !loaded.contains(type)) { - get(type); // force-load type. + } + + synchronized (classes) { + if (this.classProvider == null) { + return; // Has been force-loaded concurrently. + } + + // We avoid calling get() on a class supplier unless we know it was loaded. + // At this time `classes` may have more types then `knownClasses`, but for + // all extra classes we expect the supplier to return 'null' after loading. + Iterator<Map.Entry<DexType, Supplier<T>>> iterator = classes.entrySet().iterator(); + while (iterator.hasNext()) { + Map.Entry<DexType, Supplier<T>> e = iterator.next(); + + if (knownClasses.contains(e.getKey())) { + // Get the class (it is expected to be loaded by this time). + T clazz = e.getValue().get(); + if (clazz != null) { + // Since the class is already loaded, get rid of possible wrapping suppliers. + assert clazz.type == e.getKey(); + e.setValue(getTransparentSupplier(clazz)); + continue; + } } + + // If the type is not in `knownClasses` or resolves to `null`, + // just remove the record from the map. + iterator.remove(); } + + // Mark the class map as fully loaded. + this.classProvider = null; } } - // Represents a value in the class map. - final static class Value<T> { - volatile boolean ready; - T clazz; - - Value() { - ready = false; - clazz = null; + // Supplier implementing a thread-safe loader for a class loaded from a + // class provider. Helps avoid synchronizing on the whole class map + // when loading a class. + private static class ConcurrentClassLoader<T extends DexClass> implements Supplier<T> { + private ClassMap<T> classMap; + private ClassProvider<T> provider; + private DexType type; + + private T clazz = null; + private volatile boolean ready = false; + + ConcurrentClassLoader(ClassMap<T> classMap, ClassProvider<T> provider, DexType type) { + this.classMap = classMap; + this.provider = provider; + this.type = type; } - Value(T clazz) { - this.clazz = clazz; - this.ready = true; + @Override + public T get() { + if (ready) { + return clazz; + } + + synchronized (this) { + if (!ready) { + assert classMap != null && provider != null && type != null; + provider.collectClass(type, createdClass -> { + assert createdClass != null; + assert classMap.getClassKind().isOfKind(createdClass); + assert !ready; + + if (createdClass.type != type) { + throw new CompilationError( + "Class content provided for type descriptor " + type.toSourceString() + + " actually defines class " + createdClass.type.toSourceString()); + } + + if (clazz == null) { + clazz = createdClass; + } else { + // The class resolution *may* generate a compilation error as one of + // possible resolutions. In this case we leave `value` in (false, null) + // state so in rare case of another thread trying to get the same class + // before this error is propagated it will get the same conflict. + T oldClass = clazz; + clazz = null; + clazz = classMap.resolveClassConflict(oldClass, createdClass); + } + }); + + classMap = null; + provider = null; + type = null; + ready = true; + } + } + + assert ready; + assert classMap == null && provider == null && type == null; + return clazz; } } } diff --git a/src/main/java/com/android/tools/r8/utils/ClasspathClassCollection.java b/src/main/java/com/android/tools/r8/utils/ClasspathClassCollection.java index ee00c3976..45002d003 100644 --- a/src/main/java/com/android/tools/r8/utils/ClasspathClassCollection.java +++ b/src/main/java/com/android/tools/r8/utils/ClasspathClassCollection.java @@ -6,6 +6,7 @@ package com.android.tools.r8.utils; import com.android.tools.r8.errors.CompilationError; import com.android.tools.r8.graph.ClassKind; import com.android.tools.r8.graph.DexClasspathClass; +import java.util.function.Supplier; /** Represents a collection of classpath classes. */ public class ClasspathClassCollection extends ClassMap<DexClasspathClass> { @@ -19,6 +20,11 @@ public class ClasspathClassCollection extends ClassMap<DexClasspathClass> { } @Override + Supplier<DexClasspathClass> getTransparentSupplier(DexClasspathClass clazz) { + return clazz; + } + + @Override ClassKind getClassKind() { return ClassKind.CLASSPATH; } diff --git a/src/main/java/com/android/tools/r8/utils/InternalOptions.java b/src/main/java/com/android/tools/r8/utils/InternalOptions.java index 9d6cfa5ea..7155a13df 100644 --- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java +++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java @@ -15,6 +15,7 @@ import com.google.common.collect.ImmutableSet; import java.nio.file.Path; import java.util.List; import java.util.function.BiFunction; +import java.util.function.Function; public class InternalOptions { @@ -140,8 +141,7 @@ public class InternalOptions { } public static class TestingOptions { - - public BiFunction<List<DexEncodedMethod>, CallGraph.Leaves, List<DexEncodedMethod>> irOrdering; + public Function<List<DexEncodedMethod>, List<DexEncodedMethod>> irOrdering; } public static class AttributeRemovalOptions { @@ -251,15 +251,18 @@ public class InternalOptions { public void ensureValid(boolean isMinifying) { if (innerClasses && !enclosingMethod) { - throw new CompilationError("Attribute InnerClasses implies EnclosingMethod attribute. " + - "Check -keepattributes directive."); + throw new CompilationError("Attribute InnerClasses requires EnclosingMethod attribute. " + + "Check -keepattributes directive."); } else if (!innerClasses && enclosingMethod) { - throw new CompilationError("Attribute EnclosingMethod requires InnerClasses attribute. " + - "Check -keepattributes directive."); + throw new CompilationError("Attribute EnclosingMethod requires InnerClasses attribute. " + + "Check -keepattributes directive."); + } else if (signature && !innerClasses) { + throw new CompilationError("Attribute Signature requires InnerClasses attribute. Check " + + "-keepattributes directive."); } else if (signature && isMinifying) { // TODO(38188583): Allow this once we can minify signatures. - throw new CompilationError("Attribute Signature cannot be kept when minifying. " + - "Check -keepattributes directive."); + throw new CompilationError("Attribute Signature cannot be kept when minifying. " + + "Check -keepattributes directive."); } } } diff --git a/src/main/java/com/android/tools/r8/utils/LibraryClassCollection.java b/src/main/java/com/android/tools/r8/utils/LibraryClassCollection.java index e11e660d3..c94d7beba 100644 --- a/src/main/java/com/android/tools/r8/utils/LibraryClassCollection.java +++ b/src/main/java/com/android/tools/r8/utils/LibraryClassCollection.java @@ -9,6 +9,7 @@ import com.android.tools.r8.graph.ClassKind; import com.android.tools.r8.graph.DexApplication; import com.android.tools.r8.graph.DexLibraryClass; import com.android.tools.r8.logging.Log; +import java.util.function.Supplier; /** Represents a collection of library classes. */ public class LibraryClassCollection extends ClassMap<DexLibraryClass> { @@ -31,6 +32,11 @@ public class LibraryClassCollection extends ClassMap<DexLibraryClass> { } @Override + Supplier<DexLibraryClass> getTransparentSupplier(DexLibraryClass clazz) { + return clazz; + } + + @Override ClassKind getClassKind() { return ClassKind.LIBRARY; } diff --git a/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java b/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java index a37eb92b0..590ba834a 100644 --- a/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java +++ b/src/main/java/com/android/tools/r8/utils/ProgramClassCollection.java @@ -11,25 +11,20 @@ import com.android.tools.r8.graph.DexType; import com.android.tools.r8.ir.desugar.LambdaRewriter; import java.util.IdentityHashMap; import java.util.List; +import java.util.function.Supplier; /** Represents a collection of library classes. */ public class ProgramClassCollection extends ClassMap<DexProgramClass> { public static ProgramClassCollection create(List<DexProgramClass> classes) { // We have all classes preloaded, but not necessarily without conflicts. - IdentityHashMap<DexType, Value<DexProgramClass>> map = new IdentityHashMap<>(); + IdentityHashMap<DexType, Supplier<DexProgramClass>> map = new IdentityHashMap<>(); for (DexProgramClass clazz : classes) { - Value<DexProgramClass> value = map.get(clazz.type); - if (value == null) { - value = new Value<>(clazz); - map.put(clazz.type, value); - } else { - value.clazz = resolveClassConflictImpl(value.clazz, clazz); - } + map.merge(clazz.type, clazz, (a, b) -> resolveClassConflictImpl(a.get(), b.get())); } return new ProgramClassCollection(map); } - private ProgramClassCollection(IdentityHashMap<DexType, Value<DexProgramClass>> classes) { + private ProgramClassCollection(IdentityHashMap<DexType, Supplier<DexProgramClass>> classes) { super(classes, null); } @@ -44,6 +39,11 @@ public class ProgramClassCollection extends ClassMap<DexProgramClass> { } @Override + Supplier<DexProgramClass> getTransparentSupplier(DexProgramClass clazz) { + return clazz; + } + + @Override ClassKind getClassKind() { return ClassKind.PROGRAM; } |