1 //===- IndirectCallPromotion.cpp - Optimizations based on value profiling -===// 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 // This file implements the transformation that promotes indirect calls to 10 // conditional direct calls when the indirect-call value profile metadata is 11 // available. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "llvm/ADT/ArrayRef.h" 16 #include "llvm/ADT/STLExtras.h" 17 #include "llvm/ADT/SmallVector.h" 18 #include "llvm/ADT/Statistic.h" 19 #include "llvm/ADT/StringRef.h" 20 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h" 21 #include "llvm/Analysis/IndirectCallVisitor.h" 22 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 23 #include "llvm/Analysis/ProfileSummaryInfo.h" 24 #include "llvm/IR/Attributes.h" 25 #include "llvm/IR/BasicBlock.h" 26 #include "llvm/IR/DerivedTypes.h" 27 #include "llvm/IR/DiagnosticInfo.h" 28 #include "llvm/IR/Function.h" 29 #include "llvm/IR/IRBuilder.h" 30 #include "llvm/IR/InstrTypes.h" 31 #include "llvm/IR/Instruction.h" 32 #include "llvm/IR/Instructions.h" 33 #include "llvm/IR/LLVMContext.h" 34 #include "llvm/IR/MDBuilder.h" 35 #include "llvm/IR/PassManager.h" 36 #include "llvm/IR/Type.h" 37 #include "llvm/IR/Value.h" 38 #include "llvm/InitializePasses.h" 39 #include "llvm/Pass.h" 40 #include "llvm/ProfileData/InstrProf.h" 41 #include "llvm/Support/Casting.h" 42 #include "llvm/Support/CommandLine.h" 43 #include "llvm/Support/Debug.h" 44 #include "llvm/Support/Error.h" 45 #include "llvm/Support/raw_ostream.h" 46 #include "llvm/Transforms/Instrumentation.h" 47 #include "llvm/Transforms/Instrumentation/PGOInstrumentation.h" 48 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 49 #include "llvm/Transforms/Utils/CallPromotionUtils.h" 50 #include <cassert> 51 #include <cstdint> 52 #include <memory> 53 #include <string> 54 #include <utility> 55 #include <vector> 56 57 using namespace llvm; 58 59 #define DEBUG_TYPE "pgo-icall-prom" 60 61 STATISTIC(NumOfPGOICallPromotion, "Number of indirect call promotions."); 62 STATISTIC(NumOfPGOICallsites, "Number of indirect call candidate sites."); 63 64 // Command line option to disable indirect-call promotion with the default as 65 // false. This is for debug purpose. 66 static cl::opt<bool> DisableICP("disable-icp", cl::init(false), cl::Hidden, 67 cl::desc("Disable indirect call promotion")); 68 69 // Set the cutoff value for the promotion. If the value is other than 0, we 70 // stop the transformation once the total number of promotions equals the cutoff 71 // value. 72 // For debug use only. 73 static cl::opt<unsigned> 74 ICPCutOff("icp-cutoff", cl::init(0), cl::Hidden, cl::ZeroOrMore, 75 cl::desc("Max number of promotions for this compilation")); 76 77 // If ICPCSSkip is non zero, the first ICPCSSkip callsites will be skipped. 78 // For debug use only. 79 static cl::opt<unsigned> 80 ICPCSSkip("icp-csskip", cl::init(0), cl::Hidden, cl::ZeroOrMore, 81 cl::desc("Skip Callsite up to this number for this compilation")); 82 83 // Set if the pass is called in LTO optimization. The difference for LTO mode 84 // is the pass won't prefix the source module name to the internal linkage 85 // symbols. 86 static cl::opt<bool> ICPLTOMode("icp-lto", cl::init(false), cl::Hidden, 87 cl::desc("Run indirect-call promotion in LTO " 88 "mode")); 89 90 // Set if the pass is called in SamplePGO mode. The difference for SamplePGO 91 // mode is it will add prof metadatato the created direct call. 92 static cl::opt<bool> 93 ICPSamplePGOMode("icp-samplepgo", cl::init(false), cl::Hidden, 94 cl::desc("Run indirect-call promotion in SamplePGO mode")); 95 96 // If the option is set to true, only call instructions will be considered for 97 // transformation -- invoke instructions will be ignored. 98 static cl::opt<bool> 99 ICPCallOnly("icp-call-only", cl::init(false), cl::Hidden, 100 cl::desc("Run indirect-call promotion for call instructions " 101 "only")); 102 103 // If the option is set to true, only invoke instructions will be considered for 104 // transformation -- call instructions will be ignored. 105 static cl::opt<bool> ICPInvokeOnly("icp-invoke-only", cl::init(false), 106 cl::Hidden, 107 cl::desc("Run indirect-call promotion for " 108 "invoke instruction only")); 109 110 // Dump the function level IR if the transformation happened in this 111 // function. For debug use only. 112 static cl::opt<bool> 113 ICPDUMPAFTER("icp-dumpafter", cl::init(false), cl::Hidden, 114 cl::desc("Dump IR after transformation happens")); 115 116 namespace { 117 118 class PGOIndirectCallPromotionLegacyPass : public ModulePass { 119 public: 120 static char ID; 121 122 PGOIndirectCallPromotionLegacyPass(bool InLTO = false, bool SamplePGO = false) 123 : ModulePass(ID), InLTO(InLTO), SamplePGO(SamplePGO) { 124 initializePGOIndirectCallPromotionLegacyPassPass( 125 *PassRegistry::getPassRegistry()); 126 } 127 128 void getAnalysisUsage(AnalysisUsage &AU) const override { 129 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 130 } 131 132 StringRef getPassName() const override { return "PGOIndirectCallPromotion"; } 133 134 private: 135 bool runOnModule(Module &M) override; 136 137 // If this pass is called in LTO. We need to special handling the PGOFuncName 138 // for the static variables due to LTO's internalization. 139 bool InLTO; 140 141 // If this pass is called in SamplePGO. We need to add the prof metadata to 142 // the promoted direct call. 143 bool SamplePGO; 144 }; 145 146 } // end anonymous namespace 147 148 char PGOIndirectCallPromotionLegacyPass::ID = 0; 149 150 INITIALIZE_PASS_BEGIN(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom", 151 "Use PGO instrumentation profile to promote indirect " 152 "calls to direct calls.", 153 false, false) 154 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) 155 INITIALIZE_PASS_END(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom", 156 "Use PGO instrumentation profile to promote indirect " 157 "calls to direct calls.", 158 false, false) 159 160 ModulePass *llvm::createPGOIndirectCallPromotionLegacyPass(bool InLTO, 161 bool SamplePGO) { 162 return new PGOIndirectCallPromotionLegacyPass(InLTO, SamplePGO); 163 } 164 165 namespace { 166 167 // The class for main data structure to promote indirect calls to conditional 168 // direct calls. 169 class ICallPromotionFunc { 170 private: 171 Function &F; 172 Module *M; 173 174 // Symtab that maps indirect call profile values to function names and 175 // defines. 176 InstrProfSymtab *Symtab; 177 178 bool SamplePGO; 179 180 OptimizationRemarkEmitter &ORE; 181 182 // A struct that records the direct target and it's call count. 183 struct PromotionCandidate { 184 Function *TargetFunction; 185 uint64_t Count; 186 187 PromotionCandidate(Function *F, uint64_t C) : TargetFunction(F), Count(C) {} 188 }; 189 190 // Check if the indirect-call call site should be promoted. Return the number 191 // of promotions. Inst is the candidate indirect call, ValueDataRef 192 // contains the array of value profile data for profiled targets, 193 // TotalCount is the total profiled count of call executions, and 194 // NumCandidates is the number of candidate entries in ValueDataRef. 195 std::vector<PromotionCandidate> getPromotionCandidatesForCallSite( 196 const CallBase &CB, const ArrayRef<InstrProfValueData> &ValueDataRef, 197 uint64_t TotalCount, uint32_t NumCandidates); 198 199 // Promote a list of targets for one indirect-call callsite. Return 200 // the number of promotions. 201 uint32_t tryToPromote(CallBase &CB, 202 const std::vector<PromotionCandidate> &Candidates, 203 uint64_t &TotalCount); 204 205 public: 206 ICallPromotionFunc(Function &Func, Module *Modu, InstrProfSymtab *Symtab, 207 bool SamplePGO, OptimizationRemarkEmitter &ORE) 208 : F(Func), M(Modu), Symtab(Symtab), SamplePGO(SamplePGO), ORE(ORE) {} 209 ICallPromotionFunc(const ICallPromotionFunc &) = delete; 210 ICallPromotionFunc &operator=(const ICallPromotionFunc &) = delete; 211 212 bool processFunction(ProfileSummaryInfo *PSI); 213 }; 214 215 } // end anonymous namespace 216 217 // Indirect-call promotion heuristic. The direct targets are sorted based on 218 // the count. Stop at the first target that is not promoted. 219 std::vector<ICallPromotionFunc::PromotionCandidate> 220 ICallPromotionFunc::getPromotionCandidatesForCallSite( 221 const CallBase &CB, const ArrayRef<InstrProfValueData> &ValueDataRef, 222 uint64_t TotalCount, uint32_t NumCandidates) { 223 std::vector<PromotionCandidate> Ret; 224 225 LLVM_DEBUG(dbgs() << " \nWork on callsite #" << NumOfPGOICallsites << CB 226 << " Num_targets: " << ValueDataRef.size() 227 << " Num_candidates: " << NumCandidates << "\n"); 228 NumOfPGOICallsites++; 229 if (ICPCSSkip != 0 && NumOfPGOICallsites <= ICPCSSkip) { 230 LLVM_DEBUG(dbgs() << " Skip: User options.\n"); 231 return Ret; 232 } 233 234 for (uint32_t I = 0; I < NumCandidates; I++) { 235 uint64_t Count = ValueDataRef[I].Count; 236 assert(Count <= TotalCount); 237 (void)TotalCount; 238 uint64_t Target = ValueDataRef[I].Value; 239 LLVM_DEBUG(dbgs() << " Candidate " << I << " Count=" << Count 240 << " Target_func: " << Target << "\n"); 241 242 if (ICPInvokeOnly && isa<CallInst>(CB)) { 243 LLVM_DEBUG(dbgs() << " Not promote: User options.\n"); 244 ORE.emit([&]() { 245 return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", &CB) 246 << " Not promote: User options"; 247 }); 248 break; 249 } 250 if (ICPCallOnly && isa<InvokeInst>(CB)) { 251 LLVM_DEBUG(dbgs() << " Not promote: User option.\n"); 252 ORE.emit([&]() { 253 return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", &CB) 254 << " Not promote: User options"; 255 }); 256 break; 257 } 258 if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) { 259 LLVM_DEBUG(dbgs() << " Not promote: Cutoff reached.\n"); 260 ORE.emit([&]() { 261 return OptimizationRemarkMissed(DEBUG_TYPE, "CutOffReached", &CB) 262 << " Not promote: Cutoff reached"; 263 }); 264 break; 265 } 266 267 // Don't promote if the symbol is not defined in the module. This avoids 268 // creating a reference to a symbol that doesn't exist in the module 269 // This can happen when we compile with a sample profile collected from 270 // one binary but used for another, which may have profiled targets that 271 // aren't used in the new binary. We might have a declaration initially in 272 // the case where the symbol is globally dead in the binary and removed by 273 // ThinLTO. 274 Function *TargetFunction = Symtab->getFunction(Target); 275 if (TargetFunction == nullptr || TargetFunction->isDeclaration()) { 276 LLVM_DEBUG(dbgs() << " Not promote: Cannot find the target\n"); 277 ORE.emit([&]() { 278 return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToFindTarget", &CB) 279 << "Cannot promote indirect call: target with md5sum " 280 << ore::NV("target md5sum", Target) << " not found"; 281 }); 282 break; 283 } 284 285 const char *Reason = nullptr; 286 if (!isLegalToPromote(CB, TargetFunction, &Reason)) { 287 using namespace ore; 288 289 ORE.emit([&]() { 290 return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToPromote", &CB) 291 << "Cannot promote indirect call to " 292 << NV("TargetFunction", TargetFunction) << " with count of " 293 << NV("Count", Count) << ": " << Reason; 294 }); 295 break; 296 } 297 298 Ret.push_back(PromotionCandidate(TargetFunction, Count)); 299 TotalCount -= Count; 300 } 301 return Ret; 302 } 303 304 CallBase &llvm::pgo::promoteIndirectCall(CallBase &CB, Function *DirectCallee, 305 uint64_t Count, uint64_t TotalCount, 306 bool AttachProfToDirectCall, 307 OptimizationRemarkEmitter *ORE) { 308 309 uint64_t ElseCount = TotalCount - Count; 310 uint64_t MaxCount = (Count >= ElseCount ? Count : ElseCount); 311 uint64_t Scale = calculateCountScale(MaxCount); 312 MDBuilder MDB(CB.getContext()); 313 MDNode *BranchWeights = MDB.createBranchWeights( 314 scaleBranchCount(Count, Scale), scaleBranchCount(ElseCount, Scale)); 315 316 CallBase &NewInst = 317 promoteCallWithIfThenElse(CB, DirectCallee, BranchWeights); 318 319 if (AttachProfToDirectCall) { 320 MDBuilder MDB(NewInst.getContext()); 321 NewInst.setMetadata( 322 LLVMContext::MD_prof, 323 MDB.createBranchWeights({static_cast<uint32_t>(Count)})); 324 } 325 326 using namespace ore; 327 328 if (ORE) 329 ORE->emit([&]() { 330 return OptimizationRemark(DEBUG_TYPE, "Promoted", &CB) 331 << "Promote indirect call to " << NV("DirectCallee", DirectCallee) 332 << " with count " << NV("Count", Count) << " out of " 333 << NV("TotalCount", TotalCount); 334 }); 335 return NewInst; 336 } 337 338 // Promote indirect-call to conditional direct-call for one callsite. 339 uint32_t ICallPromotionFunc::tryToPromote( 340 CallBase &CB, const std::vector<PromotionCandidate> &Candidates, 341 uint64_t &TotalCount) { 342 uint32_t NumPromoted = 0; 343 344 for (auto &C : Candidates) { 345 uint64_t Count = C.Count; 346 pgo::promoteIndirectCall(CB, C.TargetFunction, Count, TotalCount, SamplePGO, 347 &ORE); 348 assert(TotalCount >= Count); 349 TotalCount -= Count; 350 NumOfPGOICallPromotion++; 351 NumPromoted++; 352 } 353 return NumPromoted; 354 } 355 356 // Traverse all the indirect-call callsite and get the value profile 357 // annotation to perform indirect-call promotion. 358 bool ICallPromotionFunc::processFunction(ProfileSummaryInfo *PSI) { 359 bool Changed = false; 360 ICallPromotionAnalysis ICallAnalysis; 361 for (auto *CB : findIndirectCalls(F)) { 362 uint32_t NumVals, NumCandidates; 363 uint64_t TotalCount; 364 auto ICallProfDataRef = ICallAnalysis.getPromotionCandidatesForInstruction( 365 CB, NumVals, TotalCount, NumCandidates); 366 if (!NumCandidates || 367 (PSI && PSI->hasProfileSummary() && !PSI->isHotCount(TotalCount))) 368 continue; 369 auto PromotionCandidates = getPromotionCandidatesForCallSite( 370 *CB, ICallProfDataRef, TotalCount, NumCandidates); 371 uint32_t NumPromoted = tryToPromote(*CB, PromotionCandidates, TotalCount); 372 if (NumPromoted == 0) 373 continue; 374 375 Changed = true; 376 // Adjust the MD.prof metadata. First delete the old one. 377 CB->setMetadata(LLVMContext::MD_prof, nullptr); 378 // If all promoted, we don't need the MD.prof metadata. 379 if (TotalCount == 0 || NumPromoted == NumVals) 380 continue; 381 // Otherwise we need update with the un-promoted records back. 382 annotateValueSite(*M, *CB, ICallProfDataRef.slice(NumPromoted), TotalCount, 383 IPVK_IndirectCallTarget, NumCandidates); 384 } 385 return Changed; 386 } 387 388 // A wrapper function that does the actual work. 389 static bool promoteIndirectCalls(Module &M, ProfileSummaryInfo *PSI, 390 bool InLTO, bool SamplePGO, 391 ModuleAnalysisManager *AM = nullptr) { 392 if (DisableICP) 393 return false; 394 InstrProfSymtab Symtab; 395 if (Error E = Symtab.create(M, InLTO)) { 396 std::string SymtabFailure = toString(std::move(E)); 397 M.getContext().emitError("Failed to create symtab: " + SymtabFailure); 398 return false; 399 } 400 bool Changed = false; 401 for (auto &F : M) { 402 if (F.isDeclaration() || F.hasOptNone()) 403 continue; 404 405 std::unique_ptr<OptimizationRemarkEmitter> OwnedORE; 406 OptimizationRemarkEmitter *ORE; 407 if (AM) { 408 auto &FAM = 409 AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 410 ORE = &FAM.getResult<OptimizationRemarkEmitterAnalysis>(F); 411 } else { 412 OwnedORE = std::make_unique<OptimizationRemarkEmitter>(&F); 413 ORE = OwnedORE.get(); 414 } 415 416 ICallPromotionFunc ICallPromotion(F, &M, &Symtab, SamplePGO, *ORE); 417 bool FuncChanged = ICallPromotion.processFunction(PSI); 418 if (ICPDUMPAFTER && FuncChanged) { 419 LLVM_DEBUG(dbgs() << "\n== IR Dump After =="; F.print(dbgs())); 420 LLVM_DEBUG(dbgs() << "\n"); 421 } 422 Changed |= FuncChanged; 423 if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) { 424 LLVM_DEBUG(dbgs() << " Stop: Cutoff reached.\n"); 425 break; 426 } 427 } 428 return Changed; 429 } 430 431 bool PGOIndirectCallPromotionLegacyPass::runOnModule(Module &M) { 432 ProfileSummaryInfo *PSI = 433 &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 434 435 // Command-line option has the priority for InLTO. 436 return promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode, 437 SamplePGO | ICPSamplePGOMode); 438 } 439 440 PreservedAnalyses PGOIndirectCallPromotion::run(Module &M, 441 ModuleAnalysisManager &AM) { 442 ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M); 443 444 if (!promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode, 445 SamplePGO | ICPSamplePGOMode, &AM)) 446 return PreservedAnalyses::all(); 447 448 return PreservedAnalyses::none(); 449 } 450