[PM] Port LoopSink to the new pass manager.

[chandlerc]

Summary

Like several other loop passes (the vectorizer, etc) this pass doesn't
really fit the model of a loop pass. The critical distinction is that it
isn't intended to be pipelined together with other loop passes. I plan
to add some documentation to the loop pass manager to make this more
clear on that side.

LoopSink is also different because it doesn't really need a lot of the
infrastructure of our loop passes. For example, if there aren't loop
invariant instructions causing a preheader to exist, there is no need to
form a preheader. It also doesn't need LCSSA because this pass is
only involved in sinking invariant instructions from a preheader into
the loop, not reasoning about live-outs.

This allows some nice simplifications to the pass in the new PM where we
can directly walk the loops once without restructuring them.

[davide]

The logic mostly looks fine (RPO walk etc..). Some minor comments, and I'm a little bit confused by the fact you don't pass SCEV to this pass anymore. See comments inline.

lib/Transforms/Scalar/LoopSink.cpp

311–326

This pattern is actually proliferating. How hard is to make this an helper before this patch goes in? (and replace the other uses)

331–332

The old PM actually passes SCEV to sinkLoopInvariantInstruction. Here you don't, what are the consequences?

340–345

As far as I can see the old pass doesn't preserve AA passes.
I'm fine with this going in but maybe can be separated?

370–371

Ugh, this seems wrong (not your fault of course). The transform seems to ask for AA and LoopInfo but doesn't quite list them as required.

[sanjoy]

lib/Transforms/Scalar/LoopSink.cpp

317

Don't you need to traverse LI in reverse? That way you'll push to PreOrderLoops in program order, and pop from it in reverse program order (which is what the pass expects).

345

Didn't you invalidate SCEV? Can you still preserve SCEVAA?

[chandlerc]

Update with fixes to most of the review comments. Factoring one thing out into
a separate patch.

[chandlerc]

Most comments addressed. Factoring out the loop walk to a helper.

lib/Transforms/Scalar/LoopSink.cpp

311–326

Sure. And as Sanjoy spotted, it even has a tiny bug.

331–332

It is only used to invalidate the loop in SCEV. Now we just don't preserve SCEV (and don't require it either). I'll add a comment.

340–345

In the new PM, we can actually preserve SCEVAA and not SCEV and it can work! But I don't think its in good shape yet.

And Davide, as you may have noticed below, the getLoopAnalysisUsage makes the old PM preserve AA as well! Yay!

Anyways, I'll just rip out AA preservation for now. We can add it back with intent and clarity later.

370–371

It does inside of getLoopAnalysisUsage. Yay subtle. =[

[sanjoy]

lgtm

[davide]

Looks good to me, thanks for clarifying =)

[chandlerc]

Update to use the newly added helper to compute the preorder walk, and
a freshened comment.

[chandlerc]

FYI, landing as I think this addressed everything and have LGTMs. But if anything ends up surprising folks, don't hesitate to pipe up!

include/llvm/Transforms/Scalar/LoopSink.h

+//===- LoopSink.h - Loop Sink Pass ------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file provides the interface for the Loop Sink pass.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_SCALAR_LOOPSINK_H
+#define LLVM_TRANSFORMS_SCALAR_LOOPSINK_H
+
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/IR/PassManager.h"
+#include "llvm/Transforms/Scalar/LoopPassManager.h"
+
+namespace llvm {
+
+/// A pass that does profile-guided sinking of instructions into loops.
+///
+/// This is a function pass as it shouldn't be composed into any kind of
+/// unified loop pass pipeline. The goal of it is to sink code into loops that
+/// is loop invariant but only required within the loop body when doing so
+/// reduces the global expected dynamic frequency with which it executes.
+/// A classic example is an extremely cold branch within a loop body.
+///
+/// We do this as a separate pass so that during normal optimization all
+/// invariant operations can be held outside the loop body to simplify
+/// fundamental analyses and transforms of the loop.
+class LoopSinkPass : public PassInfoMixin<LoopSinkPass> {
+public:
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM);
+};
+}
+
+#endif // LLVM_TRANSFORMS_SCALAR_LOOPSINK_H
+

lib/Passes/PassBuilder.cpp

 #include "llvm/Transforms/Scalar/NaryReassociate.h"
 #include "llvm/Transforms/Scalar/NewGVN.h"
 #include "llvm/Transforms/Scalar/PartiallyInlineLibCalls.h"
 #include "llvm/Transforms/Scalar/Reassociate.h"
 #include "llvm/Transforms/Scalar/SCCP.h"
 #include "llvm/Transforms/Scalar/SROA.h"
 #include "llvm/Transforms/Scalar/SimplifyCFG.h"
 #include "llvm/Transforms/Scalar/Sink.h"
+#include "llvm/Transforms/Scalar/LoopSink.h"
 #include "llvm/Transforms/Scalar/SpeculativeExecution.h"
 #include "llvm/Transforms/Scalar/TailRecursionElimination.h"
 #include "llvm/Transforms/Utils/AddDiscriminators.h"
 #include "llvm/Transforms/Utils/BreakCriticalEdges.h"
 #include "llvm/Transforms/Utils/LCSSA.h"
 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
 #include "llvm/Transforms/Utils/LoopSimplify.h"
 #include "llvm/Transforms/Utils/LowerInvoke.h"

lib/Passes/PassRegistry.def

 FUNCTION_PASS("no-op-function", NoOpFunctionPass())
 FUNCTION_PASS("libcalls-shrinkwrap", LibCallsShrinkWrapPass())
 FUNCTION_PASS("loweratomic", LowerAtomicPass())
 FUNCTION_PASS("lower-expect", LowerExpectIntrinsicPass())
 FUNCTION_PASS("lower-guard-intrinsic", LowerGuardIntrinsicPass())
 FUNCTION_PASS("guard-widening", GuardWideningPass())
 FUNCTION_PASS("gvn", GVN())
 FUNCTION_PASS("loop-simplify", LoopSimplifyPass())
+FUNCTION_PASS("loop-sink", LoopSinkPass())
 FUNCTION_PASS("lowerinvoke", LowerInvokePass())
 FUNCTION_PASS("mem2reg", PromotePass())
 FUNCTION_PASS("memcpyopt", MemCpyOptPass())
 FUNCTION_PASS("mldst-motion", MergedLoadStoreMotionPass())
 FUNCTION_PASS("nary-reassociate", NaryReassociatePass())
 FUNCTION_PASS("newgvn", NewGVNPass())
 FUNCTION_PASS("jump-threading", JumpThreadingPass())
 FUNCTION_PASS("partially-inline-libcalls", PartiallyInlineLibCallsPass())

lib/Transforms/Scalar/LoopSink.cpp

 //     DomBBs = BBs in InsertBBs that are dominated by BB
 //     if freq(DomBBs) > freq(BB)
 //       InsertBBs = UseBBs - DomBBs + BB
 //   For BB in InsertBBs:
 //     Insert I at BB's beginning
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Transforms/Scalar/LoopSink.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
       Changed = true;
   }
 
   if (Changed && SE)
     SE->forgetLoopDispositions(&L);
   return Changed;
 }
 
+PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) {
+  LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
+  // Nothing to do if there are no loops.
+  if (LI.empty())
+    return PreservedAnalyses::all();
+
+  AAResults &AA = FAM.getResult<AAManager>(F);
+  DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
+  BlockFrequencyInfo &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
+
+  // We want to do a postorder walk over the loops. Since loops are a tree this
+  // is equivalent to a reversed preorder walk and preorder is easy to compute
+  // without recursion.
+  // FIXME: We do this in several places, we should factor it into a helper.
+  SmallVector<Loop *, 4> PreOrderLoops, PreOrderWorklist;
+  for (Loop *RootL : LI) {
+    assert(PreOrderWorklist.empty() &&
+           "Must start with an empty preorder walk worklist.");
+    PreOrderWorklist.push_back(RootL);
+    do {
+      Loop *L = PreOrderWorklist.pop_back_val();
+      PreOrderWorklist.append(L->begin(), L->end());
+      PreOrderLoops.push_back(L);
+    } while (!PreOrderWorklist.empty());
+  }
+
+  bool Changed = false;
+  do {
+    Loop &L = *PreOrderLoops.pop_back_val();
+    Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI,
+                                             /*ScalarEvolution*/ nullptr);
+  } while (!PreOrderLoops.empty());
+
+  if (!Changed)
+    return PreservedAnalyses::all();
+
+  PreservedAnalyses PA;
+  PA.preserveSet<CFGAnalyses>();
+  // TODO: What we really want to do here is preserve an AA category, but that
+  // concept doesn't exist yet.
+  PA.preserve<AAManager>();
+  PA.preserve<BasicAA>();
+  PA.preserve<GlobalsAA>();
+  PA.preserve<SCEVAA>();
+  return PA;
+}
+
 namespace {
 struct LegacyLoopSinkPass : public LoopPass {
   static char ID;
   LegacyLoopSinkPass() : LoopPass(ID) {
     initializeLegacyLoopSinkPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
 
     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     return sinkLoopInvariantInstructions(
         *L, getAnalysis<AAResultsWrapperPass>().getAAResults(),
         getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
         getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
         getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
         SE ? &SE->getSE() : nullptr);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<BlockFrequencyInfoWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 };
 }
 
 char LegacyLoopSinkPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
 
 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }

test/Transforms/LICM/loopsink.ll

 ; RUN: opt -S -loop-sink < %s | FileCheck %s
+; RUN: opt -S -passes=loop-sink < %s | FileCheck %s
 
 @g = global i32 0, align 4
 
 ;     b1
 ;    /  \
 ;   b2  b6
 ;  /  \  |
 ; b3  b4 |

test/Transforms/LICM/sink.ll

 ; RUN: opt -S -licm < %s | FileCheck %s --check-prefix=CHECK-LICM
 ; RUN: opt -S -licm < %s | opt -S -loop-sink | FileCheck %s --check-prefix=CHECK-SINK
+; RUN: opt -S < %s -passes='require<opt-remark-emit>,loop(licm),loop-sink' \
+; RUN:     | FileCheck %s --check-prefix=CHECK-SINK
 
 ; Original source code:
 ; int g;
 ; int foo(int p, int x) {
 ;   for (int i = 0; i != x; i++)
 ;     if (__builtin_expect(i == p, 0)) {
 ;       x += g; x *= g;
 ;     }