| 1 | //===- MachineBlockFrequencyInfo.cpp - MBB Frequency Analysis -------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | // |
| 9 | // Loops should be simplified before this analysis. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #include "llvm/CodeGen/MachineBlockFrequencyInfo.h" |
| 14 | #include "llvm/ADT/DenseMap.h" |
| 15 | #include "llvm/ADT/iterator.h" |
| 16 | #include "llvm/Analysis/BlockFrequencyInfo.h" |
| 17 | #include "llvm/Analysis/BlockFrequencyInfoImpl.h" |
| 18 | #include "llvm/CodeGen/MachineBasicBlock.h" |
| 19 | #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" |
| 20 | #include "llvm/CodeGen/MachineCycleAnalysis.h" |
| 21 | #include "llvm/CodeGen/MachineFunction.h" |
| 22 | #include "llvm/InitializePasses.h" |
| 23 | #include "llvm/Pass.h" |
| 24 | #include "llvm/Support/CommandLine.h" |
| 25 | #include "llvm/Support/GraphWriter.h" |
| 26 | #include <optional> |
| 27 | #include <string> |
| 28 | |
| 29 | using namespace llvm; |
| 30 | |
| 31 | #define DEBUG_TYPE "machine-block-freq" |
| 32 | |
| 33 | static cl::opt<GVDAGType> ViewMachineBlockFreqPropagationDAG( |
| 34 | "view-machine-block-freq-propagation-dags" , cl::Hidden, |
| 35 | cl::desc("Pop up a window to show a dag displaying how machine block " |
| 36 | "frequencies propagate through the CFG." ), |
| 37 | cl::values(clEnumValN(GVDAGType::None, "none" , "do not display graphs." ), |
| 38 | clEnumValN(GVDAGType::Fraction, "fraction" , |
| 39 | "display a graph using the " |
| 40 | "fractional block frequency representation." ), |
| 41 | clEnumValN(GVDAGType::Integer, "integer" , |
| 42 | "display a graph using the raw " |
| 43 | "integer fractional block frequency representation." ), |
| 44 | clEnumValN(GVDAGType::Count, "count" , |
| 45 | "display a graph using the real " |
| 46 | "profile count if available." ))); |
| 47 | |
| 48 | namespace llvm { |
| 49 | // Similar option above, but used to control BFI display only after MBP pass |
| 50 | cl::opt<GVDAGType> ViewBlockLayoutWithBFI( |
| 51 | "view-block-layout-with-bfi" , cl::Hidden, |
| 52 | cl::desc( |
| 53 | "Pop up a window to show a dag displaying MBP layout and associated " |
| 54 | "block frequencies of the CFG." ), |
| 55 | cl::values(clEnumValN(GVDAGType::None, "none" , "do not display graphs." ), |
| 56 | clEnumValN(GVDAGType::Fraction, "fraction" , |
| 57 | "display a graph using the " |
| 58 | "fractional block frequency representation." ), |
| 59 | clEnumValN(GVDAGType::Integer, "integer" , |
| 60 | "display a graph using the raw " |
| 61 | "integer fractional block frequency representation." ), |
| 62 | clEnumValN(GVDAGType::Count, "count" , |
| 63 | "display a graph using the real " |
| 64 | "profile count if available." ))); |
| 65 | |
| 66 | } // namespace llvm |
| 67 | |
| 68 | static cl::opt<bool> |
| 69 | PrintMachineBlockFreq("print-machine-bfi" , cl::init(Val: false), cl::Hidden, |
| 70 | cl::desc("Print the machine block frequency info." )); |
| 71 | |
| 72 | static GVDAGType getGVDT() { |
| 73 | if (ViewBlockLayoutWithBFI != GVDAGType::None) |
| 74 | return ViewBlockLayoutWithBFI; |
| 75 | |
| 76 | return ViewMachineBlockFreqPropagationDAG; |
| 77 | } |
| 78 | |
| 79 | template <> struct llvm::GraphTraits<MachineBlockFrequencyInfo *> { |
| 80 | using NodeRef = const MachineBasicBlock *; |
| 81 | using ChildIteratorType = MachineBasicBlock::const_succ_iterator; |
| 82 | using nodes_iterator = pointer_iterator<MachineFunction::const_iterator>; |
| 83 | |
| 84 | static NodeRef getEntryNode(const MachineBlockFrequencyInfo *G) { |
| 85 | return &G->getFunction()->front(); |
| 86 | } |
| 87 | |
| 88 | static ChildIteratorType child_begin(const NodeRef N) { |
| 89 | return N->succ_begin(); |
| 90 | } |
| 91 | |
| 92 | static ChildIteratorType child_end(const NodeRef N) { return N->succ_end(); } |
| 93 | |
| 94 | static nodes_iterator nodes_begin(const MachineBlockFrequencyInfo *G) { |
| 95 | return nodes_iterator(G->getFunction()->begin()); |
| 96 | } |
| 97 | |
| 98 | static nodes_iterator nodes_end(const MachineBlockFrequencyInfo *G) { |
| 99 | return nodes_iterator(G->getFunction()->end()); |
| 100 | } |
| 101 | }; |
| 102 | |
| 103 | using MBFIDOTGraphTraitsBase = |
| 104 | BFIDOTGraphTraitsBase<MachineBlockFrequencyInfo, |
| 105 | MachineBranchProbabilityInfo>; |
| 106 | |
| 107 | template <> |
| 108 | struct llvm::DOTGraphTraits<MachineBlockFrequencyInfo *> |
| 109 | : public MBFIDOTGraphTraitsBase { |
| 110 | const MachineFunction *CurFunc = nullptr; |
| 111 | DenseMap<const MachineBasicBlock *, int> LayoutOrderMap; |
| 112 | |
| 113 | explicit DOTGraphTraits(bool isSimple = false) |
| 114 | : MBFIDOTGraphTraitsBase(isSimple) {} |
| 115 | |
| 116 | std::string getNodeLabel(const MachineBasicBlock *Node, |
| 117 | const MachineBlockFrequencyInfo *Graph) { |
| 118 | int layout_order = -1; |
| 119 | // Attach additional ordering information if 'isSimple' is false. |
| 120 | if (!isSimple()) { |
| 121 | const MachineFunction *F = Node->getParent(); |
| 122 | if (!CurFunc || F != CurFunc) { |
| 123 | if (CurFunc) |
| 124 | LayoutOrderMap.clear(); |
| 125 | |
| 126 | CurFunc = F; |
| 127 | int O = 0; |
| 128 | for (auto MBI = F->begin(); MBI != F->end(); ++MBI, ++O) { |
| 129 | LayoutOrderMap[&*MBI] = O; |
| 130 | } |
| 131 | } |
| 132 | layout_order = LayoutOrderMap[Node]; |
| 133 | } |
| 134 | return MBFIDOTGraphTraitsBase::getNodeLabel(Node, Graph, GType: getGVDT(), |
| 135 | layout_order); |
| 136 | } |
| 137 | |
| 138 | std::string getNodeAttributes(const MachineBasicBlock *Node, |
| 139 | const MachineBlockFrequencyInfo *Graph) { |
| 140 | return MBFIDOTGraphTraitsBase::getNodeAttributes( |
| 141 | Node, Graph, |
| 142 | HotPercentThreshold: getViewHotFreqPercent(C: Node->getParent()->getFunction().getContext())); |
| 143 | } |
| 144 | |
| 145 | std::string getEdgeAttributes(const MachineBasicBlock *Node, EdgeIter EI, |
| 146 | const MachineBlockFrequencyInfo *MBFI) { |
| 147 | return MBFIDOTGraphTraitsBase::getEdgeAttributes( |
| 148 | Node, EI, BFI: MBFI, BPI: MBFI->getMBPI(), |
| 149 | HotPercentThreshold: getViewHotFreqPercent(C: Node->getParent()->getFunction().getContext())); |
| 150 | } |
| 151 | }; |
| 152 | |
| 153 | AnalysisKey MachineBlockFrequencyAnalysis::Key; |
| 154 | |
| 155 | MachineBlockFrequencyAnalysis::Result |
| 156 | MachineBlockFrequencyAnalysis::run(MachineFunction &MF, |
| 157 | MachineFunctionAnalysisManager &MFAM) { |
| 158 | auto &MBPI = MFAM.getResult<MachineBranchProbabilityAnalysis>(IR&: MF); |
| 159 | auto &MCI = MFAM.getResult<MachineCycleAnalysis>(IR&: MF); |
| 160 | return Result(MF, MBPI, MCI); |
| 161 | } |
| 162 | |
| 163 | PreservedAnalyses |
| 164 | MachineBlockFrequencyPrinterPass::run(MachineFunction &MF, |
| 165 | MachineFunctionAnalysisManager &MFAM) { |
| 166 | auto &MBFI = MFAM.getResult<MachineBlockFrequencyAnalysis>(IR&: MF); |
| 167 | OS << "Machine block frequency for machine function: " << MF.getName() |
| 168 | << '\n'; |
| 169 | MBFI.print(OS); |
| 170 | return PreservedAnalyses::all(); |
| 171 | } |
| 172 | |
| 173 | INITIALIZE_PASS_BEGIN(MachineBlockFrequencyInfoWrapperPass, DEBUG_TYPE, |
| 174 | "Machine Block Frequency Analysis" , true, true) |
| 175 | INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfoWrapperPass) |
| 176 | INITIALIZE_PASS_DEPENDENCY(MachineCycleInfoWrapperPass) |
| 177 | INITIALIZE_PASS_END(MachineBlockFrequencyInfoWrapperPass, DEBUG_TYPE, |
| 178 | "Machine Block Frequency Analysis" , true, true) |
| 179 | |
| 180 | char MachineBlockFrequencyInfoWrapperPass::ID = 0; |
| 181 | |
| 182 | MachineBlockFrequencyInfoWrapperPass::MachineBlockFrequencyInfoWrapperPass() |
| 183 | : MachineFunctionPass(ID) {} |
| 184 | |
| 185 | MachineBlockFrequencyInfo::MachineBlockFrequencyInfo() = default; |
| 186 | |
| 187 | MachineBlockFrequencyInfo::MachineBlockFrequencyInfo( |
| 188 | MachineBlockFrequencyInfo &&) = default; |
| 189 | |
| 190 | MachineBlockFrequencyInfo::MachineBlockFrequencyInfo( |
| 191 | const MachineFunction &F, const MachineBranchProbabilityInfo &MBPI, |
| 192 | const MachineCycleInfo &MCI) { |
| 193 | calculate(F, MBPI, MCI); |
| 194 | } |
| 195 | |
| 196 | MachineBlockFrequencyInfo::~MachineBlockFrequencyInfo() = default; |
| 197 | |
| 198 | bool MachineBlockFrequencyInfo::invalidate( |
| 199 | MachineFunction &MF, const PreservedAnalyses &PA, |
| 200 | MachineFunctionAnalysisManager::Invalidator &) { |
| 201 | // Check whether the analysis, all analyses on machine functions, or the |
| 202 | // machine function's CFG have been preserved. |
| 203 | auto PAC = PA.getChecker<MachineBlockFrequencyAnalysis>(); |
| 204 | return !PAC.preserved() && |
| 205 | !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() && |
| 206 | !PAC.preservedSet<CFGAnalyses>(); |
| 207 | } |
| 208 | |
| 209 | void MachineBlockFrequencyInfoWrapperPass::getAnalysisUsage( |
| 210 | AnalysisUsage &AU) const { |
| 211 | AU.addRequired<MachineBranchProbabilityInfoWrapperPass>(); |
| 212 | AU.addRequired<MachineCycleInfoWrapperPass>(); |
| 213 | AU.setPreservesAll(); |
| 214 | MachineFunctionPass::getAnalysisUsage(AU); |
| 215 | } |
| 216 | |
| 217 | void MachineBlockFrequencyInfo::calculate( |
| 218 | const MachineFunction &F, const MachineBranchProbabilityInfo &MBPI, |
| 219 | const MachineCycleInfo &MCI) { |
| 220 | if (!MBFI) |
| 221 | MBFI.reset(p: new ImplType); |
| 222 | MBFI->calculate(F, BPI: MBPI, CI: MCI); |
| 223 | const LLVMContext &Ctx = F.getFunction().getContext(); |
| 224 | StringRef ViewFuncName = getViewBlockFreqFuncName(C: Ctx); |
| 225 | if (ViewMachineBlockFreqPropagationDAG != GVDAGType::None && |
| 226 | (ViewFuncName.empty() || F.getName() == ViewFuncName)) { |
| 227 | view(Name: "MachineBlockFrequencyDAGS." + F.getName()); |
| 228 | } |
| 229 | StringRef PrintFuncName = getPrintBFIFuncName(C: Ctx); |
| 230 | if (PrintMachineBlockFreq && |
| 231 | (PrintFuncName.empty() || F.getName() == PrintFuncName)) { |
| 232 | MBFI->print(OS&: dbgs()); |
| 233 | } |
| 234 | } |
| 235 | |
| 236 | bool MachineBlockFrequencyInfoWrapperPass::runOnMachineFunction( |
| 237 | MachineFunction &F) { |
| 238 | MachineBranchProbabilityInfo &MBPI = |
| 239 | getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI(); |
| 240 | MachineCycleInfo &MCI = |
| 241 | getAnalysis<MachineCycleInfoWrapperPass>().getCycleInfo(); |
| 242 | MBFI.calculate(F, MBPI, MCI); |
| 243 | return false; |
| 244 | } |
| 245 | |
| 246 | void MachineBlockFrequencyInfo::print(raw_ostream &OS) { MBFI->print(OS); } |
| 247 | |
| 248 | void MachineBlockFrequencyInfo::releaseMemory() { MBFI.reset(); } |
| 249 | |
| 250 | /// Pop up a ghostview window with the current block frequency propagation |
| 251 | /// rendered using dot. |
| 252 | void MachineBlockFrequencyInfo::view(const Twine &Name, bool isSimple) const { |
| 253 | // This code is only for debugging. |
| 254 | ViewGraph(G: const_cast<MachineBlockFrequencyInfo *>(this), Name, ShortNames: isSimple); |
| 255 | } |
| 256 | |
| 257 | BlockFrequency |
| 258 | MachineBlockFrequencyInfo::getBlockFreq(const MachineBasicBlock *MBB) const { |
| 259 | return MBFI ? MBFI->getBlockFreq(BB: MBB) : BlockFrequency(0); |
| 260 | } |
| 261 | |
| 262 | std::optional<uint64_t> MachineBlockFrequencyInfo::getBlockProfileCount( |
| 263 | const MachineBasicBlock *MBB) const { |
| 264 | if (!MBFI) |
| 265 | return std::nullopt; |
| 266 | |
| 267 | const Function &F = MBFI->getFunction()->getFunction(); |
| 268 | return MBFI->getBlockProfileCount(F, BB: MBB); |
| 269 | } |
| 270 | |
| 271 | std::optional<uint64_t> |
| 272 | MachineBlockFrequencyInfo::getProfileCountFromFreq(BlockFrequency Freq) const { |
| 273 | if (!MBFI) |
| 274 | return std::nullopt; |
| 275 | |
| 276 | const Function &F = MBFI->getFunction()->getFunction(); |
| 277 | return MBFI->getProfileCountFromFreq(F, Freq); |
| 278 | } |
| 279 | |
| 280 | void MachineBlockFrequencyInfo::onEdgeSplit( |
| 281 | const MachineBasicBlock &NewPredecessor, |
| 282 | const MachineBasicBlock &NewSuccessor, |
| 283 | const MachineBranchProbabilityInfo &MBPI) { |
| 284 | assert(MBFI && "Expected analysis to be available" ); |
| 285 | auto NewSuccFreq = MBFI->getBlockFreq(BB: &NewPredecessor) * |
| 286 | MBPI.getEdgeProbability(Src: &NewPredecessor, Dst: &NewSuccessor); |
| 287 | |
| 288 | MBFI->setBlockFreq(BB: &NewSuccessor, Freq: NewSuccFreq); |
| 289 | } |
| 290 | |
| 291 | const MachineFunction *MachineBlockFrequencyInfo::getFunction() const { |
| 292 | return MBFI ? MBFI->getFunction() : nullptr; |
| 293 | } |
| 294 | |
| 295 | const MachineBranchProbabilityInfo *MachineBlockFrequencyInfo::getMBPI() const { |
| 296 | return MBFI ? &MBFI->getBPI() : nullptr; |
| 297 | } |
| 298 | |
| 299 | BlockFrequency MachineBlockFrequencyInfo::getEntryFreq() const { |
| 300 | return MBFI ? MBFI->getEntryFreq() : BlockFrequency(0); |
| 301 | } |
| 302 | |
| 303 | Printable llvm::printBlockFreq(const MachineBlockFrequencyInfo &MBFI, |
| 304 | BlockFrequency Freq) { |
| 305 | return Printable([&MBFI, Freq](raw_ostream &OS) { |
| 306 | printRelativeBlockFreq(OS, EntryFreq: MBFI.getEntryFreq(), Freq); |
| 307 | }); |
| 308 | } |
| 309 | |
| 310 | Printable llvm::printBlockFreq(const MachineBlockFrequencyInfo &MBFI, |
| 311 | const MachineBasicBlock &MBB) { |
| 312 | return printBlockFreq(MBFI, Freq: MBFI.getBlockFreq(MBB: &MBB)); |
| 313 | } |
| 314 | |