BlockFrequencyInfo.cpp 9.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267
  1. //===- BlockFrequencyInfo.cpp - Block Frequency Analysis ------------------===//
  2. //
  3. // The LLVM Compiler Infrastructure
  4. //
  5. // This file is distributed under the University of Illinois Open Source
  6. // License. See LICENSE.TXT for details.
  7. //
  8. //===----------------------------------------------------------------------===//
  9. //
  10. // Loops should be simplified before this analysis.
  11. //
  12. //===----------------------------------------------------------------------===//
  13. #include "llvm/Analysis/BlockFrequencyInfo.h"
  14. #include "llvm/Analysis/BlockFrequencyInfoImpl.h"
  15. #include "llvm/Analysis/BranchProbabilityInfo.h"
  16. #include "llvm/Analysis/LoopInfo.h"
  17. #include "llvm/Analysis/Passes.h"
  18. #include "llvm/IR/CFG.h"
  19. #include "llvm/InitializePasses.h"
  20. #include "llvm/Support/CommandLine.h"
  21. #include "llvm/Support/Debug.h"
  22. #include "llvm/Support/GraphWriter.h"
  23. using namespace llvm;
  24. #define DEBUG_TYPE "block-freq"
  25. #ifndef NDEBUG
  26. static cl::opt<GVDAGType> ViewBlockFreqPropagationDAG(
  27. "view-block-freq-propagation-dags", cl::Hidden,
  28. cl::desc("Pop up a window to show a dag displaying how block "
  29. "frequencies propagation through the CFG."),
  30. cl::values(clEnumValN(GVDT_None, "none", "do not display graphs."),
  31. clEnumValN(GVDT_Fraction, "fraction",
  32. "display a graph using the "
  33. "fractional block frequency representation."),
  34. clEnumValN(GVDT_Integer, "integer",
  35. "display a graph using the raw "
  36. "integer fractional block frequency representation."),
  37. clEnumValN(GVDT_Count, "count", "display a graph using the real "
  38. "profile count if available."),
  39. clEnumValEnd));
  40. cl::opt<std::string>
  41. ViewBlockFreqFuncName("view-bfi-func-name", cl::Hidden,
  42. cl::desc("The option to specify "
  43. "the name of the function "
  44. "whose CFG will be displayed."));
  45. cl::opt<unsigned>
  46. ViewHotFreqPercent("view-hot-freq-percent", cl::init(10), cl::Hidden,
  47. cl::desc("An integer in percent used to specify "
  48. "the hot blocks/edges to be displayed "
  49. "in red: a block or edge whose frequency "
  50. "is no less than the max frequency of the "
  51. "function multiplied by this percent."));
  52. namespace llvm {
  53. template <>
  54. struct GraphTraits<BlockFrequencyInfo *> {
  55. typedef const BasicBlock NodeType;
  56. typedef succ_const_iterator ChildIteratorType;
  57. typedef Function::const_iterator nodes_iterator;
  58. static inline const NodeType *getEntryNode(const BlockFrequencyInfo *G) {
  59. return &G->getFunction()->front();
  60. }
  61. static ChildIteratorType child_begin(const NodeType *N) {
  62. return succ_begin(N);
  63. }
  64. static ChildIteratorType child_end(const NodeType *N) {
  65. return succ_end(N);
  66. }
  67. static nodes_iterator nodes_begin(const BlockFrequencyInfo *G) {
  68. return G->getFunction()->begin();
  69. }
  70. static nodes_iterator nodes_end(const BlockFrequencyInfo *G) {
  71. return G->getFunction()->end();
  72. }
  73. };
  74. typedef BFIDOTGraphTraitsBase<BlockFrequencyInfo, BranchProbabilityInfo>
  75. BFIDOTGTraitsBase;
  76. template <>
  77. struct DOTGraphTraits<BlockFrequencyInfo *> : public BFIDOTGTraitsBase {
  78. explicit DOTGraphTraits(bool isSimple = false)
  79. : BFIDOTGTraitsBase(isSimple) {}
  80. std::string getNodeLabel(const BasicBlock *Node,
  81. const BlockFrequencyInfo *Graph) {
  82. return BFIDOTGTraitsBase::getNodeLabel(Node, Graph,
  83. ViewBlockFreqPropagationDAG);
  84. }
  85. std::string getNodeAttributes(const BasicBlock *Node,
  86. const BlockFrequencyInfo *Graph) {
  87. return BFIDOTGTraitsBase::getNodeAttributes(Node, Graph,
  88. ViewHotFreqPercent);
  89. }
  90. std::string getEdgeAttributes(const BasicBlock *Node, EdgeIter EI,
  91. const BlockFrequencyInfo *BFI) {
  92. return BFIDOTGTraitsBase::getEdgeAttributes(Node, EI, BFI, BFI->getBPI(),
  93. ViewHotFreqPercent);
  94. }
  95. };
  96. } // end namespace llvm
  97. #endif
  98. BlockFrequencyInfo::BlockFrequencyInfo() {}
  99. BlockFrequencyInfo::BlockFrequencyInfo(const Function &F,
  100. const BranchProbabilityInfo &BPI,
  101. const LoopInfo &LI) {
  102. calculate(F, BPI, LI);
  103. }
  104. BlockFrequencyInfo::BlockFrequencyInfo(BlockFrequencyInfo &&Arg)
  105. : BFI(std::move(Arg.BFI)) {}
  106. BlockFrequencyInfo &BlockFrequencyInfo::operator=(BlockFrequencyInfo &&RHS) {
  107. releaseMemory();
  108. BFI = std::move(RHS.BFI);
  109. return *this;
  110. }
  111. // Explicitly define the default constructor otherwise it would be implicitly
  112. // defined at the first ODR-use which is the BFI member in the
  113. // LazyBlockFrequencyInfo header. The dtor needs the BlockFrequencyInfoImpl
  114. // template instantiated which is not available in the header.
  115. BlockFrequencyInfo::~BlockFrequencyInfo() {}
  116. void BlockFrequencyInfo::calculate(const Function &F,
  117. const BranchProbabilityInfo &BPI,
  118. const LoopInfo &LI) {
  119. if (!BFI)
  120. BFI.reset(new ImplType);
  121. BFI->calculate(F, BPI, LI);
  122. #ifndef NDEBUG
  123. if (ViewBlockFreqPropagationDAG != GVDT_None &&
  124. (ViewBlockFreqFuncName.empty() ||
  125. F.getName().equals(ViewBlockFreqFuncName))) {
  126. view();
  127. }
  128. #endif
  129. }
  130. BlockFrequency BlockFrequencyInfo::getBlockFreq(const BasicBlock *BB) const {
  131. return BFI ? BFI->getBlockFreq(BB) : 0;
  132. }
  133. Optional<uint64_t>
  134. BlockFrequencyInfo::getBlockProfileCount(const BasicBlock *BB) const {
  135. if (!BFI)
  136. return None;
  137. return BFI->getBlockProfileCount(*getFunction(), BB);
  138. }
  139. void BlockFrequencyInfo::setBlockFreq(const BasicBlock *BB, uint64_t Freq) {
  140. assert(BFI && "Expected analysis to be available");
  141. BFI->setBlockFreq(BB, Freq);
  142. }
  143. /// Pop up a ghostview window with the current block frequency propagation
  144. /// rendered using dot.
  145. void BlockFrequencyInfo::view() const {
  146. // This code is only for debugging.
  147. #ifndef NDEBUG
  148. ViewGraph(const_cast<BlockFrequencyInfo *>(this), "BlockFrequencyDAGs");
  149. #else
  150. errs() << "BlockFrequencyInfo::view is only available in debug builds on "
  151. "systems with Graphviz or gv!\n";
  152. #endif // NDEBUG
  153. }
  154. const Function *BlockFrequencyInfo::getFunction() const {
  155. return BFI ? BFI->getFunction() : nullptr;
  156. }
  157. const BranchProbabilityInfo *BlockFrequencyInfo::getBPI() const {
  158. return BFI ? &BFI->getBPI() : nullptr;
  159. }
  160. raw_ostream &BlockFrequencyInfo::
  161. printBlockFreq(raw_ostream &OS, const BlockFrequency Freq) const {
  162. return BFI ? BFI->printBlockFreq(OS, Freq) : OS;
  163. }
  164. raw_ostream &
  165. BlockFrequencyInfo::printBlockFreq(raw_ostream &OS,
  166. const BasicBlock *BB) const {
  167. return BFI ? BFI->printBlockFreq(OS, BB) : OS;
  168. }
  169. uint64_t BlockFrequencyInfo::getEntryFreq() const {
  170. return BFI ? BFI->getEntryFreq() : 0;
  171. }
  172. void BlockFrequencyInfo::releaseMemory() { BFI.reset(); }
  173. void BlockFrequencyInfo::print(raw_ostream &OS) const {
  174. if (BFI)
  175. BFI->print(OS);
  176. }
  177. INITIALIZE_PASS_BEGIN(BlockFrequencyInfoWrapperPass, "block-freq",
  178. "Block Frequency Analysis", true, true)
  179. INITIALIZE_PASS_DEPENDENCY(BranchProbabilityInfoWrapperPass)
  180. INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
  181. INITIALIZE_PASS_END(BlockFrequencyInfoWrapperPass, "block-freq",
  182. "Block Frequency Analysis", true, true)
  183. char BlockFrequencyInfoWrapperPass::ID = 0;
  184. BlockFrequencyInfoWrapperPass::BlockFrequencyInfoWrapperPass()
  185. : FunctionPass(ID) {
  186. initializeBlockFrequencyInfoWrapperPassPass(*PassRegistry::getPassRegistry());
  187. }
  188. BlockFrequencyInfoWrapperPass::~BlockFrequencyInfoWrapperPass() {}
  189. void BlockFrequencyInfoWrapperPass::print(raw_ostream &OS,
  190. const Module *) const {
  191. BFI.print(OS);
  192. }
  193. void BlockFrequencyInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
  194. AU.addRequired<BranchProbabilityInfoWrapperPass>();
  195. AU.addRequired<LoopInfoWrapperPass>();
  196. AU.setPreservesAll();
  197. }
  198. void BlockFrequencyInfoWrapperPass::releaseMemory() { BFI.releaseMemory(); }
  199. bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
  200. BranchProbabilityInfo &BPI =
  201. getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
  202. LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  203. BFI.calculate(F, BPI, LI);
  204. return false;
  205. }
  206. char BlockFrequencyAnalysis::PassID;
  207. BlockFrequencyInfo BlockFrequencyAnalysis::run(Function &F,
  208. AnalysisManager<Function> &AM) {
  209. BlockFrequencyInfo BFI;
  210. BFI.calculate(F, AM.getResult<BranchProbabilityAnalysis>(F),
  211. AM.getResult<LoopAnalysis>(F));
  212. return BFI;
  213. }
  214. PreservedAnalyses
  215. BlockFrequencyPrinterPass::run(Function &F, AnalysisManager<Function> &AM) {
  216. OS << "Printing analysis results of BFI for function "
  217. << "'" << F.getName() << "':"
  218. << "\n";
  219. AM.getResult<BlockFrequencyAnalysis>(F).print(OS);
  220. return PreservedAnalyses::all();
  221. }