1 //===- CtxProfAnalysis.cpp - contextual profile 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 // Implementation of the contextual profile analysis, which maintains contextual 10 // profiling info through IPO passes. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Analysis/CtxProfAnalysis.h" 15 #include "llvm/ADT/STLExtras.h" 16 #include "llvm/IR/Analysis.h" 17 #include "llvm/IR/IntrinsicInst.h" 18 #include "llvm/IR/Module.h" 19 #include "llvm/IR/PassManager.h" 20 #include "llvm/ProfileData/PGOCtxProfReader.h" 21 #include "llvm/Support/CommandLine.h" 22 #include "llvm/Support/MemoryBuffer.h" 23 24 #define DEBUG_TYPE "ctx_prof" 25 26 using namespace llvm; 27 cl::opt<std::string> 28 UseCtxProfile("use-ctx-profile", cl::init(""), cl::Hidden, 29 cl::desc("Use the specified contextual profile file")); 30 31 static cl::opt<CtxProfAnalysisPrinterPass::PrintMode> PrintLevel( 32 "ctx-profile-printer-level", 33 cl::init(CtxProfAnalysisPrinterPass::PrintMode::YAML), cl::Hidden, 34 cl::values(clEnumValN(CtxProfAnalysisPrinterPass::PrintMode::Everything, 35 "everything", "print everything - most verbose"), 36 clEnumValN(CtxProfAnalysisPrinterPass::PrintMode::YAML, "yaml", 37 "just the yaml representation of the profile")), 38 cl::desc("Verbosity level of the contextual profile printer pass.")); 39 40 const char *AssignGUIDPass::GUIDMetadataName = "guid"; 41 42 PreservedAnalyses AssignGUIDPass::run(Module &M, ModuleAnalysisManager &MAM) { 43 for (auto &F : M.functions()) { 44 if (F.isDeclaration()) 45 continue; 46 if (F.getMetadata(GUIDMetadataName)) 47 continue; 48 const GlobalValue::GUID GUID = F.getGUID(); 49 F.setMetadata(GUIDMetadataName, 50 MDNode::get(M.getContext(), 51 {ConstantAsMetadata::get(ConstantInt::get( 52 Type::getInt64Ty(M.getContext()), GUID))})); 53 } 54 return PreservedAnalyses::none(); 55 } 56 57 GlobalValue::GUID AssignGUIDPass::getGUID(const Function &F) { 58 if (F.isDeclaration()) { 59 assert(GlobalValue::isExternalLinkage(F.getLinkage())); 60 return GlobalValue::getGUID(F.getGlobalIdentifier()); 61 } 62 auto *MD = F.getMetadata(GUIDMetadataName); 63 assert(MD && "guid not found for defined function"); 64 return cast<ConstantInt>(cast<ConstantAsMetadata>(MD->getOperand(0)) 65 ->getValue() 66 ->stripPointerCasts()) 67 ->getZExtValue(); 68 } 69 AnalysisKey CtxProfAnalysis::Key; 70 71 CtxProfAnalysis::CtxProfAnalysis(std::optional<StringRef> Profile) 72 : Profile([&]() -> std::optional<StringRef> { 73 if (Profile) 74 return *Profile; 75 if (UseCtxProfile.getNumOccurrences()) 76 return UseCtxProfile; 77 return std::nullopt; 78 }()) {} 79 80 PGOContextualProfile CtxProfAnalysis::run(Module &M, 81 ModuleAnalysisManager &MAM) { 82 if (!Profile) 83 return {}; 84 ErrorOr<std::unique_ptr<MemoryBuffer>> MB = MemoryBuffer::getFile(*Profile); 85 if (auto EC = MB.getError()) { 86 M.getContext().emitError("could not open contextual profile file: " + 87 EC.message()); 88 return {}; 89 } 90 PGOCtxProfileReader Reader(MB.get()->getBuffer()); 91 auto MaybeCtx = Reader.loadContexts(); 92 if (!MaybeCtx) { 93 M.getContext().emitError("contextual profile file is invalid: " + 94 toString(MaybeCtx.takeError())); 95 return {}; 96 } 97 98 DenseSet<GlobalValue::GUID> ProfileRootsInModule; 99 for (const auto &F : M) 100 if (!F.isDeclaration()) 101 if (auto GUID = AssignGUIDPass::getGUID(F); 102 MaybeCtx->find(GUID) != MaybeCtx->end()) 103 ProfileRootsInModule.insert(GUID); 104 105 // Trim first the roots that aren't in this module. 106 for (auto &[RootGuid, _] : llvm::make_early_inc_range(*MaybeCtx)) 107 if (!ProfileRootsInModule.contains(RootGuid)) 108 MaybeCtx->erase(RootGuid); 109 // If none of the roots are in the module, we have no profile (for this 110 // module) 111 if (MaybeCtx->empty()) 112 return {}; 113 114 // OK, so we have a valid profile and it's applicable to roots in this module. 115 PGOContextualProfile Result; 116 117 for (const auto &F : M) { 118 if (F.isDeclaration()) 119 continue; 120 auto GUID = AssignGUIDPass::getGUID(F); 121 assert(GUID && "guid not found for defined function"); 122 const auto &Entry = F.begin(); 123 uint32_t MaxCounters = 0; // we expect at least a counter. 124 for (const auto &I : *Entry) 125 if (auto *C = dyn_cast<InstrProfIncrementInst>(&I)) { 126 MaxCounters = 127 static_cast<uint32_t>(C->getNumCounters()->getZExtValue()); 128 break; 129 } 130 if (!MaxCounters) 131 continue; 132 uint32_t MaxCallsites = 0; 133 for (const auto &BB : F) 134 for (const auto &I : BB) 135 if (auto *C = dyn_cast<InstrProfCallsite>(&I)) { 136 MaxCallsites = 137 static_cast<uint32_t>(C->getNumCounters()->getZExtValue()); 138 break; 139 } 140 auto [It, Ins] = Result.FuncInfo.insert( 141 {GUID, PGOContextualProfile::FunctionInfo(F.getName())}); 142 (void)Ins; 143 assert(Ins); 144 It->second.NextCallsiteIndex = MaxCallsites; 145 It->second.NextCounterIndex = MaxCounters; 146 } 147 // If we made it this far, the Result is valid - which we mark by setting 148 // .Profiles. 149 Result.Profiles = std::move(*MaybeCtx); 150 Result.initIndex(); 151 return Result; 152 } 153 154 GlobalValue::GUID 155 PGOContextualProfile::getDefinedFunctionGUID(const Function &F) const { 156 if (auto It = FuncInfo.find(AssignGUIDPass::getGUID(F)); It != FuncInfo.end()) 157 return It->first; 158 return 0; 159 } 160 161 CtxProfAnalysisPrinterPass::CtxProfAnalysisPrinterPass(raw_ostream &OS) 162 : OS(OS), Mode(PrintLevel) {} 163 164 PreservedAnalyses CtxProfAnalysisPrinterPass::run(Module &M, 165 ModuleAnalysisManager &MAM) { 166 CtxProfAnalysis::Result &C = MAM.getResult<CtxProfAnalysis>(M); 167 if (!C) { 168 OS << "No contextual profile was provided.\n"; 169 return PreservedAnalyses::all(); 170 } 171 172 if (Mode == PrintMode::Everything) { 173 OS << "Function Info:\n"; 174 for (const auto &[Guid, FuncInfo] : C.FuncInfo) 175 OS << Guid << " : " << FuncInfo.Name 176 << ". MaxCounterID: " << FuncInfo.NextCounterIndex 177 << ". MaxCallsiteID: " << FuncInfo.NextCallsiteIndex << "\n"; 178 } 179 180 if (Mode == PrintMode::Everything) 181 OS << "\nCurrent Profile:\n"; 182 convertCtxProfToYaml(OS, C.profiles()); 183 OS << "\n"; 184 if (Mode == PrintMode::YAML) 185 return PreservedAnalyses::all(); 186 187 OS << "\nFlat Profile:\n"; 188 auto Flat = C.flatten(); 189 for (const auto &[Guid, Counters] : Flat) { 190 OS << Guid << " : "; 191 for (auto V : Counters) 192 OS << V << " "; 193 OS << "\n"; 194 } 195 return PreservedAnalyses::all(); 196 } 197 198 InstrProfCallsite *CtxProfAnalysis::getCallsiteInstrumentation(CallBase &CB) { 199 if (!InstrProfCallsite::canInstrumentCallsite(CB)) 200 return nullptr; 201 for (auto *Prev = CB.getPrevNode(); Prev; Prev = Prev->getPrevNode()) { 202 if (auto *IPC = dyn_cast<InstrProfCallsite>(Prev)) 203 return IPC; 204 assert(!isa<CallBase>(Prev) && 205 "didn't expect to find another call, that's not the callsite " 206 "instrumentation, before an instrumentable callsite"); 207 } 208 return nullptr; 209 } 210 211 InstrProfIncrementInst *CtxProfAnalysis::getBBInstrumentation(BasicBlock &BB) { 212 for (auto &I : BB) 213 if (auto *Incr = dyn_cast<InstrProfIncrementInst>(&I)) 214 if (!isa<InstrProfIncrementInstStep>(&I)) 215 return Incr; 216 return nullptr; 217 } 218 219 InstrProfIncrementInstStep * 220 CtxProfAnalysis::getSelectInstrumentation(SelectInst &SI) { 221 Instruction *Prev = &SI; 222 while ((Prev = Prev->getPrevNode())) 223 if (auto *Step = dyn_cast<InstrProfIncrementInstStep>(Prev)) 224 return Step; 225 return nullptr; 226 } 227 228 template <class ProfilesTy, class ProfTy> 229 static void preorderVisit(ProfilesTy &Profiles, 230 function_ref<void(ProfTy &)> Visitor) { 231 std::function<void(ProfTy &)> Traverser = [&](auto &Ctx) { 232 Visitor(Ctx); 233 for (auto &[_, SubCtxSet] : Ctx.callsites()) 234 for (auto &[__, Subctx] : SubCtxSet) 235 Traverser(Subctx); 236 }; 237 for (auto &[_, P] : Profiles) 238 Traverser(P); 239 } 240 241 void PGOContextualProfile::initIndex() { 242 // Initialize the head of the index list for each function. We don't need it 243 // after this point. 244 DenseMap<GlobalValue::GUID, PGOCtxProfContext *> InsertionPoints; 245 for (auto &[Guid, FI] : FuncInfo) 246 InsertionPoints[Guid] = &FI.Index; 247 preorderVisit<PGOCtxProfContext::CallTargetMapTy, PGOCtxProfContext>( 248 *Profiles, [&](PGOCtxProfContext &Ctx) { 249 auto InsertIt = InsertionPoints.find(Ctx.guid()); 250 if (InsertIt == InsertionPoints.end()) 251 return; 252 // Insert at the end of the list. Since we traverse in preorder, it 253 // means that when we iterate the list from the beginning, we'd 254 // encounter the contexts in the order we would have, should we have 255 // performed a full preorder traversal. 256 InsertIt->second->Next = &Ctx; 257 Ctx.Previous = InsertIt->second; 258 InsertIt->second = &Ctx; 259 }); 260 } 261 262 void PGOContextualProfile::update(Visitor V, const Function &F) { 263 assert(isFunctionKnown(F)); 264 GlobalValue::GUID G = getDefinedFunctionGUID(F); 265 for (auto *Node = FuncInfo.find(G)->second.Index.Next; Node; 266 Node = Node->Next) 267 V(*reinterpret_cast<PGOCtxProfContext *>(Node)); 268 } 269 270 void PGOContextualProfile::visit(ConstVisitor V, const Function *F) const { 271 if (!F) 272 return preorderVisit<const PGOCtxProfContext::CallTargetMapTy, 273 const PGOCtxProfContext>(*Profiles, V); 274 assert(isFunctionKnown(*F)); 275 GlobalValue::GUID G = getDefinedFunctionGUID(*F); 276 for (const auto *Node = FuncInfo.find(G)->second.Index.Next; Node; 277 Node = Node->Next) 278 V(*reinterpret_cast<const PGOCtxProfContext *>(Node)); 279 } 280 281 const CtxProfFlatProfile PGOContextualProfile::flatten() const { 282 assert(Profiles.has_value()); 283 CtxProfFlatProfile Flat; 284 preorderVisit<const PGOCtxProfContext::CallTargetMapTy, 285 const PGOCtxProfContext>( 286 *Profiles, [&](const PGOCtxProfContext &Ctx) { 287 auto [It, Ins] = Flat.insert({Ctx.guid(), {}}); 288 if (Ins) { 289 llvm::append_range(It->second, Ctx.counters()); 290 return; 291 } 292 assert(It->second.size() == Ctx.counters().size() && 293 "All contexts corresponding to a function should have the exact " 294 "same number of counters."); 295 for (size_t I = 0, E = It->second.size(); I < E; ++I) 296 It->second[I] += Ctx.counters()[I]; 297 }); 298 return Flat; 299 } 300 301 void CtxProfAnalysis::collectIndirectCallPromotionList( 302 CallBase &IC, Result &Profile, 303 SetVector<std::pair<CallBase *, Function *>> &Candidates) { 304 const auto *Instr = CtxProfAnalysis::getCallsiteInstrumentation(IC); 305 if (!Instr) 306 return; 307 Module &M = *IC.getParent()->getModule(); 308 const uint32_t CallID = Instr->getIndex()->getZExtValue(); 309 Profile.visit( 310 [&](const PGOCtxProfContext &Ctx) { 311 const auto &Targets = Ctx.callsites().find(CallID); 312 if (Targets == Ctx.callsites().end()) 313 return; 314 for (const auto &[Guid, _] : Targets->second) 315 if (auto Name = Profile.getFunctionName(Guid); !Name.empty()) 316 if (auto *Target = M.getFunction(Name)) 317 if (Target->hasFnAttribute(Attribute::AlwaysInline)) 318 Candidates.insert({&IC, Target}); 319 }, 320 IC.getCaller()); 321 } 322