[PGO] Promote indirect calls to conditional direct calls with value-profile

[xur]

Summary

This patch implements the transformation that promotes indirect calls to conditional direct calls when the indirect-call value profile meta-data is available.

It is invoked in two places: (1) after the IR-level profile-use pass. (2) in LTO optimizations. (1) performs limited promotion as many of the targets are in other modules. (2) is capable of promoting all the targets.

The Transformation performs legality check and profitability check. Legality check mainly for corrupted profiles where the ic-targets can points to wrong targets. Profitability check currently only uses the counts value and the ratio b/w this target and total indirect-call count.

We stress-tested the transformation with SPEC2006 to promote all the indirect-targets in the value profiles (in lto compilation).

We haven yet to do a thorough performance tuning. Here is the initial performance numbers with some SPEC programming running (10-run average on an ibis_sandybridge machine).

`` (1) (2) (3) (4)
spec/2006/fp/C++/453.povray 42.05 -8.17% +3.72% +2.32%
spec/2006/int/C++/471.omnetpp 23.69 -3.41% +3.37% +1.27%
spec/2006/int/C++/473.astar 23.04 -1.49% +1.91% +1.68%
spec/2006/int/C++/483.xalancbmk 38.83 -1.91% +6.01% +4.99%
spec/2000/int/C++/252.eon 4999 -14.47% +4.84% +2.36%``

(1) PGO + LTO
(2) PGO
(3) PGO + LTO + ICP(Indirect Call Promotion)
(4) PGO + LTO + ICP(only promote 1 target)

One known issue to be fixed later:
code duplication (like unroll) b/w value profile annotation and value profile transformation blindly duplicates the counts in the VP metadata. Need to update the metadata copying.

[silvas]

Can you split the pass out of PGOInstrumentation.cpp?

Also, there does not appear to be enough testing for the amount of functionality introduced.

include/llvm/Transforms/Instrumentation.h

86

Please name the parameter after what it does. What does it control?

Also, whatever it does control can probably be done in a separate patch.

lib/ProfileData/InstrProf.cpp

91 ↗

(On Diff #49766)

This function is confusingly named. How about "get name ignoring per-file mangling" or something? A comment can explain why this is valid for LTO.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

302 ↗

(On Diff #49766)

Please clarify why this is needed in a comment (and possibly a separate patch).

973 ↗

(On Diff #49766)

No floating point.

1000 ↗

(On Diff #49766)

ParamNum

1025 ↗

(On Diff #49766)

NumVals is way too generic of a name. Please be more specific. If it is just the number of entries in ValueData then use ArrayRef.

1059 ↗

(On Diff #49766)

NumPromotions is always just equal to WorkList.size().

Actually, I would remove the terminology "worklist" and just say "promotions".

E.g. add struct CandidatePromotion with two members TargetFunction and Count. Then have this function just return a std::vector<CandidatePromotion>.

1130 ↗

(On Diff #49766)

Redundant parentheses.

1140 ↗

(On Diff #49766)

std::next (or llvm::next, if we can't use std::next yet).

I.e.

if (FuncRetType != CallRetType)
  NewInst = new BitCastInst(NewInst, CallRetType, "", std::next(NewInst));

Also, I see you are using IRBuilder above. Any reason why IRBuilder is not preferred for the IR building later in the function?

1184 ↗

(On Diff #49766)

The naming here is quite poor. We have 3 functions:

performPromotion
doPromotion
doVersion

I think a better naming is:

processFunction
tryToPromote
promote

respectively.

1188 ↗

(On Diff #49766)

In a separate patch, please add a helper function findIndirectCallSites(F) so that you can do for auto &I : findIndirectCallSites(F)) instead of having this boilerplate manually calling visit.

1198 ↗

(On Diff #49766)

getCandidatePromotionsForCallSite is a better name.

auto CandidatePromotions = getCandidatePromotionsForCallSite(...);
NumPromoted += tryToPromote(ICall, CandidatePromotions, TotalCount)

1213 ↗

(On Diff #49766)

If you had ValueDataArray in an ArrayRef (and annotateValueSite took an ArrayRef), then this would be annotateValueSite(*M, *I, ValueDataArray.drop_front(NumPromoted, TotalCount, IPVK_IndirectCallTarget, MaxNumPromotions) which would be a lot nicer.

test/Transforms/PGOProfile/indirect_call_annotation.ll

2 ↗

(On Diff #49766)

Do not piggy-back on existing tests. You are adding completely new functionality which should have its own independent tests.

[xur]

Sean: Thanks for the detailed suggestions. I'll split the new feature into a separated file.

I will also put some of changes into a separated patch.

I do have some other tests locally -- I just not yet to convert them into the unit tests. I'll add them alone with the review goes.

lib/ProfileData/InstrProf.cpp

91 ↗

(On Diff #49766)

This is to deal with the interaction with LTO's internalization. I'll split this part of change into a separated patch.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

302 ↗

(On Diff #49766)

This will go to a separated patch.

1025 ↗

(On Diff #49766)

will use a ArrayRef

1140 ↗

(On Diff #49766)

No particular reason that I don't use IRbuilder. The inserted instructions are not in different BBs (not with the original call inst). I just thought it's convenient to change the code stream directly.

1188 ↗

(On Diff #49766)

ok. will do a separated patch.

1213 ↗

(On Diff #49766)

yes. this is cleaner. but this requires a annotateValueSite() change. I prefer to do this in a post-commit cleanup patch.

test/Transforms/PGOProfile/indirect_call_annotation.ll

2 ↗

(On Diff #49766)

undo the change.

[silvas]

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1213 ↗

(On Diff #49766)

A pre-commit cleanup patch is also possible.

[mehdi_amini]

include/llvm/ProfileData/InstrProf.h

160 ↗

(On Diff #49766)

I expect lengthy description of the naming, why the difference between LTO and non-LTO. If it described somewhere else, please insert a reference to it.

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

126 ↗

(On Diff #49766)

Remove

1140 ↗

(On Diff #49766)

The IRBuilder has the nice property that you can supply a name for the instruction and it'll show up only in debug build.

[xur]

split some of the chages to http://reviews.llvm.org/D17895

include/llvm/ProfileData/InstrProf.h

160 ↗

(On Diff #49766)

see http://reviews.llvm.org/D17895

[xur]

Integrated with Sean's review comments.
more unit tests are still to be added. Will include them later.

This patch depends on
http://reviews.llvm.org/D17895

Thanks,

-Rong

[davidxl]

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1223 ↗

(On Diff #49766)

See comment in 17895.

There is no need for this map. InstrProfSymtab should return the real function name from the PGOName's MD5 sum (icall target value). Using the real function name, you can directly use:

M.getFunction(RealName) to return the function.

[mehdi_amini]

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

1140 ↗

(On Diff #49766)

Just a note: forget the comment above on the IRBuilder, this has changed recently and names are handled dynamically in the Context now.

[xur]

This patch uses the updated InstrProf interface in patch http://reviews.llvm.org/D17895.

A few more unit tests also added.

This also fixed a regression in last patch: it seems the "std::next()" is not working I thought here:
NewInst = new BitCastInst(NewInst, CallRetType, "", std::next(NewInst));
It would not return the next instruction. This is fixed in this patch.

Again, this patch depends on http://reviews.llvm.org/D17895.

[xur]

Update the patch with recently refactoring patches.
Add handling of invoke instructions (covariant return type for invoke is to be supported later).
Also add some internal options for debugging.
Stressed tested with SPEC2006.

[johanengelen]

lib/Transforms/IPO/PassManagerBuilder.cpp

229

Placing add(createPGOIndirectCallPromotionPass()) here means that IndirectCallPromotionPass will be enabled at -O0, which I think is undesirable.

[mehdi_amini]

I expect that somewhere you look at the "opt_none" attribute on the function and bail.

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

559

Why isn't is a function pass?

[mehdi_amini]

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

75

s/transforamtion/transformation/

[xur]

I will check Attribute::OptimizeNone per @joker.eph's suggestion.

lib/Transforms/IPO/PassManagerBuilder.cpp

229

Good point. We should not do this in O0. I'll move this call out of this function.

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

559

mainly I need to create InstrProfSymtab which is module level. I don't want to create this symtab for each function.

[xur]

Integrated the review comments from Johan and Mehdi.

Thanks!

[mehdi_amini]

lib/Transforms/IPO/PassManagerBuilder.cpp

386

Why is it running twice in LTO mode?

591

What is the meaning of the "xur" here?

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

535

Can you implement this in a utility function? I expect the "pass wrapper" to have a dummy runOnModule that would only call the public API.

[xur]

Medhi, here is the patch that uses a static function. Does it look OK?

As for your question about the two-step promotion: Yes, this produces the same result if we only do the promotion in LTO optimization. The intra-module promotion will stop at the first target that it cannot promote and write the remaining VP targets to the metadata. The cross-module promotion will pick it up and do the rest.

Thanks!
-Rong

[mehdi_amini]

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

536

Nice, but should be static considering the name. Alternatively I don't mind having it non static if it is called something like promoteIndirectCalls()

[xur]

Fix the function name.

[johanengelen]

(thanks for your work on this btw! ;)

test/Transforms/PGOProfile/icp_vararg.ll

34

I think the branch_weights are calculated slightly wrong.
branch_weights usually have an offset of 1, where 1 means there is no profile measurement that it was taken. See the documentation of scaleBranchWeight in CodeGenPGO.cpp of Clang.

[xur]

We intentionally drop this +1 in IR level PGO instrumentation. I thing
branch weight can handle 0 weight now.

Thanks,

-Rong

[xur]

Refactor the code to break a large function into smaller ones.
This new patch supports the covariant return for invoke instructions too.

[xur]

fix comments.

[anemet]

I benchmarked this patch on our ARM64. I've done two runs.

In the first, I used the patch with -enable-value-profiling, LTO and PGO of course. I was using FE-based instrumentation. This is the first column in the table below.

I've also done a second run where I tried to fix up the missed promotions due to the incorrect internalization for static functions (the FE variant of D17895). This helps povray which has a few critical indirect calls to functions that are statically defined. Unfortunately, the promoted calls are still not inlined in povray which would further improve performance.

This the second column in the table and the diff is relative to the previous column (i.e. povray in the second run recovers *half* the regression from the first run). The numbers are directly from LNT so a negative percentage is a performance *improvement*.

|                        |    patch  | no-localize |
|------------------------+-----------+-------------+
| CINT2006/464.h264ref   |    -3.35% |             |
| CINT2006/483.xalancbmk |    -1.11% |             |
|------------------------+-----------+-------------+
| CFP2006/453.povray     |    +0.92% | -0.48%      |
|------------------------+-----------+-------------+
| CINT2000/252.eon       |    -1.06% |             |

[anemet]

So to summarize, this looks great on ARM64 assuming we have a solution for the internalization problem for FE-based profiling as well. xur, is there already a patch for that?

[xur]

Adam, thanks for testing on ARM64 and sharing the number.

For front-end's VP annotation, I've sent out a patch for review a few weeks
early:
http://reviews.llvm.org/D18624

Could you try that?

Thanks,

-Rong

[anemet]

Sure, I'll try it.

[davidxl]

First batch of comments from browsing the patch.

lib/IR/Instructions.cpp

3016 ↗

(On Diff #53081)

This change can be carved out as a NFC refactoring.

lib/Transforms/IPO/PassManagerBuilder.cpp

591

that left -- that are left

592

intra-module targets

593

can you explain the 'save compile time' part here?

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

75

once the total number of promotions equals the cutoff value.

78

Why all upper case, ICPCutOff looks better.

81

-->

If ICPCSSkip is non zero, the first ICPCSSkip callsites will be skipped.

93

If the option is set to true, only call instructions will be considered for transformation -- invoke instructions will be ignored.

150

maps indirect call profile values to function names.

170

records

171

Perhaps PromotionCandidate?

186

Document this method -- what is passed in and what is returned.

190

make it static member function

222

just
if (count < ICPCountThreshold)

224

When can this happen? Should it be corrected in caller?

235

Is this check needed? NotAvailableInModule is essentially body not available.

279

This local variable is not used.

363

make the name more meaningful such as "if.true.direct_targ"

538

It always returns true -- change it to void

[anemet]

In D17864#402676, @xur wrote:

Adam, thanks for testing on ARM64 and sharing the number.

For front-end's VP annotation, I've sent out a patch for review a few weeks
early:
http://reviews.llvm.org/D18624

Could you try that?

I am replying under D18624.

[davidxl]

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

379

Do you need merge BB here for invoke at all (which will be empty and unreachable)?

440

if you remove MergeBB, there is no need for this step -- or this is needed to avoid fixing up phis in the original normal dest?

446

add comment -- clear the value profile data.

556

Can this be folded into create4DirectCallInst call?

[xur]

lib/IR/Instructions.cpp

3016 ↗

(On Diff #53081)

OK. Will split this code out to a separated patch.

lib/Transforms/IPO/PassManagerBuilder.cpp

593

As I mentioned in earlier reply. the optimization performed in LTOOptimizationPasses cannot be palatalized. The Intra-module promotion can be trivially paralleled. LTO part of promotion takes pretty long for moderately large programs like 483.xalancbmk in spec2006. Splitting into two part saves the time for parallel builds.

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

186

will do.

224

will have this checked in the caller.

235

decls might be available.
just for debug.
I'll merge this two cases.

379

I assume you are referring this to the invoke instr.
I need this BB to insert a potential bit-cast inst.
If there is not bit-cast, it will be just a branch to the original destBB.
I assume this gonna be clean by late CFG optimization.

440

as I mentioned early, this is for bit-cast, not for phis.

556

I remember there is a transformation ordering issue. but I can try. will comment this more in the new patch.

[xur]

Integrated David's comments.
(1) it turned out we don't need new interface for castIsValid. I now use the existing isBitCastable()
(2) I was able to fold insertCallRetCast() to createDirectCallInst() which make code more compact.
I have to add a reference parameter in createDirCallInst() as I need to use both the direct-call instruction and the bitcast instruction.

Thanks,

-Rong

[davidxl]

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

408

Fix the comments.

This method fixes up PHI nodes in block BB. In BB, there may be PHIs with incoming block being OrigBB (the MergeBB after block splitting). After if-then-else splitting, OrigBB is no longer the predecessor block of BB. Instead two new predecessors are added: IndirectCallBB and DirectCallBB, so the PHI nodes's incoming BBs need to be fixed up accordingly.

412

This method is correct only for unwind/eh dest BB for an invoke instruction. It is not right for the normalDest.

For normalDest BB, the PHI node's predecessor BB remain unchanged -- OrigBB (i.e. MergeBB), but the value of the PHI incoming value may change into new PHI or cast inst inserted into the MergeBB.

428

Add assert that V is defined in a BB that dominates IndirectCallBB

478

Clean --> Clear

497

This comment needs lots of cleanup.

502

Since this function body computes lots of values already available in the caller context, suggest removing it and inline it into the caller.

511

nullptr ? It does not look correct. It shold be the DirectcallInst.

513

see comment in fixupPHINode method.

526

For Invoke, since the cast is inserted in the original BB (mergeBB) -- i.e., the new NormalDest, it post-dominates the call return values from both predecessors so there seems to be no need for phi insertion -- unless you split the another new BB between DirectBB and MergeBB.

[xur]

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

412

Note the condition "if (DirectCallBB)"
I only change the phi operand points to DirectcallBB when it's not a nullptr.

For normalDest, the DirectcallBB is set to nullptr in the caller.
This also answers your question about the call's nullptr argument.

511

see the reply in fixupPHINode.

513

see the reply in the fixupPHINode.

526

The phi is not inserted in the mergeBB. It's in the BB the joins mergeBB and original NormalDest. We now have one return value from the original indirect invoke and one from new direct invoke. A phi is needed in the join point.

[xur]

another comments

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

428

do you mean V is defined in IndirectCallBB and dominates BB?

we are in the middle of CFG transformation and dominate tree might not be valid.
Is there a cheap way to check?

why do you think we need to check this? this seems to be obvious (unless the phis are corrupted already).

[xur]

Addressed some of the David's most recently comments:
(1) comments change
(2) inline fixupInvokeInst into promote(). After this change, we no longer need the direct-call instruction. So I changed createDirectCallInst() to return the new instruction (either is direct-call or the result-cast).
(3) simplify the test case for the covariant return for call.
(4) add a test case for covariant return for invoke.

[davidxl]

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

388

Document that this is needed for the newly created direct call (invoke) -- as its normal Dst will be fixed up to MergeBB

409

.. in BB (where BB can either be the original NormalDst BB or the unwind BB of the indirect call/invoke instruction).

411

After if-then-else splitting, if BB is the unwindBB, OrigBB will no longer be the pre...

If BB is the Original NormalDstBB, a new incoming edge will be added to the original NormalDstBB from the IndirectCallBB.

414

I suggest split this method into two fixPHINodesForNormDest and fixPHINodesForUnwind -- for better readability.

459

Document parameters. For instance, for mergeBB, document that it is the mergeBB (bottom BB of the if-then-else-diamond) after indirect call promotion. For Invoke instruction, the edges from directBB and IndirectBB to mergedBB are removed before this call (during createIfThenElse).

Also document the CFG effect of this method: after the call, the direct invokes normal destination will be redirected to MergeBB.

463

NormalDest --> MergeBB

474

Add a comment lie:

direct Invoke's normal destinaion is fixed up to mergeBB. MergeBB is the place where return cast is inserted. Also since indirectCallBB does not have an edge to MergeBB, there is no need to insert new PHIs into MergeBB.

[xur]

Integrated David's most recently review comments.

Thanks,

-Rong

[davidxl]

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

416

Document 'Inst'. Also looks like Inst is not used in the body.

425

Is this condition possible?

429

What is the phi arg value for this new incoming block?

434

invoke --> invoke (indirect)

437

Add this description: the OrigBB is still an incoming block for NormalDstBB, but the phi incoming value from this block becomes the new value NewInst

448

Is IX == -1 possible?

[xur]

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

416

you are right. Inst parameter is only used to check the invoke return value. I assume the UnwindDest will not have a phi using the return value.

I'll remove Inst from the parameter list.

425

why not? The operand can come from a basic block other than OrigBB:
like bb1 (def v_1) --> bb2(invoke) --> bb

bb2(def v_2) --> bb

bb can have a phi(v_1, v_2) in bb.
The incoming block for the phi with ix 0 is bb1, rather bb2, right?

429

it's the same value as the one from OriginBB: in the two statements, the first only dup the value, and second one rest the incoming bb to DirectCallBB.

448

see earlier reply.

[davidxl]

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

425

Sorry -- I misread it :) WHat I meant is that the loop should have an assert that OrigBB is found in one of the iterations

429

IF the value was the value from the original indirect call, should the new value become the result of the direct call?

[xur]

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

425

It might not have a PHI that have OrigBB has the incoming BB, right?

429

We have the special handling of the return value PHI. This only applies to the NormalDest.

I assume UnwindBB won't use the return value. Let me know my assumption is incorrect.

This code handle the phi other than the return value PHI.

[davidxl]

LGTM

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

429

This assumption is probably correct -- in case of exception, the return value is not properly defined.

include/llvm/InitializePasses.h

 void initializeDominatorTreeWrapperPassPass(PassRegistry&);
 void initializeEarlyIfConverterPass(PassRegistry&);
 void initializeEdgeBundlesPass(PassRegistry&);
 void initializeExpandPostRAPass(PassRegistry&);
 void initializeAAResultsWrapperPassPass(PassRegistry &);
 void initializeGCOVProfilerPass(PassRegistry&);
 void initializePGOInstrumentationGenPass(PassRegistry&);
 void initializePGOInstrumentationUsePass(PassRegistry&);
+void initializePGOIndirectCallPromotionPass(PassRegistry&);
 void initializeInstrProfilingLegacyPassPass(PassRegistry &);
 void initializeAddressSanitizerPass(PassRegistry&);
 void initializeAddressSanitizerModulePass(PassRegistry&);
 void initializeMemorySanitizerPass(PassRegistry&);
 void initializeThreadSanitizerPass(PassRegistry&);
 void initializeSanitizerCoverageModulePass(PassRegistry&);
 void initializeDataFlowSanitizerPass(PassRegistry&);
 void initializeEfficiencySanitizerPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createDivergenceAnalysisPass();
       (void) llvm::createDomOnlyPrinterPass();
       (void) llvm::createDomPrinterPass();
       (void) llvm::createDomOnlyViewerPass();
       (void) llvm::createDomViewerPass();
       (void) llvm::createGCOVProfilerPass();
       (void) llvm::createPGOInstrumentationGenPass();
       (void) llvm::createPGOInstrumentationUsePass();
+      (void) llvm::createPGOIndirectCallPromotionPass();
       (void) llvm::createInstrProfilingLegacyPass();
       (void) llvm::createFunctionImportPass();
       (void) llvm::createFunctionInliningPass();
       (void) llvm::createAlwaysInlinerPass();
       (void) llvm::createGlobalDCEPass();
       (void) llvm::createGlobalOptimizerPass();
       (void) llvm::createGlobalsAAWrapperPass();
       (void) llvm::createIPConstantPropagationPass();

include/llvm/Transforms/Instrumentation.h

 };
 ModulePass *createGCOVProfilerPass(const GCOVOptions &Options =
                                    GCOVOptions::getDefault());
 
 // PGO Instrumention
 ModulePass *createPGOInstrumentationGenPass();
 ModulePass *
 createPGOInstrumentationUsePass(StringRef Filename = StringRef(""));
+ModulePass *createPGOIndirectCallPromotionPass(bool InLTO = false);
 
 /// Options for the frontend instrumentation based profiling pass.
 struct InstrProfOptions {
   InstrProfOptions() : NoRedZone(false) {}
 
   // Add the 'noredzone' attribute to added runtime library calls.
   bool NoRedZone;
 

lib/Transforms/IPO/PassManagerBuilder.cpp

if (!PGOInstrGen.empty()) {
     InstrProfOptions Options;
     Options.InstrProfileOutput = PGOInstrGen;
     MPM.add(createInstrProfilingLegacyPass(Options));
   }
   if (!PGOInstrUse.empty())
     MPM.add(createPGOInstrumentationUsePass(PGOInstrUse));
 }
 void PassManagerBuilder::addFunctionSimplificationPasses(
     legacy::PassManagerBase &MPM) {
   // Start of function pass.
   // Break up aggregate allocas, using SSAUpdater.
   if (UseNewSROA)
     MPM.add(createSROAPass());
   else
     MPM.add(createScalarReplAggregatesPass(-1, false));
   MPM.add(createEarlyCSEPass());              // Catch trivial redundancies
   // Speculative execution if the target has divergent branches; otherwise nop.
if (!DisableUnitAtATime) {
 
     MPM.add(createDeadArgEliminationPass()); // Dead argument elimination
 
     addInstructionCombiningPass(MPM); // Clean up after IPCP & DAE
     addExtensionsToPM(EP_Peephole, MPM);
     MPM.add(createCFGSimplificationPass()); // Clean up after IPCP & DAE
   }
 
-  if (!PerformThinLTO)
+  if (!PerformThinLTO) {
     /// PGO instrumentation is added during the compile phase for ThinLTO, do
     /// not run it a second time
     addPGOInstrPasses(MPM);
+    // Indirect call promotion that promotes intra-module targets only.
+    MPM.add(createPGOIndirectCallPromotionPass());
+  }
 
   if (EnableNonLTOGlobalsModRef)
     // We add a module alias analysis pass here. In part due to bugs in the
     // analysis infrastructure this "works" in that the analysis stays alive
     // for the entire SCC pass run below.
     MPM.add(createGlobalsAAWrapperPass());
 
   // Start of CallGraph SCC passes.
if (ModuleSummary)
     PM.add(createFunctionImportPass(ModuleSummary));
 
   // Allow forcing function attributes as a debugging and tuning aid.
   PM.add(createForceFunctionAttrsLegacyPass());
 
   // Infer attributes about declarations if possible.
   PM.add(createInferFunctionAttrsLegacyPass());
 
+  // Indirect call promotion. This should promote all the targets that are left
+  // by the earlier promotion pass that promotes intra-module targets.
+  // This two-step promotion is to save the compile time. For LTO, it should
+  // produce the same result as if we only do promotion here.
+  PM.add(createPGOIndirectCallPromotionPass(true));
+
   // Propagate constants at call sites into the functions they call.  This
   // opens opportunities for globalopt (and inlining) by substituting function
   // pointers passed as arguments to direct uses of functions.
   PM.add(createIPSCCPPass());
 
   // Now that we internalized some globals, see if we can hack on them!
   PM.add(createPostOrderFunctionAttrsLegacyPass());
   PM.add(createReversePostOrderFunctionAttrsPass());

lib/Transforms/Instrumentation/CMakeLists.txt

 add_llvm_library(LLVMInstrumentation
   AddressSanitizer.cpp
   BoundsChecking.cpp
   DataFlowSanitizer.cpp
   GCOVProfiling.cpp
   MemorySanitizer.cpp
+  IndirectCallPromotion.cpp
   Instrumentation.cpp
   InstrProfiling.cpp
   PGOInstrumentation.cpp
   SanitizerCoverage.cpp
   ThreadSanitizer.cpp
   EfficiencySanitizer.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
   )
 
 add_dependencies(LLVMInstrumentation intrinsics_gen)

lib/Transforms/Instrumentation/IndirectCallPromotion.cpp

+//===-- IndirectCallPromotion.cpp - Promote indirect calls to direct calls ===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the transformation that promotes indirect calls to
+// conditional direct calls when the indirect-call value profile metadata is
+// available.
+//
+//===----------------------------------------------------------------------===//
+
+#include "IndirectCallSiteVisitor.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/Statistic.h"
+#include "llvm/ADT/Triple.h"
+#include "llvm/Analysis/CFG.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/InstVisitor.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/MDBuilder.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/ProfileData/InstrProfReader.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Instrumentation.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include <string>
+#include <utility>
+#include <vector>
+
+using namespace llvm;
+
+#define DEBUG_TYPE "icall-promotion"
+
+STATISTIC(NumOfPGOICallPromotion, "Number of indirect call promotions.");
+STATISTIC(NumOfPGOICallsites, "Number of indirect call candidate sites.");
+
+// Command line option to disable indirect-call promotion with the default as
+// false. This is for debug purpose.
+static cl::opt<bool> DisableICP("disable-icp", cl::init(false), cl::Hidden,
+                                cl::desc("Disable indirect call promotion"));
+
+// The minimum call count for the direct-call target to be considered as the
+// promotion candidate.
+static cl::opt<unsigned>
+    ICPCountThreshold("icp-count-threshold", cl::Hidden, cl::ZeroOrMore,
+                      cl::init(1000),
+                      cl::desc("The minimum count to the direct call target "
+                               "for the promotion"));
+
+// The percent threshold for the direct-call target (this call site vs the
+// total call count) for it to be considered as the promotion target.
+static cl::opt<unsigned>
+    ICPPercentThreshold("icp-percent-threshold", cl::init(33), cl::Hidden,
+                        cl::ZeroOrMore,
+                        cl::desc("The percentage threshold for the promotion"));
+
+// Set the maximum number of targets to promote for a single indirect-call
+// callsite.
+static cl::opt<unsigned>
+    MaxNumPromotions("icp-max-prom", cl::init(2), cl::Hidden, cl::ZeroOrMore,
+                     cl::desc("Max number of promotions for a single indirect "
+                              "call callsite"));
+
+// Set the cutoff value for the promotion. If the value is other than 0, we
+// stop the transformation once the total number of promotions equals the cutoff
+// value.
+// For debug use only.
+static cl::opt<unsigned>
+    ICPCutOff("icp-cutoff", cl::init(0), cl::Hidden, cl::ZeroOrMore,
+              cl::desc("Max number of promotions for this compilaiton"));
+
+// If ICPCSSkip is non zero, the first ICPCSSkip callsites will be skipped.
+// For debug use only.
+static cl::opt<unsigned>
+    ICPCSSkip("icp-csskip", cl::init(0), cl::Hidden, cl::ZeroOrMore,
+              cl::desc("Skip Callsite up to this number for this compilaiton"));
+
+// Set if the pass is called in LTO optimization. The difference for LTO mode
+// is the pass won't prefix the source module name to the internal linkage
+// symbols.
+static cl::opt<bool> ICPLTOMode("icp-lto", cl::init(false), cl::Hidden,
+                                cl::desc("Run indirect-call promotion in LTO "
+                                         "mode"));
+// If the option is set to true, only call instructions will be considered for
+// transformation -- invoke instructions will be ignored.
+static cl::opt<bool>
+    ICPCallOnly("icp-call-only", cl::init(false), cl::Hidden,
+                cl::desc("Run indirect-call promotion for call instructions "
+                         "only"));
+
+// If the option is set to true, only invoke instructions will be considered for
+// transformation -- call instructions will be ignored.
+static cl::opt<bool> ICPInvokeOnly("icp-invoke-only", cl::init(false),
+                                   cl::Hidden,
+                                   cl::desc("Run indirect-call promotion for "
+                                            "invoke instruction only"));
+
+// Dump the function level IR if the transformation happened in this
+// function. For debug use only.
+static cl::opt<bool>
+    ICPDUMPAFTER("icp-dumpafter", cl::init(false), cl::Hidden,
+                 cl::desc("Dump IR after transformation happens"));
+
+namespace {
+class PGOIndirectCallPromotion : public ModulePass {
+public:
+  static char ID;
+
+  PGOIndirectCallPromotion(bool InLTO = false) : ModulePass(ID), InLTO(InLTO) {
+    initializePGOIndirectCallPromotionPass(*PassRegistry::getPassRegistry());
+  }
+
+  const char *getPassName() const override {
+    return "PGOIndirectCallPromotion";
+  }
+
+private:
+  bool runOnModule(Module &M) override;
+
+  // If this pass is called in LTO. We need to special handling the PGOFuncName
+  // for the static variables due to LTO's internalization.
+  bool InLTO;
+};
+} // end anonymous namespace
+
+char PGOIndirectCallPromotion::ID = 0;
+INITIALIZE_PASS(PGOIndirectCallPromotion, "pgo-icall-prom",
+                "Use PGO instrumentation profile to promote indirect calls to "
+                "direct calls.",
+                false, false)
+
+ModulePass *llvm::createPGOIndirectCallPromotionPass(bool InLTO) {
+  return new PGOIndirectCallPromotion(InLTO);
+}
+
+// The class for main data structure to promote indirect calls to conditional
+// direct calls.
+class ICallPromotionFunc {
+private:
+  Function &F;
+  Module *M;
+
+  // Symtab that maps indirect call profile values to function names and
+  // defines.
+  InstrProfSymtab *Symtab;
+
+  // Allocate space to read the profile annotation.
+  std::unique_ptr<InstrProfValueData[]> ValueDataArray;
+
+  // Count is the call count for the direct-call target and
+  // TotalCount is the call count for the indirect-call callsite.
+  // Return true we should promote this indirect-call target.
+  bool isPromotionProfitable(uint64_t Count, uint64_t TotalCount);
+
+  enum TargetStatus {
+    OK,                   // Should be able to promote.
+    NotAvailableInModule, // Cannot find the target in current module.
+    ReturnTypeMismatch,   // Return type mismatch b/w target and indirect-call.
+    NumArgsMismatch,      // Number of arguments does not match.
+    ArgTypeMismatch       // Type mismatch in the arguments (cannot bitcast).
+  };
+
+  // Test if we can legally promote this direct-call of Target.
+  TargetStatus isPromotionLegal(Instruction *Inst, uint64_t Target,
+                                Function *&F);
+
+  // A struct that records the direct target and it's call count.
+  struct PromotionCandidate {
+    Function *TargetFunction;
+    uint64_t Count;
+    PromotionCandidate(Function *F, uint64_t C) : TargetFunction(F), Count(C) {}
+  };
+
+  // Check if the indirect-call call site should be promoted. Return the number
+  // of promotions.
+  std::vector<PromotionCandidate> getPromotionCandidatesForCallSite(
+      Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
+      uint64_t TotalCount);
+
+  // Main function that transforms Inst (either a indirect-call instruction, or
+  // an invoke instruction , to a conditional call to F. This is like:
+  //     if (Inst.CalledValue == F)
+  //        F(...);
+  //     else
+  //        Inst(...);
+  //     end
+  // TotalCount is the profile count value that the instruction executes.
+  // Count is the profile count value that F is the target function.
+  // These two values are being used to update the branch weight.
+  void promote(Instruction *Inst, Function *F, uint64_t Count,
+               uint64_t TotalCount);
+
+  // Promote a list of targets for one indirect-call callsite. Return
+  // the number of promotions.
+  uint32_t tryToPromote(Instruction *Inst,
+                        const std::vector<PromotionCandidate> &Candidates,
+                        uint64_t &TotalCount);
+
+  static const char *StatusToString(const TargetStatus S) {
+    switch (S) {
+    case OK:
+      return "OK to promote";
+    case NotAvailableInModule:
+      return "Cannot find the target";
+    case ReturnTypeMismatch:
+      return "Return type mismatch";
+    case NumArgsMismatch:
+      return "The number of arguments mismatch";
+    case ArgTypeMismatch:
+      return "Argument Type mismatch";
+    }
+    llvm_unreachable("Should not reach here");
+  }
+
+  // Noncopyable
+  ICallPromotionFunc(const ICallPromotionFunc &other) = delete;
+  ICallPromotionFunc &operator=(const ICallPromotionFunc &other) = delete;
+
+public:
+  ICallPromotionFunc(Function &Func, Module *Modu, InstrProfSymtab *Symtab)
+      : F(Func), M(Modu), Symtab(Symtab) {
+    ValueDataArray = llvm::make_unique<InstrProfValueData[]>(MaxNumPromotions);
+  }
+  bool processFunction();
+};
+
+bool ICallPromotionFunc::isPromotionProfitable(uint64_t Count,
+                                               uint64_t TotalCount) {
+  if (Count < ICPCountThreshold)
+    return false;
+
+  unsigned Percentage = (Count * 100) / TotalCount;
+  return (Percentage >= ICPPercentThreshold);
+}
+
+ICallPromotionFunc::TargetStatus
+ICallPromotionFunc::isPromotionLegal(Instruction *Inst, uint64_t Target,
+                                     Function *&TargetFunction) {
+  Function *DirectCallee = Symtab->getFunction(Target);
+  if (DirectCallee == nullptr)
+    return NotAvailableInModule;
+  // Check the return type.
+  Type *CallRetType = Inst->getType();
+  if (!CallRetType->isVoidTy()) {
+    Type *FuncRetType = DirectCallee->getReturnType();
+    if (FuncRetType != CallRetType &&
+        !CastInst::isBitCastable(FuncRetType, CallRetType))
+      return ReturnTypeMismatch;
+  }
+
+  // Check if the arguments are compatible with the parameters
+  FunctionType *DirectCalleeType = DirectCallee->getFunctionType();
+  unsigned ParamNum = DirectCalleeType->getFunctionNumParams();
+  CallSite CS(Inst);
+  unsigned ArgNum = CS.arg_size();
+
+  if (ParamNum != ArgNum && !DirectCalleeType->isVarArg())
+    return NumArgsMismatch;
+
+  for (unsigned I = 0; I < ParamNum; ++I) {
+    Type *PTy = DirectCalleeType->getFunctionParamType(I);
+    Type *ATy = CS.getArgument(I)->getType();
+    if (PTy == ATy)
+      continue;
+    if (!CastInst::castIsValid(Instruction::BitCast, CS.getArgument(I), PTy))
+      return ArgTypeMismatch;
+  }
+
+  DEBUG(dbgs() << " #" << NumOfPGOICallPromotion << " Promote the icall to "
+               << Symtab->getFuncName(Target) << "\n");
+  TargetFunction = DirectCallee;
+  return OK;
+}
+
+// Indirect-call promotion heuristic. The direct targets are sorted based on
+// the count. Stop at the first target that is not promoted.
+std::vector<ICallPromotionFunc::PromotionCandidate>
+ICallPromotionFunc::getPromotionCandidatesForCallSite(
+    Instruction *Inst, const ArrayRef<InstrProfValueData> &ValueDataRef,
+    uint64_t TotalCount) {
+  uint32_t NumVals = ValueDataRef.size();
+  std::vector<PromotionCandidate> Ret;
+
+  DEBUG(dbgs() << " \nWork on callsite #" << NumOfPGOICallsites << *Inst
+               << " Num_targets: " << NumVals << "\n");
+  NumOfPGOICallsites++;
+  if (ICPCSSkip != 0 && NumOfPGOICallsites <= ICPCSSkip) {
+    DEBUG(dbgs() << " Skip: User options.\n");
+    return Ret;
+  }
+
+  for (uint32_t I = 0; I < MaxNumPromotions && I < NumVals; I++) {
+    uint64_t Count = ValueDataRef[I].Count;
+    assert(Count <= TotalCount);
+    uint64_t Target = ValueDataRef[I].Value;
+    DEBUG(dbgs() << " Candidate " << I << " Count=" << Count
+                 << "  Target_func: " << Target << "\n");
+
+    if (ICPInvokeOnly && dyn_cast<CallInst>(Inst)) {
+      DEBUG(dbgs() << " Not promote: User options.\n");
+      break;
+    }
+    if (ICPCallOnly && dyn_cast<InvokeInst>(Inst)) {
+      DEBUG(dbgs() << " Not promote: User option.\n");
+      break;
+    }
+    if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
+      DEBUG(dbgs() << " Not promote: Cutoff reached.\n");
+      break;
+    }
+    if (!isPromotionProfitable(Count, TotalCount)) {
+      DEBUG(dbgs() << " Not promote: Cold target.\n");
+      break;
+    }
+    Function *TargetFunction = nullptr;
+    TargetStatus Status = isPromotionLegal(Inst, Target, TargetFunction);
+    if (Status != OK) {
+      StringRef TargetFuncName = Symtab->getFuncName(Target);
+      const char *Reason = StatusToString(Status);
+      DEBUG(dbgs() << " Not promote: " << Reason << "\n");
+      Twine Msg =
+          Twine("Cannot promote indirect call to ") +
+          (TargetFuncName.empty() ? Twine(Target) : Twine(TargetFuncName)) +
+          Twine(" with count of ") + Twine(Count) + ": " + Reason;
+      emitOptimizationRemarkMissed(F.getContext(), "PGOIndirectCallPromotion",
+                                   F, Inst->getDebugLoc(), Msg);
+      break;
+    }
+    Ret.push_back(PromotionCandidate(TargetFunction, Count));
+    TotalCount -= Count;
+  }
+  return Ret;
+}
+
+// Create a diamond structure for If_Then_Else. Also update the profile
+// count. Do the fix-up for the invoke instruction.
+static void createIfThenElse(Instruction *Inst, Function *DirectCallee,
+                             uint64_t Count, uint64_t TotalCount,
+                             BasicBlock **DirectCallBB,
+                             BasicBlock **IndirectCallBB,
+                             BasicBlock **MergeBB) {
+  CallSite CS(Inst);
+  Value *OrigCallee = CS.getCalledValue();
+
+  IRBuilder<> BBBuilder(Inst);
+  LLVMContext &Ctx = Inst->getContext();
+  Value *BCI1 =
+      BBBuilder.CreateBitCast(OrigCallee, Type::getInt8PtrTy(Ctx), "");
+  Value *BCI2 =
+      BBBuilder.CreateBitCast(DirectCallee, Type::getInt8PtrTy(Ctx), "");
+  Value *PtrCmp = BBBuilder.CreateICmpEQ(BCI1, BCI2, "");
+
+  uint64_t ElseCount = TotalCount - Count;
+  uint64_t MaxCount = (Count >= ElseCount ? Count : ElseCount);
+  uint64_t Scale = calculateCountScale(MaxCount);
+  MDBuilder MDB(Inst->getContext());
+  MDNode *BranchWeights = MDB.createBranchWeights(
+      scaleBranchCount(Count, Scale), scaleBranchCount(ElseCount, Scale));
+  TerminatorInst *ThenTerm, *ElseTerm;
+  SplitBlockAndInsertIfThenElse(PtrCmp, Inst, &ThenTerm, &ElseTerm,
+                                BranchWeights);
+  *DirectCallBB = ThenTerm->getParent();
+  (*DirectCallBB)->setName("if.true.direct_targ");
+  *IndirectCallBB = ElseTerm->getParent();
+  (*IndirectCallBB)->setName("if.false.orig_indirect");
+  *MergeBB = Inst->getParent();
+  (*MergeBB)->setName("if.end.icp");
+
+  // Special handing of Invoke instructions.
+  InvokeInst *II = dyn_cast<InvokeInst>(Inst);
+  if (!II)
+    return;
+
+  // We don't need branch instructions for invoke.
+  ThenTerm->eraseFromParent();
+  ElseTerm->eraseFromParent();
+
+  // Add jump from Merge BB to the NormalDest.
+  BranchInst::Create(II->getNormalDest(), *MergeBB);
+}
+
+// Find the PHI in BB that have the CallResult as the operand.
+static bool getCallRetPHINode(BasicBlock *BB, Instruction *Inst) {
+  BasicBlock *From = Inst->getParent();
+  for (auto &I : *BB) {
+    PHINode *PHI = dyn_cast<PHINode>(&I);
+    if (!PHI)
+      continue;
+    int IX = PHI->getBasicBlockIndex(From);
+    if (IX == -1)
+      continue;
+    Value *V = PHI->getIncomingValue(IX);
+    if (dyn_cast<Instruction>(V) == Inst)
+      return true;
+  }
+  return false;
+}
+
+// Fix the PHI node in the basic block BB. We have the PHIs from
+// OrigBB and we need to duplicate them for the IndirectCall BB.
+// For CallResult, we cannot duplicated -- need to set the right value.
+static void fixupPHINode(Instruction *Inst, Instruction *NewInst,
+                         BasicBlock *BB, BasicBlock *OrigBB,
+                         BasicBlock *IndirectCallBB, BasicBlock *DirectCallBB) {
+  for (auto &I : *BB) {
+    PHINode *PHI = dyn_cast<PHINode>(&I);
+    if (!PHI)
+      continue;
+    int IX = PHI->getBasicBlockIndex(OrigBB);
+    if (IX == -1)
+      continue;
+    Value *V = PHI->getIncomingValue(IX);
+    if (dyn_cast<Instruction>(V) == Inst) {
+      PHI->setIncomingBlock(IX, IndirectCallBB);
+      PHI->addIncoming(NewInst, OrigBB);
+      continue;
+    }
+
+    PHI->addIncoming(V, IndirectCallBB);
+    if (DirectCallBB)
+      PHI->setIncomingBlock(IX, DirectCallBB);
+  }
+}
+
+// Add a bitcast instruction to the direct-call return value if needed.
+static Instruction *insertCallRetCast(const Instruction *Inst,
+                                      Instruction *DirectCallInst,
+                                      Function *DirectCallee) {
+  if (Inst->getType()->isVoidTy())
+    return DirectCallInst;
+
+  Type *CallRetType = Inst->getType();
+  Type *FuncRetType = DirectCallee->getReturnType();
+  if (FuncRetType == CallRetType)
+    return DirectCallInst;
+
+  BasicBlock *InsertionBB;
+  if (CallInst *CI = dyn_cast<CallInst>(DirectCallInst))
+    InsertionBB = CI->getParent();
+  else
+    InsertionBB = (dyn_cast<InvokeInst>(DirectCallInst))->getNormalDest();
+
+  return (new BitCastInst(DirectCallInst, CallRetType, "",
+                          InsertionBB->getTerminator()));
+}
+
+// Create a DirectCall instruction in the DirectCallBB.
+static Instruction *createDirectCallInst(const Instruction *Inst,
+                                         Function *DirectCallee,
+                                         BasicBlock *DirectCallBB,
+                                         BasicBlock *NormalDest,
+                                         Instruction *&DirectCallResult) {
+  Instruction *NewInst = Inst->clone();
+  if (CallInst *CI = dyn_cast<CallInst>(NewInst)) {
+    CI->setCalledFunction(DirectCallee);
+    CI->mutateFunctionType(DirectCallee->getFunctionType());
+  } else {
+    // Must be an invoke instruction.
+    InvokeInst *II = dyn_cast<InvokeInst>(NewInst);
+    assert(II);
+    II->setCalledFunction(DirectCallee);
+    II->mutateFunctionType(DirectCallee->getFunctionType());
+    II->setNormalDest(NormalDest);
+  }
+
+  DirectCallBB->getInstList().insert(DirectCallBB->getFirstInsertionPt(),
+                                     NewInst);
+
+  // Clean the value profile data.
+  NewInst->setMetadata(LLVMContext::MD_prof, 0);
+  CallSite NewCS(NewInst);
+  FunctionType *DirectCalleeType = DirectCallee->getFunctionType();
+  unsigned ParamNum = DirectCalleeType->getFunctionNumParams();
+  for (unsigned I = 0; I < ParamNum; ++I) {
+    Type *ATy = NewCS.getArgument(I)->getType();
+    Type *PTy = DirectCalleeType->getParamType(I);
+    if (ATy != PTy) {
+      BitCastInst *BI = new BitCastInst(NewCS.getArgument(I), PTy, "", NewInst);
+      NewCS.setArgument(I, BI);
+    }
+  }
+
+  /*Instruction *DirectCallResult = */
+  DirectCallResult = insertCallRetCast(Inst, NewInst, DirectCallee);
+  return NewInst;
+}
+
+// After creating IF_Then_Else, the PHIs for NormalDest and UnwindDest point to
+// the mergeBB (which is the new NormalDest for direct-call. We need to
+// duplicate the PHIs for the indirect call BB. Note that we need to
+// DirectCallResult (could be a cast) to update the NormalDest BB.  And we
+// don't need to DirectCallBB for updating the PHIs for NormalDest.
+static void fixupInvokeInst(Instruction *Inst, Instruction *DirectCallInst,
+                            Instruction *DirectCallResult) {
+  InvokeInst *II = dyn_cast<InvokeInst>(Inst);
+  if (!II)
+    return;
+
+  BasicBlock *IndirectCallBB = Inst->getParent();
+  BasicBlock *DirectCallBB = DirectCallInst->getParent();
+  BasicBlock *MergeBB = dyn_cast<InvokeInst>(DirectCallInst)->getNormalDest();
+  fixupPHINode(Inst, nullptr, II->getUnwindDest(), MergeBB, IndirectCallBB,
+               DirectCallBB);
+  fixupPHINode(Inst, DirectCallResult, II->getNormalDest(), MergeBB,
+               IndirectCallBB, nullptr);
+}
+
+// Create a PHI to unify the return values of calls.
+static void insertCallRetPHI(Instruction *Inst, Instruction *CallResult,
+                             Function *DirectCallee) {
+  if (Inst->getType()->isVoidTy())
+    return;
+
+  BasicBlock *RetValBB = CallResult->getParent();
+
+  BasicBlock *PHIBB;
+  if (InvokeInst *II = dyn_cast<InvokeInst>(CallResult))
+    RetValBB = II->getNormalDest();
+
+  PHIBB = RetValBB->getSingleSuccessor();
+  if (getCallRetPHINode(PHIBB, Inst))
+    return;
+
+  PHINode *CallRetPHI = PHINode::Create(Inst->getType(), 0);
+  PHIBB->getInstList().push_front(CallRetPHI);
+  Inst->replaceAllUsesWith(CallRetPHI);
+  CallRetPHI->addIncoming(Inst, Inst->getParent());
+  CallRetPHI->addIncoming(CallResult, RetValBB);
+}
+
+// This function does the actual indirect-call promotion transformation:
+// For an indirect-call like:
+//     Ret = (*Foo)(Args);
+// It transforms to:
+//     if (Foo == DirectCallee)
+//        Ret1 = DirectCallee(Args);
+//     else
+//        Ret2 = (*Foo)(Args);
+//     Ret = phi(Ret1, Ret2);
+// It adds type casts for the args do not match the parameters and the return
+// value. Branch weights metadata also updated.
+//
+void ICallPromotionFunc::promote(Instruction *Inst, Function *DirectCallee,
+                                 uint64_t Count, uint64_t TotalCount) {
+  assert(DirectCallee != nullptr);
+  BasicBlock *BB = Inst->getParent();
+  // Just to suppress the non-debug build warning.
+  (void)BB;
+  DEBUG(dbgs() << "\n\n== Basic Block Before ==\n");
+  DEBUG(dbgs() << *BB << "\n");
+
+  BasicBlock *DirectCallBB, *IndirectCallBB, *MergeBB;
+  createIfThenElse(Inst, DirectCallee, Count, TotalCount, &DirectCallBB,
+                   &IndirectCallBB, &MergeBB);
+
+  Instruction *DirectCallResult;
+  Instruction *NewInst = createDirectCallInst(Inst, DirectCallee, DirectCallBB,
+                                              MergeBB, DirectCallResult);
+
+  // Move Inst from MergeBB to IndirectCallBB.
+  Inst->removeFromParent();
+  IndirectCallBB->getInstList().insert(IndirectCallBB->getFirstInsertionPt(),
+                                       Inst);
+  fixupInvokeInst(Inst, NewInst, DirectCallResult);
+  insertCallRetPHI(Inst, DirectCallResult, DirectCallee);
+
+  DEBUG(dbgs() << "\n== Basic Blocks After ==\n");
+  DEBUG(dbgs() << *BB << *DirectCallBB << *IndirectCallBB << *MergeBB << "\n");
+
+  Twine Msg = Twine("Promote indirect call to ") + DirectCallee->getName() +
+              " with count " + Twine(Count) + " out of " + Twine(TotalCount);
+  emitOptimizationRemark(F.getContext(), "PGOIndirectCallPromotion", F,
+                         Inst->getDebugLoc(), Msg);
+}
+
+// Promote indirect-call to conditional direct-call for one callsite.
+uint32_t ICallPromotionFunc::tryToPromote(
+    Instruction *Inst, const std::vector<PromotionCandidate> &Candidates,
+    uint64_t &TotalCount) {
+  uint32_t NumPromoted = 0;
+
+  for (auto &C : Candidates) {
+    uint64_t Count = C.Count;
+    promote(Inst, C.TargetFunction, Count, TotalCount);
+    assert(TotalCount >= Count);
+    TotalCount -= Count;
+    NumOfPGOICallPromotion++;
+    NumPromoted++;
+  }
+  return NumPromoted;
+}
+
+// Traverse all the indirect-call callsite and get the value profile
+// annotation to perform indirect-call promotion.
+bool ICallPromotionFunc::processFunction() {
+  bool Changed = false;
+  for (auto &I : findIndirectCallSites(F)) {
+    uint32_t NumVals;
+    uint64_t TotalCount;
+    bool Res =
+        getValueProfDataFromInst(*I, IPVK_IndirectCallTarget, MaxNumPromotions,
+                                 ValueDataArray.get(), NumVals, TotalCount);
+    if (!Res)
+      continue;
+    ArrayRef<InstrProfValueData> ValueDataArrayRef(ValueDataArray.get(),
+                                                   NumVals);
+    auto PromotionCandidates =
+        getPromotionCandidatesForCallSite(I, ValueDataArrayRef, TotalCount);
+    uint32_t NumPromoted = tryToPromote(I, PromotionCandidates, TotalCount);
+    if (NumPromoted == 0)
+      continue;
+
+    Changed = true;
+    // Adjust the MD.prof metadata. First delete the old one.
+    I->setMetadata(LLVMContext::MD_prof, 0);
+    // If all promoted, we don't need the MD.prof metadata.
+    if (TotalCount == 0 || NumPromoted == NumVals)
+      continue;
+    // Otherwise we need update with the un-promoted records back.
+    annotateValueSite(*M, *I, ValueDataArrayRef.slice(NumPromoted), TotalCount,
+                      IPVK_IndirectCallTarget, MaxNumPromotions);
+  }
+  return Changed;
+}
+
+// A wrapper function that does the actual work.
+static bool promoteIndirectCalls(Module &M, bool InLTO) {
+  if (DisableICP)
+    return false;
+  InstrProfSymtab Symtab;
+  Symtab.create(M, InLTO);
+  bool Changed = false;
+  for (auto &F : M) {
+    if (F.isDeclaration())
+      continue;
+    if (F.hasFnAttribute(Attribute::OptimizeNone))
+      continue;
+    ICallPromotionFunc ICallPromotion(F, &M, &Symtab);
+    bool FuncChanged = ICallPromotion.processFunction();
+    if (ICPDUMPAFTER && FuncChanged) {
+      DEBUG(dbgs() << "\n== IR Dump After =="; F.print(dbgs()));
+      DEBUG(dbgs() << "\n");
+    }
+    Changed |= FuncChanged;
+    if (ICPCutOff != 0 && NumOfPGOICallPromotion >= ICPCutOff) {
+      DEBUG(dbgs() << " Stop: Cutoff reached.\n");
+      break;
+    }
+  }
+  return Changed;
+}
+
+bool PGOIndirectCallPromotion::runOnModule(Module &M) {
+  // Command-line option has the priority for InLTO.
+  InLTO |= ICPLTOMode;
+  return promoteIndirectCalls(M, InLTO);
+}

lib/Transforms/Instrumentation/Instrumentation.cpp

 /// library.
 void llvm::initializeInstrumentation(PassRegistry &Registry) {
   initializeAddressSanitizerPass(Registry);
   initializeAddressSanitizerModulePass(Registry);
   initializeBoundsCheckingPass(Registry);
   initializeGCOVProfilerPass(Registry);
   initializePGOInstrumentationGenPass(Registry);
   initializePGOInstrumentationUsePass(Registry);
+  initializePGOIndirectCallPromotionPass(Registry);
   initializeInstrProfilingLegacyPassPass(Registry);
   initializeMemorySanitizerPass(Registry);
   initializeThreadSanitizerPass(Registry);
   initializeSanitizerCoverageModulePass(Registry);
   initializeDataFlowSanitizerPass(Registry);
   initializeEfficiencySanitizerPass(Registry);
 }
 
 /// LLVMInitializeInstrumentation - C binding for
 /// initializeInstrumentation.
 void LLVMInitializeInstrumentation(LLVMPassRegistryRef R) {
   initializeInstrumentation(*unwrap(R));
 }

test/Transforms/PGOProfile/icp_covariant_return.ll

+; RUN: opt < %s -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"
+
+%struct.D = type { %struct.B }
+%struct.B = type { i32 (...)** }
+%struct.Base = type { i8 }
+%struct.Derived = type { i8 }
+$_ZN1DC2Ev = comdat any
+$_ZN1BC2Ev = comdat any
+$_ZN1D4funcEv = comdat any
+$_ZN1DD2Ev = comdat any
+$_ZN1DD0Ev = comdat any
+$_ZN1B4funcEv = comdat any
+$_ZN1BD2Ev = comdat any
+$_ZN1BD0Ev = comdat any
+$_ZTV1D = comdat any
+$_ZTS1D = comdat any
+$_ZTS1B = comdat any
+$_ZTI1B = comdat any
+$_ZTI1D = comdat any
+$_ZTV1B = comdat any
+@_ZTV1D = linkonce_odr unnamed_addr constant [5 x i8*] [i8* null, i8* bitcast ({ i8*, i8*, i8* }* @_ZTI1D to i8*), i8* bitcast (%struct.Derived* (%struct.D*)* @_ZN1D4funcEv to i8*), i8* bitcast (void (%struct.D*)* @_ZN1DD2Ev to i8*), i8* bitcast (void (%struct.D*)* @_ZN1DD0Ev to i8*)], comdat, align 8
+@_ZTVN10__cxxabiv120__si_class_type_infoE = external global i8*
+@_ZTS1D = linkonce_odr constant [3 x i8] c"1D\00", comdat
+@_ZTVN10__cxxabiv117__class_type_infoE = external global i8*
+@_ZTS1B = linkonce_odr constant [3 x i8] c"1B\00", comdat
+@_ZTI1B = linkonce_odr constant { i8*, i8* } { i8* bitcast (i8** getelementptr inbounds (i8*, i8** @_ZTVN10__cxxabiv117__class_type_infoE, i64 2) to i8*), i8* getelementptr inbounds ([3 x i8], [3 x i8]* @_ZTS1B, i32 0, i32 0) }, comdat
+@_ZTI1D = linkonce_odr constant { i8*, i8*, i8* } { i8* bitcast (i8** getelementptr inbounds (i8*, i8** @_ZTVN10__cxxabiv120__si_class_type_infoE, i64 2) to i8*), i8* getelementptr inbounds ([3 x i8], [3 x i8]* @_ZTS1D, i32 0, i32 0), i8* bitcast ({ i8*, i8* }* @_ZTI1B to i8*) }, comdat
+@_ZTV1B = linkonce_odr unnamed_addr constant [5 x i8*] [i8* null, i8* bitcast ({ i8*, i8* }* @_ZTI1B to i8*), i8* bitcast (%struct.Base* (%struct.B*)* @_ZN1B4funcEv to i8*), i8* bitcast (void (%struct.B*)* @_ZN1BD2Ev to i8*), i8* bitcast (void (%struct.B*)* @_ZN1BD0Ev to i8*)], comdat, align 8
+
+define i32 @bar() {
+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:  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 
+  %call1 = call %struct.Base* %tmp3(%struct.B* %tmp1), !prof !1
+; ICALL-PROM:if.false.orig_indirect:
+; 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 ]
+  ret i32 0
+}
+
+declare noalias i8* @_Znwm(i64)
+
+define linkonce_odr void @_ZN1DC2Ev(%struct.D* %this) unnamed_addr comdat align 2 {
+entry:
+  %tmp = bitcast %struct.D* %this to %struct.B*
+  call void @_ZN1BC2Ev(%struct.B* %tmp)
+  %tmp1 = bitcast %struct.D* %this to i32 (...)***
+  store i32 (...)** bitcast (i8** getelementptr inbounds ([5 x i8*], [5 x i8*]* @_ZTV1D, i64 0, i64 2) to i32 (...)**), i32 (...)*** %tmp1, align 8
+  ret void
+}
+
+define linkonce_odr void @_ZN1BC2Ev(%struct.B* %this) unnamed_addr comdat align 2 {
+entry:
+  %tmp = bitcast %struct.B* %this to i32 (...)***
+  store i32 (...)** bitcast (i8** getelementptr inbounds ([5 x i8*], [5 x i8*]* @_ZTV1B, i64 0, i64 2) to i32 (...)**), i32 (...)*** %tmp, align 8
+  ret void
+}
+
+define linkonce_odr %struct.Derived* @_ZN1D4funcEv(%struct.D* %this) unnamed_addr comdat align 2 {
+entry:
+  %call = call noalias i8* @_Znwm(i64 1)
+  %tmp = bitcast i8* %call to %struct.Derived*
+  ret %struct.Derived* %tmp
+}
+
+define linkonce_odr void @_ZN1DD2Ev(%struct.D* %this) unnamed_addr comdat align 2 {
+entry:
+  %tmp = bitcast %struct.D* %this to %struct.B*
+  call void @_ZN1BD2Ev(%struct.B* %tmp)
+  ret void
+}
+
+define linkonce_odr void @_ZN1DD0Ev(%struct.D* %this) unnamed_addr comdat align 2 {
+entry:
+  call void @_ZN1DD2Ev(%struct.D* %this)
+  %tmp = bitcast %struct.D* %this to i8*
+  call void @_ZdlPv(i8* %tmp)
+  ret void
+}
+
+define linkonce_odr %struct.Base* @_ZN1B4funcEv(%struct.B* %this) unnamed_addr comdat align 2 {
+entry:
+  %call = call noalias i8* @_Znwm(i64 1)
+  %tmp = bitcast i8* %call to %struct.Base*
+  ret %struct.Base* %tmp
+}
+
+define linkonce_odr void @_ZN1BD2Ev(%struct.B* %this) unnamed_addr comdat align 2 {
+entry:
+  ret void
+}
+
+define linkonce_odr void @_ZN1BD0Ev(%struct.B* %this) unnamed_addr comdat align 2 {
+entry:
+  call void @_ZN1BD2Ev(%struct.B* %this)
+  %tmp = bitcast %struct.B* %this to i8*
+  call void @_ZdlPv(i8* %tmp)
+  ret void
+}
+
+declare void @_ZdlPv(i8*)
+
+!1 = !{!"VP", i32 0, i64 12345, i64 -3913987384944532146, i64 12345}
+; ICALL-PROM: [[BRANCH_WEIGHT]] = !{!"branch_weights", i32 12345, i32 0}

test/Transforms/PGOProfile/icp_invoke.ll

+; RUN: opt < %s -icp-lto -pgo-icall-prom -S -icp-count-threshold=0 | FileCheck %s --check-prefix=ICP
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@foo1 = global void ()* null, align 8
+@foo2 = global i32 ()* null, align 8
+@_ZTIi = external constant i8*
+
+define internal void @_ZL4bar1v() !PGOFuncName !0 {
+entry:
+  ret void
+}
+
+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:  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
+
+; ICP:[[DCALL_NORMAL_DEST_IC1]]:
+; ICP:  br label %try.cont
+
+lpad:
+  %tmp1 = landingpad { i8*, i32 }
+          catch i8* bitcast (i8** @_ZTIi to i8*)
+  %tmp2 = extractvalue { i8*, i32 } %tmp1, 0
+  %tmp3 = extractvalue { i8*, i32 } %tmp1, 1
+  %tmp4 = tail call i32 @llvm.eh.typeid.for(i8* bitcast (i8** @_ZTIi to i8*))
+  %matches = icmp eq i32 %tmp3, %tmp4
+  br i1 %matches, label %catch, label %eh.resume
+
+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:  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:[[FALSE_LABEL_IC2]]:
+  %call = invoke i32 %tmp6()
+          to label %try.cont8 unwind label %lpad1, !prof !3
+
+; ICP:[[DCALL_NORMAL_DEST_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]] ]
+  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
+}
+
+declare i32 @__gxx_personality_v0(...)
+
+declare i32 @llvm.eh.typeid.for(i8*)
+
+declare i8* @__cxa_begin_catch(i8*)
+
+declare void @__cxa_end_catch()
+
+!0 = !{!"invoke.ll:_ZL4bar1v"}
+!1 = !{!"invoke.ll:_ZL4bar2v"}
+!2 = !{!"VP", i32 0, i64 1, i64 -2732222848796217051, i64 1}
+!3 = !{!"VP", i32 0, i64 1, i64 -6116256810522035449, i64 1}
+; ICP-NOT !3 = !{!"VP", i32 0, i64 1, i64 -2732222848796217051, i64 1}
+; ICP-NOT !4 = !{!"VP", i32 0, i64 1, i64 -6116256810522035449, i64 1}
+; ICP: [[BRANCH_WEIGHT]] = !{!"branch_weights", i32 1, i32 0}

test/Transforms/PGOProfile/icp_mismatch_msg.ll

+; RUN: opt < %s -pgo-icall-prom -pass-remarks-missed=PGOIndirectCallPromotion -S 2>& 1 | FileCheck %s
+
+; CHECK: remark: <unknown>:0:0: Cannot promote indirect call to func4 with count of 1234: The number of arguments mismatch
+; CHECK: remark: <unknown>:0:0: Cannot promote indirect call to 11517462787082255043 with count of 2345: Cannot find the target
+; CHECK: remark: <unknown>:0:0: Cannot promote indirect call to func2 with count of 7890: Return type mismatch
+
+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 ()* null, align 8
+@foo2 = common global i32 ()* null, align 8
+@foo3 = common global i32 ()* null, align 8
+
+define i32 @func4(i32 %i) {
+entry:
+  ret i32 %i
+}
+
+define void @func2() {
+entry:
+  ret void
+}
+
+define i32 @bar() {
+entry:
+  %tmp = load i32 ()*, i32 ()** @foo, align 8
+  %call = call i32 %tmp(), !prof !1
+  %tmp2 = load i32 ()*, i32 ()** @foo2, align 8
+  %call1 = call i32 %tmp2(), !prof !2
+  %add = add nsw i32 %call1, %call
+  %tmp3 = load i32 ()*, i32 ()** @foo3, align 8
+  %call2 = call i32 %tmp3(), !prof !3
+  %add2 = add nsw i32 %add, %call2
+  ret i32 %add2
+}
+
+!1 = !{!"VP", i32 0, i64 1801, i64 7651369219802541373, i64 1234, i64 -4377547752858689819, i64 567}
+!2 = !{!"VP", i32 0, i64 3023, i64 -6929281286627296573, i64 2345, i64 -4377547752858689819, i64 678}
+!3 = !{!"VP", i32 0, i64 7890,  i64 -4377547752858689819, i64 7890}

test/Transforms/PGOProfile/icp_vararg.ll

+; RUN: opt < %s -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:  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
+  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:  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

+; RUN: opt < %s -pgo-icall-prom -S | FileCheck %s --check-prefix=ICALL-PROM
+; RUN: opt < %s -pgo-icall-prom -S -pass-remarks=PGOIndirectCallPromotion -icp-count-threshold=0 -icp-percent-threshold=0 -icp-max-prom=4 2>&1 | FileCheck %s --check-prefix=PASS-REMARK
+; PASS-REMARK: remark: <unknown>:0:0: Promote indirect call to func4 with count 1030 out of 1600
+; PASS-REMARK: remark: <unknown>:0:0: Promote indirect call to func2 with count 410 out of 570
+; PASS-REMARK: remark: <unknown>:0:0: Promote indirect call to func3 with count 150 out of 160
+; PASS-REMARK: remark: <unknown>:0:0: Promote indirect call to func1 with count 10 out of 10
+
+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 ()* null, align 8
+
+define i32 @func1() {
+entry:
+  ret i32 0
+}
+
+define i32 @func2() {
+entry:
+  ret i32 1
+}
+
+define i32 @func3() {
+entry:
+  ret i32 2
+}
+
+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:   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:   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]+]]
+  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:   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}