contrib/llvm/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   enum TargetStatus {
 148     OK,                   // Should be able to promote.
 149     NotAvailableInModule, // Cannot find the target in current module.
 150     ReturnTypeMismatch,   // Return type mismatch b/w target and indirect-call.
 151     NumArgsMismatch,      // Number of arguments does not match.
 152     ArgTypeMismatch       // Type mismatch in the arguments (cannot bitcast).
 153   };
 154
 155   // Test if we can legally promote this direct-call of Target.
 156   TargetStatus isPromotionLegal(Instruction *Inst, uint64_t Target,
 157                                 Function *&F);
 158
 159   // A struct that records the direct target and it's call count.
 160   struct PromotionCandidate {
 161     Function *TargetFunction;
 162     uint64_t Count;
 163     PromotionCandidate(Function *F, uint64_t C) : TargetFunction(F), Count(C) {}
 164   };
 165
 166   // Check if the indirect-call call site should be promoted. Return the number
 167   // of promotions. Inst is the candidate indirect call, ValueDataRef
 168   // contains the array of value profile data for profiled targets,
 169   // TotalCount is the total profiled count of call executions, and
 170   // NumCandidates is the number of candidate entries in ValueDataRef.
 171   std::vector<PromotionCandidate> getPromotionCandidatesForCallSite(
 172       Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
 173       uint64_t TotalCount, uint32_t NumCandidates);
 174
 175   // Main function that transforms Inst (either a indirect-call instruction, or
 176   // an invoke instruction , to a conditional call to F. This is like:
 177   //     if (Inst.CalledValue == F)
 178   //        F(...);
 179   //     else
 180   //        Inst(...);
 181   //     end
 182   // TotalCount is the profile count value that the instruction executes.
 183   // Count is the profile count value that F is the target function.
 184   // These two values are being used to update the branch weight.
 185   void promote(Instruction *Inst, Function *F, uint64_t Count,
 186                uint64_t TotalCount);
 187
 188   // Promote a list of targets for one indirect-call callsite. Return
 189   // the number of promotions.
 190   uint32_t tryToPromote(Instruction *Inst,
 191                         const std::vector<PromotionCandidate> &Candidates,
 192                         uint64_t &TotalCount);
 193
 194   static const char *StatusToString(const TargetStatus S) {
 195     switch (S) {
 196     case OK:
 197       return "OK to promote";
 198     case NotAvailableInModule:
 199       return "Cannot find the target";
 200     case ReturnTypeMismatch:
 201       return "Return type mismatch";
 202     case NumArgsMismatch:
 203       return "The number of arguments mismatch";
 204     case ArgTypeMismatch:
 205       return "Argument Type mismatch";
 206     }
 207     llvm_unreachable("Should not reach here");
 208   }
 209
 210   // Noncopyable
 211   ICallPromotionFunc(const ICallPromotionFunc &other) = delete;
 212   ICallPromotionFunc &operator=(const ICallPromotionFunc &other) = delete;
 213
 214 public:
 215   ICallPromotionFunc(Function &Func, Module *Modu, InstrProfSymtab *Symtab)
 216       : F(Func), M(Modu), Symtab(Symtab) {
 217   }
 218
 219   bool processFunction();
 220 };
 221 } // end anonymous namespace
 222
 223 ICallPromotionFunc::TargetStatus
 224 ICallPromotionFunc::isPromotionLegal(Instruction *Inst, uint64_t Target,
 225                                      Function *&TargetFunction) {
 226   Function *DirectCallee = Symtab->getFunction(Target);
 227   if (DirectCallee == nullptr)
 228     return NotAvailableInModule;
 229   // Check the return type.
 230   Type *CallRetType = Inst->getType();
 231   if (!CallRetType->isVoidTy()) {
 232     Type *FuncRetType = DirectCallee->getReturnType();
 233     if (FuncRetType != CallRetType &&
 234         !CastInst::isBitCastable(FuncRetType, CallRetType))
 235       return ReturnTypeMismatch;
 236   }
 237
 238   // Check if the arguments are compatible with the parameters
 239   FunctionType *DirectCalleeType = DirectCallee->getFunctionType();
 240   unsigned ParamNum = DirectCalleeType->getFunctionNumParams();
 241   CallSite CS(Inst);
 242   unsigned ArgNum = CS.arg_size();
 243
 244   if (ParamNum != ArgNum && !DirectCalleeType->isVarArg())
 245     return NumArgsMismatch;
 246
 247   for (unsigned I = 0; I < ParamNum; ++I) {
 248     Type *PTy = DirectCalleeType->getFunctionParamType(I);
 249     Type *ATy = CS.getArgument(I)->getType();
 250     if (PTy == ATy)
 251       continue;
 252     if (!CastInst::castIsValid(Instruction::BitCast, CS.getArgument(I), PTy))
 253       return ArgTypeMismatch;
 254   }
 255
 256   DEBUG(dbgs() << " #" << NumOfPGOICallPromotion << " Promote the icall to "
 257                << Symtab->getFuncName(Target) << "\n");
 258   TargetFunction = DirectCallee;
 259   return OK;
 260 }
 261
 262 // Indirect-call promotion heuristic. The direct targets are sorted based on
 263 // the count. Stop at the first target that is not promoted.
 264 std::vector<ICallPromotionFunc::PromotionCandidate>
 265 ICallPromotionFunc::getPromotionCandidatesForCallSite(
 266     Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
 267     uint64_t TotalCount, uint32_t NumCandidates) {
 268   std::vector<PromotionCandidate> Ret;
 269
 270   DEBUG(dbgs() << " \nWork on callsite #" << NumOfPGOICallsites << *Inst
 271                << " Num_targets: " << ValueDataRef.size()
 272                << " Num_candidates: " << NumCandidates << "\n");
 273   NumOfPGOICallsites++;
 274   if (ICPCSSkip != 0 && NumOfPGOICallsites <= ICPCSSkip) {
 275     DEBUG(dbgs() << " Skip: User options.\n");
 276     return Ret;
 277   }
 278
 279   for (uint32_t I = 0; I < NumCandidates; I++) {
 280     uint64_t Count = ValueDataRef[I].Count;
 281     assert(Count <= TotalCount);
 282     uint64_t Target = ValueDataRef[I].Value;
 283     DEBUG(dbgs() << " Candidate " << I << " Count=" << Count
 284                  << "  Target_func: " << Target << "\n");
 285
 286     if (ICPInvokeOnly && dyn_cast<CallInst>(Inst)) {
 287       DEBUG(dbgs() << " Not promote: User options.\n");
 288       break;
 289     }
 290     if (ICPCallOnly && dyn_cast<InvokeInst>(Inst)) {
 291       DEBUG(dbgs() << " Not promote: User option.\n");
 292       break;
 293     }
 294     if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
 295       DEBUG(dbgs() << " Not promote: Cutoff reached.\n");
 296       break;
 297     }
 298     Function *TargetFunction = nullptr;
 299     TargetStatus Status = isPromotionLegal(Inst, Target, TargetFunction);
 300     if (Status != OK) {
 301       StringRef TargetFuncName = Symtab->getFuncName(Target);
 302       const char *Reason = StatusToString(Status);
 303       DEBUG(dbgs() << " Not promote: " << Reason << "\n");
 304       emitOptimizationRemarkMissed(
 305           F.getContext(), "pgo-icall-prom", F, Inst->getDebugLoc(),
 306           Twine("Cannot promote indirect call to ") +
 307               (TargetFuncName.empty() ? Twine(Target) : Twine(TargetFuncName)) +
 308               Twine(" with count of ") + Twine(Count) + ": " + Reason);
 309       break;
 310     }
 311     Ret.push_back(PromotionCandidate(TargetFunction, Count));
 312     TotalCount -= Count;
 313   }
 314   return Ret;
 315 }
 316
 317 // Create a diamond structure for If_Then_Else. Also update the profile
 318 // count. Do the fix-up for the invoke instruction.
 319 static void createIfThenElse(Instruction *Inst, Function *DirectCallee,
 320                              uint64_t Count, uint64_t TotalCount,
 321                              BasicBlock **DirectCallBB,
 322                              BasicBlock **IndirectCallBB,
 323                              BasicBlock **MergeBB) {
 324   CallSite CS(Inst);
 325   Value *OrigCallee = CS.getCalledValue();
 326
 327   IRBuilder<> BBBuilder(Inst);
 328   LLVMContext &Ctx = Inst->getContext();
 329   Value *BCI1 =
 330       BBBuilder.CreateBitCast(OrigCallee, Type::getInt8PtrTy(Ctx), "");
 331   Value *BCI2 =
 332       BBBuilder.CreateBitCast(DirectCallee, Type::getInt8PtrTy(Ctx), "");
 333   Value *PtrCmp = BBBuilder.CreateICmpEQ(BCI1, BCI2, "");
 334
 335   uint64_t ElseCount = TotalCount - Count;
 336   uint64_t MaxCount = (Count >= ElseCount ? Count : ElseCount);
 337   uint64_t Scale = calculateCountScale(MaxCount);
 338   MDBuilder MDB(Inst->getContext());
 339   MDNode *BranchWeights = MDB.createBranchWeights(
 340       scaleBranchCount(Count, Scale), scaleBranchCount(ElseCount, Scale));
 341   TerminatorInst *ThenTerm, *ElseTerm;
 342   SplitBlockAndInsertIfThenElse(PtrCmp, Inst, &ThenTerm, &ElseTerm,
 343                                 BranchWeights);
 344   *DirectCallBB = ThenTerm->getParent();
 345   (*DirectCallBB)->setName("if.true.direct_targ");
 346   *IndirectCallBB = ElseTerm->getParent();
 347   (*IndirectCallBB)->setName("if.false.orig_indirect");
 348   *MergeBB = Inst->getParent();
 349   (*MergeBB)->setName("if.end.icp");
 350
 351   // Special handing of Invoke instructions.
 352   InvokeInst *II = dyn_cast<InvokeInst>(Inst);
 353   if (!II)
 354     return;
 355
 356   // We don't need branch instructions for invoke.
 357   ThenTerm->eraseFromParent();
 358   ElseTerm->eraseFromParent();
 359
 360   // Add jump from Merge BB to the NormalDest. This is needed for the newly
 361   // created direct invoke stmt -- as its NormalDst will be fixed up to MergeBB.
 362   BranchInst::Create(II->getNormalDest(), *MergeBB);
 363 }
 364
 365 // Find the PHI in BB that have the CallResult as the operand.
 366 static bool getCallRetPHINode(BasicBlock *BB, Instruction *Inst) {
 367   BasicBlock *From = Inst->getParent();
 368   for (auto &I : *BB) {
 369     PHINode *PHI = dyn_cast<PHINode>(&I);
 370     if (!PHI)
 371       continue;
 372     int IX = PHI->getBasicBlockIndex(From);
 373     if (IX == -1)
 374       continue;
 375     Value *V = PHI->getIncomingValue(IX);
 376     if (dyn_cast<Instruction>(V) == Inst)
 377       return true;
 378   }
 379   return false;
 380 }
 381
 382 // This method fixes up PHI nodes in BB where BB is the UnwindDest 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, OrigBB is no longer the predecessor block of BB.
 386 // Instead two new predecessors are added: IndirectCallBB and DirectCallBB,
 387 // so the PHI node's incoming BBs need to be fixed up accordingly.
 388 static void fixupPHINodeForUnwind(Instruction *Inst, BasicBlock *BB,
 389                                   BasicBlock *OrigBB,
 390                                   BasicBlock *IndirectCallBB,
 391                                   BasicBlock *DirectCallBB) {
 392   for (auto &I : *BB) {
 393     PHINode *PHI = dyn_cast<PHINode>(&I);
 394     if (!PHI)
 395       continue;
 396     int IX = PHI->getBasicBlockIndex(OrigBB);
 397     if (IX == -1)
 398       continue;
 399     Value *V = PHI->getIncomingValue(IX);
 400     PHI->addIncoming(V, IndirectCallBB);
 401     PHI->setIncomingBlock(IX, DirectCallBB);
 402   }
 403 }
 404
 405 // This method fixes up PHI nodes in BB where BB is the NormalDest of an
 406 // invoke instruction. In BB, there may be PHIs with incoming block being
 407 // OrigBB (the MergeBB after if-then-else splitting). After moving the invoke
 408 // instructions to its own BB, a new incoming edge will be added to the original
 409 // NormalDstBB from the IndirectCallBB.
 410 static void fixupPHINodeForNormalDest(Instruction *Inst, BasicBlock *BB,
 411                                       BasicBlock *OrigBB,
 412                                       BasicBlock *IndirectCallBB,
 413                                       Instruction *NewInst) {
 414   for (auto &I : *BB) {
 415     PHINode *PHI = dyn_cast<PHINode>(&I);
 416     if (!PHI)
 417       continue;
 418     int IX = PHI->getBasicBlockIndex(OrigBB);
 419     if (IX == -1)
 420       continue;
 421     Value *V = PHI->getIncomingValue(IX);
 422     if (dyn_cast<Instruction>(V) == Inst) {
 423       PHI->setIncomingBlock(IX, IndirectCallBB);
 424       PHI->addIncoming(NewInst, OrigBB);
 425       continue;
 426     }
 427     PHI->addIncoming(V, IndirectCallBB);
 428   }
 429 }
 430
 431 // Add a bitcast instruction to the direct-call return value if needed.
 432 static Instruction *insertCallRetCast(const Instruction *Inst,
 433                                       Instruction *DirectCallInst,
 434                                       Function *DirectCallee) {
 435   if (Inst->getType()->isVoidTy())
 436     return DirectCallInst;
 437
 438   Type *CallRetType = Inst->getType();
 439   Type *FuncRetType = DirectCallee->getReturnType();
 440   if (FuncRetType == CallRetType)
 441     return DirectCallInst;
 442
 443   BasicBlock *InsertionBB;
 444   if (CallInst *CI = dyn_cast<CallInst>(DirectCallInst))
 445     InsertionBB = CI->getParent();
 446   else
 447     InsertionBB = (dyn_cast<InvokeInst>(DirectCallInst))->getNormalDest();
 448
 449   return (new BitCastInst(DirectCallInst, CallRetType, "",
 450                           InsertionBB->getTerminator()));
 451 }
 452
 453 // Create a DirectCall instruction in the DirectCallBB.
 454 // Parameter Inst is the indirect-call (invoke) instruction.
 455 // DirectCallee is the decl of the direct-call (invoke) target.
 456 // DirecallBB is the BB that the direct-call (invoke) instruction is inserted.
 457 // MergeBB is the bottom BB of the if-then-else-diamond after the
 458 // transformation. For invoke instruction, the edges from DirectCallBB and
 459 // IndirectCallBB to MergeBB are removed before this call (during
 460 // createIfThenElse).
 461 static Instruction *createDirectCallInst(const Instruction *Inst,
 462                                          Function *DirectCallee,
 463                                          BasicBlock *DirectCallBB,
 464                                          BasicBlock *MergeBB) {
 465   Instruction *NewInst = Inst->clone();
 466   if (CallInst *CI = dyn_cast<CallInst>(NewInst)) {
 467     CI->setCalledFunction(DirectCallee);
 468     CI->mutateFunctionType(DirectCallee->getFunctionType());
 469   } else {
 470     // Must be an invoke instruction. Direct invoke's normal destination is
 471     // fixed up to MergeBB. MergeBB is the place where return cast is inserted.
 472     // Also since IndirectCallBB does not have an edge to MergeBB, there is no
 473     // need to insert new PHIs into MergeBB.
 474     InvokeInst *II = dyn_cast<InvokeInst>(NewInst);
 475     assert(II);
 476     II->setCalledFunction(DirectCallee);
 477     II->mutateFunctionType(DirectCallee->getFunctionType());
 478     II->setNormalDest(MergeBB);
 479   }
 480
 481   DirectCallBB->getInstList().insert(DirectCallBB->getFirstInsertionPt(),
 482                                      NewInst);
 483
 484   // Clear the value profile data.
 485   NewInst->setMetadata(LLVMContext::MD_prof, nullptr);
 486   CallSite NewCS(NewInst);
 487   FunctionType *DirectCalleeType = DirectCallee->getFunctionType();
 488   unsigned ParamNum = DirectCalleeType->getFunctionNumParams();
 489   for (unsigned I = 0; I < ParamNum; ++I) {
 490     Type *ATy = NewCS.getArgument(I)->getType();
 491     Type *PTy = DirectCalleeType->getParamType(I);
 492     if (ATy != PTy) {
 493       BitCastInst *BI = new BitCastInst(NewCS.getArgument(I), PTy, "", NewInst);
 494       NewCS.setArgument(I, BI);
 495     }
 496   }
 497
 498   return insertCallRetCast(Inst, NewInst, DirectCallee);
 499 }
 500
 501 // Create a PHI to unify the return values of calls.
 502 static void insertCallRetPHI(Instruction *Inst, Instruction *CallResult,
 503                              Function *DirectCallee) {
 504   if (Inst->getType()->isVoidTy())
 505     return;
 506
 507   BasicBlock *RetValBB = CallResult->getParent();
 508
 509   BasicBlock *PHIBB;
 510   if (InvokeInst *II = dyn_cast<InvokeInst>(CallResult))
 511     RetValBB = II->getNormalDest();
 512
 513   PHIBB = RetValBB->getSingleSuccessor();
 514   if (getCallRetPHINode(PHIBB, Inst))
 515     return;
 516
 517   PHINode *CallRetPHI = PHINode::Create(Inst->getType(), 0);
 518   PHIBB->getInstList().push_front(CallRetPHI);
 519   Inst->replaceAllUsesWith(CallRetPHI);
 520   CallRetPHI->addIncoming(Inst, Inst->getParent());
 521   CallRetPHI->addIncoming(CallResult, RetValBB);
 522 }
 523
 524 // This function does the actual indirect-call promotion transformation:
 525 // For an indirect-call like:
 526 //     Ret = (*Foo)(Args);
 527 // It transforms to:
 528 //     if (Foo == DirectCallee)
 529 //        Ret1 = DirectCallee(Args);
 530 //     else
 531 //        Ret2 = (*Foo)(Args);
 532 //     Ret = phi(Ret1, Ret2);
 533 // It adds type casts for the args do not match the parameters and the return
 534 // value. Branch weights metadata also updated.
 535 void ICallPromotionFunc::promote(Instruction *Inst, Function *DirectCallee,
 536                                  uint64_t Count, uint64_t TotalCount) {
 537   assert(DirectCallee != nullptr);
 538   BasicBlock *BB = Inst->getParent();
 539   // Just to suppress the non-debug build warning.
 540   (void)BB;
 541   DEBUG(dbgs() << "\n\n== Basic Block Before ==\n");
 542   DEBUG(dbgs() << *BB << "\n");
 543
 544   BasicBlock *DirectCallBB, *IndirectCallBB, *MergeBB;
 545   createIfThenElse(Inst, DirectCallee, Count, TotalCount, &DirectCallBB,
 546                    &IndirectCallBB, &MergeBB);
 547
 548   Instruction *NewInst =
 549       createDirectCallInst(Inst, DirectCallee, DirectCallBB, MergeBB);
 550
 551   // Move Inst from MergeBB to IndirectCallBB.
 552   Inst->removeFromParent();
 553   IndirectCallBB->getInstList().insert(IndirectCallBB->getFirstInsertionPt(),
 554                                        Inst);
 555
 556   if (InvokeInst *II = dyn_cast<InvokeInst>(Inst)) {
 557     // At this point, the original indirect invoke instruction has the original
 558     // UnwindDest and NormalDest. For the direct invoke instruction, the
 559     // NormalDest points to MergeBB, and MergeBB jumps to the original
 560     // NormalDest. MergeBB might have a new bitcast instruction for the return
 561     // value. The PHIs are with the original NormalDest. Since we now have two
 562     // incoming edges to NormalDest and UnwindDest, we have to do some fixups.
 563     //
 564     // UnwindDest will not use the return value. So pass nullptr here.
 565     fixupPHINodeForUnwind(Inst, II->getUnwindDest(), MergeBB, IndirectCallBB,
 566                           DirectCallBB);
 567     // We don't need to update the operand from NormalDest for DirectCallBB.
 568     // Pass nullptr here.
 569     fixupPHINodeForNormalDest(Inst, II->getNormalDest(), MergeBB,
 570                               IndirectCallBB, NewInst);
 571   }
 572
 573   insertCallRetPHI(Inst, NewInst, DirectCallee);
 574
 575   DEBUG(dbgs() << "\n== Basic Blocks After ==\n");
 576   DEBUG(dbgs() << *BB << *DirectCallBB << *IndirectCallBB << *MergeBB << "\n");
 577
 578   emitOptimizationRemark(
 579       F.getContext(), "pgo-icall-prom", F, Inst->getDebugLoc(),
 580       Twine("Promote indirect call to ") + DirectCallee->getName() +
 581           " with count " + Twine(Count) + " out of " + Twine(TotalCount));
 582 }
 583
 584 // Promote indirect-call to conditional direct-call for one callsite.
 585 uint32_t ICallPromotionFunc::tryToPromote(
 586     Instruction *Inst, const std::vector<PromotionCandidate> &Candidates,
 587     uint64_t &TotalCount) {
 588   uint32_t NumPromoted = 0;
 589
 590   for (auto &C : Candidates) {
 591     uint64_t Count = C.Count;
 592     promote(Inst, C.TargetFunction, Count, TotalCount);
 593     assert(TotalCount >= Count);
 594     TotalCount -= Count;
 595     NumOfPGOICallPromotion++;
 596     NumPromoted++;
 597   }
 598   return NumPromoted;
 599 }
 600
 601 // Traverse all the indirect-call callsite and get the value profile
 602 // annotation to perform indirect-call promotion.
 603 bool ICallPromotionFunc::processFunction() {
 604   bool Changed = false;
 605   ICallPromotionAnalysis ICallAnalysis;
 606   for (auto &I : findIndirectCallSites(F)) {
 607     uint32_t NumVals, NumCandidates;
 608     uint64_t TotalCount;
 609     auto ICallProfDataRef = ICallAnalysis.getPromotionCandidatesForInstruction(
 610         I, NumVals, TotalCount, NumCandidates);
 611     if (!NumCandidates)
 612       continue;
 613     auto PromotionCandidates = getPromotionCandidatesForCallSite(
 614         I, ICallProfDataRef, TotalCount, NumCandidates);
 615     uint32_t NumPromoted = tryToPromote(I, PromotionCandidates, TotalCount);
 616     if (NumPromoted == 0)
 617       continue;
 618
 619     Changed = true;
 620     // Adjust the MD.prof metadata. First delete the old one.
 621     I->setMetadata(LLVMContext::MD_prof, nullptr);
 622     // If all promoted, we don't need the MD.prof metadata.
 623     if (TotalCount == 0 || NumPromoted == NumVals)
 624       continue;
 625     // Otherwise we need update with the un-promoted records back.
 626     annotateValueSite(*M, *I, ICallProfDataRef.slice(NumPromoted), TotalCount,
 627                       IPVK_IndirectCallTarget, NumCandidates);
 628   }
 629   return Changed;
 630 }
 631
 632 // A wrapper function that does the actual work.
 633 static bool promoteIndirectCalls(Module &M, bool InLTO) {
 634   if (DisableICP)
 635     return false;
 636   InstrProfSymtab Symtab;
 637   Symtab.create(M, InLTO);
 638   bool Changed = false;
 639   for (auto &F : M) {
 640     if (F.isDeclaration())
 641       continue;
 642     if (F.hasFnAttribute(Attribute::OptimizeNone))
 643       continue;
 644     ICallPromotionFunc ICallPromotion(F, &M, &Symtab);
 645     bool FuncChanged = ICallPromotion.processFunction();
 646     if (ICPDUMPAFTER && FuncChanged) {
 647       DEBUG(dbgs() << "\n== IR Dump After =="; F.print(dbgs()));
 648       DEBUG(dbgs() << "\n");
 649     }
 650     Changed |= FuncChanged;
 651     if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
 652       DEBUG(dbgs() << " Stop: Cutoff reached.\n");
 653       break;
 654     }
 655   }
 656   return Changed;
 657 }
 658
 659 bool PGOIndirectCallPromotionLegacyPass::runOnModule(Module &M) {
 660   // Command-line option has the priority for InLTO.
 661   return promoteIndirectCalls(M, InLTO | ICPLTOMode);
 662 }
 663
 664 PreservedAnalyses PGOIndirectCallPromotion::run(Module &M, ModuleAnalysisManager &AM) {
 665   if (!promoteIndirectCalls(M, InLTO | ICPLTOMode))
 666     return PreservedAnalyses::all();
 667
 668   return PreservedAnalyses::none();
 669 }