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