[ICP] Expose unconditional call promotion interface

[mssimpso]

Summary

This patch modifies the common indirect call promotion utilities by by exposing and using an unconditional call promotion interface. These changes are meant to accommodate the planned use case in D39869. The unconditional promotion interface (i.e., call promotion without creating an if-then-else) can be used if it's known that an indirect call has only one possible callee. The existing conditional promotion interface uses this unconditional interface to promote an indirect call after it has been versioned and placed within the "then" block.

A consequence of unconditional promotion is that the fix-up operations for phi nodes in the normal destination of invoke instructions are changed. This is necessary because the existing implementation assumed that an invoke had been versioned, creating a "merge" block where a return value bitcast could be placed. In the new implementation, the edge between a promoted invoke's parent block and its normal destination is split if needed to add a bitcast for the return value. If the invoke is also versioned, the phi node merging the return value of the promoted and original invoke instructions is placed in the "merge" block.

[mssimpso]

Rebased. Thanks!

[mssimpso]

Ping.

[davidxl]

include/llvm/Transforms/Utils/CallPromotionUtils.h

49

Can you remove this method in this patch? It is not used anywhere

lib/Transforms/IPO/SampleProfile.cpp

829–830

what is this change for?

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

315–316

What is this change for?

lib/Transforms/Utils/CallPromotionUtils.cpp

37–38

Can you explain this change (and other related interface changes) perhaps with a tiny example -- there are lots of words in the description but not as helpful as an example.

282

Remove this one from this patch.

[mssimpso]

Addressed David's comments. Thanks for the feedback!

• Moved demoteCall to D39869.
• Added comments with example code snippets to the basic transformations.

[mssimpso]

include/llvm/Transforms/Utils/CallPromotionUtils.h

49

Sure, that make sense. I'll add this part to D39869.

lib/Transforms/IPO/SampleProfile.cpp

829–830

The conditional promotion interface now modifies the given call site to be direct and returns the newly created indirect call site. Previously the given call site was left unmodified, and a newly created direct call site was returned. This change makes the conditional and unconditional promotion interfaces consistent with each other (the given call site is changed to be direct), and also works well with D39869.

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

315–316

Same as above. "Inst" is now made to be direct, and "NewInst" is the new instruction in the "else" block.

lib/Transforms/Utils/CallPromotionUtils.cpp

37–38

Sure, I've added code snippets to all of the basic transformations with both call and invoke examples.

Basically, the code here is changing because the control-flow we create for conditional promotion is slightly different than it was previously. The reason it's different is described below. Previously, we generated code like:

orig_bb:
  %cond = icmp eq i32 ()* %ptr, @func
  br i1 %cond, %then_bb, %else_bb

then_bb:
  %t0 = invoke i32 @func() to label %merge_bb unwind label %unwind_dst

else_bb:
  %t1 = invoke i32 %ptr() to label %normal_dst unwind label %unwind_dst

merge_bb:
  br %normal_dst

normal_dst:
  %t2 = phi i32 [ %t0, %merge_bb ], [ %t1, %else_bb ]

Whereas now, we generate code like:

orig_bb:
  %cond = icmp eq i32 ()* %ptr, @func
  br i1 %cond, %then_bb, %else_bb

then_bb:
  %t0 = invoke i32 @func() to label %merge_bb unwind label %unwind_dst

else_bb:
  %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst

merge_bb:
  %t2 = phi i32 [ %t0, %then_bb ], [ %t1, %else_bb ]
  br %normal_dst

The difference is that now both invokes have "merge_bb" as their normal destination. Previously, only the normal destination of the promoted invoke was set to "merge_bb", where a return value bitcast was added if needed, and the phi node for merging the return values was created/modified in the original normal destination. After this patch, the normal destination of both invokes is set to "merge_bb", where the merge phi node is added, and if a return value bitcast is required, the edge between "then_bb" and "merge_bb" is split and the bitcast is placed there.

Previously, there was no way to perform a stand-alone unconditional promotion because it was assumed that an if-then-else structure would always be created. We can do that now with this patch, and the refactoring allows greater code reuse between the conditional and unconditional cases. To perform conditional promotion, we just need to version the original invoke (which creates the if-then-else structure, adds the merge phi node, and fixes up phi nodes in the normal and unwind destinations), and then unconditionally promote one of them (which also adds the return value bitcast if necessary). I hope that helps!

282

This will be added to D39869

[davidxl]

lib/Transforms/IPO/SampleProfile.cpp

829–830

I don't see pgo::promoteIndirectCall interface documentation change in this patch (in the header).

Besides, I am not sure the proposed interface change is better -- it is more natural to return the promoted 'direct call' instruction and modify I (reference) to be the indirect call, instead of requiring the client to do DI = I before the call.

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

315–316

It is very confusing -- this is the reason I don't like the interface change. A reader will naturally think NewInst is the newly created direct call (the implementation may still choose to modify the existing instruction and return it).

lib/Transforms/Utils/CallPromotionUtils.cpp

123

Add a test case for the splitBB case for bitcast?

[mssimpso]

Thanks again for the comments, David. I'll update the patch shortly.

lib/Transforms/IPO/SampleProfile.cpp

829–830

Sure, I'm fine restoring the interface if you'd prefer. The client can always swap the pointers after the call if needed.

lib/Transforms/Utils/CallPromotionUtils.cpp

123

This case is reflected in the change to test/Transforms/PGOProfile/icp_covariant_invoke_return.ll. After versioning the invoke, the if.true.direct_targ.if.end.icp_crit_edge block, which contains the bitcast, is added between the invoke's parent block (the direct call bock), and it's normal destination (the merge block).

[mssimpso]

Addressed David's comments. Thanks again!

• Restored the existing conditional call promotion interface.

[davidxl]

there are two small suggestions. otherwise LGTM

include/llvm/Transforms/Utils/CallPromotionUtils.h

38

Perhaps return the callInstruction and perhaps a third optional pointer parameter to store the bitcast created.

lib/Transforms/Utils/CallPromotionUtils.cpp

313

let NewInst = promoteCall(...) instead of implicitly assume the same instruction gets converted.

[mssimpso]

Thanks David! I'll make those changes before committing.

include/llvm/Transforms/Utils/CallPromotionUtils.h

 /// This function ensures that the number and type of the call site's arguments
 /// and return value match those of the given function. If the types do not
 /// match exactly, they must at least be bitcast compatible. If \p FailureReason
 /// is non-null and the indirect call cannot be promoted, the failure reason
 /// will be stored in it.
 bool isLegalToPromote(CallSite CS, Function *Callee,
                       const char **FailureReason = nullptr);
 
+/// Promote the given indirect call site to unconditionally call \p Callee.
+///
+/// If the function type of the call site doesn't match that of the callee,
+/// bitcast instructions are inserted where appropriate. If \p Casts is
+/// non-null, these bitcasts are collected in the provided container.
+void promoteCall(CallSite CS, Function *Callee,
+                 SmallVectorImpl<CastInst *> *Casts = nullptr);
+
+/// Demote the given direct call site to call \p CalledValue.
+///
+/// This function is meant to be used in conjunction with \p promoteCall. As
+/// such, any bitcast instructions contained in \p Casts, which were created by
+/// \p promoteCall, will be erased. Together, these functions can be used to
+/// temporarily promote a call to facilitate analyzing the program as if the
+/// call were direct.
+void demoteCall(CallSite CS, Value *CalledValue, ArrayRef<CastInst *> Casts);
+
 /// Promote the given indirect call site to conditionally call \p Callee.
 ///
 /// This function creates an if-then-else structure at the location of the call
 /// site. The original call site is promoted and moved into the "then" block. A
 /// clone of the indirect call site is placed in the "else" block and returned.
 /// If \p BranchWeights is non-null, it will be used to set !prof metadata on
 /// the new conditional branch.
 Instruction *promoteCallWithIfThenElse(CallSite CS, Function *Callee,
                                        MDNode *BranchWeights = nullptr);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_CALLPROMOTIONUTILS_H

lib/Transforms/IPO/SampleProfile.cpp

for (auto I : CIS) {
 
           const char *Reason = "Callee function not available";
           auto R = SymbolMap.find(CalleeFunctionName);
           if (R != SymbolMap.end() && R->getValue() &&
               !R->getValue()->isDeclaration() &&
               R->getValue()->getSubprogram() &&
               isLegalToPromote(CallSite(I), R->getValue(), &Reason)) {
             uint64_t C = FS->getEntrySamples();
-            Instruction *DI =
-                pgo::promoteIndirectCall(I, R->getValue(), C, Sum, false, ORE);
+            Instruction *DI = I;
+            I = pgo::promoteIndirectCall(I, R->getValue(), C, Sum, false, ORE);
             Sum -= C;
             PromotedInsns.insert(I);
             // If profile mismatches, we should not attempt to inline DI.
             if ((isa<CallInst>(DI) || isa<InvokeInst>(DI)) &&
                 inlineCallInstruction(DI))
               LocalChanged = true;
           } else {
             DEBUG(dbgs()

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

private:
   // TotalCount is the total profiled count of call executions, and
   // NumCandidates is the number of candidate entries in ValueDataRef.
   std::vector<PromotionCandidate> getPromotionCandidatesForCallSite(
       Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
       uint64_t TotalCount, uint32_t NumCandidates);
 
   // Promote a list of targets for one indirect-call callsite. Return
   // the number of promotions.
-  uint32_t tryToPromote(Instruction *Inst,
+  uint32_t tryToPromote(Instruction *&Inst,
                         const std::vector<PromotionCandidate> &Candidates,
                         uint64_t &TotalCount);
 
 public:
   ICallPromotionFunc(Function &Func, Module *Modu, InstrProfSymtab *Symtab,
                      bool SamplePGO, OptimizationRemarkEmitter &ORE)
       : F(Func), M(Modu), Symtab(Symtab), SamplePGO(SamplePGO), ORE(ORE) {}
   ICallPromotionFunc(const ICallPromotionFunc &) = delete;
MDNode *BranchWeights = MDB.createBranchWeights(
       scaleBranchCount(Count, Scale), scaleBranchCount(ElseCount, Scale));
 
   Instruction *NewInst =
       promoteCallWithIfThenElse(CallSite(Inst), DirectCallee, BranchWeights);
 
   if (AttachProfToDirectCall) {
     SmallVector<uint32_t, 1> Weights;
     Weights.push_back(Count);
-    MDBuilder MDB(NewInst->getContext());
-    NewInst->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
+    MDBuilder MDB(Inst->getContext());
+    Inst->setMetadata(LLVMContext::MD_prof, MDB.createBranchWeights(Weights));
   }
 
   using namespace ore;
 
   if (ORE)
     ORE->emit([&]() {
       return OptimizationRemark(DEBUG_TYPE, "Promoted", Inst)
              << "Promote indirect call to " << NV("DirectCallee", DirectCallee)
              << " with count " << NV("Count", Count) << " out of "
              << NV("TotalCount", TotalCount);
     });
   return NewInst;
 }
 
 // Promote indirect-call to conditional direct-call for one callsite.
 uint32_t ICallPromotionFunc::tryToPromote(
-    Instruction *Inst, const std::vector<PromotionCandidate> &Candidates,
+    Instruction *&Inst, const std::vector<PromotionCandidate> &Candidates,
     uint64_t &TotalCount) {
   uint32_t NumPromoted = 0;
 
   for (auto &C : Candidates) {
     uint64_t Count = C.Count;
-    pgo::promoteIndirectCall(Inst, C.TargetFunction, Count, TotalCount,
+    Inst = pgo::promoteIndirectCall(Inst, C.TargetFunction, Count, TotalCount,
                                     SamplePGO, &ORE);
     assert(TotalCount >= Count);
     TotalCount -= Count;
     NumOfPGOICallPromotion++;
     NumPromoted++;
   }
   return NumPromoted;
 }
 

lib/Transforms/Utils/CallPromotionUtils.cpp

 
 using namespace llvm;
 
 #define DEBUG_TYPE "call-promotion-utils"
 
 /// Fix-up phi nodes in an invoke instruction's normal destination.
 ///
 /// After versioning an invoke instruction, values coming from the original
-/// block will now either be coming from the original block or the "else" block.
+/// block will now be coming from the "merge" block.
 static void fixupPHINodeForNormalDest(InvokeInst *Invoke, BasicBlock *OrigBlock,
-                                      BasicBlock *ElseBlock,
-                                      Instruction *NewInst) {
+                                      BasicBlock *MergeBlock) {
   for (auto &I : *Invoke->getNormalDest()) {
     auto *Phi = dyn_cast<PHINode>(&I);
     if (!Phi)
       break;
     int Idx = Phi->getBasicBlockIndex(OrigBlock);
     if (Idx == -1)
       continue;
-    Phi->setIncomingBlock(Idx, ElseBlock);
-    Phi->addIncoming(NewInst, OrigBlock);
+    Phi->setIncomingBlock(Idx, MergeBlock);
   }
 }
 
 /// Fix-up phi nodes in an invoke instruction's unwind destination.
 ///
 /// After versioning an invoke instruction, values coming from the original
 /// block will now be coming from either the "then" block or the "else" block.
 static void fixupPHINodeForUnwindDest(InvokeInst *Invoke, BasicBlock *OrigBlock,
                                       BasicBlock *ThenBlock,
                                       BasicBlock *ElseBlock) {
   for (auto &I : *Invoke->getUnwindDest()) {
     auto *Phi = dyn_cast<PHINode>(&I);
     if (!Phi)
       break;
     int Idx = Phi->getBasicBlockIndex(OrigBlock);
     if (Idx == -1)
       continue;
     auto *V = Phi->getIncomingValue(Idx);
     Phi->setIncomingBlock(Idx, ThenBlock);
     Phi->addIncoming(V, ElseBlock);
   }
 }
 
-/// Get the phi node having the returned value of a call or invoke instruction
-/// as it's operand.
-static bool getRetPhiNode(Instruction *Inst, BasicBlock *Block) {
-  BasicBlock *FromBlock = Inst->getParent();
-  for (auto &I : *Block) {
-    PHINode *PHI = dyn_cast<PHINode>(&I);
-    if (!PHI)
-      break;
-    int Idx = PHI->getBasicBlockIndex(FromBlock);
-    if (Idx == -1)
-      continue;
-    auto *V = PHI->getIncomingValue(Idx);
-    if (V == Inst)
-      return true;
-  }
-  return false;
-}
-
 /// Create a phi node for the returned value of a call or invoke instruction.
 ///
 /// After versioning a call or invoke instruction that returns a value, we have
 /// to merge the value of the original and new instructions. We do this by
 /// creating a phi node and replacing uses of the original instruction with this
 /// phi node.
-static void createRetPHINode(Instruction *OrigInst, Instruction *NewInst) {
+static void createRetPHINode(Instruction *OrigInst, Instruction *NewInst,
+                             BasicBlock *MergeBlock, IRBuilder<> &Builder) {
 
   if (OrigInst->getType()->isVoidTy() || OrigInst->use_empty())
     return;
 
-  BasicBlock *RetValBB = NewInst->getParent();
-  if (auto *Invoke = dyn_cast<InvokeInst>(NewInst))
-    RetValBB = Invoke->getNormalDest();
-  BasicBlock *PhiBB = RetValBB->getSingleSuccessor();
-
-  if (getRetPhiNode(OrigInst, PhiBB))
-    return;
-
-  IRBuilder<> Builder(&PhiBB->front());
+  Builder.SetInsertPoint(&MergeBlock->front());
   PHINode *Phi = Builder.CreatePHI(OrigInst->getType(), 0);
   SmallVector<User *, 16> UsersToUpdate;
   for (User *U : OrigInst->users())
     UsersToUpdate.push_back(U);
   for (User *U : UsersToUpdate)
     U->replaceUsesOfWith(OrigInst, Phi);
+  Phi->addIncoming(NewInst, NewInst->getParent());
   Phi->addIncoming(OrigInst, OrigInst->getParent());
-  Phi->addIncoming(NewInst, RetValBB);
 }
 
 /// Cast a call or invoke instruction to the given type.
 ///
 /// When promoting a call site, the return type of the call site might not match
 /// that of the callee. If this is the case, we have to cast the returned value
 /// to the correct type. The location of the cast depends of if we have a call
 /// or invoke instruction.
-Instruction *createRetBitCast(CallSite CS, Type *RetTy) {
+static void createRetBitCast(CallSite CS, Type *RetTy,
+                             SmallVectorImpl<CastInst *> *Casts) {
 
   // Save the users of the calling instruction. These uses will be changed to
   // use the bitcast after we create it.
   SmallVector<User *, 16> UsersToUpdate;
   for (User *U : CS.getInstruction()->users())
     UsersToUpdate.push_back(U);
 
   // Determine an appropriate location to create the bitcast for the return
   // value. The location depends on if we have a call or invoke instruction.
   Instruction *InsertBefore = nullptr;
   if (auto *Invoke = dyn_cast<InvokeInst>(CS.getInstruction()))
-    InsertBefore = &*Invoke->getNormalDest()->getFirstInsertionPt();
+    InsertBefore =
+        &SplitEdge(Invoke->getParent(), Invoke->getNormalDest())->front();
   else
     InsertBefore = &*std::next(CS.getInstruction()->getIterator());
 
   // Bitcast the return value to the correct type.
   auto *Cast = CastInst::Create(Instruction::BitCast, CS.getInstruction(),
                                 RetTy, "", InsertBefore);
+  if (Casts)
+    Casts->push_back(Cast);
 
   // Replace all the original uses of the calling instruction with the bitcast.
   for (User *U : UsersToUpdate)
     U->replaceUsesOfWith(CS.getInstruction(), Cast);
-
-  return Cast;
 }
 
 /// Predicate and clone the given call site.
 ///
 /// This function creates an if-then-else structure at the location of the call
 /// site. The "if" condition compares the call site's called value to the given
 /// callee. The original call site is moved into the "then" block, and a clone
 /// of the call site is placed in the "else" block. The cloned instruction is
 /// returned. If the call site happens to be an invoke instruction, further work
 /// is done to fix phi nodes in the invoke's normal and unwind destinations.
 static Instruction *versionCallSite(CallSite CS, Value *Callee,
                                     MDNode *BranchWeights) {
 
   IRBuilder<> Builder(CS.getInstruction());
   Instruction *OrigInst = CS.getInstruction();
+  BasicBlock *OrigBlock = OrigInst->getParent();
 
   // Create the compare. The called value and callee must have the same type to
   // be compared.
-  auto *LHS =
-      Builder.CreateBitCast(CS.getCalledValue(), Builder.getInt8PtrTy());
-  auto *RHS = Builder.CreateBitCast(Callee, Builder.getInt8PtrTy());
-  auto *Cond = Builder.CreateICmpEQ(LHS, RHS);
+  if (CS.getCalledValue()->getType() != Callee->getType())
+    Callee = Builder.CreateBitCast(Callee, CS.getCalledValue()->getType());
+  auto *Cond = Builder.CreateICmpEQ(CS.getCalledValue(), Callee);
 
   // Create an if-then-else structure. The original instruction is moved into
-  // the "else" block, and a clone of the original instruction is placed in the
-  // "then" block.
+  // the "then" block, and a clone of the original instruction is placed in the
+  // "else" block.
   TerminatorInst *ThenTerm = nullptr;
   TerminatorInst *ElseTerm = nullptr;
   SplitBlockAndInsertIfThenElse(Cond, CS.getInstruction(), &ThenTerm, &ElseTerm,
                                 BranchWeights);
   BasicBlock *ThenBlock = ThenTerm->getParent();
   BasicBlock *ElseBlock = ElseTerm->getParent();
   BasicBlock *MergeBlock = OrigInst->getParent();
 
   ThenBlock->setName("if.true.direct_targ");
   ElseBlock->setName("if.false.orig_indirect");
   MergeBlock->setName("if.end.icp");
 
   Instruction *NewInst = OrigInst->clone();
-  OrigInst->moveBefore(ElseTerm);
-  NewInst->insertBefore(ThenTerm);
+  OrigInst->moveBefore(ThenTerm);
+  NewInst->insertBefore(ElseTerm);
 
   // If the original call site is an invoke instruction, we have extra work to
   // do since invoke instructions are terminating. We have to fix-up phi nodes
   // in the invoke's normal and unwind destinations.
   if (auto *OrigInvoke = dyn_cast<InvokeInst>(OrigInst)) {
     auto *NewInvoke = cast<InvokeInst>(NewInst);
 
     // Invoke instructions are terminating, so we don't need the terminator
     // instructions that were just created.
     ThenTerm->eraseFromParent();
     ElseTerm->eraseFromParent();
 
     // Branch from the "merge" block to the original normal destination.
     Builder.SetInsertPoint(MergeBlock);
     Builder.CreateBr(OrigInvoke->getNormalDest());
 
     // Fix-up phi nodes in the original invoke's normal and unwind destinations.
-    fixupPHINodeForNormalDest(OrigInvoke, MergeBlock, ElseBlock, NewInst);
-    fixupPHINodeForUnwindDest(OrigInvoke, MergeBlock, ThenBlock, ElseBlock);
+    fixupPHINodeForNormalDest(OrigInvoke, OrigBlock, MergeBlock);
+    fixupPHINodeForUnwindDest(OrigInvoke, OrigBlock, ThenBlock, ElseBlock);
 
-    // Now set the normal destination of new the invoke instruction to be the
+    // Now set the normal destinations of the invoke instructions to be the
     // "merge" block.
+    OrigInvoke->setNormalDest(MergeBlock);
     NewInvoke->setNormalDest(MergeBlock);
   }
 
+  // Create a phi node for the returned value of the call site.
+  createRetPHINode(OrigInst, NewInst, MergeBlock, Builder);
+
   return NewInst;
 }
 
 bool llvm::isLegalToPromote(CallSite CS, Function *Callee,
                             const char **FailureReason) {
   assert(!CS.getCalledFunction() && "Only indirect call sites can be promoted");
 
   // Check the return type. The callee's return value type must be bitcast
if (!CastInst::isBitCastable(ActualTy, FormalTy)) {
         *FailureReason = "Argument type mismatch";
       return false;
     }
   }
 
   return true;
 }
 
-static void promoteCall(CallSite CS, Function *Callee, Instruction *&Cast) {
+void llvm::promoteCall(CallSite CS, Function *Callee,
+                       SmallVectorImpl<CastInst *> *Casts) {
   assert(!CS.getCalledFunction() && "Only indirect call sites can be promoted");
 
   // Set the called function of the call site to be the given callee.
   CS.setCalledFunction(Callee);
 
   // Since the call site will no longer be direct, we must clear metadata that
   // is only appropriate for indirect calls. This includes !prof and !callees
   // metadata.
void llvm::promoteCall(CallSite CS, Function *Callee,
   for (Use &U : CS.args()) {
     unsigned ArgNo = CS.getArgumentNo(&U);
     Type *FormalTy = Callee->getFunctionType()->getParamType(ArgNo);
     Type *ActualTy = U.get()->getType();
     if (FormalTy != ActualTy) {
       auto *Cast = CastInst::Create(Instruction::BitCast, U.get(), FormalTy, "",
                                     CS.getInstruction());
       CS.setArgument(ArgNo, Cast);
+      if (Casts)
+        Casts->push_back(Cast);
     }
   }
 
   // If the return type of the call site doesn't match that of the callee, cast
   // the returned value to the appropriate type.
   if (!CallSiteRetTy->isVoidTy() && CallSiteRetTy != CalleeRetTy)
-    Cast = createRetBitCast(CS, CallSiteRetTy);
+    createRetBitCast(CS, CallSiteRetTy, Casts);
+}
+
+void llvm::demoteCall(CallSite CS, Value *CalledValue,
+                      ArrayRef<CastInst *> Casts) {
+  assert(CS.getCalledFunction() && "Only direct call sites can be demoted");
+
+  // For each cast instruction, replace all of its uses with its source
+  // operand.
+  for (CastInst *Cast : Casts) {
+    while (!Cast->user_empty())
+      Cast->user_back()->replaceUsesOfWith(Cast, Cast->getOperand(0));
+    Cast->eraseFromParent();
+  }
+
+  // Set the called value of the call site, and mutate its function type.
+  CS.setCalledFunction(CalledValue);
+  CS.mutateFunctionType(cast<FunctionType>(
+      cast<PointerType>(CalledValue->getType())->getElementType()));
 }
 
 Instruction *llvm::promoteCallWithIfThenElse(CallSite CS, Function *Callee,
                                              MDNode *BranchWeights) {
 
   // Version the indirect call site. If the called value is equal to the given
-  // callee, 'NewInst' will be executed, otherwise the original call site will
+  // callee, the original call site will be executed, otherwise 'NewInst' will
   // be executed.
   Instruction *NewInst = versionCallSite(CS, Callee, BranchWeights);
 
-  // Promote 'NewInst' so that it directly calls the desired function.
-  Instruction *Cast = nullptr;
-  promoteCall(CallSite(NewInst), Callee, Cast);
-
-  // Create a phi node for the returned value of the call site.
-  createRetPHINode(CS.getInstruction(), Cast ? Cast : NewInst);
+  // Promote the original call site so that it directly calls the desired
+  // function.
+  promoteCall(CS, Callee);
 
-  // Return the new direct call.
+  // Return the new indirect call.
   return NewInst;
 }
 
 #undef DEBUG_TYPE

test/Transforms/PGOProfile/icp_covariant_call_return.ll

entry:
   %call = call noalias i8* @_Znwm(i64 8)
   %tmp = bitcast i8* %call to %struct.D*
   call void @_ZN1DC2Ev(%struct.D* %tmp)
   %tmp1 = bitcast %struct.D* %tmp to %struct.B*
   %tmp2 = bitcast %struct.B* %tmp1 to %struct.Base* (%struct.B*)***
   %vtable = load %struct.Base* (%struct.B*)**, %struct.Base* (%struct.B*)*** %tmp2, align 8
   %vfn = getelementptr inbounds %struct.Base* (%struct.B*)*, %struct.Base* (%struct.B*)** %vtable, i64 0
   %tmp3 = load %struct.Base* (%struct.B*)*, %struct.Base* (%struct.B*)** %vfn, align 8
-; ICALL-PROM:  [[BITCAST:%[0-9]+]] = bitcast %struct.Base* (%struct.B*)* %tmp3 to i8*
-; ICALL-PROM:  [[CMP:%[0-9]+]] = icmp eq i8* [[BITCAST]], bitcast (%struct.Derived* (%struct.D*)* @_ZN1D4funcEv to i8*)
+; ICALL-PROM:  [[CMP:%[0-9]+]] = icmp eq %struct.Base* (%struct.B*)* %tmp3, bitcast (%struct.Derived* (%struct.D*)* @_ZN1D4funcEv to %struct.Base* (%struct.B*)*)
 ; ICALL-PROM:  br i1 [[CMP]], label %if.true.direct_targ, label %if.false.orig_indirect, !prof [[BRANCH_WEIGHT:![0-9]+]]
 ; ICALL-PROM:if.true.direct_targ:
 ; ICALL-PROM:  [[ARG_BITCAST:%[0-9]+]] = bitcast %struct.B* %tmp1 to %struct.D*
-; ICALL-PROM:  [[DIRCALL_RET:%[0-9]+]] = call %struct.Derived* @_ZN1D4funcEv(%struct.D* [[ARG_BITCAST]])
+; ICALL-PROM:  [[DIRCALL_RET:%.+]] = call %struct.Derived* @_ZN1D4funcEv(%struct.D* [[ARG_BITCAST]])
 ; ICALL-PROM:  [[DIRCALL_RET_CAST:%[0-9]+]] = bitcast %struct.Derived* [[DIRCALL_RET]] to %struct.Base*
 ; ICALL-PROM:  br label %if.end.icp 
 ; ICALL-PROM:if.false.orig_indirect:
-; ICALL-PROM:  %call1 = call %struct.Base* %tmp3(%struct.B* %tmp1)
+; ICALL-PROM:  [[CALL1:%.+]] = call %struct.Base* %tmp3(%struct.B* %tmp1)
 ; ICALL-PROM:  br label %if.end.icp
 ; ICALL-PROM:if.end.icp:
-; ICALL-PROM:  [[PHI_RET:%[0-9]+]] = phi %struct.Base* [ %call1, %if.false.orig_indirect ], [ [[DIRCALL_RET_CAST]], %if.true.direct_targ ]
+; ICALL-PROM:  [[PHI_RET:%[0-9]+]] = phi %struct.Base* [ [[CALL1]], %if.false.orig_indirect ], [ [[DIRCALL_RET_CAST]], %if.true.direct_targ ]
   %call1 = call %struct.Base* %tmp3(%struct.B* %tmp1), !prof !1
   ret %struct.Base* %call1
 }
 
 !1 = !{!"VP", i32 0, i64 12345, i64 -3913987384944532146, i64 12345}
 ; ICALL-PROM-NOT: !1 = !{!"VP", i32 0, i64 12345, i64 -3913987384944532146, i64 12345}
 ; ICALL-PROM: [[BRANCH_WEIGHT]] = !{!"branch_weights", i32 12345, i32 0}
 ; ICALL-PROM-NOT: !1 = !{!"VP", i32 0, i64 12345, i64 -3913987384944532146, i64 12345}

test/Transforms/PGOProfile/icp_covariant_invoke_return.ll

 invoke.cont:
   %tmp = bitcast i8* %call to %struct.D*
   call void @_ZN1DC2Ev(%struct.D* %tmp)
   %tmp1 = bitcast %struct.D* %tmp to %struct.B*
   %tmp2 = bitcast %struct.B* %tmp1 to %struct.Base* (%struct.B*)***
   %vtable = load %struct.Base* (%struct.B*)**, %struct.Base* (%struct.B*)*** %tmp2, align 8
   %vfn = getelementptr inbounds %struct.Base* (%struct.B*)*, %struct.Base* (%struct.B*)** %vtable, i64 0
   %tmp3 = load %struct.Base* (%struct.B*)*, %struct.Base* (%struct.B*)** %vfn, align 8
-; ICALL-PROM:  [[BITCAST:%[0-9]+]] = bitcast %struct.Base* (%struct.B*)* %tmp3 to i8*
-; ICALL-PROM:  [[CMP:%[0-9]+]] = icmp eq i8* [[BITCAST]], bitcast (%struct.Derived* (%struct.D*)* @_ZN1D4funcEv to i8*)
+; ICALL-PROM:  [[CMP:%[0-9]+]] = icmp eq %struct.Base* (%struct.B*)* %tmp3, bitcast (%struct.Derived* (%struct.D*)* @_ZN1D4funcEv to %struct.Base* (%struct.B*)*)
 ; ICALL-PROM:  br i1 [[CMP]], label %if.true.direct_targ, label %if.false.orig_indirect, !prof [[BRANCH_WEIGHT:![0-9]+]]
 ; ICALL-PROM:if.true.direct_targ:
 ; ICALL-PROM:  [[ARG_BITCAST:%[0-9]+]] = bitcast %struct.B* %tmp1 to %struct.D*
-; ICALL-PROM:  [[DIRCALL_RET:%[0-9]+]] = invoke %struct.Derived* @_ZN1D4funcEv(%struct.D* [[ARG_BITCAST]])
-; ICALL-PROM:          to label %if.end.icp unwind label %lpad
+; ICALL-PROM:  [[DIRCALL_RET:%.+]] = invoke %struct.Derived* @_ZN1D4funcEv(%struct.D* [[ARG_BITCAST]])
+; ICALL-PROM:          to label %if.true.direct_targ.if.end.icp_crit_edge unwind label %lpad
+; ICALL-PROM:if.true.direct_targ.if.end.icp_crit_edge:
+; ICALL-PROM:  [[DIRCALL_RET_CAST:%[0-9]+]] = bitcast %struct.Derived* %call2 to %struct.Base*
+; ICALL-PROM:  br label %if.end.icp
 ; ICALL-PROM:if.false.orig_indirect:
 ; ICAll-PROM:  %call2 = invoke %struct.Base* %tmp3(%struct.B* %tmp1)
 ; ICAll-PROM:          to label %invoke.cont1 unwind label %lpad
 ; ICALL-PROM:if.end.icp:
-; ICALL-PROM:  [[DIRCALL_RET_CAST:%[0-9]+]] = bitcast %struct.Derived* [[DIRCALL_RET]] to %struct.Base*
 ; ICALL-PROM:  br label %invoke.cont1
   %call2 = invoke %struct.Base* %tmp3(%struct.B* %tmp1)
           to label %invoke.cont1 unwind label %lpad, !prof !1
 
 invoke.cont1:
 ; ICAll-PROM:  [[PHI_RET:%[0-9]+]] = phi %struct.Base* [ %call2, %if.false.orig_indirect ], [ [[DIRCALL_RET_CAST]], %if.end.icp ]
 ; ICAll-PROM:  %isnull = icmp eq %struct.Base* [[PHI_RET]], null
   %isnull = icmp eq %struct.Base* %call2, null

test/Transforms/PGOProfile/icp_invoke.ll

 define internal i32 @_ZL4bar2v() !PGOFuncName !1 {
 entry:
   ret i32 100
 }
 
 define i32 @_Z3goov() personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
 entry:
   %tmp = load void ()*, void ()** @foo1, align 8
-; ICP:  [[BITCAST_IC1:%[0-9]+]] = bitcast void ()* %tmp to i8*
-; ICP:  [[CMP_IC1:%[0-9]+]] = icmp eq i8* [[BITCAST_IC1]], bitcast (void ()* @_ZL4bar1v to i8*)
+; ICP:  [[CMP_IC1:%[0-9]+]] = icmp eq void ()* %tmp, @_ZL4bar1v
 ; ICP:  br i1 [[CMP_IC1]], label %[[TRUE_LABEL_IC1:.*]], label %[[FALSE_LABEL_IC1:.*]], !prof [[BRANCH_WEIGHT:![0-9]+]]
 ; ICP:[[TRUE_LABEL_IC1]]:
 ; ICP:  invoke void @_ZL4bar1v()
 ; ICP:          to label %[[DCALL_NORMAL_DEST_IC1:.*]] unwind label %lpad
 ; ICP:[[FALSE_LABEL_IC1]]:
   invoke void %tmp()
           to label %try.cont unwind label %lpad, !prof !2
 

 
 catch:
   %tmp5 = tail call i8* @__cxa_begin_catch(i8* %tmp2)
   tail call void @__cxa_end_catch()
   br label %try.cont
 
 try.cont:
   %tmp6 = load i32 ()*, i32 ()** @foo2, align 8
-; ICP:  [[BITCAST_IC2:%[0-9]+]] = bitcast i32 ()* %tmp6 to i8*
-; ICP:  [[CMP_IC2:%[0-9]+]] = icmp eq i8* [[BITCAST_IC2]], bitcast (i32 ()* @_ZL4bar2v to i8*)
+; ICP:  [[CMP_IC2:%[0-9]+]] = icmp eq i32 ()* %tmp6, @_ZL4bar2v
 ; ICP:  br i1 [[CMP_IC2]], label %[[TRUE_LABEL_IC2:.*]], label %[[FALSE_LABEL_IC2:.*]], !prof [[BRANCH_WEIGHT:![0-9]+]]
 ; ICP:[[TRUE_LABEL_IC2]]:
-; ICP:  [[RESULT_IC2:%[0-9]+]] = invoke i32 @_ZL4bar2v()
+; ICP:  [[RESULT_IC2_0:%.+]] = invoke i32 @_ZL4bar2v()
 ; ICP:          to label %[[DCALL_NORMAL_DEST_IC2:.*]] unwind label %lpad1
 ; ICP:[[FALSE_LABEL_IC2]]:
+; ICP:  [[RESULT_IC2_1:%.+]] = invoke i32 %tmp6()
+; ICP:          to label %[[DCALL_NORMAL_DEST_IC2:.*]] unwind label %lpad1
   %call = invoke i32 %tmp6()
           to label %try.cont8 unwind label %lpad1, !prof !3
 
 ; ICP:[[DCALL_NORMAL_DEST_IC2]]:
+; ICP:  [[PHI_0:%.+]] = phi i32 [ [[RESULT_IC2_1]], %[[FALSE_LABEL_IC2]] ], [ [[RESULT_IC2_0]], %[[TRUE_LABEL_IC2]] ]
 ; ICP:  br label %try.cont8
 lpad1:
   %tmp7 = landingpad { i8*, i32 }
           catch i8* bitcast (i8** @_ZTIi to i8*)
   %tmp8 = extractvalue { i8*, i32 } %tmp7, 0
   %tmp9 = extractvalue { i8*, i32 } %tmp7, 1
   %tmp10 = tail call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
   %matches5 = icmp eq i32 %tmp9, %tmp10
   br i1 %matches5, label %catch6, label %eh.resume
 
 catch6:
   %tmp11 = tail call i8* @__cxa_begin_catch(i8* %tmp8)
   tail call void @__cxa_end_catch()
   br label %try.cont8
 
 try.cont8:
   %i.0 = phi i32 [ undef, %catch6 ], [ %call, %try.cont ]
-; ICP:  %i.0 = phi i32 [ undef, %catch6 ], [ %call, %[[FALSE_LABEL_IC2]] ], [ [[RESULT_IC2]], %[[DCALL_NORMAL_DEST_IC2]] ]
+; ICP:  %i.0 = phi i32 [ undef, %catch6 ], [ [[PHI_0]], %[[DCALL_NORMAL_DEST_IC2]] ]
   ret i32 %i.0
 
 eh.resume:
   %ehselector.slot.0 = phi i32 [ %tmp9, %lpad1 ], [ %tmp3, %lpad ]
   %exn.slot.0 = phi i8* [ %tmp8, %lpad1 ], [ %tmp2, %lpad ]
   %lpad.val = insertvalue { i8*, i32 } undef, i8* %exn.slot.0, 0
   %lpad.val11 = insertvalue { i8*, i32 } %lpad.val, i32 %ehselector.slot.0, 1
   resume { i8*, i32 } %lpad.val11

test/Transforms/PGOProfile/icp_invoke_nouse.ll

 ; Function Attrs: uwtable
 define i32 @_Z3fooi(i32 %x) local_unnamed_addr personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
 entry:
   %tobool = icmp eq i32 %x, 0
   br i1 %tobool, label %if.end, label %cleanup
 
 if.end:                                           ; preds = %entry
   %fptr = load i32 ()*, i32 ()** @pfptr, align 8
-; ICP:  [[BITCAST_IC1:%[0-9]+]] = bitcast i32 ()* %fptr to i8*
-; ICP:  [[CMP_IC1:%[0-9]+]] = icmp eq i8* [[BITCAST_IC1]], bitcast (i32 ()* @_ZL4bar1v to i8*)
+; ICP:  [[CMP_IC1:%[0-9]+]] = icmp eq i32 ()* %fptr, @_ZL4bar1v
 ; ICP:  br i1 [[CMP_IC1]], label %[[TRUE_LABEL_IC1:.*]], label %[[FALSE_LABEL_IC1:.*]], !prof [[BRANCH_WEIGHT:![0-9]+]]
 ; ICP:[[TRUE_LABEL_IC1]]:
 ; ICP:  invoke i32 @_ZL4bar1v()
 ; ICP:          to label %[[DCALL_NORMAL_DEST_IC1:.*]] unwind label %lpad
 ; ICP:[[FALSE_LABEL_IC1]]:
   %call = invoke i32 %fptr()
           to label %cleanup unwind label %lpad, !prof !1
 

test/Transforms/PGOProfile/icp_vararg.ll

 ; RUN: opt < %s -pgo-icall-prom -S | FileCheck %s --check-prefix=ICALL-PROM
 ; RUN: opt < %s -passes=pgo-icall-prom -S | FileCheck %s --check-prefix=ICALL-PROM
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @foo = common global i32 (i32, ...)* null, align 8
 
 define i32 @va_func(i32 %num, ...) {
 entry:
   ret i32 0
 }
 
 define i32 @bar() #1 {
 entry:
   %tmp = load i32 (i32, ...)*, i32 (i32, ...)** @foo, align 8
-; ICALL-PROM:  [[BITCAST:%[0-9]+]] = bitcast i32 (i32, ...)* %tmp to i8*
-; ICALL-PROM:  [[CMP:%[0-9]+]] = icmp eq i8* [[BITCAST]], bitcast (i32 (i32, ...)* @va_func to i8*)
+; ICALL-PROM:  [[CMP:%[0-9]+]] = icmp eq i32 (i32, ...)* %tmp, @va_func
 ; ICALL-PROM:  br i1 [[CMP]], label %if.true.direct_targ, label %if.false.orig_indirect, !prof [[BRANCH_WEIGHT:![0-9]+]]
 ; ICALL-PROM:if.true.direct_targ:
-; ICALL-PROM:  [[DIRCALL_RET:%[0-9]+]] = call i32 (i32, ...) @va_func(i32 3, i32 12, i32 22, i32 4)
+; ICALL-PROM:  [[DIRCALL_RET:%.+]] = call i32 (i32, ...) @va_func(i32 3, i32 12, i32 22, i32 4)
 ; ICALL-PROM:  br label %if.end.icp
   %call = call i32 (i32, ...) %tmp(i32 3, i32 12, i32 22, i32 4), !prof !1
 ; ICALL-PROM:if.false.orig_indirect:
-; ICALL-PROM:  %call = call i32 (i32, ...) %tmp(i32 3, i32 12, i32 22, i32 4)
+; ICALL-PROM:  [[CALL:%.+]] = call i32 (i32, ...) %tmp(i32 3, i32 12, i32 22, i32 4)
 ; ICALL-PROM:  br label %if.end.icp
   ret i32 %call
 ; ICALL-PROM:if.end.icp:
-; ICALL-PROM:  [[PHI_RET:%[0-9]+]] = phi i32 [ %call, %if.false.orig_indirect ], [ [[DIRCALL_RET]], %if.true.direct_targ ]
+; ICALL-PROM:  [[PHI_RET:%[0-9]+]] = phi i32 [ [[CALL]], %if.false.orig_indirect ], [ [[DIRCALL_RET]], %if.true.direct_targ ]
 ; ICALL-PROM:  ret i32 [[PHI_RET]] 
 
 }
 
 !1 = !{!"VP", i32 0, i64 12345, i64 989055279648259519, i64 12345}
 ; ICALL-PROM: [[BRANCH_WEIGHT]] = !{!"branch_weights", i32 12345, i32 0}

test/Transforms/PGOProfile/indirect_call_promotion.ll

 define i32 @func4() {
 entry:
   ret i32 3
 }
 
 define i32 @bar() {
 entry:
   %tmp = load i32 ()*, i32 ()** @foo, align 8
-; ICALL-PROM:   [[BITCAST:%[0-9]+]] = bitcast i32 ()* %tmp to i8*
-; ICALL-PROM:   [[CMP:%[0-9]+]] = icmp eq i8* [[BITCAST]], bitcast (i32 ()* @func4 to i8*)
+; ICALL-PROM:   [[CMP:%[0-9]+]] = icmp eq i32 ()* %tmp, @func4
 ; ICALL-PROM:   br i1 [[CMP]], label %if.true.direct_targ, label %if.false.orig_indirect, !prof [[BRANCH_WEIGHT:![0-9]+]]
 ; ICALL-PROM: if.true.direct_targ:
-; ICALL-PROM:   [[DIRCALL_RET:%[0-9]+]] = call i32 @func4()
+; ICALL-PROM:   [[DIRCALL_RET:%.+]] = call i32 @func4()
 ; ICALL-PROM-SAMPLEPGO: call i32 @func4(), !prof [[CALL_METADATA:![0-9]+]]
 ; ICALL-PROM:   br label %if.end.icp
   %call = call i32 %tmp(), !prof !1
 ; ICALL-PROM: if.false.orig_indirect:
-; ICALL-PROM:   %call = call i32 %tmp(), !prof [[NEW_VP_METADATA:![0-9]+]]
+; ICALL-PROM:   [[CALL:%.+]] = call i32 %tmp(), !prof [[NEW_VP_METADATA:![0-9]+]]
   ret i32 %call
 ; ICALL-PROM: if.end.icp:
-; ICALL-PROM:   [[PHI_RET:%[0-9]+]] = phi i32 [ %call, %if.false.orig_indirect ], [ [[DIRCALL_RET]], %if.true.direct_targ ]
+; ICALL-PROM:   [[PHI_RET:%[0-9]+]] = phi i32 [ [[CALL]], %if.false.orig_indirect ], [ [[DIRCALL_RET]], %if.true.direct_targ ]
 ; ICALL-PROM:   ret i32 [[PHI_RET]]
 }
 
 !1 = !{!"VP", i32 0, i64 1600, i64 7651369219802541373, i64 1030, i64 -4377547752858689819, i64 410, i64 -6929281286627296573, i64 150, i64 -2545542355363006406, i64 10}
 
 ; ICALL-PROM: [[BRANCH_WEIGHT]] = !{!"branch_weights", i32 1030, i32 570}
 ; ICALL-PROM: [[NEW_VP_METADATA]] = !{!"VP", i32 0, i64 570, i64 -4377547752858689819, i64 410}
 ; ICALL-PROM-SAMPLEPGO: [[CALL_METADATA]] = !{!"branch_weights", i32 1030}