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
57using namespace llvm;
58
59#define DEBUG_TYPE "pgo-icall-prom"
60
61STATISTIC(NumOfPGOICallPromotion, "Number of indirect call promotions.");
62STATISTIC(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.
66static 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.
73static 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.
79static 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.
86static 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.
92static 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.
98static 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.
105static 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.
112static cl::opt<bool>
113    ICPDUMPAFTER("icp-dumpafter", cl::init(false), cl::Hidden,
114                 cl::desc("Dump IR after transformation happens"));
115
116namespace {
117
118class PGOIndirectCallPromotionLegacyPass : public ModulePass {
119public:
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
134private:
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
148char PGOIndirectCallPromotionLegacyPass::ID = 0;
149
150INITIALIZE_PASS_BEGIN(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom",
151                      "Use PGO instrumentation profile to promote indirect "
152                      "calls to direct calls.",
153                      false, false)
154INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
155INITIALIZE_PASS_END(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom",
156                    "Use PGO instrumentation profile to promote indirect "
157                    "calls to direct calls.",
158                    false, false)
159
160ModulePass *llvm::createPGOIndirectCallPromotionLegacyPass(bool InLTO,
161                                                           bool SamplePGO) {
162  return new PGOIndirectCallPromotionLegacyPass(InLTO, SamplePGO);
163}
164
165namespace {
166
167// The class for main data structure to promote indirect calls to conditional
168// direct calls.
169class ICallPromotionFunc {
170private:
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
205public:
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.
219std::vector<ICallPromotionFunc::PromotionCandidate>
220ICallPromotionFunc::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    uint64_t Target = ValueDataRef[I].Value;
238    LLVM_DEBUG(dbgs() << " Candidate " << I << " Count=" << Count
239                      << "  Target_func: " << Target << "\n");
240
241    if (ICPInvokeOnly && isa<CallInst>(CB)) {
242      LLVM_DEBUG(dbgs() << " Not promote: User options.\n");
243      ORE.emit([&]() {
244        return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", &CB)
245               << " Not promote: User options";
246      });
247      break;
248    }
249    if (ICPCallOnly && isa<InvokeInst>(CB)) {
250      LLVM_DEBUG(dbgs() << " Not promote: User option.\n");
251      ORE.emit([&]() {
252        return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", &CB)
253               << " Not promote: User options";
254      });
255      break;
256    }
257    if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
258      LLVM_DEBUG(dbgs() << " Not promote: Cutoff reached.\n");
259      ORE.emit([&]() {
260        return OptimizationRemarkMissed(DEBUG_TYPE, "CutOffReached", &CB)
261               << " Not promote: Cutoff reached";
262      });
263      break;
264    }
265
266    Function *TargetFunction = Symtab->getFunction(Target);
267    if (TargetFunction == nullptr) {
268      LLVM_DEBUG(dbgs() << " Not promote: Cannot find the target\n");
269      ORE.emit([&]() {
270        return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToFindTarget", &CB)
271               << "Cannot promote indirect call: target with md5sum "
272               << ore::NV("target md5sum", Target) << " not found";
273      });
274      break;
275    }
276
277    const char *Reason = nullptr;
278    if (!isLegalToPromote(CB, TargetFunction, &Reason)) {
279      using namespace ore;
280
281      ORE.emit([&]() {
282        return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToPromote", &CB)
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
296CallBase &llvm::pgo::promoteIndirectCall(CallBase &CB, Function *DirectCallee,
297                                         uint64_t Count, uint64_t TotalCount,
298                                         bool AttachProfToDirectCall,
299                                         OptimizationRemarkEmitter *ORE) {
300
301  uint64_t ElseCount = TotalCount - Count;
302  uint64_t MaxCount = (Count >= ElseCount ? Count : ElseCount);
303  uint64_t Scale = calculateCountScale(MaxCount);
304  MDBuilder MDB(CB.getContext());
305  MDNode *BranchWeights = MDB.createBranchWeights(
306      scaleBranchCount(Count, Scale), scaleBranchCount(ElseCount, Scale));
307
308  CallBase &NewInst =
309      promoteCallWithIfThenElse(CB, DirectCallee, BranchWeights);
310
311  if (AttachProfToDirectCall) {
312    MDBuilder MDB(NewInst.getContext());
313    NewInst.setMetadata(
314        LLVMContext::MD_prof,
315        MDB.createBranchWeights({static_cast<uint32_t>(Count)}));
316  }
317
318  using namespace ore;
319
320  if (ORE)
321    ORE->emit([&]() {
322      return OptimizationRemark(DEBUG_TYPE, "Promoted", &CB)
323             << "Promote indirect call to " << NV("DirectCallee", DirectCallee)
324             << " with count " << NV("Count", Count) << " out of "
325             << NV("TotalCount", TotalCount);
326    });
327  return NewInst;
328}
329
330// Promote indirect-call to conditional direct-call for one callsite.
331uint32_t ICallPromotionFunc::tryToPromote(
332    CallBase &CB, const std::vector<PromotionCandidate> &Candidates,
333    uint64_t &TotalCount) {
334  uint32_t NumPromoted = 0;
335
336  for (auto &C : Candidates) {
337    uint64_t Count = C.Count;
338    pgo::promoteIndirectCall(CB, C.TargetFunction, Count, TotalCount, SamplePGO,
339                             &ORE);
340    assert(TotalCount >= Count);
341    TotalCount -= Count;
342    NumOfPGOICallPromotion++;
343    NumPromoted++;
344  }
345  return NumPromoted;
346}
347
348// Traverse all the indirect-call callsite and get the value profile
349// annotation to perform indirect-call promotion.
350bool ICallPromotionFunc::processFunction(ProfileSummaryInfo *PSI) {
351  bool Changed = false;
352  ICallPromotionAnalysis ICallAnalysis;
353  for (auto *CB : findIndirectCalls(F)) {
354    uint32_t NumVals, NumCandidates;
355    uint64_t TotalCount;
356    auto ICallProfDataRef = ICallAnalysis.getPromotionCandidatesForInstruction(
357        CB, NumVals, TotalCount, NumCandidates);
358    if (!NumCandidates ||
359        (PSI && PSI->hasProfileSummary() && !PSI->isHotCount(TotalCount)))
360      continue;
361    auto PromotionCandidates = getPromotionCandidatesForCallSite(
362        *CB, ICallProfDataRef, TotalCount, NumCandidates);
363    uint32_t NumPromoted = tryToPromote(*CB, PromotionCandidates, TotalCount);
364    if (NumPromoted == 0)
365      continue;
366
367    Changed = true;
368    // Adjust the MD.prof metadata. First delete the old one.
369    CB->setMetadata(LLVMContext::MD_prof, nullptr);
370    // If all promoted, we don't need the MD.prof metadata.
371    if (TotalCount == 0 || NumPromoted == NumVals)
372      continue;
373    // Otherwise we need update with the un-promoted records back.
374    annotateValueSite(*M, *CB, ICallProfDataRef.slice(NumPromoted), TotalCount,
375                      IPVK_IndirectCallTarget, NumCandidates);
376  }
377  return Changed;
378}
379
380// A wrapper function that does the actual work.
381static bool promoteIndirectCalls(Module &M, ProfileSummaryInfo *PSI,
382                                 bool InLTO, bool SamplePGO,
383                                 ModuleAnalysisManager *AM = nullptr) {
384  if (DisableICP)
385    return false;
386  InstrProfSymtab Symtab;
387  if (Error E = Symtab.create(M, InLTO)) {
388    std::string SymtabFailure = toString(std::move(E));
389    LLVM_DEBUG(dbgs() << "Failed to create symtab: " << SymtabFailure << "\n");
390    (void)SymtabFailure;
391    return false;
392  }
393  bool Changed = false;
394  for (auto &F : M) {
395    if (F.isDeclaration() || F.hasOptNone())
396      continue;
397
398    std::unique_ptr<OptimizationRemarkEmitter> OwnedORE;
399    OptimizationRemarkEmitter *ORE;
400    if (AM) {
401      auto &FAM =
402          AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
403      ORE = &FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
404    } else {
405      OwnedORE = std::make_unique<OptimizationRemarkEmitter>(&F);
406      ORE = OwnedORE.get();
407    }
408
409    ICallPromotionFunc ICallPromotion(F, &M, &Symtab, SamplePGO, *ORE);
410    bool FuncChanged = ICallPromotion.processFunction(PSI);
411    if (ICPDUMPAFTER && FuncChanged) {
412      LLVM_DEBUG(dbgs() << "\n== IR Dump After =="; F.print(dbgs()));
413      LLVM_DEBUG(dbgs() << "\n");
414    }
415    Changed |= FuncChanged;
416    if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
417      LLVM_DEBUG(dbgs() << " Stop: Cutoff reached.\n");
418      break;
419    }
420  }
421  return Changed;
422}
423
424bool PGOIndirectCallPromotionLegacyPass::runOnModule(Module &M) {
425  ProfileSummaryInfo *PSI =
426      &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
427
428  // Command-line option has the priority for InLTO.
429  return promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode,
430                              SamplePGO | ICPSamplePGOMode);
431}
432
433PreservedAnalyses PGOIndirectCallPromotion::run(Module &M,
434                                                ModuleAnalysisManager &AM) {
435  ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M);
436
437  if (!promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode,
438                            SamplePGO | ICPSamplePGOMode, &AM))
439    return PreservedAnalyses::all();
440
441  return PreservedAnalyses::none();
442}
443