llvm/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

   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 }