[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

47 ↗

(On Diff #125800)

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

lib/Transforms/IPO/SampleProfile.cpp

829 ↗

(On Diff #125800)

what is this change for?

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

315 ↗

(On Diff #125800)

What is this change for?

lib/Transforms/Utils/CallPromotionUtils.cpp

36 ↗

(On Diff #125800)

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.

279 ↗

(On Diff #125800)

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

47 ↗

(On Diff #125800)

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

lib/Transforms/IPO/SampleProfile.cpp

829 ↗

(On Diff #125800)

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 ↗

(On Diff #125800)

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

36 ↗

(On Diff #125800)

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!

279 ↗

(On Diff #125800)

This will be added to D39869

[davidxl]

lib/Transforms/IPO/SampleProfile.cpp

829 ↗

(On Diff #125800)

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 ↗

(On Diff #125800)

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

166 ↗

(On Diff #126569)

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 ↗

(On Diff #125800)

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

166 ↗

(On Diff #126569)

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

36 ↗

(On Diff #127032)

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

lib/Transforms/Utils/CallPromotionUtils.cpp

424 ↗

(On Diff #127032)

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

[mssimpso]

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

llvm/trunk/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.
+///
+/// This function promotes the given call site, returning the direct call or
+/// invoke instruction. If the function type of the call site doesn't match that
+/// of the callee, bitcast instructions are inserted where appropriate. If \p
+/// RetBitCast is non-null, it will be used to store the return value bitcast,
+/// if created.
+Instruction *promoteCall(CallSite CS, Function *Callee,
+                         CastInst **RetBitCast = nullptr);
+
 /// 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.
+/// site. The original call site is moved into the "else" block. A clone of the
+/// indirect call site is promoted, placed in the "then" 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

llvm/trunk/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. For example, in the code
+/// below:
+///
+///   then_bb:
+///     %t0 = invoke i32 %ptr() 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
+///
+///   normal_dst:
+///     %t3 = phi i32 [ %x, %orig_bb ], ...
+///
+/// "orig_bb" is no longer a predecessor of "normal_dst", so the phi nodes in
+/// "normal_dst" must be fixed to refer to "merge_bb":
+///
+///    normal_dst:
+///      %t3 = phi i32 [ %x, %merge_bb ], ...
+///
 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;
-    Value *V = Phi->getIncomingValue(Idx);
-    if (dyn_cast<Instruction>(V) == Invoke) {
-      Phi->setIncomingBlock(Idx, ElseBlock);
-      Phi->addIncoming(NewInst, OrigBlock);
-      continue;
-    }
-    Phi->addIncoming(V, ElseBlock);
+    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.
+/// For example, in the code below:
+///
+///   then_bb:
+///     %t0 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
+///
+///   else_bb:
+///     %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
+///
+///   unwind_dst:
+///     %t3 = phi i32 [ %x, %orig_bb ], ...
+///
+/// "orig_bb" is no longer a predecessor of "unwind_dst", so the phi nodes in
+/// "unwind_dst" must be fixed to refer to "then_bb" and "else_bb":
+///
+///   unwind_dst:
+///     %t3 = phi i32 [ %x, %then_bb ], [ %x, %else_bb ], ...
+///
 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) {
+///
+/// For example, if \p OrigInst is defined in "else_bb" and \p NewInst is
+/// defined in "then_bb", we create the following phi node:
+///
+///   ; Uses of the original instruction are replaced by uses of the phi node.
+///   %t0 = phi i32 [ %orig_inst, %else_bb ], [ %new_inst, %then_bb ],
+///
+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(OrigInst, OrigInst->getParent());
-  Phi->addIncoming(NewInst, RetValBB);
+  Phi->addIncoming(NewInst, NewInst->getParent());
 }
 
 /// 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 on if we have a call
 /// or invoke instruction.
-Instruction *createRetBitCast(CallSite CS, Type *RetTy) {
+///
+/// For example, if the call instruction below requires a bitcast after
+/// promotion:
+///
+///   orig_bb:
+///     %t0 = call i32 @func()
+///     ...
+///
+/// The bitcast is placed after the call instruction:
+///
+///   orig_bb:
+///     ; Uses of the original return value are replaced by uses of the bitcast.
+///     %t0 = call i32 @func()
+///     %t1 = bitcast i32 %t0 to ...
+///     ...
+///
+/// A similar transformation is performed for invoke instructions. However,
+/// since invokes are terminating, a new block is created for the bitcast. For
+/// example, if the invoke instruction below requires a bitcast after promotion:
+///
+///   orig_bb:
+///     %t0 = invoke i32 @func() to label %normal_dst unwind label %unwind_dst
+///
+/// The edge between the original block and the invoke's normal destination is
+/// split, and the bitcast is placed there:
+///
+///   orig_bb:
+///     %t0 = invoke i32 @func() to label %split_bb unwind label %unwind_dst
+///
+///   split_bb:
+///     ; Uses of the original return value are replaced by uses of the bitcast.
+///     %t1 = bitcast i32 %t0 to ...
+///     br label %normal_dst
+///
+static void createRetBitCast(CallSite CS, Type *RetTy, CastInst **RetBitCast) {
 
   // 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 (RetBitCast)
+    *RetBitCast = 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 "else" block, and a clone
 /// of the call site is placed in the "then" block. The cloned instruction is
 /// returned.
+///
+/// For example, the call instruction below:
+///
+///   orig_bb:
+///     %t0 = call i32 %ptr()
+///     ...
+///
+/// Is replace by the following:
+///
+///   orig_bb:
+///     %cond = icmp eq i32 ()* %ptr, @func
+///     br i1 %cond, %then_bb, %else_bb
+///
+///   then_bb:
+///     ; The clone of the original call instruction is placed in the "then"
+///     ; block. It is not yet promoted.
+///     %t1 = call i32 %ptr()
+///     br merge_bb
+///
+///   else_bb:
+///     ; The original call instruction is moved to the "else" block.
+///     %t0 = call i32 %ptr()
+///     br merge_bb
+///
+///   merge_bb:
+///     ; Uses of the original call instruction are replaced by uses of the phi
+///     ; node.
+///     %t2 = phi i32 [ %t0, %else_bb ], [ %t1, %then_bb ]
+///     ...
+///
+/// A similar transformation is performed for invoke instructions. However,
+/// since invokes are terminating, more work is required. For example, the
+/// invoke instruction below:
+///
+///   orig_bb:
+///     %t0 = invoke %ptr() to label %normal_dst unwind label %unwind_dst
+///
+/// Is replace by the following:
+///
+///   orig_bb:
+///     %cond = icmp eq i32 ()* %ptr, @func
+///     br i1 %cond, %then_bb, %else_bb
+///
+///   then_bb:
+///     ; The clone of the original invoke instruction is placed in the "then"
+///     ; block, and its normal destination is set to the "merge" block. It is
+///     ; not yet promoted.
+///     %t1 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
+///
+///   else_bb:
+///     ; The original invoke instruction is moved into the "else" block, and
+///     ; its normal destination is set to the "merge" block.
+///     %t0 = invoke i32 %ptr() to label %merge_bb unwind label %unwind_dst
+///
+///   merge_bb:
+///     ; Uses of the original invoke instruction are replaced by uses of the
+///     ; phi node, and the merge block branches to the normal destination.
+///     %t2 = phi i32 [ %t0, %else_bb ], [ %t1, %then_bb ]
+///     br %normal_dst
+///
 static Instruction *versionCallSite(CallSite CS, Value *Callee,
-                                    MDNode *BranchWeights,
-                                    BasicBlock *&ThenBlock,
-                                    BasicBlock *&ElseBlock,
-                                    BasicBlock *&MergeBlock) {
+                                    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.
   TerminatorInst *ThenTerm = nullptr;
   TerminatorInst *ElseTerm = nullptr;
   SplitBlockAndInsertIfThenElse(Cond, CS.getInstruction(), &ThenTerm, &ElseTerm,
                                 BranchWeights);
-  ThenBlock = ThenTerm->getParent();
-  ElseBlock = ElseTerm->getParent();
-  MergeBlock = OrigInst->getParent();
+  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);
 
   // If the original call site is an invoke instruction, we have extra work to
-  // do since invoke instructions are terminating.
+  // 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());
 
-    // Now set the normal destination of new the invoke instruction to be the
+    // Fix-up phi nodes in the original invoke's normal and unwind destinations.
+    fixupPHINodeForNormalDest(OrigInvoke, OrigBlock, MergeBlock);
+    fixupPHINodeForUnwindDest(OrigInvoke, MergeBlock, ThenBlock, ElseBlock);
+
+    // 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) {
+Instruction *llvm::promoteCall(CallSite CS, Function *Callee,
+                               CastInst **RetBitCast) {
   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.
   CS.getInstruction()->setMetadata(LLVMContext::MD_prof, nullptr);
   CS.getInstruction()->setMetadata(LLVMContext::MD_callees, nullptr);
 
   // If the function type of the call site matches that of the callee, no
   // additional work is required.
   if (CS.getFunctionType() == Callee->getFunctionType())
-    return;
+    return CS.getInstruction();
 
   // Save the return types of the call site and callee.
   Type *CallSiteRetTy = CS.getInstruction()->getType();
   Type *CalleeRetTy = Callee->getReturnType();
 
   // Change the function type of the call site the match that of the callee.
   CS.mutateFunctionType(Callee->getFunctionType());
 
if (FormalTy != ActualTy) {
                                     CS.getInstruction());
       CS.setArgument(ArgNo, 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, RetBitCast);
+
+  return CS.getInstruction();
 }
 
 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
   // be executed.
-  BasicBlock *ThenBlock, *ElseBlock, *MergeBlock;
-  Instruction *NewInst = versionCallSite(CS, Callee, BranchWeights, ThenBlock,
-                                         ElseBlock, MergeBlock);
+  Instruction *NewInst = versionCallSite(CS, Callee, BranchWeights);
 
   // Promote 'NewInst' so that it directly calls the desired function.
-  Instruction *Cast = NewInst;
-  promoteCall(CallSite(NewInst), Callee, Cast);
-
-  // If the original call site is an invoke instruction, we have to fix-up phi
-  // nodes in the invoke's normal and unwind destinations.
-  if (auto *OrigInvoke = dyn_cast<InvokeInst>(CS.getInstruction())) {
-    fixupPHINodeForNormalDest(OrigInvoke, MergeBlock, ElseBlock, Cast);
-    fixupPHINodeForUnwindDest(OrigInvoke, MergeBlock, ThenBlock, ElseBlock);
-  }
-
-  // Create a phi node for the returned value of the call site.
-  createRetPHINode(CS.getInstruction(), Cast ? Cast : NewInst);
-
-  // Return the new direct call.
-  return NewInst;
+  return promoteCall(CallSite(NewInst), Callee);
 }
 
 #undef DEBUG_TYPE

llvm/trunk/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_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)

llvm/trunk/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:          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* [[DIRCALL_RET]] 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

llvm/trunk/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:          to label %[[DCALL_NORMAL_DEST_IC2:.*]] unwind label %lpad1
+; ICP:  [[RESULT_IC2_0:%[0-9]+]] = invoke i32 @_ZL4bar2v()
+; ICP:          to label %[[MERGE_BB:.*]] unwind label %lpad1
 ; ICP:[[FALSE_LABEL_IC2]]:
+; ICP:  [[RESULT_IC2_1:%.+]] = invoke i32 %tmp6()
+; ICP:          to label %[[MERGE_BB]] unwind label %lpad1
   %call = invoke i32 %tmp6()
           to label %try.cont8 unwind label %lpad1, !prof !3
 
-; ICP:[[DCALL_NORMAL_DEST_IC2]]:
+; ICP:[[MERGE_BB]]:
+; ICP:  [[MERGE_PHI:%.+]] = 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 ], [ [[MERGE_PHI]], %[[MERGE_BB]] ]
   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

llvm/trunk/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
 

llvm/trunk/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:  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:  br label %if.end.icp

llvm/trunk/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-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]+]]