lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

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