Index: llvm/include/llvm/Analysis/CFGPrinter.h =================================================================== --- llvm/include/llvm/Analysis/CFGPrinter.h +++ llvm/include/llvm/Analysis/CFGPrinter.h @@ -18,11 +18,15 @@ #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/PassManager.h" +#include "llvm/Support/FormatVariadic.h" #include "llvm/Support/GraphWriter.h" namespace llvm { @@ -50,20 +54,86 @@ PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; -template<> -struct DOTGraphTraits : public DefaultDOTGraphTraits { +class CFGDOTInfo { +private: + const Function *F; + const BlockFrequencyInfo *BFI; + const BranchProbabilityInfo *BPI; + uint64_t MaxFreq; + bool ShowHeat; + 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; + 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 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 +145,7 @@ } static std::string getCompleteNodeLabel(const BasicBlock *Node, - const Function *) { + CFGDOTInfo *) { enum { MaxColumns = 80 }; std::string Str; raw_string_ostream OS(Str); @@ -120,11 +190,12 @@ } std::string getNodeLabel(const BasicBlock *Node, - const Function *Graph) { + 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, @@ -151,11 +222,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,17 +262,31 @@ 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)); + } - // 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(); + std::string getNodeAttributes(const BasicBlock *Node, CFGDOTInfo *CFGInfo) { + + if (!CFGInfo->showHeatColors()) + return ""; + + 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); Index: llvm/include/llvm/Analysis/HeatUtils.h =================================================================== --- /dev/null +++ llvm/include/llvm/Analysis/HeatUtils.h @@ -0,0 +1,48 @@ +//===-- 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 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 { + +// Returns number of calls of calledFunction by callerFunction. +uint64_t +getNumOfCalls(Function &callerFunction, Function &calledFunction, + function_ref LookupBFI); + +// Returns number of calls from the call-site. +uint64_t +getNumOfCalls(CallSite &callsite, + function_ref LookupBFI); + +// Returns the maximum frequency of a BB in a function. +uint64_t getMaxFreq(const Function &F, const BlockFrequencyInfo *BFI); + +// Calculates heat color based on current and maximum frequencies. +std::string getHeatColor(uint64_t freq, uint64_t maxFreq); + +// Calculates heat color based on percent of "hotness". +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 @@ -42,6 +42,51 @@ static cl::opt HideDeoptimizePaths("cfg-hide-deoptimize-paths", cl::init(false)); +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 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.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 viewHeatCFG(Function &F, BlockFrequencyInfo *BFI, + BranchProbabilityInfo *BPI, uint64_t MaxFreq, + bool isSimple) { + CFGDOTInfo CFGInfo(&F, BFI, BPI, MaxFreq); + CFGInfo.setHeatColors(ShowHeatColors); + CFGInfo.setEdgeWeights(ShowEdgeWeight); + CFGInfo.setRawEdgeWeights(UseRawEdgeWeight); + + ViewGraph(&CFGInfo, "cfg." + F.getName(), isSimple); +} + namespace { struct CFGViewerLegacyPass : public FunctionPass { static char ID; // Pass identifcation, replacement for typeid @@ -50,13 +95,18 @@ } bool runOnFunction(Function &F) override { - F.viewCFG(); + auto *BPI = &getAnalysis().getBPI(); + auto *BFI = &getAnalysis().getBFI(); + viewHeatCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*isSimple=*/false); return false; } void print(raw_ostream &OS, const Module* = nullptr) const override {} void getAnalysisUsage(AnalysisUsage &AU) const override { + FunctionPass::getAnalysisUsage(AU); // Maybe Change to FunctionPass::... + AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } }; @@ -67,7 +117,9 @@ PreservedAnalyses CFGViewerPass::run(Function &F, FunctionAnalysisManager &AM) { - F.viewCFG(); + auto *BFI = &AM.getResult(F); + auto *BPI = &AM.getResult(F); + viewHeatCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*isSimple=*/false); return PreservedAnalyses::all(); } @@ -80,13 +132,18 @@ } bool runOnFunction(Function &F) override { - F.viewCFGOnly(); + auto *BPI = &getAnalysis().getBPI(); + auto *BFI = &getAnalysis().getBFI(); + viewHeatCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*isSimple=*/false); return false; } void print(raw_ostream &OS, const Module* = nullptr) const override {} void getAnalysisUsage(AnalysisUsage &AU) const override { + FunctionPass::getAnalysisUsage(AU); + AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } }; @@ -98,27 +155,12 @@ PreservedAnalyses CFGOnlyViewerPass::run(Function &F, FunctionAnalysisManager &AM) { - F.viewCFGOnly(); + auto *BFI = &AM.getResult(F); + auto *BPI = &AM.getResult(F); + viewHeatCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*isSimple=*/false); 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 { static char ID; // Pass identification, replacement for typeid @@ -127,13 +169,18 @@ } bool runOnFunction(Function &F) override { - writeCFGToDotFile(F); + auto *BPI = &getAnalysis().getBPI(); + auto *BFI = &getAnalysis().getBFI(); + writeHeatCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*isSimple=*/false); return false; } void print(raw_ostream &OS, const Module* = nullptr) const override {} void getAnalysisUsage(AnalysisUsage &AU) const override { + FunctionPass::getAnalysisUsage(AU); + AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } }; @@ -145,7 +192,9 @@ PreservedAnalyses CFGPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { - writeCFGToDotFile(F); + auto *BFI = &AM.getResult(F); + auto *BPI = &AM.getResult(F); + writeHeatCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*isSimple=*/false); return PreservedAnalyses::all(); } @@ -157,12 +206,17 @@ } bool runOnFunction(Function &F) override { - writeCFGToDotFile(F, /*CFGOnly=*/true); + auto *BPI = &getAnalysis().getBPI(); + auto *BFI = &getAnalysis().getBFI(); + writeHeatCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*isSimple=*/false); return false; } void print(raw_ostream &OS, const Module* = nullptr) const override {} void getAnalysisUsage(AnalysisUsage &AU) const override { + FunctionPass::getAnalysisUsage(AU); + AU.addRequired(); + AU.addRequired(); AU.setPreservesAll(); } }; @@ -175,7 +229,9 @@ PreservedAnalyses CFGOnlyPrinterPass::run(Function &F, FunctionAnalysisManager &AM) { - writeCFGToDotFile(F, /*CFGOnly=*/true); + auto *BFI = &AM.getResult(F); + auto *BPI = &AM.getResult(F); + writeHeatCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*isSimple=*/false); return PreservedAnalyses::all(); } @@ -187,7 +243,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,7 +255,8 @@ 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 () { @@ -209,7 +267,7 @@ 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 +286,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,30 +14,247 @@ //===----------------------------------------------------------------------===// #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.")); + +static cl::opt CallGraphDotFilenamePrefix( + "callgraph-dot-filename-prefix", cl::Hidden, + cl::desc("The prefix used for the CallGraph dot file names.")); + 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 (auto F = M->getFunctionList().begin(); F != M->getFunctionList().end(); ++F) { + for (auto pairF = F; pairF != M->getFunctionList().end(); ++pairF) { + uint64_t Counter = getNumOfCalls(*F, *pairF, LookupBFI); + if (Counter > MaxEdgeCount) + MaxEdgeCount = Counter; + Counter = getNumOfCalls(*pairF, *F, LookupBFI); + if (Counter > MaxEdgeCount) + MaxEdgeCount = Counter; + } + } + 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; } }; @@ -45,32 +262,90 @@ 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; + if (!CallGraphDotFilenamePrefix.empty()) + Filename = (CallGraphDotFilenamePrefix + ".callgraph.dot"); + else + 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 @@ -40,11 +40,11 @@ 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); } }; Index: llvm/lib/Analysis/HeatUtils.cpp =================================================================== --- /dev/null +++ llvm/lib/Analysis/HeatUtils.cpp @@ -0,0 +1,90 @@ +//===-- 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; +} + +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 @@ -47,11 +47,11 @@ 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: 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 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: llvm/test/Other/heat-colors-graphs.ll =================================================================== --- /dev/null +++ llvm/test/Other/heat-colors-graphs.ll @@ -0,0 +1,21 @@ +; RUN: opt < %s -analyze -dot-cfg -cfg-heat-colors -cfg-dot-filename-prefix=%t 2>/dev/null +; RUN: FileCheck %s -input-file=%t.f.dot --check-prefixes=CHECK-CFG,CHECK-BOTH +; RUN: opt %s -dot-callgraph -callgraph-heat-colors -callgraph-dot-filename-prefix=%t 2>/dev/null +; RUN: FileCheck %s -input-file=%t.callgraph.dot --check-prefix=CHECK-BOTH + +; CHECK-BOTH: color="#{{[(a-z)(0-9)]+}}", style={{[a-z]+}}, fillcolor="#{{[(a-z)(0-9)]+}}" +; CHECK-CFG: color="#{{[(a-z)(0-9)]+}}", style={{[a-z]+}}, fillcolor="#{{[(a-z)(0-9)]+}}" +; CHECK-CFG: color="#{{[(a-z)(0-9)]+}}", style={{[a-z]+}}, fillcolor="#{{[(a-z)(0-9)]+}}" + +define void @f(i32) { +entry: + %check = icmp sgt i32 %0, 0 + br i1 %check, label %if, label %exit, !prof !0 + +if: ; preds = %entry + br label %exit +exit: ; preds = %entry, %if + ret void +} + +!0 = !{!"branch_weights", i32 1, i32 200} Index: llvm/test/Other/heat-colors-multigraph.ll =================================================================== --- /dev/null +++ llvm/test/Other/heat-colors-multigraph.ll @@ -0,0 +1,16 @@ +; RUN: opt %s -dot-callgraph -call-multigraph -callgraph-dot-filename-prefix=%t 2>/dev/null +; RUN: FileCheck %s -input-file=%t.callgraph.dot --check-prefix=CHECK-MULTIGRAPH +; RUN: opt %s -dot-callgraph -callgraph-dot-filename-prefix=%t 2>/dev/null +; RUN: FileCheck %s -input-file=%t.callgraph.dot --check-prefix=CHECK + +; CHECK-MULTIGRAPH: {external caller} +; CHECK-NOT: {external caller} + +define void @bar() { + ret void +} + +define void @foo() { + call void @bar() + 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";