Home | History | Annotate | Line # | Download | only in Analysis 
      1 //===- BlockFrequencyInfo.h - Block Frequency Analysis ----------*- C++ -*-===//
      2 //
      3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
      4 // See https://llvm.org/LICENSE.txt for license information.
      5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
      6 //
      7 //===----------------------------------------------------------------------===//
      8 //
      9 // Loops should be simplified before this analysis.
     10 //
     11 //===----------------------------------------------------------------------===//
     12 
     13 #ifndef LLVM_ANALYSIS_BLOCKFREQUENCYINFO_H
     14 #define LLVM_ANALYSIS_BLOCKFREQUENCYINFO_H
     15 
     16 #include "llvm/ADT/Optional.h"
     17 #include "llvm/IR/PassManager.h"
     18 #include "llvm/Pass.h"
     19 #include "llvm/Support/BlockFrequency.h"
     20 #include <cstdint>
     21 #include <memory>
     22 
     23 namespace llvm {
     24 
     25 class BasicBlock;
     26 class BranchProbabilityInfo;
     27 class Function;
     28 class LoopInfo;
     29 class Module;
     30 class raw_ostream;
     31 template <class BlockT> class BlockFrequencyInfoImpl;
     32 
     33 enum PGOViewCountsType { PGOVCT_None, PGOVCT_Graph, PGOVCT_Text };
     34 
     35 /// BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to
     36 /// estimate IR basic block frequencies.
     37 class BlockFrequencyInfo {
     38   using ImplType = BlockFrequencyInfoImpl<BasicBlock>;
     39 
     40   std::unique_ptr<ImplType> BFI;
     41 
     42 public:
     43   BlockFrequencyInfo();
     44   BlockFrequencyInfo(const Function &F, const BranchProbabilityInfo &BPI,
     45                      const LoopInfo &LI);
     46   BlockFrequencyInfo(const BlockFrequencyInfo &) = delete;
     47   BlockFrequencyInfo &operator=(const BlockFrequencyInfo &) = delete;
     48   BlockFrequencyInfo(BlockFrequencyInfo &&Arg);
     49   BlockFrequencyInfo &operator=(BlockFrequencyInfo &&RHS);
     50   ~BlockFrequencyInfo();
     51 
     52   /// Handle invalidation explicitly.
     53   bool invalidate(Function &F, const PreservedAnalyses &PA,
     54                   FunctionAnalysisManager::Invalidator &);
     55 
     56   const Function *getFunction() const;
     57   const BranchProbabilityInfo *getBPI() const;
     58   void view(StringRef = "BlockFrequencyDAGs") const;
     59 
     60   /// getblockFreq - Return block frequency. Return 0 if we don't have the
     61   /// information. Please note that initial frequency is equal to ENTRY_FREQ. It
     62   /// means that we should not rely on the value itself, but only on the
     63   /// comparison to the other block frequencies. We do this to avoid using of
     64   /// floating points.
     65   BlockFrequency getBlockFreq(const BasicBlock *BB) const;
     66 
     67   /// Returns the estimated profile count of \p BB.
     68   /// This computes the relative block frequency of \p BB and multiplies it by
     69   /// the enclosing function's count (if available) and returns the value.
     70   Optional<uint64_t> getBlockProfileCount(const BasicBlock *BB,
     71                                           bool AllowSynthetic = false) const;
     72 
     73   /// Returns the estimated profile count of \p Freq.
     74   /// This uses the frequency \p Freq and multiplies it by
     75   /// the enclosing function's count (if available) and returns the value.
     76   Optional<uint64_t> getProfileCountFromFreq(uint64_t Freq) const;
     77 
     78   /// Returns true if \p BB is an irreducible loop header
     79   /// block. Otherwise false.
     80   bool isIrrLoopHeader(const BasicBlock *BB);
     81 
     82   // Set the frequency of the given basic block.
     83   void setBlockFreq(const BasicBlock *BB, uint64_t Freq);
     84 
     85   /// Set the frequency of \p ReferenceBB to \p Freq and scale the frequencies
     86   /// of the blocks in \p BlocksToScale such that their frequencies relative
     87   /// to \p ReferenceBB remain unchanged.
     88   void setBlockFreqAndScale(const BasicBlock *ReferenceBB, uint64_t Freq,
     89                             SmallPtrSetImpl<BasicBlock *> &BlocksToScale);
     90 
     91   /// calculate - compute block frequency info for the given function.
     92   void calculate(const Function &F, const BranchProbabilityInfo &BPI,
     93                  const LoopInfo &LI);
     94 
     95   // Print the block frequency Freq to OS using the current functions entry
     96   // frequency to convert freq into a relative decimal form.
     97   raw_ostream &printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const;
     98 
     99   // Convenience method that attempts to look up the frequency associated with
    100   // BB and print it to OS.
    101   raw_ostream &printBlockFreq(raw_ostream &OS, const BasicBlock *BB) const;
    102 
    103   uint64_t getEntryFreq() const;
    104   void releaseMemory();
    105   void print(raw_ostream &OS) const;
    106 
    107   // Compare to the other BFI and verify they match.
    108   void verifyMatch(BlockFrequencyInfo &Other) const;
    109 };
    110 
    111 /// Analysis pass which computes \c BlockFrequencyInfo.
    112 class BlockFrequencyAnalysis
    113     : public AnalysisInfoMixin<BlockFrequencyAnalysis> {
    114   friend AnalysisInfoMixin<BlockFrequencyAnalysis>;
    115 
    116   static AnalysisKey Key;
    117 
    118 public:
    119   /// Provide the result type for this analysis pass.
    120   using Result = BlockFrequencyInfo;
    121 
    122   /// Run the analysis pass over a function and produce BFI.
    123   Result run(Function &F, FunctionAnalysisManager &AM);
    124 };
    125 
    126 /// Printer pass for the \c BlockFrequencyInfo results.
    127 class BlockFrequencyPrinterPass
    128     : public PassInfoMixin<BlockFrequencyPrinterPass> {
    129   raw_ostream &OS;
    130 
    131 public:
    132   explicit BlockFrequencyPrinterPass(raw_ostream &OS) : OS(OS) {}
    133 
    134   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
    135 };
    136 
    137 /// Legacy analysis pass which computes \c BlockFrequencyInfo.
    138 class BlockFrequencyInfoWrapperPass : public FunctionPass {
    139   BlockFrequencyInfo BFI;
    140 
    141 public:
    142   static char ID;
    143 
    144   BlockFrequencyInfoWrapperPass();
    145   ~BlockFrequencyInfoWrapperPass() override;
    146 
    147   BlockFrequencyInfo &getBFI() { return BFI; }
    148   const BlockFrequencyInfo &getBFI() const { return BFI; }
    149 
    150   void getAnalysisUsage(AnalysisUsage &AU) const override;
    151 
    152   bool runOnFunction(Function &F) override;
    153   void releaseMemory() override;
    154   void print(raw_ostream &OS, const Module *M) const override;
    155 };
    156 
    157 } // end namespace llvm
    158 
    159 #endif // LLVM_ANALYSIS_BLOCKFREQUENCYINFO_H
    160