Reenable loop unrolling with phis
Change-Id: I8e22c86e63596730ad249cd787d6ab03245b74cc
diff --git a/src/main/java/com/android/tools/r8/ir/conversion/passes/NaturalIntLoopRemover.java b/src/main/java/com/android/tools/r8/ir/conversion/passes/NaturalIntLoopRemover.java
index 23cf067..1e327f8 100644
--- a/src/main/java/com/android/tools/r8/ir/conversion/passes/NaturalIntLoopRemover.java
+++ b/src/main/java/com/android/tools/r8/ir/conversion/passes/NaturalIntLoopRemover.java
@@ -19,6 +19,7 @@
import com.android.tools.r8.ir.conversion.passes.result.CodeRewriterResult;
import com.android.tools.r8.ir.optimize.AffectedValues;
import com.android.tools.r8.utils.WorkList;
+import com.google.common.collect.Sets;
import java.util.Set;
/**
@@ -109,7 +110,7 @@
if (!analyzeLoopExit(loopBody, comparison, builder)) {
return false;
}
- if (!analyzePhiUses(loopBody, comparison)) {
+ if (!analyzePhiUses(loopBody, comparison, builder)) {
return false;
}
@@ -123,10 +124,25 @@
}
/**
- * The loop unroller removes phis corresponding to the loop backjump if they are not used outside
- * the loop.
+ * The loop unroller removes phis corresponding to the loop backjump. There are three scenarios:
+ * (1) The loop has a single exit point analyzed, phis used outside the loop are replaced by the
+ * value at the end of the loop body.
+ * (2) The phis are unused outside the loop, and they are simply removed.
+ * (3) The loop has multiple exits and the phis are used outside the loop, this would require
+ * dealing with complex merge point and postponing phis after the loop, we bail out.
*/
- private boolean analyzePhiUses(Set<BasicBlock> loopBody, If comparison) {
+ private boolean analyzePhiUses(
+ Set<BasicBlock> loopBody, If comparison, NaturalIntLoopWithKnowIterations.Builder builder) {
+ // Check for single exit scenario.
+ Set<BasicBlock> successors = Sets.newIdentityHashSet();
+ for (BasicBlock basicBlock : loopBody) {
+ successors.addAll(basicBlock.getSuccessors());
+ }
+ successors.removeAll(loopBody);
+ if (successors.size() == 1) {
+ assert successors.iterator().next() == builder.getLoopExit();
+ return true;
+ }
// Check phis are unused outside the loop.
for (Phi phi : comparison.getBlock().getPhis()) {
for (Instruction use : phi.uniqueUsers()) {
@@ -411,6 +427,10 @@
for (Phi phi : comparisonBlock.getPhis()) {
Value loopEntryValue = phi.getOperand(1 - backIndex);
Value loopExitValue = phi.getOperand(backIndex);
+ if (loopExitValue.isPhi() && comparisonBlock.getPhis().contains(loopExitValue.asPhi())) {
+ loopExitValue = loopExitValue.asPhi().getOperand(1 - backIndex);
+ }
+ assert !loopExitValue.isPhi() || !comparisonBlock.getPhis().contains(loopExitValue.asPhi());
for (Instruction uniqueUser : phi.uniqueUsers()) {
if (loopBody.contains(uniqueUser.getBlock())) {
uniqueUser.replaceValue(phi, loopEntryValue, affectedValues);
diff --git a/src/test/java/com/android/tools/r8/ir/optimize/loops/B341618078Test.java b/src/test/java/com/android/tools/r8/regress/B341618078Test.java
similarity index 76%
rename from src/test/java/com/android/tools/r8/ir/optimize/loops/B341618078Test.java
rename to src/test/java/com/android/tools/r8/regress/B341618078Test.java
index 85d5d98..a0a14ed 100644
--- a/src/test/java/com/android/tools/r8/ir/optimize/loops/B341618078Test.java
+++ b/src/test/java/com/android/tools/r8/regress/B341618078Test.java
@@ -1,14 +1,16 @@
// 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.loops;
+package com.android.tools.r8.regress;
+import static org.junit.Assert.assertTrue;
import static org.junit.Assume.assumeTrue;
import com.android.tools.r8.TestBase;
import com.android.tools.r8.TestParameters;
import com.android.tools.r8.TestParametersCollection;
import com.android.tools.r8.utils.StringUtils;
+import com.android.tools.r8.utils.codeinspector.CodeInspector;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
@@ -26,7 +28,7 @@
return getTestParameters().withAllRuntimesAndApiLevels().build();
}
- private static final String EXPECTED_OUTPUT = StringUtils.lines("0", "0");
+ private static final String EXPECTED_OUTPUT = StringUtils.lines("0", "0", "1");
@Test
public void testJvm() throws Exception {
@@ -53,10 +55,18 @@
.addInnerClasses(getClass())
.addKeepMainRule(TestClass.class)
.setMinApi(parameters)
+ .compile()
+ .inspect(this::assertLoopUnrolled)
.run(parameters.getRuntime(), TestClass.class)
.assertSuccessWithOutput(EXPECTED_OUTPUT);
}
+ private void assertLoopUnrolled(CodeInspector inspector) {
+ // All control flow has been removed.
+ inspector.clazz(TestClass.class).forAllMethods(m ->
+ assertTrue(m.streamInstructions().noneMatch(i -> i.isGoto() || i.isIf())));
+ }
+
static class TestClass {
long a;
@@ -87,10 +97,24 @@
System.out.println(g);
}
+ static void cChainedSimplified() {
+ int a = 1;
+ int b = 2;
+ int c = 3;
+ int d = 4;
+ for (int h = 0; h < 1; h++) {
+ b = a;
+ c = b;
+ d = c;
+ }
+ System.out.println(d);
+ }
+
public static void main(String[] k) {
TestClass m = new TestClass();
m.i(k);
- TestClass.cSimplified();
+ cSimplified();
+ cChainedSimplified();
}
}
}
