Index: llvm/include/llvm/Analysis/CFGPrinter.h =================================================================== --- llvm/include/llvm/Analysis/CFGPrinter.h +++ llvm/include/llvm/Analysis/CFGPrinter.h @@ -18,52 +18,125 @@ #ifndef LLVM_ANALYSIS_CFGPRINTER_H #define LLVM_ANALYSIS_CFGPRINTER_H +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" +#include "llvm/Analysis/HeatUtils.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Constants.h" #include "llvm/IR/Function.h" #include "llvm/IR/Instructions.h" +#include "llvm/IR/Module.h" #include "llvm/IR/PassManager.h" +#include "llvm/Support/FormatVariadic.h" #include "llvm/Support/GraphWriter.h" namespace llvm { -class CFGViewerPass - : public PassInfoMixin { +class CFGViewerPass : public PassInfoMixin { public: - PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); }; -class CFGOnlyViewerPass - : public PassInfoMixin { +class CFGOnlyViewerPass : public PassInfoMixin { public: - PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); }; -class CFGPrinterPass - : public PassInfoMixin { +class CFGPrinterPass : public PassInfoMixin { public: - PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); }; -class CFGOnlyPrinterPass - : public PassInfoMixin { +class CFGOnlyPrinterPass : public PassInfoMixin { public: - PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); + PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); }; -template<> -struct DOTGraphTraits : public DefaultDOTGraphTraits { +class CFGDOTInfo { +private: + const Function *F; + const BlockFrequencyInfo *BFI; + const BranchProbabilityInfo *BPI; + uint64_t MaxFreq; + bool ShowHeat; + bool Heuristic; + bool EdgeWeights; + bool RawWeights; + +public: + CFGDOTInfo(const Function *F) : CFGDOTInfo(F, nullptr, nullptr, 0) {} + + CFGDOTInfo(const Function *F, const BlockFrequencyInfo *BFI, + BranchProbabilityInfo *BPI, uint64_t MaxFreq) + : F(F), BFI(BFI), BPI(BPI), MaxFreq(MaxFreq) { + ShowHeat = false; + Heuristic = true; + EdgeWeights = true; + RawWeights = true; + } + + const BlockFrequencyInfo *getBFI() { return BFI; } + + const BranchProbabilityInfo *getBPI() { return BPI; } + + const Function *getFunction() { return this->F; } + + uint64_t getMaxFreq() { return MaxFreq; } + + uint64_t getFreq(const BasicBlock *BB) { + return BFI->getBlockFreq(BB).getFrequency(); + } + + void setHeatColors(bool ShowHeat) { this->ShowHeat = ShowHeat; } + + bool showHeatColors() { return ShowHeat; } + + void setHeuristic(bool Heuristic) { this->Heuristic = Heuristic; } + + bool useHeuristic() { return Heuristic; } + + void setRawEdgeWeights(bool RawWeights) { this->RawWeights = RawWeights; } + + bool useRawEdgeWeights() { return RawWeights; } + + void setEdgeWeights(bool EdgeWeights) { this->EdgeWeights = EdgeWeights; } + + bool showEdgeWeights() { return EdgeWeights; } +}; + +template <> +struct GraphTraits : public GraphTraits { + static NodeRef getEntryNode(CFGDOTInfo *CFGInfo) { + return &(CFGInfo->getFunction()->getEntryBlock()); + } + + // nodes_iterator/begin/end - Allow iteration over all nodes in the graph + using nodes_iterator = pointer_iterator; + + static nodes_iterator nodes_begin(CFGDOTInfo *CFGInfo) { + return nodes_iterator(CFGInfo->getFunction()->begin()); + } + + static nodes_iterator nodes_end(CFGDOTInfo *CFGInfo) { + return nodes_iterator(CFGInfo->getFunction()->end()); + } + + static size_t size(CFGDOTInfo *CFGInfo) { + return CFGInfo->getFunction()->size(); + } +}; + +template <> struct DOTGraphTraits : public DefaultDOTGraphTraits { // Cache for is hidden property llvm::DenseMap isHiddenBasicBlock; DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} - static std::string getGraphName(const Function *F) { - return "CFG for '" + F->getName().str() + "' function"; + static std::string getGraphName(CFGDOTInfo *CFGInfo) { + return "CFG for '" + CFGInfo->getFunction()->getName().str() + "' function"; } - static std::string getSimpleNodeLabel(const BasicBlock *Node, - const Function *) { + static std::string getSimpleNodeLabel(const BasicBlock *Node, CFGDOTInfo *) { if (!Node->getName().empty()) return Node->getName().str(); @@ -75,7 +148,7 @@ } static std::string getCompleteNodeLabel(const BasicBlock *Node, - const Function *) { + CFGDOTInfo *) { enum { MaxColumns = 80 }; std::string Str; raw_string_ostream OS(Str); @@ -87,22 +160,23 @@ OS << *Node; std::string OutStr = OS.str(); - if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); + if (OutStr[0] == '\n') + OutStr.erase(OutStr.begin()); // Process string output to make it nicer... unsigned ColNum = 0; unsigned LastSpace = 0; for (unsigned i = 0; i != OutStr.length(); ++i) { - if (OutStr[i] == '\n') { // Left justify + if (OutStr[i] == '\n') { // Left justify OutStr[i] = '\\'; - OutStr.insert(OutStr.begin()+i+1, 'l'); + OutStr.insert(OutStr.begin() + i + 1, 'l'); ColNum = 0; LastSpace = 0; - } else if (OutStr[i] == ';') { // Delete comments! - unsigned Idx = OutStr.find('\n', i+1); // Find end of line - OutStr.erase(OutStr.begin()+i, OutStr.begin()+Idx); + } else if (OutStr[i] == ';') { + unsigned Idx = OutStr.find('\n', i + 1); // Find end of line + OutStr.erase(OutStr.begin() + i, OutStr.begin() + Idx); --i; - } else if (ColNum == MaxColumns) { // Wrap lines. + } else if (ColNum == MaxColumns) { // Wrap lines. // Wrap very long names even though we can't find a space. if (!LastSpace) LastSpace = i; @@ -110,8 +184,7 @@ ColNum = i - LastSpace; LastSpace = 0; i += 3; // The loop will advance 'i' again. - } - else + } else ++ColNum; if (OutStr[i] == ' ') LastSpace = i; @@ -119,12 +192,12 @@ return OutStr; } - std::string getNodeLabel(const BasicBlock *Node, - const Function *Graph) { + std::string getNodeLabel(const BasicBlock *Node, CFGDOTInfo *CFGInfo) { + if (isSimple()) - return getSimpleNodeLabel(Node, Graph); + return getSimpleNodeLabel(Node, CFGInfo); else - return getCompleteNodeLabel(Node, Graph); + return getCompleteNodeLabel(Node, CFGInfo); } static std::string getEdgeSourceLabel(const BasicBlock *Node, @@ -138,7 +211,8 @@ if (const SwitchInst *SI = dyn_cast(Node->getTerminator())) { unsigned SuccNo = I.getSuccessorIndex(); - if (SuccNo == 0) return "def"; + if (SuccNo == 0) + return "def"; std::string Str; raw_string_ostream OS(Str); @@ -151,11 +225,38 @@ /// Display the raw branch weights from PGO. std::string getEdgeAttributes(const BasicBlock *Node, succ_const_iterator I, - const Function *F) { + CFGDOTInfo *CFGInfo) { + if (!CFGInfo->showEdgeWeights()) + return ""; + const Instruction *TI = Node->getTerminator(); if (TI->getNumSuccessors() == 1) + return "penwidth=2"; + + unsigned OpNo = I.getSuccessorIndex(); + + if (OpNo >= TI->getNumSuccessors()) return ""; + BasicBlock *SuccBB = TI->getSuccessor(OpNo); + auto BranchProb = CFGInfo->getBPI()->getEdgeProbability(Node, SuccBB); + double WeightPercent = ((double)BranchProb.getNumerator()) / + ((double)BranchProb.getDenominator()); + double Width = 1 + WeightPercent; + + if (!CFGInfo->useRawEdgeWeights()) + return formatv("label=\"{0:P}\" penwidth={1}", WeightPercent, Width) + .str(); + + // Prepend a 'W' to indicate that this is a weight rather than the actual + // profile count (due to scaling). + + uint64_t Freq = CFGInfo->getFreq(Node); + std::string Attrs = formatv("label=\"W:{0}\" penwidth={1}", + (uint64_t)(Freq * WeightPercent), Width); + if (Attrs.size()) + return Attrs; + MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof); if (!WeightsNode) return ""; @@ -164,27 +265,41 @@ if (MDName->getString() != "branch_weights") return ""; - unsigned OpNo = I.getSuccessorIndex() + 1; + OpNo = I.getSuccessorIndex() + 1; if (OpNo >= WeightsNode->getNumOperands()) return ""; ConstantInt *Weight = mdconst::dyn_extract(WeightsNode->getOperand(OpNo)); if (!Weight) return ""; + return ("label=\"W:" + std::to_string(Weight->getZExtValue()) + + "\" penwidth=" + std::to_string(Width)); + } + + std::string getNodeAttributes(const BasicBlock *Node, CFGDOTInfo *CFGInfo) { + + if (!CFGInfo->showHeatColors()) + return ""; - // Prepend a 'W' to indicate that this is a weight rather than the actual - // profile count (due to scaling). - return ("label=\"W:" + Twine(Weight->getZExtValue()) + "\"").str(); + uint64_t Freq = CFGInfo->getFreq(Node); + std::string Color = getHeatColor(Freq, CFGInfo->getMaxFreq()); + std::string EdgeColor = (Freq <= (CFGInfo->getMaxFreq() / 2)) + ? (getHeatColor(0)) + : (getHeatColor(1)); + + std::string Attrs = "color=\"" + EdgeColor + "ff\", style=filled," + + "fillcolor=\"" + Color + "70\""; + return Attrs; } bool isNodeHidden(const BasicBlock *Node); void computeHiddenNodes(const Function *F); }; -} // End llvm namespace +} // namespace llvm namespace llvm { - class FunctionPass; - FunctionPass *createCFGPrinterLegacyPassPass (); - FunctionPass *createCFGOnlyPrinterLegacyPassPass (); -} // End llvm namespace +class ModulePass; +ModulePass *createCFGPrinterLegacyPassPass(); +ModulePass *createCFGOnlyPrinterLegacyPassPass(); +} // namespace llvm #endif Index: llvm/include/llvm/Analysis/HeatUtils.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/HeatUtils.h @@ -0,0 +1,47 @@ +//===-- HeatUtils.h - Utility for printing heat colors ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Utility for printing heat colors based on heuristics or profiling +// information. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_HEATUTILS_H +#define LLVM_ANALYSIS_HEATUTILS_H + +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CallSite.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/Module.h" + +#include + +namespace llvm { + +uint64_t +getNumOfCalls(Function &callerFunction, Function &calledFunction, + function_ref LookupBFI); + +uint64_t +getNumOfCalls(CallSite &callsite, + function_ref LookupBFI); + +uint64_t getMaxFreq(const Function &F, const BlockFrequencyInfo *BFI); + +uint64_t getMaxFreq(Module &M, + function_ref LookupBFI); + +std::string getHeatColor(uint64_t freq, uint64_t maxFreq); + +std::string getHeatColor(double percent); + +} // namespace llvm + +#endif \ No newline at end of file Index: llvm/lib/Analysis/CFGPrinter.cpp =================================================================== --- llvm/lib/Analysis/CFGPrinter.cpp +++ llvm/lib/Analysis/CFGPrinter.cpp @@ -41,52 +41,164 @@ static cl::opt HideDeoptimizePaths("cfg-hide-deoptimize-paths", cl::init(false)); +static cl::opt CFGHeatPerFunction("cfg-heat-per-function", + cl::init(false), cl::Hidden, + cl::desc("Heat CFG per function")); + +static cl::opt ShowHeatColors("cfg-heat-colors", cl::init(false), + cl::Hidden, + cl::desc("Show heat colors in CFG")); + +static cl::opt UseRawEdgeWeight("cfg-raw-weights", cl::init(false), + cl::Hidden, + cl::desc("Use raw weights for labels. " + "Use percentages as default.")); + +static cl::opt ShowEdgeWeight("cfg-weights", cl::init(false), cl::Hidden, + cl::desc("Show edges labeled with weights")); + +static void writeHeatCFGToDotFile(Function &F, BlockFrequencyInfo *BFI, + BranchProbabilityInfo *BPI, uint64_t MaxFreq, + bool UseHeuristic, bool isSimple) { + std::string Filename = + (CFGDotFilenamePrefix + "." + F.getName() + ".dot").str(); + errs() << "Writing '" << Filename << "'..."; + + std::error_code EC; + raw_fd_ostream File(Filename, EC, sys::fs::F_Text); + + CFGDOTInfo CFGInfo(&F, BFI, BPI, MaxFreq); + CFGInfo.setHeuristic(UseHeuristic); + CFGInfo.setHeatColors(ShowHeatColors); + CFGInfo.setEdgeWeights(ShowEdgeWeight); + CFGInfo.setRawEdgeWeights(UseRawEdgeWeight); + + if (!EC) + WriteGraph(File, &CFGInfo, isSimple); + else + errs() << " error opening file for writing!"; + errs() << "\n"; +} + +static void writeAllCFGsToDotFile(Module &M, + function_ref LookupBFI, + function_ref LookupBPI, + bool isSimple) { + uint64_t MaxFreq = 0; + if (!CFGHeatPerFunction) + MaxFreq = getMaxFreq(M, LookupBFI); + + for (auto &F : M) { + if (F.isDeclaration()) continue; + auto *BFI = LookupBFI(F); + auto *BPI = LookupBPI(F); + if (CFGHeatPerFunction) + MaxFreq = getMaxFreq(F, BFI); + writeHeatCFGToDotFile(F, BFI, BPI, MaxFreq, true, isSimple); + } + +} + +static void viewHeatCFG(Function &F, BlockFrequencyInfo *BFI, + BranchProbabilityInfo *BPI, uint64_t MaxFreq, + bool UseHeuristic, bool isSimple) { + CFGDOTInfo CFGInfo(&F, BFI, BPI, MaxFreq); + CFGInfo.setHeuristic(UseHeuristic); + CFGInfo.setHeatColors(ShowHeatColors); + CFGInfo.setEdgeWeights(ShowEdgeWeight); + CFGInfo.setRawEdgeWeights(UseRawEdgeWeight); + + ViewGraph(&CFGInfo, "cfg." + F.getName(), isSimple); +} + +static void viewAllCFGs(Module &M, + function_ref LookupBFI, + function_ref LookupBPI, + bool isSimple) { + uint64_t MaxFreq = 0; + if (!CFGHeatPerFunction) + MaxFreq = getMaxFreq(M, LookupBFI); + + for (auto &F : M) { + if (F.isDeclaration()) continue; + auto *BFI = LookupBFI(F); + auto *BPI = LookupBPI(F); + if (CFGHeatPerFunction) + MaxFreq = getMaxFreq(F, BFI); + viewHeatCFG(F, BFI, BPI, MaxFreq, true, isSimple); + } +} namespace { - struct CFGViewerLegacyPass : public FunctionPass { + struct CFGViewerLegacyPass : public ModulePass { static char ID; // Pass identifcation, replacement for typeid - CFGViewerLegacyPass() : FunctionPass(ID) { + CFGViewerLegacyPass() : ModulePass(ID) { initializeCFGViewerLegacyPassPass(*PassRegistry::getPassRegistry()); } - bool runOnFunction(Function &F) override { - F.viewCFG(); + bool runOnModule(Module &M) override { + auto LookupBFI = [this](Function &F) { + return &this->getAnalysis(F).getBFI(); + }; + auto LookupBPI = [this](Function &F) { + return &this->getAnalysis(F).getBPI(); + }; + viewAllCFGs(M, LookupBFI, LookupBPI, /*isSimple=*/false); return false; } - void print(raw_ostream &OS, const Module* = nullptr) const override {} + void print(raw_ostream &OS, const Module * = nullptr) const override {} void getAnalysisUsage(AnalysisUsage &AU) const override { + ModulePass::getAnalysisUsage(AU); + AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } - }; + }; } char CFGViewerLegacyPass::ID = 0; INITIALIZE_PASS(CFGViewerLegacyPass, "view-cfg", "View CFG of function", false, true) -PreservedAnalyses CFGViewerPass::run(Function &F, - FunctionAnalysisManager &AM) { - F.viewCFG(); +PreservedAnalyses CFGViewerPass::run(Module &M, + ModuleAnalysisManager &AM) { + auto &FAM = AM.getResult(M).getManager(); + auto LookupBFI = [&FAM](Function &F) { + return &FAM.getResult(F); + }; + auto LookupBPI = [&FAM](Function &F) { + return &FAM.getResult(F); + }; + viewAllCFGs(M, LookupBFI, LookupBPI, /*isSimple=*/false); return PreservedAnalyses::all(); } namespace { - struct CFGOnlyViewerLegacyPass : public FunctionPass { + struct CFGOnlyViewerLegacyPass : public ModulePass { static char ID; // Pass identifcation, replacement for typeid - CFGOnlyViewerLegacyPass() : FunctionPass(ID) { + CFGOnlyViewerLegacyPass() : ModulePass(ID) { initializeCFGOnlyViewerLegacyPassPass(*PassRegistry::getPassRegistry()); } - bool runOnFunction(Function &F) override { - F.viewCFGOnly(); + bool runOnModule(Module &M) override { + auto LookupBFI = [this](Function &F) { + return &this->getAnalysis(F).getBFI(); + }; + auto LookupBPI = [this](Function &F) { + return &this->getAnalysis(F).getBPI(); + }; + viewAllCFGs(M, LookupBFI, LookupBPI, /*isSimple=*/true); return false; } - void print(raw_ostream &OS, const Module* = nullptr) const override {} + void print(raw_ostream &OS, const Module * = nullptr) const override {} void getAnalysisUsage(AnalysisUsage &AU) const override { + ModulePass::getAnalysisUsage(AU); + AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } }; @@ -96,44 +208,43 @@ INITIALIZE_PASS(CFGOnlyViewerLegacyPass, "view-cfg-only", "View CFG of function (with no function bodies)", false, true) -PreservedAnalyses CFGOnlyViewerPass::run(Function &F, - FunctionAnalysisManager &AM) { - F.viewCFGOnly(); +PreservedAnalyses CFGOnlyViewerPass::run(Module &M, + ModuleAnalysisManager &AM) { + auto &FAM = AM.getResult(M).getManager(); + auto LookupBFI = [&FAM](Function &F) { + return &FAM.getResult(F); + }; + auto LookupBPI = [&FAM](Function &F) { + return &FAM.getResult(F); + }; + viewAllCFGs(M, LookupBFI, LookupBPI, /*isSimple=*/true); return PreservedAnalyses::all(); } -static void writeCFGToDotFile(Function &F, bool CFGOnly = false) { - if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName)) - return; - std::string Filename = - (CFGDotFilenamePrefix + "." + F.getName() + ".dot").str(); - errs() << "Writing '" << Filename << "'..."; - - std::error_code EC; - raw_fd_ostream File(Filename, EC, sys::fs::OF_Text); - - if (!EC) - WriteGraph(File, (const Function*)&F, CFGOnly); - else - errs() << " error opening file for writing!"; - errs() << "\n"; -} - namespace { - struct CFGPrinterLegacyPass : public FunctionPass { + struct CFGPrinterLegacyPass : public ModulePass { static char ID; // Pass identification, replacement for typeid - CFGPrinterLegacyPass() : FunctionPass(ID) { + CFGPrinterLegacyPass() : ModulePass(ID) { initializeCFGPrinterLegacyPassPass(*PassRegistry::getPassRegistry()); } - bool runOnFunction(Function &F) override { - writeCFGToDotFile(F); + bool runOnModule(Module &M) override { + auto LookupBFI = [this](Function &F) { + return &this->getAnalysis(F).getBFI(); + }; + auto LookupBPI = [this](Function &F) { + return &this->getAnalysis(F).getBPI(); + }; + writeAllCFGsToDotFile(M, LookupBFI, LookupBPI, /*isSimple=*/false); return false; } - void print(raw_ostream &OS, const Module* = nullptr) const override {} + void print(raw_ostream &OS, const Module * = nullptr) const override {} void getAnalysisUsage(AnalysisUsage &AU) const override { + ModulePass::getAnalysisUsage(AU); + AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } }; @@ -143,26 +254,42 @@ INITIALIZE_PASS(CFGPrinterLegacyPass, "dot-cfg", "Print CFG of function to 'dot' file", false, true) -PreservedAnalyses CFGPrinterPass::run(Function &F, - FunctionAnalysisManager &AM) { - writeCFGToDotFile(F); +PreservedAnalyses CFGPrinterPass::run(Module &M, + ModuleAnalysisManager &AM) { + auto &FAM = AM.getResult(M).getManager(); + auto LookupBFI = [&FAM](Function &F) { + return &FAM.getResult(F); + }; + auto LookupBPI = [&FAM](Function &F) { + return &FAM.getResult(F); + }; + writeAllCFGsToDotFile(M, LookupBFI, LookupBPI, /*isSimple=*/false); return PreservedAnalyses::all(); } namespace { - struct CFGOnlyPrinterLegacyPass : public FunctionPass { + struct CFGOnlyPrinterLegacyPass : public ModulePass { static char ID; // Pass identification, replacement for typeid - CFGOnlyPrinterLegacyPass() : FunctionPass(ID) { + CFGOnlyPrinterLegacyPass() : ModulePass(ID) { initializeCFGOnlyPrinterLegacyPassPass(*PassRegistry::getPassRegistry()); } - bool runOnFunction(Function &F) override { - writeCFGToDotFile(F, /*CFGOnly=*/true); + bool runOnModule(Module &M) override { + auto LookupBFI = [this](Function &F) { + return &this->getAnalysis(F).getBFI(); + }; + auto LookupBPI = [this](Function &F) { + return &this->getAnalysis(F).getBPI(); + }; + writeAllCFGsToDotFile(M, LookupBFI, LookupBPI, /*isSimple=*/true); return false; } - void print(raw_ostream &OS, const Module* = nullptr) const override {} + void print(raw_ostream &OS, const Module * = nullptr) const override {} void getAnalysisUsage(AnalysisUsage &AU) const override { + ModulePass::getAnalysisUsage(AU); + AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } }; @@ -173,9 +300,16 @@ "Print CFG of function to 'dot' file (with no function bodies)", false, true) -PreservedAnalyses CFGOnlyPrinterPass::run(Function &F, - FunctionAnalysisManager &AM) { - writeCFGToDotFile(F, /*CFGOnly=*/true); +PreservedAnalyses CFGOnlyPrinterPass::run(Module &M, + ModuleAnalysisManager &AM) { + auto &FAM = AM.getResult(M).getManager(); + auto LookupBFI = [&FAM](Function &F) { + return &FAM.getResult(F); + }; + auto LookupBPI = [&FAM](Function &F) { + return &FAM.getResult(F); + }; + writeAllCFGsToDotFile(M, LookupBFI, LookupBPI, /*isSimple=*/true); return PreservedAnalyses::all(); } @@ -187,7 +321,8 @@ void Function::viewCFG() const { if (!CFGFuncName.empty() && !getName().contains(CFGFuncName)) return; - ViewGraph(this, "cfg" + getName()); + CFGDOTInfo CFGInfo(this); + ViewGraph(&CFGInfo, "cfg" + getName()); } /// viewCFGOnly - This function is meant for use from the debugger. It works @@ -198,18 +333,19 @@ void Function::viewCFGOnly() const { if (!CFGFuncName.empty() && !getName().contains(CFGFuncName)) return; - ViewGraph(this, "cfg" + getName(), true); + CFGDOTInfo CFGInfo(this); + ViewGraph(&CFGInfo, "cfg" + getName(), true); } -FunctionPass *llvm::createCFGPrinterLegacyPassPass () { +ModulePass *llvm::createCFGPrinterLegacyPassPass() { return new CFGPrinterLegacyPass(); } -FunctionPass *llvm::createCFGOnlyPrinterLegacyPassPass () { +ModulePass *llvm::createCFGOnlyPrinterLegacyPassPass() { return new CFGOnlyPrinterLegacyPass(); } -void DOTGraphTraits::computeHiddenNodes(const Function *F) { +void DOTGraphTraits::computeHiddenNodes(const Function *F) { auto evaluateBB = [&](const BasicBlock *Node) { if (succ_begin(Node) == succ_end(Node)) { const Instruction *TI = Node->getTerminator(); @@ -228,7 +364,7 @@ evaluateBB); } -bool DOTGraphTraits::isNodeHidden(const BasicBlock *Node) { +bool DOTGraphTraits::isNodeHidden(const BasicBlock *Node) { // If both restricting flags are false, all nodes are displayed. if (!HideUnreachablePaths && !HideDeoptimizePaths) return false; Index: llvm/lib/Analysis/CMakeLists.txt =================================================================== --- llvm/lib/Analysis/CMakeLists.txt +++ llvm/lib/Analysis/CMakeLists.txt @@ -34,6 +34,7 @@ EHPersonalities.cpp GlobalsModRef.cpp GuardUtils.cpp + HeatUtils.cpp IVDescriptors.cpp IVUsers.cpp IndirectCallPromotionAnalysis.cpp Index: llvm/lib/Analysis/CallPrinter.cpp =================================================================== --- llvm/lib/Analysis/CallPrinter.cpp +++ llvm/lib/Analysis/CallPrinter.cpp @@ -14,63 +14,328 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/CallPrinter.h" +#include "llvm/Analysis/BlockFrequencyInfo.h" +#include "llvm/Analysis/BranchProbabilityInfo.h" #include "llvm/Analysis/CallGraph.h" #include "llvm/Analysis/DOTGraphTraitsPass.h" +#include "llvm/Analysis/HeatUtils.h" +#include "llvm/Support/CommandLine.h" #include "llvm/InitializePasses.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallSet.h" using namespace llvm; +static cl::opt ShowHeatColors("callgraph-heat-colors", cl::init(false), + cl::Hidden, + cl::desc("Show heat colors in call-graph")); + +static cl::opt + EstimateEdgeWeight("callgraph-weights", cl::init(false), cl::Hidden, + cl::desc("Show edges labeled with weights")); + +static cl::opt + CallMultiGraph("call-multigraph", cl::init(false), cl::Hidden, + cl::desc("Show call-multigraph (do not remove parallel edges)")); + +static cl::opt UseCallCounter( + "callgraph-call-count", cl::init(false), cl::Hidden, + cl::desc("Use function's call counter as a heat metric. " + "The default is the function's maximum block frequency.")); + namespace llvm { -template <> struct DOTGraphTraits : public DefaultDOTGraphTraits { - DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} +class CallGraphDOTInfo { +private: + Module *M; + CallGraph *CG; + DenseMap Freq; + uint64_t MaxFreq; + uint64_t MaxEdgeCount; + +public: + std::function LookupBFI; + + CallGraphDOTInfo(Module *M, CallGraph *CG, + function_ref LookupBFI) + : M(M), CG(CG), LookupBFI(LookupBFI) { + MaxFreq = 0; + MaxEdgeCount = 0; + + for (Function &F : *M) { + Freq[&F] = 0; + + if (F.isDeclaration()) + continue; + uint64_t localMaxFreq = 0; + if (UseCallCounter) { + Function::ProfileCount EntryCount = F.getEntryCount(); + if (EntryCount.hasValue()) + localMaxFreq = EntryCount.getCount(); + } else { + localMaxFreq = llvm::getMaxFreq(F, LookupBFI(F)); + } + if (localMaxFreq >= MaxFreq) + MaxFreq = localMaxFreq; + Freq[&F] = localMaxFreq; + + if (!CallMultiGraph) { + for (Function &Callee : *M) { + uint64_t Counter = getNumOfCalls(F, Callee, LookupBFI); + if (Counter > MaxEdgeCount) { + MaxEdgeCount = Counter; + } + } + } + } + if (!CallMultiGraph) + removeParallelEdges(); + } + + Module *getModule() const { return M; } + CallGraph *getCallGraph() const { return CG; } + + uint64_t getFreq(const Function *F) { return Freq[F]; } + + uint64_t getMaxFreq() { return MaxFreq; } + + uint64_t getMaxEdgeCount() { return MaxEdgeCount; } + +private: + void removeParallelEdges() { + for (auto &I : (*CG)) { + CallGraphNode *Node = I.second.get(); + + bool FoundParallelEdge = true; + while (FoundParallelEdge) { + SmallSet Visited; + FoundParallelEdge = false; + for (auto CI = Node->begin(), CE = Node->end(); CI != CE; CI++) { + if (!Visited.count(CI->second->getFunction())) + Visited.insert(CI->second->getFunction()); + else { + FoundParallelEdge = true; + Node->removeCallEdge(CI); + break; + } + } + } + } + } +}; + +template <> +struct GraphTraits + : public GraphTraits { + static NodeRef getEntryNode(CallGraphDOTInfo *CGInfo) { + // Start at the external node! + return CGInfo->getCallGraph()->getExternalCallingNode(); + } + + typedef std::pair> + PairTy; + static const CallGraphNode *CGGetValuePtr(const PairTy &P) { + return P.second.get(); + } + + // nodes_iterator/begin/end - Allow iteration over all nodes in the graph + typedef mapped_iterator + nodes_iterator; + + static nodes_iterator nodes_begin(CallGraphDOTInfo *CGInfo) { + return nodes_iterator(CGInfo->getCallGraph()->begin(), &CGGetValuePtr); + } + static nodes_iterator nodes_end(CallGraphDOTInfo *CGInfo) { + return nodes_iterator(CGInfo->getCallGraph()->end(), &CGGetValuePtr); + } +}; - static std::string getGraphName(CallGraph *Graph) { return "Call graph"; } +template <> +struct DOTGraphTraits : public DefaultDOTGraphTraits { + + SmallSet VisitedCallSites; DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} + + static std::string getGraphName(CallGraphDOTInfo *CGInfo) { + return "Call graph: " + + std::string(CGInfo->getModule()->getModuleIdentifier()); + } + + static bool isNodeHidden(const CallGraphNode *Node) { + if (CallMultiGraph) + return false; + + if (Node->getFunction()) + return false; + + return true; + } + + std::string getNodeLabel(const CallGraphNode *Node, + CallGraphDOTInfo *CGInfo) { + if (Node == CGInfo->getCallGraph()->getExternalCallingNode()) + return "external caller"; + + if (Node == CGInfo->getCallGraph()->getCallsExternalNode()) + return "external callee"; - std::string getNodeLabel(CallGraphNode *Node, CallGraph *Graph) { if (Function *Func = Node->getFunction()) return std::string(Func->getName()); return "external node"; } -}; + static const CallGraphNode *CGGetValuePtr(CallGraphNode::CallRecord P) { + return P.second; + } -struct AnalysisCallGraphWrapperPassTraits { - static CallGraph *getGraph(CallGraphWrapperPass *P) { - return &P->getCallGraph(); + // nodes_iterator/begin/end - Allow iteration over all nodes in the graph + typedef mapped_iterator + nodes_iterator; + + std::string getEdgeAttributes(const CallGraphNode *Node, nodes_iterator I, + CallGraphDOTInfo *CGInfo) { + if (!EstimateEdgeWeight) + return ""; + + Function *Caller = Node->getFunction(); + if (Caller == nullptr || Caller->isDeclaration()) + return ""; + + Function *Callee = (*I)->getFunction(); + if (Callee == nullptr) + return ""; + + uint64_t Counter = 0; + if (CallMultiGraph) { + // looks for next call site between Caller and Callee + for (User *U : Callee->users()) { + auto CS = CallSite(U); + if (CS.getCaller() == Caller) { + if (VisitedCallSites.count(U)) + continue; + VisitedCallSites.insert(U); + Counter = getNumOfCalls(CS, CGInfo->LookupBFI); + break; + } + } + } else { + Counter = getNumOfCalls(*Caller, *Callee, CGInfo->LookupBFI); + } + + double Width = + 1 + 2 * (double(Counter) / CGInfo->getMaxEdgeCount()); + std::string Attrs = "label=\"" + std::to_string(Counter) + + "\" penwidth=" + std::to_string(Width); + + return Attrs; + } + + std::string getNodeAttributes(const CallGraphNode *Node, + CallGraphDOTInfo *CGInfo) { + Function *F = Node->getFunction(); + if (F == nullptr || F->isDeclaration()) + return ""; + + std::string attrs = ""; + if (ShowHeatColors) { + uint64_t freq = CGInfo->getFreq(F); + std::string color = getHeatColor(freq, CGInfo->getMaxFreq()); + std::string edgeColor = (freq <= (CGInfo->getMaxFreq() / 2)) + ? getHeatColor(0) + : getHeatColor(1); + + attrs = "color=\"" + edgeColor + "ff\", style=filled, fillcolor=\"" + + color + "80\""; + } + return attrs; } }; -} // end llvm namespace +} // namespace llvm namespace { -struct CallGraphViewer - : public DOTGraphTraitsModuleViewer { +// Viewer + +class CallGraphViewer : public ModulePass { +public: static char ID; + CallGraphViewer() : ModulePass(ID) {} + + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnModule(Module &M) override; + + + - CallGraphViewer() - : DOTGraphTraitsModuleViewer( - "callgraph", ID) { - initializeCallGraphViewerPass(*PassRegistry::getPassRegistry()); - } }; -struct CallGraphDOTPrinter : public DOTGraphTraitsModulePrinter< - CallGraphWrapperPass, true, CallGraph *, - AnalysisCallGraphWrapperPassTraits> { +void CallGraphViewer::getAnalysisUsage(AnalysisUsage &AU) const { + ModulePass::getAnalysisUsage(AU); + AU.addRequired(); + AU.setPreservesAll(); +} + +bool CallGraphViewer::runOnModule(Module &M) { + auto LookupBFI = [this](Function &F) { + return &this->getAnalysis(F).getBFI(); + }; + + CallGraph CG(M); + CallGraphDOTInfo CFGInfo(&M, &CG, LookupBFI); + + std::string Title = + DOTGraphTraits::getGraphName(&CFGInfo); + ViewGraph(&CFGInfo, "callgraph", true, Title); + + return false; +} + +// DOT Printer + +class CallGraphDOTPrinter : public ModulePass { +public: static char ID; + CallGraphDOTPrinter() : ModulePass(ID) {} + + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnModule(Module &M) override; + + + - CallGraphDOTPrinter() - : DOTGraphTraitsModulePrinter( - "callgraph", ID) { - initializeCallGraphDOTPrinterPass(*PassRegistry::getPassRegistry()); - } }; +void CallGraphDOTPrinter::getAnalysisUsage(AnalysisUsage &AU) const { + ModulePass::getAnalysisUsage(AU); + AU.addRequired(); + AU.setPreservesAll(); +} + +bool CallGraphDOTPrinter::runOnModule(Module &M) { + auto LookupBFI = [this](Function &F) { + return &this->getAnalysis(F).getBFI(); + }; + + std::string Filename = + (std::string(M.getModuleIdentifier()) + ".callgraph.dot"); + errs() << "Writing '" << Filename << "'..."; + + std::error_code EC; + raw_fd_ostream File(Filename, EC, sys::fs::F_Text); + + CallGraph CG(M); + CallGraphDOTInfo CFGInfo(&M, &CG, LookupBFI); + + if (!EC) + WriteGraph(File, &CFGInfo); + else + errs() << " error opening file for writing!"; + errs() << "\n"; + + return false; +} + } // end anonymous namespace char CallGraphViewer::ID = 0; Index: llvm/lib/Analysis/DomPrinter.cpp =================================================================== --- llvm/lib/Analysis/DomPrinter.cpp +++ llvm/lib/Analysis/DomPrinter.cpp @@ -25,11 +25,10 @@ using namespace llvm; namespace llvm { -template<> -struct DOTGraphTraits : public DefaultDOTGraphTraits { +template <> +struct DOTGraphTraits : public DefaultDOTGraphTraits { - DOTGraphTraits (bool isSimple=false) - : DefaultDOTGraphTraits(isSimple) {} + DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} std::string getNodeLabel(DomTreeNode *Node, DomTreeNode *Graph) { @@ -38,44 +37,41 @@ if (!BB) return "Post dominance root node"; - if (isSimple()) - return DOTGraphTraits - ::getSimpleNodeLabel(BB, BB->getParent()); + return DOTGraphTraits::getSimpleNodeLabel(BB, nullptr); else - return DOTGraphTraits - ::getCompleteNodeLabel(BB, BB->getParent()); + return DOTGraphTraits::getCompleteNodeLabel(BB, nullptr); } }; -template<> -struct DOTGraphTraits : public DOTGraphTraits { +template <> +struct DOTGraphTraits : public DOTGraphTraits { - DOTGraphTraits (bool isSimple=false) - : DOTGraphTraits(isSimple) {} + DOTGraphTraits(bool isSimple = false) + : DOTGraphTraits(isSimple) {} static std::string getGraphName(DominatorTree *DT) { return "Dominator tree"; } std::string getNodeLabel(DomTreeNode *Node, DominatorTree *G) { - return DOTGraphTraits::getNodeLabel(Node, G->getRootNode()); + return DOTGraphTraits::getNodeLabel(Node, G->getRootNode()); } }; -template<> -struct DOTGraphTraits - : public DOTGraphTraits { +template <> +struct DOTGraphTraits + : public DOTGraphTraits { - DOTGraphTraits (bool isSimple=false) - : DOTGraphTraits(isSimple) {} + DOTGraphTraits(bool isSimple = false) + : DOTGraphTraits(isSimple) {} static std::string getGraphName(PostDominatorTree *DT) { return "Post dominator tree"; } - std::string getNodeLabel(DomTreeNode *Node, PostDominatorTree *G ) { - return DOTGraphTraits::getNodeLabel(Node, G->getRootNode()); + std::string getNodeLabel(DomTreeNode *Node, PostDominatorTree *G) { + return DOTGraphTraits::getNodeLabel(Node, G->getRootNode()); } }; } @@ -85,7 +81,7 @@ ViewGraph(this, Name, false, Title); #else errs() << "DomTree dump not available, build with DEBUG\n"; -#endif // NDEBUG +#endif // NDEBUG } void DominatorTree::viewGraph() { @@ -93,7 +89,7 @@ this->viewGraph("domtree", "Dominator Tree for function"); #else errs() << "DomTree dump not available, build with DEBUG\n"; -#endif // NDEBUG +#endif // NDEBUG } namespace { @@ -103,21 +99,23 @@ } }; -struct DomViewer : public DOTGraphTraitsViewer< - DominatorTreeWrapperPass, false, DominatorTree *, - DominatorTreeWrapperPassAnalysisGraphTraits> { +struct DomViewer + : public DOTGraphTraitsViewer { static char ID; DomViewer() : DOTGraphTraitsViewer( - "dom", ID) { + DominatorTreeWrapperPassAnalysisGraphTraits>("dom", + ID) { initializeDomViewerPass(*PassRegistry::getPassRegistry()); } }; -struct DomOnlyViewer : public DOTGraphTraitsViewer< - DominatorTreeWrapperPass, true, DominatorTree *, - DominatorTreeWrapperPassAnalysisGraphTraits> { +struct DomOnlyViewer + : public DOTGraphTraitsViewer { static char ID; DomOnlyViewer() : DOTGraphTraitsViewer { +struct PostDomViewer + : public DOTGraphTraitsViewer< + PostDominatorTreeWrapperPass, false, PostDominatorTree *, + PostDominatorTreeWrapperPassAnalysisGraphTraits> { static char ID; - PostDomViewer() : - DOTGraphTraitsViewer( - "postdom", ID){ - initializePostDomViewerPass(*PassRegistry::getPassRegistry()); - } + PostDomViewer() + : DOTGraphTraitsViewer( + "postdom", ID) { + initializePostDomViewerPass(*PassRegistry::getPassRegistry()); + } }; -struct PostDomOnlyViewer : public DOTGraphTraitsViewer< - PostDominatorTreeWrapperPass, true, - PostDominatorTree *, - PostDominatorTreeWrapperPassAnalysisGraphTraits> { +struct PostDomOnlyViewer + : public DOTGraphTraitsViewer< + PostDominatorTreeWrapperPass, true, PostDominatorTree *, + PostDominatorTreeWrapperPassAnalysisGraphTraits> { static char ID; - PostDomOnlyViewer() : - DOTGraphTraitsViewer( - "postdomonly", ID){ - initializePostDomOnlyViewerPass(*PassRegistry::getPassRegistry()); - } + PostDomOnlyViewer() + : DOTGraphTraitsViewer( + "postdomonly", ID) { + initializePostDomOnlyViewerPass(*PassRegistry::getPassRegistry()); + } }; } // end anonymous namespace char DomViewer::ID = 0; -INITIALIZE_PASS(DomViewer, "view-dom", - "View dominance tree of function", false, false) +INITIALIZE_PASS(DomViewer, "view-dom", "View dominance tree of function", false, + false) char DomOnlyViewer::ID = 0; INITIALIZE_PASS(DomOnlyViewer, "view-dom-only", @@ -207,42 +205,37 @@ }; struct PostDomPrinter - : public DOTGraphTraitsPrinter< - PostDominatorTreeWrapperPass, false, - PostDominatorTree *, - PostDominatorTreeWrapperPassAnalysisGraphTraits> { + : public DOTGraphTraitsPrinter< + PostDominatorTreeWrapperPass, false, PostDominatorTree *, + PostDominatorTreeWrapperPassAnalysisGraphTraits> { static char ID; - PostDomPrinter() : - DOTGraphTraitsPrinter( - "postdom", ID) { - initializePostDomPrinterPass(*PassRegistry::getPassRegistry()); - } + PostDomPrinter() + : DOTGraphTraitsPrinter( + "postdom", ID) { + initializePostDomPrinterPass(*PassRegistry::getPassRegistry()); + } }; struct PostDomOnlyPrinter - : public DOTGraphTraitsPrinter< - PostDominatorTreeWrapperPass, true, - PostDominatorTree *, - PostDominatorTreeWrapperPassAnalysisGraphTraits> { + : public DOTGraphTraitsPrinter< + PostDominatorTreeWrapperPass, true, PostDominatorTree *, + PostDominatorTreeWrapperPassAnalysisGraphTraits> { static char ID; - PostDomOnlyPrinter() : - DOTGraphTraitsPrinter( - "postdomonly", ID) { - initializePostDomOnlyPrinterPass(*PassRegistry::getPassRegistry()); - } + PostDomOnlyPrinter() + : DOTGraphTraitsPrinter( + "postdomonly", ID) { + initializePostDomOnlyPrinterPass(*PassRegistry::getPassRegistry()); + } }; } // end anonymous namespace - - char DomPrinter::ID = 0; INITIALIZE_PASS(DomPrinter, "dot-dom", - "Print dominance tree of function to 'dot' file", - false, false) + "Print dominance tree of function to 'dot' file", false, false) char DomOnlyPrinter::ID = 0; INITIALIZE_PASS(DomOnlyPrinter, "dot-dom-only", @@ -252,8 +245,8 @@ char PostDomPrinter::ID = 0; INITIALIZE_PASS(PostDomPrinter, "dot-postdom", - "Print postdominance tree of function to 'dot' file", - false, false) + "Print postdominance tree of function to 'dot' file", false, + false) char PostDomOnlyPrinter::ID = 0; INITIALIZE_PASS(PostDomOnlyPrinter, "dot-postdom-only", @@ -265,33 +258,21 @@ // "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by // the link time optimization. -FunctionPass *llvm::createDomPrinterPass() { - return new DomPrinter(); -} +FunctionPass *llvm::createDomPrinterPass() { return new DomPrinter(); } -FunctionPass *llvm::createDomOnlyPrinterPass() { - return new DomOnlyPrinter(); -} +FunctionPass *llvm::createDomOnlyPrinterPass() { return new DomOnlyPrinter(); } -FunctionPass *llvm::createDomViewerPass() { - return new DomViewer(); -} +FunctionPass *llvm::createDomViewerPass() { return new DomViewer(); } -FunctionPass *llvm::createDomOnlyViewerPass() { - return new DomOnlyViewer(); -} +FunctionPass *llvm::createDomOnlyViewerPass() { return new DomOnlyViewer(); } -FunctionPass *llvm::createPostDomPrinterPass() { - return new PostDomPrinter(); -} +FunctionPass *llvm::createPostDomPrinterPass() { return new PostDomPrinter(); } FunctionPass *llvm::createPostDomOnlyPrinterPass() { return new PostDomOnlyPrinter(); } -FunctionPass *llvm::createPostDomViewerPass() { - return new PostDomViewer(); -} +FunctionPass *llvm::createPostDomViewerPass() { return new PostDomViewer(); } FunctionPass *llvm::createPostDomOnlyViewerPass() { return new PostDomOnlyViewer(); Index: llvm/lib/Analysis/HeatUtils.cpp =================================================================== --- /dev/null +++ llvm/lib/Analysis/HeatUtils.cpp @@ -0,0 +1,103 @@ +//===-- HeatUtils.cpp - Utility for printing heat colors --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Utility for printing heat colors based on heuristics or profiling +// information. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/HeatUtils.h" +#include "llvm/IR/Instructions.h" + +namespace llvm { + +static const unsigned heatSize = 100; +static const std::string heatPalette[heatSize] = { + "#3d50c3", "#4055c8", "#4358cb", "#465ecf", "#4961d2", "#4c66d6", "#4f69d9", + "#536edd", "#5572df", "#5977e3", "#5b7ae5", "#5f7fe8", "#6282ea", "#6687ed", + "#6a8bef", "#6c8ff1", "#7093f3", "#7396f5", "#779af7", "#7a9df8", "#7ea1fa", + "#81a4fb", "#85a8fc", "#88abfd", "#8caffe", "#8fb1fe", "#93b5fe", "#96b7ff", + "#9abbff", "#9ebeff", "#a1c0ff", "#a5c3fe", "#a7c5fe", "#abc8fd", "#aec9fc", + "#b2ccfb", "#b5cdfa", "#b9d0f9", "#bbd1f8", "#bfd3f6", "#c1d4f4", "#c5d6f2", + "#c7d7f0", "#cbd8ee", "#cedaeb", "#d1dae9", "#d4dbe6", "#d6dce4", "#d9dce1", + "#dbdcde", "#dedcdb", "#e0dbd8", "#e3d9d3", "#e5d8d1", "#e8d6cc", "#ead5c9", + "#ecd3c5", "#eed0c0", "#efcebd", "#f1ccb8", "#f2cab5", "#f3c7b1", "#f4c5ad", + "#f5c1a9", "#f6bfa6", "#f7bca1", "#f7b99e", "#f7b599", "#f7b396", "#f7af91", + "#f7ac8e", "#f7a889", "#f6a385", "#f5a081", "#f59c7d", "#f4987a", "#f39475", + "#f29072", "#f08b6e", "#ef886b", "#ed8366", "#ec7f63", "#e97a5f", "#e8765c", + "#e57058", "#e36c55", "#e16751", "#de614d", "#dc5d4a", "#d85646", "#d65244", + "#d24b40", "#d0473d", "#cc403a", "#ca3b37", "#c53334", "#c32e31", "#be242e", + "#bb1b2c", "#b70d28"}; + +uint64_t +getNumOfCalls(CallSite &CS, + function_ref LookupBFI) { + if (CS.getInstruction() == nullptr) + return 0; + if (CS.getInstruction()->getParent() == nullptr) + return 0; + BasicBlock *BB = CS.getInstruction()->getParent(); + return LookupBFI(*CS.getCaller())->getBlockFreq(BB).getFrequency(); +} + +uint64_t +getNumOfCalls(Function &callerFunction, Function &calledFunction, + function_ref LookupBFI) { + uint64_t counter = 0; + for (User *U : calledFunction.users()) { + if (isa(U)) { + auto CS = CallSite(U); + if (CS.getCaller() == (&callerFunction)) { + counter += getNumOfCalls(CS, LookupBFI); + } + } + } + return counter; +} + +uint64_t getMaxFreq(const Function &F, const BlockFrequencyInfo *BFI) { + uint64_t maxFreq = 0; + for (const BasicBlock &BB : F) { + uint64_t freqVal = BFI->getBlockFreq(&BB).getFrequency(); + if (freqVal >= maxFreq) + maxFreq = freqVal; + } + return maxFreq; +} + +uint64_t getMaxFreq(Module &M, + function_ref LookupBFI) { + uint64_t maxFreq = 0; + for (auto &F : M) { + if (F.isDeclaration()) + continue; + uint64_t localMaxFreq = getMaxFreq(F, LookupBFI(F)); + if (localMaxFreq >= maxFreq) + maxFreq = localMaxFreq; + } + return maxFreq; +} + +std::string getHeatColor(uint64_t freq, uint64_t maxFreq) { + if (freq > maxFreq) + freq = maxFreq; + double percent = log2(double(freq)) / log2(maxFreq); + return getHeatColor(percent); +} + +std::string getHeatColor(double percent) { + if (percent > 1.0) + percent = 1.0; + if (percent < 0.0) + percent = 0.0; + unsigned colorId = unsigned(round(percent * (heatSize - 1.0))); + return heatPalette[colorId]; +} + +} // namespace llvm \ No newline at end of file Index: llvm/lib/Analysis/RegionPrinter.cpp =================================================================== --- llvm/lib/Analysis/RegionPrinter.cpp +++ llvm/lib/Analysis/RegionPrinter.cpp @@ -28,18 +28,15 @@ //===----------------------------------------------------------------------===// /// onlySimpleRegion - Show only the simple regions in the RegionViewer. -static cl::opt -onlySimpleRegions("only-simple-regions", - cl::desc("Show only simple regions in the graphviz viewer"), - cl::Hidden, - cl::init(false)); +static cl::opt onlySimpleRegions( + "only-simple-regions", + cl::desc("Show only simple regions in the graphviz viewer"), cl::Hidden, + cl::init(false)); namespace llvm { -template<> -struct DOTGraphTraits : public DefaultDOTGraphTraits { +template <> struct DOTGraphTraits : public DefaultDOTGraphTraits { - DOTGraphTraits (bool isSimple=false) - : DefaultDOTGraphTraits(isSimple) {} + DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} std::string getNodeLabel(RegionNode *Node, RegionNode *Graph) { @@ -47,11 +44,9 @@ BasicBlock *BB = Node->getNodeAs(); if (isSimple()) - return DOTGraphTraits - ::getSimpleNodeLabel(BB, BB->getParent()); + return DOTGraphTraits::getSimpleNodeLabel(BB, nullptr); else - return DOTGraphTraits - ::getCompleteNodeLabel(BB, BB->getParent()); + return DOTGraphTraits::getCompleteNodeLabel(BB, nullptr); } return "Not implemented"; @@ -61,8 +56,8 @@ template <> struct DOTGraphTraits : public DOTGraphTraits { - DOTGraphTraits (bool isSimple = false) - : DOTGraphTraits(isSimple) {} + DOTGraphTraits(bool isSimple = false) + : DOTGraphTraits(isSimple) {} static std::string getGraphName(const RegionInfo *) { return "Region Graph"; } @@ -102,31 +97,32 @@ static void printRegionCluster(const Region &R, GraphWriter &GW, unsigned depth = 0) { raw_ostream &O = GW.getOStream(); - O.indent(2 * depth) << "subgraph cluster_" << static_cast(&R) - << " {\n"; + O.indent(2 * depth) << "subgraph cluster_" << static_cast(&R) + << " {\n"; O.indent(2 * (depth + 1)) << "label = \"\";\n"; if (!onlySimpleRegions || R.isSimple()) { O.indent(2 * (depth + 1)) << "style = filled;\n"; - O.indent(2 * (depth + 1)) << "color = " - << ((R.getDepth() * 2 % 12) + 1) << "\n"; + O.indent(2 * (depth + 1)) + << "color = " << ((R.getDepth() * 2 % 12) + 1) << "\n"; } else { O.indent(2 * (depth + 1)) << "style = solid;\n"; - O.indent(2 * (depth + 1)) << "color = " - << ((R.getDepth() * 2 % 12) + 2) << "\n"; + O.indent(2 * (depth + 1)) + << "color = " << ((R.getDepth() * 2 % 12) + 2) << "\n"; } for (const auto &RI : R) printRegionCluster(*RI, GW, depth + 1); - const RegionInfo &RI = *static_cast(R.getRegionInfo()); + const RegionInfo &RI = *static_cast(R.getRegionInfo()); for (auto *BB : R.blocks()) if (RI.getRegionFor(BB) == &R) - O.indent(2 * (depth + 1)) << "Node" - << static_cast(RI.getTopLevelRegion()->getBBNode(BB)) - << ";\n"; + O.indent(2 * (depth + 1)) + << "Node" + << static_cast(RI.getTopLevelRegion()->getBBNode(BB)) + << ";\n"; O.indent(2 * depth) << "}\n"; } @@ -138,7 +134,7 @@ printRegionCluster(*G->getTopLevelRegion(), GW, 4); } }; -} //end namespace llvm +} // end namespace llvm namespace { @@ -196,7 +192,7 @@ }; char RegionOnlyViewer::ID = 0; -} //end anonymous namespace +} // end anonymous namespace INITIALIZE_PASS(RegionPrinter, "dot-regions", "Print regions of function to 'dot' file", true, true) @@ -206,12 +202,12 @@ "Print regions of function to 'dot' file (with no function bodies)", true, true) -INITIALIZE_PASS(RegionViewer, "view-regions", "View regions of function", - true, true) +INITIALIZE_PASS(RegionViewer, "view-regions", "View regions of function", true, + true) INITIALIZE_PASS(RegionOnlyViewer, "view-regions-only", - "View regions of function (with no function bodies)", - true, true) + "View regions of function (with no function bodies)", true, + true) FunctionPass *llvm::createRegionPrinterPass() { return new RegionPrinter(); } @@ -219,11 +215,9 @@ return new RegionOnlyPrinter(); } -FunctionPass* llvm::createRegionViewerPass() { - return new RegionViewer(); -} +FunctionPass *llvm::createRegionViewerPass() { return new RegionViewer(); } -FunctionPass* llvm::createRegionOnlyViewerPass() { +FunctionPass *llvm::createRegionOnlyViewerPass() { return new RegionOnlyViewer(); } Index: llvm/lib/Passes/PassRegistry.def =================================================================== --- llvm/lib/Passes/PassRegistry.def +++ llvm/lib/Passes/PassRegistry.def @@ -47,6 +47,8 @@ MODULE_PASS("constmerge", ConstantMergePass()) MODULE_PASS("cross-dso-cfi", CrossDSOCFIPass()) MODULE_PASS("deadargelim", DeadArgumentEliminationPass()) +MODULE_PASS("dot-cfg", CFGPrinterPass()) +MODULE_PASS("dot-cfg-only", CFGOnlyPrinterPass()) MODULE_PASS("elim-avail-extern", EliminateAvailableExternallyPass()) MODULE_PASS("forceattrs", ForceFunctionAttrsPass()) MODULE_PASS("function-import", FunctionImportPass()) @@ -92,6 +94,8 @@ MODULE_PASS("kasan-module", ModuleAddressSanitizerPass(/*CompileKernel=*/true, false, true, false)) MODULE_PASS("sancov-module", ModuleSanitizerCoveragePass()) MODULE_PASS("poison-checking", PoisonCheckingPass()) +MODULE_PASS("view-cfg", CFGViewerPass()) +MODULE_PASS("view-cfg-only", CFGOnlyViewerPass()) #undef MODULE_PASS #ifndef CGSCC_ANALYSIS @@ -178,8 +182,6 @@ FUNCTION_PASS("dce", DCEPass()) FUNCTION_PASS("div-rem-pairs", DivRemPairsPass()) FUNCTION_PASS("dse", DSEPass()) -FUNCTION_PASS("dot-cfg", CFGPrinterPass()) -FUNCTION_PASS("dot-cfg-only", CFGOnlyPrinterPass()) FUNCTION_PASS("early-cse", EarlyCSEPass(/*UseMemorySSA=*/false)) FUNCTION_PASS("early-cse-memssa", EarlyCSEPass(/*UseMemorySSA=*/true)) FUNCTION_PASS("ee-instrument", EntryExitInstrumenterPass(/*PostInlining=*/false)) @@ -252,8 +254,6 @@ FUNCTION_PASS("verify", RegionInfoVerifierPass()) FUNCTION_PASS("verify", SafepointIRVerifierPass()) FUNCTION_PASS("verify", ScalarEvolutionVerifierPass()) -FUNCTION_PASS("view-cfg", CFGViewerPass()) -FUNCTION_PASS("view-cfg-only", CFGOnlyViewerPass()) FUNCTION_PASS("transform-warning", WarnMissedTransformationsPass()) FUNCTION_PASS("asan", AddressSanitizerPass(false, false, false)) FUNCTION_PASS("kasan", AddressSanitizerPass(true, false, false)) Index: llvm/lib/Transforms/Scalar/NewGVN.cpp =================================================================== --- llvm/lib/Transforms/Scalar/NewGVN.cpp +++ llvm/lib/Transforms/Scalar/NewGVN.cpp @@ -898,7 +898,7 @@ #ifndef NDEBUG static std::string getBlockName(const BasicBlock *B) { - return DOTGraphTraits::getSimpleNodeLabel(B, nullptr); + return DOTGraphTraits::getSimpleNodeLabel(B, nullptr); } #endif @@ -1261,10 +1261,11 @@ bool NewGVN::someEquivalentDominates(const Instruction *Inst, const Instruction *U) const { auto *CC = ValueToClass.lookup(Inst); - // This must be an instruction because we are only called from phi nodes + // This must be an instruction because we are only called from phi nodes // in the case that the value it needs to check against is an instruction. - // The most likely candidates for dominance are the leader and the next leader. + // The most likely candidates for dominance are the leader and the next + // leader. // The leader or nextleader will dominate in all cases where there is an // equivalent that is higher up in the dom tree. // We can't *only* check them, however, because the @@ -1736,8 +1737,7 @@ // Evaluate PHI nodes symbolically and create an expression result. const Expression * -NewGVN::performSymbolicPHIEvaluation(ArrayRef PHIOps, - Instruction *I, +NewGVN::performSymbolicPHIEvaluation(ArrayRef PHIOps, Instruction *I, BasicBlock *PHIBlock) const { // True if one of the incoming phi edges is a backedge. bool HasBackedge = false; @@ -2785,9 +2785,9 @@ // constant. For anything where that is true, and unsafe, we should // have made a phi-of-ops (or value numbered it equivalent to something) // for the pieces already. - FoundVal = !SafeForPHIOfOps ? nullptr - : findLeaderForInst(ValueOp, Visited, - MemAccess, I, PredBB); + FoundVal = + !SafeForPHIOfOps ? nullptr : findLeaderForInst(ValueOp, Visited, + MemAccess, I, PredBB); ValueOp->deleteValue(); if (!FoundVal) { // We failed to find a leader for the current ValueOp, but this might Index: llvm/test/Other/2007-06-05-PassID.ll =================================================================== --- llvm/test/Other/2007-06-05-PassID.ll +++ llvm/test/Other/2007-06-05-PassID.ll @@ -1,5 +1,13 @@ ;RUN: opt < %s -analyze -dot-cfg-only 2>/dev/null ;RUN: opt < %s -analyze -passes=dot-cfg-only 2>/dev/null +;RUN: opt < %s -analyze -dot-cfg-only \ +;RUN: -cfg-heat-colors=true -cfg-weights=true 2>/dev/null +;RUN: opt < %s -analyze -dot-cfg-only \ +;RUN: -cfg-heat-colors=false -cfg-weights=false 2>/dev/null +;RUN: opt < %s -analyze -dot-cfg \ +;RUN: -cfg-heat-colors=true -cfg-weights=true 2>/dev/null +;RUN: opt < %s -analyze -dot-cfg \ +;RUN: -cfg-heat-colors=false -cfg-weights=false 2>/dev/null ;PR 1497 define void @foo() { Index: llvm/test/Other/cfg-printer-branch-weights-percent.ll =================================================================== --- /dev/null +++ llvm/test/Other/cfg-printer-branch-weights-percent.ll @@ -0,0 +1,19 @@ +;RUN: opt < %s -analyze -dot-cfg -cfg-weights -cfg-dot-filename-prefix=%t 2>/dev/null +;RUN: FileCheck %s -input-file=%t.f.dot + +define void @f(i32) { +entry: + %check = icmp sgt i32 %0, 0 + br i1 %check, label %if, label %exit, !prof !0 + +; CHECK: label="0.50%" +; CHECK-NOT: ["]; +if: ; preds = %entry + br label %exit +; CHECK: label="99.50%" +; CHECK-NOT: ["]; +exit: ; preds = %entry, %if + ret void +} + +!0 = !{!"branch_weights", i32 1, i32 200} Index: llvm/test/Other/cfg-printer-branch-weights.ll =================================================================== --- llvm/test/Other/cfg-printer-branch-weights.ll +++ llvm/test/Other/cfg-printer-branch-weights.ll @@ -1,4 +1,4 @@ -;RUN: opt < %s -analyze -dot-cfg -cfg-dot-filename-prefix=%t 2>/dev/null +;RUN: opt < %s -analyze -dot-cfg -cfg-weights -cfg-raw-weights -cfg-dot-filename-prefix=%t 2>/dev/null ;RUN: FileCheck %s -input-file=%t.f.dot define void @f(i32) { @@ -6,11 +6,11 @@ %check = icmp sgt i32 %0, 0 br i1 %check, label %if, label %exit, !prof !0 -; CHECK: label="W:1" +; CHECK: label="W:7" ; CHECK-NOT: ["]; if: ; preds = %entry br label %exit -; CHECK: label="W:200" +; CHECK: label="W:1600" ; CHECK-NOT: ["]; exit: ; preds = %entry, %if ret void Index: polly/lib/Analysis/ScopGraphPrinter.cpp =================================================================== --- polly/lib/Analysis/ScopGraphPrinter.cpp +++ polly/lib/Analysis/ScopGraphPrinter.cpp @@ -68,11 +68,10 @@ BasicBlock *BB = Node->getNodeAs(); if (isSimple()) - return DOTGraphTraits::getSimpleNodeLabel( - BB, BB->getParent()); + return DOTGraphTraits::getSimpleNodeLabel(BB, nullptr); + else - return DOTGraphTraits::getCompleteNodeLabel( - BB, BB->getParent()); + return DOTGraphTraits::getCompleteNodeLabel(BB, nullptr); } return "Not implemented"; Index: polly/lib/Support/RegisterPasses.cpp =================================================================== --- polly/lib/Support/RegisterPasses.cpp +++ polly/lib/Support/RegisterPasses.cpp @@ -528,9 +528,6 @@ assert(!DumpAfter && "This option is not implemented"); assert(DumpAfterFile.empty() && "This option is not implemented"); - - if (CFGPrinter) - PM.addPass(llvm::CFGPrinterPass()); } /// Register Polly to be available as an optimizer @@ -703,7 +700,8 @@ MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); if (VerifyEachPass) MPM.addPass(VerifierPass()); - + if (CFGPrinter) + MPM.addPass(llvm::CFGPrinterPass()); return true; }