llvm/lib/Analysis/CFGPrinter.cpp

   1 //===- CFGPrinter.cpp - DOT printer for the control flow graph ------------===//
   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 // This file defines a `-dot-cfg` analysis pass, which emits the
  10 // `<prefix>.<fnname>.dot` file for each function in the program, with a graph
  11 // of the CFG for that function. The default value for `<prefix>` is `cfg` but
  12 // can be customized as needed.
  13 //
  14 // The other main feature of this file is that it implements the
  15 // Function::viewCFG method, which is useful for debugging passes which operate
  16 // on the CFG.
  17 //
  18 //===----------------------------------------------------------------------===//
  19
  20 #include "llvm/Analysis/CFGPrinter.h"
  21 #include "llvm/ADT/PostOrderIterator.h"
  22 #include "llvm/InitializePasses.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include "llvm/Support/FileSystem.h"
  26 #include <algorithm>
  27
  28 using namespace llvm;
  29
  30 static cl::opt<std::string>
  31     CFGFuncName("cfg-func-name", cl::Hidden,
  32                 cl::desc("The name of a function (or its substring)"
  33                          " whose CFG is viewed/printed."));
  34
  35 static cl::opt<std::string> CFGDotFilenamePrefix(
  36     "cfg-dot-filename-prefix", cl::Hidden,
  37     cl::desc("The prefix used for the CFG dot file names."));
  38
  39 static cl::opt<bool> HideUnreachablePaths("cfg-hide-unreachable-paths",
  40                                           cl::init(false));
  41
  42 static cl::opt<bool> HideDeoptimizePaths("cfg-hide-deoptimize-paths",
  43                                          cl::init(false));
  44
  45 static cl::opt<double> HideColdPaths(
  46     "cfg-hide-cold-paths", cl::init(0.0),
  47     cl::desc("Hide blocks with relative frequency below the given value"));
  48
  49 static cl::opt<bool> ShowHeatColors("cfg-heat-colors", cl::init(true),
  50                                     cl::Hidden,
  51                                     cl::desc("Show heat colors in CFG"));
  52
  53 static cl::opt<bool> UseRawEdgeWeight("cfg-raw-weights", cl::init(false),
  54                                       cl::Hidden,
  55                                       cl::desc("Use raw weights for labels. "
  56                                                "Use percentages as default."));
  57
  58 static cl::opt<bool>
  59     ShowEdgeWeight("cfg-weights", cl::init(false), cl::Hidden,
  60                    cl::desc("Show edges labeled with weights"));
  61
  62 static void writeCFGToDotFile(Function &F, BlockFrequencyInfo *BFI,
  63                               BranchProbabilityInfo *BPI, uint64_t MaxFreq,
  64                               bool CFGOnly = false) {
  65   std::string Filename =
  66       (CFGDotFilenamePrefix + "." + F.getName() + ".dot").str();
  67   errs() << "Writing '" << Filename << "'...";
  68
  69   std::error_code EC;
  70   raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
  71
  72   DOTFuncInfo CFGInfo(&F, BFI, BPI, MaxFreq);
  73   CFGInfo.setHeatColors(ShowHeatColors);
  74   CFGInfo.setEdgeWeights(ShowEdgeWeight);
  75   CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
  76
  77   if (!EC)
  78     WriteGraph(File, &CFGInfo, CFGOnly);
  79   else
  80     errs() << "  error opening file for writing!";
  81   errs() << "\n";
  82 }
  83
  84 static void viewCFG(Function &F, const BlockFrequencyInfo *BFI,
  85                     const BranchProbabilityInfo *BPI, uint64_t MaxFreq,
  86                     bool CFGOnly = false) {
  87   DOTFuncInfo CFGInfo(&F, BFI, BPI, MaxFreq);
  88   CFGInfo.setHeatColors(ShowHeatColors);
  89   CFGInfo.setEdgeWeights(ShowEdgeWeight);
  90   CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
  91
  92   ViewGraph(&CFGInfo, "cfg." + F.getName(), CFGOnly);
  93 }
  94
  95 namespace {
  96 struct CFGViewerLegacyPass : public FunctionPass {
  97   static char ID; // Pass identifcation, replacement for typeid
  98   CFGViewerLegacyPass() : FunctionPass(ID) {
  99     initializeCFGViewerLegacyPassPass(*PassRegistry::getPassRegistry());
 100   }
 101
 102   bool runOnFunction(Function &F) override {
 103     if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
 104       return false;
 105     auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
 106     auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
 107     viewCFG(F, BFI, BPI, getMaxFreq(F, BFI));
 108     return false;
 109   }
 110
 111   void print(raw_ostream &OS, const Module * = nullptr) const override {}
 112
 113   void getAnalysisUsage(AnalysisUsage &AU) const override {
 114     FunctionPass::getAnalysisUsage(AU);
 115     AU.addRequired<BlockFrequencyInfoWrapperPass>();
 116     AU.addRequired<BranchProbabilityInfoWrapperPass>();
 117     AU.setPreservesAll();
 118   }
 119 };
 120 } // namespace
 121
 122 char CFGViewerLegacyPass::ID = 0;
 123 INITIALIZE_PASS(CFGViewerLegacyPass, "view-cfg", "View CFG of function", false,
 124                 true)
 125
 126 PreservedAnalyses CFGViewerPass::run(Function &F, FunctionAnalysisManager &AM) {
 127   if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
 128     return PreservedAnalyses::all();
 129   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
 130   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
 131   viewCFG(F, BFI, BPI, getMaxFreq(F, BFI));
 132   return PreservedAnalyses::all();
 133 }
 134
 135 namespace {
 136 struct CFGOnlyViewerLegacyPass : public FunctionPass {
 137   static char ID; // Pass identifcation, replacement for typeid
 138   CFGOnlyViewerLegacyPass() : FunctionPass(ID) {
 139     initializeCFGOnlyViewerLegacyPassPass(*PassRegistry::getPassRegistry());
 140   }
 141
 142   bool runOnFunction(Function &F) override {
 143     if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
 144       return false;
 145     auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
 146     auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
 147     viewCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
 148     return false;
 149   }
 150
 151   void print(raw_ostream &OS, const Module * = nullptr) const override {}
 152
 153   void getAnalysisUsage(AnalysisUsage &AU) const override {
 154     FunctionPass::getAnalysisUsage(AU);
 155     AU.addRequired<BlockFrequencyInfoWrapperPass>();
 156     AU.addRequired<BranchProbabilityInfoWrapperPass>();
 157     AU.setPreservesAll();
 158   }
 159 };
 160 } // namespace
 161
 162 char CFGOnlyViewerLegacyPass::ID = 0;
 163 INITIALIZE_PASS(CFGOnlyViewerLegacyPass, "view-cfg-only",
 164                 "View CFG of function (with no function bodies)", false, true)
 165
 166 PreservedAnalyses CFGOnlyViewerPass::run(Function &F,
 167                                          FunctionAnalysisManager &AM) {
 168   if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
 169     return PreservedAnalyses::all();
 170   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
 171   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
 172   viewCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
 173   return PreservedAnalyses::all();
 174 }
 175
 176 namespace {
 177 struct CFGPrinterLegacyPass : public FunctionPass {
 178   static char ID; // Pass identification, replacement for typeid
 179   CFGPrinterLegacyPass() : FunctionPass(ID) {
 180     initializeCFGPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
 181   }
 182
 183   bool runOnFunction(Function &F) override {
 184     if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
 185       return false;
 186     auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
 187     auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
 188     writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI));
 189     return false;
 190   }
 191
 192   void print(raw_ostream &OS, const Module * = nullptr) const override {}
 193
 194   void getAnalysisUsage(AnalysisUsage &AU) const override {
 195     FunctionPass::getAnalysisUsage(AU);
 196     AU.addRequired<BlockFrequencyInfoWrapperPass>();
 197     AU.addRequired<BranchProbabilityInfoWrapperPass>();
 198     AU.setPreservesAll();
 199   }
 200 };
 201 } // namespace
 202
 203 char CFGPrinterLegacyPass::ID = 0;
 204 INITIALIZE_PASS(CFGPrinterLegacyPass, "dot-cfg",
 205                 "Print CFG of function to 'dot' file", false, true)
 206
 207 PreservedAnalyses CFGPrinterPass::run(Function &F,
 208                                       FunctionAnalysisManager &AM) {
 209   if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
 210     return PreservedAnalyses::all();
 211   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
 212   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
 213   writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI));
 214   return PreservedAnalyses::all();
 215 }
 216
 217 namespace {
 218 struct CFGOnlyPrinterLegacyPass : public FunctionPass {
 219   static char ID; // Pass identification, replacement for typeid
 220   CFGOnlyPrinterLegacyPass() : FunctionPass(ID) {
 221     initializeCFGOnlyPrinterLegacyPassPass(*PassRegistry::getPassRegistry());
 222   }
 223
 224   bool runOnFunction(Function &F) override {
 225     if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
 226       return false;
 227     auto *BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
 228     auto *BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
 229     writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
 230     return false;
 231   }
 232   void print(raw_ostream &OS, const Module * = nullptr) const override {}
 233
 234   void getAnalysisUsage(AnalysisUsage &AU) const override {
 235     FunctionPass::getAnalysisUsage(AU);
 236     AU.addRequired<BlockFrequencyInfoWrapperPass>();
 237     AU.addRequired<BranchProbabilityInfoWrapperPass>();
 238     AU.setPreservesAll();
 239   }
 240 };
 241 } // namespace
 242
 243 char CFGOnlyPrinterLegacyPass::ID = 0;
 244 INITIALIZE_PASS(CFGOnlyPrinterLegacyPass, "dot-cfg-only",
 245                 "Print CFG of function to 'dot' file (with no function bodies)",
 246                 false, true)
 247
 248 PreservedAnalyses CFGOnlyPrinterPass::run(Function &F,
 249                                           FunctionAnalysisManager &AM) {
 250   if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
 251     return PreservedAnalyses::all();
 252   auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
 253   auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
 254   writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
 255   return PreservedAnalyses::all();
 256 }
 257
 258 /// viewCFG - This function is meant for use from the debugger.  You can just
 259 /// say 'call F->viewCFG()' and a ghostview window should pop up from the
 260 /// program, displaying the CFG of the current function.  This depends on there
 261 /// being a 'dot' and 'gv' program in your path.
 262 ///
 263 void Function::viewCFG() const { viewCFG(false, nullptr, nullptr); }
 264
 265 void Function::viewCFG(bool ViewCFGOnly, const BlockFrequencyInfo *BFI,
 266                        const BranchProbabilityInfo *BPI) const {
 267   if (!CFGFuncName.empty() && !getName().contains(CFGFuncName))
 268     return;
 269   DOTFuncInfo CFGInfo(this, BFI, BPI, BFI ? getMaxFreq(*this, BFI) : 0);
 270   ViewGraph(&CFGInfo, "cfg" + getName(), ViewCFGOnly);
 271 }
 272
 273 /// viewCFGOnly - This function is meant for use from the debugger.  It works
 274 /// just like viewCFG, but it does not include the contents of basic blocks
 275 /// into the nodes, just the label.  If you are only interested in the CFG
 276 /// this can make the graph smaller.
 277 ///
 278 void Function::viewCFGOnly() const { viewCFGOnly(nullptr, nullptr); }
 279
 280 void Function::viewCFGOnly(const BlockFrequencyInfo *BFI,
 281                            const BranchProbabilityInfo *BPI) const {
 282   viewCFG(true, BFI, BPI);
 283 }
 284
 285 FunctionPass *llvm::createCFGPrinterLegacyPassPass() {
 286   return new CFGPrinterLegacyPass();
 287 }
 288
 289 FunctionPass *llvm::createCFGOnlyPrinterLegacyPassPass() {
 290   return new CFGOnlyPrinterLegacyPass();
 291 }
 292
 293 /// Find all blocks on the paths which terminate with a deoptimize or
 294 /// unreachable (i.e. all blocks which are post-dominated by a deoptimize
 295 /// or unreachable). These paths are hidden if the corresponding cl::opts
 296 /// are enabled.
 297 void DOTGraphTraits<DOTFuncInfo *>::computeDeoptOrUnreachablePaths(
 298     const Function *F) {
 299   auto evaluateBB = [&](const BasicBlock *Node) {
 300     if (succ_empty(Node)) {
 301       const Instruction *TI = Node->getTerminator();
 302       isOnDeoptOrUnreachablePath[Node] =
 303           (HideUnreachablePaths && isa<UnreachableInst>(TI)) ||
 304           (HideDeoptimizePaths && Node->getTerminatingDeoptimizeCall());
 305       return;
 306     }
 307     isOnDeoptOrUnreachablePath[Node] =
 308         llvm::all_of(successors(Node), [this](const BasicBlock *BB) {
 309           return isOnDeoptOrUnreachablePath[BB];
 310         });
 311   };
 312   /// The post order traversal iteration is done to know the status of
 313   /// isOnDeoptOrUnreachablePath for all the successors on the current BB.
 314   llvm::for_each(post_order(&F->getEntryBlock()), evaluateBB);
 315 }
 316
 317 bool DOTGraphTraits<DOTFuncInfo *>::isNodeHidden(const BasicBlock *Node,
 318                                                  const DOTFuncInfo *CFGInfo) {
 319   if (HideColdPaths.getNumOccurrences() > 0)
 320     if (auto *BFI = CFGInfo->getBFI()) {
 321       uint64_t NodeFreq = BFI->getBlockFreq(Node).getFrequency();
 322       uint64_t EntryFreq = BFI->getEntryFreq();
 323       // Hide blocks with relative frequency below HideColdPaths threshold.
 324       if ((double)NodeFreq / EntryFreq < HideColdPaths)
 325         return true;
 326     }
 327   if (HideUnreachablePaths || HideDeoptimizePaths) {
 328     if (isOnDeoptOrUnreachablePath.find(Node) ==
 329         isOnDeoptOrUnreachablePath.end())
 330       computeDeoptOrUnreachablePaths(Node->getParent());
 331     return isOnDeoptOrUnreachablePath[Node];
 332   }
 333   return false;
 334 }