Rewrite outliner state with lens
Change-Id: I79e59d37c3110fa860469943cbce6245ff3d1f2c
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 83fc48c..8de51ce 100644
--- a/src/main/java/com/android/tools/r8/graph/Code.java
+++ b/src/main/java/com/android/tools/r8/graph/Code.java
@@ -8,7 +8,7 @@
import com.android.tools.r8.ir.code.IRCode;
import com.android.tools.r8.ir.code.NumberGenerator;
import com.android.tools.r8.ir.code.Position;
-import com.android.tools.r8.ir.optimize.Outliner.OutlineCode;
+import com.android.tools.r8.ir.optimize.OutlinerImpl.OutlineCode;
import com.android.tools.r8.naming.ClassNameMapper;
import com.android.tools.r8.origin.Origin;
import it.unimi.dsi.fastutil.ints.Int2ReferenceMap;
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 8f2a62f..0235660 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
@@ -73,7 +73,6 @@
import com.android.tools.r8.ir.optimize.Inliner;
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
import com.android.tools.r8.ir.optimize.MemberValuePropagation;
-import com.android.tools.r8.ir.optimize.Outliner;
import com.android.tools.r8.ir.optimize.PeepholeOptimizer;
import com.android.tools.r8.ir.optimize.RedundantFieldLoadElimination;
import com.android.tools.r8.ir.optimize.ReflectionOptimizer;
@@ -88,6 +87,7 @@
import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackIgnore;
import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackSimple;
import com.android.tools.r8.ir.optimize.info.field.InstanceFieldInitializationInfoCollection;
+import com.android.tools.r8.ir.optimize.outliner.Outliner;
import com.android.tools.r8.ir.optimize.staticizer.ClassStaticizer;
import com.android.tools.r8.ir.optimize.string.StringBuilderOptimizer;
import com.android.tools.r8.ir.optimize.string.StringOptimizer;
@@ -141,7 +141,7 @@
private final ClassStaticizer classStaticizer;
private final InternalOptions options;
private final CfgPrinter printer;
- private final CodeRewriter codeRewriter;
+ public final CodeRewriter codeRewriter;
private final ConstantCanonicalizer constantCanonicalizer;
private final MemberValuePropagation memberValuePropagation;
private final LensCodeRewriter lensCodeRewriter;
@@ -159,7 +159,7 @@
private final DynamicTypeOptimization dynamicTypeOptimization;
final AssertionsRewriter assertionsRewriter;
- final DeadCodeRemover deadCodeRemover;
+ public final DeadCodeRemover deadCodeRemover;
private final MethodOptimizationInfoCollector methodOptimizationInfoCollector;
@@ -229,7 +229,7 @@
this.fieldAccessAnalysis = null;
this.libraryMethodOverrideAnalysis = null;
this.inliner = null;
- this.outliner = null;
+ this.outliner = Outliner.empty();
this.memberValuePropagation = null;
this.lensCodeRewriter = null;
this.identifierNameStringMarker = null;
@@ -270,7 +270,7 @@
this.enumUnboxer = options.enableEnumUnboxing ? new EnumUnboxer(appViewWithLiveness) : null;
this.lensCodeRewriter = new LensCodeRewriter(appViewWithLiveness, enumUnboxer);
this.inliner = new Inliner(appViewWithLiveness, lensCodeRewriter);
- this.outliner = new Outliner(appViewWithLiveness);
+ this.outliner = Outliner.create(appViewWithLiveness);
this.memberValuePropagation =
options.enableValuePropagation ? new MemberValuePropagation(appViewWithLiveness) : null;
this.methodOptimizationInfoCollector =
@@ -297,7 +297,7 @@
this.fieldAccessAnalysis = null;
this.libraryMethodOverrideAnalysis = null;
this.inliner = null;
- this.outliner = null;
+ this.outliner = Outliner.empty();
this.memberValuePropagation = null;
this.lensCodeRewriter = null;
this.identifierNameStringMarker = null;
@@ -651,6 +651,7 @@
ConsumerUtils.acceptIfNotNull(
inliner,
inliner -> inliner.initializeDoubleInlineCallers(graphLensForPrimaryOptimizationPass));
+ outliner.prepareForPrimaryOptimizationPass(graphLensForPrimaryOptimizationPass);
if (fieldAccessAnalysis != null) {
fieldAccessAnalysis.fieldAssignmentTracker().initialize();
@@ -667,9 +668,6 @@
appView.withLiveness(), postMethodProcessorBuilder, executorService, timing);
timing.end();
timing.begin("IR conversion phase 1");
- if (outliner != null) {
- outliner.createOutlineMethodIdentifierGenerator();
- }
assert appView.graphLens() == graphLensForPrimaryOptimizationPass;
primaryMethodProcessor.forEachMethod(
(method, methodProcessingContext) ->
@@ -727,6 +725,7 @@
}
if (enumUnboxer != null) {
+ outliner.rewriteWithLens();
enumUnboxer.unboxEnums(this, postMethodProcessorBuilder, executorService, feedback);
} else {
appView.setUnboxedEnums(EnumDataMap.empty());
@@ -739,6 +738,7 @@
classStaticizer ->
classStaticizer.prepareForSecondaryOptimizationPass(
graphLensForSecondaryOptimizationPass));
+ outliner.rewriteWithLens();
timing.begin("IR conversion phase 2");
PostMethodProcessor postMethodProcessor =
@@ -794,35 +794,7 @@
feedback.updateVisibleOptimizationInfo();
// TODO(b/127694949): Adapt to PostOptimization.
- if (outliner != null) {
- printPhase("Outlining");
- timing.begin("IR conversion phase 3");
- ProgramMethodSet methodsSelectedForOutlining = outliner.selectMethodsForOutlining();
- if (!methodsSelectedForOutlining.isEmpty()) {
- forEachSelectedOutliningMethod(
- methodsSelectedForOutlining,
- code -> {
- printMethod(code, "IR before outlining (SSA)", null);
- outliner.identifyOutlineSites(code);
- },
- executorService);
- List<ProgramMethod> outlineMethods = outliner.buildOutlineMethods();
- optimizeSynthesizedMethods(outlineMethods, executorService);
- forEachSelectedOutliningMethod(
- methodsSelectedForOutlining,
- code -> {
- outliner.applyOutliningCandidate(code);
- printMethod(code, "IR after outlining (SSA)", null);
- removeDeadCodeAndFinalizeIR(
- code, OptimizationFeedbackIgnore.getInstance(), Timing.empty());
- },
- executorService);
- feedback.updateVisibleOptimizationInfo();
- assert outliner.checkAllOutlineSitesFoundAgain();
- outlineMethods.forEach(m -> m.getDefinition().markNotProcessed());
- }
- timing.end();
- }
+ outliner.performOutlining(this, feedback, executorService, timing);
clearDexMethodCompilationState();
if (identifierNameStringMarker != null) {
@@ -1463,12 +1435,7 @@
// TODO(b/140766440): an ideal solution would be puttting CodeOptimization for this into
// the list for primary processing only.
- if (options.outline.enabled && outliner != null && methodProcessor.isPrimaryMethodProcessor()) {
- timing.begin("Identify outlines");
- outliner.getOutlineMethodIdentifierGenerator().accept(code);
- timing.end();
- assert code.isConsistentSSA();
- }
+ outliner.collectOutlineSites(code, timing);
assert code.verifyTypes(appView);
@@ -1957,13 +1924,13 @@
}
}
- private void printPhase(String phase) {
+ public void printPhase(String phase) {
if (!options.extensiveLoggingFilter.isEmpty()) {
System.out.println("Entering phase: " + phase);
}
}
- private String printMethod(IRCode code, String title, String previous) {
+ public String printMethod(IRCode code, String title, String previous) {
if (printer != null) {
printer.resetUnusedValue();
printer.begin("cfg");
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java b/src/main/java/com/android/tools/r8/ir/optimize/OutlinerImpl.java
similarity index 88%
rename from src/main/java/com/android/tools/r8/ir/optimize/Outliner.java
rename to src/main/java/com/android/tools/r8/ir/optimize/OutlinerImpl.java
index dfa9eac..958d8ac 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/Outliner.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/OutlinerImpl.java
@@ -53,8 +53,13 @@
import com.android.tools.r8.ir.code.ValueType;
import com.android.tools.r8.ir.code.ValueTypeConstraint;
import com.android.tools.r8.ir.conversion.IRBuilder;
+import com.android.tools.r8.ir.conversion.IRConverter;
import com.android.tools.r8.ir.conversion.SourceCode;
import com.android.tools.r8.ir.optimize.Inliner.ConstraintWithTarget;
+import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackDelayed;
+import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackIgnore;
+import com.android.tools.r8.ir.optimize.outliner.OutlineCollection;
+import com.android.tools.r8.ir.optimize.outliner.Outliner;
import com.android.tools.r8.naming.ClassNameMapper;
import com.android.tools.r8.origin.Origin;
import com.android.tools.r8.shaking.AppInfoWithLiveness;
@@ -65,8 +70,8 @@
import com.android.tools.r8.utils.ListUtils;
import com.android.tools.r8.utils.StringUtils;
import com.android.tools.r8.utils.StringUtils.BraceType;
-import com.android.tools.r8.utils.collections.LongLivedProgramMethodMultisetBuilder;
-import com.android.tools.r8.utils.collections.ProgramMethodMultiset;
+import com.android.tools.r8.utils.ThreadUtils;
+import com.android.tools.r8.utils.Timing;
import com.android.tools.r8.utils.collections.ProgramMethodSet;
import com.google.common.collect.Iterables;
import java.util.ArrayList;
@@ -78,6 +83,8 @@
import java.util.Map;
import java.util.Map.Entry;
import java.util.Objects;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
import java.util.function.Consumer;
/**
@@ -87,37 +94,41 @@
*
* <ul>
* <li>First, all methods are converted to IR and passed to {@link
- * Outliner#createOutlineMethodIdentifierGenerator()}} to identify outlining candidates and
- * the methods containing each candidate. IR is converted to the output format (DEX or CF) and
- * thrown away along with the outlining candidates; only a list of lists of methods is kept,
- * where each list of methods corresponds to methods containing an outlining candidate.
- * <li>Second, {@link Outliner#selectMethodsForOutlining()} is called to retain the lists of
+ * OutlinerImpl#collectOutlineSites} to identify outlining candidates and the methods
+ * containing each candidate. IR is converted to the output format (DEX or CF) and thrown away
+ * along with the outlining candidates; only a list of lists of methods is kept, where each
+ * list of methods corresponds to methods containing an outlining candidate.
+ * <li>Second, {@link OutlinerImpl#selectMethodsForOutlining()} is called to retain the lists of
* methods found in the first step that are large enough (see {@link InternalOptions#outline}
* {@link OutlineOptions#threshold}). Each selected method is then converted back to IR and
- * passed to {@link Outliner#identifyOutlineSites(IRCode)}, which then stores concrete
- * outlining candidates in {@link Outliner#outlineSites}.
- * <li>Third, {@link Outliner#buildOutlineMethods()} is called to construct the <em>outline
+ * passed to {@link OutlinerImpl#identifyOutlineSites(IRCode)}, which then stores concrete
+ * outlining candidates in {@link OutlinerImpl#outlineSites}.
+ * <li>Third, {@link OutlinerImpl#buildOutlineMethods()} is called to construct the <em>outline
* support classes</em> containing a static helper method for each outline candidate that
* occurs frequently enough. Each selected method is then converted to IR, passed to {@link
- * Outliner#applyOutliningCandidate(IRCode)} to perform the outlining, and converted back to
- * the output format (DEX or CF).
+ * OutlinerImpl#applyOutliningCandidate(IRCode)} to perform the outlining, and converted back
+ * to the output format (DEX or CF).
* </ul>
*/
-public class Outliner {
+public class OutlinerImpl extends Outliner {
- /** Result of first step (see {@link Outliner#createOutlineMethodIdentifierGenerator()}. */
- private final List<LongLivedProgramMethodMultisetBuilder> candidateMethodLists =
- new ArrayList<>();
- /** Result of second step (see {@link Outliner#selectMethodsForOutlining()}. */
+ /**
+ * Result of first step (see {@link OutlinerImpl#prepareForPrimaryOptimizationPass(GraphLens)}
+ * ()}.
+ */
+ private OutlineCollection outlineCollection;
+
+ /** Result of second step (see {@link OutlinerImpl#selectMethodsForOutlining()}. */
private final Map<Outline, List<ProgramMethod>> outlineSites = new HashMap<>();
- /** Result of third step (see {@link Outliner#buildOutlineMethods()}. */
+
+ /** Result of third step (see {@link OutlinerImpl#buildOutlineMethods()}. */
private final Map<Outline, DexMethod> generatedOutlines = new HashMap<>();
static final int MAX_IN_SIZE = 5; // Avoid using ranged calls for outlined code.
private final AppView<AppInfoWithLiveness> appView;
private final InliningConstraints inliningConstraints;
-
+
private abstract static class OutlineInstruction {
// Value signaling that this is the one allowed temporary register for an outline.
@@ -196,6 +207,8 @@
public abstract int numberOfInputs();
public abstract int createInstruction(IRBuilder builder, Outline outline, int argumentMapIndex);
+
+ public abstract boolean needsLensRewriting(GraphLens currentGraphLens);
}
private static class BinOpOutlineInstruction extends OutlineInstruction {
@@ -301,6 +314,11 @@
builder.add(newInstruction);
return argumentMapIndex;
}
+
+ @Override
+ public boolean needsLensRewriting(GraphLens currentGraphLens) {
+ return false;
+ }
}
private static class NewInstanceOutlineInstruction extends OutlineInstruction {
@@ -365,6 +383,11 @@
builder.add(newInstruction);
return argumentMapIndex;
}
+
+ @Override
+ public boolean needsLensRewriting(GraphLens currentGraphLens) {
+ return currentGraphLens.lookupType(clazz) != clazz;
+ }
}
private static class InvokeOutlineInstruction extends OutlineInstruction {
@@ -503,6 +526,11 @@
builder.add(newInstruction);
return argumentMapIndex;
}
+
+ @Override
+ public boolean needsLensRewriting(GraphLens currentGraphLens) {
+ return currentGraphLens.getRenamedMethodSignature(method) != method;
+ }
}
// Representation of an outline.
@@ -575,6 +603,28 @@
return proto;
}
+ public Outline rewrittenWithLens(GraphLens currentGraphLens) {
+ if (needsLensRewriting(currentGraphLens)) {
+ // Discard this outline.
+ return null;
+ }
+ return this;
+ }
+
+ private boolean needsLensRewriting(GraphLens currentGraphLens) {
+ for (DexType argumentType : argumentTypes) {
+ if (currentGraphLens.lookupType(argumentType) != argumentType) {
+ return true;
+ }
+ }
+ if (currentGraphLens.lookupType(returnType) != returnType) {
+ return true;
+ }
+ return Iterables.any(
+ templateInstructions,
+ templateInstruction -> templateInstruction.needsLensRewriting(currentGraphLens));
+ }
+
@Override
public boolean equals(Object other) {
if (!(other instanceof Outline)) {
@@ -1135,27 +1185,17 @@
// TODO(sgjesse): This does not take several usages in the same method into account.
private class OutlineMethodIdentifier extends OutlineSpotter {
- private final Map<Outline, LongLivedProgramMethodMultisetBuilder> candidateMap;
+ private final List<Outline> outlinesForMethod;
OutlineMethodIdentifier(
- ProgramMethod method,
- BasicBlock block,
- Map<Outline, LongLivedProgramMethodMultisetBuilder> candidateMap) {
+ ProgramMethod method, BasicBlock block, List<Outline> outlinesForMethod) {
super(method, block);
- this.candidateMap = candidateMap;
+ this.outlinesForMethod = outlinesForMethod;
}
@Override
protected void handle(int start, int end, Outline outline) {
- synchronized (candidateMap) {
- candidateMap.computeIfAbsent(outline, this::addOutlineMethodList).add(method);
- }
- }
-
- private LongLivedProgramMethodMultisetBuilder addOutlineMethodList(Outline outline) {
- LongLivedProgramMethodMultisetBuilder result = LongLivedProgramMethodMultisetBuilder.create();
- candidateMethodLists.add(result);
- return result;
+ outlinesForMethod.add(outline);
}
}
@@ -1270,37 +1310,107 @@
}
}
- public Outliner(AppView<AppInfoWithLiveness> appView) {
+ public OutlinerImpl(AppView<AppInfoWithLiveness> appView) {
this.appView = appView;
this.inliningConstraints = new InliningConstraints(appView, GraphLens.getIdentityLens());
}
- public void createOutlineMethodIdentifierGenerator() {
- // Since optimizations may change the map identity of Outline objects (e.g. by setting the
- // out-value of invokes to null), this map must not be used except for identifying methods
- // potentially relevant to outlining. OutlineMethodIdentifier will add method lists to
- // candidateMethodLists whenever it adds an entry to candidateMap.
- Map<Outline, LongLivedProgramMethodMultisetBuilder> candidateMap = new HashMap<>();
- assert candidateMethodLists.isEmpty();
- assert outlineMethodIdentifierGenerator == null;
- outlineMethodIdentifierGenerator =
- code -> {
- ProgramMethod context = code.context();
- assert !context.getDefinition().getCode().isOutlineCode();
- if (ClassToFeatureSplitMap.isInFeature(context.getHolder(), appView)) {
- return;
- }
- for (BasicBlock block : code.blocks) {
- new OutlineMethodIdentifier(context, block, candidateMap).process();
- }
- };
+ @Override
+ public void prepareForPrimaryOptimizationPass(GraphLens graphLensForPrimaryOptimizationPass) {
+ assert appView.graphLens() == graphLensForPrimaryOptimizationPass;
+ assert outlineCollection == null;
+ outlineCollection = new OutlineCollection(graphLensForPrimaryOptimizationPass);
}
- private Consumer<IRCode> outlineMethodIdentifierGenerator;
+ @Override
+ public void performOutlining(
+ IRConverter converter,
+ OptimizationFeedbackDelayed feedback,
+ ExecutorService executorService,
+ Timing timing)
+ throws ExecutionException {
+ converter.printPhase("Outlining");
+ timing.begin("IR conversion phase 3");
+ ProgramMethodSet methodsSelectedForOutlining = selectMethodsForOutlining();
+ if (!methodsSelectedForOutlining.isEmpty()) {
+ forEachSelectedOutliningMethod(
+ converter,
+ methodsSelectedForOutlining,
+ code -> {
+ converter.printMethod(code, "IR before outlining (SSA)", null);
+ identifyOutlineSites(code);
+ },
+ executorService);
+ List<ProgramMethod> outlineMethods = buildOutlineMethods();
+ converter.optimizeSynthesizedMethods(outlineMethods, executorService);
+ forEachSelectedOutliningMethod(
+ converter,
+ methodsSelectedForOutlining,
+ code -> {
+ applyOutliningCandidate(code);
+ converter.printMethod(code, "IR after outlining (SSA)", null);
+ converter.removeDeadCodeAndFinalizeIR(
+ code, OptimizationFeedbackIgnore.getInstance(), Timing.empty());
+ },
+ executorService);
+ feedback.updateVisibleOptimizationInfo();
+ assert checkAllOutlineSitesFoundAgain();
+ outlineMethods.forEach(m -> m.getDefinition().markNotProcessed());
+ }
+ timing.end();
+ }
- public Consumer<IRCode> getOutlineMethodIdentifierGenerator() {
- assert outlineMethodIdentifierGenerator != null;
- return outlineMethodIdentifierGenerator;
+ private void forEachSelectedOutliningMethod(
+ IRConverter converter,
+ ProgramMethodSet methodsSelectedForOutlining,
+ Consumer<IRCode> consumer,
+ ExecutorService executorService)
+ throws ExecutionException {
+ assert !appView.options().skipIR;
+ ThreadUtils.processItems(
+ methodsSelectedForOutlining,
+ method -> {
+ IRCode code = method.buildIR(appView);
+ assert code != null;
+ assert !method.getDefinition().getCode().isOutlineCode();
+ // Instead of repeating all the optimizations of rewriteCode(), only run the
+ // optimizations needed for outlining: rewriteMoveResult() to remove out-values on
+ // StringBuilder/StringBuffer method invocations, and removeDeadCode() to remove
+ // unused out-values.
+ converter.codeRewriter.rewriteMoveResult(code);
+ converter.deadCodeRemover.run(code, Timing.empty());
+ CodeRewriter.removeAssumeInstructions(appView, code);
+ consumer.accept(code);
+ },
+ executorService);
+ }
+
+ public void rewriteWithLens() {
+ // Rewrite the outline collection with the graph lens, such that the reprocessing of methods
+ // will correctly delete/rewrite entries in the outline collection.
+ outlineCollection.rewriteWithLens(appView.graphLens());
+ }
+
+ @Override
+ public void collectOutlineSites(IRCode code, Timing timing) {
+ if (outlineCollection == null) {
+ return;
+ }
+
+ ProgramMethod context = code.context();
+ assert !context.getDefinition().getCode().isOutlineCode();
+
+ if (ClassToFeatureSplitMap.isInFeature(context.getHolder(), appView)) {
+ return;
+ }
+
+ timing.begin("Collect outlines");
+ List<Outline> outlinesForMethod = new ArrayList<>();
+ for (BasicBlock block : code.blocks) {
+ new OutlineMethodIdentifier(context, block, outlinesForMethod).process();
+ }
+ outlineCollection.set(appView, context, outlinesForMethod);
+ timing.end();
}
public void identifyOutlineSites(IRCode code) {
@@ -1313,16 +1423,9 @@
}
public ProgramMethodSet selectMethodsForOutlining() {
- ProgramMethodSet methodsSelectedForOutlining = ProgramMethodSet.create();
- assert outlineSites.isEmpty();
- for (LongLivedProgramMethodMultisetBuilder outlineMethods : candidateMethodLists) {
- if (outlineMethods.size() >= appView.options().outline.threshold) {
- ProgramMethodMultiset multiset = outlineMethods.build(appView);
- multiset.forEachEntry((method, ignore) -> methodsSelectedForOutlining.add(method));
- }
- }
- candidateMethodLists.clear();
- return methodsSelectedForOutlining;
+ ProgramMethodSet result = outlineCollection.computeMethodsSubjectToOutlining(appView);
+ outlineCollection = null;
+ return result;
}
public List<ProgramMethod> buildOutlineMethods() {
@@ -1374,7 +1477,6 @@
private List<Outline> selectOutlines() {
assert !outlineSites.isEmpty();
- assert candidateMethodLists.isEmpty();
List<Outline> result = new ArrayList<>();
for (Entry<Outline, List<ProgramMethod>> entry : outlineSites.entrySet()) {
if (entry.getValue().size() >= appView.options().outline.threshold) {
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/outliner/OutlineCollection.java b/src/main/java/com/android/tools/r8/ir/optimize/outliner/OutlineCollection.java
new file mode 100644
index 0000000..16e4dab
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/outliner/OutlineCollection.java
@@ -0,0 +1,122 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.outliner;
+
+import static com.android.tools.r8.utils.MapUtils.ignoreKey;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProgramClass;
+import com.android.tools.r8.graph.GraphLens;
+import com.android.tools.r8.graph.ProgramMethod;
+import com.android.tools.r8.ir.optimize.OutlinerImpl.Outline;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.ListUtils;
+import com.android.tools.r8.utils.collections.ProgramMethodSet;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.ConcurrentHashMap;
+import java.util.function.Function;
+
+// Maps each method to the outline candidates found in the method.
+public class OutlineCollection {
+
+ private final Map<Outline, Outline> canonicalization = new ConcurrentHashMap<>();
+
+ private GraphLens appliedGraphLens;
+ private Map<DexMethod, List<Outline>> outlines = new ConcurrentHashMap<>();
+
+ public OutlineCollection(GraphLens graphLensForPrimaryOptimizationPass) {
+ this.appliedGraphLens = graphLensForPrimaryOptimizationPass;
+ }
+
+ public void set(
+ AppView<AppInfoWithLiveness> appView, ProgramMethod method, List<Outline> outlinesForMethod) {
+ assert appView.graphLens() == appliedGraphLens;
+ if (outlinesForMethod.isEmpty()) {
+ // If we are reprocessing the method, and found no instructions sequences eligible for
+ // outlining, then clear the outline candidates for the given method.
+ outlines.remove(method.getReference());
+ } else {
+ outlines.put(method.getReference(), canonicalize(outlinesForMethod));
+ }
+ }
+
+ public void rewriteWithLens(GraphLens currentGraphLens) {
+ if (currentGraphLens == appliedGraphLens) {
+ return;
+ }
+
+ Map<DexMethod, List<Outline>> rewrittenOutlines = new ConcurrentHashMap<>(outlines.size());
+ outlines.forEach(
+ (method, outlinesForMethod) -> {
+ DexMethod rewrittenMethod =
+ currentGraphLens.getRenamedMethodSignature(method, appliedGraphLens);
+ assert !rewrittenOutlines.containsKey(rewrittenMethod);
+ List<Outline> rewrittenOutlinesForMethod =
+ rewriteOutlinesWithLens(outlinesForMethod, currentGraphLens);
+ if (!rewrittenOutlinesForMethod.isEmpty()) {
+ rewrittenOutlines.put(rewrittenMethod, rewrittenOutlinesForMethod);
+ }
+ });
+ outlines = rewrittenOutlines;
+
+ // Record that this collection is now rewritten up until the point of the given graph lens.
+ appliedGraphLens = currentGraphLens;
+ }
+
+ private List<Outline> rewriteOutlinesWithLens(
+ List<Outline> outlines, GraphLens currentGraphLens) {
+ assert currentGraphLens != appliedGraphLens;
+ return ListUtils.mapOrElse(outlines, outline -> outline.rewrittenWithLens(currentGraphLens));
+ }
+
+ public ProgramMethodSet computeMethodsSubjectToOutlining(AppView<AppInfoWithLiveness> appView) {
+ ProgramMethodSet result = ProgramMethodSet.create();
+ Map<Outline, List<ProgramMethod>> methodsPerOutline = computeMethodsPerOutline(appView);
+ for (List<ProgramMethod> methodsWithSameOutline : methodsPerOutline.values()) {
+ if (methodsWithSameOutline.size() >= appView.options().outline.threshold) {
+ result.addAll(methodsWithSameOutline);
+ }
+ }
+ return result;
+ }
+
+ private Map<Outline, List<ProgramMethod>> computeMethodsPerOutline(
+ AppView<AppInfoWithLiveness> appView) {
+ Map<Outline, List<ProgramMethod>> methodsPerOutline = new HashMap<>();
+ outlines.forEach(
+ (reference, outlinesForMethod) -> {
+ DexMethod rewrittenReference =
+ appView.graphLens().getRenamedMethodSignature(reference, appliedGraphLens);
+ DexProgramClass holder =
+ DexProgramClass.asProgramClassOrNull(
+ appView.definitionFor(rewrittenReference.getHolderType()));
+ ProgramMethod method = rewrittenReference.lookupOnProgramClass(holder);
+ if (method != null) {
+ for (Outline outline : outlinesForMethod) {
+ methodsPerOutline.computeIfAbsent(outline, ignoreKey(ArrayList::new)).add(method);
+ }
+ } else {
+ assert false;
+ }
+ });
+ return methodsPerOutline;
+ }
+
+ private List<Outline> canonicalize(List<Outline> outlines) {
+ List<Outline> canonicalizedOutlines = new ArrayList<>(outlines.size());
+ for (Outline outline : outlines) {
+ canonicalizedOutlines.add(canonicalize(outline));
+ }
+ return canonicalizedOutlines;
+ }
+
+ private Outline canonicalize(Outline outline) {
+ return canonicalization.computeIfAbsent(outline, Function.identity());
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/outliner/Outliner.java b/src/main/java/com/android/tools/r8/ir/optimize/outliner/Outliner.java
new file mode 100644
index 0000000..a2bd90f
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/outliner/Outliner.java
@@ -0,0 +1,66 @@
+// Copyright (c) 2021, the R8 project authors. Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+package com.android.tools.r8.ir.optimize.outliner;
+
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.GraphLens;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.conversion.IRConverter;
+import com.android.tools.r8.ir.optimize.OutlinerImpl;
+import com.android.tools.r8.ir.optimize.info.OptimizationFeedbackDelayed;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.Timing;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.ExecutorService;
+
+public abstract class Outliner {
+
+ public static Outliner create(AppView<AppInfoWithLiveness> appView) {
+ return appView.options().outline.enabled ? new OutlinerImpl(appView) : empty();
+ }
+
+ public static Outliner empty() {
+ return new Outliner() {
+ @Override
+ public void collectOutlineSites(IRCode code, Timing timing) {
+ // Intentionally empty.
+ }
+
+ @Override
+ public void prepareForPrimaryOptimizationPass(GraphLens graphLensForPrimaryOptimizationPass) {
+ // Intentionally empty.
+ }
+
+ @Override
+ public void performOutlining(
+ IRConverter converter,
+ OptimizationFeedbackDelayed feedback,
+ ExecutorService executorService,
+ Timing timing)
+ throws ExecutionException {
+ // Intentionally empty.
+ }
+
+ @Override
+ public void rewriteWithLens() {
+ // Intentionally empty.
+ }
+ };
+ }
+
+ public abstract void collectOutlineSites(IRCode code, Timing timing);
+
+ public abstract void prepareForPrimaryOptimizationPass(
+ GraphLens graphLensForPrimaryOptimizationPass);
+
+ public abstract void performOutlining(
+ IRConverter converter,
+ OptimizationFeedbackDelayed feedback,
+ ExecutorService executorService,
+ Timing timing)
+ throws ExecutionException;
+
+ public abstract void rewriteWithLens();
+}
