LLVM  6.0.0svn
IndirectCallPromotion.cpp
Go to the documentation of this file.
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"
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"
42 #include "llvm/Support/Casting.h"
44 #include "llvm/Support/Error.h"
45 #include "llvm/Support/Debug.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) {
126  }
127 
128  void getAnalysisUsage(AnalysisUsage &AU) const override {
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 
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)
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 
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 
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  Instruction *Inst, 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(Instruction *Inst,
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 
218  const char **Reason) {
219  // Check the return type.
220  Type *CallRetType = Inst->getType();
221  if (!CallRetType->isVoidTy()) {
222  Type *FuncRetType = F->getReturnType();
223  if (FuncRetType != CallRetType &&
224  !CastInst::isBitCastable(FuncRetType, CallRetType)) {
225  if (Reason)
226  *Reason = "Return type mismatch";
227  return false;
228  }
229  }
230 
231  // Check if the arguments are compatible with the parameters
232  FunctionType *DirectCalleeType = F->getFunctionType();
233  unsigned ParamNum = DirectCalleeType->getFunctionNumParams();
234  CallSite CS(Inst);
235  unsigned ArgNum = CS.arg_size();
236 
237  if (ParamNum != ArgNum && !DirectCalleeType->isVarArg()) {
238  if (Reason)
239  *Reason = "The number of arguments mismatch";
240  return false;
241  }
242 
243  for (unsigned I = 0; I < ParamNum; ++I) {
244  Type *PTy = DirectCalleeType->getFunctionParamType(I);
245  Type *ATy = CS.getArgument(I)->getType();
246  if (PTy == ATy)
247  continue;
248  if (!CastInst::castIsValid(Instruction::BitCast, CS.getArgument(I), PTy)) {
249  if (Reason)
250  *Reason = "Argument type mismatch";
251  return false;
252  }
253  }
254 
255  DEBUG(dbgs() << " #" << NumOfPGOICallPromotion << " Promote the icall to "
256  << F->getName() << "\n");
257  return true;
258 }
259 
260 // Indirect-call promotion heuristic. The direct targets are sorted based on
261 // the count. Stop at the first target that is not promoted.
262 std::vector<ICallPromotionFunc::PromotionCandidate>
263 ICallPromotionFunc::getPromotionCandidatesForCallSite(
264  Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
265  uint64_t TotalCount, uint32_t NumCandidates) {
266  std::vector<PromotionCandidate> Ret;
267 
268  DEBUG(dbgs() << " \nWork on callsite #" << NumOfPGOICallsites << *Inst
269  << " Num_targets: " << ValueDataRef.size()
270  << " Num_candidates: " << NumCandidates << "\n");
271  NumOfPGOICallsites++;
272  if (ICPCSSkip != 0 && NumOfPGOICallsites <= ICPCSSkip) {
273  DEBUG(dbgs() << " Skip: User options.\n");
274  return Ret;
275  }
276 
277  for (uint32_t I = 0; I < NumCandidates; I++) {
278  uint64_t Count = ValueDataRef[I].Count;
279  assert(Count <= TotalCount);
280  uint64_t Target = ValueDataRef[I].Value;
281  DEBUG(dbgs() << " Candidate " << I << " Count=" << Count
282  << " Target_func: " << Target << "\n");
283 
284  if (ICPInvokeOnly && dyn_cast<CallInst>(Inst)) {
285  DEBUG(dbgs() << " Not promote: User options.\n");
286  ORE.emit([&]() {
287  return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", Inst)
288  << " Not promote: User options";
289  });
290  break;
291  }
292  if (ICPCallOnly && dyn_cast<InvokeInst>(Inst)) {
293  DEBUG(dbgs() << " Not promote: User option.\n");
294  ORE.emit([&]() {
295  return OptimizationRemarkMissed(DEBUG_TYPE, "UserOptions", Inst)
296  << " Not promote: User options";
297  });
298  break;
299  }
300  if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
301  DEBUG(dbgs() << " Not promote: Cutoff reached.\n");
302  ORE.emit([&]() {
303  return OptimizationRemarkMissed(DEBUG_TYPE, "CutOffReached", Inst)
304  << " Not promote: Cutoff reached";
305  });
306  break;
307  }
308 
309  Function *TargetFunction = Symtab->getFunction(Target);
310  if (TargetFunction == nullptr) {
311  DEBUG(dbgs() << " Not promote: Cannot find the target\n");
312  ORE.emit([&]() {
313  return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToFindTarget", Inst)
314  << "Cannot promote indirect call: target not found";
315  });
316  break;
317  }
318 
319  const char *Reason = nullptr;
320  if (!isLegalToPromote(Inst, TargetFunction, &Reason)) {
321  using namespace ore;
322 
323  ORE.emit([&]() {
324  return OptimizationRemarkMissed(DEBUG_TYPE, "UnableToPromote", Inst)
325  << "Cannot promote indirect call to "
326  << NV("TargetFunction", TargetFunction) << " with count of "
327  << NV("Count", Count) << ": " << Reason;
328  });
329  break;
330  }
331 
332  Ret.push_back(PromotionCandidate(TargetFunction, Count));
333  TotalCount -= Count;
334  }
335  return Ret;
336 }
337 
338 // Create a diamond structure for If_Then_Else. Also update the profile
339 // count. Do the fix-up for the invoke instruction.
340 static void createIfThenElse(Instruction *Inst, Function *DirectCallee,
341  uint64_t Count, uint64_t TotalCount,
342  BasicBlock **DirectCallBB,
343  BasicBlock **IndirectCallBB,
344  BasicBlock **MergeBB) {
345  CallSite CS(Inst);
346  Value *OrigCallee = CS.getCalledValue();
347 
348  IRBuilder<> BBBuilder(Inst);
349  LLVMContext &Ctx = Inst->getContext();
350  Value *BCI1 =
351  BBBuilder.CreateBitCast(OrigCallee, Type::getInt8PtrTy(Ctx), "");
352  Value *BCI2 =
353  BBBuilder.CreateBitCast(DirectCallee, Type::getInt8PtrTy(Ctx), "");
354  Value *PtrCmp = BBBuilder.CreateICmpEQ(BCI1, BCI2, "");
355 
356  uint64_t ElseCount = TotalCount - Count;
357  uint64_t MaxCount = (Count >= ElseCount ? Count : ElseCount);
358  uint64_t Scale = calculateCountScale(MaxCount);
359  MDBuilder MDB(Inst->getContext());
360  MDNode *BranchWeights = MDB.createBranchWeights(
361  scaleBranchCount(Count, Scale), scaleBranchCount(ElseCount, Scale));
362  TerminatorInst *ThenTerm, *ElseTerm;
363  SplitBlockAndInsertIfThenElse(PtrCmp, Inst, &ThenTerm, &ElseTerm,
364  BranchWeights);
365  *DirectCallBB = ThenTerm->getParent();
366  (*DirectCallBB)->setName("if.true.direct_targ");
367  *IndirectCallBB = ElseTerm->getParent();
368  (*IndirectCallBB)->setName("if.false.orig_indirect");
369  *MergeBB = Inst->getParent();
370  (*MergeBB)->setName("if.end.icp");
371 
372  // Special handing of Invoke instructions.
373  InvokeInst *II = dyn_cast<InvokeInst>(Inst);
374  if (!II)
375  return;
376 
377  // We don't need branch instructions for invoke.
378  ThenTerm->eraseFromParent();
379  ElseTerm->eraseFromParent();
380 
381  // Add jump from Merge BB to the NormalDest. This is needed for the newly
382  // created direct invoke stmt -- as its NormalDst will be fixed up to MergeBB.
383  BranchInst::Create(II->getNormalDest(), *MergeBB);
384 }
385 
386 // Find the PHI in BB that have the CallResult as the operand.
387 static bool getCallRetPHINode(BasicBlock *BB, Instruction *Inst) {
388  BasicBlock *From = Inst->getParent();
389  for (auto &I : *BB) {
390  PHINode *PHI = dyn_cast<PHINode>(&I);
391  if (!PHI)
392  continue;
393  int IX = PHI->getBasicBlockIndex(From);
394  if (IX == -1)
395  continue;
396  Value *V = PHI->getIncomingValue(IX);
397  if (dyn_cast<Instruction>(V) == Inst)
398  return true;
399  }
400  return false;
401 }
402 
403 // This method fixes up PHI nodes in BB where BB is the UnwindDest of an
404 // invoke instruction. In BB, there may be PHIs with incoming block being
405 // OrigBB (the MergeBB after if-then-else splitting). After moving the invoke
406 // instructions to its own BB, OrigBB is no longer the predecessor block of BB.
407 // Instead two new predecessors are added: IndirectCallBB and DirectCallBB,
408 // so the PHI node's incoming BBs need to be fixed up accordingly.
410  BasicBlock *OrigBB,
411  BasicBlock *IndirectCallBB,
412  BasicBlock *DirectCallBB) {
413  for (auto &I : *BB) {
414  PHINode *PHI = dyn_cast<PHINode>(&I);
415  if (!PHI)
416  continue;
417  int IX = PHI->getBasicBlockIndex(OrigBB);
418  if (IX == -1)
419  continue;
420  Value *V = PHI->getIncomingValue(IX);
421  PHI->addIncoming(V, IndirectCallBB);
422  PHI->setIncomingBlock(IX, DirectCallBB);
423  }
424 }
425 
426 // This method fixes up PHI nodes in BB where BB is the NormalDest of an
427 // invoke instruction. In BB, there may be PHIs with incoming block being
428 // OrigBB (the MergeBB after if-then-else splitting). After moving the invoke
429 // instructions to its own BB, a new incoming edge will be added to the original
430 // NormalDstBB from the IndirectCallBB.
432  BasicBlock *OrigBB,
433  BasicBlock *IndirectCallBB,
434  Instruction *NewInst) {
435  for (auto &I : *BB) {
436  PHINode *PHI = dyn_cast<PHINode>(&I);
437  if (!PHI)
438  continue;
439  int IX = PHI->getBasicBlockIndex(OrigBB);
440  if (IX == -1)
441  continue;
442  Value *V = PHI->getIncomingValue(IX);
443  if (dyn_cast<Instruction>(V) == Inst) {
444  PHI->setIncomingBlock(IX, IndirectCallBB);
445  PHI->addIncoming(NewInst, OrigBB);
446  continue;
447  }
448  PHI->addIncoming(V, IndirectCallBB);
449  }
450 }
451 
452 // Add a bitcast instruction to the direct-call return value if needed.
454  Instruction *DirectCallInst,
455  Function *DirectCallee) {
456  if (Inst->getType()->isVoidTy())
457  return DirectCallInst;
458 
459  Type *CallRetType = Inst->getType();
460  Type *FuncRetType = DirectCallee->getReturnType();
461  if (FuncRetType == CallRetType)
462  return DirectCallInst;
463 
464  BasicBlock *InsertionBB;
465  if (CallInst *CI = dyn_cast<CallInst>(DirectCallInst))
466  InsertionBB = CI->getParent();
467  else
468  InsertionBB = (dyn_cast<InvokeInst>(DirectCallInst))->getNormalDest();
469 
470  return (new BitCastInst(DirectCallInst, CallRetType, "",
471  InsertionBB->getTerminator()));
472 }
473 
474 // Create a DirectCall instruction in the DirectCallBB.
475 // Parameter Inst is the indirect-call (invoke) instruction.
476 // DirectCallee is the decl of the direct-call (invoke) target.
477 // DirecallBB is the BB that the direct-call (invoke) instruction is inserted.
478 // MergeBB is the bottom BB of the if-then-else-diamond after the
479 // transformation. For invoke instruction, the edges from DirectCallBB and
480 // IndirectCallBB to MergeBB are removed before this call (during
481 // createIfThenElse). Stores the pointer to the Instruction that cast
482 // the direct call in \p CastInst.
484  Function *DirectCallee,
485  BasicBlock *DirectCallBB,
486  BasicBlock *MergeBB,
487  Instruction *&CastInst) {
488  Instruction *NewInst = Inst->clone();
489  if (CallInst *CI = dyn_cast<CallInst>(NewInst)) {
490  CI->setCalledFunction(DirectCallee);
491  CI->mutateFunctionType(DirectCallee->getFunctionType());
492  } else {
493  // Must be an invoke instruction. Direct invoke's normal destination is
494  // fixed up to MergeBB. MergeBB is the place where return cast is inserted.
495  // Also since IndirectCallBB does not have an edge to MergeBB, there is no
496  // need to insert new PHIs into MergeBB.
497  InvokeInst *II = dyn_cast<InvokeInst>(NewInst);
498  assert(II);
499  II->setCalledFunction(DirectCallee);
500  II->mutateFunctionType(DirectCallee->getFunctionType());
501  II->setNormalDest(MergeBB);
502  }
503 
504  DirectCallBB->getInstList().insert(DirectCallBB->getFirstInsertionPt(),
505  NewInst);
506 
507  // Clear the value profile data.
508  NewInst->setMetadata(LLVMContext::MD_prof, nullptr);
509  CallSite NewCS(NewInst);
510  FunctionType *DirectCalleeType = DirectCallee->getFunctionType();
511  unsigned ParamNum = DirectCalleeType->getFunctionNumParams();
512  for (unsigned I = 0; I < ParamNum; ++I) {
513  Type *ATy = NewCS.getArgument(I)->getType();
514  Type *PTy = DirectCalleeType->getParamType(I);
515  if (ATy != PTy) {
516  BitCastInst *BI = new BitCastInst(NewCS.getArgument(I), PTy, "", NewInst);
517  NewCS.setArgument(I, BI);
518  }
519  }
520 
521  CastInst = insertCallRetCast(Inst, NewInst, DirectCallee);
522  return NewInst;
523 }
524 
525 // Create a PHI to unify the return values of calls.
526 static void insertCallRetPHI(Instruction *Inst, Instruction *CallResult,
527  Function *DirectCallee) {
528  if (Inst->getType()->isVoidTy())
529  return;
530 
531  if (Inst->use_empty())
532  return;
533 
534  BasicBlock *RetValBB = CallResult->getParent();
535 
536  BasicBlock *PHIBB;
537  if (InvokeInst *II = dyn_cast<InvokeInst>(CallResult))
538  RetValBB = II->getNormalDest();
539 
540  PHIBB = RetValBB->getSingleSuccessor();
541  if (getCallRetPHINode(PHIBB, Inst))
542  return;
543 
544  PHINode *CallRetPHI = PHINode::Create(Inst->getType(), 0);
545  PHIBB->getInstList().push_front(CallRetPHI);
546  Inst->replaceAllUsesWith(CallRetPHI);
547  CallRetPHI->addIncoming(Inst, Inst->getParent());
548  CallRetPHI->addIncoming(CallResult, RetValBB);
549 }
550 
551 // This function does the actual indirect-call promotion transformation:
552 // For an indirect-call like:
553 // Ret = (*Foo)(Args);
554 // It transforms to:
555 // if (Foo == DirectCallee)
556 // Ret1 = DirectCallee(Args);
557 // else
558 // Ret2 = (*Foo)(Args);
559 // Ret = phi(Ret1, Ret2);
560 // It adds type casts for the args do not match the parameters and the return
561 // value. Branch weights metadata also updated.
562 // If \p AttachProfToDirectCall is true, a prof metadata is attached to the
563 // new direct call to contain \p Count. This is used by SamplePGO inliner to
564 // check callsite hotness.
565 // Returns the promoted direct call instruction.
567  Function *DirectCallee, uint64_t Count,
568  uint64_t TotalCount,
569  bool AttachProfToDirectCall,
571  assert(DirectCallee != nullptr);
572  BasicBlock *BB = Inst->getParent();
573  // Just to suppress the non-debug build warning.
574  (void)BB;
575  DEBUG(dbgs() << "\n\n== Basic Block Before ==\n");
576  DEBUG(dbgs() << *BB << "\n");
577 
578  BasicBlock *DirectCallBB, *IndirectCallBB, *MergeBB;
579  createIfThenElse(Inst, DirectCallee, Count, TotalCount, &DirectCallBB,
580  &IndirectCallBB, &MergeBB);
581 
582  // If the return type of the NewInst is not the same as the Inst, a CastInst
583  // is needed for type casting. Otherwise CastInst is the same as NewInst.
584  Instruction *CastInst = nullptr;
585  Instruction *NewInst =
586  createDirectCallInst(Inst, DirectCallee, DirectCallBB, MergeBB, CastInst);
587 
588  if (AttachProfToDirectCall) {
589  SmallVector<uint32_t, 1> Weights;
590  Weights.push_back(Count);
591  MDBuilder MDB(NewInst->getContext());
592  NewInst->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
593  }
594 
595  // Move Inst from MergeBB to IndirectCallBB.
596  Inst->removeFromParent();
597  IndirectCallBB->getInstList().insert(IndirectCallBB->getFirstInsertionPt(),
598  Inst);
599 
600  if (InvokeInst *II = dyn_cast<InvokeInst>(Inst)) {
601  // At this point, the original indirect invoke instruction has the original
602  // UnwindDest and NormalDest. For the direct invoke instruction, the
603  // NormalDest points to MergeBB, and MergeBB jumps to the original
604  // NormalDest. MergeBB might have a new bitcast instruction for the return
605  // value. The PHIs are with the original NormalDest. Since we now have two
606  // incoming edges to NormalDest and UnwindDest, we have to do some fixups.
607  //
608  // UnwindDest will not use the return value. So pass nullptr here.
609  fixupPHINodeForUnwind(Inst, II->getUnwindDest(), MergeBB, IndirectCallBB,
610  DirectCallBB);
611  // We don't need to update the operand from NormalDest for DirectCallBB.
612  // Pass nullptr here.
613  fixupPHINodeForNormalDest(Inst, II->getNormalDest(), MergeBB,
614  IndirectCallBB, CastInst);
615  }
616 
617  insertCallRetPHI(Inst, CastInst, DirectCallee);
618 
619  DEBUG(dbgs() << "\n== Basic Blocks After ==\n");
620  DEBUG(dbgs() << *BB << *DirectCallBB << *IndirectCallBB << *MergeBB << "\n");
621 
622  using namespace ore;
623 
624  if (ORE)
625  ORE->emit([&]() {
626  return OptimizationRemark(DEBUG_TYPE, "Promoted", Inst)
627  << "Promote indirect call to " << NV("DirectCallee", DirectCallee)
628  << " with count " << NV("Count", Count) << " out of "
629  << NV("TotalCount", TotalCount);
630  });
631  return NewInst;
632 }
633 
634 // Promote indirect-call to conditional direct-call for one callsite.
635 uint32_t ICallPromotionFunc::tryToPromote(
636  Instruction *Inst, const std::vector<PromotionCandidate> &Candidates,
637  uint64_t &TotalCount) {
638  uint32_t NumPromoted = 0;
639 
640  for (auto &C : Candidates) {
641  uint64_t Count = C.Count;
642  promoteIndirectCall(Inst, C.TargetFunction, Count, TotalCount, SamplePGO,
643  &ORE);
644  assert(TotalCount >= Count);
645  TotalCount -= Count;
646  NumOfPGOICallPromotion++;
647  NumPromoted++;
648  }
649  return NumPromoted;
650 }
651 
652 // Traverse all the indirect-call callsite and get the value profile
653 // annotation to perform indirect-call promotion.
654 bool ICallPromotionFunc::processFunction(ProfileSummaryInfo *PSI) {
655  bool Changed = false;
656  ICallPromotionAnalysis ICallAnalysis;
657  for (auto &I : findIndirectCallSites(F)) {
658  uint32_t NumVals, NumCandidates;
659  uint64_t TotalCount;
660  auto ICallProfDataRef = ICallAnalysis.getPromotionCandidatesForInstruction(
661  I, NumVals, TotalCount, NumCandidates);
662  if (!NumCandidates ||
663  (PSI && PSI->hasProfileSummary() && !PSI->isHotCount(TotalCount)))
664  continue;
665  auto PromotionCandidates = getPromotionCandidatesForCallSite(
666  I, ICallProfDataRef, TotalCount, NumCandidates);
667  uint32_t NumPromoted = tryToPromote(I, PromotionCandidates, TotalCount);
668  if (NumPromoted == 0)
669  continue;
670 
671  Changed = true;
672  // Adjust the MD.prof metadata. First delete the old one.
673  I->setMetadata(LLVMContext::MD_prof, nullptr);
674  // If all promoted, we don't need the MD.prof metadata.
675  if (TotalCount == 0 || NumPromoted == NumVals)
676  continue;
677  // Otherwise we need update with the un-promoted records back.
678  annotateValueSite(*M, *I, ICallProfDataRef.slice(NumPromoted), TotalCount,
679  IPVK_IndirectCallTarget, NumCandidates);
680  }
681  return Changed;
682 }
683 
684 // A wrapper function that does the actual work.
686  bool InLTO, bool SamplePGO,
687  ModuleAnalysisManager *AM = nullptr) {
688  if (DisableICP)
689  return false;
690  InstrProfSymtab Symtab;
691  if (Error E = Symtab.create(M, InLTO)) {
692  std::string SymtabFailure = toString(std::move(E));
693  DEBUG(dbgs() << "Failed to create symtab: " << SymtabFailure << "\n");
694  (void)SymtabFailure;
695  return false;
696  }
697  bool Changed = false;
698  for (auto &F : M) {
699  if (F.isDeclaration())
700  continue;
701  if (F.hasFnAttribute(Attribute::OptimizeNone))
702  continue;
703 
704  std::unique_ptr<OptimizationRemarkEmitter> OwnedORE;
706  if (AM) {
707  auto &FAM =
708  AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
709  ORE = &FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);
710  } else {
711  OwnedORE = llvm::make_unique<OptimizationRemarkEmitter>(&F);
712  ORE = OwnedORE.get();
713  }
714 
715  ICallPromotionFunc ICallPromotion(F, &M, &Symtab, SamplePGO, *ORE);
716  bool FuncChanged = ICallPromotion.processFunction(PSI);
717  if (ICPDUMPAFTER && FuncChanged) {
718  DEBUG(dbgs() << "\n== IR Dump After =="; F.print(dbgs()));
719  DEBUG(dbgs() << "\n");
720  }
721  Changed |= FuncChanged;
722  if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
723  DEBUG(dbgs() << " Stop: Cutoff reached.\n");
724  break;
725  }
726  }
727  return Changed;
728 }
729 
730 bool PGOIndirectCallPromotionLegacyPass::runOnModule(Module &M) {
731  ProfileSummaryInfo *PSI =
732  getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
733 
734  // Command-line option has the priority for InLTO.
735  return promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode,
736  SamplePGO | ICPSamplePGOMode);
737 }
738 
740  ModuleAnalysisManager &AM) {
742 
743  if (!promoteIndirectCalls(M, PSI, InLTO | ICPLTOMode,
744  SamplePGO | ICPSamplePGOMode, &AM))
745  return PreservedAnalyses::all();
746 
747  return PreservedAnalyses::none();
748 }
ArrayRef< InstrProfValueData > getPromotionCandidatesForInstruction(const Instruction *I, uint32_t &NumVals, uint64_t &TotalCount, uint32_t &NumCandidates)
Returns reference to array of InstrProfValueData for the given instruction I.
uint64_t CallInst * C
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:69
static cl::opt< unsigned > ICPCSSkip("icp-csskip", cl::init(0), cl::Hidden, cl::ZeroOrMore, cl::desc("Skip Callsite up to this number for this compilation"))
A symbol table used for function PGO name look-up with keys (such as pointers, md5hash values) to the...
Definition: InstrProf.h:411
#define DEBUG_TYPE
Diagnostic information for missed-optimization remarks.
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
void SplitBlockAndInsertIfThenElse(Value *Cond, Instruction *SplitBefore, TerminatorInst **ThenTerm, TerminatorInst **ElseTerm, MDNode *BranchWeights=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
DiagnosticInfoOptimizationBase::Argument NV
unsigned arg_size() const
Definition: CallSite.h:219
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Type * getParamType(unsigned i) const
Parameter type accessors.
Definition: DerivedTypes.h:135
void setCalledFunction(Value *Fn)
Set the function called.
unsigned getFunctionNumParams() const
Definition: DerivedTypes.h:157
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:63
static void createIfThenElse(Instruction *Inst, Function *DirectCallee, uint64_t Count, uint64_t TotalCount, BasicBlock **DirectCallBB, BasicBlock **IndirectCallBB, BasicBlock **MergeBB)
static Instruction * createDirectCallInst(const Instruction *Inst, Function *DirectCallee, BasicBlock *DirectCallBB, BasicBlock *MergeBB, Instruction *&CastInst)
Analysis providing profile information.
This class represents a function call, abstracting a target machine&#39;s calling convention.
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:697
STATISTIC(NumFunctions, "Total number of functions")
Metadata node.
Definition: Metadata.h:862
F(f)
bool isHotCount(uint64_t C)
Returns true if F is a hot function.
static cl::opt< bool > DisableICP("disable-icp", cl::init(false), cl::Hidden, cl::desc("Disable indirect call promotion"))
AnalysisUsage & addRequired()
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
static bool castIsValid(Instruction::CastOps op, Value *S, Type *DstTy)
This method can be used to determine if a cast from S to DstTy using Opcode op is valid or not...
std::string toString(Error E)
Write all error messages (if any) in E to a string.
Definition: Error.h:938
static void fixupPHINodeForNormalDest(Instruction *Inst, BasicBlock *BB, BasicBlock *OrigBB, BasicBlock *IndirectCallBB, Instruction *NewInst)
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:560
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:664
This file contains the simple types necessary to represent the attributes associated with functions a...
void setName(const Twine &Name)
Change the name of the value.
Definition: Value.cpp:284
Type * getFunctionParamType(unsigned i) const
Definition: DerivedTypes.h:153
void setArgument(unsigned ArgNo, Value *newVal)
Definition: CallSite.h:191
ValTy * getCalledValue() const
Return the pointer to function that is being called.
Definition: CallSite.h:100
Instruction * clone() const
Create a copy of &#39;this&#39; instruction that is identical in all ways except the following: ...
Class to represent function types.
Definition: DerivedTypes.h:103
This file provides the interface for IR based instrumentation passes ( (profile-gen, and profile-use).
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
Definition: IRBuilder.h:1444
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
static bool promoteIndirectCalls(Module &M, ProfileSummaryInfo *PSI, bool InLTO, bool SamplePGO, ModuleAnalysisManager *AM=nullptr)
void setNormalDest(BasicBlock *B)
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
Definition: BasicBlock.cpp:244
bool isVarArg() const
Definition: DerivedTypes.h:123
static cl::opt< bool > ICPLTOMode("icp-lto", cl::init(false), cl::Hidden, cl::desc("Run indirect-call promotion in LTO " "mode"))
This class represents a no-op cast from one type to another.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:33
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:428
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:156
Interface to identify indirect call promotion candidates.
bool hasProfileSummary()
Returns true if profile summary is available.
static bool getCallRetPHINode(BasicBlock *BB, Instruction *Inst)
bool isVoidTy() const
Return true if this is &#39;void&#39;.
Definition: Type.h:141
xray instrumentation
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
Type * getReturnType() const
Returns the type of the ret val.
Definition: Function.h:150
Subclasses of this class are all able to terminate a basic block.
Definition: InstrTypes.h:54
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
Definition: BasicBlock.cpp:200
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
void push_front(pointer val)
Definition: ilist.h:325
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:149
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static void insertCallRetPHI(Instruction *Inst, Instruction *CallResult, Function *DirectCallee)
Diagnostic information for applied optimization remarks.
static bool isBitCastable(Type *SrcTy, Type *DestTy)
Check whether a bitcast between these types is valid.
Represent the analysis usage information of a pass.
bool isLegalToPromote(Instruction *Inst, Function *F, const char **Reason)
INITIALIZE_PASS_BEGIN(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom", "Use PGO instrumentation profile to promote indirect " "calls to direct calls.", false, false) INITIALIZE_PASS_END(PGOIndirectCallPromotionLegacyPass
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Definition: IRBuilder.h:1546
static uint64_t calculateCountScale(uint64_t MaxCount)
Calculate what to divide by to scale counts.
pgo icall prom
static uint32_t scaleBranchCount(uint64_t Count, uint64_t Scale)
Scale an individual branch count.
void annotateValueSite(Module &M, Instruction &Inst, const InstrProfRecord &InstrProfR, InstrProfValueKind ValueKind, uint32_t SiteIndx, uint32_t MaxMDCount=3)
Get the value profile data for value site SiteIdx from InstrProfR and annotate the instruction Inst w...
Definition: InstrProf.cpp:811
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:220
static void fixupPHINodeForUnwind(Instruction *Inst, BasicBlock *BB, BasicBlock *OrigBB, BasicBlock *IndirectCallBB, BasicBlock *DirectCallBB)
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1214
BasicBlock * getNormalDest() const
const InstListType & getInstList() const
Return the underlying instruction list container.
Definition: BasicBlock.h:317
Error create(object::SectionRef &Section)
Create InstrProfSymtab from an object file section which contains function PGO names.
static cl::opt< bool > ICPSamplePGOMode("icp-samplepgo", cl::init(false), cl::Hidden, cl::desc("Run indirect-call promotion in SamplePGO mode"))
pgo icall Use PGO instrumentation profile to promote indirect calls to direct calls
void emit(DiagnosticInfoOptimizationBase &OptDiag)
Output the remark via the diagnostic handler and to the optimization record file. ...
void setIncomingBlock(unsigned i, BasicBlock *BB)
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:186
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
void mutateFunctionType(FunctionType *FTy)
void initializePGOIndirectCallPromotionLegacyPassPass(PassRegistry &)
static cl::opt< bool > ICPCallOnly("icp-call-only", cl::init(false), cl::Hidden, cl::desc("Run indirect-call promotion for call instructions " "only"))
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Instruction * promoteIndirectCall(Instruction *Inst, Function *F, uint64_t Count, uint64_t TotalCount, bool AttachProfToDirectCall, OptimizationRemarkEmitter *ORE)
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:145
Target - Wrapper for Target specific information.
static cl::opt< bool > ICPDUMPAFTER("icp-dumpafter", cl::init(false), cl::Hidden, cl::desc("Dump IR after transformation happens"))
void removeFromParent()
This method unlinks &#39;this&#39; from the containing basic block, but does not delete it.
Definition: Instruction.cpp:65
pgo instr Read PGO instrumentation profile
iterator insert(iterator where, pointer New)
Definition: ilist.h:241
static std::vector< Instruction * > findIndirectCallSites(Function &F)
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:218
static cl::opt< unsigned > ICPCutOff("icp-cutoff", cl::init(0), cl::Hidden, cl::ZeroOrMore, cl::desc("Max number of promotions for this compilation"))
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
static cl::opt< bool > ICPInvokeOnly("icp-invoke-only", cl::init(false), cl::Hidden, cl::desc("Run indirect-call promotion for " "invoke instruction only"))
#define I(x, y, z)
Definition: MD5.cpp:58
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:225
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
const Function * getFunction() const
Definition: Function.h:134
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
Lightweight error class with error context and mandatory checking.
Definition: Error.h:156
Invoke instruction.
#define DEBUG(X)
Definition: Debug.h:118
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
A container for analyses that lazily runs them and caches their results.
static Instruction * insertCallRetCast(const Instruction *Inst, Instruction *DirectCallInst, Function *DirectCallee)
const TerminatorInst * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:120
This header defines various interfaces for pass management in LLVM.
ModulePass * createPGOIndirectCallPromotionLegacyPass(bool InLTO=false, bool SamplePGO=false)
The optimization diagnostic interface.
bool use_empty() const
Definition: Value.h:322
const BasicBlock * getParent() const
Definition: Instruction.h:66
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:946