[Inliner] Inline through indirect call sites having !callees metadata

[mssimpso]

Summary

This patch allows the inliner to inspect !callees metadata attached to an indirect call site, and then inline the subset of callees for which inlining is profitable. The inlined code is conditionally executed depending on the run-time value of the call site's function pointer. !callees metadata is attached to an indirect call by the called value propagation pass and indicates the set of functions the call site might call.

Functionally, the patch versions an indirect call site for each possible callee that can be inlined, and then promotes those call sites to direct calls. If inlining is unsuccessful for any reason, a promoted call site is demoted and made indirect once again. This ensures that no direct call sites remain after inlining that weren't already in the program. Although call site promotion based on !callees metadata could conceivably be performed as a stand-alone pass, performing it in the inliner avoids extra work, since inline cost is used as the determining measure. Moreover, knowing if a callee will be inlined is probably one of the most reasonable static estimates of whether a call site should be promoted.

A dependent revision (D39339) modifies the call graph analyses to consider !callees metadata. It ensures the inliner will visit all of the functions listed in a given !callees metadata node prior to the functions containing call sites annotated by that node. This means the inliner's normal bottom-up traversal of the call graph is valid when promoting and then inlining the subset of possible callees.

[mssimpso]

Ping.

[davidxl]

A high level comment: I think the right direction is to share the implementation with the existing IndirectCallPromotion.cpp pass. The analyzer can synthesize the MD_prof profile data for the indirect targets, though the actual target count can be synthesized with some heuristics.

[mssimpso]

In D39869#936138, @davidxl wrote:

A high level comment: I think the right direction is to share the implementation with the existing IndirectCallPromotion.cpp pass. The analyzer can synthesize the MD_prof profile data for the indirect targets, though the actual target count can be synthesized with some heuristics.

Thanks very much for the feedback, David. Just to clarify, you mean both the indirect call promotion pass and the inliner patch here should use a common interface (like llvm::promoteIndirectCall, et al.) to perform the actual transformation? This makes sense to me, since there's a lot of overlap. There are a few differences in what I've implemented, though. For example, in this patch, we can do the promotion for a single callee without creating an if-then-else structure. I think sharing the implementation might require refactoring the existing code in the indirect call promotion pass somewhat. Are you OK with me doing that as a first step?

[davidxl]

Yes, I think it is good to do the necessary refactoring work first.

[mssimpso]

In D39869#936338, @davidxl wrote:

Yes, I think it is good to do the necessary refactoring work first.

OK, sounds good. I'll submit the refactoring patch for review, and then update this one afterwards. Thanks!

[mssimpso]

Rebased on top of D40658. We now use a common indirect call promotion interface.

[mssimpso]

Moved demoteCall, previously in D40751, to this patch.

[mssimpso]

Rebased.

[mssimpso]

Ping.

[davidxl]

I think 'tryToPromote' method should be moved to the indirect call promotion pass so that the callback to inline cost/benefit is exposed there (a more general cost/benefit model needs to be developed for indirect call promotion). Initially, I think we can limit the use of the getInlineCost callback to cases where profile data is not available, this will achieve what this patch is doing without affecting existing promotion heuristics.

[mssimpso]

In D39869#969989, @davidxl wrote:

I think 'tryToPromote' method should be moved to the indirect call promotion pass so that the callback to inline cost/benefit is exposed there (a more general cost/benefit model needs to be developed for indirect call promotion). Initially, I think we can limit the use of the getInlineCost callback to cases where profile data is not available, this will achieve what this patch is doing without affecting existing promotion heuristics.

Thanks for taking a look at this again, David. This makes sense to me -- I'll update the patch shortly.

[tejohnson]

Ping

[tejohnson]

In D39869#970309, @tejohnson wrote:

Ping

Wrong Patch - please ignore! Sorry.

[mssimpso]

Addressed David's comments.

• Made tryToPromote visible to the indirect call promotion pass
• Added a check in tryToPromote that gives up if a call site has profile metadata to avoid conflicting heuristics.

David,

I hope I've at least addressed the spirit of you comments. First, I've moved tryToPromote to Transforms/Utils/CallPromotionUtils.cpp. IndirectCallPromotion.cpp already includes the necessary header, so the function is now visible there.

Second, regarding the inline cost callback, I made the profitability measure completely generic. So the client needs to provide tryToPromote with a function to determine if promotion is profitable, given an indirect call site and possible direct callee. I think it makes sense to implement it in this generic way if we leave the function in CallPromotionUtils.cpp. When called from within the inliner, the profitability measure is a wrapper around shouldInline that takes care of caching the inline cost to avoid recomputing it, etc. If we want to reuse the code in the indirect call promotion pass, we would need to define provide a similar profitability function.

I was unsure if you intended that I completely scrap all of the inliner changes, and make tryToPromote only available to the indirect call promotion pass. I didn't take your comment to mean this, but I could be wrong. Just in case, here are a few words in defense of the current patch.

In the current approach, where promotion is directed by the inliner, we limit promotion to the callees we know will definitely be inlined. So promotion is really just an intermediate step. We know the direct callee will be eliminated by inlining, so we're actually just inlining code through the indirect call. We also know the profitability measure we're trying to satisfy, inline cost, is accurate (but note that we need D39339 to get this right). Although a useful indicator, I think if we use inline cost outside the inliner, or at least outside a CallGraphSCCPass, it may end up being wrong in some cases. Suppose, for example, we use inline cost in a module pass that promotes an indirect call site to directly call function F. Later, the inliner may decide to inline a lot of code into F, making F a bad candidate for inlining into its caller. So the benefit we thought we were getting by promotion (the code simplification, measured by inline cost, due to inlining F into its caller) turns out to be nothing. This kind of situation is avoided by letting the inliner direct the promotion.

Thanks again!

[davidxl]

I actually mean the former.

Regarding your comment "Although a useful indicator, I think if we use inline cost outside the inliner, or at least outside a CallGraphSCCPass, it may end up being wrong in some cases. Suppose, for example, we use inline cost in a module pass that promotes an indirect call site to directly call function F. Later, the inliner may decide to inline a lot of code into F, making F a bad candidate for inlining into its caller. So the benefit we thought we were getting by promotion (the code simplification, measured by inline cost, due to inlining F into its caller) turns out to be nothing. This kind of situation is avoided by letting the inliner direct the promotion",

I understand what you are saying -- due to the bottom up order (limitation) of the current inliner, doing inlining cost analysis at indirect call promootion may not reflect what is actually happening -- the indirect callsite that deem to be beneficial to be inlined at indirect call promotion pass may not be inlinable anymore because it may get too large.

I need to think about this a little.

[mssimpso]

Hi David,

I'd like to get back to this patch soon. Have you given the previous comments anymore thought? We had started to discuss whether the transformation should be done inside the inliner or the indirect call promotion pass. An advantage of letting the inliner do the promotion is that the inline cost, which is used to determine if an indirect call should be promoted, is known. If promotion is done outside the inliner, the cost would only be an estimate. An advantage of moving the transformation to the indirect call promotion pass may be that it is a better conceptual fit within that pass. On the other hand, it is not a pgo-driven transformation. A third possibility would be a separate pass. Would do you think?

[mssimpso]

Ping.

[davidxl]

I added Easwaran to get a closer look at the change.

[mssimpso]

In D39869#1042160, @davidxl wrote:

I added Easwaran to get a closer look at the change.

Thanks David.

[eraman]

lib/Transforms/IPO/Inliner.cpp

447

CallSite has a getCaller method.

1121

This same code repeats twice. This can be moved to a static function. Actually, most of the logic used is common to legacy and new PM (except for the callgraph updating bit) and hence could be consolidated into a separate function.

1142

There are two other checks (starting at line 1051) that could prevent a callsite from inlining before we call shouldInline. This means it is possible that the promoted call doesn't get inlined.

[mssimpso]

Addressed Easwaran's comments.

• Reused more code between the new and legacy pass managers.
• Ensured that promotion only happens when inlining is successful.

Thanks for your comments, Easwaran. This a fairly large update, primarily meant to address your concern that a promoted call site doesn't end up getting inlined. Ensuring this situation doesn't happen is somewhat difficult because the inlining algorithm itself can abort, even after the inline cost has been computed and inlining found to be profitable. The solution I've implemented here is to perform the promotion before the inline cost is computed (as in the previous version of the patch), but if inlining fails for any reason, the call site is demoted and made indirect again. So there shouldn't be any new direct calls in the program that weren't there before.

[eraman]

This is looking good. Main comment I have is about the number of promotions+inlining that can take place is unbounded. One could argue that if there were many small direct calls, we would inline all of them, but still I feel it is better to limit the number of promotions.

lib/Transforms/IPO/Inliner.cpp

723

Is there any limit on the size of the callees metadata? Otherwise you might potentially end up promoting a large number of calls and inline them

842

Nit: The call is not necessarily inlined. More precisely, the call is deleted (either due to inlining or because it is dead). Perhaps just modify the comment above or rename the function.

lib/Transforms/Utils/CallPromotionUtils.cpp

447

You could set the CPI->Versioned = true here instead of passing an additional parameter to versionCallSite.

476

It looks like isLegalToPromote doesn't check if the callee's body is available. If F->isDeclaration() is true, is there any reason to promote? The inliner is going to not inline the callee and ends up unnecessarily promote and demote the callee. This is even more important in the versioned case since it invalidates the analysis.

test/Transforms/Inline/callees-metadata.ll

23

This is relying on how instructions get simplified after inlining. Why not check that there are not call instructions and followed by a ret?

[mssimpso]

Addressed Easwaran's comments. Thanks again!

• Added a command line option to limit the number of callees that are inlined for a given indirect call site.
• Changed tests to not run simplification after inlining.
• Renamed setInlined to setCallSiteRemoved.
• Addressed the remaining comments for CallPromotionUtils.

lib/Transforms/IPO/Inliner.cpp

723

The CalledValuePropagation pass limits the size of the callees set to 4 functions. But it's probably a good idea to have a limit in the inliner as well. I'll add a command line option for limiting the number of callees we inline for a given call site.

lib/Transforms/Utils/CallPromotionUtils.cpp

476

Nice catch! I think this check was present in a previous version of this patch, but it must have gotten lost in an update. I'll add it back.

[mssimpso]

Ping.

[eraman]

LGTM

lib/Transforms/IPO/Inliner.cpp

764

Typo

[mssimpso]

Thanks very much for the review Easwaran! As this patch still depends on D39339 to get the function iteration order right in the inliner, would you mind taking at look at that patch if you have a chance, or recommending someone for the review? Thanks again.

include/llvm/Transforms/Utils/CallPromotionUtils.h

 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.
+/// Casts is non-null, these bitcasts are collected in the provided container.
 Instruction *promoteCall(CallSite CS, Function *Callee,
-                         CastInst **RetBitCast = nullptr);
+                         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. The indirect call or invoke instruction is returned.
+Instruction *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 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

lib/Transforms/IPO/Inliner.cpp

 #include "llvm/IR/DebugLoc.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
+#include "llvm/Transforms/Utils/CallPromotionUtils.h"
 #include "llvm/Transforms/Utils/Cloning.h"
 #include "llvm/Transforms/Utils/ImportedFunctionsInliningStatistics.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/ModuleUtils.h"
 #include <algorithm>
 #include <cassert>
 #include <functional>
 #include <tuple>
shouldInline(CallSite CS, function_ref<InlineCost(CallSite CS)> GetInlineCost,
   }
 
   DEBUG(dbgs() << "    Inlining: cost=" << IC.getCost()
                << ", thres=" << IC.getThreshold()
                << ", Call: " << *CS.getInstruction() << '\n');
   return IC;
 }
 
+/// Update the legacy call graph after the given call site is promoted.
+///
+/// The call site should be direct at this point. If it was versioned when it
+/// was promoted, \p Inst should refer to the newly created indirect call.
+static void updateLegacyCGAfterCSPromotion(CallGraph &CG, CallSite DirectCS,
+                                           CallSite IndirectCS) {
+  Function *Callee = DirectCS.getCalledFunction();
+  assert(Callee && "Call was not promoted");
+  CallGraphNode *Caller = CG[DirectCS.getInstruction()->getFunction()];
+
+  // The promoted call site had !callees metadata attached to it. This is
+  // represented in the legacy call graph by an external node. Find it.
+  CallGraphNode *External = nullptr;
+  for (CallGraphNode::iterator I = Caller->begin(), E = Caller->end(); I != E;
+       ++I)
+    if (I->first == IndirectCS.getInstruction()) {
+      External = I->second;
+      break;
+    }
+
+  // Unlink the direct callee from the external node.
+  assert(External && "External node for !callees metadata not found");
+  External->removeAnyCallEdgeTo(CG[Callee]);
+
+  if (DirectCS.getInstruction() != IndirectCS.getInstruction())
+    // If the original call site was versioned, the direct call site is not yet
+    // in the call graph.
+    Caller->addCalledFunction(DirectCS, CG[Callee]);
+  else
+    // Otherwise, replace the indirect call site edge with the direct call site
+    // edge.
+    Caller->replaceCallEdge(IndirectCS, DirectCS, CG[Callee]);
+}
+
+/// Try to promote an indirect call site.
+///
+/// This function attempts to promote the given indirect call site so that its
+/// callee (or potential callees) may be inlined. Promotion is attempted for
+/// call sites having !callees metadata. For indirect call sites having a small
+/// number of possible callees, !callees metadata indicates what those
+/// functions are.
+///
+/// The approach begins by inspecting the !callees metadata attached to a call
+/// site. There are a few cases to consider based on the number of possible
+/// callees. The first two are trivial. First, if the metadata indicates that
+/// there are zero possible callees, the call site must be dead, and so it is
+/// marked unreachable. Second, if the metadata indicates that there is only
+/// one possible callee, it is promoted to a direct call site regardless of
+/// whether inlining the callee is profitable or not. The last and most
+/// interesting case is when the metadata indicates that there are more than
+/// one possible callee.
+///
+/// When a call site has more then one possible callee, the inliner is allowed
+/// to inline any of the callees according to its usual heuristics. This is
+/// done by iterating over the possible callees and computing their inline
+/// cost. If a profitable callee is found, the iteration terminates and the
+/// call site is immediately promoted inside an if-then-else structure, where
+/// the "then" block contains a direct call to the profitable callee, and the
+/// "else" block contains a clone of the original indirect call site. The
+/// callees metadata of the two call sites is updated to reflect the promotion.
+///
+/// The inline cost and call site clone are communicated back to the inliner.
+/// This allows the inliner to avoid recomputing the inline cost for the callee
+/// that was just promoted, and it allows it to add the new indirect call site
+/// to its work list to be processed once again. The new indirect call site
+/// will have one less possible callee. Processing the call sites in this way
+/// effectively inlines all the profitable callees of the original indirect
+/// call site. Callees for which the inline cost is computed but found to be
+/// unprofitable to inline are cached so that they will not be analyzed more
+/// than once.
+///
+/// The function returns a pointer to the direct call or invoke instruction if
+/// the given call site was promoted. Otherwise, it returns a null pointer. If
+/// the inline cost of the resulting direct call site was computed, it is stored
+/// in \p OIC. Lastly, the callees for which the inline cost is computed are
+/// stored in \p Visited.
+static Instruction *
+tryToPromoteCallSite(CallSite CS,
+                     function_ref<InlineCost(CallSite CS)> GetInlineCost,
+                     OptimizationRemarkEmitter &ORE, Optional<InlineCost> &OIC,
+                     SmallPtrSetImpl<Function *> &Visited) {
+  assert(!CS.getCalledFunction() && "Can only promote indirect calls");
+
+  // Collect the functions the call site might call. If the call site doesn't
+  // have !callees metadata, we don't know its possible callees, so there's
+  // nothing to do.
+  if (!CS.getInstruction()->getMetadata(LLVMContext::MD_callees))
+    return nullptr;
+  SmallVector<Function *, 4> PossibleCallees = CS.getKnownCallees();
+
+  // If the metadata indicates that there are zero possible callees, the call
+  // site must be dead, so we mark it unreachable.
+  if (PossibleCallees.empty()) {
+    BasicBlock *BB = CS.getInstruction()->getParent();
+    BB->splitBasicBlock(CS.getInstruction());
+    BB->getTerminator()->eraseFromParent();
+    new UnreachableInst(BB->getContext(), BB);
+    return nullptr;
+  }
+
+  // If the metadata indicates that there is only one possible callee, we
+  // attempt to promote the call site. If successful, we clear the call site's
+  // !callees metadata.
+  if (PossibleCallees.size() == 1) {
+    if (!isLegalToPromote(CS, PossibleCallees[0]))
+      return nullptr;
+    Instruction *Direct = promoteCall(CS, PossibleCallees[0]);
+    Direct->setMetadata(LLVMContext::MD_callees, nullptr);
+    return Direct;
+  }
+
+  // If the metadata indicates that there is more than one possible callee, we
+  // attempt to promote the call site by versioning it.
+  for (unsigned I = 0; I < PossibleCallees.size(); ++I) {
+    Function *F = PossibleCallees[I];
+
+    // Skip this function if we already know it to be unprofitable, it's a
+    // declaration, or it can't be promoted.
+    if (Visited.count(F) || F->isDeclaration() || !isLegalToPromote(CS, F))
+      continue;
+
+    Visited.insert(F);
+    Value *CalledValue = CS.getCalledValue();
+
+    // Compute the inline cost of the function. We do this by first
+    // speculatively modifying the call site so that it calls the desired
+    // function. We then compute the inline cost using the regular inline
+    // heuristic. Once the cost is computed, the call site is demoted to its
+    // original state. If inlining is not profitable, we move on to the next
+    // possible callee.
+    SmallVector<CastInst *, 4> Casts;
+    CS = CallSite(promoteCall(CS, F, &Casts));
+    Optional<InlineCost> Cost = shouldInline(CS, GetInlineCost, ORE);
+    CS = CallSite(demoteCall(CS, CalledValue, Casts));
+    if (!Cost)
+      continue;
+
+    // Promote the indirect call site such that we conditionally execute the
+    // direct call. The original instruction is moved to the "else" block, and
+    // the new direct call in the "then" block is returned.
+    Instruction *Direct = promoteCallWithIfThenElse(CS, F);
+
+    // The original call site remains indirect, but we must remove the function
+    // from its !callees metadata. After the promotion, we know this call site
+    // cannot target it.
+    PossibleCallees.erase(PossibleCallees.begin() + I);
+    MDBuilder MDB(CS.getInstruction()->getContext());
+    CS.getInstruction()->setMetadata(LLVMContext::MD_callees,
+                      MDB.createCallees(PossibleCallees));
+
+    // Save the inline cost so the inliner doesn't have to recompute it. The
+    // function will be inlined into the promoted call site.
+    OIC.emplace(*Cost);
+    return Direct;
+  }
+
+  return nullptr;
+}
+
 /// Return true if the specified inline history ID
 /// indicates an inline history that includes the specified function.
 static bool InlineHistoryIncludes(
     Function *F, int InlineHistoryID,
     const SmallVectorImpl<std::pair<Function *, int>> &InlineHistory) {
   while (InlineHistoryID != -1) {
     assert(unsigned(InlineHistoryID) < InlineHistory.size() &&
            "Invalid inline history ID");
inlineCallsImpl(CallGraphSCC &SCC, CallGraph &CG,
   for (unsigned i = 0; i < FirstCallInSCC; ++i)
     if (Function *F = CallSites[i].first.getCalledFunction())
       if (SCCFunctions.count(F))
         std::swap(CallSites[i--], CallSites[--FirstCallInSCC]);
 
   InlinedArrayAllocasTy InlinedArrayAllocas;
   InlineFunctionInfo InlineInfo(&CG, &GetAssumptionCache, PSI);
 
+  // A cache of callees per indirect call site for which we've computed an
+  // inline cost. Inlining these callees is not profitable, and we don't want
+  // to recompute the cost.
+  DenseMap<Instruction *, SmallPtrSet<Function *, 4>> UnprofitableCallees;
+
   // Now that we have all of the call sites, loop over them and inline them if
   // it looks profitable to do so.
   bool Changed = false;
   bool LocalChange;
   do {
     LocalChange = false;
     // Iterate over the outer loop because inlining functions can cause indirect
     // calls to become direct calls.
     // CallSites may be modified inside so ranged for loop can not be used.
     for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
       CallSite CS = CallSites[CSi].first;
 
       Function *Caller = CS.getCaller();
-      Function *Callee = CS.getCalledFunction();
+
+      // FIXME for new PM: because of the old PM we currently generate ORE and
+      // in turn BFI on demand.  With the new PM, the ORE dependency should
+      // just become a regular analysis dependency.
+      OptimizationRemarkEmitter ORE(Caller);
+
+      // Try to inline through indirect call sites. If we have an indirect call
+      // site with a known set of possible callees (e.g., as specified by
+      // !callees metadata), promote the call site to directly call a function
+      // we know will be inlined. The inline cost, if computed during promotion,
+      // is saved to avoid recomputation. If the call site was versioned by the
+      // promotion, it is added to the work list to be processed again.
+      Optional<InlineCost> OIC = None;
+      if (!CS.getCalledFunction()) {
+        auto &Visited = UnprofitableCallees[CS.getInstruction()];
+        Instruction *Direct = tryToPromoteCallSite(CS, GetInlineCost, ORE, OIC, Visited);
+        if (!Direct)
+          continue;
+        CallSite DirectCS(Direct);
+        updateLegacyCGAfterCSPromotion(CG, DirectCS, CS);
+        if (Direct != CS.getInstruction())
+          CallSites.push_back({CS, -1});
+        CS = DirectCS;
+      }
 
       // We can only inline direct calls to non-declarations.
-      if (!Callee || Callee->isDeclaration())
+      Function *Callee = CS.getCalledFunction();
+      if (Callee->isDeclaration())
         continue;
 
       Instruction *Instr = CS.getInstruction();
 
       bool IsTriviallyDead = isInstructionTriviallyDead(Instr, &TLI);
 
       int InlineHistoryID;
       if (!IsTriviallyDead) {
         // If this call site was obtained by inlining another function, verify
         // that the include path for the function did not include the callee
         // itself.  If so, we'd be recursively inlining the same function,
         // which would provide the same callsites, which would cause us to
         // infinitely inline.
         InlineHistoryID = CallSites[CSi].second;
         if (InlineHistoryID != -1 &&
             InlineHistoryIncludes(Callee, InlineHistoryID, InlineHistory))
           continue;
       }
 
-      // FIXME for new PM: because of the old PM we currently generate ORE and
-      // in turn BFI on demand.  With the new PM, the ORE dependency should
-      // just become a regular analysis dependency.
-      OptimizationRemarkEmitter ORE(Caller);
-
-      Optional<InlineCost> OIC = shouldInline(CS, GetInlineCost, ORE);
+      if (!OIC) {
+        Optional<InlineCost> Cost = shouldInline(CS, GetInlineCost, ORE);
         // If the policy determines that we should inline this function,
         // delete the call instead.
-      if (!OIC)
+        if (!Cost)
           continue;
+        OIC.emplace(*Cost);
+      }
 
       // If this call site is dead and it is to a readonly function, we should
       // just delete the call instead of trying to inline it, regardless of
       // size.  This happens because IPSCCP propagates the result out of the
       // call and then we're left with the dead call.
       if (IsTriviallyDead) {
         DEBUG(dbgs() << "    -> Deleting dead call: " << *Instr << "\n");
         // Update the call graph by deleting the edge from Callee to Caller.
for (unsigned CSi = 0; CSi != CallSites.size(); ++CSi) {
           for (Value *Ptr : InlineInfo.InlinedCalls)
             CallSites.push_back(std::make_pair(CallSite(Ptr), NewHistoryID));
         }
       }
 
       // If we inlined or deleted the last possible call site to the function,
       // delete the function body now.
       if (Callee && Callee->use_empty() && Callee->hasLocalLinkage() &&
           // TODO: Can remove if in SCC now.
           !SCCFunctions.count(Callee) &&
           // The function may be apparently dead, but if there are indirect
           // callgraph references to the node, we cannot delete it yet, this
           // could invalidate the CGSCC iterator.
           CG[Callee]->getNumReferences() == 0) {
         DEBUG(dbgs() << "    -> Deleting dead function: " << Callee->getName()
                      << "\n");
         CallGraphNode *CalleeNode = CG[Callee];
PreservedAnalyses InlinerPass::run(LazyCallGraph::SCC &InitialC,
   for (auto &N : InitialC) {
     // We want to generally process call sites top-down in order for
     // simplifications stemming from replacing the call with the returned value
     // after inlining to be visible to subsequent inlining decisions.
     // FIXME: Using instructions sequence is a really bad way to do this.
     // Instead we should do an actual RPO walk of the function body.
     for (Instruction &I : instructions(N.getFunction()))
       if (auto CS = CallSite(&I))
-        if (Function *Callee = CS.getCalledFunction())
-          if (!Callee->isDeclaration())
-            Calls.push_back({CS, -1});
   }
   if (Calls.empty())
     return PreservedAnalyses::all();
 
   // Capture updatable variables for the current SCC and RefSCC.
   auto *C = &InitialC;
   auto *RC = &C->getOuterRefSCC();
 
for (int i = 0; i < (int)Calls.size(); ++i) {
 
     auto GetInlineCost = [&](CallSite CS) {
       Function &Callee = *CS.getCalledFunction();
       auto &CalleeTTI = FAM.getResult<TargetIRAnalysis>(Callee);
       return getInlineCost(CS, Params, CalleeTTI, GetAssumptionCache, {GetBFI},
                            PSI, &ORE);
     };
 
+    // A cache of callees per indirect call site for which we've computed an
+    // inline cost. Inlining these callees is not profitable, and we don't want
+    // to recompute the cost.
+    DenseMap<Instruction *, SmallPtrSet<Function *, 4>> UnprofitableCallees;
+
     // Now process as many calls as we have within this caller in the sequnece.
     // We bail out as soon as the caller has to change so we can update the
     // call graph and prepare the context of that new caller.
-    bool DidInline = false;
+    bool ChangedCallGraph = false;
     for (; i < (int)Calls.size() && Calls[i].first.getCaller() == &F; ++i) {
       int InlineHistoryID;
       CallSite CS;
       std::tie(CS, InlineHistoryID) = Calls[i];
+
+      // Try to inline through indirect call sites. If we have an indirect call
+      // site with a known set of possible callees (e.g., as specified by
+      // !callees metadata), promote the call site to directly call a function
+      // we know will be inlined. The inline cost, if computed during promotion,
+      // is saved to avoid recomputation. If the call site was versioned by the
+      // promotion, it is added to the work list to be processed again.
+      Optional<InlineCost> OIC = None;
+      if (!CS.getCalledFunction()) {
+        auto &Visited = UnprofitableCallees[CS.getInstruction()];
+        Instruction *Direct = tryToPromoteCallSite(CS, GetInlineCost, ORE, OIC, Visited);
+        if (!Direct)
+          continue;
+        ChangedCallGraph = true;
+        if (Direct != CS.getInstruction())
+          Calls.push_back({CS, -1});
+        CS = CallSite(Direct);
+      }
+
+      // We can only inline direct calls to non-declarations.
       Function &Callee = *CS.getCalledFunction();
+      if (Callee.isDeclaration())
+        continue;
 
       if (InlineHistoryID != -1 &&
           InlineHistoryIncludes(&Callee, InlineHistoryID, InlineHistory))
         continue;
 
       // Check if this inlining may repeat breaking an SCC apart that has
       // already been split once before. In that case, inlining here may
       // trigger infinite inlining, much like is prevented within the inliner
       // itself by the InlineHistory above, but spread across CGSCC iterations
       // and thus hidden from the full inline history.
       if (CG.lookupSCC(*CG.lookup(Callee)) == C &&
           UR.InlinedInternalEdges.count({&N, C})) {
         DEBUG(dbgs() << "Skipping inlining internal SCC edge from a node "
                         "previously split out of this SCC by inlining: "
                      << F.getName() << " -> " << Callee.getName() << "\n");
         continue;
       }
 
-      Optional<InlineCost> OIC = shouldInline(CS, GetInlineCost, ORE);
+      if (!OIC) {
+        Optional<InlineCost> Cost = shouldInline(CS, GetInlineCost, ORE);
         // Check whether we want to inline this callsite.
-      if (!OIC)
+        if (!Cost)
           continue;
+        OIC.emplace(*Cost);
+      }
 
       // Setup the data structure used to plumb customization into the
       // `InlineFunction` routine.
       InlineFunctionInfo IFI(
           /*cg=*/nullptr, &GetAssumptionCache, PSI,
           &FAM.getResult<BlockFrequencyAnalysis>(*(CS.getCaller())),
           &FAM.getResult<BlockFrequencyAnalysis>(Callee));
 
       // Get DebugLoc to report. CS will be invalid after Inliner.
       DebugLoc DLoc = CS->getDebugLoc();
       BasicBlock *Block = CS.getParent();
 
       using namespace ore;
 
       if (!InlineFunction(CS, IFI)) {
         ORE.emit([&]() {
           return OptimizationRemarkMissed(DEBUG_TYPE, "NotInlined", DLoc, Block)
                  << NV("Callee", &Callee) << " will not be inlined into "
                  << NV("Caller", &F);
         });
         continue;
       }
-      DidInline = true;
+      ChangedCallGraph = true;
       InlinedCallees.insert(&Callee);
 
       ORE.emit([&]() {
         bool AlwaysInline = OIC->isAlways();
         StringRef RemarkName = AlwaysInline ? "AlwaysInline" : "Inlined";
         OptimizationRemark R(DEBUG_TYPE, RemarkName, DLoc, Block);
         R << NV("Callee", &Callee) << " inlined into ";
         R << NV("Caller", &F);
for (; i < (int)Calls.size() && Calls[i].first.getCaller() == &F; ++i) {
         }
       }
     }
 
     // Back the call index up by one to put us in a good position to go around
     // the outer loop.
     --i;
 
-    if (!DidInline)
+    if (!ChangedCallGraph)
       continue;
     Changed = true;
 
     // Add all the inlined callees' edges as ref edges to the caller. These are
     // by definition trivial edges as we always have *some* transitive ref edge
     // chain. While in some cases these edges are direct calls inside the
     // callee, they have to be modeled in the inliner as reference edges as
     // there may be a reference edge anywhere along the chain from the current

lib/Transforms/Utils/CallPromotionUtils.cpp

 // direct call sites.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/CallPromotionUtils.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
+#include "llvm/Support/Debug.h"
 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 be coming from the "merge" block. For example, in the code

 ///   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) {
+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 =
         &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;
+  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);
 }
 
 /// Predicate and clone the given call site.
 ///
if (!CastInst::isBitCastable(ActualTy, FormalTy)) {
       return false;
     }
   }
 
   return true;
 }
 
 Instruction *llvm::promoteCall(CallSite CS, Function *Callee,
-                               CastInst **RetBitCast) {
+                               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.
Instruction *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)
-    createRetBitCast(CS, CallSiteRetTy, RetBitCast);
+    createRetBitCast(CS, CallSiteRetTy, Casts);
+
+  return CS.getInstruction();
+}
+
+Instruction *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()));
 
   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.
   Instruction *NewInst = versionCallSite(CS, Callee, BranchWeights);
 
   // Promote 'NewInst' so that it directly calls the desired function.
   return promoteCall(CallSite(NewInst), Callee);
 }
 
 #undef DEBUG_TYPE

test/Other/new-pm-defaults.ll

 ; CHECK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}ProfileSummaryAnalysis
 ; CHECK-O-NEXT: Running analysis: ProfileSummaryAnalysis
 ; CHECK-O-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}LazyCallGraph{{.*}}>
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-O-NEXT: Starting CGSCC pass manager run.
 ; CHECK-O-NEXT: Running pass: InlinerPass
 ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph{{.*}}>
-; CHECK-O-NEXT: Running pass: PostOrderFunctionAttrsPass
 ; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
+; CHECK-O-NEXT: Running pass: PostOrderFunctionAttrsPass
 ; CHECK-O3-NEXT: Running pass: ArgumentPromotionPass
 ; CHECK-O-NEXT: Running pass: CGSCCToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-O-NEXT: Running pass: SpeculativeExecutionPass
 ; CHECK-O-NEXT: Running pass: JumpThreadingPass

test/Other/new-pm-thinlto-defaults.ll

 ; CHECK-O-NEXT: Running pass: RequireAnalysisPass<{{.*}}ProfileSummaryAnalysis
 ; CHECK-PRELINK-O-NEXT: Running analysis: ProfileSummaryAnalysis
 ; CHECK-O-NEXT: Running pass: ModuleToPostOrderCGSCCPassAdaptor<{{.*}}LazyCallGraph{{.*}}>
 ; CHECK-O-NEXT: Running analysis: InnerAnalysisManagerProxy
 ; CHECK-O-NEXT: Running analysis: LazyCallGraphAnalysis
 ; CHECK-O-NEXT: Starting CGSCC pass manager run.
 ; CHECK-O-NEXT: Running pass: InlinerPass
 ; CHECK-O-NEXT: Running analysis: OuterAnalysisManagerProxy<{{.*}}LazyCallGraph{{.*}}>
-; CHECK-O-NEXT: Running pass: PostOrderFunctionAttrsPass
 ; CHECK-O-NEXT: Running analysis: FunctionAnalysisManagerCGSCCProxy
+; CHECK-O-NEXT: Running pass: PostOrderFunctionAttrsPass
 ; CHECK-O3-NEXT: Running pass: ArgumentPromotionPass
 ; CHECK-O-NEXT: Running pass: CGSCCToFunctionPassAdaptor<{{.*}}PassManager{{.*}}>
 ; CHECK-O-NEXT: Starting llvm::Function pass manager run.
 ; CHECK-O-NEXT: Running pass: SROA
 ; CHECK-O-NEXT: Running pass: EarlyCSEPass
 ; CHECK-O-NEXT: Running analysis: MemorySSAAnalysis
 ; CHECK-O-NEXT: Running pass: SpeculativeExecutionPass
 ; CHECK-O-NEXT: Running pass: JumpThreadingPass

test/Transforms/Inline/callees-metadata.ll

+; RUN: opt < %s -inline -simplifycfg -S | FileCheck %s
+; RUN: opt < %s -passes='cgscc(inline,function(simplify-cfg))' -S | FileCheck %s
+
+; A call instruction with empty !callees metadata. This is undefined behavior,
+; so the call is marked unreachable.
+;
+; CHECK-LABEL: @call.0.0(
+; CHECK-NEXT:    unreachable
+define void @call.0.0(void ()* %fp) {
+  call void %fp(), !callees !{}
+  ret void
+}
+
+; A call instruction with two possible callees that can both inlined.
+;
+; CHECK-LABEL: @call.2.2(
+; CHECK:         [[TMP0:%.*]] = icmp eq i64 (i64, i64)* %fp, @select_def_0
+; CHECK-NEXT:    [[TMP1:%.*]] = select i1 [[TMP0]], i64 %x, i64 %y
+; CHECK-NEXT:    ret i64 [[TMP1]]
+;
+define i64 @call.2.2(i64 %x, i64 %y, i64 (i64, i64)* %fp) {
+  %tmp0 = call i64 %fp(i64 %x, i64 %y),
+     !callees !{i64 (i64, i64)* @select_def_0, i64 (i64, i64)* @select_def_1}
+  ret i64 %tmp0
+}
+
+; A call instruction with three possible callees, only one of which can be
+; inlined. Since more than one possible callee remains after promotion, the
+; cloned call is indirect.
+;
+; CHECK-LABEL: @call.3.1(
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i64 (i64, i64)* %fp, @select_def_0
+; CHECK-NEXT:    br i1 [[TMP0]], label %[[MERGE:.*]], label %[[ELSE:.*]]
+; CHECK:       [[ELSE]]:
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 %fp(i64 %x, i64 %y), !callees
+; CHECK-NEXT:    br label %[[MERGE:.*]]
+; CHECK:       [[MERGE]]:
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i64 [ [[TMP1]], %[[ELSE]] ], [ %x, {{.*}} ]
+; CHECK-NEXT:    ret i64 [[TMP2]]
+;
+define i64 @call.3.1(i64 %x, i64 %y, i64 (i64, i64)* %fp) {
+  %tmp0 = call i64 %fp(i64 %x, i64 %y),
+     !callees !{i64 (i64, i64)* @select_def_0, i64 (i64, i64)* @select_dec_1,
+                i64 (i64, i64)* @select_dec_0}
+  ret i64 %tmp0
+}
+
+; A call instruction with two possible callees, only one of which can be
+; inlined. Since only one possible callee remains after promotion, the cloned
+; call is promoted as well.
+;
+; CHECK-LABEL: @call.2.1(
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i64 (i64, i64)* %fp, @select_def_0
+; CHECK-NEXT:    br i1 [[TMP0]], label %[[MERGE:.*]], label %[[ELSE:.*]]
+; CHECK:       [[ELSE]]:
+; CHECK-NEXT:    [[TMP1:%.*]] = call i64 @select_dec_1(i64 %x, i64 %y)
+; CHECK-NEXT:    br label %[[MERGE:.*]]
+; CHECK:       [[MERGE]]:
+; CHECK-NEXT:    [[TMP2:%.*]] = phi i64 [ [[TMP1]], %[[ELSE]] ], [ %x, {{.*}} ]
+; CHECK-NEXT:    ret i64 [[TMP2]]
+;
+define i64 @call.2.1(i64 %x, i64 %y, i64 (i64, i64)* %fp) {
+  %tmp0 = call i64 %fp(i64 %x, i64 %y),
+     !callees !{i64 (i64, i64)* @select_def_0, i64 (i64, i64)* @select_dec_1}
+  ret i64 %tmp0
+}
+
+; A call instruction with two possible callees, only one of which can be
+; inlined. Since only one possible callee remains after promotion, the cloned
+; call is promoted as well. Bitcasts must be inserted for the promoted call's
+; arguments and return value since the callee's function type doesn't match
+; that of the function pointer.
+;
+; CHECK-LABEL: @call.2.1.bitcast(
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32* (i32**)* %fp, bitcast (i64* (i64**)* @load_def to i32* (i32**)*)
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32** %x to i64**
+; CHECK-NEXT:    br i1 [[TMP0]], label %[[THEN:.*]], label %[[ELSE:.*]]
+; CHECK:       [[THEN]]:
+; CHECK-NEXT:    [[TMP2:%.*]] = load i64*, i64** [[TMP1]]
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i64* [[TMP2]] to i32*
+; CHECK-NEXT:    br label %[[MERGE:.*]]
+; CHECK:       [[ELSE]]:
+; CHECK-NEXT:    [[TMP4:%.*]] = call i64* @load_dec(i64** [[TMP1]])
+; CHECK-NEXT:    [[TMP5:%.*]] = bitcast i64* [[TMP4]] to i32*
+; CHECK-NEXT:    br label %[[MERGE]]
+; CHECK:       [[MERGE]]:
+; CHECK-NEXT:    [[TMP6:%.*]] = phi i32* [ [[TMP5]], %[[ELSE]] ], [ [[TMP3]], %[[THEN]] ]
+; CHECK-NEXT:    ret i32* [[TMP6]]
+;
+define i32* @call.2.1.bitcast(i32** %x, i32* (i32**)* %fp) {
+  %tmp0 = call i32* %fp(i32** %x),
+     !callees !{i64* (i64**)* @load_def, i64* (i64**)* @load_dec}
+  ret i32* %tmp0
+}
+
+; An invoke instruction with two possible callees, only one of which can be
+; inlined. Since only one possible callee remains after promotion, the cloned
+; invoke is promoted as well. The normal destination has a phi node that must
+; be fixed.
+;
+; CHECK-LABEL: @invoke.2.1(
+; CHECK:         br i1 undef, label %[[TRY:.*]], label %[[NORMAL:.*]]
+; CHECK:       [[TRY]]:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i64* (i64**)* %op, @load_def
+; CHECK-NEXT:    br i1 [[TMP0]], label %[[THEN:.*]], label %[[ELSE:.*]]
+; CHECK:       [[THEN]]:
+; CHECK-NEXT:    [[TMP1:%.*]] = load i64*, i64** %x
+; CHECK-NEXT:    br label %[[NORMAL]]
+; CHECK:       [[ELSE]]:
+; CHECK:         [[TMP2:%.*]] = invoke i64* @load_dec(i64** %x)
+; CHECK-NEXT:                      to label %[[NORMAL]] unwind label %[[EXCEPT:.*]]
+; CHECK:       [[NORMAL]]:
+; CHECK-NEXT:    [[TMP3:%.*]] = phi i64* [ null, %entry ], [ [[TMP2]], %[[ELSE]] ], [ [[TMP1]], %[[THEN]] ]
+; CHECK-NEXT:    ret i64* [[TMP3]]
+; CHECK:       [[EXCEPT]]:
+; CHECK-NEXT:    [[TMP4:%.*]] = landingpad { i8*, i64 }
+; CHECK-NEXT:                   cleanup
+; CHECK-NEXT:    ret i64* null
+;
+define i64* @invoke.2.1(i64** %x, i64* (i64**)* %op) personality i64 (...)* null {
+entry:
+  br i1 undef, label %try, label %normal
+try:
+  %tmp0 = invoke i64* %op(i64 **%x)
+             to label %normal unwind label %except,
+                !callees !{i64* (i64**)* @load_def, i64* (i64**)* @load_dec}
+normal:
+  %tmp1 = phi i64* [ %tmp0, %try ], [ null, %entry ]
+  ret i64* %tmp1
+except:
+  %tmp2 = landingpad {i8*, i64}
+          cleanup
+  ret i64* null
+}
+
+; An invoke instruction with two possible callees, only one of which can be
+; inlined. Since only one possible callee remains after promotion, the cloned
+; invoke is promoted as well. The normal destination has a phi node that must
+; be fixed. Additionally, bitcasts must be inserted for the promoted invoke's
+; arguments and return value since the callee's function type doesn't match
+; that of the function pointer.
+;
+; CHECK-LABEL: @invoke.2.1.bitcast(
+; CHECK:         br i1 undef, label %[[TRY:.*]], label %[[NORMAL:.*]]
+; CHECK:       [[TRY]]:
+; CHECK-NEXT:    [[TMP0:%.*]] = icmp eq i32* (i32**)* %op, bitcast (i64* (i64**)* @load_def to i32* (i32**)*)
+; CHECK-NEXT:    [[TMP1:%.*]] = bitcast i32** %x to i64**
+; CHECK-NEXT:    br i1 [[TMP0]], label %[[THEN:.*]], label %[[ELSE:.*]]
+; CHECK:       [[THEN]]:
+; CHECK-NEXT:    [[TMP2:%.*]] = load i64*, i64** [[TMP1]]
+; CHECK-NEXT:    [[TMP3:%.*]] = bitcast i64* [[TMP2]] to i32*
+; CHECK-NEXT:    br label %[[NORMAL]]
+; CHECK:       [[ELSE]]:
+; CHECK:         [[TMP4:%.*]] = invoke i64* @load_dec(i64** [[TMP1]])
+; CHECK-NEXT:                      to label %[[MERGE:.*]] unwind label %[[EXCEPT:.*]]
+; CHECK:       [[MERGE]]:
+; CHECK-NEXT:    [[TMP5:%.*]] = bitcast i64* [[TMP4]] to i32*
+; CHECK-NEXT:    br label %[[NORMAL]]
+; CHECK:       [[NORMAL]]:
+; CHECK-NEXT:    [[TMP6:%.*]] = phi i32* [ null, %entry ], [ [[TMP5]], %[[MERGE]] ], [ [[TMP3]], %[[THEN]] ]
+; CHECK-NEXT:    ret i32* [[TMP6]]
+; CHECK:       [[EXCEPT]]:
+; CHECK-NEXT:    [[TMP8:%.*]] = landingpad { i8*, i32 }
+; CHECK-NEXT:                   cleanup
+; CHECK-NEXT:    ret i32* null
+;
+define i32* @invoke.2.1.bitcast(i32** %x, i32* (i32**)* %op) personality i32 (...)* null {
+entry:
+  br i1 undef, label %try, label %normal
+try:
+  %tmp0 = invoke i32* %op(i32 **%x)
+             to label %normal unwind label %except,
+                !callees !{i64* (i64**)* @load_def, i64* (i64**)* @load_dec}
+normal:
+  %tmp1 = phi i32* [ %tmp0, %try ], [ null, %entry ]
+  ret i32* %tmp1
+except:
+  %tmp2 = landingpad {i8*, i32}
+          cleanup
+  ret i32* null
+}
+
+; The functions declarations and definitions below are used in the above tests
+; and are not interesting. The !callees metadata that references the functions
+; is expanded and attached to the call sites.
+;
+declare i64 @select_dec_0(i64 %x, i64 %y)
+declare i64 @select_dec_1(i64 %x, i64 %y)
+declare i64* @load_dec(i64** %x)
+
+define i64 @select_def_0(i64 %x, i64 %y) { ret i64 %x }
+define i64 @select_def_1(i64 %x, i64 %y) { ret i64 %y }
+define i64* @load_def(i64** %x) {
+  %tmp0 = load i64*, i64** %x
+  ret i64* %tmp0
+}