[BFI] Make BFI information available through loop passes inside LoopStandardAnalysisResults

[modimo]

Summary

D65060 uncovered that trying to use BFI in loop passes can lead to non-deterministic behavior when blocks are re-used while retaining old BFI data.

To make sure BFI is preserved through loop passes a Value Handle (VH) callback is registered on blocks themselves. When a block is freed it now also wipes out the accompanying BFI entry such that stale BFI data can no longer persist resolving the determinism issue.

An optimistic approach would be to incrementally update BFI information throughout the loop passes rather than only invalidating them on removed blocks. The issues with that are:
1. It is not clear how BFI information should be incrementally updated: If a block is duplicated does its BFI information come with? How about if it's split/modified/moved around?
2. Assuming we can address these problems the implementation here will be a massive undertaking.

There's a known need of BFI in LICM analysis which requires correct but not incrementally updated BFI data. A follow-up change can register BFI in all loop passes so this preserved but potentially lossy data is available to any loop pass that wants it.

See: D75341 for an identical implementation of preserving BFI via VH callbacks. The previous statements do still apply but this change no longer has to be in this diff because it's already upstream 😄 .

This diff also moves BFI to be a part of LoopStandardAnalysisResults since the previous method using getCachedResults now (correctly!) statically asserts (D72893) that this data isn't static through the loop passes.

Testing
Ninja check

[modimo]

Linting

[modimo]

Commit my changes (crazy I know) so that the diff is actually updated for linting

[asbirlea]

A couple of quick comments, I haven't gone into details yet.

• please split off the changes that are NFCs (deleted spaces) and clang-format for ease to review.
• the test changes show a lot of dependencies that overload the loop pipeline. If only LICM benefits from it, I'd consider creating a BFI instance for the duration of the LICM pass, or only enabling it in loop pipelines that have LICM in them (see example comment in one of the tests).

llvm/include/llvm/Transforms/Scalar/LoopPassManager.h

278

This should not be unconditional. See MSSA approach.

llvm/test/Transforms/LoopRotate/pr35210.ll

51 ↗

(On Diff #286392)

e.g. there's no use of creating these for LoopRotate.

[modimo]

@asbirlea Thanks for taking a look!

I updated BFI to resemble MSSA as recommended which removed the BFI calculation unless LICM is invoked. Also removed the spurious diffs from formatting.

[modimo]

llvm/include/llvm/Transforms/Scalar/LoopPassManager.h

278

Fixed it up to resemble MSSA

408–409

@asbirlea Assuming this change matches expectations of making BFI on present when LICM or loop passes contain LICM I'm looking at the users of this and they seem to fall into 2 categories:

1. Those that specify the optional flags
2. Those that only pass in the LoopPassT

I found as I was updating with a new flag that due to C++ behavior a place that wasn't updated to have all 3 optional parameters will place DebugLogging into UseBlockFrequencyInfo which is a nasty error. I think a way around it is to enforce overloaded functions with either 0 additional parameters or having every "optional" parameter specified so it'll be a build time error for the previous scenario rather than a runtime issue.

llvm/test/Transforms/LoopRotate/pr35210.ll

51 ↗

(On Diff #286392)

Changed up so LoopRotate no longer has a dependency on BFI

[nikic]

This change adds three PDT calculations to the standard pipeline. Please try to avoid the PDT calculations if PGO is not used, possibly by using LazyBPI.

[wenlei]

If only LICM benefits from it, I'd consider creating a BFI instance for the duration of the LICM pass

Currently only LICM uses BFI, but I think it'd be beneficial for other loop passes to be able to use BFI too. BFI not accessible to loop passes seems to be a non-trivial limitation (comparing to other compilers). I would think it's not that other loop passes won't benefit from BFI, but because of the constraints imposed by pass manager, we couldn't reap any potential benefit.

I'm hoping that we could find a way to lift that limitation (and of course without breaking the invariants we need to keep for pass manager). This change is an attempt towards that. It's not ideal, as it only covers invalidation (for removal of blocks), but not incremental update for BFI to reflect arbitrary CFG changes, which can be really hard. Still, we think it's a practical solution to expose BFI to loop passes.

or only enabling it in loop pipelines that have LICM in them (see example comment in one of the tests).

Makes sense for now.

[modimo]

Change to LazyBFI for legacy pass manager to prevent rebuilding the post-dominator tree

[modimo]

In D86156#2231710, @nikic wrote:

This change adds three PDT calculations to the standard pipeline. Please try to avoid the PDT calculations if PGO is not used, possibly by using LazyBPI.

Good catch, changed to use LazyBFI which eliminates the extra PDT calculations unless this is accessed by PGO

[asbirlea]

llvm/lib/Passes/PassBuilder.cpp

522–523

It doesn't look like UseBlockFrequencyInfo is used for LPM2 here and below. Would it make sense to set it to false at this point?

llvm/test/Other/pass-pipelines.ll

57 ↗

(On Diff #288125)

Add ; CHECK-O2: Loop Pass Manager along with this comment.

Please consider if splitting the loop pass pipeline has any effects on optimizations. This is for the legacyPM only, so those who switched to the newPM will not be affected.
The solution may be to mark the analyses preserved in loop unswitch.

[modimo]

Remove usage need for BFI in LPM2 and set unswitching to preserve lazy BPI/BFI so it can remain in the same loop pass as LICM

llvm/lib/Passes/PassBuilder.cpp

522–523

Good catch, changed to false for LPM2.

llvm/test/Other/pass-pipelines.ll

57 ↗

(On Diff #288125)

To check my understanding here, with the split loop pass pipeline the phases look like the following:

Lazy Branch Probability Analysis
Lazy Block Frequency Analysis
Loop Pass Manager
  Loop Invariant Code Motion
Loop Pass Manager
  Unswitch loops

Walking through the code of Loop Pass Manager by itself it doesn't re-calculate or produce additional analysis. Thus the difference appears to arise as follows:

1. combined loop pass: loop opts are run one after the other per loop, so if you have loops L1 and L2 the order would be L1(LICM, Unswitch) -> L2 (LICM, Unswitch)
2. split loop pass: in this case it would be L1(LICM)->L2(LICM) into L1(Unswitch)->L2(Unswitch)

My qualitative assessment is that the impact here is quite minimal. The main scenario I can think of where differences could occur is having all LICM completed early can change the costing in unswitching for nested loops.

Unswitching only occurs once in the legacyPM and always after LICM so it seems fairly tame to build in this cross-pass dependence by marking lazy BFI/BPI preserved. I'd like to know if this level of cross-pass dependence is potentially an issue and if there's precedence for doing so if you have that context.

I've made the changes in the latest commit so that they exist in the same pass pipeline again by marking lazy BFI/FPI as preserved in unswitching. The value is definitely there to prevent unwanted side-effects.

[asbirlea]

Your understanding is correct. I only have one more comment on preserving passes in LICM too.

As a general note, it may make sense to include BFI in the set of loop passes always preserved (getLoopPassPreservedAnalyses()), if its nature is to always be preserved (with some potential info loss) due to the callbacks deleting blocks. But since we're only looking at LICM effect for now, this can be a follow up when/if needed.

Please allow some time for nikic@ to take a look too.

llvm/test/Other/opt-O2-pipeline.ll

277

Mark LICM to preserve these passes so they get moved above LICM rather than recomputed here (same as they are preserved in unswitch).

[nikic]

Current compile-time numbers show a 1% geomean regression: https://llvm-compile-time-tracker.com/compare.php?from=d7c119d89c5f6d0789cfd0a139c80e23912c0bb0&to=127615d90c7b4424ec83f5a8ab4256d08f7a8362&stat=instructions

I've left a comment inline with a possible cause.

llvm/lib/Transforms/Scalar/LICM.cpp

220

I believe that to make this actually lazy the getBFI() call needs to be guarded by some other check for presence of profiling data, otherwise it will be computed unconditionally at this point. Typically something like F.hasProfileData() or PSI.hasProfileSummary().

[modimo]

only use BFI when profile is enabled, have LICM mark BFI as preserved

[modimo]

In D86156#2242872, @asbirlea wrote:

As a general note, it may make sense to include BFI in the set of loop passes always preserved (getLoopPassPreservedAnalyses()), if its nature is to always be preserved (with some potential info loss) due to the callbacks deleting blocks. But since we're only looking at LICM effect for now, this can be a follow up when/if needed.

Certainly, that makes a lot of sense and makes it easier for any other loop optimization to take advantage of this data. I definitely want to make that happen, process-wise agreed that following up makes sense instead of tacking this on in addition.

llvm/lib/Transforms/Scalar/LICM.cpp

220

Appreciate the diligence here-your website is great!

Your assessment is correct, the ".getBFI()" call for lazy will calculate BFI. I've guarded it under hasProfileData now.

I see in the "about" section that I can use your setup to test TP changes myself, here's my fork of llvm-project if that option is still available: https://github.com/modiking/llvm-project

llvm/test/Other/opt-O2-pipeline.ll

277

Marked, these are no longer calculated again.

[asbirlea]

llvm/include/llvm/Transforms/Scalar/LoopPassManager.h

273

Add && F.hasProfileData() check here, in the NPM as well?

[modimo]

Condition usage of BFI to PGO in newPM as well

[modimo]

llvm/include/llvm/Transforms/Scalar/LoopPassManager.h

273

Makes sense, added.

[asbirlea]

Diff looks reasonable at this point. Thank you for the patch!
Please wait on @nikic for compile-time impact or additional feedback.

Just out of curiosity, in D65060, it was mentioned that using BFI got you ~7% improvement for a CPU related metric (@wenlei). Are you seeing benefits from this patch? And which pass manager are you using?

[wenlei]

In D86156#2243393, @asbirlea wrote:

Diff looks reasonable at this point. Thank you for the patch!
Please wait on @nikic for compile-time impact or additional feedback.

Just out of curiosity, in D65060, it was mentioned that using BFI got you ~7% improvement for a CPU related metric (@wenlei). Are you seeing benefits from this patch? And which pass manager are you using?

Thanks for quick review. We got the perf improvement from preventing a bad hoisting in a critical loop using BFI. Originally it was with legacy pass manager, hence the invalidation issue with new pass manager wasn't caught from our usage. This change was made as an internal patch for perf parity when we moved to new pass manager, and we've been using it for a while now.

[nikic]

New compile-time numbers: https://llvm-compile-time-tracker.com/compare.php?from=d7c119d89c5f6d0789cfd0a139c80e23912c0bb0&to=e0a1a6cac1b982023f8ceba8285d1ee7bc96bd32&stat=instructions The regression is now reduced to 0.2%. I assume that's the overhead of those CallbackVHs.

I have no familiarity with BFI, so possibly stupid question: There is already some similar handling as part of BFIImpl here: https://github.com/llvm/llvm-project/blob/0f14b2e6cbb54c84ed3b00b0db521f5ce2d1e3f2/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h#L1043-L1058 What is the difference to that / why are both needed?

llvm/include/llvm/Analysis/BlockFrequencyInfo.h

43

Is the shared_ptr/weak_ptr usage here necessary? This type of map deletion CallbackVH is a common pattern, but this is the first time I see it with weak_ptr.

44

It should not be necessary to explicitly store BB here, it is already part of the value handle (you can access it via *this for example).

48

I don't believe this virtual dtor is needed (class is final). For that matter, the method below also don't need to marked virtual.

llvm/lib/Analysis/BlockFrequencyInfo.cpp

212

May want to clear BlockWatchers in BlockFrequencyInfo::releaseMemory()?

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

1062

Huh, surprised that clang-format allows this.

[modimo]

Remove redundant VH callback as @nikic helpfully pointed out!

[modimo]

In D86156#2245103, @nikic wrote:

I have no familiarity with BFI, so possibly stupid question: There is already some similar handling as part of BFIImpl here: https://github.com/llvm/llvm-project/blob/0f14b2e6cbb54c84ed3b00b0db521f5ce2d1e3f2/llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h#L1043-L1058 What is the difference to that / why are both needed?

Well this is a funny situation: looks like someone else saw the same problem we observed and pushed the fix also using VH callbacks (D75341). Both of us coming to the same solution here is a good sign that its a good fit.

I'm glad you pointed this out! Looking at my diff with both callbacks incorporated the node gets erase() called twice but since the second call isn't in the DenseMap erase becomes a no-op. This explains why both changes didn't catastrophically collide against each other.

Given all that, the changes here to pass along the BFI information in the loop passes and allow usage in LICM still seems meaningful enough to commit. I've removed the redundant call-back added. Also updating the description to reflect the latest updates.

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

1062

I also thought that was a mis-format at first but the combination of rules turns out to prefer this.

[nikic]

Thanks, looks good now :)

[modimo]

Rebase

[modimo]

Rebase #2

[wenlei]

Committed on behalf of @modimo.

[thakis]

Looks like this breaks tests: http://45.33.8.238/linux/27942/step_12.txt

Ptal, and revert for now if it takes a while to fix.

[wenlei]

Just saw this. Thanks @Alina Sbirlea for fixing the tests, much appreciated!

On 9/15/20, 6:44 PM, "Nico Weber via Phabricator" <[e-mail]> wrote:

thakis added a comment.

Looks like this breaks tests: https://urldefense.proofpoint.com/v2/url?u=http-3A__45.33.8.238_linux_27942_step-5F12.txt&d=DwIFAg&c=5VD0RTtNlTh3ycd41b3MUw&r=KfYo542rDdZQGClmgz-RBw&m=WVDTkMJEgC2QBjCWKFwyWX-ftSq4MQIeuJdkzkhJdck&s=u5nGzx9n7KhDMJ5K5977aCoxEF8XTrwovmuF0w0QVhw&e= 

Ptal, and revert for now if it takes a while to fix.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D86156_new_&d=DwIFAg&c=5VD0RTtNlTh3ycd41b3MUw&r=KfYo542rDdZQGClmgz-RBw&m=WVDTkMJEgC2QBjCWKFwyWX-ftSq4MQIeuJdkzkhJdck&s=7S7jBRn6nAdqYCKhAJ2_bj-1GFfwhTmDvykaV67bOd4&e= 

https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D86156&d=DwIFAg&c=5VD0RTtNlTh3ycd41b3MUw&r=KfYo542rDdZQGClmgz-RBw&m=WVDTkMJEgC2QBjCWKFwyWX-ftSq4MQIeuJdkzkhJdck&s=whWFyZ-i_C3g_NJi7ZrVBm4HMklqSjbBalaSQEIf22g&e=

[modimo]

Thanks @asbirlea!

llvm/include/llvm/Analysis/BlockFrequencyInfo.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFO_H
 #define LLVM_ANALYSIS_BLOCKFREQUENCYINFO_H
 
 #include "llvm/ADT/Optional.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/BlockFrequency.h"
 #include <cstdint>
 #include <memory>
+#include <vector>
 
 namespace llvm {
 
 class BasicBlock;
 class BranchProbabilityInfo;
 class Function;
 class LoopInfo;
 class Module;
 class raw_ostream;
 template <class BlockT> class BlockFrequencyInfoImpl;
 
 enum PGOViewCountsType { PGOVCT_None, PGOVCT_Graph, PGOVCT_Text };
 
 /// BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to
 /// estimate IR basic block frequencies.
 class BlockFrequencyInfo {
   using ImplType = BlockFrequencyInfoImpl<BasicBlock>;
 
-  std::unique_ptr<ImplType> BFI;
+  class BFICallbackVH final : public CallbackVH {
+    std::weak_ptr<ImplType> BFI;
+    const BasicBlock *BB;
+
+  public:
+    BFICallbackVH(std::shared_ptr<ImplType> BFI, const BasicBlock *BB);
+    virtual ~BFICallbackVH() = default;
+
+    virtual void deleted() override;
+    virtual void allUsesReplacedWith(Value *V) override;
+  };
+  std::vector<BFICallbackVH> BlockWatchers;
+
+  std::shared_ptr<ImplType> BFI;
 
 public:
   BlockFrequencyInfo();
   BlockFrequencyInfo(const Function &F, const BranchProbabilityInfo &BPI,
                      const LoopInfo &LI);
   BlockFrequencyInfo(const BlockFrequencyInfo &) = delete;
   BlockFrequencyInfo &operator=(const BlockFrequencyInfo &) = delete;
   BlockFrequencyInfo(BlockFrequencyInfo &&Arg);

llvm/include/llvm/Analysis/BlockFrequencyInfoImpl.h

 ///       - We can propagate mass iteratively through the SCC, for some fixed
 ///         number of iterations.  Each iteration starts by assigning the entry
 ///         blocks their backedge mass from the prior iteration.  The final
 ///         mass for each block (and each exit, and the total backedge mass
 ///         used for computing loop scale) is the sum of all iterations.
 ///         (Running this until fixed point would "solve" the geometric
 ///         series by simulation.)
 template <class BT> class BlockFrequencyInfoImpl : BlockFrequencyInfoImplBase {
+public:
+  using BlockT = typename bfi_detail::TypeMap<BT>::BlockT;
+
+private:
   // This is part of a workaround for a GCC 4.7 crash on lambdas.
   friend struct bfi_detail::BlockEdgesAdder<BT>;
 
-  using BlockT = typename bfi_detail::TypeMap<BT>::BlockT;
   using BlockKeyT = typename bfi_detail::TypeMap<BT>::BlockKeyT;
   using FunctionT = typename bfi_detail::TypeMap<BT>::FunctionT;
   using BranchProbabilityInfoT =
       typename bfi_detail::TypeMap<BT>::BranchProbabilityInfoT;
   using LoopT = typename bfi_detail::TypeMap<BT>::LoopT;
   using LoopInfoT = typename bfi_detail::TypeMap<BT>::LoopInfoT;
   using Successor = GraphTraits<const BlockT *>;
   using Predecessor = GraphTraits<Inverse<const BlockT *>>;

   }
 
   Scaled64 getFloatingBlockFreq(const BlockT *BB) const {
     return BlockFrequencyInfoImplBase::getFloatingBlockFreq(getNode(BB));
   }
 
   const BranchProbabilityInfoT &getBPI() const { return *BPI; }
 
+  /// Removes \p BB from internal datastructures.
+  /// \return false if the block did not exist.
+  bool removeBlock(const BlockT *BB);
+
+  /// \return all blocks known to this datastructure.
+  DenseSet<const BlockT *> getRegisteredBlocks() const;
+
   /// Print the frequencies for the current function.
   ///
   /// Prints the frequencies for the blocks in the current function.
   ///
   /// Blocks are printed in the natural iteration order of the function, rather
   /// than reverse post-order.  This provides two advantages:  writing -analyze
   /// tests is easier (since blocks come out in source order), and even
   /// unreachable blocks are printed.

     // by the size of Freqs.
     BlockNode NewNode(Freqs.size());
     Nodes[BB] = {NewNode, BFICallbackVH(BB, this)};
     Freqs.emplace_back();
     BlockFrequencyInfoImplBase::setBlockFreq(NewNode, Freq);
   }
 }
 
+template <class BT>
+bool BlockFrequencyInfoImpl<BT>::removeBlock(const BlockT *BB) {
+  return Nodes.erase(BB);
+}
+
+template <class BT>
+DenseSet<const typename BlockFrequencyInfoImpl<BT>::BlockT *>
+BlockFrequencyInfoImpl<BT>::getRegisteredBlocks() const {
+  DenseSet<const BlockT *> Ret;
+  for (auto &BN : Nodes)
+    Ret.insert(BN.first);
+  return Ret;
+}
+
 template <class BT> void BlockFrequencyInfoImpl<BT>::initializeRPOT() {
   const BlockT *Entry = &F->front();
   RPOT.reserve(F->size());
   std::copy(po_begin(Entry), po_end(Entry), std::back_inserter(RPOT));
   std::reverse(RPOT.begin(), RPOT.end());
 
   assert(RPOT.size() - 1 <= BlockNode::getMaxIndex() &&
          "More nodes in function than Block Frequency Info supports");

llvm/include/llvm/Analysis/LoopAnalysisManager.h

 struct LoopStandardAnalysisResults {
   AAResults &AA;
   AssumptionCache ∾
   DominatorTree &DT;
   LoopInfo &LI;
   ScalarEvolution &SE;
   TargetLibraryInfo &TLI;
   TargetTransformInfo &TTI;
+  BlockFrequencyInfo *BFI;
   MemorySSA *MSSA;
 };
 
 /// Extern template declaration for the analysis set for this IR unit.
 extern template class AllAnalysesOn<Loop>;
 
 extern template class AnalysisManager<Loop, LoopStandardAnalysisResults &>;
 /// The loop analysis manager.

llvm/include/llvm/Transforms/Scalar/LoopPassManager.h

 #ifndef LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H
 #define LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H
 
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/PriorityWorklist.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"

 /// 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, bool UseMemorySSA = false,
+                                     bool UseBlockFrequencyInfo = false,
                                      bool DebugLogging = false)
       : Pass(std::move(Pass)), LoopCanonicalizationFPM(DebugLogging),
-        UseMemorySSA(UseMemorySSA) {
+        UseMemorySSA(UseMemorySSA),
+        UseBlockFrequencyInfo(UseBlockFrequencyInfo) {
     LoopCanonicalizationFPM.addPass(LoopSimplifyPass());
     LoopCanonicalizationFPM.addPass(LCSSAPass());
   }
 
   /// 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
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
     // If there are no loops, there is nothing to do here.
     if (LI.empty())
       return PA;
 
     // Get the analysis results needed by loop passes.
     MemorySSA *MSSA = UseMemorySSA
                           ? (&AM.getResult<MemorySSAAnalysis>(F).getMSSA())
                           : nullptr;
+    BlockFrequencyInfo *BFI = UseBlockFrequencyInfo && F.hasProfileData()
+                                  ? (&AM.getResult<BlockFrequencyAnalysis>(F))
+                                  : nullptr;
     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),
+                                       BFI,
                                        MSSA};
 
     // Setup the loop analysis manager from its proxy. It is important that
     // this is only done when there are loops to process and we have built the
     // LoopStandardAnalysisResults object. The loop analyses cached in this
     // manager have access to those analysis results and so it must invalidate
     // itself when they go away.
     auto &LAMFP = AM.getResult<LoopAnalysisManagerFunctionProxy>(F);
#endif
     // but that's OK because we've taken care to invalidate analyses in the
     // loop analysis manager incrementally above.
     PA.preserveSet<AllAnalysesOn<Loop>>();
     PA.preserve<LoopAnalysisManagerFunctionProxy>();
     // We also preserve the set of standard analyses.
     PA.preserve<DominatorTreeAnalysis>();
     PA.preserve<LoopAnalysis>();
     PA.preserve<ScalarEvolutionAnalysis>();
+    if (UseBlockFrequencyInfo && F.hasProfileData())
+      PA.preserve<BlockFrequencyAnalysis>();
     if (UseMemorySSA)
       PA.preserve<MemorySSAAnalysis>();
     // FIXME: 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;
   }
 
   static bool isRequired() { return true; }
 
 private:
   LoopPassT Pass;
 
   FunctionPassManager LoopCanonicalizationFPM;
 
   bool UseMemorySSA = false;
+  bool UseBlockFrequencyInfo = false;
 };
 
 /// A function to deduce a loop pass type and wrap it in the templated
 /// adaptor.
 template <typename LoopPassT>
 FunctionToLoopPassAdaptor<LoopPassT>
 createFunctionToLoopPassAdaptor(LoopPassT Pass, bool UseMemorySSA = false,
+                                bool UseBlockFrequencyInfo = false,
                                 bool DebugLogging = false) {
-  return FunctionToLoopPassAdaptor<LoopPassT>(std::move(Pass), UseMemorySSA,
-                                              DebugLogging);
+  return FunctionToLoopPassAdaptor<LoopPassT>(
+      std::move(Pass), UseMemorySSA, UseBlockFrequencyInfo, DebugLogging);
 }
 
 /// Pass for printing a loop's contents as textual IR.
 class PrintLoopPass : public PassInfoMixin<PrintLoopPass> {
   raw_ostream &OS;
   std::string Banner;
 
 public:

llvm/lib/Analysis/BlockFrequencyInfo.cpp

                                     FunctionAnalysisManager::Invalidator &) {
   // Check whether the analysis, all analyses on functions, or the function's
   // CFG have been preserved.
   auto PAC = PA.getChecker<BlockFrequencyAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
            PAC.preservedSet<CFGAnalyses>());
 }
 
+BlockFrequencyInfo::BFICallbackVH::BFICallbackVH(
+    std::shared_ptr<BlockFrequencyInfoImpl<BasicBlock>> BFI,
+    const BasicBlock *BB)
+    : CallbackVH(const_cast<BasicBlock *>(BB)), BFI(BFI), BB(BB) {}
+
+void BlockFrequencyInfo::BFICallbackVH::deleted() {
+  if (auto BFII = BFI.lock())
+    BFII->removeBlock(BB);
+  CallbackVH::deleted();
+}
+
+void BlockFrequencyInfo::BFICallbackVH::allUsesReplacedWith(Value *V) {
+  if (auto BFII = BFI.lock())
+    BFII->removeBlock(BB);
+  CallbackVH::allUsesReplacedWith(V);
+}
+
 void BlockFrequencyInfo::calculate(const Function &F,
                                    const BranchProbabilityInfo &BPI,
                                    const LoopInfo &LI) {
   if (!BFI)
     BFI.reset(new ImplType);
   BFI->calculate(F, BPI, LI);
+
+  BlockWatchers.clear();
+  auto RegisteredBlocks = BFI->getRegisteredBlocks();
+  BlockWatchers.reserve(RegisteredBlocks.size());
+  for (const auto *BB : RegisteredBlocks)
+    BlockWatchers.emplace_back(BFICallbackVH(BFI, BB));
+
   if (ViewBlockFreqPropagationDAG != GVDT_None &&
       (ViewBlockFreqFuncName.empty() ||
        F.getName().equals(ViewBlockFreqFuncName))) {
     view();
   }
   if (PrintBlockFreq &&
       (PrintBlockFreqFuncName.empty() ||
        F.getName().equals(PrintBlockFreqFuncName))) {

llvm/lib/Passes/PassBuilder.cpp

   for (auto &C : LoopOptimizerEndEPCallbacks)
     C(LPM2, Level);
 
   // We provide the opt remark emitter pass for LICM to use. We only need to do
   // this once as it is immutable.
   FPM.addPass(
       RequireAnalysisPass<OptimizationRemarkEmitterAnalysis, Function>());
   FPM.addPass(createFunctionToLoopPassAdaptor(
-      std::move(LPM1), EnableMSSALoopDependency, DebugLogging));
+      std::move(LPM1), EnableMSSALoopDependency, /*UseBlockFrequencyInfo=*/true,
+      DebugLogging));
   FPM.addPass(SimplifyCFGPass());
   FPM.addPass(InstCombinePass());
   // The loop passes in LPM2 (LoopFullUnrollPass) do not preserve MemorySSA.
   // *All* loop passes must preserve it, in order to be able to use it.
   FPM.addPass(createFunctionToLoopPassAdaptor(
-      std::move(LPM2), /*UseMemorySSA=*/false, DebugLogging));
+      std::move(LPM2), /*UseMemorySSA=*/false, /*UseBlockFrequencyInfo=*/false,
+      DebugLogging));
 
   // Delete small array after loop unroll.
   FPM.addPass(SROA());
 
   // Specially optimize memory movement as it doesn't look like dataflow in SSA.
   FPM.addPass(MemCpyOptPass());
 
   // Sparse conditional constant propagation.

   for (auto &C : LoopOptimizerEndEPCallbacks)
     C(LPM2, Level);
 
   // We provide the opt remark emitter pass for LICM to use. We only need to do
   // this once as it is immutable.
   FPM.addPass(
       RequireAnalysisPass<OptimizationRemarkEmitterAnalysis, Function>());
   FPM.addPass(createFunctionToLoopPassAdaptor(
-      std::move(LPM1), EnableMSSALoopDependency, DebugLogging));
+      std::move(LPM1), EnableMSSALoopDependency, /*UseBlockFrequencyInfo=*/true,
+      DebugLogging));
   FPM.addPass(SimplifyCFGPass());
   FPM.addPass(InstCombinePass());
   // The loop passes in LPM2 (IndVarSimplifyPass, LoopIdiomRecognizePass,
   // LoopDeletionPass and LoopFullUnrollPass) do not preserve MemorySSA.
   // *All* loop passes must preserve it, in order to be able to use it.
   FPM.addPass(createFunctionToLoopPassAdaptor(
-      std::move(LPM2), /*UseMemorySSA=*/false, DebugLogging));
+      std::move(LPM2), /*UseMemorySSA=*/false, /*UseBlockFrequencyInfo=*/false,
+      DebugLogging));
 
   // Delete small array after loop unroll.
   FPM.addPass(SROA());
 
   // Eliminate redundancies.
   FPM.addPass(MergedLoadStoreMotionPass());
   if (RunNewGVN)
     FPM.addPass(NewGVNPass());

 
   // Re-consider control flow based optimizations after redundancy elimination,
   // redo DCE, etc.
   FPM.addPass(JumpThreadingPass());
   FPM.addPass(CorrelatedValuePropagationPass());
   FPM.addPass(DSEPass());
   FPM.addPass(createFunctionToLoopPassAdaptor(
       LICMPass(PTO.LicmMssaOptCap, PTO.LicmMssaNoAccForPromotionCap),
-      EnableMSSALoopDependency, DebugLogging));
+      EnableMSSALoopDependency, /*UseBlockFrequencyInfo=*/true, DebugLogging));
 
   if (PTO.Coroutines)
     FPM.addPass(CoroElidePass());
 
   for (auto &C : ScalarOptimizerLateEPCallbacks)
     C(FPM, Level);
 
   // Finally, do an expensive DCE pass to catch all the dead code exposed by

     return;
   }
 
   // Perform PGO instrumentation.
   MPM.addPass(PGOInstrumentationGen(IsCS));
 
   FunctionPassManager FPM;
   FPM.addPass(createFunctionToLoopPassAdaptor(
-      LoopRotatePass(), EnableMSSALoopDependency, DebugLogging));
+      LoopRotatePass(), EnableMSSALoopDependency,
+      /*UseBlockFrequencyInfo=*/false, DebugLogging));
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
 
   // Add the profile lowering pass.
   InstrProfOptions Options;
   if (!ProfileFile.empty())
     Options.InstrProfileOutput = ProfileFile;
   // Do counter promotion at Level greater than O0.
   Options.DoCounterPromotion = true;

   // rather than on each loop in an inside-out manner, and so they are actually
   // function passes.
 
   for (auto &C : VectorizerStartEPCallbacks)
     C(OptimizePM, Level);
 
   // First rotate loops that may have been un-rotated by prior passes.
   OptimizePM.addPass(createFunctionToLoopPassAdaptor(
-      LoopRotatePass(), EnableMSSALoopDependency, DebugLogging));
+      LoopRotatePass(), EnableMSSALoopDependency,
+      /*UseBlockFrequencyInfo=*/false, DebugLogging));
 
   // Distribute loops to allow partial vectorization.  I.e. isolate dependences
   // into separate loop that would otherwise inhibit vectorization.  This is
   // currently only performed for loops marked with the metadata
   // llvm.loop.distribute=true or when -enable-loop-distribute is specified.
   OptimizePM.addPass(LoopDistributePass());
 
   // Populates the VFABI attribute with the scalar-to-vector mappings

   OptimizePM.addPass(LoopUnrollPass(LoopUnrollOptions(
       Level.getSpeedupLevel(), /*OnlyWhenForced=*/!PTO.LoopUnrolling,
       PTO.ForgetAllSCEVInLoopUnroll)));
   OptimizePM.addPass(WarnMissedTransformationsPass());
   OptimizePM.addPass(InstCombinePass());
   OptimizePM.addPass(RequireAnalysisPass<OptimizationRemarkEmitterAnalysis, Function>());
   OptimizePM.addPass(createFunctionToLoopPassAdaptor(
       LICMPass(PTO.LicmMssaOptCap, PTO.LicmMssaNoAccForPromotionCap),
-      EnableMSSALoopDependency, DebugLogging));
+      EnableMSSALoopDependency, /*UseBlockFrequencyInfo=*/true, DebugLogging));
 
   // Now that we've vectorized and unrolled loops, we may have more refined
   // alignment information, try to re-derive it here.
   OptimizePM.addPass(AlignmentFromAssumptionsPass());
 
   // Split out cold code. Splitting is done late to avoid hiding context from
   // other optimizations and inadvertently regressing performance. The tradeoff
   // is that this has a higher code size cost than splitting early.

     auto Params = parsePassParameters(PARSER, Name, NAME);                     \
     if (!Params)                                                               \
       return Params.takeError();                                               \
     MPM.addPass(createModuleToFunctionPassAdaptor(CREATE_PASS(Params.get()))); \
     return Error::success();                                                   \
   }
 #define LOOP_PASS(NAME, CREATE_PASS)                                           \
   if (Name == NAME) {                                                          \
-    MPM.addPass(createModuleToFunctionPassAdaptor(                             \
-        createFunctionToLoopPassAdaptor(CREATE_PASS, false, DebugLogging)));   \
+    MPM.addPass(                                                               \
+        createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(     \
+            CREATE_PASS, false, false, DebugLogging)));                        \
     return Error::success();                                                   \
   }
 #define LOOP_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER)                       \
   if (checkParametrizedPassName(Name, NAME)) {                                 \
     auto Params = parsePassParameters(PARSER, Name, NAME);                     \
     if (!Params)                                                               \
       return Params.takeError();                                               \
     MPM.addPass(                                                               \
         createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(     \
-            CREATE_PASS(Params.get()), false, DebugLogging)));                 \
+            CREATE_PASS(Params.get()), false, false, DebugLogging)));          \
     return Error::success();                                                   \
   }
 #include "PassRegistry.def"
 
   for (auto &C : ModulePipelineParsingCallbacks)
     if (C(Name, MPM, InnerPipeline))
       return Error::success();
   return make_error<StringError>(

     auto Params = parsePassParameters(PARSER, Name, NAME);                     \
     if (!Params)                                                               \
       return Params.takeError();                                               \
     CGPM.addPass(createCGSCCToFunctionPassAdaptor(CREATE_PASS(Params.get()))); \
     return Error::success();                                                   \
   }
 #define LOOP_PASS(NAME, CREATE_PASS)                                           \
   if (Name == NAME) {                                                          \
-    CGPM.addPass(createCGSCCToFunctionPassAdaptor(                             \
-        createFunctionToLoopPassAdaptor(CREATE_PASS, false, DebugLogging)));   \
+    CGPM.addPass(                                                              \
+        createCGSCCToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(      \
+            CREATE_PASS, false, false, DebugLogging)));                        \
     return Error::success();                                                   \
   }
 #define LOOP_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER)                       \
   if (checkParametrizedPassName(Name, NAME)) {                                 \
     auto Params = parsePassParameters(PARSER, Name, NAME);                     \
     if (!Params)                                                               \
       return Params.takeError();                                               \
     CGPM.addPass(                                                              \
         createCGSCCToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(      \
-            CREATE_PASS(Params.get()), false, DebugLogging)));                 \
+            CREATE_PASS(Params.get()), false, false, DebugLogging)));          \
     return Error::success();                                                   \
   }
 #include "PassRegistry.def"
 
   for (auto &C : CGSCCPipelineParsingCallbacks)
     if (C(Name, CGPM, InnerPipeline))
       return Error::success();
   return make_error<StringError>(

     }
     if (Name == "loop" || Name == "loop-mssa") {
       LoopPassManager LPM(DebugLogging);
       if (auto Err = parseLoopPassPipeline(LPM, InnerPipeline, VerifyEachPass,
                                            DebugLogging))
         return Err;
       // Add the nested pass manager with the appropriate adaptor.
       bool UseMemorySSA = (Name == "loop-mssa");
-      FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM), UseMemorySSA,
-                                                  DebugLogging));
+      FPM.addPass(createFunctionToLoopPassAdaptor(
+          std::move(LPM), UseMemorySSA, /*UseBlockFrequencyInfo=*/false,
+          DebugLogging));
       return Error::success();
     }
     if (auto Count = parseRepeatPassName(Name)) {
       FunctionPassManager NestedFPM(DebugLogging);
       if (auto Err = parseFunctionPassPipeline(NestedFPM, InnerPipeline,
                                                VerifyEachPass, DebugLogging))
         return Err;
       FPM.addPass(createRepeatedPass(*Count, std::move(NestedFPM)));

     return Error::success();                                                   \
   }
 // FIXME: UseMemorySSA is set to false. Maybe we could do things like:
 //        bool UseMemorySSA = !("canon-freeze" || "loop-predication" ||
 //                              "guard-widening");
 //        The risk is that it may become obsolete if we're not careful.
 #define LOOP_PASS(NAME, CREATE_PASS)                                           \
   if (Name == NAME) {                                                          \
-    FPM.addPass(                                                               \
-        createFunctionToLoopPassAdaptor(CREATE_PASS, false, DebugLogging));    \
+    FPM.addPass(createFunctionToLoopPassAdaptor(CREATE_PASS, false, false,     \
+                                                DebugLogging));                \
     return Error::success();                                                   \
   }
 #define LOOP_PASS_WITH_PARAMS(NAME, CREATE_PASS, PARSER)                       \
   if (checkParametrizedPassName(Name, NAME)) {                                 \
     auto Params = parsePassParameters(PARSER, Name, NAME);                     \
     if (!Params)                                                               \
       return Params.takeError();                                               \
     FPM.addPass(createFunctionToLoopPassAdaptor(CREATE_PASS(Params.get()),     \
-                                                false, DebugLogging));         \
+                                                false, false, DebugLogging));  \
     return Error::success();                                                   \
   }
 #include "PassRegistry.def"
 
   for (auto &C : FunctionPipelineParsingCallbacks)
     if (C(Name, FPM, InnerPipeline))
       return Error::success();
   return make_error<StringError>(

llvm/lib/Transforms/Scalar/LICM.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/GuardUtils.h"
+#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
 #include "llvm/Analysis/Loads.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/MustExecute.h"

 
 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
                                   ICFLoopSafetyInfo &SafetyInfo,
                                   MemorySSAUpdater *MSSAU, ScalarEvolution *SE);
 
 namespace {
 struct LoopInvariantCodeMotion {
   bool runOnLoop(Loop *L, AAResults *AA, LoopInfo *LI, DominatorTree *DT,
-                 TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
-                 ScalarEvolution *SE, MemorySSA *MSSA,
+                 BlockFrequencyInfo *BFI, TargetLibraryInfo *TLI,
+                 TargetTransformInfo *TTI, ScalarEvolution *SE, MemorySSA *MSSA,
                  OptimizationRemarkEmitter *ORE);
 
   LoopInvariantCodeMotion(unsigned LicmMssaOptCap,
                           unsigned LicmMssaNoAccForPromotionCap)
       : LicmMssaOptCap(LicmMssaOptCap),
         LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap) {}
 
 private:
struct LegacyLICMPass : public LoopPass {
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
 
     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
     MemorySSA *MSSA = EnableMSSALoopDependency
                           ? (&getAnalysis<MemorySSAWrapperPass>().getMSSA())
                           : nullptr;
+    bool hasProfileData = L->getHeader()->getParent()->hasProfileData();
+    BlockFrequencyInfo *BFI =
+        hasProfileData ? &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI()
+                       : nullptr;
     // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
-    // pass.  Function analyses need to be preserved across loop transformations
+    // pass. Function analyses need to be preserved across loop transformations
     // but ORE cannot be preserved (see comment before the pass definition).
     OptimizationRemarkEmitter ORE(L->getHeader()->getParent());
-    return LICM.runOnLoop(L,
-                          &getAnalysis<AAResultsWrapperPass>().getAAResults(),
-                          &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
-                          &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
-                          &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
-                              *L->getHeader()->getParent()),
-                          &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
-                              *L->getHeader()->getParent()),
-                          SE ? &SE->getSE() : nullptr, MSSA, &ORE);
+    return LICM.runOnLoop(
+        L, &getAnalysis<AAResultsWrapperPass>().getAAResults(),
+        &getAnalysis<DominatorTreeWrapperPass>().getDomTree(), BFI,
   }
 
   /// This transformation requires natural loop information & requires that
   /// loop preheaders be inserted into the CFG...
   ///
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addPreserved<DominatorTreeWrapperPass>();
     AU.addPreserved<LoopInfoWrapperPass>();
     AU.addRequired<TargetLibraryInfoWrapperPass>();
     if (EnableMSSALoopDependency) {
       AU.addRequired<MemorySSAWrapperPass>();
       AU.addPreserved<MemorySSAWrapperPass>();
     }
     AU.addRequired<TargetTransformInfoWrapperPass>();
     getLoopAnalysisUsage(AU);
+    LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);
+    AU.addPreserved<LazyBlockFrequencyInfoPass>();
+    AU.addPreserved<LazyBranchProbabilityInfoPass>();
   }
 
 private:
   LoopInvariantCodeMotion LICM;
 };
 } // namespace
 
 PreservedAnalyses LICMPass::run(Loop &L, LoopAnalysisManager &AM,
                                 LoopStandardAnalysisResults &AR, LPMUpdater &) {
   // For the new PM, we also can't use OptimizationRemarkEmitter as an analysis
   // pass.  Function analyses need to be preserved across loop transformations
   // but ORE cannot be preserved (see comment before the pass definition).
   OptimizationRemarkEmitter ORE(L.getHeader()->getParent());
 
   LoopInvariantCodeMotion LICM(LicmMssaOptCap, LicmMssaNoAccForPromotionCap);
-  if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, &AR.TLI, &AR.TTI, &AR.SE,
-                      AR.MSSA, &ORE))
+  if (!LICM.runOnLoop(&L, &AR.AA, &AR.LI, &AR.DT, AR.BFI, &AR.TLI, &AR.TTI,
+                      &AR.SE, AR.MSSA, &ORE))
     return PreservedAnalyses::all();
 
   auto PA = getLoopPassPreservedAnalyses();
 
   PA.preserve<DominatorTreeAnalysis>();
   PA.preserve<LoopAnalysis>();
   if (AR.MSSA)
     PA.preserve<MemorySSAAnalysis>();
 
   return PA;
 }
 
 char LegacyLICMPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",
                       false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LazyBFIPass)
 INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,
                     false)
 
 Pass *llvm::createLICMPass() { return new LegacyLICMPass(); }
 Pass *llvm::createLICMPass(unsigned LicmMssaOptCap,
                            unsigned LicmMssaNoAccForPromotionCap) {
   return new LegacyLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap);
 }
 
 /// Hoist expressions out of the specified loop. Note, alias info for inner
 /// loop is not preserved so it is not a good idea to run LICM multiple
 /// times on one loop.
 bool LoopInvariantCodeMotion::runOnLoop(
     Loop *L, AAResults *AA, LoopInfo *LI, DominatorTree *DT,
-    TargetLibraryInfo *TLI, TargetTransformInfo *TTI, ScalarEvolution *SE,
-    MemorySSA *MSSA, OptimizationRemarkEmitter *ORE) {
+    BlockFrequencyInfo *BFI, TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
+    ScalarEvolution *SE, MemorySSA *MSSA, OptimizationRemarkEmitter *ORE) {
   bool Changed = false;
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
   // If this loop has metadata indicating that LICM is not to be performed then
   // just exit.
   if (hasDisableLICMTransformsHint(L)) {
     return false;

llvm/lib/Transforms/Scalar/LoopDistribute.cpp

   auto &AA = AM.getResult<AAManager>(F);
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
 
   auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
   std::function<const LoopAccessInfo &(Loop &)> GetLAA =
       [&](Loop &L) -> const LoopAccessInfo & {
-    LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI, nullptr};
+    LoopStandardAnalysisResults AR = {AA,  AC,  DT,      LI,     SE,
+                                      TLI, TTI, nullptr, nullptr};
     return LAM.getResult<LoopAccessAnalysis>(L, AR);
   };
 
   bool Changed = runImpl(F, &LI, &DT, &SE, &ORE, GetLAA);
   if (!Changed)
     return PreservedAnalyses::all();
   PreservedAnalyses PA;
   PA.preserve<LoopAnalysis>();

llvm/lib/Transforms/Scalar/LoopLoadElimination.cpp

       &AM.getResult<BlockFrequencyAnalysis>(F) : nullptr;
   MemorySSA *MSSA = EnableMSSALoopDependency
                         ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA()
                         : nullptr;
 
   auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
   bool Changed = eliminateLoadsAcrossLoops(
       F, LI, DT, BFI, PSI, [&](Loop &L) -> const LoopAccessInfo & {
-        LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI, MSSA};
+        LoopStandardAnalysisResults AR = {AA,  AC,  DT,      LI,  SE,
+                                          TLI, TTI, nullptr, MSSA};
         return LAM.getResult<LoopAccessAnalysis>(L, AR);
       });
 
   if (!Changed)
     return PreservedAnalyses::all();
 
   PreservedAnalyses PA;
   return PA;
 }

llvm/lib/Transforms/Scalar/LoopUnswitch.cpp

 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/CodeMetrics.h"
 #include "llvm/Analysis/InstructionSimplify.h"
+#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
 #include "llvm/Analysis/LegacyDivergenceAnalysis.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/MustExecute.h"
 #include "llvm/Analysis/ScalarEvolution.h"
public:
     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
     bool processCurrentLoop();
     bool isUnreachableDueToPreviousUnswitching(BasicBlock *);
 
     /// This transformation requires natural loop information & requires that
     /// loop preheaders be inserted into the CFG.
     ///
     void getAnalysisUsage(AnalysisUsage &AU) const override {
+      // Lazy BFI and BPI are marked as preserved here so Loop Unswitching
+      // can remain part of the same loop pass as LICM
+      AU.addPreserved<LazyBlockFrequencyInfoPass>();
+      AU.addPreserved<LazyBranchProbabilityInfoPass>();
       AU.addRequired<AssumptionCacheTracker>();
       AU.addRequired<TargetTransformInfoWrapperPass>();
       if (EnableMSSALoopDependency) {
         AU.addRequired<MemorySSAWrapperPass>();
         AU.addPreserved<MemorySSAWrapperPass>();
       }
       if (HasBranchDivergence)
         AU.addRequired<LegacyDivergenceAnalysis>();

llvm/lib/Transforms/Utils/LoopVersioning.cpp

   auto &AA = AM.getResult<AAManager>(F);
   auto &AC = AM.getResult<AssumptionAnalysis>(F);
   MemorySSA *MSSA = EnableMSSALoopDependency
                         ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA()
                         : nullptr;
 
   auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
   auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
-    LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI, MSSA};
+    LoopStandardAnalysisResults AR = {AA,  AC,  DT,      LI,  SE,
+                                      TLI, TTI, nullptr, MSSA};
     return LAM.getResult<LoopAccessAnalysis>(L, AR);
   };
 
   if (runImpl(&LI, GetLAA, &DT, &SE))
     return PreservedAnalyses::none();
   return PreservedAnalyses::all();
 }
 } // namespace llvm

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

     auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
     MemorySSA *MSSA = EnableMSSALoopDependency
                           ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA()
                           : nullptr;
 
     auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
     std::function<const LoopAccessInfo &(Loop &)> GetLAA =
         [&](Loop &L) -> const LoopAccessInfo & {
-      LoopStandardAnalysisResults AR = {AA, AC, DT, LI, SE, TLI, TTI, MSSA};
+      LoopStandardAnalysisResults AR = {AA,  AC,  DT,      LI,  SE,
+                                        TLI, TTI, nullptr, MSSA};
       return LAM.getResult<LoopAccessAnalysis>(L, AR);
     };
     auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
     ProfileSummaryInfo *PSI =
         MAMProxy.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
     LoopVectorizeResult Result =
         runImpl(F, SE, LI, TTI, DT, BFI, &TLI, DB, AA, AC, GetLAA, ORE, PSI);
     if (!Result.MadeAnyChange)

llvm/test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
 ; CHECK-NEXT:         Memory SSA
+; CHECK-NEXT:         Lazy Branch Probability Analysis
+; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information

 ; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Scalar Evolution Analysis
+; CHECK-NEXT:         Lazy Branch Probability Analysis
+; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Aggressive Dead Code Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results

 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Memory SSA
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
 ; CHECK-NEXT:       Scalar Evolution Analysis
-; CHECK-NEXT:       Loop Pass Manager
-; CHECK-NEXT:         Loop Invariant Code Motion
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
+; CHECK-NEXT:       Loop Pass Manager
+; CHECK-NEXT:         Loop Invariant Code Motion
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Warn about non-applied transformations
 ; CHECK-NEXT:       Alignment from assumptions
 ; CHECK-NEXT:     Strip Unused Function Prototypes
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     Merge Duplicate Global Constants
 ; CHECK-NEXT:     Call Graph Profile
 ; CHECK-NEXT:       FunctionPass Manager

llvm/test/Other/opt-O3-pipeline-enable-matrix.ll

 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
 ; CHECK-NEXT:         Memory SSA
+; CHECK-NEXT:         Lazy Branch Probability Analysis
+; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information

 ; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Scalar Evolution Analysis
+; CHECK-NEXT:         Lazy Branch Probability Analysis
+; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Aggressive Dead Code Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results

 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Memory SSA
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
 ; CHECK-NEXT:       Scalar Evolution Analysis
-; CHECK-NEXT:       Loop Pass Manager
-; CHECK-NEXT:         Loop Invariant Code Motion
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
+; CHECK-NEXT:       Loop Pass Manager
+; CHECK-NEXT:         Loop Invariant Code Motion
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Warn about non-applied transformations
 ; CHECK-NEXT:       Alignment from assumptions
 ; CHECK-NEXT:     Strip Unused Function Prototypes
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     Merge Duplicate Global Constants
 ; CHECK-NEXT:     Call Graph Profile
 ; CHECK-NEXT:       FunctionPass Manager

llvm/test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
 ; CHECK-NEXT:         Memory SSA
+; CHECK-NEXT:         Lazy Branch Probability Analysis
+; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information

 ; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Scalar Evolution Analysis
+; CHECK-NEXT:         Lazy Branch Probability Analysis
+; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Aggressive Dead Code Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results

 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Memory SSA
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
 ; CHECK-NEXT:       Scalar Evolution Analysis
-; CHECK-NEXT:       Loop Pass Manager
-; CHECK-NEXT:         Loop Invariant Code Motion
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
+; CHECK-NEXT:       Loop Pass Manager
+; CHECK-NEXT:         Loop Invariant Code Motion
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Warn about non-applied transformations
 ; CHECK-NEXT:       Alignment from assumptions
 ; CHECK-NEXT:     Strip Unused Function Prototypes
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     Merge Duplicate Global Constants
 ; CHECK-NEXT:     Call Graph Profile
 ; CHECK-NEXT:       FunctionPass Manager

llvm/test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Rotate Loops
 ; CHECK-NEXT:         Memory SSA
+; CHECK-NEXT:         Lazy Branch Probability Analysis
+; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:           Unswitch loops
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information

 ; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Scalar Evolution Analysis
+; CHECK-NEXT:         Lazy Branch Probability Analysis
+; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Aggressive Dead Code Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results

 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Combine redundant instructions
 ; CHECK-NEXT:       Memory SSA
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
 ; CHECK-NEXT:       Scalar Evolution Analysis
-; CHECK-NEXT:       Loop Pass Manager
-; CHECK-NEXT:         Loop Invariant Code Motion
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
+; CHECK-NEXT:       Loop Pass Manager
+; CHECK-NEXT:         Loop Invariant Code Motion
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Warn about non-applied transformations
 ; CHECK-NEXT:       Alignment from assumptions
 ; CHECK-NEXT:     Strip Unused Function Prototypes
 ; CHECK-NEXT:     Dead Global Elimination
 ; CHECK-NEXT:     Merge Duplicate Global Constants
 ; CHECK-NEXT:     Call Graph Profile
 ; CHECK-NEXT:       FunctionPass Manager

llvm/unittests/Transforms/Scalar/LoopPassManagerTest.cpp

 //===- llvm/unittest/Analysis/LoopPassManagerTest.cpp - LPM tests ---------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
 #include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"

 
     // We need DominatorTreeAnalysis for LoopAnalysis.
     FAM.registerPass([&] { return DominatorTreeAnalysis(); });
     FAM.registerPass([&] { return LoopAnalysis(); });
     // We also allow loop passes to assume a set of other analyses and so need
     // those.
     FAM.registerPass([&] { return AAManager(); });
     FAM.registerPass([&] { return AssumptionAnalysis(); });
+    FAM.registerPass([&] { return BlockFrequencyAnalysis(); });
+    FAM.registerPass([&] { return BranchProbabilityAnalysis(); });
+    FAM.registerPass([&] { return PostDominatorTreeAnalysis(); });
     FAM.registerPass([&] { return MemorySSAAnalysis(); });
     FAM.registerPass([&] { return ScalarEvolutionAnalysis(); });
     FAM.registerPass([&] { return TargetLibraryAnalysis(); });
     FAM.registerPass([&] { return TargetIRAnalysis(); });
 
     // Register required pass instrumentation analysis.
     LAM.registerPass([&] { return PassInstrumentationAnalysis(); });
     FAM.registerPass([&] { return PassInstrumentationAnalysis(); });