10b57cec5SDimitry Andric //===- CFGPrinter.cpp - DOT printer for the control flow graph ------------===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric // This file defines a `-dot-cfg` analysis pass, which emits the
100b57cec5SDimitry Andric // `<prefix>.<fnname>.dot` file for each function in the program, with a graph
110b57cec5SDimitry Andric // of the CFG for that function. The default value for `<prefix>` is `cfg` but
120b57cec5SDimitry Andric // can be customized as needed.
130b57cec5SDimitry Andric //
140b57cec5SDimitry Andric // The other main feature of this file is that it implements the
150b57cec5SDimitry Andric // Function::viewCFG method, which is useful for debugging passes which operate
160b57cec5SDimitry Andric // on the CFG.
170b57cec5SDimitry Andric //
180b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
190b57cec5SDimitry Andric
200b57cec5SDimitry Andric #include "llvm/Analysis/CFGPrinter.h"
215ffd83dbSDimitry Andric #include "llvm/ADT/PostOrderIterator.h"
22480093f4SDimitry Andric #include "llvm/Support/CommandLine.h"
230b57cec5SDimitry Andric #include "llvm/Support/FileSystem.h"
2481ad6265SDimitry Andric #include "llvm/Support/GraphWriter.h"
255ffd83dbSDimitry Andric
260b57cec5SDimitry Andric using namespace llvm;
270b57cec5SDimitry Andric
285ffd83dbSDimitry Andric static cl::opt<std::string>
295ffd83dbSDimitry Andric CFGFuncName("cfg-func-name", cl::Hidden,
300b57cec5SDimitry Andric cl::desc("The name of a function (or its substring)"
310b57cec5SDimitry Andric " whose CFG is viewed/printed."));
320b57cec5SDimitry Andric
330b57cec5SDimitry Andric static cl::opt<std::string> CFGDotFilenamePrefix(
340b57cec5SDimitry Andric "cfg-dot-filename-prefix", cl::Hidden,
350b57cec5SDimitry Andric cl::desc("The prefix used for the CFG dot file names."));
360b57cec5SDimitry Andric
375ffd83dbSDimitry Andric static cl::opt<bool> HideUnreachablePaths("cfg-hide-unreachable-paths",
385ffd83dbSDimitry Andric cl::init(false));
395ffd83dbSDimitry Andric
405ffd83dbSDimitry Andric static cl::opt<bool> HideDeoptimizePaths("cfg-hide-deoptimize-paths",
415ffd83dbSDimitry Andric cl::init(false));
425ffd83dbSDimitry Andric
43fe6060f1SDimitry Andric static cl::opt<double> HideColdPaths(
44fe6060f1SDimitry Andric "cfg-hide-cold-paths", cl::init(0.0),
45fe6060f1SDimitry Andric cl::desc("Hide blocks with relative frequency below the given value"));
46fe6060f1SDimitry Andric
475ffd83dbSDimitry Andric static cl::opt<bool> ShowHeatColors("cfg-heat-colors", cl::init(true),
485ffd83dbSDimitry Andric cl::Hidden,
495ffd83dbSDimitry Andric cl::desc("Show heat colors in CFG"));
505ffd83dbSDimitry Andric
515ffd83dbSDimitry Andric static cl::opt<bool> UseRawEdgeWeight("cfg-raw-weights", cl::init(false),
525ffd83dbSDimitry Andric cl::Hidden,
535ffd83dbSDimitry Andric cl::desc("Use raw weights for labels. "
545ffd83dbSDimitry Andric "Use percentages as default."));
555ffd83dbSDimitry Andric
565ffd83dbSDimitry Andric static cl::opt<bool>
575ffd83dbSDimitry Andric ShowEdgeWeight("cfg-weights", cl::init(false), cl::Hidden,
585ffd83dbSDimitry Andric cl::desc("Show edges labeled with weights"));
595ffd83dbSDimitry Andric
writeCFGToDotFile(Function & F,BlockFrequencyInfo * BFI,BranchProbabilityInfo * BPI,uint64_t MaxFreq,bool CFGOnly=false)605ffd83dbSDimitry Andric static void writeCFGToDotFile(Function &F, BlockFrequencyInfo *BFI,
615ffd83dbSDimitry Andric BranchProbabilityInfo *BPI, uint64_t MaxFreq,
625ffd83dbSDimitry Andric bool CFGOnly = false) {
635ffd83dbSDimitry Andric std::string Filename =
645ffd83dbSDimitry Andric (CFGDotFilenamePrefix + "." + F.getName() + ".dot").str();
655ffd83dbSDimitry Andric errs() << "Writing '" << Filename << "'...";
665ffd83dbSDimitry Andric
675ffd83dbSDimitry Andric std::error_code EC;
68fe6060f1SDimitry Andric raw_fd_ostream File(Filename, EC, sys::fs::OF_Text);
695ffd83dbSDimitry Andric
705ffd83dbSDimitry Andric DOTFuncInfo CFGInfo(&F, BFI, BPI, MaxFreq);
715ffd83dbSDimitry Andric CFGInfo.setHeatColors(ShowHeatColors);
725ffd83dbSDimitry Andric CFGInfo.setEdgeWeights(ShowEdgeWeight);
735ffd83dbSDimitry Andric CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
745ffd83dbSDimitry Andric
755ffd83dbSDimitry Andric if (!EC)
765ffd83dbSDimitry Andric WriteGraph(File, &CFGInfo, CFGOnly);
775ffd83dbSDimitry Andric else
785ffd83dbSDimitry Andric errs() << " error opening file for writing!";
795ffd83dbSDimitry Andric errs() << "\n";
805ffd83dbSDimitry Andric }
815ffd83dbSDimitry Andric
viewCFG(Function & F,const BlockFrequencyInfo * BFI,const BranchProbabilityInfo * BPI,uint64_t MaxFreq,bool CFGOnly=false)825ffd83dbSDimitry Andric static void viewCFG(Function &F, const BlockFrequencyInfo *BFI,
835ffd83dbSDimitry Andric const BranchProbabilityInfo *BPI, uint64_t MaxFreq,
845ffd83dbSDimitry Andric bool CFGOnly = false) {
855ffd83dbSDimitry Andric DOTFuncInfo CFGInfo(&F, BFI, BPI, MaxFreq);
865ffd83dbSDimitry Andric CFGInfo.setHeatColors(ShowHeatColors);
875ffd83dbSDimitry Andric CFGInfo.setEdgeWeights(ShowEdgeWeight);
885ffd83dbSDimitry Andric CFGInfo.setRawEdgeWeights(UseRawEdgeWeight);
895ffd83dbSDimitry Andric
905ffd83dbSDimitry Andric ViewGraph(&CFGInfo, "cfg." + F.getName(), CFGOnly);
915ffd83dbSDimitry Andric }
925ffd83dbSDimitry Andric
run(Function & F,FunctionAnalysisManager & AM)935ffd83dbSDimitry Andric PreservedAnalyses CFGViewerPass::run(Function &F, FunctionAnalysisManager &AM) {
94fe6060f1SDimitry Andric if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
95fe6060f1SDimitry Andric return PreservedAnalyses::all();
965ffd83dbSDimitry Andric auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
975ffd83dbSDimitry Andric auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
985ffd83dbSDimitry Andric viewCFG(F, BFI, BPI, getMaxFreq(F, BFI));
990b57cec5SDimitry Andric return PreservedAnalyses::all();
1000b57cec5SDimitry Andric }
1010b57cec5SDimitry Andric
run(Function & F,FunctionAnalysisManager & AM)1020b57cec5SDimitry Andric PreservedAnalyses CFGOnlyViewerPass::run(Function &F,
1030b57cec5SDimitry Andric FunctionAnalysisManager &AM) {
104fe6060f1SDimitry Andric if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
105fe6060f1SDimitry Andric return PreservedAnalyses::all();
1065ffd83dbSDimitry Andric auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
1075ffd83dbSDimitry Andric auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
1085ffd83dbSDimitry Andric viewCFG(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
1090b57cec5SDimitry Andric return PreservedAnalyses::all();
1100b57cec5SDimitry Andric }
1110b57cec5SDimitry Andric
run(Function & F,FunctionAnalysisManager & AM)1120b57cec5SDimitry Andric PreservedAnalyses CFGPrinterPass::run(Function &F,
1130b57cec5SDimitry Andric FunctionAnalysisManager &AM) {
114fe6060f1SDimitry Andric if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
115fe6060f1SDimitry Andric return PreservedAnalyses::all();
1165ffd83dbSDimitry Andric auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
1175ffd83dbSDimitry Andric auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
1185ffd83dbSDimitry Andric writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI));
1190b57cec5SDimitry Andric return PreservedAnalyses::all();
1200b57cec5SDimitry Andric }
1210b57cec5SDimitry Andric
run(Function & F,FunctionAnalysisManager & AM)1220b57cec5SDimitry Andric PreservedAnalyses CFGOnlyPrinterPass::run(Function &F,
1230b57cec5SDimitry Andric FunctionAnalysisManager &AM) {
124fe6060f1SDimitry Andric if (!CFGFuncName.empty() && !F.getName().contains(CFGFuncName))
125fe6060f1SDimitry Andric return PreservedAnalyses::all();
1265ffd83dbSDimitry Andric auto *BFI = &AM.getResult<BlockFrequencyAnalysis>(F);
1275ffd83dbSDimitry Andric auto *BPI = &AM.getResult<BranchProbabilityAnalysis>(F);
1285ffd83dbSDimitry Andric writeCFGToDotFile(F, BFI, BPI, getMaxFreq(F, BFI), /*CFGOnly=*/true);
1290b57cec5SDimitry Andric return PreservedAnalyses::all();
1300b57cec5SDimitry Andric }
1310b57cec5SDimitry Andric
1320b57cec5SDimitry Andric /// viewCFG - This function is meant for use from the debugger. You can just
1330b57cec5SDimitry Andric /// say 'call F->viewCFG()' and a ghostview window should pop up from the
1340b57cec5SDimitry Andric /// program, displaying the CFG of the current function. This depends on there
1350b57cec5SDimitry Andric /// being a 'dot' and 'gv' program in your path.
1360b57cec5SDimitry Andric ///
viewCFG() const1375ffd83dbSDimitry Andric void Function::viewCFG() const { viewCFG(false, nullptr, nullptr); }
1385ffd83dbSDimitry Andric
viewCFG(bool ViewCFGOnly,const BlockFrequencyInfo * BFI,const BranchProbabilityInfo * BPI) const1395ffd83dbSDimitry Andric void Function::viewCFG(bool ViewCFGOnly, const BlockFrequencyInfo *BFI,
1405ffd83dbSDimitry Andric const BranchProbabilityInfo *BPI) const {
1410b57cec5SDimitry Andric if (!CFGFuncName.empty() && !getName().contains(CFGFuncName))
1420b57cec5SDimitry Andric return;
1435ffd83dbSDimitry Andric DOTFuncInfo CFGInfo(this, BFI, BPI, BFI ? getMaxFreq(*this, BFI) : 0);
1445ffd83dbSDimitry Andric ViewGraph(&CFGInfo, "cfg" + getName(), ViewCFGOnly);
1450b57cec5SDimitry Andric }
1460b57cec5SDimitry Andric
1470b57cec5SDimitry Andric /// viewCFGOnly - This function is meant for use from the debugger. It works
1480b57cec5SDimitry Andric /// just like viewCFG, but it does not include the contents of basic blocks
1490b57cec5SDimitry Andric /// into the nodes, just the label. If you are only interested in the CFG
1500b57cec5SDimitry Andric /// this can make the graph smaller.
1510b57cec5SDimitry Andric ///
viewCFGOnly() const1525ffd83dbSDimitry Andric void Function::viewCFGOnly() const { viewCFGOnly(nullptr, nullptr); }
1535ffd83dbSDimitry Andric
viewCFGOnly(const BlockFrequencyInfo * BFI,const BranchProbabilityInfo * BPI) const1545ffd83dbSDimitry Andric void Function::viewCFGOnly(const BlockFrequencyInfo *BFI,
1555ffd83dbSDimitry Andric const BranchProbabilityInfo *BPI) const {
1565ffd83dbSDimitry Andric viewCFG(true, BFI, BPI);
1570b57cec5SDimitry Andric }
1580b57cec5SDimitry Andric
159fe6060f1SDimitry Andric /// Find all blocks on the paths which terminate with a deoptimize or
160fe6060f1SDimitry Andric /// unreachable (i.e. all blocks which are post-dominated by a deoptimize
161fe6060f1SDimitry Andric /// or unreachable). These paths are hidden if the corresponding cl::opts
162fe6060f1SDimitry Andric /// are enabled.
computeDeoptOrUnreachablePaths(const Function * F)163fe6060f1SDimitry Andric void DOTGraphTraits<DOTFuncInfo *>::computeDeoptOrUnreachablePaths(
164fe6060f1SDimitry Andric const Function *F) {
1655ffd83dbSDimitry Andric auto evaluateBB = [&](const BasicBlock *Node) {
166e8d8bef9SDimitry Andric if (succ_empty(Node)) {
1675ffd83dbSDimitry Andric const Instruction *TI = Node->getTerminator();
168fe6060f1SDimitry Andric isOnDeoptOrUnreachablePath[Node] =
1695ffd83dbSDimitry Andric (HideUnreachablePaths && isa<UnreachableInst>(TI)) ||
1705ffd83dbSDimitry Andric (HideDeoptimizePaths && Node->getTerminatingDeoptimizeCall());
1715ffd83dbSDimitry Andric return;
1725ffd83dbSDimitry Andric }
173fe6060f1SDimitry Andric isOnDeoptOrUnreachablePath[Node] =
174e8d8bef9SDimitry Andric llvm::all_of(successors(Node), [this](const BasicBlock *BB) {
175fe6060f1SDimitry Andric return isOnDeoptOrUnreachablePath[BB];
176e8d8bef9SDimitry Andric });
1775ffd83dbSDimitry Andric };
1785ffd83dbSDimitry Andric /// The post order traversal iteration is done to know the status of
179fe6060f1SDimitry Andric /// isOnDeoptOrUnreachablePath for all the successors on the current BB.
180fe6060f1SDimitry Andric llvm::for_each(post_order(&F->getEntryBlock()), evaluateBB);
1815ffd83dbSDimitry Andric }
1825ffd83dbSDimitry Andric
isNodeHidden(const BasicBlock * Node,const DOTFuncInfo * CFGInfo)183e8d8bef9SDimitry Andric bool DOTGraphTraits<DOTFuncInfo *>::isNodeHidden(const BasicBlock *Node,
184e8d8bef9SDimitry Andric const DOTFuncInfo *CFGInfo) {
185fe6060f1SDimitry Andric if (HideColdPaths.getNumOccurrences() > 0)
186fe6060f1SDimitry Andric if (auto *BFI = CFGInfo->getBFI()) {
1875f757f3fSDimitry Andric BlockFrequency NodeFreq = BFI->getBlockFreq(Node);
1885f757f3fSDimitry Andric BlockFrequency EntryFreq = BFI->getEntryFreq();
189fe6060f1SDimitry Andric // Hide blocks with relative frequency below HideColdPaths threshold.
1905f757f3fSDimitry Andric if ((double)NodeFreq.getFrequency() / EntryFreq.getFrequency() <
1915f757f3fSDimitry Andric HideColdPaths)
192fe6060f1SDimitry Andric return true;
193fe6060f1SDimitry Andric }
194fe6060f1SDimitry Andric if (HideUnreachablePaths || HideDeoptimizePaths) {
19506c3fb27SDimitry Andric if (!isOnDeoptOrUnreachablePath.contains(Node))
196fe6060f1SDimitry Andric computeDeoptOrUnreachablePaths(Node->getParent());
197fe6060f1SDimitry Andric return isOnDeoptOrUnreachablePath[Node];
198fe6060f1SDimitry Andric }
1995ffd83dbSDimitry Andric return false;
2005ffd83dbSDimitry Andric }
201