[PM] Simplify the new PM interface to the loop unroller and expose two factory functions for the two modes the loop unroller is actually used in in-tree: simplified full-unrolling and the entire thing including partial unrolling.

[chandlerc]

Summary

I've also wired these up to nice names so you can express both of these
being in a pipeline easily. This is a precursor to actually enabling
these parts of the O2 pipeline.

I'm happy to consider alternative names here. I'm not a huge fan of
"simple" but it is what we were using.

Depends on D28848.

[davide]

I have a fundamental question about the constructors. Also, I would prefer the spelling FullUnroll instead of SimpleUnroll.

include/llvm/Transforms/Scalar/LoopUnrollPass.h

25–31 ↗

(On Diff #84956)

Is it intended that you're passing false to both create() and createSimple() ?
Shouldn't create() allow the entire thing, including partial unrolling? Here you don't enable it at all.

[chandlerc]

include/llvm/Transforms/Scalar/LoopUnrollPass.h

25–31 ↗

(On Diff #84956)

Ahem. Indeed, that was not intended. More tests are also in order here!

(This isn't heavily used yet, so it isn't that surprising that i've missed a test for this.)

[chandlerc]

Update with more correctness and more testing!

[chandlerc]

In D28897#654378, @davide wrote:

I have a fundamental question about the constructors.

See updated patch! =D

Also, I would prefer the spelling FullUnroll instead of SimpleUnroll.

Not sure what you actually want yet...

Currently we have LoopUnrollPass::create() and LoopUnrollPass::createSimple(), and at the pipeline unroll and unroll-simple. Are you suggesting just using "full" instead of "simple" with the same structure? unroll-full makes sense, but LoopUnrollPass::createFull() seems weird. It is a less powerful pass...

include/llvm/Transforms/Scalar/LoopUnrollPass.h

25–31 ↗

(On Diff #84956)

It was worse than you realize.

The flag was actually backwards so that, combined with this being false, made both of these the more generic unroller.

I've added a test that the simple unroller *just* does full unrolling and that this one *does* do partial unrolling. Sorry for getting all my flags wrong.

[davide]

In D28897#654715, @chandlerc wrote:

In D28897#654378, @davide wrote:

I have a fundamental question about the constructors.

See updated patch! =D

Also, I would prefer the spelling FullUnroll instead of SimpleUnroll.

Not sure what you actually want yet...

Currently we have LoopUnrollPass::create() and LoopUnrollPass::createSimple(), and at the pipeline unroll and unroll-simple. Are you suggesting just using "full" instead of "simple" with the same structure? unroll-full makes sense, but LoopUnrollPass::createFull() seems weird. It is a less powerful pass...

I was suggesting unroll-full for the name of the pass (and what you pass to opt, or whatever. I agree with you createFull and createSimple can stay as they are (sorry if it wasn't entirely clear to begin with)

[davide]

The new patch looks fine (now that you fixed the flag), minor comments inline.

[mzolotukhin]

lib/Passes/PassRegistry.def

228 ↗

(On Diff #85561)

I agree with @davide regarding the name of the pass. IMO unroll-full better reflects what the pass is doing.

lib/Transforms/Scalar/LoopUnrollPass.cpp

1124 ↗

(On Diff #85561)

Do we want to use LoopUnrollPass::createSimple here? This part (and the function above) seems to be doing almost the same as we do with the new functions.

1158 ↗

(On Diff #85561)

How do we use ProvidedThreshold and ProvidedThreshold now?

[chandlerc]

Update with new function name based on review comments.

[davide]

LGTM if @mzolotukhin is happy.

[chandlerc]

lib/Transforms/Scalar/LoopUnrollPass.cpp

1124 ↗

(On Diff #85561)

Yeah, but they need the legacy PM bits so I just didn't want to touch them right away. We could refactor this some in the future if you want.

1158 ↗

(On Diff #85561)

We don't at all. It's just vestigal for the legacy PM. We now have target hooks to control threshold and flags to do debugging. That seemed sufficient to me.

[mzolotukhin]

LGTM too!

Michael

llvm/trunk/include/llvm/Transforms/Scalar/LoopUnrollPass.h

 #define LLVM_TRANSFORMS_SCALAR_LOOPUNROLLPASS_H
 
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 
 namespace llvm {
 
-struct LoopUnrollPass : public PassInfoMixin<LoopUnrollPass> {
-  Optional<unsigned> ProvidedCount;
-  Optional<unsigned> ProvidedThreshold;
-  Optional<bool> ProvidedAllowPartial;
-  Optional<bool> ProvidedRuntime;
-  Optional<bool> ProvidedUpperBound;
+class LoopUnrollPass : public PassInfoMixin<LoopUnrollPass> {
+  const bool AllowPartialUnrolling;
+
+  explicit LoopUnrollPass(bool AllowPartialUnrolling)
+      : AllowPartialUnrolling(AllowPartialUnrolling) {}
+
+public:
+  /// Create an instance of the loop unroll pass that will support both full
+  /// and partial unrolling.
+  ///
+  /// This uses the target information (or flags) to control the thresholds for
+  /// different unrolling stategies but supports all of them.
+  static LoopUnrollPass create() {
+    return LoopUnrollPass(/*AllowPartialUnrolling*/ true);
+  }
+
+  /// Create an instance of the loop unroll pass that only does full loop
+  /// unrolling.
+  ///
+  /// This will disable any runtime or partial unrolling.
+  static LoopUnrollPass createFull() {
+    return LoopUnrollPass(/*AllowPartialUnrolling*/ false);
+  }
 
   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
 };
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_LOOPUNROLLPASS_H

llvm/trunk/lib/Passes/PassRegistry.def

 LOOP_PASS("loop-instsimplify", LoopInstSimplifyPass())
 LOOP_PASS("rotate", LoopRotatePass())
 LOOP_PASS("no-op-loop", NoOpLoopPass())
 LOOP_PASS("print", PrintLoopPass(dbgs()))
 LOOP_PASS("loop-deletion", LoopDeletionPass())
 LOOP_PASS("simplify-cfg", LoopSimplifyCFGPass())
 LOOP_PASS("strength-reduce", LoopStrengthReducePass())
 LOOP_PASS("indvars", IndVarSimplifyPass())
-LOOP_PASS("unroll", LoopUnrollPass())
+LOOP_PASS("unroll", LoopUnrollPass::create())
+LOOP_PASS("unroll-full", LoopUnrollPass::createFull())
 LOOP_PASS("print-access-info", LoopAccessInfoPrinterPass(dbgs()))
 LOOP_PASS("print<ivusers>", IVUsersPrinterPass(dbgs()))
 LOOP_PASS("loop-predication", LoopPredicationPass())
 #undef LOOP_PASS

llvm/trunk/lib/Transforms/Scalar/LoopUnrollPass.cpp

PreservedAnalyses LoopUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
   // created by unrolling.
   Loop *ParentL = L.getParentLoop();
   SmallPtrSet<Loop *, 4> OldLoops;
   if (ParentL)
     OldLoops.insert(ParentL->begin(), ParentL->end());
   else
     OldLoops.insert(AR.LI.begin(), AR.LI.end());
 
+  // The API here is quite complex to call, but there are only two interesting
+  // states we support: partial and full (or "simple") unrolling. However, to
+  // enable these things we actually pass "None" in for the optional to avoid
+  // providing an explicit choice.
+  Optional<bool> AllowPartialParam, RuntimeParam, UpperBoundParam;
+  if (!AllowPartialUnrolling)
+    AllowPartialParam = RuntimeParam = UpperBoundParam = false;
   bool Changed = tryToUnrollLoop(&L, AR.DT, &AR.LI, &AR.SE, AR.TTI, AR.AC, *ORE,
-                                 /*PreserveLCSSA*/ true, ProvidedCount,
-                                 ProvidedThreshold, ProvidedAllowPartial,
-                                 ProvidedRuntime, ProvidedUpperBound);
+                                 /*PreserveLCSSA*/ true, /*Count*/ None,
+                                 /*Threshold*/ None, AllowPartialParam,
+                                 RuntimeParam, UpperBoundParam);
   if (!Changed)
     return PreservedAnalyses::all();
 
   // The parent must not be damaged by unrolling!
 #ifndef NDEBUG
   if (ParentL)
     ParentL->verifyLoop();
 #endif

llvm/trunk/test/Transforms/LoopUnroll/full-unroll-bad-cost.ll

 ; RUN: opt -S -loop-unroll < %s | FileCheck %s
-; RUN: opt < %s -passes='require<opt-remark-emit>,loop(unroll)' -S | FileCheck %s
+; RUN: opt < %s -passes='require<opt-remark-emit>,loop(unroll-full)' -S | FileCheck %s
 
 ; LLVM should not try to fully unroll this loop.
 
 declare void @f()
 declare void @g()
 declare void @h()
 
 define void @trivial_loop() {

llvm/trunk/test/Transforms/LoopUnroll/full-unroll-crashers.ll

 ; Check that we don't crash on corner cases.
 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=1 -unroll-max-percent-threshold-boost=200 -o /dev/null
-; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=1 -unroll-max-percent-threshold-boost=200 -o /dev/null
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll-full)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=1 -unroll-max-percent-threshold-boost=200 -o /dev/null
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 @known_constant = internal unnamed_addr constant [10 x i32] [i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1], align 16
 
 define void @foo1() {
 entry:
   br label %for.body
 

llvm/trunk/test/Transforms/LoopUnroll/full-unroll-heuristics-2.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
-; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll-full)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 @unknown_global = internal unnamed_addr global [9 x i32] [i32 0, i32 -1, i32 0, i32 -1, i32 5, i32 -1, i32 0, i32 -1, i32 0], align 16
 @weak_constant = weak unnamed_addr constant [9 x i32] [i32 0, i32 -1, i32 0, i32 -1, i32 5, i32 -1, i32 0, i32 -1, i32 0], align 16
 
 ; Though @unknown_global is initialized with constant values, we can't consider
 ; it as a constant, so we shouldn't unroll the loop.
 ; CHECK-LABEL: @foo

llvm/trunk/test/Transforms/LoopUnroll/full-unroll-heuristics-cmp.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
-; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll-full)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 @known_constant = internal unnamed_addr constant [10 x i32] [i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1], align 16
 
 ; If we can figure out result of comparison on each iteration, we can resolve
 ; the depending branch. That means, that the unrolled version of the loop would
 ; have less code, because we don't need not-taken basic blocks there.
 ; This test checks that this is taken into consideration.

llvm/trunk/test/Transforms/LoopUnroll/full-unroll-heuristics-dce.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=12 -unroll-max-percent-threshold-boost=400 | FileCheck %s
-; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=12 -unroll-max-percent-threshold-boost=400 | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll-full)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=12 -unroll-max-percent-threshold-boost=400 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 @known_constant = internal unnamed_addr constant [10 x i32] [i32 0, i32 0, i32 0, i32 0, i32 1, i32 0, i32 0, i32 0, i32 0, i32 0], align 16
 
 ; If a load becomes a constant after loop unrolling, we sometimes can simplify
 ; CFG. This test verifies that we handle such cases.
 ; After one operand in an instruction is constant-folded and the
 ; instruction is simplified, the other operand might become dead.

llvm/trunk/test/Transforms/LoopUnroll/full-unroll-heuristics-geps.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
-; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll-full)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 ; When examining gep-instructions we shouldn't consider them simplified if the
 ; corresponding memory access isn't simplified. Doing the opposite might bias
 ; our estimate, so that we might decide to unroll even a simple memcpy loop.
 ;
 ; Thus, the following loop shouldn't be unrolled:
 ; CHECK-LABEL: @not_simplified_geps

llvm/trunk/test/Transforms/LoopUnroll/full-unroll-heuristics-phi-prop.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
-; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll-full)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 define i64 @propagate_loop_phis() {
 ; CHECK-LABEL: @propagate_loop_phis(
 ; CHECK-NOT: br i1
 ; CHECK: ret i64 3
 entry:
   br label %loop

llvm/trunk/test/Transforms/LoopUnroll/full-unroll-heuristics.ll

 ; In this particular test-case, complete unrolling will allow later
 ; optimizations to remove ~55% of the instructions, the loop body size is 9,
 ; and unrolled size is 65.
 
 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=10 -unroll-max-percent-threshold-boost=100 | FileCheck %s -check-prefix=TEST1
 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=20 -unroll-max-percent-threshold-boost=200 | FileCheck %s -check-prefix=TEST2
 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=20 -unroll-max-percent-threshold-boost=100 | FileCheck %s -check-prefix=TEST3
 
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll-full)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=10 -unroll-max-percent-threshold-boost=100 | FileCheck %s -check-prefix=TEST1
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll-full)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=20 -unroll-max-percent-threshold-boost=200 | FileCheck %s -check-prefix=TEST2
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll-full)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=20 -unroll-max-percent-threshold-boost=100 | FileCheck %s -check-prefix=TEST3
+
+; Check that these work when the unroller has partial unrolling enabled too.
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=10 -unroll-max-percent-threshold-boost=100 | FileCheck %s -check-prefix=TEST1
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=20 -unroll-max-percent-threshold-boost=200 | FileCheck %s -check-prefix=TEST2
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=20 -unroll-max-percent-threshold-boost=100 | FileCheck %s -check-prefix=TEST3
+
 ; If the absolute threshold is too low, we should not unroll:
 ; TEST1: %array_const_idx = getelementptr inbounds [9 x i32], [9 x i32]* @known_constant, i64 0, i64 %iv
 
 ; Otherwise, we should:
 ; TEST2-NOT: %array_const_idx = getelementptr inbounds [9 x i32], [9 x i32]* @known_constant, i64 0, i64 %iv
 
 ; If we do not boost threshold, the unroll will not happen:
 ; TEST3: %array_const_idx = getelementptr inbounds [9 x i32], [9 x i32]* @known_constant, i64 0, i64 %iv
 
 ; And check that we don't crash when we're not allowed to do any analysis.
 ; RUN: opt < %s -loop-unroll -unroll-max-iteration-count-to-analyze=0 -disable-output
+; RUN: opt < %s -passes='require<opt-remark-emit>,loop(unroll-full)' -unroll-max-iteration-count-to-analyze=0 -disable-output
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 @known_constant = internal unnamed_addr constant [9 x i32] [i32 0, i32 -1, i32 0, i32 -1, i32 5, i32 -1, i32 0, i32 -1, i32 0], align 16
 
 define i32 @foo(i32* noalias nocapture readonly %src) {
 entry:
   br label %loop
 

llvm/trunk/test/Transforms/LoopUnroll/full-unroll-keep-first-exit.ll

 ; RUN: opt -S -loop-unroll < %s | FileCheck %s
-; RUN: opt -S -passes='require<opt-remark-emit>,loop(unroll)' < %s | FileCheck %s
+; RUN: opt -S -passes='require<opt-remark-emit>,loop(unroll-full)' < %s | FileCheck %s
 
 ; Unroll twice, with first loop exit kept
 ; CHECK-LABEL: @s32_max1
 ; CHECK: do.body:
 ; CHECK:  store
 ; CHECK:  br i1 %cmp, label %do.body.1, label %do.end
 ; CHECK: do.end:
 ; CHECK:  ret void

llvm/trunk/test/Transforms/LoopUnroll/partial-unroll-const-bounds.ll

 ; RUN: opt < %s -S -unroll-partial-threshold=20 -unroll-threshold=20 -loop-unroll -unroll-allow-partial -unroll-runtime -unroll-allow-remainder -unroll-max-percent-threshold-boost=100 | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-partial-threshold=20 -unroll-threshold=20 -unroll-allow-partial -unroll-runtime -unroll-allow-remainder -unroll-max-percent-threshold-boost=100 | FileCheck %s
+;
+; Also check that the simple unroller doesn't allow the partial unrolling.
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll-full)' -unroll-partial-threshold=20 -unroll-threshold=20 -unroll-allow-partial -unroll-runtime -unroll-allow-remainder -unroll-max-percent-threshold-boost=100 | FileCheck %s --check-prefix=CHECK-NO-UNROLL
 
 ; The Loop TripCount is 9. However unroll factors 3 or 9 exceed given threshold.
 ; The test checks that we choose a smaller, power-of-two, unroll count and do not give up on unrolling.
 
 ; CHECK: for.body:
 ; CHECK: store
 ; CHECK: for.body.1:
 ; CHECK: store
 
+; CHECK-NO-UNROLL: for.body:
+; CHECK-NO-UNROLL: store
+; CHECK-NO-UNROLL-NOT: store
+
 define void @foo(i32* nocapture %a, i32* nocapture readonly %b) nounwind uwtable {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry
   %indvars.iv = phi i64 [ 1, %entry ], [ %indvars.iv.next, %for.body ]
   %arrayidx = getelementptr inbounds i32, i32* %b, i64 %indvars.iv
   %ld = load i32, i32* %arrayidx, align 4