contrib/llvm/lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

   1 //===- IndirectCallPromotion.cpp - Optimizations based on value profiling -===//
   2 //
   3 //                      The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file implements the transformation that promotes indirect calls to
  11 // conditional direct calls when the indirect-call value profile metadata is
  12 // available.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/ADT/ArrayRef.h"
  17 #include "llvm/ADT/STLExtras.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/Statistic.h"
  20 #include "llvm/ADT/StringRef.h"
  21 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
  22 #include "llvm/Analysis/IndirectCallSiteVisitor.h"
  23 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
  24 #include "llvm/Analysis/ProfileSummaryInfo.h"
  25 #include "llvm/IR/Attributes.h"
  26 #include "llvm/IR/BasicBlock.h"
  27 #include "llvm/IR/CallSite.h"
  28 #include "llvm/IR/DerivedTypes.h"
  29 #include "llvm/IR/DiagnosticInfo.h"
  30 #include "llvm/IR/Function.h"
  31 #include "llvm/IR/IRBuilder.h"
  32 #include "llvm/IR/InstrTypes.h"
  33 #include "llvm/IR/Instruction.h"
  34 #include "llvm/IR/Instructions.h"
  35 #include "llvm/IR/LLVMContext.h"
  36 #include "llvm/IR/MDBuilder.h"
  37 #include "llvm/IR/PassManager.h"
  38 #include "llvm/IR/Type.h"
  39 #include "llvm/IR/Value.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/Error.h"
  45 #include "llvm/Support/Debug.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 && dyn_cast<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 && dyn_cast<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 not found";
 273       });
 274       break;
 275     }
 276
 277     const char *Reason = nullptr;
 278     if (!isLegalToPromote(CallSite(Inst), TargetFunction, &Reason)) {
 279       using namespace ore;
 280
 281       ORE.emit([&]() {
 282         return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToPromote", Inst)
 283                << "Cannot promote indirect call to "
 284                << NV("TargetFunction", TargetFunction) << " with count of "
 285                << NV("Count", Count) << ": " << Reason;
 286       });
 287       break;
 288     }
 289
 290     Ret.push_back(PromotionCandidate(TargetFunction, Count));
 291     TotalCount -= Count;
 292   }
 293   return Ret;
 294 }
 295
 296 Instruction *llvm::pgo::promoteIndirectCall(Instruction *Inst,
 297                                             Function *DirectCallee,
 298                                             uint64_t Count, uint64_t TotalCount,
 299                                             bool AttachProfToDirectCall,
 300                                             OptimizationRemarkEmitter *ORE) {
 301
 302   uint64_t ElseCount = TotalCount - Count;
 303   uint64_t MaxCount = (Count >= ElseCount ? Count : ElseCount);
 304   uint64_t Scale = calculateCountScale(MaxCount);
 305   MDBuilder MDB(Inst->getContext());
 306   MDNode *BranchWeights = MDB.createBranchWeights(
 307       scaleBranchCount(Count, Scale), scaleBranchCount(ElseCount, Scale));
 308
 309   Instruction *NewInst =
 310       promoteCallWithIfThenElse(CallSite(Inst), DirectCallee, BranchWeights);
 311
 312   if (AttachProfToDirectCall) {
 313     SmallVector<uint32_t, 1> Weights;
 314     Weights.push_back(Count);
 315     MDBuilder MDB(NewInst->getContext());
 316     NewInst->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
 317   }
 318
 319   using namespace ore;
 320
 321   if (ORE)
 322     ORE->emit([&]() {
 323       return OptimizationRemark(DEBUG_TYPE, "Promoted", Inst)
 324              << "Promote indirect call to " << NV("DirectCallee", DirectCallee)
 325              << " with count " << NV("Count", Count) << " out of "
 326              << NV("TotalCount", TotalCount);
 327     });
 328   return NewInst;
 329 }
 330
 331 // Promote indirect-call to conditional direct-call for one callsite.
 332 uint32_t ICallPromotionFunc::tryToPromote(
 333     Instruction *Inst, const std::vector<PromotionCandidate> &Candidates,
 334     uint64_t &TotalCount) {
 335   uint32_t NumPromoted = 0;
 336
 337   for (auto &C : Candidates) {
 338     uint64_t Count = C.Count;
 339     pgo::promoteIndirectCall(Inst, C.TargetFunction, Count, TotalCount,
 340                              SamplePGO, &ORE);
 341     assert(TotalCount >= Count);
 342     TotalCount -= Count;
 343     NumOfPGOICallPromotion++;
 344     NumPromoted++;
 345   }
 346   return NumPromoted;
 347 }
 348
 349 // Traverse all the indirect-call callsite and get the value profile
 350 // annotation to perform indirect-call promotion.
 351 bool ICallPromotionFunc::processFunction(ProfileSummaryInfo *PSI) {
 352   bool Changed = false;
 353   ICallPromotionAnalysis ICallAnalysis;
 354   for (auto &I : findIndirectCallSites(F)) {
 355     uint32_t NumVals, NumCandidates;
 356     uint64_t TotalCount;
 357     auto ICallProfDataRef = ICallAnalysis.getPromotionCandidatesForInstruction(
 358         I, NumVals, TotalCount, NumCandidates);
 359     if (!NumCandidates ||
 360         (PSI && PSI->hasProfileSummary() && !PSI->isHotCount(TotalCount)))
 361       continue;
 362     auto PromotionCandidates = getPromotionCandidatesForCallSite(
 363         I, ICallProfDataRef, TotalCount, NumCandidates);
 364     uint32_t NumPromoted = tryToPromote(I, PromotionCandidates, TotalCount);
 365     if (NumPromoted == 0)
 366       continue;
 367
 368     Changed = true;
 369     // Adjust the MD.prof metadata. First delete the old one.
 370     I->setMetadata(LLVMContext::MD_prof, nullptr);
 371     // If all promoted, we don't need the MD.prof metadata.
 372     if (TotalCount == 0 || NumPromoted == NumVals)
 373       continue;
 374     // Otherwise we need update with the un-promoted records back.
 375     annotateValueSite(*M, *I, ICallProfDataRef.slice(NumPromoted), TotalCount,
 376                       IPVK_IndirectCallTarget, NumCandidates);
 377   }
 378   return Changed;
 379 }
 380
 381 // A wrapper function that does the actual work.
 382 static bool promoteIndirectCalls(Module &M, ProfileSummaryInfo *PSI,
 383                                  bool InLTO, bool SamplePGO,
 384                                  ModuleAnalysisManager *AM = nullptr) {
 385   if (DisableICP)
 386     return false;
 387   InstrProfSymtab Symtab;
 388   if (Error E = Symtab.create(M, InLTO)) {
 389     std::string SymtabFailure = toString(std::move(E));
 390     LLVM_DEBUG(dbgs() << "Failed to create symtab: " << SymtabFailure << "\n");
 391     (void)SymtabFailure;
 392     return false;
 393   }
 394   bool Changed = false;
 395   for (auto &F : M) {
 396     if (F.isDeclaration())
 397       continue;
 398     if (F.hasFnAttribute(Attribute::OptimizeNone))
 399       continue;
 400
 401     std::unique_ptr<OptimizationRemarkEmitter> OwnedORE;
 402     OptimizationRemarkEmitter *ORE;
 403     if (AM) {
 404       auto &FAM =
 405           AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
 406       ORE = &FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
 407     } else {
 408       OwnedORE = llvm::make_unique<OptimizationRemarkEmitter>(&F);
 409       ORE = OwnedORE.get();
 410     }
 411
 412     ICallPromotionFunc ICallPromotion(F, &M, &Symtab, SamplePGO, *ORE);
 413     bool FuncChanged = ICallPromotion.processFunction(PSI);
 414     if (ICPDUMPAFTER && FuncChanged) {
 415       LLVM_DEBUG(dbgs() << "\n== IR Dump After =="; F.print(dbgs()));
 416       LLVM_DEBUG(dbgs() << "\n");
 417     }
 418     Changed |= FuncChanged;
 419     if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
 420       LLVM_DEBUG(dbgs() << " Stop: Cutoff reached.\n");
 421       break;
 422     }
 423   }
 424   return Changed;
 425 }
 426
 427 bool PGOIndirectCallPromotionLegacyPass::runOnModule(Module &M) {
 428   ProfileSummaryInfo *PSI =
 429       getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
 430
 431   // Command-line option has the priority for InLTO.
 432   return promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode,
 433                               SamplePGO | ICPSamplePGOMode);
 434 }
 435
 436 PreservedAnalyses PGOIndirectCallPromotion::run(Module &M,
 437                                                 ModuleAnalysisManager &AM) {
 438   ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M);
 439
 440   if (!promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode,
 441                             SamplePGO | ICPSamplePGOMode, &AM))
 442     return PreservedAnalyses::all();
 443
 444   return PreservedAnalyses::none();
 445 }