[PM] Teach the LoopPassManager to automatically canonicalize loops by runnig LCSSA over them prior to running the loop pipeline.

[chandlerc]

Summary

This also teaches the loop PM to verify that LCSSA form is preserved
throughout the pipeline's run across the loop nest.

Most of the test updates just leverage this new functionality. One has to be
relaxed with the new PM as IVUsers is less powerful when it sees LCSSA input.

[davide]

include/llvm/Transforms/Scalar/LoopPassManager.h

315–317

These two can be a bit expensive. Maybe put them under #ifndef NDEBUG ?

[sepavloff]

include/llvm/Transforms/Scalar/LoopPassManager.h

315–317

In D28676 the same problem were solved by making VerifyLoopInfo global and running expensive checks only if -verify-loop-info is specified in command line. Maybe that change can be useful here?

[davide]

include/llvm/Transforms/Scalar/LoopPassManager.h

315–317

Maybe, eventually. But until all the bugs in the new PM are shaken properly my preference would be to run this check unconditionally for debug builds. (note, we do something similar for NewGVN and it revealed quite a few bugs, and these checks can be always be moved to LLVM_ENABLE_EXPENSIVE_CHECKS once we're satisfied with things and/or we think running the verification by default is crazy expensive).

[davide]

test/Analysis/IVUsers/quadradic-exit-value.ll

8

Why two prefixes here?

[chandlerc]

include/llvm/Transforms/Scalar/LoopPassManager.h

315–317

Agreed on all counts. Eventually we can turn this down, but for now I'd like to be aggressive.

test/Analysis/IVUsers/quadradic-exit-value.ll

8

Below, we only use the one prefix.

Without LCSSA, we get substantially more precise results here, whereas with it we get substantially more poor results. This is because of a combined weakness of SCEV and IVUsers which stems from SCEVExpander's inability to expand correctly in LCSSA form. =[ It's a mess.

I've talked to Michael (K) and Sanjoy about this and we have some ideas to fix this eventually, but not right away. (Fortunately, the only thing that cares today is LSR which is in the codegen phase and so not blocking anything.)

I wrote the FIXME above this to document what is going on here.

[davide]

LGTM. I'm still in favour of having the LCSSA verification enabled *only* for debug builds, but if you want to have that unconditionally (i.e. also for release, for now), fair enough. Worst case we'll get terribly annoyed by the long compile times and disable it =)

[chandlerc]

Update addressing code review comments and cleaning things up.

[davide]

Some minor comments , but I think this is good to go. I'll review the other related patch soon'ish.

include/llvm/Transforms/Scalar/LoopPassManager.h

52–54

Nit: unsorted (IR < Transforms)

test/Analysis/IVUsers/quadradic-exit-value.ll

8

Oh, sorry, I missed the fixme. Ignore my comment.

include/llvm/Transforms/Scalar/LoopPassManager.h

 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Transforms/Utils/LCSSA.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/PassManager.h"
 
 namespace llvm {
 
 // Forward declarations of an update tracking API used in the pass manager.
 class LPMUpdater;
 
 // Explicit specialization and instantiation declarations for the pass manager.
 // See the comments on the definition of the specialization for details on how

 /// FunctionPassManager. Note that if this pass is constructed with a \c
 /// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy
 /// analysis prior to running the loop passes over the function to enable a \c
 /// LoopAnalysisManager to be used within this run safely.
 template <typename LoopPassT>
 class FunctionToLoopPassAdaptor
     : public PassInfoMixin<FunctionToLoopPassAdaptor<LoopPassT>> {
 public:
-  explicit FunctionToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) {}
+  explicit FunctionToLoopPassAdaptor(LoopPassT Pass) : Pass(std::move(Pass)) {
+    LoopCanonicalizationFPM.addPass(LCSSAPass());
+  }
 
   /// \brief Runs the loop passes across every loop in the function.
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
+    // Before we even compute any loop analyses, first run a miniature function
+    // pass pipeline to put loops into their canonical form. Note that we can
+    // directly build up function analyses after this as the function pass
+    // manager handles all the invalidation at that layer.
+    PreservedAnalyses PA = LoopCanonicalizationFPM.run(F, AM);
+
     // Setup the loop analysis manager from its proxy.
     LoopAnalysisManager &LAM =
         AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
     // Get the loop structure for this function
     LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
 
     // If there are no loops, there is nothing to do here.
     if (LI.empty())
-      return PreservedAnalyses::all();
+      return PA;
 
     // Get the analysis results needed by loop passes.
     LoopStandardAnalysisResults LAR = {AM.getResult<AAManager>(F),
                                        AM.getResult<AssumptionAnalysis>(F),
                                        AM.getResult<DominatorTreeAnalysis>(F),
                                        AM.getResult<LoopAnalysis>(F),
                                        AM.getResult<ScalarEvolutionAnalysis>(F),
                                        AM.getResult<TargetLibraryAnalysis>(F),
                                        AM.getResult<TargetIRAnalysis>(F)};
 
-    PreservedAnalyses PA = PreservedAnalyses::all();
-
     // A postorder worklist of loops to process.
     SmallPriorityWorklist<Loop *, 4> Worklist;
 
     // Register the worklist and loop analysis manager so that loop passes can
     // update them when they mutate the loop nest structure.
     LPMUpdater Updater(Worklist, LAM);
 
     // Add the loop nests in the reverse order of LoopInfo. For some reason,
     // they are stored in RPO w.r.t. the control flow graph in LoopInfo. For
     // the purpose of unrolling, loop deletion, and LICM, we largely want to
     // work forward across the CFG so that we visit defs before uses and can
     // propagate simplifications from one loop nest into the next.
     // FIXME: Consider changing the order in LoopInfo.
     internal::appendLoopsToWorklist(reverse(LI), Worklist);
 
     do {
       Loop *L = Worklist.pop_back_val();
 
       // Reset the update structure for this loop.
       Updater.CurrentL = L;
       Updater.SkipCurrentLoop = false;
+
 #ifndef NDEBUG
+      // Save a parent loop pointer for asserts.
       Updater.ParentL = L->getParentLoop();
+
+      // Verify the loop structure and LCSSA form before visiting the loop.
+      L->verifyLoop();
+      assert(L->isRecursivelyLCSSAForm(LAR.DT, LI) &&
+             "Loops must remain in LCSSA form!");
 #endif
 
       PreservedAnalyses PassPA = Pass.run(*L, LAM, LAR, Updater);
       // FIXME: We should verify the set of analyses relevant to Loop passes
       // are preserved.
 
       // If the loop hasn't been deleted, we need to handle invalidation here.
       if (!Updater.skipCurrentLoop())
         // We know that the loop pass couldn't have invalidated any other
         // loop's analyses (that's the contract of a loop pass), so directly
         // handle the loop analysis manager's invalidation here.
         LAM.invalidate(*L, PassPA);
 
#endif
     PA.preserve<BasicAA>();
     PA.preserve<GlobalsAA>();
     PA.preserve<SCEVAA>();
     return PA;
   }
 
 private:
   LoopPassT Pass;
+
+  FunctionPassManager LoopCanonicalizationFPM;
 };
 
 /// \brief A function to deduce a loop pass type and wrap it in the templated
 /// adaptor.
 template <typename LoopPassT>
 FunctionToLoopPassAdaptor<LoopPassT>
 createFunctionToLoopPassAdaptor(LoopPassT Pass) {
   return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass));

test/Analysis/IVUsers/quadradic-exit-value.ll

 ; This test ensures that IVUsers works correctly in the legacy pass manager
 ; without LCSSA and in the specific ways that some of its users (LSR) require.
 ;
 ; FIXME: We need some way to match the precision here in the new PM where loop
 ; passes *always* work on LCSSA. This should stop using a different set of
 ; checks at that point.
 
-; RUN: opt < %s -analyze -iv-users | FileCheck %s
+; RUN: opt < %s -analyze -iv-users | FileCheck %s --check-prefixes=CHECK,CHECK-NO-LCSSA
 ; RUN: opt < %s -disable-output -passes='print<ivusers>' 2>&1 | FileCheck %s
 
 ; Provide legal integer types.
 target datalayout = "n8:16:32:64"
 
 ; The value of %r is dependent on a polynomial iteration expression.
 ;
 ; CHECK-LABEL: IV Users for loop %foo.loop
-; CHECK: {1,+,3,+,2}<%foo.loop>
+; CHECK-NO-LCSSA: {1,+,3,+,2}<%foo.loop>
 define i64 @foo(i64 %n) {
 entry:
   br label %foo.loop
 
 foo.loop:
   %indvar = phi i64 [ 0, %entry ], [ %indvar.next, %foo.loop ]
   %indvar.next = add i64 %indvar, 1
   %c = icmp eq i64 %indvar.next, %n
   br i1 %c, label %exit, label %foo.loop
 
 exit:
   %r = mul i64 %indvar.next, %indvar.next
   ret i64 %r
 }
 
 ; PR15470: LSR miscompile. The test2 function should return '1'.
 ;
 ; SCEV does not know how to denormalize chained recurrences, so make
 ; sure they aren't marked as post-inc users.
 ;
 ; CHECK-LABEL: IV Users for loop %test2.loop
-; CHECK: %sext.us = {0,+,(16777216 + (-16777216 * %sub.us))<nuw><nsw>,+,33554432}<%test2.loop> in %f = ashr i32 %sext.us, 24
+; CHECK-NO-LCSSA: %sext.us = {0,+,(16777216 + (-16777216 * %sub.us))<nuw><nsw>,+,33554432}<%test2.loop> in %f = ashr i32 %sext.us, 24
 define i32 @test2() {
 entry:
   br label %test2.loop
 
 test2.loop:
   %inc1115.us = phi i32 [ 0, %entry ], [ %inc11.us, %test2.loop ]
   %inc11.us = add nsw i32 %inc1115.us, 1
   %cmp.us = icmp slt i32 %inc11.us, 2

test/Other/new-pass-manager.ll

 ; RUN: opt -disable-output -disable-verify -debug-pass-manager \
 ; RUN:     -passes='loop(repeat<3>(no-op-loop))' %s 2>&1 \
 ; RUN:     | FileCheck %s --check-prefix=CHECK-REPEAT-LOOP-PASS
 ; CHECK-REPEAT-LOOP-PASS: Starting llvm::Module pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running pass: ModuleToFunctionPassAdaptor
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}>
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Starting llvm::Function pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running pass: FunctionToLoopPassAdaptor
-; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}>
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: LoopAnalysis
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: DominatorTreeAnalysis
+; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: InnerAnalysisManagerProxy<{{.*}}>
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: AAManager
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: TargetLibraryAnalysis
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: AssumptionAnalysis
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: ScalarEvolutionAnalysis
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running analysis: TargetIRAnalysis
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Starting Loop pass manager run
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Running pass: RepeatedPass
 ; CHECK-REPEAT-LOOP-PASS-NEXT: Starting Loop pass manager run

test/Transforms/LICM/atomics.ll

 ; RUN: opt < %s -S -basicaa -licm | FileCheck %s
-; RUN: opt -aa-pipeline=basic-aa -passes='lcssa,require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
 
 ; Check that we can hoist unordered loads
 define i32 @test1(i32* nocapture %y) nounwind uwtable ssp {
 entry:
   br label %loop
 
 loop:
   %i = phi i32 [ %inc, %loop ], [ 0, %entry ]

test/Transforms/LICM/constexpr.ll

 ; RUN: opt < %s -S -basicaa -licm | FileCheck %s
-; RUN: opt -aa-pipeline=basic-aa -passes='lcssa,require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' < %s -S | FileCheck %s
 ; This fixes PR22460
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-pc-windows-msvc"
 
 @in = internal unnamed_addr global i32* null, align 8
 @out = internal unnamed_addr global i32* null, align 8
 

test/Transforms/LICM/hoist-nounwind.ll

 ; RUN: opt -S -basicaa -licm < %s | FileCheck %s
-; RUN: opt -aa-pipeline=basic-aa -passes='lcssa,require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' -S %s | FileCheck %s
+; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' -S %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 declare void @f() nounwind
 
 ; Don't hoist load past nounwind call.
 define i32 @test1(i32* noalias nocapture readonly %a) nounwind uwtable {
 ; CHECK-LABEL: @test1(

test/Transforms/LICM/hoisting.ll

 ; RUN: opt < %s -licm -S | FileCheck %s
-; RUN: opt -lcssa %s | opt -aa-pipeline=basic-aa -passes='require<aa>,require<targetir>,require<scalar-evolution>,require<opt-remark-emit>,loop(licm)' -S | FileCheck %s
+; RUN: opt < %s -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' -S | FileCheck %s
 
 @X = global i32 0   ; <i32*> [#uses=1]
 
 declare void @foo()
 
 declare i32 @llvm.bitreverse.i32(i32)
 
 ; This testcase tests for a problem where LICM hoists