[LazyMachineBFI] Reimplement with getAnalysisIfAvailable

[anemet]

Summary

Since LoopInfo is not available in machine passes as universally as in IR
passes, using the same approach for OptimizationRemarkEmitter as we did for IR
will run LoopInfo and DominatorTree unnecessarily. (LoopInfo is not used
lazily by ORE.)

To fix this, I am modifying the approach I took in D29836. LazyMachineBFI now
uses its client passes including MachineBFI itself that are available or
otherwise compute them on the fly.

So for example the GreedyRegAlloc since it's already using MBFI will reuse
that instance. On the other hand, AsmPrinter in Justin's patch will generate
DT, LI and finally BFI on the fly.

(I am of course wondering now if the simplicity of this approach is even
preferable in IR. I will do some experiments.)

Testing is provided by an updated version of D29837 which requires Justin's
patch to bring ORE to the AsmPrinter.

[davide]

What's the compile time savings you're seeing from not computing these analyses unnecessarily?

Side rant: I think some of the names in LLVM are really poorly chosen, DominatorTree in fact is not an analysis but the result of an analysis.

[anemet]

In D30128#680739, @davide wrote:

What's the compile time savings you're seeing from not computing these analyses unnecessarily?

This would be hard to measure for the machine passes since GreedyRegAlloc already uses MachineLoopInfo. This was more of a precaution for the machine passes at this point. But I can try to measure this when I look at the IR passes.

Side rant: I think some of the names in LLVM are really poorly chosen, DominatorTree in fact is not an analysis but the result of an analysis.

Agreed and then in both MachineLoopInfo and MachineDT, we go out of our way to pretend that the pass has the same APIs as the result. Very confusing.

[davidxl]

Is there a need to keep LazyBlockFrequencyInfo as a template class after this change?

include/llvm/CodeGen/MachineBlockFrequencyInfo.h

41

Is there a need for this helper -- it is used only in one place. Just construct one and call calculate?

lib/CodeGen/LazyMachineBlockFrequencyInfo.cpp

61

Set MBPI here too?

[anemet]

In D30128#682495, @davidxl wrote:

Is there a need to keep LazyBlockFrequencyInfo as a template class after this change?

No. I'd like to evaluate if we want to use the same approach as this in LBFI (do you have any opinion on this?) and if yes, the entire class can go.

[anemet]

Address David's comments.

[anemet]

Hi David, is this looking good to you now? Sorry to push but Justin's change is blocked by this. Thanks!!

[davidxl]

lgtm

[anemet]

Thanks, David!

include/llvm/CodeGen/LazyMachineBlockFrequencyInfo.h

 ///===---------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_LAZYMACHINEBLOCKFREQUENCYINFO_H
 #define LLVM_ANALYSIS_LAZYMACHINEBLOCKFREQUENCYINFO_H
 
 #include "llvm/Analysis/LazyBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
+#include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 
 namespace llvm {
 /// \brief This is an alternative analysis pass to MachineBlockFrequencyInfo.
 /// The difference is that with this pass, the block frequencies are not
 /// computed when the analysis pass is executed but rather when the BFI result
 /// 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(LazyMachineBFIPass)
-///
-/// 2. Similarly, getAnalysisUsage should call:
-///
-///   LazyMachineBlockFrequencyInfoPass::getLazyMachineBFIAnalysisUsage(AU)
-///
-/// 3. The computed MachineBFI should be requested with
-///    getAnalysis<LazyMachineBlockFrequencyInfoPass>().getBFI() before
-///    MachineLoopInfo could be invalidated for example by changing the CFG.
+/// This works by checking querying if MBFI is available and otherwise
+/// generating MBFI on the fly.  In this case the passes required for (LI, DT)
+/// are also queried before being computed on the fly.
 ///
 /// 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 LazyMachineBlockFrequencyInfoPass : public MachineFunctionPass {
 private:
-  /// \brief Machine BPI is an immutable pass, no need to use it lazily.
-  LazyBlockFrequencyInfo<MachineFunction, MachineBranchProbabilityInfo,
-                         MachineLoopInfo, MachineBlockFrequencyInfo>
-      LMBFI;
+  /// If generated on the fly this own the instance.
+  mutable std::unique_ptr<MachineBlockFrequencyInfo> OwnedMBFI;
+
+  /// If generated on the fly this own the instance.
+  mutable std::unique_ptr<MachineLoopInfo> OwnedMLI;
+
+  /// If generated on the fly this own the instance.
+  mutable std::unique_ptr<MachineDominatorTree> OwnedMDT;
+
+  /// MBPI analysis which is immutable.
+  MachineBranchProbabilityInfo *MBPI = nullptr;
+
+  /// The function.
+  MachineFunction *MF = nullptr;
+
+  /// \brief Calculate MBFI and all other analyses that's not available and
+  /// required by BFI.
+  MachineBlockFrequencyInfo &calculateIfNotAvailable() const;
 
 public:
   static char ID;
 
   LazyMachineBlockFrequencyInfoPass();
 
   /// \brief Compute and return the block frequencies.
-  MachineBlockFrequencyInfo &getBFI() { return LMBFI.getCalculated(); }
+  MachineBlockFrequencyInfo &getBFI() { return calculateIfNotAvailable(); }
 
   /// \brief Compute and return the block frequencies.
   const MachineBlockFrequencyInfo &getBFI() const {
-    return LMBFI.getCalculated();
+    return calculateIfNotAvailable();
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
-  /// Helper for client passes to set up the analysis usage on behalf of this
-  /// pass.
-  static void getLazyMachineBFIAnalysisUsage(AnalysisUsage &AU);
-
   bool runOnMachineFunction(MachineFunction &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 LMBFI.
-void initializeLazyMachineBFIPassPass(PassRegistry &Registry);
 }
 #endif

include/llvm/CodeGen/MachineBlockFrequencyInfo.h

class MachineBlockFrequencyInfo : public MachineFunctionPass {
   typedef BlockFrequencyInfoImpl<MachineBasicBlock> ImplType;
   std::unique_ptr<ImplType> MBFI;
 
 public:
   static char ID;
 
   MachineBlockFrequencyInfo();
 
+  /// Construct and also populate BFI.
+  MachineBlockFrequencyInfo(MachineFunction &MF,
+                            MachineBranchProbabilityInfo &MBPI,
+                            MachineLoopInfo &MLI);
+
   ~MachineBlockFrequencyInfo() override;
 
   void getAnalysisUsage(AnalysisUsage &AU) const override;
 
   bool runOnMachineFunction(MachineFunction &F) override;
 
   /// calculate - compute block frequency info for the given function.
   void calculate(const MachineFunction &F,

lib/CodeGen/LazyMachineBlockFrequencyInfo.cpp

 LazyMachineBlockFrequencyInfoPass::LazyMachineBlockFrequencyInfoPass()
     : MachineFunctionPass(ID) {
   initializeLazyMachineBlockFrequencyInfoPassPass(
       *PassRegistry::getPassRegistry());
 }
 
 void LazyMachineBlockFrequencyInfoPass::print(raw_ostream &OS,
                                               const Module *M) const {
-  LMBFI.getCalculated().print(OS, M);
+  getBFI().print(OS, M);
 }
 
 void LazyMachineBlockFrequencyInfoPass::getAnalysisUsage(
     AnalysisUsage &AU) const {
   AU.addRequired<MachineBranchProbabilityInfo>();
-  AU.addRequired<MachineLoopInfo>();
   AU.setPreservesAll();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 void LazyMachineBlockFrequencyInfoPass::releaseMemory() {
-  LMBFI.releaseMemory();
+  MBPI = nullptr;
+  OwnedMBFI.reset();
+  OwnedMLI.reset();
+  OwnedMDT.reset();
+}
+
+MachineBlockFrequencyInfo &
+LazyMachineBlockFrequencyInfoPass::calculateIfNotAvailable() const {
+  auto *MBFI = getAnalysisIfAvailable<MachineBlockFrequencyInfo>();
+  if (MBFI) {
+    DEBUG(dbgs() << "MachineBlockFrequencyInfo is available\n");
+    return *MBFI;
+  }
+  auto *MLI = getAnalysisIfAvailable<MachineLoopInfo>();
+  auto *MDT = getAnalysisIfAvailable<MachineDominatorTree>();
+  DEBUG(dbgs() << "Building MachineBlockFrequencyInfo on the fly\n");
+  DEBUG(if (MLI) dbgs() << "LoopInfo is available\n");
+
+  if (!MLI) {
+    DEBUG(dbgs() << "Building LoopInfo on the fly\n");
+    // First create a dominator tree.
+    DEBUG(if (MDT) dbgs() << "DominatorTree is available\n");
+
+    if (!MDT) {
+      DEBUG(dbgs() << "Building DominatorTree on the fly\n");
+      OwnedMDT = make_unique<MachineDominatorTree>();
+      OwnedMDT->getBase().recalculate(*MF);
+      MDT = OwnedMDT.get();
+    }
+
+    // Generate LoopInfo from it.
+    OwnedMLI = make_unique<MachineLoopInfo>();
+    OwnedMLI->getBase().analyze(MDT->getBase());
+    MLI = OwnedMLI.get();
   }
 
-bool LazyMachineBlockFrequencyInfoPass::runOnMachineFunction(
-    MachineFunction &MF) {
-  auto &BPIPass = getAnalysis<MachineBranchProbabilityInfo>();
-  auto &LI = getAnalysis<MachineLoopInfo>();
-  LMBFI.setAnalysis(&MF, &BPIPass, &LI);
-  return false;
+  OwnedMBFI = make_unique<MachineBlockFrequencyInfo>(*MF, *MBPI, *MLI);
+  return *OwnedMBFI.get();
 }
 
-void LazyMachineBlockFrequencyInfoPass::getLazyMachineBFIAnalysisUsage(
-    AnalysisUsage &AU) {
-  AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
-  AU.addRequired<MachineBranchProbabilityInfo>();
-  AU.addRequired<MachineLoopInfo>();
-}
-
-void llvm::initializeLazyMachineBFIPassPass(PassRegistry &Registry) {
-  INITIALIZE_PASS_DEPENDENCY(LazyMachineBlockFrequencyInfoPass);
-  INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo);
-  INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo);
+bool LazyMachineBlockFrequencyInfoPass::runOnMachineFunction(
+    MachineFunction &F) {
+  MF = &F;
+  MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
+  return false;
 }

lib/CodeGen/MachineBlockFrequencyInfo.cpp

 
 char MachineBlockFrequencyInfo::ID = 0;
 
 MachineBlockFrequencyInfo::MachineBlockFrequencyInfo()
     : MachineFunctionPass(ID) {
   initializeMachineBlockFrequencyInfoPass(*PassRegistry::getPassRegistry());
 }
 
+MachineBlockFrequencyInfo::MachineBlockFrequencyInfo(
+    MachineFunction &MF, MachineBranchProbabilityInfo &MBPI,
+    MachineLoopInfo &MLI)
+    : MachineFunctionPass(ID) {
+  calculate(MF, MBPI, MLI);
+}
+
 MachineBlockFrequencyInfo::~MachineBlockFrequencyInfo() {}
 
 void MachineBlockFrequencyInfo::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.addRequired<MachineBranchProbabilityInfo>();
   AU.addRequired<MachineLoopInfo>();
   AU.setPreservesAll();
   MachineFunctionPass::getAnalysisUsage(AU);
 }

lib/CodeGen/MachineOptimizationRemarkEmitter.cpp

else
     MBFI = nullptr;
 
   ORE = llvm::make_unique<MachineOptimizationRemarkEmitter>(MF, MBFI);
   return false;
 }
 
 void MachineOptimizationRemarkEmitterPass::getAnalysisUsage(
     AnalysisUsage &AU) const {
-  LazyMachineBlockFrequencyInfoPass::getLazyMachineBFIAnalysisUsage(AU);
+  AU.addRequired<LazyMachineBlockFrequencyInfoPass>();
   AU.setPreservesAll();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 char MachineOptimizationRemarkEmitterPass::ID = 0;
 static const char ore_name[] = "Machine Optimization Remark Emitter";
 #define ORE_NAME "machine-opt-remark-emitter"
 
 INITIALIZE_PASS_BEGIN(MachineOptimizationRemarkEmitterPass, ORE_NAME, ore_name,
                       false, true)
-INITIALIZE_PASS_DEPENDENCY(LazyMachineBFIPass)
+INITIALIZE_PASS_DEPENDENCY(LazyMachineBlockFrequencyInfoPass)
 INITIALIZE_PASS_END(MachineOptimizationRemarkEmitterPass, ORE_NAME, ore_name,
                     false, true)