[BFI] Add new LazyBFI analysis pass

[anemet]

Summary

[BFI] Add new LazyBFI analysis pass

This is necessary for D21771. In order to add the hotness attribute to
optimization remarks we need BFI to be available in all passes that emit
optimization remarks.

However we don't want to pay for computing BFI unless the hotness
attribute is requested.

This is achieved by making BFI lazy at the very high-level through a new
analysis pass -- BFI is not calculated unless requested.

I am adding a test to check the laziness under D21771 where the first
user of the analysis is added.

[davidxl]

There are already too many classes related to BFI, so I am not a fan of introducing another LazyBFI.

I suggest just making BFI lazy itself (when getBlockFreq() is first called ...). In fact I think the laziness handling should be in BlocFrequencyInfoImpl class. By so doing, MBFI can get the laziness automatically as well.

[dexonsmith]

David's suggested direction SGTM.

[anemet]

In D22141#478534, @davidxl wrote:

There are already too many classes related to BFI, so I am not a fan of introducing another LazyBFI.

I suggest just making BFI lazy itself (when getBlockFreq() is first called ...). In fact I think the laziness handling should be in BlocFrequencyInfoImpl class. By so doing, MBFI can get the laziness automatically as well.

Moving it to MBFI, SGTM but I don't think that forcing the calculation of the frequencies in getBlockFreq is sufficient.

So just to be clear, you're suggesting sprinkling around in the code like this:

if (!Calculated)
  calculate()

in getBlockFreq, getBlockProfileCount, setBlockFreq, getFloatingBlockFreq, print and printBlockFreq?

[anemet]

In D22141#478534, @davidxl wrote:

I suggest just making BFI lazy itself (when getBlockFreq() is first called ...). In fact I think the laziness handling should be in BlocFrequencyInfoImpl class. By so doing, MBFI can get the laziness automatically as well.

I've tried and unfortunately, I don't think this will work. I saw two issues:

a. LoopInfo is freed by the time block frequencies are requested

This can be fixed by making users of BFI also dependent on LI but that's an overkill for existing users

b. The pass starts modifying the CFG and when it tries to update the frequencies LI and the CFG are already inconsistent

I think that these issues (there maybe more) are difficult to fix in the context of existing BFI's users. My new proposal is to introduce a new analysis, LazyBFI. Then, new users could opt in by complying with LBFI's requirements:

1. require LI and BPI as well (I will add an 'required' enumerator)

2. compute BFI before making any CFG changes

The analysis would effectively consist of the LazyBFI class I had earlier. It will only cover IR BFI for now but we could later template-ize it to also work with BFI.

I talked with Duncan about this and he was fine with this idea. Let me know your thoughts.

Adam

[dexonsmith]

Just confirming my off-line conversation with Adam. LazyBFI needs a fundamentally different contract than the current BFI, and having clients opt-in seems right.

Long term: I imagine once the new pass manager is the one-true-way there could be a way to unify LazyBFI and BFI (it solves everything, right?), but I don't see how we could reasonably block improving optimization remarks on that.

[davidxl]

The idea of lazyBFI analysis sounds good to me. Need to see what the actual
patch look like :)

David

[anemet]

Expose LBFI as a new analysis pass.

Will also update the review description shortly.

[davidxl]

include/llvm/Analysis/LazyBlockFrequencyInfo.h

22 ↗

(On Diff #63738)

What is the use model for the new pass manager? Anything worth documenting?

91 ↗

(On Diff #63738)

Can the wrapper class of BFI be 'inlined' into this class so that we don't need LBFI ?

lib/Analysis/LazyBlockFrequencyInfo.cpp

38 ↗

(On Diff #63738)

Why not also implementing the new PM part of the support?

[anemet]

include/llvm/Analysis/LazyBlockFrequencyInfo.h

22 ↗

(On Diff #63738)

I am not sure we will need this class with the new PM. Correct me if I am wrong but I thought as long as the client does not call something like getResult<BlockFrequencyAnalysis>(F), the analysis won't be populated. This is not the case for the old PM.

I was going to play with this after this patch and post follow-on patches if anything is required for the new PM.

Since the vectorizer is converted now, I should be able to try it there.

91 ↗

(On Diff #63738)

It could certainly live nested in the pass, I would rather not remove it though; it nicely captures the single functionality it provides and the abstraction overhead should be removed by the compiler.

[anemet]

Addresses David's comment. Make LBFI private. Add comment about presumed
direction for new PM.

[davidxl]

lgtm

llvm/trunk/include/llvm/Analysis/BlockFrequencyInfo.h

 public:
   BlockFrequencyInfo();
   BlockFrequencyInfo(const Function &F, const BranchProbabilityInfo &BPI,
                      const LoopInfo &LI);
   BlockFrequencyInfo(BlockFrequencyInfo &&Arg);
 
   BlockFrequencyInfo &operator=(BlockFrequencyInfo &&RHS);
 
+  ~BlockFrequencyInfo();
+
   const Function *getFunction() const;
   const BranchProbabilityInfo *getBPI() const;
   void view() const;
 
   /// getblockFreq - Return block frequency. Return 0 if we don't have the
   /// information. Please note that initial frequency is equal to ENTRY_FREQ. It
   /// means that we should not rely on the value itself, but only on the
   /// comparison to the other block frequencies. We do this to avoid using of

llvm/trunk/include/llvm/Analysis/LazyBlockFrequencyInfo.h

+//===- LazyBlockFrequencyInfo.h - Lazy Block Frequency Analysis -*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.  The
+// difference is that with this pass the block frequencies are not computed when
+// the analysis pass is executed but rather when the BFI results is explicitly
+// requested by the analysis client.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_LAZYBLOCKFREQUENCYINFO_H
+#define LLVM_ANALYSIS_LAZYBLOCKFREQUENCYINFO_H
+
+#include "llvm/Analysis/BlockFrequencyInfo.h"
+#include "llvm/Pass.h"
+
+namespace llvm {
+class AnalysisUsage;
+class BranchProbabilityInfo;
+class Function;
+class LoopInfo;
+
+/// \brief This is an alternative analysis pass to
+/// BlockFrequencyInfoWrapperPass.  The difference is that with this pass the
+/// block frequencies are not computed when the analysis pass is executed but
+/// rather when the BFI results is explicitly requested by the analysis client.
+///
+/// There are some additional requirements for any client pass that wants to use
+/// the analysis:
+///
+/// 1. The pass needs to initialize dependent passes with:
+///
+///   INITIALIZE_PASS_DEPENDENCY(LazyBFIPass)
+///
+/// 2. Similarly, getAnalysisUsage should call:
+///
+///   LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU)
+///
+/// 3. The computed BFI should be requested with
+///    getAnalysis<LazyBlockFrequencyInfoPass>().getBFI() before either LoopInfo
+///    or BPI could be invalidated for example by changing the CFG.
+///
+/// Note that it is expected that we wouldn't need this functionality for the
+/// new PM since with the new PM, analyses are executed on demand.
+class LazyBlockFrequencyInfoPass : public FunctionPass {
+
+  /// Wraps a BFI to allow lazy computation of the block frequencies.
+  ///
+  /// A pass that only conditionally uses BFI can uncondtionally require the
+  /// analysis without paying for the overhead if BFI doesn't end up being used.
+  class LazyBlockFrequencyInfo {
+  public:
+    LazyBlockFrequencyInfo()
+        : Calculated(false), F(nullptr), BPI(nullptr), LI(nullptr) {}
+
+    /// Set up the per-function input.
+    void setAnalysis(const Function *F, const BranchProbabilityInfo *BPI,
+                     const LoopInfo *LI) {
+      this->F = F;
+      this->BPI = BPI;
+      this->LI = LI;
+    }
+
+    /// Retrieve the BFI with the block frequencies computed.
+    BlockFrequencyInfo &getCalculated() {
+      if (!Calculated) {
+        assert(F && BPI && LI && "call setAnalysis");
+        BFI.calculate(*F, *BPI, *LI);
+        Calculated = true;
+      }
+      return BFI;
+    }
+
+    const BlockFrequencyInfo &getCalculated() const {
+      return const_cast<LazyBlockFrequencyInfo *>(this)->getCalculated();
+    }
+
+    void releaseMemory() {
+      BFI.releaseMemory();
+      Calculated = false;
+      setAnalysis(nullptr, nullptr, nullptr);
+    }
+
+  private:
+    BlockFrequencyInfo BFI;
+    bool Calculated;
+    const Function *F;
+    const BranchProbabilityInfo *BPI;
+    const LoopInfo *LI;
+  };
+
+  LazyBlockFrequencyInfo LBFI;
+
+public:
+  static char ID;
+
+  LazyBlockFrequencyInfoPass();
+
+  /// \brief Compute and return the block frequencies.
+  BlockFrequencyInfo &getBFI() { return LBFI.getCalculated(); }
+
+  /// \brief Compute and return the block frequencies.
+  const BlockFrequencyInfo &getBFI() const { return LBFI.getCalculated(); }
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+
+  /// Helper for client passes to set up the analysis usage on behalf of this
+  /// pass.
+  static void getLazyBFIAnalysisUsage(AnalysisUsage &AU);
+
+  bool runOnFunction(Function &F) override;
+  void releaseMemory() override;
+  void print(raw_ostream &OS, const Module *M) const override;
+};
+
+/// \brief Helper for client passes to initialize dependent passes for LBFI.
+void initializeLazyBFIPassPass(PassRegistry &Registry);
+}
+#endif

llvm/trunk/include/llvm/InitializePasses.h

 void initializeInstrProfilingLegacyPassPass(PassRegistry &);
 void initializeInstructionCombiningPassPass(PassRegistry&);
 void initializeInterleavedAccessPass(PassRegistry &);
 void initializeInternalizeLegacyPassPass(PassRegistry&);
 void initializeIntervalPartitionPass(PassRegistry&);
 void initializeJumpThreadingPass(PassRegistry&);
 void initializeLCSSAWrapperPassPass(PassRegistry &);
 void initializeLegacyLICMPassPass(PassRegistry&);
+void initializeLazyBlockFrequencyInfoPassPass(PassRegistry&);
 void initializeLazyValueInfoWrapperPassPass(PassRegistry&);
 void initializeLintPass(PassRegistry&);
 void initializeLiveDebugValuesPass(PassRegistry&);
 void initializeLiveDebugVariablesPass(PassRegistry&);
 void initializeLiveIntervalsPass(PassRegistry&);
 void initializeLiveRegMatrixPass(PassRegistry&);
 void initializeLiveStacksPass(PassRegistry&);
 void initializeLiveVariablesPass(PassRegistry&);

llvm/trunk/lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializePostDomPrinterPass(Registry);
   initializePostDomOnlyViewerPass(Registry);
   initializePostDomOnlyPrinterPass(Registry);
   initializeAAResultsWrapperPassPass(Registry);
   initializeGlobalsAAWrapperPassPass(Registry);
   initializeIVUsersPass(Registry);
   initializeInstCountPass(Registry);
   initializeIntervalPartitionPass(Registry);
+  initializeLazyBlockFrequencyInfoPassPass(Registry);
   initializeLazyValueInfoWrapperPassPass(Registry);
   initializeLintPass(Registry);
   initializeLoopInfoWrapperPassPass(Registry);
   initializeMemDepPrinterPass(Registry);
   initializeMemDerefPrinterPass(Registry);
   initializeMemoryDependenceWrapperPassPass(Registry);
   initializeModuleDebugInfoPrinterPass(Registry);
   initializeModuleSummaryIndexWrapperPassPass(Registry);

llvm/trunk/lib/Analysis/BlockFrequencyInfo.cpp

BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)
     : BFI(std::move(Arg.BFI)) {}
 
 BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {
   releaseMemory();
   BFI = std::move(RHS.BFI);
   return *this;
 }
 
+// Explicitly define the default constructor otherwise it would be implicitly
+// defined at the first ODR-use which is the BFI member in the
+// LazyBlockFrequencyInfo header.  The dtor needs the BlockFrequencyInfoImpl
+// template instantiated which is not available in the header.
+BlockFrequencyInfo::~BlockFrequencyInfo() {}
+
 void BlockFrequencyInfo::calculate(const Function &F,
                                    const BranchProbabilityInfo &BPI,
                                    const LoopInfo &LI) {
   if (!BFI)
     BFI.reset(new ImplType);
   BFI->calculate(F, BPI, LI);
 #ifndef NDEBUG
   if (ViewBlockFreqPropagationDAG != GVDT_None &&

llvm/trunk/lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   IVUsers.cpp
   IndirectCallPromotionAnalysis.cpp
   InlineCost.cpp
   InstCount.cpp
   InstructionSimplify.cpp
   Interval.cpp
   IntervalPartition.cpp
   IteratedDominanceFrontier.cpp
+  LazyBlockFrequencyInfo.cpp
   LazyCallGraph.cpp
   LazyValueInfo.cpp
   Lint.cpp
   Loads.cpp
   LoopAccessAnalysis.cpp
   LoopUnrollAnalyzer.cpp
   LoopInfo.cpp
   LoopPass.cpp

llvm/trunk/lib/Analysis/LazyBlockFrequencyInfo.cpp

+//===- LazyBlockFrequencyInfo.cpp - Lazy Block Frequency Analysis ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This is an alternative analysis pass to BlockFrequencyInfoWrapperPass.  The
+// difference is that with this pass the block frequencies are not computed when
+// the analysis pass is executed but rather when the BFI results is explicitly
+// requested by the analysis client.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
+#include "llvm/Analysis/BranchProbabilityInfo.h"
+#include "llvm/Analysis/LoopInfo.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "lazy-block-freq"
+
+INITIALIZE_PASS_BEGIN(LazyBlockFrequencyInfoPass, DEBUG_TYPE,
+                      "Lazy Block Frequency Analysis", true, true)
+INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_END(LazyBlockFrequencyInfoPass, DEBUG_TYPE,
+                    "Lazy Block Frequency Analysis", true, true)
+
+char LazyBlockFrequencyInfoPass::ID = 0;
+
+LazyBlockFrequencyInfoPass::LazyBlockFrequencyInfoPass() : FunctionPass(ID) {
+  initializeLazyBlockFrequencyInfoPassPass(*PassRegistry::getPassRegistry());
+}
+
+void LazyBlockFrequencyInfoPass::print(raw_ostream &OS, const Module *) const {
+  LBFI.getCalculated().print(OS);
+}
+
+void LazyBlockFrequencyInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<BranchProbabilityInfoWrapperPass>();
+  AU.addRequired<LoopInfoWrapperPass>();
+  AU.setPreservesAll();
+}
+
+void LazyBlockFrequencyInfoPass::releaseMemory() { LBFI.releaseMemory(); }
+
+bool LazyBlockFrequencyInfoPass::runOnFunction(Function &F) {
+  BranchProbabilityInfo &BPI =
+      getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
+  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
+  LBFI.setAnalysis(&F, &BPI, &LI);
+  return false;
+}
+
+void LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AnalysisUsage &AU) {
+  AU.addRequired<BranchProbabilityInfoWrapperPass>();
+  AU.addRequired<LazyBlockFrequencyInfoPass>();
+  AU.addRequired<LoopInfoWrapperPass>();
+}
+
+void llvm::initializeLazyBFIPassPass(PassRegistry &Registry) {
+  INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass);
+  INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass);
+  INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
+}

llvm/trunk/test/Analysis/BlockFrequencyInfo/basic.ll

 ; RUN: opt < %s -analyze -block-freq | FileCheck %s
+; RUN: opt < %s -analyze -lazy-block-freq | FileCheck %s
 ; RUN: opt < %s -passes='print<block-freq>' -disable-output 2>&1 | FileCheck %s
 
 define i32 @test1(i32 %i, i32* %a) {
 ; CHECK-LABEL: Printing analysis {{.*}} for function 'test1':
 ; CHECK-NEXT: block-frequency-info: test1
 ; CHECK-NEXT: entry: float = 1.0, int = [[ENTRY:[0-9]+]]
 entry:
   br label %body