llvm/Analysis/CFGPrinter.h

0001 //===-- CFGPrinter.h - CFG printer external interface -----------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 // This file defines a 'dot-cfg' analysis pass, which emits the
0010 // cfg.<fnname>.dot file for each function in the program, with a graph of the
0011 // CFG for that function.
0012 //
0013 // This file defines external functions that can be called to explicitly
0014 // instantiate the CFG printer.
0015 //
0016 //===----------------------------------------------------------------------===//
0017
0018 #ifndef LLVM_ANALYSIS_CFGPRINTER_H
0019 #define LLVM_ANALYSIS_CFGPRINTER_H
0020
0021 #include "llvm/Analysis/BlockFrequencyInfo.h"
0022 #include "llvm/Analysis/BranchProbabilityInfo.h"
0023 #include "llvm/Analysis/HeatUtils.h"
0024 #include "llvm/IR/CFG.h"
0025 #include "llvm/IR/Constants.h"
0026 #include "llvm/IR/Function.h"
0027 #include "llvm/IR/Instructions.h"
0028 #include "llvm/IR/PassManager.h"
0029 #include "llvm/IR/ProfDataUtils.h"
0030 #include "llvm/Support/DOTGraphTraits.h"
0031 #include "llvm/Support/FormatVariadic.h"
0032
0033 namespace llvm {
0034 template <class GraphType> struct GraphTraits;
0035 class CFGViewerPass : public PassInfoMixin<CFGViewerPass> {
0036 public:
0037   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
0038   static bool isRequired() { return true; }
0039 };
0040
0041 class CFGOnlyViewerPass : public PassInfoMixin<CFGOnlyViewerPass> {
0042 public:
0043   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
0044   static bool isRequired() { return true; }
0045 };
0046
0047 class CFGPrinterPass : public PassInfoMixin<CFGPrinterPass> {
0048 public:
0049   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
0050   static bool isRequired() { return true; }
0051 };
0052
0053 class CFGOnlyPrinterPass : public PassInfoMixin<CFGOnlyPrinterPass> {
0054 public:
0055   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
0056   static bool isRequired() { return true; }
0057 };
0058
0059 class DOTFuncInfo {
0060 private:
0061   const Function *F;
0062   const BlockFrequencyInfo *BFI;
0063   const BranchProbabilityInfo *BPI;
0064   uint64_t MaxFreq;
0065   bool ShowHeat;
0066   bool EdgeWeights;
0067   bool RawWeights;
0068
0069 public:
0070   DOTFuncInfo(const Function *F) : DOTFuncInfo(F, nullptr, nullptr, 0) {}
0071
0072   DOTFuncInfo(const Function *F, const BlockFrequencyInfo *BFI,
0073               const BranchProbabilityInfo *BPI, uint64_t MaxFreq)
0074       : F(F), BFI(BFI), BPI(BPI), MaxFreq(MaxFreq) {
0075     ShowHeat = false;
0076     EdgeWeights = !!BPI; // Print EdgeWeights when BPI is available.
0077     RawWeights = !!BFI;  // Print RawWeights when BFI is available.
0078   }
0079
0080   const BlockFrequencyInfo *getBFI() const { return BFI; }
0081
0082   const BranchProbabilityInfo *getBPI() const { return BPI; }
0083
0084   const Function *getFunction() const { return this->F; }
0085
0086   uint64_t getMaxFreq() const { return MaxFreq; }
0087
0088   uint64_t getFreq(const BasicBlock *BB) const {
0089     return BFI->getBlockFreq(BB).getFrequency();
0090   }
0091
0092   void setHeatColors(bool ShowHeat) { this->ShowHeat = ShowHeat; }
0093
0094   bool showHeatColors() { return ShowHeat; }
0095
0096   void setRawEdgeWeights(bool RawWeights) { this->RawWeights = RawWeights; }
0097
0098   bool useRawEdgeWeights() { return RawWeights; }
0099
0100   void setEdgeWeights(bool EdgeWeights) { this->EdgeWeights = EdgeWeights; }
0101
0102   bool showEdgeWeights() { return EdgeWeights; }
0103 };
0104
0105 template <>
0106 struct GraphTraits<DOTFuncInfo *> : public GraphTraits<const BasicBlock *> {
0107   static NodeRef getEntryNode(DOTFuncInfo *CFGInfo) {
0108     return &(CFGInfo->getFunction()->getEntryBlock());
0109   }
0110
0111   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
0112   using nodes_iterator = pointer_iterator<Function::const_iterator>;
0113
0114   static nodes_iterator nodes_begin(DOTFuncInfo *CFGInfo) {
0115     return nodes_iterator(CFGInfo->getFunction()->begin());
0116   }
0117
0118   static nodes_iterator nodes_end(DOTFuncInfo *CFGInfo) {
0119     return nodes_iterator(CFGInfo->getFunction()->end());
0120   }
0121
0122   static size_t size(DOTFuncInfo *CFGInfo) {
0123     return CFGInfo->getFunction()->size();
0124   }
0125 };
0126
0127 template <typename BasicBlockT>
0128 std::string SimpleNodeLabelString(const BasicBlockT *Node) {
0129   if (!Node->getName().empty())
0130     return Node->getName().str();
0131
0132   std::string Str;
0133   raw_string_ostream OS(Str);
0134
0135   Node->printAsOperand(OS, false);
0136   return Str;
0137 }
0138
0139 template <typename BasicBlockT>
0140 std::string CompleteNodeLabelString(
0141     const BasicBlockT *Node,
0142     function_ref<void(raw_string_ostream &, const BasicBlockT &)>
0143         HandleBasicBlock,
0144     function_ref<void(std::string &, unsigned &, unsigned)>
0145         HandleComment) {
0146
0147   enum { MaxColumns = 80 };
0148   std::string OutStr;
0149   raw_string_ostream OS(OutStr);
0150   HandleBasicBlock(OS, *Node);
0151   // Remove "%" from BB name
0152   if (OutStr[0] == '%') {
0153     OutStr.erase(OutStr.begin());
0154   }
0155   // Place | after BB name to separate it into header
0156   OutStr.insert(OutStr.find_first_of('\n') + 1, "\\|");
0157
0158   unsigned ColNum = 0;
0159   unsigned LastSpace = 0;
0160   for (unsigned i = 0; i != OutStr.length(); ++i) {
0161     if (OutStr[i] == '\n') { // Left justify
0162       OutStr[i] = '\\';
0163       OutStr.insert(OutStr.begin() + i + 1, 'l');
0164       ColNum = 0;
0165       LastSpace = 0;
0166     } else if (OutStr[i] == ';') {             // Delete comments!
0167       unsigned Idx = OutStr.find('\n', i + 1); // Find end of line
0168       HandleComment(OutStr, i, Idx);
0169     } else if (ColNum == MaxColumns) { // Wrap lines.
0170       // Wrap very long names even though we can't find a space.
0171       if (!LastSpace)
0172         LastSpace = i;
0173       OutStr.insert(LastSpace, "\\l...");
0174       ColNum = i - LastSpace;
0175       LastSpace = 0;
0176       i += 3; // The loop will advance 'i' again.
0177     } else
0178       ++ColNum;
0179     if (OutStr[i] == ' ')
0180       LastSpace = i;
0181   }
0182   return OutStr;
0183 }
0184
0185 template <>
0186 struct DOTGraphTraits<DOTFuncInfo *> : public DefaultDOTGraphTraits {
0187
0188   // Cache for is hidden property
0189   DenseMap<const BasicBlock *, bool> isOnDeoptOrUnreachablePath;
0190
0191   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
0192
0193   static void eraseComment(std::string &OutStr, unsigned &I, unsigned Idx) {
0194     OutStr.erase(OutStr.begin() + I, OutStr.begin() + Idx);
0195     --I;
0196   }
0197
0198   static std::string getGraphName(DOTFuncInfo *CFGInfo) {
0199     return "CFG for '" + CFGInfo->getFunction()->getName().str() + "' function";
0200   }
0201
0202   static std::string getSimpleNodeLabel(const BasicBlock *Node, DOTFuncInfo *) {
0203     return SimpleNodeLabelString(Node);
0204   }
0205
0206   static void printBasicBlock(raw_string_ostream &OS, const BasicBlock &Node) {
0207     // Prepend label name
0208     Node.printAsOperand(OS, false);
0209     OS << ":\n";
0210     for (const Instruction &Inst : Node)
0211       OS << Inst << "\n";
0212   }
0213
0214   static std::string getCompleteNodeLabel(
0215       const BasicBlock *Node, DOTFuncInfo *,
0216       function_ref<void(raw_string_ostream &, const BasicBlock &)>
0217           HandleBasicBlock = printBasicBlock,
0218       function_ref<void(std::string &, unsigned &, unsigned)>
0219           HandleComment = eraseComment) {
0220     return CompleteNodeLabelString(Node, HandleBasicBlock, HandleComment);
0221   }
0222
0223   std::string getNodeLabel(const BasicBlock *Node, DOTFuncInfo *CFGInfo) {
0224
0225     if (isSimple())
0226       return getSimpleNodeLabel(Node, CFGInfo);
0227     else
0228       return getCompleteNodeLabel(Node, CFGInfo);
0229   }
0230
0231   static std::string getEdgeSourceLabel(const BasicBlock *Node,
0232                                         const_succ_iterator I) {
0233     // Label source of conditional branches with "T" or "F"
0234     if (const BranchInst *BI = dyn_cast<BranchInst>(Node->getTerminator()))
0235       if (BI->isConditional())
0236         return (I == succ_begin(Node)) ? "T" : "F";
0237
0238     // Label source of switch edges with the associated value.
0239     if (const SwitchInst *SI = dyn_cast<SwitchInst>(Node->getTerminator())) {
0240       unsigned SuccNo = I.getSuccessorIndex();
0241
0242       if (SuccNo == 0)
0243         return "def";
0244
0245       std::string Str;
0246       raw_string_ostream OS(Str);
0247       auto Case = *SwitchInst::ConstCaseIt::fromSuccessorIndex(SI, SuccNo);
0248       OS << Case.getCaseValue()->getValue();
0249       return Str;
0250     }
0251     return "";
0252   }
0253
0254   static std::string getBBName(const BasicBlock *Node) {
0255     std::string NodeName = Node->getName().str();
0256     if (NodeName.empty()) {
0257       raw_string_ostream NodeOS(NodeName);
0258       Node->printAsOperand(NodeOS, false);
0259       // Removing %
0260       NodeName.erase(NodeName.begin());
0261     }
0262     return NodeName;
0263   }
0264
0265   /// Display the raw branch weights from PGO.
0266   std::string getEdgeAttributes(const BasicBlock *Node, const_succ_iterator I,
0267                                 DOTFuncInfo *CFGInfo) {
0268     // If BPI is not provided do not display any edge attributes
0269     if (!CFGInfo->showEdgeWeights())
0270       return "";
0271
0272     unsigned OpNo = I.getSuccessorIndex();
0273     const Instruction *TI = Node->getTerminator();
0274     BasicBlock *SuccBB = TI->getSuccessor(OpNo);
0275     auto BranchProb = CFGInfo->getBPI()->getEdgeProbability(Node, SuccBB);
0276     double WeightPercent = ((double)BranchProb.getNumerator()) /
0277                            ((double)BranchProb.getDenominator());
0278     std::string TTAttr =
0279         formatv("tooltip=\"{0} -> {1}\\nProbability {2:P}\" ", getBBName(Node),
0280                 getBBName(SuccBB), WeightPercent);
0281
0282     if (TI->getNumSuccessors() == 1)
0283       return TTAttr + "penwidth=2";
0284
0285     if (OpNo >= TI->getNumSuccessors())
0286       return TTAttr;
0287
0288     double Width = 1 + WeightPercent;
0289
0290     if (!CFGInfo->useRawEdgeWeights())
0291       return TTAttr +
0292              formatv("label=\"{0:P}\" penwidth={1}", WeightPercent, Width)
0293                  .str();
0294
0295     // Prepend a 'W' to indicate that this is a weight rather than the actual
0296     // profile count (due to scaling).
0297
0298     uint64_t Freq = CFGInfo->getFreq(Node);
0299     std::string Attrs =
0300         TTAttr + formatv("label=\"W:{0}\" penwidth={1}",
0301                          (uint64_t)(Freq * WeightPercent), Width)
0302                      .str();
0303     if (Attrs.size())
0304       return Attrs;
0305
0306     MDNode *WeightsNode = getBranchWeightMDNode(*TI);
0307     if (!WeightsNode)
0308       return TTAttr;
0309
0310     OpNo = I.getSuccessorIndex() + 1;
0311     if (OpNo >= WeightsNode->getNumOperands())
0312       return TTAttr;
0313     ConstantInt *Weight =
0314         mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(OpNo));
0315     if (!Weight)
0316       return TTAttr;
0317     return (TTAttr + "label=\"W:" + std::to_string(Weight->getZExtValue()) +
0318             "\" penwidth=" + std::to_string(Width));
0319   }
0320
0321   std::string getNodeAttributes(const BasicBlock *Node, DOTFuncInfo *CFGInfo) {
0322
0323     if (!CFGInfo->showHeatColors())
0324       return "";
0325
0326     uint64_t Freq = CFGInfo->getFreq(Node);
0327     std::string Color = getHeatColor(Freq, CFGInfo->getMaxFreq());
0328     std::string EdgeColor = (Freq <= (CFGInfo->getMaxFreq() / 2))
0329                                 ? (getHeatColor(0))
0330                                 : (getHeatColor(1));
0331
0332     std::string Attrs = "color=\"" + EdgeColor + "ff\", style=filled," +
0333                         " fillcolor=\"" + Color + "70\"" +
0334                         " fontname=\"Courier\"";
0335     return Attrs;
0336   }
0337   bool isNodeHidden(const BasicBlock *Node, const DOTFuncInfo *CFGInfo);
0338   void computeDeoptOrUnreachablePaths(const Function *F);
0339 };
0340 } // End llvm namespace
0341
0342 #endif