Introduce disabled optimization ListIterationRewriter
This is to rewrite iterator-based for-each loops to indexed loops.
Adds a test, InternalOptions flag, and initial optimization.
It does not kick in when List subclass is not known.
For Chrome, this converts 1010 out of 1731 possible loops. The
remaining 721 are those where the type is not ArrayList or
ImmutableList (e.g. most are of type "List").
The DEX size shrank by 300 bytes.
Follow-ups:
* Enable the optimization
* Add more allowlisted list types (e.g. kotlin lists)
Bug: b/145280859
Change-Id: Ifb63ad5295207f6309060db9cd6d4be58a46d4d7
diff --git a/src/main/java/com/android/tools/r8/R8.java b/src/main/java/com/android/tools/r8/R8.java
index 46f11fd..1baf054 100644
--- a/src/main/java/com/android/tools/r8/R8.java
+++ b/src/main/java/com/android/tools/r8/R8.java
@@ -49,6 +49,7 @@
import com.android.tools.r8.ir.desugar.records.RecordInstructionDesugaring;
import com.android.tools.r8.ir.desugar.varhandle.VarHandleDesugaring;
import com.android.tools.r8.ir.optimize.Inliner;
+import com.android.tools.r8.ir.optimize.ListIterationRewriter;
import com.android.tools.r8.ir.optimize.NestReducer;
import com.android.tools.r8.ir.optimize.SwitchMapCollector;
import com.android.tools.r8.ir.optimize.enums.EnumUnboxingCfMethods;
@@ -359,6 +360,7 @@
timing.begin("Strip unused code");
timing.begin("Before enqueuer");
List<ProguardConfigurationRule> synthesizedProguardRules;
+ boolean enableListIterationRewriter;
try {
synthesizedProguardRules = ProguardConfigurationUtils.synthesizeRules(appView);
ProfileCollectionAdditions profileCollectionAdditions =
@@ -424,6 +426,7 @@
ExceptionUtils.withFinishedResourceHandler(
options.reporter, options.proguardSeedsConsumer);
}
+
if (options.isShrinking()) {
// Mark dead proto extensions fields as neither being read nor written. This step must
// run prior to the tree pruner.
@@ -462,6 +465,10 @@
assert appView.checkForTesting(() -> allReferencesAssignedApiLevel(appViewWithLiveness));
}
+
+ // Compute after initial round of tree shaking to not trigger on pruned classes.
+ enableListIterationRewriter = ListIterationRewriter.shouldEnable(appView, subtypingInfo);
+
timing.end();
} finally {
timing.end();
@@ -536,7 +543,7 @@
assert ArtProfileCompletenessChecker.verify(appView);
- new PrimaryR8IRConverter(appViewWithLiveness, timing)
+ new PrimaryR8IRConverter(appViewWithLiveness, timing, enableListIterationRewriter)
.optimize(appViewWithLiveness, executorService);
assert LirConverter.verifyLirOnly(appView);
diff --git a/src/main/java/com/android/tools/r8/graph/AppView.java b/src/main/java/com/android/tools/r8/graph/AppView.java
index 9f3483e..eb26701 100644
--- a/src/main/java/com/android/tools/r8/graph/AppView.java
+++ b/src/main/java/com/android/tools/r8/graph/AppView.java
@@ -514,6 +514,11 @@
return appInfo().definitionFor(type);
}
+ @Override
+ public final boolean hasDefinitionFor(DexType type) {
+ return appInfo().hasDefinitionFor(type);
+ }
+
public OptionalBool isInterface(DexType type) {
assert type.isClassType();
// Without whole program information we should not assume anything about any other class than
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 586b968..a79ae60 100644
--- a/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
+++ b/src/main/java/com/android/tools/r8/graph/DexItemFactory.java
@@ -225,6 +225,9 @@
public final DexString convertMethodName = createString("convert");
public final DexString wrapperFieldName = createString("wrappedValue");
+ public final DexString iteratorName = createString("iterator");
+ public final DexString hasNextName = createString("hasNext");
+ public final DexString nextName = createString("next");
public final DexString getClassMethodName = createString("getClass");
public final DexString finalizeMethodName = createString("finalize");
public final DexString ordinalMethodName = createString("ordinal");
@@ -484,7 +487,6 @@
public final DexType serviceLoaderType = createStaticallyKnownType(serviceLoaderDescriptor);
public final DexType serviceLoaderConfigurationErrorType =
createStaticallyKnownType(serviceLoaderConfigurationErrorDescriptor);
- public final DexType listType = createStaticallyKnownType(listDescriptor);
public final DexType setType = createStaticallyKnownType(setDescriptor);
public final DexType mapType = createStaticallyKnownType(mapDescriptor);
public final DexType mapEntryType = createStaticallyKnownType(mapEntryDescriptor);
@@ -613,12 +615,20 @@
public final DexType javaNioByteOrderType = createStaticallyKnownType("Ljava/nio/ByteOrder;");
public final DexType javaUtilCollectionsType =
createStaticallyKnownType("Ljava/util/Collections;");
+ public final DexType javaUtilIteratorType = createStaticallyKnownType("Ljava/util/Iterator;");
+ public final DexProto javaUtilIteratorProto = createProto(javaUtilIteratorType);
public final DexType javaUtilComparatorType = createStaticallyKnownType("Ljava/util/Comparator;");
public final DexType javaUtilConcurrentTimeUnitType =
createStaticallyKnownType("Ljava/util/concurrent/TimeUnit;");
public final DexType javaUtilFormattableType =
createStaticallyKnownType("Ljava/util/Formattable;");
- public final DexType javaUtilListType = createStaticallyKnownType("Ljava/util/List;");
+ public final DexType javaUtilListType = createStaticallyKnownType(listDescriptor);
+ public final DexType javaUtilArrayListType = createStaticallyKnownType("Ljava/util/ArrayList;");
+ public final DexType javaUtilLinkedListType = createStaticallyKnownType("Ljava/util/LinkedList;");
+ public final DexType comGoogleCommonCollectImmutableListType =
+ createStaticallyKnownType("Lcom/google/common/collect/ImmutableList;");
+ public final DexType javaUtilConcurrentCopyOnWriteArrayListType =
+ createStaticallyKnownType("Ljava/util/concurrent/CopyOnWriteArrayList;");
public final DexType javaUtilLocaleType = createStaticallyKnownType(localeDescriptor);
public final DexType javaUtilLoggingLevelType =
createStaticallyKnownType("Ljava/util/logging/Level;");
@@ -741,6 +751,8 @@
new JavaUtilComparatorMembers();
public final JavaUtilConcurrentTimeUnitMembers javaUtilConcurrentTimeUnitMembers =
new JavaUtilConcurrentTimeUnitMembers();
+
+ public final JavaUtilListMembers javaUtilListMembers = new JavaUtilListMembers();
public final JavaUtilLocaleMembers javaUtilLocaleMembers = new JavaUtilLocaleMembers();
public final JavaUtilLoggingLevelMembers javaUtilLoggingLevelMembers =
new JavaUtilLoggingLevelMembers();
@@ -862,7 +874,6 @@
createStaticallyKnownType("Ljava/lang/runtime/ObjectMethods;");
public final DexType typeDescriptorType =
createStaticallyKnownType("Ljava/lang/invoke/TypeDescriptor;");
- public final DexType iteratorType = createStaticallyKnownType("Ljava/util/Iterator;");
public final DexType listIteratorType = createStaticallyKnownType("Ljava/util/ListIterator;");
public final DexType enumerationType = createStaticallyKnownType("Ljava/util/Enumeration;");
public final DexType serializableType = createStaticallyKnownType("Ljava/io/Serializable;");
@@ -1511,6 +1522,15 @@
}
}
+ public class JavaUtilListMembers {
+ public final DexMethod size =
+ createMethod(javaUtilListType, createProto(intType), createString("size"));
+ public final DexMethod get =
+ createMethod(javaUtilListType, createProto(objectType, intType), getString);
+ public final DexMethod iterator =
+ createMethod(javaUtilListType, createProto(javaUtilIteratorType), iteratorName);
+ }
+
public class JavaUtilLocaleMembers extends LibraryMembers {
public final DexField ENGLISH = createField(javaUtilLocaleType, javaUtilLocaleType, "ENGLISH");
@@ -2690,7 +2710,8 @@
createProto(serviceLoaderType, classType),
createString("loadInstalled"));
iterator =
- createMethod(serviceLoaderType, createProto(iteratorType), createString("iterator"));
+ createMethod(
+ serviceLoaderType, createProto(javaUtilIteratorType), createString("iterator"));
}
@SuppressWarnings("ReferenceEquality")
@@ -2701,8 +2722,9 @@
public class IteratorMethods {
public final DexMethod hasNext =
- createMethod(iteratorType, createProto(booleanType), "hasNext");
- public final DexMethod next = createMethod(iteratorType, createProto(objectType), "next");
+ createMethod(javaUtilIteratorType, createProto(booleanType), hasNextName);
+ public final DexMethod next =
+ createMethod(javaUtilIteratorType, createProto(objectType), nextName);
}
private static <T extends DexItem> T canonicalize(Map<T, T> map, T item) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
index 5e5c563..9fe31b3 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlock.java
@@ -1798,8 +1798,9 @@
* <p>The catch successors are either on the original block or the new block depending on the
* value of <code>keepCatchHandlers</code>.
*
- * <p>The current block still has all the instructions, and the new block is empty
- * instruction-wise.
+ * <p>A Goto will be added to link the blocks (either to the end of this block when <code>
+ * firstInstructionOfNewBlock</code> is not null, or as the only instruction in the new block
+ * otherwise.
*
* @param blockNumber block number for new block
* @param keepCatchHandlers keep catch successors on the original block
@@ -1829,8 +1830,17 @@
// Link the two blocks
link(newBlock);
+ Goto newGoto = new Goto();
if (firstInstructionOfNewBlock != null) {
newBlock.instructions.severFrom(firstInstructionOfNewBlock);
+ newGoto.setPosition(
+ firstInstructionOfNewBlock.getPrev() != null
+ ? firstInstructionOfNewBlock.getPrev().getPosition()
+ : firstInstructionOfNewBlock.getPosition());
+ instructions.addLast(newGoto);
+ } else {
+ newGoto.setPosition(Position.none());
+ newBlock.instructions.addLast(newGoto);
}
// Mark the new block filled and sealed.
@@ -1841,6 +1851,34 @@
}
/**
+ * Split the block into two. The existing block will have all the instructions before the
+ * |firstInstructionOfNewBlock, and the new block all the instructions after. A Goto will be added
+ * either to the new block (if firstInstructionOfNewBlock is null), or to this block.
+ *
+ * <p>If the current block has catch handlers these catch handlers will be attached to the block
+ * containing the throwing instruction after the split.
+ *
+ * @param code the IR code for the block this iterator originates from.
+ * @param keepCatchHandlers whether to keep catch handlers on the original block.
+ * @param firstInstructionOfNewBlock first instruction to put into the new block. Can be null.
+ * @return Returns the new block.
+ */
+ public BasicBlock split(
+ IRCode code, boolean keepCatchHandlers, Instruction firstInstructionOfNewBlock) {
+ List<BasicBlock> blocks = code.blocks;
+ assert blocks.contains(this);
+ assert firstInstructionOfNewBlock == null || firstInstructionOfNewBlock.block == this;
+
+ // Prepare the new block, placing the exception handlers on the block with the throwing
+ // instruction.
+ BasicBlock newBlock =
+ createSplitBlock(code.getNextBlockNumber(), keepCatchHandlers, firstInstructionOfNewBlock);
+
+ blocks.add(blocks.indexOf(this) + 1, newBlock);
+ return newBlock;
+ }
+
+ /**
* Moves catch successors from `fromBlock` into this block.
*/
public void moveCatchHandlers(BasicBlock fromBlock) {
diff --git a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
index af87309..68ef0c8 100644
--- a/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
+++ b/src/main/java/com/android/tools/r8/ir/code/BasicBlockInstructionListIterator.java
@@ -656,20 +656,8 @@
@Override
public BasicBlock split(
IRCode code, ListIterator<BasicBlock> blocksIterator, boolean keepCatchHandlers) {
- List<BasicBlock> blocks = code.blocks;
assert blocksIterator == null || IteratorUtils.peekPrevious(blocksIterator) == block;
- // Don't allow splitting after the last instruction.
- assert hasNext();
-
- // Get the position at which the block is being split.
- Position position = getPreviousPosition();
-
- // Add a goto instruction.
- Goto newGoto = new Goto();
- instructionList.addBefore(newGoto, next);
- newGoto.setPosition(position);
-
// Prepare the new block, placing the exception handlers on the block with the throwing
// instruction.
BasicBlock newBlock =
@@ -679,6 +667,7 @@
// Insert the new block in the block list right after the current block.
if (blocksIterator == null) {
+ List<BasicBlock> blocks = code.blocks;
blocks.add(blocks.indexOf(block) + 1, newBlock);
} else {
blocksIterator.add(newBlock);
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 cbf7075..8a4d964 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
@@ -384,9 +384,6 @@
List<BasicBlock> successors = block.getSuccessors();
if (successors.size() == 1 && ListUtils.first(successors).getPredecessors().size() > 1) {
BasicBlock splitBlock = block.createSplitBlock(getNextBlockNumber(), true, null);
- Goto newGoto = new Goto();
- newGoto.setPosition(Position.none());
- splitBlock.getInstructions().addLast(newGoto);
blockIterator.add(splitBlock);
}
}
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 f51475e..ba6564d 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
@@ -105,7 +105,7 @@
public final AppView<?> appView;
public final Outliner outliner;
- private final CodeRewriterPassCollection rewriterPassCollection;
+ protected final CodeRewriterPassCollection rewriterPassCollection;
private final ClassInitializerDefaultsOptimization classInitializerDefaultsOptimization;
protected final CfInstructionDesugaringCollection instructionDesugaring;
protected FieldAccessAnalysis fieldAccessAnalysis;
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/PrimaryR8IRConverter.java b/src/main/java/com/android/tools/r8/ir/conversion/PrimaryR8IRConverter.java
index 7e02b35..fad62b5 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/PrimaryR8IRConverter.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/PrimaryR8IRConverter.java
@@ -28,9 +28,15 @@
private final Timing timing;
- public PrimaryR8IRConverter(AppView<? extends AppInfoWithClassHierarchy> appView, Timing timing) {
+ public PrimaryR8IRConverter(
+ AppView<? extends AppInfoWithClassHierarchy> appView,
+ Timing timing,
+ boolean enableListIterationRewriter) {
super(appView);
this.timing = timing;
+ if (enableListIterationRewriter) {
+ rewriterPassCollection.enableListIterationRewriter(appView);
+ }
}
public void optimize(AppView<AppInfoWithLiveness> appView, ExecutorService executorService)
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/CodeRewriterPassCollection.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/CodeRewriterPassCollection.java
index bae921e2..a6bbd64 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/CodeRewriterPassCollection.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/CodeRewriterPassCollection.java
@@ -11,6 +11,7 @@
import com.android.tools.r8.ir.conversion.IRConverter;
import com.android.tools.r8.ir.conversion.MethodProcessor;
import com.android.tools.r8.ir.conversion.passes.result.CodeRewriterResult;
+import com.android.tools.r8.ir.optimize.ListIterationRewriter;
import com.android.tools.r8.ir.optimize.RedundantFieldLoadAndStoreElimination;
import com.android.tools.r8.ir.optimize.ServiceLoaderRewriter;
import com.android.tools.r8.ir.optimize.enums.EnumValueOptimizer;
@@ -78,4 +79,8 @@
}
return new Pair<>(changed, previousMethodPrinting);
}
+
+ public void enableListIterationRewriter(AppView<?> appView) {
+ passes.add(new ListIterationRewriter(appView));
+ }
}
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
index e24701c..a9ec6d2 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/BackportedMethodRewriter.java
@@ -526,7 +526,7 @@
// Iterator<T> Collections.emptyIterator();
name = factory.createString("emptyIterator");
- proto = factory.createProto(factory.iteratorType);
+ proto = factory.createProto(factory.javaUtilIteratorType);
method = factory.createMethod(type, proto, name);
addProvider(new MethodGenerator(method, BackportedMethods::CollectionsMethods_emptyIterator));
@@ -1174,7 +1174,7 @@
DexMethod method;
// List<E> List.of(<args>) for 0 to 10 arguments and List.of(E[])
- type = factory.listType;
+ type = factory.javaUtilListType;
name = factory.createString("of");
for (int i = 0; i <= 10; i++) {
final int formalCount = i;
@@ -1249,11 +1249,11 @@
DexMethod method;
// List
- type = factory.listType;
+ type = factory.javaUtilListType;
// List List.copyOf(Collection)
name = factory.createString("copyOf");
- proto = factory.createProto(factory.listType, factory.collectionType);
+ proto = factory.createProto(factory.javaUtilListType, factory.collectionType);
method = factory.createMethod(type, proto, name);
addProvider(
new MethodGenerator(
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/ServiceLoaderSourceCode.java b/src/main/java/com/android/tools/r8/ir/desugar/ServiceLoaderSourceCode.java
index 83730de..e37fd11 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/ServiceLoaderSourceCode.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/ServiceLoaderSourceCode.java
@@ -76,8 +76,8 @@
new CfInvoke(
INVOKEINTERFACE,
factory.createMethod(
- factory.listType,
- factory.createProto(factory.iteratorType),
+ factory.javaUtilListType,
+ factory.createProto(factory.javaUtilIteratorType),
factory.createString("iterator")),
true),
tryCatchEnd,
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/backports/CollectionMethodGenerators.java b/src/main/java/com/android/tools/r8/ir/desugar/backports/CollectionMethodGenerators.java
index 532fc1a..9e643a6 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/backports/CollectionMethodGenerators.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/backports/CollectionMethodGenerators.java
@@ -28,7 +28,7 @@
private CollectionMethodGenerators() {}
public static CfCode generateListOf(DexItemFactory factory, DexMethod method, int formalCount) {
- return generateFixedMethods(factory, method, formalCount, factory.listType);
+ return generateFixedMethods(factory, method, formalCount, factory.javaUtilListType);
}
public static CfCode generateSetOf(DexItemFactory factory, DexMethod method, int formalCount) {
diff --git a/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/humanspecification/HumanRewritingFlags.java b/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/humanspecification/HumanRewritingFlags.java
index daf641b..ad35ac4 100644
--- a/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/humanspecification/HumanRewritingFlags.java
+++ b/src/main/java/com/android/tools/r8/ir/desugar/desugaredlibrary/humanspecification/HumanRewritingFlags.java
@@ -183,7 +183,7 @@
// Equivalence for parsing specification with format version 100.
DexMethod dontRewrite =
factory.createMethod(
- factory.iteratorType, factory.createProto(factory.voidType), "remove");
+ factory.javaUtilIteratorType, factory.createProto(factory.voidType), "remove");
return !reference.isIdenticalTo(dontRewrite);
}
}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ListIterationRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/ListIterationRewriter.java
new file mode 100644
index 0000000..35e9f46
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ListIterationRewriter.java
@@ -0,0 +1,492 @@
+// Copyright (c) 2024, 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;
+
+import com.android.tools.r8.contexts.CompilationContext.MethodProcessingContext;
+import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
+import com.android.tools.r8.graph.AppView;
+import com.android.tools.r8.graph.DexClass;
+import com.android.tools.r8.graph.DexItemFactory.JavaUtilListMembers;
+import com.android.tools.r8.graph.DexMethod;
+import com.android.tools.r8.graph.DexProto;
+import com.android.tools.r8.graph.DexString;
+import com.android.tools.r8.graph.DexType;
+import com.android.tools.r8.graph.MethodResolutionResult;
+import com.android.tools.r8.graph.SubtypingInfo;
+import com.android.tools.r8.ir.analysis.type.DynamicType;
+import com.android.tools.r8.ir.analysis.type.TypeElement;
+import com.android.tools.r8.ir.code.Add;
+import com.android.tools.r8.ir.code.Assume;
+import com.android.tools.r8.ir.code.BasicBlock;
+import com.android.tools.r8.ir.code.ConstNumber;
+import com.android.tools.r8.ir.code.IRCode;
+import com.android.tools.r8.ir.code.If;
+import com.android.tools.r8.ir.code.IfType;
+import com.android.tools.r8.ir.code.Instruction;
+import com.android.tools.r8.ir.code.InvokeInterface;
+import com.android.tools.r8.ir.code.InvokeMethodWithReceiver;
+import com.android.tools.r8.ir.code.InvokeVirtual;
+import com.android.tools.r8.ir.code.NumericType;
+import com.android.tools.r8.ir.code.Phi;
+import com.android.tools.r8.ir.code.Value;
+import com.android.tools.r8.ir.conversion.MethodProcessor;
+import com.android.tools.r8.ir.conversion.passes.CodeRewriterPass;
+import com.android.tools.r8.ir.conversion.passes.result.CodeRewriterResult;
+import com.android.tools.r8.shaking.AppInfoWithLiveness;
+import com.android.tools.r8.utils.InternalOptions.TestingOptions;
+import com.google.common.collect.ImmutableList;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.List;
+
+/**
+ * Rewrites iterator-based for-each loops into indexed loops for random access lists.
+ *
+ * <pre>
+ * For lists that can be determined to be random access (e.g. ArrayList), rewrites:
+ * for (var x : list) { ... }
+ * to:
+ * int len = list.size();
+ * int i = 0;
+ * while (i < len){
+ * var x = list.get(i);
+ * i++;
+ * ...
+ * }
+ *
+ * IR version: From:
+ * 0000: invoke-virtual {v2}, Ljava/util/ArrayList;.iterator:()Ljava/util/Iterator;
+ * 0003: move-result-object v2
+ * 0004: invoke-interface {v2}, Ljava/util/Iterator;.hasNext:()Z
+ * 0007: move-result v0
+ * 0008: if-eqz v0, 0016 // +000e
+ * 000a: invoke-interface {v2}, Ljava/util/Iterator;.next:()Ljava/lang/Object;
+ * 000d: move-result-object v0
+ * 000e: ...
+ * 0015: goto 0004 // -0011
+ *
+ * To:
+ * 0000: invoke-virtual {v4}, Ljava/util/ArrayList;.size:()I
+ * 0003: move-result v0
+ * 0004: const/4 v1, #int 0 // #0
+ * 0005: if-ge v1, v0, 0015 // +0010
+ * 0007: invoke-virtual {v4, v1}, Ljava/util/ArrayList;.get:(I)Ljava/lang/Object;
+ * 000a: move-result-object v2
+ * 000b: add-int/lit8 v1, v1, #int 1
+ * 000d: ...
+ * 0014: goto 0005 // -000f
+ *
+ * The reason for the transformation is that the code runs ~3x faster and saves an allocation.
+ * This transformation requires 2 extra registers and saves 2 bytes.
+ */
+public class ListIterationRewriter extends CodeRewriterPass<AppInfoWithLiveness> {
+ private final DexString iteratorName;
+ private final DexProto iteratorProto;
+ private final DexType listType;
+ private final DexType copyOnWriteArrayListType;
+ private final DexType linkedListType;
+ private final DexString hasNextName;
+ private final DexProto hasNextProto;
+ private final DexString nextName;
+ private final DexMethod sizeMethod;
+ private final DexMethod getMethod;
+ private final DexType arrayListType;
+ private final DexType immutableListType;
+
+ public ListIterationRewriter(AppView<?> appView) {
+ super(appView);
+ // Do not match using Iterator DexMethods since InvokeVirtual may be used if the list or
+ // iterator is a concrete class.
+ this.iteratorName = dexItemFactory.iteratorName;
+ this.iteratorProto = dexItemFactory.javaUtilIteratorProto;
+ this.hasNextName = dexItemFactory.hasNextName;
+ this.hasNextProto = dexItemFactory.iteratorMethods.hasNext.getProto();
+ this.nextName = dexItemFactory.nextName;
+ this.listType = dexItemFactory.javaUtilListType;
+ this.copyOnWriteArrayListType = dexItemFactory.javaUtilConcurrentCopyOnWriteArrayListType;
+ this.linkedListType = dexItemFactory.javaUtilLinkedListType;
+ this.sizeMethod = dexItemFactory.javaUtilListMembers.size;
+ this.getMethod = dexItemFactory.javaUtilListMembers.get;
+ this.arrayListType = dexItemFactory.javaUtilArrayListType;
+ this.immutableListType = dexItemFactory.comGoogleCommonCollectImmutableListType;
+ }
+
+ /**
+ * Returns whether to enable the optimization.
+ *
+ * @param subtypingInfo May contain pruned items, but must not be missing any types.
+ */
+ public static boolean shouldEnable(
+ AppView<? extends AppInfoWithClassHierarchy> appView, SubtypingInfo subtypingInfo) {
+ TestingOptions opts = appView.options().testing;
+ if (!appView.hasLiveness() || !opts.listIterationRewritingEnabled) {
+ return false;
+ }
+ if (opts.listIterationRewritingRewriteCustomIterators) {
+ return true;
+ }
+
+ // Enable only if there are no ArrayList subclasses that override iterator() / get() / size().
+ DexType arrayListType = appView.dexItemFactory().javaUtilArrayListType;
+ JavaUtilListMembers listMembers = appView.dexItemFactory().javaUtilListMembers;
+
+ return subtypingInfo.subtypes(arrayListType).stream()
+ .noneMatch(
+ subType -> {
+ DexClass dexClass =
+ appView.hasDefinitionFor(subType)
+ ? appView.contextIndependentDefinitionFor(subType)
+ : null;
+ return dexClass != null
+ && dexClass.isProgramClass()
+ && dexClass
+ .getMethodCollection()
+ .hasVirtualMethods(
+ m ->
+ listMembers.iterator.match(m)
+ || listMembers.get.match(m)
+ || listMembers.size.match(m));
+ });
+ }
+
+ @Override
+ protected String getRewriterId() {
+ return "ListIterationRewriter";
+ }
+
+ @Override
+ protected boolean shouldRewriteCode(IRCode code, MethodProcessor methodProcessor) {
+ return code.metadata().mayHaveIf();
+ }
+
+ @Override
+ protected CodeRewriterResult rewriteCode(
+ IRCode code,
+ MethodProcessor methodProcessor,
+ MethodProcessingContext methodProcessingContext) {
+ List<AnalysisResult> results = new ArrayList<>();
+ for (Instruction instruction : code.instructions()) {
+ InvokeMethodWithReceiver iteratorInstr = instruction.asInvokeMethodWithReceiver();
+ if (iteratorInstr == null) {
+ continue;
+ }
+ DexMethod invokedMethod = iteratorInstr.getInvokedMethod();
+ if (!invokedMethod.match(iteratorProto, iteratorName)) {
+ continue;
+ }
+ Value listValue = iteratorInstr.getReceiver();
+ if (!isWellBehavedList(listValue)) {
+ continue;
+ }
+
+ // See if it can be optimized.
+ AnalysisResult result = analyzeIterator(iteratorInstr);
+ if (result != null) {
+ results.add(result);
+ }
+ }
+
+ if (!results.isEmpty()) {
+ for (AnalysisResult result : results) {
+ rewriteInstance(code, result);
+ }
+
+ code.removeRedundantBlocks();
+ return CodeRewriterResult.HAS_CHANGED;
+ }
+ return CodeRewriterResult.NO_CHANGE;
+ }
+
+ private boolean isWellBehavedList(Value listValue) {
+ if (!listValue.getType().isClassType()) {
+ return false;
+ }
+ DexType valueType = listValue.getType().asClassType().toDexType(dexItemFactory);
+ if (options.testing.listIterationRewritingRewriteInterfaces) {
+ // In Chrome in Nov 2024, enabling for all list types causes the number of iteration rewrites
+ // go to from 1010 to 1731.
+ // While this would be safe for lists like: List.of(), singletonList(), etc, it would require
+ // expensive intra-procedural analysis to track when it is safe.
+ return appView().appInfo().isSubtype(valueType, listType)
+ // LinkedList.get() is not O(1).
+ && valueType.isNotIdenticalTo(linkedListType)
+ // CopyOnWriteArrayList.iterator() provides a snapshot of the list.
+ && valueType.isNotIdenticalTo(copyOnWriteArrayListType);
+ }
+ // TODO(b/145280859): Add support for kotlin.collections.ArrayList.
+ return appView().appInfo().isSubtype(valueType, arrayListType)
+ || valueType.isIdenticalTo(immutableListType);
+ }
+
+ private static class InstructionAndOptionalAssume {
+ public final Instruction instruction;
+ public final Assume assume;
+
+ InstructionAndOptionalAssume(Instruction instruction, Assume assume) {
+ this.instruction = instruction;
+ this.assume = assume;
+ }
+ }
+
+ private static InstructionAndOptionalAssume findNextMeaningfulInstruction(
+ Instruction instruction) {
+ Assume assume = null;
+ instruction = instruction.getNext();
+ while (instruction != null) {
+ if (instruction.isGoto()) {
+ instruction = instruction.asGoto().getTarget().entry();
+ continue;
+ } else if (instruction.isAssume()) {
+ if (assume != null) {
+ return null;
+ }
+ assume = instruction.asAssume();
+ } else if (!instruction.isConstNumber()) {
+ // Constant hoisting can cause const instructions to appear between iterator() and
+ // hasNext().
+ return new InstructionAndOptionalAssume(instruction, assume);
+ }
+ instruction = instruction.getNext();
+ }
+ return null;
+ }
+
+ private AnalysisResult analyzeIterator(InvokeMethodWithReceiver iteratorInstr) {
+ Value iteratorValue = iteratorInstr.outValue();
+
+ if (iteratorValue == null || iteratorValue.hasPhiUsers() || iteratorValue.hasDebugUsers()) {
+ return null;
+ }
+
+ InstructionAndOptionalAssume instructionAndAssume =
+ findNextMeaningfulInstruction(iteratorInstr);
+ if (instructionAndAssume == null) {
+ return null;
+ }
+
+ InvokeMethodWithReceiver hasNextInstr =
+ instructionAndAssume.instruction.asInvokeMethodWithReceiver();
+ if (hasNextInstr == null
+ || hasNextInstr.getReceiver().getAliasedValue() != iteratorValue
+ || !isHasNextMethod(hasNextInstr.getInvokedMethod())) {
+ return null;
+ }
+
+ // Ensure there is a loop.
+ if (hasNextInstr.getBlock().hasUniquePredecessor()) {
+ return null;
+ }
+ // Ensure hasNext() is the loop condition.
+ if (hasNextInstr.getBlock().entry() != hasNextInstr) {
+ return null;
+ }
+
+ // If .iterator() is the first call on the list, it will be followed by an Assume, which we'll
+ // need to update when rewriting.
+ Assume listAssumeInstr = null;
+ if (instructionAndAssume.assume != null) {
+ if (instructionAndAssume.assume.getFirstOperand() == iteratorInstr.getFirstOperand()) {
+ listAssumeInstr = instructionAndAssume.assume;
+ }
+ }
+
+ Value hasNextValue = hasNextInstr.outValue();
+ if (hasNextValue.hasPhiUsers()
+ || !hasNextValue.hasSingleUniqueUser()
+ || hasNextValue.hasDebugUsers()) {
+ return null;
+ }
+
+ instructionAndAssume = findNextMeaningfulInstruction(hasNextInstr);
+ if (instructionAndAssume == null) {
+ return null;
+ }
+ If ifInstr = instructionAndAssume.instruction.asIf();
+ // Do not need to check ifInstr for unique predecessors since we already check that it's inValue
+ // is the outValue of hasNext().
+ if (ifInstr == null || hasNextValue.singleUniqueUser() != ifInstr || !ifInstr.isZeroTest()) {
+ return null;
+ }
+
+ // Since .hasNext() is the first call on the iterator, it will be followed by a not-null Assume.
+ Assume iteratorAssumeInstr = null;
+ if (instructionAndAssume.assume != null) {
+ if (instructionAndAssume.assume.getFirstOperand() == hasNextInstr.getFirstOperand()) {
+ iteratorAssumeInstr = instructionAndAssume.assume;
+ }
+ }
+
+ BasicBlock relevantBlock =
+ ifInstr.getType() == IfType.EQ ? ifInstr.fallthroughBlock() : ifInstr.getTrueTarget();
+ InvokeMethodWithReceiver nextInstr = relevantBlock.entry().asInvokeMethodWithReceiver();
+ if (nextInstr == null
+ || nextInstr.getReceiver().getAliasedValue() != iteratorValue
+ || !isNextMethod(nextInstr.getInvokedMethod())
+ || !relevantBlock.hasUniquePredecessor()) {
+ return null;
+ }
+
+ // Ensure there are only 2 users of the iterator: hasNext() and next().
+ int numNonAliasIteratorUsers = iteratorValue.numberOfUsers();
+ if (iteratorAssumeInstr != null) {
+ if (iteratorAssumeInstr.outValue().hasPhiUsers()) {
+ return null;
+ }
+ numNonAliasIteratorUsers += iteratorAssumeInstr.outValue().numberOfUsers() - 1;
+ }
+ if (numNonAliasIteratorUsers != 2) {
+ return null;
+ }
+ return new AnalysisResult(
+ iteratorInstr, hasNextInstr, ifInstr, nextInstr, listAssumeInstr, iteratorAssumeInstr);
+ }
+
+ private boolean isHasNextMethod(DexMethod method) {
+ return method.match(hasNextProto, hasNextName);
+ }
+
+ private boolean isNextMethod(DexMethod method) {
+ return method.getName().isIdenticalTo(nextName)
+ && method.getProto().getParameters().isEmpty()
+ && method.getReturnType().isClassType();
+ }
+
+ private void rewriteInstance(IRCode code, AnalysisResult analysisResult) {
+ InvokeMethodWithReceiver iteratorInstr = analysisResult.iteratorInstr;
+ InvokeMethodWithReceiver hasNextInstr = analysisResult.hasNextInstr;
+ If ifInstr = analysisResult.ifInstr;
+ InvokeMethodWithReceiver nextInstr = analysisResult.nextInstr;
+ Assume listAssumeInstr = analysisResult.listAssumeInstr;
+ Assume iteratorAssumeInstr = analysisResult.iteratorAssumeInstr;
+ Value listValue = iteratorInstr.getReceiver();
+
+ // Add the "int i = 0;".
+ // Add it before size() since it's a non-throwing instruction (no need to split blocks).
+ ConstNumber initIndexInstr = code.createIntConstant(0);
+ initIndexInstr.setPosition(iteratorInstr.getPosition());
+ iteratorInstr.getBlock().getInstructions().addBefore(initIndexInstr, iteratorInstr);
+
+ // Replace: "list.iterator()" with "list.size()".
+ DexType listType = listValue.getType().asClassType().toDexType(dexItemFactory);
+ DexClass listClass = appView().definitionFor(listType);
+ Value sizeValue = code.createValue(TypeElement.getInt());
+ List<Value> sizeArgs = Collections.singletonList(listValue);
+ // Use invoke-virtual when list is a non-abstract concrete class.
+ MethodResolutionResult resolvedSizeMethod =
+ listClass == null || listClass.isInterface()
+ ? null
+ : appView().appInfo().resolveMethodOnClass(listClass, sizeMethod);
+ InvokeMethodWithReceiver sizeInstr =
+ resolvedSizeMethod == null || resolvedSizeMethod.getResolvedHolder().isInterface()
+ ? new InvokeInterface(sizeMethod, sizeValue, sizeArgs)
+ : new InvokeVirtual(
+ resolvedSizeMethod.getResolvedMethod().getReference(), sizeValue, sizeArgs);
+ iteratorInstr.replace(sizeInstr);
+
+ // Update List's assume-not-null to update its origin.
+ if (listAssumeInstr != null) {
+ Assume newAssume =
+ Assume.create(
+ DynamicType.definitelyNotNull(),
+ listAssumeInstr.outValue(),
+ listValue,
+ sizeInstr,
+ appView,
+ code.context());
+ listAssumeInstr.replace(newAssume, code);
+ listValue = newAssume.outValue();
+ }
+
+ // Figure out which block comes before the loop target, for Phi purposes.
+ BasicBlock phiBlock = hasNextInstr.getBlock();
+ BasicBlock blockBeforePhi = sizeInstr.getBlock();
+ while (true) {
+ // Walk through assume block and possible empty block.
+ BasicBlock nextBlock = blockBeforePhi.getUniqueNormalSuccessor();
+ if (nextBlock == phiBlock) {
+ break;
+ }
+ blockBeforePhi = nextBlock;
+ }
+
+ // Replace if-eqz with if-ge.
+ Phi indexPhi = code.createPhi(phiBlock, TypeElement.getInt());
+ IfType newIfType = ifInstr.getType() == IfType.EQ ? IfType.GE : IfType.LT;
+ If newIf = new If(newIfType, ImmutableList.of(indexPhi, sizeValue));
+ ifInstr.replace(newIf, code);
+
+ // Replace "x = iterator.next()" with "x = list.get(i)".
+ Value elementValue = nextInstr.outValue();
+ ImmutableList<Value> getArgs = ImmutableList.of(listValue, indexPhi);
+ // Use invoke-virtual when list is a non-abstract concrete class.
+ MethodResolutionResult resolvedGetMethod =
+ listClass == null || listClass.isInterface()
+ ? null
+ : appView().appInfo().resolveMethodOnClass(listClass, getMethod);
+ InvokeMethodWithReceiver getInstr =
+ resolvedGetMethod == null || resolvedGetMethod.getResolvedHolder().isInterface()
+ ? new InvokeInterface(getMethod, elementValue, getArgs)
+ : new InvokeVirtual(
+ resolvedGetMethod.getResolvedMethod().getReference(), elementValue, getArgs);
+ nextInstr.replace(getInstr);
+
+ // Add "i = i + 1" right after "x = iterator.next()".
+ Instruction toInsertBefore = nextInstr.getNext();
+ if (toInsertBefore.isGoto()) {
+ // Split in the case of a subsequent loop or catch handlers.
+ toInsertBefore.getBlock().split(code, true, toInsertBefore);
+ }
+ ConstNumber one = code.createIntConstant(1);
+ one.setPosition(nextInstr.getPosition());
+ toInsertBefore.getBlock().getInstructions().addBefore(one, toInsertBefore);
+ Add incrementIndexInstr =
+ Add.createNonNormalized(
+ NumericType.INT, code.createValue(TypeElement.getInt()), indexPhi, one.outValue());
+ incrementIndexInstr.setPosition(nextInstr.getPosition());
+ toInsertBefore.getBlock().getInstructions().addBefore(incrementIndexInstr, toInsertBefore);
+
+ // Delete iterator assume now that .next() has been removed.
+ if (iteratorAssumeInstr != null) {
+ iteratorAssumeInstr.removeOrReplaceByDebugLocalRead(code);
+ }
+
+ // Delete iterator.hasNext() now that old If was removed.
+ hasNextInstr.removeOrReplaceByDebugLocalRead(code);
+
+ // Populate the index phi.
+ for (BasicBlock b : phiBlock.getPredecessors()) {
+ if (b == blockBeforePhi) {
+ indexPhi.appendOperand(initIndexInstr.outValue());
+ } else {
+ indexPhi.appendOperand(incrementIndexInstr.outValue());
+ }
+ }
+ }
+
+ private static class AnalysisResult {
+
+ public final InvokeMethodWithReceiver iteratorInstr;
+ public final InvokeMethodWithReceiver hasNextInstr;
+ public final If ifInstr;
+ public final InvokeMethodWithReceiver nextInstr;
+ private final Assume listAssumeInstr;
+ private final Assume iteratorAssumeInstr;
+
+ public AnalysisResult(
+ InvokeMethodWithReceiver iteratorInstr,
+ InvokeMethodWithReceiver hasNextInstr,
+ If ifInstr,
+ InvokeMethodWithReceiver nextInstr,
+ Assume listAssumeInstr,
+ Assume iteratorAssumeInstr) {
+ this.iteratorInstr = iteratorInstr;
+ this.hasNextInstr = hasNextInstr;
+ this.ifInstr = ifInstr;
+ this.nextInstr = nextInstr;
+ this.listAssumeInstr = listAssumeInstr;
+ this.iteratorAssumeInstr = iteratorAssumeInstr;
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/ir/optimize/ServiceLoaderRewriter.java b/src/main/java/com/android/tools/r8/ir/optimize/ServiceLoaderRewriter.java
index 2a21f45..badc7ea 100644
--- a/src/main/java/com/android/tools/r8/ir/optimize/ServiceLoaderRewriter.java
+++ b/src/main/java/com/android/tools/r8/ir/optimize/ServiceLoaderRewriter.java
@@ -643,7 +643,8 @@
List<DexClass> classes,
MethodProcessor methodProcessor,
MethodProcessingContext methodProcessingContext) {
- DexProto proto = appView.dexItemFactory().createProto(appView.dexItemFactory().iteratorType);
+ DexProto proto =
+ appView.dexItemFactory().createProto(appView.dexItemFactory().javaUtilIteratorType);
ProgramMethod method =
appView
.getSyntheticItems()
diff --git a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
index cbba232..f16a61c 100644
--- a/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
+++ b/src/main/java/com/android/tools/r8/shaking/AppInfoWithLiveness.java
@@ -532,6 +532,12 @@
return definition;
}
+ @Override
+ public final boolean hasDefinitionFor(DexType type) {
+ // Avoid assertion added in our definitionFor().
+ return super.definitionFor(type) != null;
+ }
+
private CfVersion largestInputCfVersion = null;
public boolean canUseConstClassInstructions(InternalOptions options) {
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 b0757f4..0952033 100644
--- a/src/main/java/com/android/tools/r8/utils/InternalOptions.java
+++ b/src/main/java/com/android/tools/r8/utils/InternalOptions.java
@@ -2606,6 +2606,15 @@
public boolean enableExperimentalMapFileVersion = false;
public boolean alwaysGenerateLambdaFactoryMethods = false;
+
+ // Work-in-progress optimization: b/145280859.
+ public boolean listIterationRewritingEnabled =
+ System.getProperty("com.android.tools.r8.enableListIterationRewriting") != null;
+ public boolean listIterationRewritingRewriteInterfaces =
+ "all".equals(System.getProperty("com.android.tools.r8.enableListIterationRewriting"));
+ // Used by unit tests.
+ public boolean listIterationRewritingRewriteCustomIterators =
+ listIterationRewritingRewriteInterfaces;
}
public MapVersion getMapFileVersion() {
diff --git a/src/test/java/com/android/tools/r8/optimize/listiteration/ListIterationRewriterTest.java b/src/test/java/com/android/tools/r8/optimize/listiteration/ListIterationRewriterTest.java
new file mode 100644
index 0000000..811ff2b
--- /dev/null
+++ b/src/test/java/com/android/tools/r8/optimize/listiteration/ListIterationRewriterTest.java
@@ -0,0 +1,667 @@
+// Copyright (c) 2024, 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.optimize.listiteration;
+
+import static org.junit.Assert.assertTrue;
+
+import com.android.tools.r8.NeverInline;
+import com.android.tools.r8.TestBase;
+import com.android.tools.r8.TestParameters;
+import com.android.tools.r8.TestParametersCollection;
+import com.android.tools.r8.utils.codeinspector.FoundClassSubject;
+import com.android.tools.r8.utils.codeinspector.InstructionSubject;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.concurrent.CopyOnWriteArrayList;
+import java.util.stream.Stream;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+import org.junit.runners.Parameterized.Parameter;
+import org.junit.runners.Parameterized.Parameters;
+
+@RunWith(Parameterized.class)
+public class ListIterationRewriterTest extends TestBase {
+ interface TestCase {
+ String[] expectedOutput();
+
+ void run();
+
+ default String getName() {
+ // Some runtimes prefix the outer class, and some do not.
+ return getClass().getSimpleName().replaceFirst(".*\\$", "");
+ }
+ }
+
+ public static class ArrayListMethodWithTryCatch implements TestCase {
+ @NeverInline
+ private static void helper(ArrayList<Integer> list) {
+ try {
+ for (Integer x : list) {
+ System.out.println(x);
+ }
+ } catch (Throwable t) {
+ System.out.println("error");
+ }
+ }
+
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ helper(list);
+ }
+ }
+
+ public static class ArrayListMethodWithSubsequentLoop implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "1", "1", "1", "2", "3"};
+ }
+
+ // Use ArrayList<Object> to avoid check-cast instructions.
+ @NeverInline
+ private static void helper(ArrayList<Object> list) {
+ long now = System.currentTimeMillis();
+ int i = 0;
+ for (Object x : list) {
+ for (; i < Math.min(3, now); ++i) {
+ System.out.println(x);
+ }
+ System.out.println(x);
+ }
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Object> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ helper(list);
+ }
+ }
+
+ public static class ArrayListMethodWithSubsequentLoopAndTryCatch implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "1", "1", "1", "2", "3"};
+ }
+
+ // Use ArrayList<Object> to avoid check-cast instructions.
+ @NeverInline
+ private static void helper(ArrayList<Object> list) {
+ long now = System.currentTimeMillis();
+ int i = 0;
+ try {
+ for (Object x : list) {
+ for (; i < Math.min(3, now); ++i) {
+ System.out.println(x);
+ }
+ System.out.println(x);
+ }
+ } catch (Throwable t) {
+ System.out.println("error");
+ }
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Object> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ helper(list);
+ }
+ }
+
+ public static class ArrayListMethod implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @NeverInline
+ private static void helper(ArrayList<Integer> list) {
+ for (Integer x : list) {
+ System.out.println(x);
+ }
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ helper(list);
+ }
+ }
+
+ public static class ArrayListLocal implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ for (Integer x : list) {
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class ArrayListLocalNoOutValue implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "1", "1"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ for (Integer x : list) {
+ System.out.println("1");
+ }
+ }
+ }
+
+ public static class NestedLocalArrayList implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"7", "8", "9", "1", "2", "3"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ for (int x : list) {
+ for (int y : list) {
+ x += y;
+ }
+ System.out.println(x);
+ }
+ // Also test sibling loop.
+ for (int x : list) {
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class LocalArrayListWithExtraConstInstr implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3", "true"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ Iterator<Integer> it = list.iterator();
+ boolean found = false;
+ while (it.hasNext()) {
+ Integer x = it.next();
+ if (x == 3) {
+ found = true;
+ }
+ System.out.println(x);
+ }
+ System.out.println(found);
+ }
+ }
+
+ public static class LocalArrayListWithInvertedIfCondition implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ Iterator<Integer> it = list.iterator();
+ while (true) {
+ // This will be an "if NEZ" rather than the normal "if EQZ".
+ if (!it.hasNext()) {
+ return;
+ }
+ Integer x = it.next();
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class LoopWithContinue implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @NeverInline
+ private static List<Integer> getList() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ return list;
+ }
+
+ @Override
+ public void run() {
+ Collection<Integer> list = getList();
+ for (Integer x : list) {
+ if (x == null) {
+ continue;
+ }
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class DoNotOptimizeCopyOnWrite implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @Override
+ public void run() {
+ CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ for (int x : list) {
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class DoNotOptimizeLinkedList implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @Override
+ public void run() {
+ LinkedList<Integer> list = new LinkedList<>();
+ Collections.addAll(list, 1, 2, 3);
+ for (int x : list) {
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class DoNotOptimizeNonLoop implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ Iterator<Integer> it = list.iterator();
+ if (it.hasNext()) {
+ Integer x = it.next();
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class DoNotOptimizeCustomExtraUsers implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ Iterator<Integer> it = list.iterator();
+ while (it.hasNext()) {
+ Integer x = it.next();
+ System.out.println(x);
+ }
+ if (it.hasNext()) {
+ throw new RuntimeException();
+ }
+ }
+ }
+
+ public static class DoNotOptimizeCustomLoopWithExtraInstruction implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"01", "02", "03"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ Iterator<Integer> it = list.iterator();
+ while (it.hasNext()) {
+ System.out.print("0");
+ Integer x = it.next();
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class DoNotOptimizePhiIterator implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ Iterator<Integer> it = System.currentTimeMillis() <= 0 ? null : list.iterator();
+ while (it.hasNext()) {
+ Integer x = it.next();
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class DoNotOptimizeExtraConditionLoop implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ Iterator<Integer> it = list.iterator();
+ while (it.hasNext() && System.currentTimeMillis() > 0) {
+ Integer x = it.next();
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class DoNotOptimizeOnlyNoOutValue implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2"};
+ }
+
+ @NeverInline
+ private static void noIteratorOutValue(ArrayList<Integer> list) {
+ list.iterator();
+ System.out.println("1");
+ }
+
+ @NeverInline
+ private static void noHasNextOutValue(ArrayList<Integer> list) {
+ Iterator<Integer> it = list.iterator();
+ it.hasNext();
+ System.out.println("2");
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ noIteratorOutValue(list);
+ noHasNextOutValue(list);
+ }
+ }
+
+ public static class DoNotOptimizeWrongReceiver implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3", "4"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ Iterator<Integer> it0 = list.iterator();
+ Iterator<Integer> it1 = list.iterator();
+ while (it0.hasNext()) {
+ Integer x = it0.next();
+ System.out.println(x);
+ }
+ if (it1.hasNext()) {
+ System.out.println(4);
+ }
+ }
+ }
+
+ public static class DoNotOptimizeExtraNextPredecessors implements TestCase {
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new ArrayList<>();
+ Collections.addAll(list, 1, 2, 3);
+ Iterator<Integer> it = list.iterator();
+ while (it.hasNext()) {
+ Integer x;
+ for (; ; ) {
+ x = it.next();
+ if (x != null) {
+ break;
+ }
+ }
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class CustomArrayListNoIterator implements TestCase {
+ static class CustomArrayList extends ArrayList<Integer> {}
+
+ @Override
+ public String[] expectedOutput() {
+ return new String[] {"1", "2", "3"};
+ }
+
+ @Override
+ public void run() {
+ ArrayList<Integer> list = new CustomArrayList();
+ Collections.addAll(list, 1, 2, 3);
+ for (Object x : list) {
+ System.out.println(x);
+ }
+ }
+ }
+
+ public static class CustomArrayListWithIterator {
+ public static String[] EXPECTED_OUTPUT = new String[] {"1", "2", "3"};
+
+ static class CustomArrayListBase extends ArrayList<Integer> {}
+
+ static class CustomArrayList extends CustomArrayListBase {
+ @Override
+ public Iterator<Integer> iterator() {
+ return Arrays.asList(1, 2, 3).iterator();
+ }
+ }
+
+ public static void main(String[] args) {
+ ArrayList<Integer> list = new CustomArrayList();
+ for (Object x : list) {
+ System.out.println(x);
+ }
+ }
+ }
+
+ @Parameters(name = "{0}")
+ public static TestParametersCollection data() {
+ // Optimization does affected by API / runtime.
+ return getTestParameters().withDefaultRuntimes().withMinimumApiLevel().build();
+ }
+
+ @Parameter public TestParameters parameters;
+
+ public static class RewritesMain {
+ // Comment out cases from this list to debug individual tests.
+ static final TestCase[] CASES =
+ new TestCase[] {
+ new ArrayListLocal(),
+ new ArrayListLocalNoOutValue(),
+ new NestedLocalArrayList(),
+ new ArrayListMethod(),
+ new ArrayListMethodWithTryCatch(),
+ new ArrayListMethodWithSubsequentLoop(),
+ new ArrayListMethodWithSubsequentLoopAndTryCatch(),
+ new LocalArrayListWithExtraConstInstr(),
+ new LocalArrayListWithInvertedIfCondition(),
+ new LoopWithContinue(),
+ new CustomArrayListNoIterator(),
+ };
+
+ @NeverInline
+ public static void main(String[] args) {
+ for (TestCase test : CASES) {
+ System.out.println(test.getName());
+ test.run();
+ }
+ }
+ }
+
+ private static String[] getExpectedTestOutput(TestCase[] testCases) {
+ return Arrays.stream(testCases)
+ .flatMap(x -> Stream.concat(Stream.of(x.getName()), Arrays.stream(x.expectedOutput())))
+ .toArray(String[]::new);
+ }
+
+ @Test
+ public void testRewrites() throws Exception {
+ // Run all test classes in one compilation for faster tests compared to compiling each one
+ // separately.
+ Class[] classes =
+ Arrays.stream(RewritesMain.CASES).map(x -> x.getClass()).toArray(Class[]::new);
+ String[] expectedOutput = getExpectedTestOutput(RewritesMain.CASES);
+
+ testForR8(parameters.getBackend())
+ .setMinApi(parameters)
+ .addOptionsModification(o -> o.testing.listIterationRewritingEnabled = true)
+ .addProgramClassesAndInnerClasses(classes)
+ .addProgramClasses(RewritesMain.class, TestCase.class)
+ .addKeepMainRule(RewritesMain.class)
+ .addDontObfuscate()
+ .noHorizontalClassMerging()
+ .enableInliningAnnotations()
+ .compile()
+ .run(parameters.getRuntime(), RewritesMain.class)
+ .assertSuccessWithOutputLines(expectedOutput)
+ .inspect(
+ inspector -> inspector.forAllClasses(ListIterationRewriterTest::checkNoIteratorInvoke));
+ }
+
+ public static class NoRewritesMain {
+ // Comment out cases from this list to debug individual tests.
+ static final TestCase[] CASES =
+ new TestCase[] {
+ new DoNotOptimizeCopyOnWrite(),
+ new DoNotOptimizeLinkedList(),
+ new DoNotOptimizeNonLoop(),
+ new DoNotOptimizeCustomExtraUsers(),
+ new DoNotOptimizeCustomLoopWithExtraInstruction(),
+ new DoNotOptimizePhiIterator(),
+ new DoNotOptimizeExtraConditionLoop(),
+ new DoNotOptimizeOnlyNoOutValue(),
+ new DoNotOptimizeWrongReceiver(),
+ new DoNotOptimizeExtraNextPredecessors(),
+ };
+
+ @NeverInline
+ public static void main(String[] args) {
+ for (TestCase test : CASES) {
+ System.out.println(test.getName());
+ test.run();
+ }
+ }
+ }
+
+ private static boolean isIteratorInvoke(InstructionSubject ins) {
+ return ins.isInvoke() && ins.getMethod().name.toString().equals("iterator");
+ }
+
+ private static void checkIteratorInvokeExists(FoundClassSubject classSubject) {
+ if (classSubject.isImplementing(TestCase.class)) {
+ assertTrue(
+ "No iterator() found in " + classSubject,
+ classSubject.allMethods().stream()
+ .flatMap(m -> m.streamInstructions())
+ .anyMatch(ListIterationRewriterTest::isIteratorInvoke));
+ }
+ }
+
+ private static void checkNoIteratorInvoke(FoundClassSubject classSubject) {
+ if (classSubject.isImplementing(TestCase.class)) {
+ assertTrue(
+ "Found iterator() in " + classSubject,
+ classSubject.allMethods().stream()
+ .flatMap(m -> m.streamInstructions())
+ .noneMatch(ListIterationRewriterTest::isIteratorInvoke));
+ }
+ }
+
+ @Test
+ public void testNoRewrites() throws Exception {
+ // Run all test classes in one compilation for faster tests compared to compiling each one
+ // separately.
+ Class[] classes =
+ Arrays.stream(NoRewritesMain.CASES).map(x -> x.getClass()).toArray(Class[]::new);
+ String[] expectedOutput = getExpectedTestOutput(NoRewritesMain.CASES);
+
+ testForR8(parameters.getBackend())
+ .setMinApi(parameters)
+ .addOptionsModification(
+ o -> {
+ o.testing.listIterationRewritingEnabled = true;
+ // Ensure tests do not pass due to the optimization being disabled.
+ o.testing.listIterationRewritingRewriteCustomIterators = true;
+ })
+ .addProgramClassesAndInnerClasses(classes)
+ .addProgramClasses(NoRewritesMain.class, TestCase.class)
+ .addKeepMainRule(NoRewritesMain.class)
+ .addDontObfuscate()
+ .enableInliningAnnotations()
+ .noHorizontalClassMerging()
+ .compile()
+ .run(parameters.getRuntime(), NoRewritesMain.class)
+ .assertSuccessWithOutputLines(expectedOutput)
+ .inspect(
+ inspector ->
+ inspector.forAllClasses(ListIterationRewriterTest::checkIteratorInvokeExists));
+ }
+
+ @Test
+ public void testCustomIteratorThatDisablesOptimization() throws Exception {
+ testForR8(parameters.getBackend())
+ .setMinApi(parameters)
+ .addOptionsModification(o -> o.testing.listIterationRewritingEnabled = true)
+ .addProgramClassesAndInnerClasses(CustomArrayListWithIterator.class)
+ .addKeepMainRule(CustomArrayListWithIterator.class)
+ .compile()
+ .run(parameters.getRuntime(), CustomArrayListWithIterator.class)
+ .assertSuccessWithOutputLines(CustomArrayListWithIterator.EXPECTED_OUTPUT)
+ .inspect(
+ inspector ->
+ inspector.forAllClasses(ListIterationRewriterTest::checkIteratorInvokeExists));
+ }
+}
