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/Statistic.h"
  18 #include "llvm/ADT/StringRef.h"
  19 #include "llvm/ADT/Twine.h"
  20 #include "llvm/Analysis/BlockFrequencyInfo.h"
  21 #include "llvm/Analysis/GlobalsModRef.h"
  22 #include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
  23 #include "llvm/Analysis/IndirectCallSiteVisitor.h"
  24 #include "llvm/IR/BasicBlock.h"
  25 #include "llvm/IR/CallSite.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/Pass.h"
  38 #include "llvm/PassRegistry.h"
  39 #include "llvm/PassSupport.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/ErrorHandling.h"
  45 #include "llvm/Support/MathExtras.h"
  46 #include "llvm/Transforms/Instrumentation.h"
  47 #include "llvm/Transforms/PGOInstrumentation.h"
  48 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  49 #include <cassert>
  50 #include <cstdint>
  51 #include <vector>
  52
  53 using namespace llvm;
  54
  55 #define DEBUG_TYPE "pgo-icall-prom"
  56
  57 STATISTIC(NumOfPGOICallPromotion, "Number of indirect call promotions.");
  58 STATISTIC(NumOfPGOICallsites, "Number of indirect call candidate sites.");
  59
  60 // Command line option to disable indirect-call promotion with the default as
  61 // false. This is for debug purpose.
  62 static cl::opt<bool> DisableICP("disable-icp", cl::init(false), cl::Hidden,
  63                                 cl::desc("Disable indirect call promotion"));
  64
  65 // Set the cutoff value for the promotion. If the value is other than 0, we
  66 // stop the transformation once the total number of promotions equals the cutoff
  67 // value.
  68 // For debug use only.
  69 static cl::opt<unsigned>
  70     ICPCutOff("icp-cutoff", cl::init(0), cl::Hidden, cl::ZeroOrMore,
  71               cl::desc("Max number of promotions for this compilation"));
  72
  73 // If ICPCSSkip is non zero, the first ICPCSSkip callsites will be skipped.
  74 // For debug use only.
  75 static cl::opt<unsigned>
  76     ICPCSSkip("icp-csskip", cl::init(0), cl::Hidden, cl::ZeroOrMore,
  77               cl::desc("Skip Callsite up to this number for this compilation"));
  78
  79 // Set if the pass is called in LTO optimization. The difference for LTO mode
  80 // is the pass won't prefix the source module name to the internal linkage
  81 // symbols.
  82 static cl::opt<bool> ICPLTOMode("icp-lto", cl::init(false), cl::Hidden,
  83                                 cl::desc("Run indirect-call promotion in LTO "
  84                                          "mode"));
  85
  86 // Set if the pass is called in SamplePGO mode. The difference for SamplePGO
  87 // mode is it will add prof metadatato the created direct call.
  88 static cl::opt<bool>
  89     ICPSamplePGOMode("icp-samplepgo", cl::init(false), cl::Hidden,
  90                      cl::desc("Run indirect-call promotion in SamplePGO mode"));
  91
  92 // If the option is set to true, only call instructions will be considered for
  93 // transformation -- invoke instructions will be ignored.
  94 static cl::opt<bool>
  95     ICPCallOnly("icp-call-only", cl::init(false), cl::Hidden,
  96                 cl::desc("Run indirect-call promotion for call instructions "
  97                          "only"));
  98
  99 // If the option is set to true, only invoke instructions will be considered for
 100 // transformation -- call instructions will be ignored.
 101 static cl::opt<bool> ICPInvokeOnly("icp-invoke-only", cl::init(false),
 102                                    cl::Hidden,
 103                                    cl::desc("Run indirect-call promotion for "
 104                                             "invoke instruction only"));
 105
 106 // Dump the function level IR if the transformation happened in this
 107 // function. For debug use only.
 108 static cl::opt<bool>
 109     ICPDUMPAFTER("icp-dumpafter", cl::init(false), cl::Hidden,
 110                  cl::desc("Dump IR after transformation happens"));
 111
 112 namespace {
 113 class PGOIndirectCallPromotionLegacyPass : public ModulePass {
 114 public:
 115   static char ID;
 116
 117   PGOIndirectCallPromotionLegacyPass(bool InLTO = false, bool SamplePGO = false)
 118       : ModulePass(ID), InLTO(InLTO), SamplePGO(SamplePGO) {
 119     initializePGOIndirectCallPromotionLegacyPassPass(
 120         *PassRegistry::getPassRegistry());
 121   }
 122
 123   StringRef getPassName() const override { return "PGOIndirectCallPromotion"; }
 124
 125 private:
 126   bool runOnModule(Module &M) override;
 127
 128   // If this pass is called in LTO. We need to special handling the PGOFuncName
 129   // for the static variables due to LTO's internalization.
 130   bool InLTO;
 131
 132   // If this pass is called in SamplePGO. We need to add the prof metadata to
 133   // the promoted direct call.
 134   bool SamplePGO;
 135 };
 136 } // end anonymous namespace
 137
 138 char PGOIndirectCallPromotionLegacyPass::ID = 0;
 139 INITIALIZE_PASS(PGOIndirectCallPromotionLegacyPass, "pgo-icall-prom",
 140                 "Use PGO instrumentation profile to promote indirect calls to "
 141                 "direct calls.",
 142                 false, false)
 143
 144 ModulePass *llvm::createPGOIndirectCallPromotionLegacyPass(bool InLTO,
 145                                                            bool SamplePGO) {
 146   return new PGOIndirectCallPromotionLegacyPass(InLTO, SamplePGO);
 147 }
 148
 149 namespace {
 150 // The class for main data structure to promote indirect calls to conditional
 151 // direct calls.
 152 class ICallPromotionFunc {
 153 private:
 154   Function &F;
 155   Module *M;
 156
 157   // Symtab that maps indirect call profile values to function names and
 158   // defines.
 159   InstrProfSymtab *Symtab;
 160
 161   bool SamplePGO;
 162
 163   // Test if we can legally promote this direct-call of Target.
 164   bool isPromotionLegal(Instruction *Inst, uint64_t Target, Function *&F,
 165                         const char **Reason = nullptr);
 166
 167   // A struct that records the direct target and it's call count.
 168   struct PromotionCandidate {
 169     Function *TargetFunction;
 170     uint64_t Count;
 171     PromotionCandidate(Function *F, uint64_t C) : TargetFunction(F), Count(C) {}
 172   };
 173
 174   // Check if the indirect-call call site should be promoted. Return the number
 175   // of promotions. Inst is the candidate indirect call, ValueDataRef
 176   // contains the array of value profile data for profiled targets,
 177   // TotalCount is the total profiled count of call executions, and
 178   // NumCandidates is the number of candidate entries in ValueDataRef.
 179   std::vector<PromotionCandidate> getPromotionCandidatesForCallSite(
 180       Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
 181       uint64_t TotalCount, uint32_t NumCandidates);
 182
 183   // Promote a list of targets for one indirect-call callsite. Return
 184   // the number of promotions.
 185   uint32_t tryToPromote(Instruction *Inst,
 186                         const std::vector<PromotionCandidate> &Candidates,
 187                         uint64_t &TotalCount);
 188
 189   // Noncopyable
 190   ICallPromotionFunc(const ICallPromotionFunc &other) = delete;
 191   ICallPromotionFunc &operator=(const ICallPromotionFunc &other) = delete;
 192
 193 public:
 194   ICallPromotionFunc(Function &Func, Module *Modu, InstrProfSymtab *Symtab,
 195                      bool SamplePGO)
 196       : F(Func), M(Modu), Symtab(Symtab), SamplePGO(SamplePGO) {}
 197
 198   bool processFunction();
 199 };
 200 } // end anonymous namespace
 201
 202 bool llvm::isLegalToPromote(Instruction *Inst, Function *F,
 203                             const char **Reason) {
 204   // Check the return type.
 205   Type *CallRetType = Inst->getType();
 206   if (!CallRetType->isVoidTy()) {
 207     Type *FuncRetType = F->getReturnType();
 208     if (FuncRetType != CallRetType &&
 209         !CastInst::isBitCastable(FuncRetType, CallRetType)) {
 210       if (Reason)
 211         *Reason = "Return type mismatch";
 212       return false;
 213     }
 214   }
 215
 216   // Check if the arguments are compatible with the parameters
 217   FunctionType *DirectCalleeType = F->getFunctionType();
 218   unsigned ParamNum = DirectCalleeType->getFunctionNumParams();
 219   CallSite CS(Inst);
 220   unsigned ArgNum = CS.arg_size();
 221
 222   if (ParamNum != ArgNum && !DirectCalleeType->isVarArg()) {
 223     if (Reason)
 224       *Reason = "The number of arguments mismatch";
 225     return false;
 226   }
 227
 228   for (unsigned I = 0; I < ParamNum; ++I) {
 229     Type *PTy = DirectCalleeType->getFunctionParamType(I);
 230     Type *ATy = CS.getArgument(I)->getType();
 231     if (PTy == ATy)
 232       continue;
 233     if (!CastInst::castIsValid(Instruction::BitCast, CS.getArgument(I), PTy)) {
 234       if (Reason)
 235         *Reason = "Argument type mismatch";
 236       return false;
 237     }
 238   }
 239
 240   DEBUG(dbgs() << " #" << NumOfPGOICallPromotion << " Promote the icall to "
 241                << F->getName() << "\n");
 242   return true;
 243 }
 244
 245 bool ICallPromotionFunc::isPromotionLegal(Instruction *Inst, uint64_t Target,
 246                                           Function *&TargetFunction,
 247                                           const char **Reason) {
 248   TargetFunction = Symtab->getFunction(Target);
 249   if (TargetFunction == nullptr) {
 250     *Reason = "Cannot find the target";
 251     return false;
 252   }
 253   return isLegalToPromote(Inst, TargetFunction, Reason);
 254 }
 255
 256 // Indirect-call promotion heuristic. The direct targets are sorted based on
 257 // the count. Stop at the first target that is not promoted.
 258 std::vector<ICallPromotionFunc::PromotionCandidate>
 259 ICallPromotionFunc::getPromotionCandidatesForCallSite(
 260     Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
 261     uint64_t TotalCount, uint32_t NumCandidates) {
 262   std::vector<PromotionCandidate> Ret;
 263
 264   DEBUG(dbgs() << " \nWork on callsite #" << NumOfPGOICallsites << *Inst
 265                << " Num_targets: " << ValueDataRef.size()
 266                << " Num_candidates: " << NumCandidates << "\n");
 267   NumOfPGOICallsites++;
 268   if (ICPCSSkip != 0 && NumOfPGOICallsites <= ICPCSSkip) {
 269     DEBUG(dbgs() << " Skip: User options.\n");
 270     return Ret;
 271   }
 272
 273   for (uint32_t I = 0; I < NumCandidates; I++) {
 274     uint64_t Count = ValueDataRef[I].Count;
 275     assert(Count <= TotalCount);
 276     uint64_t Target = ValueDataRef[I].Value;
 277     DEBUG(dbgs() << " Candidate " << I << " Count=" << Count
 278                  << "  Target_func: " << Target << "\n");
 279
 280     if (ICPInvokeOnly && dyn_cast<CallInst>(Inst)) {
 281       DEBUG(dbgs() << " Not promote: User options.\n");
 282       break;
 283     }
 284     if (ICPCallOnly && dyn_cast<InvokeInst>(Inst)) {
 285       DEBUG(dbgs() << " Not promote: User option.\n");
 286       break;
 287     }
 288     if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
 289       DEBUG(dbgs() << " Not promote: Cutoff reached.\n");
 290       break;
 291     }
 292     Function *TargetFunction = nullptr;
 293     const char *Reason = nullptr;
 294     if (!isPromotionLegal(Inst, Target, TargetFunction, &Reason)) {
 295       StringRef TargetFuncName = Symtab->getFuncName(Target);
 296       DEBUG(dbgs() << " Not promote: " << Reason << "\n");
 297       emitOptimizationRemarkMissed(
 298           F.getContext(), "pgo-icall-prom", F, Inst->getDebugLoc(),
 299           Twine("Cannot promote indirect call to ") +
 300               (TargetFuncName.empty() ? Twine(Target) : Twine(TargetFuncName)) +
 301               Twine(" with count of ") + Twine(Count) + ": " + Reason);
 302       break;
 303     }
 304     Ret.push_back(PromotionCandidate(TargetFunction, Count));
 305     TotalCount -= Count;
 306   }
 307   return Ret;
 308 }
 309
 310 // Create a diamond structure for If_Then_Else. Also update the profile
 311 // count. Do the fix-up for the invoke instruction.
 312 static void createIfThenElse(Instruction *Inst, Function *DirectCallee,
 313                              uint64_t Count, uint64_t TotalCount,
 314                              BasicBlock **DirectCallBB,
 315                              BasicBlock **IndirectCallBB,
 316                              BasicBlock **MergeBB) {
 317   CallSite CS(Inst);
 318   Value *OrigCallee = CS.getCalledValue();
 319
 320   IRBuilder<> BBBuilder(Inst);
 321   LLVMContext &Ctx = Inst->getContext();
 322   Value *BCI1 =
 323       BBBuilder.CreateBitCast(OrigCallee, Type::getInt8PtrTy(Ctx), "");
 324   Value *BCI2 =
 325       BBBuilder.CreateBitCast(DirectCallee, Type::getInt8PtrTy(Ctx), "");
 326   Value *PtrCmp = BBBuilder.CreateICmpEQ(BCI1, BCI2, "");
 327
 328   uint64_t ElseCount = TotalCount - Count;
 329   uint64_t MaxCount = (Count >= ElseCount ? Count : ElseCount);
 330   uint64_t Scale = calculateCountScale(MaxCount);
 331   MDBuilder MDB(Inst->getContext());
 332   MDNode *BranchWeights = MDB.createBranchWeights(
 333       scaleBranchCount(Count, Scale), scaleBranchCount(ElseCount, Scale));
 334   TerminatorInst *ThenTerm, *ElseTerm;
 335   SplitBlockAndInsertIfThenElse(PtrCmp, Inst, &ThenTerm, &ElseTerm,
 336                                 BranchWeights);
 337   *DirectCallBB = ThenTerm->getParent();
 338   (*DirectCallBB)->setName("if.true.direct_targ");
 339   *IndirectCallBB = ElseTerm->getParent();
 340   (*IndirectCallBB)->setName("if.false.orig_indirect");
 341   *MergeBB = Inst->getParent();
 342   (*MergeBB)->setName("if.end.icp");
 343
 344   // Special handing of Invoke instructions.
 345   InvokeInst *II = dyn_cast<InvokeInst>(Inst);
 346   if (!II)
 347     return;
 348
 349   // We don't need branch instructions for invoke.
 350   ThenTerm->eraseFromParent();
 351   ElseTerm->eraseFromParent();
 352
 353   // Add jump from Merge BB to the NormalDest. This is needed for the newly
 354   // created direct invoke stmt -- as its NormalDst will be fixed up to MergeBB.
 355   BranchInst::Create(II->getNormalDest(), *MergeBB);
 356 }
 357
 358 // Find the PHI in BB that have the CallResult as the operand.
 359 static bool getCallRetPHINode(BasicBlock *BB, Instruction *Inst) {
 360   BasicBlock *From = Inst->getParent();
 361   for (auto &I : *BB) {
 362     PHINode *PHI = dyn_cast<PHINode>(&I);
 363     if (!PHI)
 364       continue;
 365     int IX = PHI->getBasicBlockIndex(From);
 366     if (IX == -1)
 367       continue;
 368     Value *V = PHI->getIncomingValue(IX);
 369     if (dyn_cast<Instruction>(V) == Inst)
 370       return true;
 371   }
 372   return false;
 373 }
 374
 375 // This method fixes up PHI nodes in BB where BB is the UnwindDest of an
 376 // invoke instruction. In BB, there may be PHIs with incoming block being
 377 // OrigBB (the MergeBB after if-then-else splitting). After moving the invoke
 378 // instructions to its own BB, OrigBB is no longer the predecessor block of BB.
 379 // Instead two new predecessors are added: IndirectCallBB and DirectCallBB,
 380 // so the PHI node's incoming BBs need to be fixed up accordingly.
 381 static void fixupPHINodeForUnwind(Instruction *Inst, BasicBlock *BB,
 382                                   BasicBlock *OrigBB,
 383                                   BasicBlock *IndirectCallBB,
 384                                   BasicBlock *DirectCallBB) {
 385   for (auto &I : *BB) {
 386     PHINode *PHI = dyn_cast<PHINode>(&I);
 387     if (!PHI)
 388       continue;
 389     int IX = PHI->getBasicBlockIndex(OrigBB);
 390     if (IX == -1)
 391       continue;
 392     Value *V = PHI->getIncomingValue(IX);
 393     PHI->addIncoming(V, IndirectCallBB);
 394     PHI->setIncomingBlock(IX, DirectCallBB);
 395   }
 396 }
 397
 398 // This method fixes up PHI nodes in BB where BB is the NormalDest of an
 399 // invoke instruction. In BB, there may be PHIs with incoming block being
 400 // OrigBB (the MergeBB after if-then-else splitting). After moving the invoke
 401 // instructions to its own BB, a new incoming edge will be added to the original
 402 // NormalDstBB from the IndirectCallBB.
 403 static void fixupPHINodeForNormalDest(Instruction *Inst, BasicBlock *BB,
 404                                       BasicBlock *OrigBB,
 405                                       BasicBlock *IndirectCallBB,
 406                                       Instruction *NewInst) {
 407   for (auto &I : *BB) {
 408     PHINode *PHI = dyn_cast<PHINode>(&I);
 409     if (!PHI)
 410       continue;
 411     int IX = PHI->getBasicBlockIndex(OrigBB);
 412     if (IX == -1)
 413       continue;
 414     Value *V = PHI->getIncomingValue(IX);
 415     if (dyn_cast<Instruction>(V) == Inst) {
 416       PHI->setIncomingBlock(IX, IndirectCallBB);
 417       PHI->addIncoming(NewInst, OrigBB);
 418       continue;
 419     }
 420     PHI->addIncoming(V, IndirectCallBB);
 421   }
 422 }
 423
 424 // Add a bitcast instruction to the direct-call return value if needed.
 425 static Instruction *insertCallRetCast(const Instruction *Inst,
 426                                       Instruction *DirectCallInst,
 427                                       Function *DirectCallee) {
 428   if (Inst->getType()->isVoidTy())
 429     return DirectCallInst;
 430
 431   Type *CallRetType = Inst->getType();
 432   Type *FuncRetType = DirectCallee->getReturnType();
 433   if (FuncRetType == CallRetType)
 434     return DirectCallInst;
 435
 436   BasicBlock *InsertionBB;
 437   if (CallInst *CI = dyn_cast<CallInst>(DirectCallInst))
 438     InsertionBB = CI->getParent();
 439   else
 440     InsertionBB = (dyn_cast<InvokeInst>(DirectCallInst))->getNormalDest();
 441
 442   return (new BitCastInst(DirectCallInst, CallRetType, "",
 443                           InsertionBB->getTerminator()));
 444 }
 445
 446 // Create a DirectCall instruction in the DirectCallBB.
 447 // Parameter Inst is the indirect-call (invoke) instruction.
 448 // DirectCallee is the decl of the direct-call (invoke) target.
 449 // DirecallBB is the BB that the direct-call (invoke) instruction is inserted.
 450 // MergeBB is the bottom BB of the if-then-else-diamond after the
 451 // transformation. For invoke instruction, the edges from DirectCallBB and
 452 // IndirectCallBB to MergeBB are removed before this call (during
 453 // createIfThenElse).
 454 static Instruction *createDirectCallInst(const Instruction *Inst,
 455                                          Function *DirectCallee,
 456                                          BasicBlock *DirectCallBB,
 457                                          BasicBlock *MergeBB) {
 458   Instruction *NewInst = Inst->clone();
 459   if (CallInst *CI = dyn_cast<CallInst>(NewInst)) {
 460     CI->setCalledFunction(DirectCallee);
 461     CI->mutateFunctionType(DirectCallee->getFunctionType());
 462   } else {
 463     // Must be an invoke instruction. Direct invoke's normal destination is
 464     // fixed up to MergeBB. MergeBB is the place where return cast is inserted.
 465     // Also since IndirectCallBB does not have an edge to MergeBB, there is no
 466     // need to insert new PHIs into MergeBB.
 467     InvokeInst *II = dyn_cast<InvokeInst>(NewInst);
 468     assert(II);
 469     II->setCalledFunction(DirectCallee);
 470     II->mutateFunctionType(DirectCallee->getFunctionType());
 471     II->setNormalDest(MergeBB);
 472   }
 473
 474   DirectCallBB->getInstList().insert(DirectCallBB->getFirstInsertionPt(),
 475                                      NewInst);
 476
 477   // Clear the value profile data.
 478   NewInst->setMetadata(LLVMContext::MD_prof, nullptr);
 479   CallSite NewCS(NewInst);
 480   FunctionType *DirectCalleeType = DirectCallee->getFunctionType();
 481   unsigned ParamNum = DirectCalleeType->getFunctionNumParams();
 482   for (unsigned I = 0; I < ParamNum; ++I) {
 483     Type *ATy = NewCS.getArgument(I)->getType();
 484     Type *PTy = DirectCalleeType->getParamType(I);
 485     if (ATy != PTy) {
 486       BitCastInst *BI = new BitCastInst(NewCS.getArgument(I), PTy, "", NewInst);
 487       NewCS.setArgument(I, BI);
 488     }
 489   }
 490
 491   return insertCallRetCast(Inst, NewInst, DirectCallee);
 492 }
 493
 494 // Create a PHI to unify the return values of calls.
 495 static void insertCallRetPHI(Instruction *Inst, Instruction *CallResult,
 496                              Function *DirectCallee) {
 497   if (Inst->getType()->isVoidTy())
 498     return;
 499
 500   BasicBlock *RetValBB = CallResult->getParent();
 501
 502   BasicBlock *PHIBB;
 503   if (InvokeInst *II = dyn_cast<InvokeInst>(CallResult))
 504     RetValBB = II->getNormalDest();
 505
 506   PHIBB = RetValBB->getSingleSuccessor();
 507   if (getCallRetPHINode(PHIBB, Inst))
 508     return;
 509
 510   PHINode *CallRetPHI = PHINode::Create(Inst->getType(), 0);
 511   PHIBB->getInstList().push_front(CallRetPHI);
 512   Inst->replaceAllUsesWith(CallRetPHI);
 513   CallRetPHI->addIncoming(Inst, Inst->getParent());
 514   CallRetPHI->addIncoming(CallResult, RetValBB);
 515 }
 516
 517 // This function does the actual indirect-call promotion transformation:
 518 // For an indirect-call like:
 519 //     Ret = (*Foo)(Args);
 520 // It transforms to:
 521 //     if (Foo == DirectCallee)
 522 //        Ret1 = DirectCallee(Args);
 523 //     else
 524 //        Ret2 = (*Foo)(Args);
 525 //     Ret = phi(Ret1, Ret2);
 526 // It adds type casts for the args do not match the parameters and the return
 527 // value. Branch weights metadata also updated.
 528 // If \p AttachProfToDirectCall is true, a prof metadata is attached to the
 529 // new direct call to contain \p Count. This is used by SamplePGO inliner to
 530 // check callsite hotness.
 531 // Returns the promoted direct call instruction.
 532 Instruction *llvm::promoteIndirectCall(Instruction *Inst,
 533                                        Function *DirectCallee, uint64_t Count,
 534                                        uint64_t TotalCount,
 535                                        bool AttachProfToDirectCall) {
 536   assert(DirectCallee != nullptr);
 537   BasicBlock *BB = Inst->getParent();
 538   // Just to suppress the non-debug build warning.
 539   (void)BB;
 540   DEBUG(dbgs() << "\n\n== Basic Block Before ==\n");
 541   DEBUG(dbgs() << *BB << "\n");
 542
 543   BasicBlock *DirectCallBB, *IndirectCallBB, *MergeBB;
 544   createIfThenElse(Inst, DirectCallee, Count, TotalCount, &DirectCallBB,
 545                    &IndirectCallBB, &MergeBB);
 546
 547   Instruction *NewInst =
 548       createDirectCallInst(Inst, DirectCallee, DirectCallBB, MergeBB);
 549
 550   if (AttachProfToDirectCall) {
 551     SmallVector<uint32_t, 1> Weights;
 552     Weights.push_back(Count);
 553     MDBuilder MDB(NewInst->getContext());
 554     dyn_cast<Instruction>(NewInst->stripPointerCasts())
 555         ->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
 556   }
 557
 558   // Move Inst from MergeBB to IndirectCallBB.
 559   Inst->removeFromParent();
 560   IndirectCallBB->getInstList().insert(IndirectCallBB->getFirstInsertionPt(),
 561                                        Inst);
 562
 563   if (InvokeInst *II = dyn_cast<InvokeInst>(Inst)) {
 564     // At this point, the original indirect invoke instruction has the original
 565     // UnwindDest and NormalDest. For the direct invoke instruction, the
 566     // NormalDest points to MergeBB, and MergeBB jumps to the original
 567     // NormalDest. MergeBB might have a new bitcast instruction for the return
 568     // value. The PHIs are with the original NormalDest. Since we now have two
 569     // incoming edges to NormalDest and UnwindDest, we have to do some fixups.
 570     //
 571     // UnwindDest will not use the return value. So pass nullptr here.
 572     fixupPHINodeForUnwind(Inst, II->getUnwindDest(), MergeBB, IndirectCallBB,
 573                           DirectCallBB);
 574     // We don't need to update the operand from NormalDest for DirectCallBB.
 575     // Pass nullptr here.
 576     fixupPHINodeForNormalDest(Inst, II->getNormalDest(), MergeBB,
 577                               IndirectCallBB, NewInst);
 578   }
 579
 580   insertCallRetPHI(Inst, NewInst, DirectCallee);
 581
 582   DEBUG(dbgs() << "\n== Basic Blocks After ==\n");
 583   DEBUG(dbgs() << *BB << *DirectCallBB << *IndirectCallBB << *MergeBB << "\n");
 584
 585   emitOptimizationRemark(
 586       BB->getContext(), "pgo-icall-prom", *BB->getParent(), Inst->getDebugLoc(),
 587       Twine("Promote indirect call to ") + DirectCallee->getName() +
 588           " with count " + Twine(Count) + " out of " + Twine(TotalCount));
 589   return NewInst;
 590 }
 591
 592 // Promote indirect-call to conditional direct-call for one callsite.
 593 uint32_t ICallPromotionFunc::tryToPromote(
 594     Instruction *Inst, const std::vector<PromotionCandidate> &Candidates,
 595     uint64_t &TotalCount) {
 596   uint32_t NumPromoted = 0;
 597
 598   for (auto &C : Candidates) {
 599     uint64_t Count = C.Count;
 600     promoteIndirectCall(Inst, C.TargetFunction, Count, TotalCount, SamplePGO);
 601     assert(TotalCount >= Count);
 602     TotalCount -= Count;
 603     NumOfPGOICallPromotion++;
 604     NumPromoted++;
 605   }
 606   return NumPromoted;
 607 }
 608
 609 // Traverse all the indirect-call callsite and get the value profile
 610 // annotation to perform indirect-call promotion.
 611 bool ICallPromotionFunc::processFunction() {
 612   bool Changed = false;
 613   ICallPromotionAnalysis ICallAnalysis;
 614   for (auto &I : findIndirectCallSites(F)) {
 615     uint32_t NumVals, NumCandidates;
 616     uint64_t TotalCount;
 617     auto ICallProfDataRef = ICallAnalysis.getPromotionCandidatesForInstruction(
 618         I, NumVals, TotalCount, NumCandidates);
 619     if (!NumCandidates)
 620       continue;
 621     auto PromotionCandidates = getPromotionCandidatesForCallSite(
 622         I, ICallProfDataRef, TotalCount, NumCandidates);
 623     uint32_t NumPromoted = tryToPromote(I, PromotionCandidates, TotalCount);
 624     if (NumPromoted == 0)
 625       continue;
 626
 627     Changed = true;
 628     // Adjust the MD.prof metadata. First delete the old one.
 629     I->setMetadata(LLVMContext::MD_prof, nullptr);
 630     // If all promoted, we don't need the MD.prof metadata.
 631     if (TotalCount == 0 || NumPromoted == NumVals)
 632       continue;
 633     // Otherwise we need update with the un-promoted records back.
 634     annotateValueSite(*M, *I, ICallProfDataRef.slice(NumPromoted), TotalCount,
 635                       IPVK_IndirectCallTarget, NumCandidates);
 636   }
 637   return Changed;
 638 }
 639
 640 // A wrapper function that does the actual work.
 641 static bool promoteIndirectCalls(Module &M, bool InLTO, bool SamplePGO) {
 642   if (DisableICP)
 643     return false;
 644   InstrProfSymtab Symtab;
 645   if (Error E = Symtab.create(M, InLTO)) {
 646     std::string SymtabFailure = toString(std::move(E));
 647     DEBUG(dbgs() << "Failed to create symtab: " << SymtabFailure << "\n");
 648     (void)SymtabFailure;
 649     return false;
 650   }
 651   bool Changed = false;
 652   for (auto &F : M) {
 653     if (F.isDeclaration())
 654       continue;
 655     if (F.hasFnAttribute(Attribute::OptimizeNone))
 656       continue;
 657     ICallPromotionFunc ICallPromotion(F, &M, &Symtab, SamplePGO);
 658     bool FuncChanged = ICallPromotion.processFunction();
 659     if (ICPDUMPAFTER && FuncChanged) {
 660       DEBUG(dbgs() << "\n== IR Dump After =="; F.print(dbgs()));
 661       DEBUG(dbgs() << "\n");
 662     }
 663     Changed |= FuncChanged;
 664     if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
 665       DEBUG(dbgs() << " Stop: Cutoff reached.\n");
 666       break;
 667     }
 668   }
 669   return Changed;
 670 }
 671
 672 bool PGOIndirectCallPromotionLegacyPass::runOnModule(Module &M) {
 673   // Command-line option has the priority for InLTO.
 674   return promoteIndirectCalls(M, InLTO | ICPLTOMode,
 675                               SamplePGO | ICPSamplePGOMode);
 676 }
 677
 678 PreservedAnalyses PGOIndirectCallPromotion::run(Module &M,
 679                                                 ModuleAnalysisManager &AM) {
 680   if (!promoteIndirectCalls(M, InLTO | ICPLTOMode,
 681                             SamplePGO | ICPSamplePGOMode))
 682     return PreservedAnalyses::all();
 683
 684   return PreservedAnalyses::none();
 685 }