[SimplifyCFG] Merge branch_weights for direct callsites and introduce options to preserve value profile for indirect callsites

[mingmingl]

Summary

• Introduce option to preserve indirect callsites with value profiles, with default value false to keep existing behavior.
  • The planned usage is to turn on this option to true in LTO prelink pipelines in a PGO build.
  • [Why] Before MD_prof metadata is used, two different callsites with MD_prof shouldn't be simplified to one.
• Merge branch_weights on direct callsites.

IR test cases are generated based on two C++ code with manually-annotated !prof metadata

• hoist of indirect call https://gcc.godbolt.org/z/o6G68rn3v
• sink of direct call https://gcc.godbolt.org/z/79E3onono
• C++ comments and test cases have brief comments to explain why/when not preserving is sub-optimal.

[mingmingl]

flag-gate the change and add test cases

[davidxl]

llvm/test/Transforms/SimplifyCFG/preserve-call-metadata-in-hoist.ll

9

Perhaps add "merging meta data will make the profile data less precise and not desirable either".

18

->createptr to match the name used in IR.

21

createptr

llvm/test/Transforms/SimplifyCFG/preserve-call-metadata-in-sink.ll

17

createptr

[mingmingl]

resolve comments.

[mingmingl]

thanks for reviews!

[davidxl]

+Teresa for pipeline changes.

[wenlei]

I guess you do this only for calls and limit it for pre-link because you want to minimize the restriction on optimization, while making post-link inlining operate on accurate call profile?

Code motion is generally destructive for profile quality. Instead of blocking all sinking and hoisting, have you considered trying to update profile for sinking/hoisting when there's no merging, but only block those that involves merging (i.e. head/tail merge) with incompatible profile? I imagine in some cases, allow sinking/hoisting but updating profile properly may help better inlining later.

llvm/test/Transforms/SimplifyCFG/preserve-call-metadata-in-hoist.ll

9

would be good to mention it in code comment and change description as well.

[davidxl]

In D147954#4276299, @wenlei wrote:

I guess you do this only for calls and limit it for pre-link because you want to minimize the restriction on optimization, while making post-link inlining operate on accurate call profile?

Code motion is generally destructive for profile quality. Instead of blocking all sinking and hoisting, have you considered trying to update profile for sinking/hoisting when there's no merging, but only block those that involves merging (i.e. head/tail merge) with incompatible profile? I imagine in some cases, allow sinking/hoisting but updating profile properly may help better inlining later.

This one is mainly for profile based devirtualization. Related to inlining, there is a pre-pass to do the unmerging:

arg = select cond, 1, val
call foo(arg)

>

if (cond) {

call foo(1)

} else

call foo(val)

[mingmingl]

follow up on comments

[mingmingl]

In D147954#4276502, @davidxl wrote:

In D147954#4276299, @wenlei wrote:

I guess you do this only for calls and limit it for pre-link because you want to minimize the restriction on optimization, while making post-link inlining operate on accurate call profile?

Yep this is the plan, but for post-link indirect-call-promotion (which could be subsequently inlined after ICP)

Code motion is generally destructive for profile quality. Instead of blocking all sinking and hoisting, have you considered trying to update profile for sinking/hoisting when there's no merging, but only block those that involves merging (i.e. head/tail merge) with incompatible profile? I imagine in some cases, allow sinking/hoisting but updating profile properly may help better inlining later.

For my understanding, is https://gcc.godbolt.org/z/cMWY9Tqzv an example (based on c++ source with manual !prof) where updating profile would be useful? I think sinking/hoisting would merge instructions but I might miss something.

• In this example, two direct callsites are merged but both branch_weights metadata (!prof 0, !prof 1) are dropped which is sub-optimal. It's likely better in majority of cases by merging two !prof into one and accumulate counters.

Nevertheless, (after thinking about direct callsites above), I modified the implementation (and option names) to look at indirect calls only primarily because 1) the desired behavior upon icall (indicating !prof is value profile as opposed to branch_weights for direct call) is probably clearer and 2) the pattern shows up (as C++ code shows) with polymorphism, and meanwhile added a 'FIXME' to mention the current 'hoisting' is still suboptimal since it dropped branch_weights on two identical direct calls.

I concur it's better to decide on option name once (preserve-call vs preserve-indirect-call) so I'm fine with implementing the sum-of-branch-weight counters or a better alternative in this patch (and name the option back to more general preserve-call... Let me know your thoughts!

This one is mainly for profile based devirtualization. Related to inlining, there is a pre-pass to do the unmerging:

For my information, in which pass does the unmerging happens?

arg = select cond, 1, val
call foo(arg)

>

if (cond) {

call foo(1)

} else

call foo(val)

llvm/test/Transforms/SimplifyCFG/preserve-call-metadata-in-hoist.ll

9

sure, added comments why preserving !prof metadata (and not hoisting/sinking) in cpp files (indent existing comments accordingly).

[mingmingl]

In D147954#4276616, @mingmingl wrote:

In D147954#4276502, @davidxl wrote:

In D147954#4276299, @wenlei wrote:

I guess you do this only for calls and limit it for pre-link because you want to minimize the restriction on optimization, while making post-link inlining operate on accurate call profile?

Yep this is the plan, but for post-link indirect-call-promotion (which could be subsequently inlined after ICP)

Code motion is generally destructive for profile quality. Instead of blocking all sinking and hoisting, have you considered trying to update profile for sinking/hoisting when there's no merging, but only block those that involves merging (i.e. head/tail merge) with incompatible profile? I imagine in some cases, allow sinking/hoisting but updating profile properly may help better inlining later.

For my understanding, is https://gcc.godbolt.org/z/cMWY9Tqzv an example (based on c++ source with manual !prof) where updating profile would be useful? I think sinking/hoisting would merge instructions but I might miss something.

• In this example, two direct callsites are merged but both branch_weights metadata (!prof 0, !prof 1) are dropped which is sub-optimal. It's likely better in majority of cases by merging two !prof into one and accumulate counters.

Nevertheless, (after thinking about direct callsites above), I modified the implementation (and option names) to look at indirect calls only primarily because 1) the desired behavior upon icall (indicating !prof is value profile as opposed to branch_weights for direct call) is probably clearer and 2) the pattern shows up (as C++ code shows) with polymorphism, and meanwhile added a 'FIXME' to mention the current 'hoisting' is still suboptimal since it dropped branch_weights on two identical direct calls.

I concur it's better to decide on option name once (preserve-call vs preserve-indirect-call) so I'm fine with implementing the sum-of-branch-weight counters or a better alternative in this patch (and name the option back to more general preserve-call... Let me know your thoughts!

My original thought is,

• given that SimplifyCFG runs multiple times, one simpler way is to conservatively prevent premature hoisting/sinking for both direct calls and indirect-calls in early stage of the pipeline and preserve the !prof (no need to sum counters for branch_weight of direct callsites), let passes that use !prof sees the original IR and make transformations (e.g., inline hot calls or whatever), and do aggressive simplifycfg, in other words, do not preserve !prof in {direct, indirect} calls in later stage of the pipeline.

Hoist direct calls and sum counters is probably better since
(use two callsites as example)

1. when both direct callsites are hot, they are hoisted once and both inlined -> faster (in terms of compile time) and more reliable than inline twice and do common code sequence elimination.
2. if one callsite is cold and another is hot, sum counters gets both callsites inlined (since there is only one hot callsites after hoist), compared with leave cold call outlined && inline hot calls.

This one is mainly for profile based devirtualization. Related to inlining, there is a pre-pass to do the unmerging:

For my information, in which pass does the unmerging happens?

arg = select cond, 1, val
call foo(arg)

>

if (cond) {

call foo(1)

} else

call foo(val)

[nikic]

Could you please start by implementing metadata merging, and then return to this patch only if strictly necessary? I'd rather not have another SimplifyCFG option for such a niche use case, if it's possible to get most of the benefit via standard metadata merging.

[tejohnson]

Instead of making this false by default and requiring it to be set from the command line for pre-LTO compile steps, it would be better to add a "setPreserveIndirectCallInstWithProfInHoistAndSink" interface and set this to false when appropriate from the pass pipeline builder (see other examples where the SimplifyCFGOptions are set from there). That way it can be controlled more exactly. I'm a little confused why we would disable this only in the pre-LTO compile step right now: I suppose this is specific to SamplePGO because ICP is not performed during the pre-LTO compile step? In other cases (non-LTO and instrumentation PGO) ICP appears to be performed right after profile annotation.

However, we also perform SimplifyCFG at least once before profile annotation (both sample and instrumentation PGO). Wouldn't we still end up merging indirect calls in some cases too aggressively, because they don't have any profile metadata so we won't know any better? I'm currently testing a change to avoid speculation in SimplifyCFG before profile annotation to avoid doing incorrectly aggressive transformations. We might want to do something similar here too: setPreserveIndirectCallInstWithProfInHoistAndSink(false) for all pre-PGO annotation invocations of SimplifyCFG in PGO compiles.

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

1818

Suggest undoing this change which just moves the comment a little but unnecessarily adds a diff.

[mingmingl]

In D147954#4276844, @nikic wrote:

Could you please start by implementing metadata merging, and then return to this patch only if strictly necessary? I'd rather not have another SimplifyCFG option for such a niche use case, if it's possible to get most of the benefit via standard metadata merging.

(quick reply to describe the plan) okay, let me implement something as described and see how it works for this use case

1. do metadata merging for direct callsites 2) conservatively not hoisting/sinking indirect callsites for indirect callsites if !prof presents -> indirect-call-promotion pass will clear !prof for indirect-callsite (since there are no other uses of this type of value profiles) so the SimplifyCFG pass after indirect-call-promotion should be able to do a full cleanup if the indirect-call is still in the IR but not speculatively devirtualized.

[davidxl]

In D147954#4276616, @mingmingl wrote:

In D147954#4276502, @davidxl wrote:

In D147954#4276299, @wenlei wrote:

I guess you do this only for calls and limit it for pre-link because you want to minimize the restriction on optimization, while making post-link inlining operate on accurate call profile?

Yep this is the plan, but for post-link indirect-call-promotion (which could be subsequently inlined after ICP)

Code motion is generally destructive for profile quality. Instead of blocking all sinking and hoisting, have you considered trying to update profile for sinking/hoisting when there's no merging, but only block those that involves merging (i.e. head/tail merge) with incompatible profile? I imagine in some cases, allow sinking/hoisting but updating profile properly may help better inlining later.

For my understanding, is https://gcc.godbolt.org/z/cMWY9Tqzv an example (based on c++ source with manual !prof) where updating profile would be useful? I think sinking/hoisting would merge instructions but I might miss something.

• In this example, two direct callsites are merged but both branch_weights metadata (!prof 0, !prof 1) are dropped which is sub-optimal. It's likely better in majority of cases by merging two !prof into one and accumulate counters.

Nevertheless, (after thinking about direct callsites above), I modified the implementation (and option names) to look at indirect calls only primarily because 1) the desired behavior upon icall (indicating !prof is value profile as opposed to branch_weights for direct call) is probably clearer and 2) the pattern shows up (as C++ code shows) with polymorphism, and meanwhile added a 'FIXME' to mention the current 'hoisting' is still suboptimal since it dropped branch_weights on two identical direct calls.

I concur it's better to decide on option name once (preserve-call vs preserve-indirect-call) so I'm fine with implementing the sum-of-branch-weight counters or a better alternative in this patch (and name the option back to more general preserve-call... Let me know your thoughts!

This one is mainly for profile based devirtualization. Related to inlining, there is a pre-pass to do the unmerging:

For my information, in which pass does the unmerging happens?

There is a CallSiteSplitting Pass that does it.

arg = select cond, 1, val
call foo(arg)

>

if (cond) {

call foo(1)

} else

call foo(val)

[davidxl]

In D147954#4276844, @nikic wrote:

Could you please start by implementing metadata merging, and then return to this patch only if strictly necessary? I'd rather not have another SimplifyCFG option for such a niche use case, if it's possible to get most of the benefit via standard metadata merging.

Merging value profile data will likely render the data not quite useful anymore -- the same effect of dropping the data completely.

[mingmingl]

implemented branch_weight merge for direct callsites in hoist and sink, and get rid of the command line option to override indirect-call specific option -> SimplifyCFG option parser still parses it for testing purposes.

[mingmingl]

In D147954#4277742, @tejohnson wrote:

Instead of making this false by default and requiring it to be set from the command line for pre-LTO compile steps, it would be better to add a "setPreserveIndirectCallInstWithProfInHoistAndSink" interface and set this to false when appropriate from the pass pipeline builder (see other examples where the SimplifyCFGOptions are set from there). That way it can be controlled more exactly.

Added setPreserveIndirectCallInstWithProfInHoistAndSink method for pass builder pipeline usage.

I'm a little confused why we would disable this only in the pre-LTO compile step right now: I suppose this is specific to SamplePGO because ICP is not performed during the pre-LTO compile step?

(I was confused when seeing it as well) It happens in IFDO since in this particular case, prelink pipeline doesn't run ICP pass; the !prof metadata is dropped in prelink build, so postlink ICP didn't see it.

In other cases (non-LTO and instrumentation PGO) ICP appears to be performed right after profile annotation.

However, we also perform SimplifyCFG at least once before profile annotation (both sample and instrumentation PGO). Wouldn't we still end up merging indirect calls in some cases too aggressively, because they don't have any profile metadata so we won't know any better? I'm currently testing a change to avoid speculation in SimplifyCFG before profile annotation to avoid doing incorrectly aggressive transformations. We might want to do something similar here too: setPreserveIndirectCallInstWithProfInHoistAndSink(false) for all pre-PGO annotation invocations of SimplifyCFG in PGO compiles.

As we briefly discussed, when profile-gen and profile-use in IFDO see the same cfg (i.e., merge happens in profile-gen) only one !prof is generated initially.

For SamplePGO, I think when two indirect calls show up in sampled binary and gives two !prof metadata at two different line offsets in SamplePGO profiles, two indirect calls are likely to be seen in sample-pgo pipeline.

In D147954#4277744, @mingmingl wrote:

In D147954#4276844, @nikic wrote:

Could you please start by implementing metadata merging, and then return to this patch only if strictly necessary? I'd rather not have another SimplifyCFG option for such a niche use case, if it's possible to get most of the benefit via standard metadata merging.

(quick reply to describe the plan) okay, let me implement something as described and see how it works for this use case

1. do metadata merging for direct callsites 2) conservatively not hoisting/sinking indirect callsites for indirect callsites if !prof presents -> indirect-call-promotion pass will clear !prof for indirect-callsite (since there are no other uses of this type of value profiles) so the SimplifyCFG pass after indirect-call-promotion should be able to do a full cleanup if the indirect-call is still in the IR but not speculatively devirtualized.

Actually merging two different virtual calls with the same counters could be counterproductive, and ICP pass preserves !prof when not all information is used so I kept the option.

In D147954#4277932, @davidxl wrote:

In D147954#4276616, @mingmingl wrote:

In D147954#4276502, @davidxl wrote:

In D147954#4276299, @wenlei wrote:

I guess you do this only for calls and limit it for pre-link because you want to minimize the restriction on optimization, while making post-link inlining operate on accurate call profile?

Yep this is the plan, but for post-link indirect-call-promotion (which could be subsequently inlined after ICP)

Code motion is generally destructive for profile quality. Instead of blocking all sinking and hoisting, have you considered trying to update profile for sinking/hoisting when there's no merging, but only block those that involves merging (i.e. head/tail merge) with incompatible profile? I imagine in some cases, allow sinking/hoisting but updating profile properly may help better inlining later.

For my understanding, is https://gcc.godbolt.org/z/cMWY9Tqzv an example (based on c++ source with manual !prof) where updating profile would be useful? I think sinking/hoisting would merge instructions but I might miss something.

• In this example, two direct callsites are merged but both branch_weights metadata (!prof 0, !prof 1) are dropped which is sub-optimal. It's likely better in majority of cases by merging two !prof into one and accumulate counters.

Nevertheless, (after thinking about direct callsites above), I modified the implementation (and option names) to look at indirect calls only primarily because 1) the desired behavior upon icall (indicating !prof is value profile as opposed to branch_weights for direct call) is probably clearer and 2) the pattern shows up (as C++ code shows) with polymorphism, and meanwhile added a 'FIXME' to mention the current 'hoisting' is still suboptimal since it dropped branch_weights on two identical direct calls.

I concur it's better to decide on option name once (preserve-call vs preserve-indirect-call) so I'm fine with implementing the sum-of-branch-weight counters or a better alternative in this patch (and name the option back to more general preserve-call... Let me know your thoughts!

This one is mainly for profile based devirtualization. Related to inlining, there is a pre-pass to do the unmerging:

For my information, in which pass does the unmerging happens?

There is a CallSiteSplitting Pass that does it.

Ack, thanks!

arg = select cond, 1, val
call foo(arg)

>

if (cond) {

call foo(1)

} else

call foo(val)

[mingmingl]

undo unrelated change around comment as suggested.

[tejohnson]

In D147954#4277744, @mingmingl wrote:

In D147954#4276844, @nikic wrote:

Could you please start by implementing metadata merging, and then return to this patch only if strictly necessary? I'd rather not have another SimplifyCFG option for such a niche use case, if it's possible to get most of the benefit via standard metadata merging.

(quick reply to describe the plan) okay, let me implement something as described and see how it works for this use case

1. do metadata merging for direct callsites 2) conservatively not hoisting/sinking indirect callsites for indirect callsites if !prof presents -> indirect-call-promotion pass will clear !prof for indirect-callsite (since there are no other uses of this type of value profiles) so the SimplifyCFG pass after indirect-call-promotion should be able to do a full cleanup if the indirect-call is still in the IR but not speculatively devirtualized.

Actually merging two different virtual calls with the same counters could be counterproductive, and ICP pass preserves !prof when not all information is used so I kept the option.

I thought per our offline chat that you were going to try merging the !prof VP metadata. When is it counterproductive?

[davidxl]

Should the direct call prof data merge be in a separate patch?

[mingmingl]

In D147954#4280439, @tejohnson wrote:

In D147954#4277744, @mingmingl wrote:

In D147954#4276844, @nikic wrote:

Could you please start by implementing metadata merging, and then return to this patch only if strictly necessary? I'd rather not have another SimplifyCFG option for such a niche use case, if it's possible to get most of the benefit via standard metadata merging.

(quick reply to describe the plan) okay, let me implement something as described and see how it works for this use case

1. do metadata merging for direct callsites 2) conservatively not hoisting/sinking indirect callsites for indirect callsites if !prof presents -> indirect-call-promotion pass will clear !prof for indirect-callsite (since there are no other uses of this type of value profiles) so the SimplifyCFG pass after indirect-call-promotion should be able to do a full cleanup if the indirect-call is still in the IR but not speculatively devirtualized.

Actually merging two different virtual calls with the same counters could be counterproductive, and ICP pass preserves !prof when not all information is used so I kept the option.

I thought per our offline chat that you were going to try merging the !prof VP metadata. When is it counterproductive?

sorry for the confusion. merging !prof of indirect call targets may make target values not significant (e.g., in https://gcc.godbolt.org/z/o6G68rn3v, 'func1' and func2' are virtual calls with different address offset so the target values are different; when call-count is updated as a sum, the values become not significant).

As discussed (with xur@ together, I'll change the implementation as
(Possible in a another patch before this)

1. introduce an option in ICP pass -to clear 'direct-call-targets' after the last ICP-> it could be a partial clear when one !prof has more than indirect-call target value profiles
2. Let pass builder set the option above (e.g. post link in a LTO pipeline, or the ICP in a non-LTO pipeline)

In this D147954

3. Get rid of the option in SimplifyCFG pass
4. Change SimplifyCFG to bail out when it sees an indirect call with target value profiles

And move 'branch_weight' merge to a separate patch as well (per comment)

In this way, value-profile metadata is preserved for ICP to make use of it, and simplifycfg could proceed to sink/hoist indirect calls if ICP didn't happen.

In D147954#4280751, @davidxl wrote:

Should the direct call prof data merge be in a separate patch?

Yep, a separate patch is reasonable. Will do that.

[wenlei]

Just to make sure I understand it correctly. The solution to the issue Teresa raised,

In other cases (non-LTO and instrumentation PGO) ICP appears to be performed right after profile annotation.

However, we also perform SimplifyCFG at least once before profile annotation (both sample and instrumentation PGO). Wouldn't we still end up merging indirect calls in some cases too aggressively, because they don't have any profile metadata so we won't know any better? I'm currently testing a change to avoid speculation in SimplifyCFG before profile annotation to avoid doing incorrectly aggressive transformations. We might want to do something similar here too: setPreserveIndirectCallInstWithProfInHoistAndSink(false) for all pre-PGO annotation invocations of SimplifyCFG in PGO compiles.

is to not rely on pre-link vs post-link to decide when to enable/disable hoist/sink for calls, but to check whether calls have target value profile remaining (i.e. ICP yet to happen) so we can always avoid destroying profile for ICP regardless of where simpilifyCFG is run. Is that correct?

[mingmingl]

In D147954#4281685, @wenlei wrote:

Just to make sure I understand it correctly. The solution to the issue Teresa raised,

In other cases (non-LTO and instrumentation PGO) ICP appears to be performed right after profile annotation.

However, we also perform SimplifyCFG at least once before profile annotation (both sample and instrumentation PGO). Wouldn't we still end up merging indirect calls in some cases too aggressively, because they don't have any profile metadata so we won't know any better? I'm currently testing a change to avoid speculation in SimplifyCFG before profile annotation to avoid doing incorrectly aggressive transformations. We might want to do something similar here too: setPreserveIndirectCallInstWithProfInHoistAndSink(false) for all pre-PGO annotation invocations of SimplifyCFG in PGO compiles.

is to not rely on pre-link vs post-link to decide when to enable/disable hoist/sink for calls, but to check whether calls have target value profile remaining (i.e. ICP yet to happen) so we can always avoid destroying profile for ICP regardless of where simpilifyCFG is run. Is that correct?

Here is a summary of how dropped metadata happens in an instrumented FDO + thinlto build

1. SimplifyCFG pass run multiple times in prelink pipeline and postlink pipeline, and each run could be configured with different SimplifyCFGOptions (sink or no sink, hoist or no hoist, etc)
2. The dropped metadata is observed in a instrumented fdo + lto build, when prelink pipeline runs simplifycfg with hoist && sink, so postlink ICP couldn't see the !prof metadata.

For the questions, here are my thoughts

• could SimplifyCFG undesirably prematurely sink/hoist callsites before we got a chance to instrument them,
  • the answer is that it shouldn't. Instead SimplifyCFG pass should preserve the callsites for instrumentation (I'm not very familiar with callsite splitting that's mentioned above, but guessing from the name it wants to split callsites and expose them)
• could SimplifyCFG sink/hoist callsites in a binary foo over which SamplePGO profiles are collected
  • if foo gets two indirect callsites c1 and c2 merged, hypothetically one debug location is kept in the merged callsite, and target values of both c1 and c2 are attributed to this debug location, so it looks like a) hoist && sink could affect the collected profiles -> we want two value profiles, one for c1 and another for c2, but we only get one profile with merged target values (since profiled binary only has one callsite) b) as long as collected sample-pgo profiles have two value profiles, in an AutoFDO build, we should see both callsites exposed and annotated.

About why we get two value profiles in the first place in an instrumentation + LTO build

• I took a look at pass builder just now, looks like earlier simplify-cfg passes in one pipeline don't turn on 'sink' or 'hoist' [1], and later simplify-cfg passes in a pipeline do turn on sink and host. Similarly, for the small test case (https://gcc.godbolt.org/z/WxE8zshqE), hoist or sink doesn't happen until the 6th SimplifyCFG run (out of 8 SimplifyCFG runs in total). That probably explains why we are able to get two different indirect callsites exposed and instrumented in the first place.

• In PassBuilderPipelines.cpp, sink and hoist are set to true inside
  1. buildFunctionSimplificationPipeline (and buildFunctionSimplificationPipeline is called inside buildInlinerPipeline)
  2. addVectorPassses

[1] https://gcc.godbolt.org/z/8E39cTosE prints the passes with options in opt since printing in clang is difficult

[mingmingl]

In D147954#4282224, @mingmingl wrote:

In D147954#4281685, @wenlei wrote:

Just to make sure I understand it correctly. The solution to the issue Teresa raised,

In other cases (non-LTO and instrumentation PGO) ICP appears to be performed right after profile annotation.

However, we also perform SimplifyCFG at least once before profile annotation (both sample and instrumentation PGO). Wouldn't we still end up merging indirect calls in some cases too aggressively, because they don't have any profile metadata so we won't know any better? I'm currently testing a change to avoid speculation in SimplifyCFG before profile annotation to avoid doing incorrectly aggressive transformations. We might want to do something similar here too: setPreserveIndirectCallInstWithProfInHoistAndSink(false) for all pre-PGO annotation invocations of SimplifyCFG in PGO compiles.

is to not rely on pre-link vs post-link to decide when to enable/disable hoist/sink for calls, but to check whether calls have target value profile remaining (i.e. ICP yet to happen) so we can always avoid destroying profile for ICP regardless of where simpilifyCFG is run. Is that correct?

Here is a summary of how dropped metadata happens in an instrumented FDO + thinlto build

1. SimplifyCFG pass run multiple times in prelink pipeline and postlink pipeline, and each run could be configured with different SimplifyCFGOptions (sink or no sink, hoist or no hoist, etc)
2. The dropped metadata is observed in a instrumented fdo + lto build, when prelink pipeline runs simplifycfg with hoist && sink, so postlink ICP couldn't see the !prof metadata.

For the questions, here are my thoughts

• could SimplifyCFG undesirably prematurely sink/hoist callsites before we got a chance to instrument them,
  • the answer is that it shouldn't. Instead SimplifyCFG pass should preserve the callsites for instrumentation (I'm not very familiar with callsite splitting that's mentioned above, but guessing from the name it wants to split callsites and expose them)

Actually https://gcc.godbolt.org/z/MM976vn55 shows two indirect callsites are merged into one in the instrumented build, meaning instrumented build could be hoist two different indirect callsites.

• could SimplifyCFG sink/hoist callsites in a binary foo over which SamplePGO profiles are collected
  • if foo gets two indirect callsites c1 and c2 merged, hypothetically one debug location is kept in the merged callsite, and target values of both c1 and c2 are attributed to this debug location, so it looks like a) hoist && sink could affect the collected profiles -> we want two value profiles, one for c1 and another for c2, but we only get one profile with merged target values (since profiled binary only has one callsite) b) as long as collected sample-pgo profiles have two value profiles, in an AutoFDO build, we should see both callsites exposed and annotated.

About why we get two value profiles in the first place in an instrumentation + LTO build

• I took a look at pass builder just now, looks like earlier simplify-cfg passes in one pipeline don't turn on 'sink' or 'hoist' [1], and later simplify-cfg passes in a pipeline do turn on sink and host. Similarly, for the small test case (https://gcc.godbolt.org/z/WxE8zshqE), hoist or sink doesn't happen until the 6th SimplifyCFG run (out of 8 SimplifyCFG runs in total). That probably explains why we are able to get two different indirect callsites exposed and instrumented in the first place.

• In PassBuilderPipelines.cpp, sink and hoist are set to true inside
  1. buildFunctionSimplificationPipeline (and buildFunctionSimplificationPipeline is called inside buildInlinerPipeline)
  2. addVectorPassses

[1] https://gcc.godbolt.org/z/8E39cTosE prints the passes with options in opt since printing in clang is difficult

[mingmingl]

the planned change of 'llvm/lib/Transforms/Utils/SimplifyCFG.cpp' for the problem to solve is in D148876 (to illustrate how module flag and added helper functions are used in one patch).

Probably will come back to update this patch for simplify-cfg as a split of D148876.

llvm/include/llvm/IR/Metadata.h

#include "llvm/IR/Metadata.def"
   /// Methods for metadata merging.
   static MDNode *concatenate(MDNode *A, MDNode *B);
   static MDNode *intersect(MDNode *A, MDNode *B);
   static MDNode *getMostGenericTBAA(MDNode *A, MDNode *B);
   static MDNode *getMostGenericFPMath(MDNode *A, MDNode *B);
   static MDNode *getMostGenericRange(MDNode *A, MDNode *B);
   static MDNode *getMostGenericAliasScope(MDNode *A, MDNode *B);
   static MDNode *getMostGenericAlignmentOrDereferenceable(MDNode *A, MDNode *B);
+  /// Returns nullptr if merge is not implementation for the type of instrutions
+  /// and !prof metadata. Currently only implemented with direct callsites with
+  /// branch weights.
+  static MDNode *getMergedProfMetadata(MDNode *A, MDNode *B,
+                                       const Instruction *AInstr,
+                                       const Instruction *BInstr);
 };
 
 /// Tuple of metadata.
 ///
 /// This is the simple \a MDNode arbitrary tuple.  Nodes are uniqued by
 /// default based on their operands.
 class MDTuple : public MDNode {
   friend class LLVMContextImpl;

llvm/include/llvm/Transforms/Utils/SimplifyCFGOptions.h

 struct SimplifyCFGOptions {
   int BonusInstThreshold = 1;
   bool ForwardSwitchCondToPhi = false;
   bool ConvertSwitchRangeToICmp = false;
   bool ConvertSwitchToLookupTable = false;
   bool NeedCanonicalLoop = true;
   bool HoistCommonInsts = false;
   bool SinkCommonInsts = false;
+  bool PreserveIndirectCallInstWithProfInHoistAndSink = false;
   bool SimplifyCondBranch = true;
   bool FoldTwoEntryPHINode = true;
 
   AssumptionCache *AC = nullptr;
 
   // Support 'builder' pattern to set members by name at construction time.
   SimplifyCFGOptions &bonusInstThreshold(int I) {
     BonusInstThreshold = I;
struct SimplifyCFGOptions {
   SimplifyCFGOptions &hoistCommonInsts(bool B) {
     HoistCommonInsts = B;
     return *this;
   }
   SimplifyCFGOptions &sinkCommonInsts(bool B) {
     SinkCommonInsts = B;
     return *this;
   }
+  SimplifyCFGOptions &
+  setPreserveIndirectCallInstWithProfInHoistAndSink(bool B) {
+    PreserveIndirectCallInstWithProfInHoistAndSink = B;
+    return *this;
+  }
   SimplifyCFGOptions &setAssumptionCache(AssumptionCache *Cache) {
     AC = Cache;
     return *this;
   }
   SimplifyCFGOptions &setSimplifyCondBranch(bool B) {
     SimplifyCondBranch = B;
     return *this;
   }

llvm/lib/IR/Metadata.cpp

MDNode *MDNode::getMostGenericFPMath(MDNode *A, MDNode *B) {
 
   APFloat AVal = mdconst::extract<ConstantFP>(A->getOperand(0))->getValueAPF();
   APFloat BVal = mdconst::extract<ConstantFP>(B->getOperand(0))->getValueAPF();
   if (AVal < BVal)
     return A;
   return B;
 }
 
+MDNode *MDNode::getMergedProfMetadata(MDNode *A, MDNode *B,
+                                      const Instruction *AInstr,
+                                      const Instruction *BInstr) {
+  if (!A)
+    return B;
+  if (!B)
+    return A;
+
+  const CallInst *ACall = dyn_cast<CallInst>(AInstr);
+  const CallInst *BCall = dyn_cast<CallInst>(BInstr);
+  if (!(ACall && BCall && ACall->getCalledFunction() &&
+        BCall->getCalledFunction()))
+    return nullptr;
+
+  auto &Ctx = AInstr->getContext();
+  MDBuilder MDHelper(Ctx);
+
+  // Both ACall and BCall are direct callsites.
+  assert(A->getNumOperands() >= 2 && B->getNumOperands() >= 2 &&
+         "!prof annotations should have no less than 2 operands");
+  MDString *AMDS = dyn_cast<MDString>(A->getOperand(0));
+  MDString *BMDS = dyn_cast<MDString>(B->getOperand(0));
+  assert(AMDS != nullptr && BMDS != nullptr &&
+         "first operand should be a non-null MDString");
+  StringRef AProfName = AMDS->getString();
+  StringRef BProfName = BMDS->getString();
+  if (AProfName.equals("branch_weights") &&
+      BProfName.equals("branch_weights")) {
+    ConstantInt *AInstrWeight =
+        mdconst::dyn_extract<ConstantInt>(A->getOperand(1));
+    ConstantInt *BInstrWeight =
+        mdconst::dyn_extract<ConstantInt>(B->getOperand(1));
+    if (AInstrWeight && BInstrWeight) {
+      return MDNode::get(
+          Ctx, {MDHelper.createString("branch_weights"),
+                MDHelper.createConstant(ConstantInt::get(
+                    Type::getInt64Ty(Ctx), AInstrWeight->getZExtValue() +
+                                               BInstrWeight->getZExtValue()))});
+    }
+  }
+  return nullptr;
+}
+
 static bool isContiguous(const ConstantRange &A, const ConstantRange &B) {
   return A.getUpper() == B.getLower() || A.getLower() == B.getUpper();
 }
 
 static bool canBeMerged(const ConstantRange &A, const ConstantRange &B) {
   return !A.intersectWith(B).isEmptySet() || isContiguous(A, B);
 }
 

llvm/lib/Passes/PassBuilder.cpp

while (!Params.empty()) {
     } else if (ParamName == "switch-to-lookup") {
       Result.convertSwitchToLookupTable(Enable);
     } else if (ParamName == "keep-loops") {
       Result.needCanonicalLoops(Enable);
     } else if (ParamName == "hoist-common-insts") {
       Result.hoistCommonInsts(Enable);
     } else if (ParamName == "sink-common-insts") {
       Result.sinkCommonInsts(Enable);
+    } else if (ParamName ==
+               "preserve-indirect-call-inst-with-prof-in-hoist-and-sink") {
+      Result.setPreserveIndirectCallInstWithProfInHoistAndSink(Enable);
     } else if (Enable && ParamName.consume_front("bonus-inst-threshold=")) {
       APInt BonusInstThreshold;
       if (ParamName.getAsInteger(0, BonusInstThreshold))
         return make_error<StringError>(
             formatv("invalid argument to SimplifyCFG pass bonus-threshold "
                     "parameter: '{0}' ",
                     ParamName).str(),
             inconvertibleErrorCode());

llvm/lib/Transforms/Utils/Local.cpp

switch (Kind) {
         // If K does move, keep noundef if it is present in both instructions.
         if (DoesKMove)
           K->setMetadata(Kind, JMD);
         break;
       case LLVMContext::MD_nontemporal:
         // Preserve !nontemporal if it is present on both instructions.
         K->setMetadata(Kind, JMD);
         break;
+      case LLVMContext::MD_prof: {
+        K->setMetadata(Kind, MDNode::getMergedProfMetadata(KMD, JMD, K, J));
+      }
     }
   }
   // Set !invariant.group from J if J has it. If both instructions have it
   // then we will just pick it from J - even when they are different.
   // Also make sure that K is load or store - f.e. combining bitcast with load
   // could produce bitcast with invariant.group metadata, which is invalid.
   // FIXME: we should try to preserve both invariant.group md if they are
   // different, but right now instruction can only have one invariant.group.
unsigned KnownIDs[] = {LLVMContext::MD_tbaa,
                          LLVMContext::MD_invariant_load,
                          LLVMContext::MD_nonnull,
                          LLVMContext::MD_invariant_group,
                          LLVMContext::MD_align,
                          LLVMContext::MD_dereferenceable,
                          LLVMContext::MD_dereferenceable_or_null,
                          LLVMContext::MD_access_group,
                          LLVMContext::MD_preserve_access_index,
+                         LLVMContext::MD_prof,
                          LLVMContext::MD_nontemporal,
                          LLVMContext::MD_noundef};
   combineMetadata(K, J, KnownIDs, KDominatesJ);
 }
 
 void llvm::copyMetadataForLoad(LoadInst &Dest, const LoadInst &Source) {
   SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
   Source.getAllMetadata(MD);

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

for (;;) {
     if (I1->isIdenticalToWhenDefined(I2)) {
       // Even if the instructions are identical, it may not be safe to hoist
       // them if we have skipped over instructions with side effects or their
       // operands weren't hoisted.
       if (!isSafeToHoistInstr(I1, SkipFlagsBB1) ||
           !isSafeToHoistInstr(I2, SkipFlagsBB2))
         return Changed;
 
-      // If we're going to hoist a call, make sure that the two instructions
-      // we're commoning/hoisting are both marked with musttail, or neither of
-      // them is marked as such. Otherwise, we might end up in a situation where
-      // we hoist from a block where the terminator is a `ret` to a block where
-      // the terminator is a `br`, and `musttail` calls expect to be followed by
-      // a return.
       auto *C1 = dyn_cast<CallInst>(I1);
       auto *C2 = dyn_cast<CallInst>(I2);
-      if (C1 && C2)
+      if (C1 && C2) {
+        // If we're going to hoist a call, make sure that the two instructions
+        // we're commoning/hoisting are both marked with musttail, or neither of
+        // them is marked as such. Otherwise, we might end up in a situation
+        // where we hoist from a block where the terminator is a `ret` to a
+        // block where the terminator is a `br`, and `musttail` calls expect to
+        // be followed by a return.
         if (C1->isMustTailCall() != C2->isMustTailCall())
           return Changed;
+        // If C1 and C2 are indirect calls with different !prof metadata (i.e.,
+        // "VP" for indirect calls), conservatively not hoisting them since
+        // merge by a naive concatenation might make profile data less precise.
+        // Here two !prof metadatas are considered different if the pointers are
+        // different. If they turn out be have the same content by a deep
+        // comparison, hoisting would still make sense.
+        // FIXME:
+        // Probably add a 'eq' comparator for "VP" of indirect calls and use
+        // it here, so that hoisting happens for icalls with essentially the
+        // same value profile metadata.
+        if (Options.PreserveIndirectCallInstWithProfInHoistAndSink &&
+            C1->isIndirectCall() && C2->isIndirectCall() &&
+            C1->getMetadata(LLVMContext::MD_prof) !=
+                C2->getMetadata(LLVMContext::MD_prof))
+          return Changed;
+      }
 
       if (!TTI.isProfitableToHoist(I1) || !TTI.isProfitableToHoist(I2))
         return Changed;
 
       // If any of the two call sites has nomerge or convergent attribute, stop
       // hoisting.
       if (const auto *CB1 = dyn_cast<CallBase>(I1))
         if (CB1->cannotMerge() || CB1->isConvergent())

 
 // All instructions in Insts belong to different blocks that all unconditionally
 // branch to a common successor. Analyze each instruction and return true if it
 // would be possible to sink them into their successor, creating one common
 // instruction instead. For every value that would be required to be provided by
 // PHI node (because an operand varies in each input block), add to PHIOperands.
 static bool canSinkInstructions(
     ArrayRef<Instruction *> Insts,
-    DenseMap<Instruction *, SmallVector<Value *, 4>> &PHIOperands) {
+    DenseMap<Instruction *, SmallVector<Value *, 4>> &PHIOperands,
+    bool PreserveCallInstWithProf) {
   // Prune out obviously bad instructions to move. Each instruction must have
   // exactly zero or one use, and we check later that use is by a single, common
   // PHI instruction in the successor.
   bool HasUse = !Insts.front()->user_empty();
   for (auto *I : Insts) {
     // These instructions may change or break semantics if moved.
     if (isa<PHINode>(I) || I->isEHPad() || isa<AllocaInst>(I) ||
         I->getType()->isTokenTy())
       return false;
 
     // Do not try to sink an instruction in an infinite loop - it can cause
     // this algorithm to infinite loop.
     if (I->getParent()->getSingleSuccessor() == I->getParent())
       return false;
 
     // Conservatively return false if I is an inline-asm instruction. Sinking
     // and merging inline-asm instructions can potentially create arguments
     // that cannot satisfy the inline-asm constraints.
     // If the instruction has nomerge or convergent attribute, return false.
     if (const auto *C = dyn_cast<CallBase>(I))
       if (C->isInlineAsm() || C->cannotMerge() || C->isConvergent())
         return false;
 
     // Each instruction must have zero or one use.
     if (HasUse && !I->hasOneUse())
       return false;
     if (!HasUse && !I->user_empty())
       return false;
if (isa<CallBase>(I0)) {
     auto IsIndirectCall = [](const Instruction *I) {
       return cast<CallBase>(I)->isIndirectCall();
     };
     bool HaveIndirectCalls = any_of(Insts, IsIndirectCall);
     bool AllCallsAreIndirect = all_of(Insts, IsIndirectCall);
     if (HaveIndirectCalls) {
       if (!AllCallsAreIndirect)
         return false;
+
+      if (PreserveCallInstWithProf) {
+        std::optional<MDNode *> ProfMD = std::nullopt;
+        // If not all indirect calls have the same !prof (i.e., value profile)
+        // metadata, conservatively not sinking them given that merging value
+        // profiles with a naive concatenation may make profiles inaccurate and
+        // counterproductive for indirect-call-promotion.
+        for (const Instruction *I : Insts) {
+          if (ProfMD == std::nullopt)
+            ProfMD = std::make_optional(I->getMetadata(LLVMContext::MD_prof));
+          else if (I->getMetadata(LLVMContext::MD_prof) != *ProfMD)
+            return false;
+        }
+      }
     } else {
       // All callees must be identical.
       Value *Callee = nullptr;
       for (const Instruction *I : Insts) {
         Value *CurrCallee = cast<CallBase>(I)->getCalledOperand();
         if (!Callee)
           Callee = CurrCallee;
         else if (Callee != CurrCallee)
ArrayRef<Instruction*> operator * () const {
       return Insts;
     }
   };
 
 } // end anonymous namespace
 
 /// Check whether BB's predecessors end with unconditional branches. If it is
 /// true, sink any common code from the predecessors to BB.
-static bool SinkCommonCodeFromPredecessors(BasicBlock *BB,
-                                           DomTreeUpdater *DTU) {
+static bool SinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU,
+                                           bool PreserveCallInstWithProf) {
   // We support two situations:
   //   (1) all incoming arcs are unconditional
   //   (2) there are non-unconditional incoming arcs
   //
   // (2) is very common in switch defaults and
   // else-if patterns;
   //
   //   if (a) f(1);
static bool SinkCommonCodeFromPredecessors(BasicBlock *BB, DomTreeUpdater *DTU,
   // carry on. If we can sink an instruction but need to PHI-merge some operands
   // (because they're not identical in each instruction) we add these to
   // PHIOperands.
   int ScanIdx = 0;
   SmallPtrSet<Value*,4> InstructionsToSink;
   DenseMap<Instruction*, SmallVector<Value*,4>> PHIOperands;
   LockstepReverseIterator LRI(UnconditionalPreds);
   while (LRI.isValid() &&
-         canSinkInstructions(*LRI, PHIOperands)) {
+         canSinkInstructions(*LRI, PHIOperands, PreserveCallInstWithProf)) {
     LLVM_DEBUG(dbgs() << "SINK: instruction can be sunk: " << *(*LRI)[0]
                       << "\n");
     InstructionsToSink.insert((*LRI).begin(), (*LRI).end());
     ++ScanIdx;
     --LRI;
   }
 
   // If no instructions can be sunk, early-return.
bool SimplifyCFGOpt::simplifyOnce(BasicBlock *BB) {
 
   // Merge basic blocks into their predecessor if there is only one distinct
   // pred, and if there is only one distinct successor of the predecessor, and
   // if there are no PHI nodes.
   if (MergeBlockIntoPredecessor(BB, DTU))
     return true;
 
   if (SinkCommon && Options.SinkCommonInsts)
-    if (SinkCommonCodeFromPredecessors(BB, DTU) ||
+    if (SinkCommonCodeFromPredecessors(
+            BB, DTU, Options.PreserveIndirectCallInstWithProfInHoistAndSink) ||
         MergeCompatibleInvokes(BB, DTU)) {
       // SinkCommonCodeFromPredecessors() does not automatically CSE PHI's,
       // so we may now how duplicate PHI's.
       // Let's rerun EliminateDuplicatePHINodes() first,
       // before FoldTwoEntryPHINode() potentially converts them into select's,
       // after which we'd need a whole EarlyCSE pass run to cleanup them.
       return true;
     }

llvm/test/Transforms/SimplifyCFG/merge-direct-call-branch-weights-in-hoist.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt < %s -passes='simplifycfg<no-sink-common-insts;hoist-common-insts>' -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s --check-prefix=HOIST
+
+define dso_local i32 @_Z4funciiii(i32 %a, i32 %b){
+; HOIST-LABEL: define dso_local i32 @_Z4funciiii
+; HOIST-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; HOIST-NEXT:  entry:
+; HOIST-NEXT:    br label [[FOR_BODY:%.*]]
+; HOIST:       for.cond.cleanup:
+; HOIST-NEXT:    [[SUM_1_LCSSA:%.*]] = phi i32 [ [[SUM_1:%.*]], [[FOR_INC:%.*]] ]
+; HOIST-NEXT:    ret i32 [[SUM_1_LCSSA]]
+; HOIST:       for.body:
+; HOIST-NEXT:    [[I_016:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC]] ]
+; HOIST-NEXT:    [[SUM_015:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[SUM_1]], [[FOR_INC]] ]
+; HOIST-NEXT:    [[REM_LHS_TRUNC:%.*]] = trunc i32 [[I_016]] to i16
+; HOIST-NEXT:    [[REM14:%.*]] = urem i16 [[REM_LHS_TRUNC]], 100
+; HOIST-NEXT:    [[CMP1:%.*]] = icmp eq i16 [[REM14]], 0
+; HOIST-NEXT:    [[CALL:%.*]] = tail call i32 @_Z5func1ii(i32 [[A]], i32 [[B]]), !prof [[PROF0:![0-9]+]]
+; HOIST-NEXT:    [[ADD:%.*]] = add nsw i32 [[CALL]], [[SUM_015]]
+; HOIST-NEXT:    br i1 [[CMP1]], label [[FOR_INC]], label [[IF_ELSE:%.*]]
+; HOIST:       if.else:
+; HOIST-NEXT:    [[CALL4:%.*]] = tail call i32 @_Z5func2ii(i32 [[A]], i32 [[B]])
+; HOIST-NEXT:    [[SUB:%.*]] = sub i32 [[ADD]], [[CALL4]]
+; HOIST-NEXT:    br label [[FOR_INC]]
+; HOIST:       for.inc:
+; HOIST-NEXT:    [[SUM_1]] = phi i32 [ [[SUB]], [[IF_ELSE]] ], [ [[ADD]], [[FOR_BODY]] ]
+; HOIST-NEXT:    [[INC]] = add nuw nsw i32 [[I_016]], 1
+; HOIST-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], 1000
+; HOIST-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.inc
+  %sum.1.lcssa = phi i32 [ %sum.1, %for.inc ]
+  ret i32 %sum.1.lcssa
+
+for.body:                                         ; preds = %entry, %for.inc
+  %i.016 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %sum.015 = phi i32 [ 0, %entry ], [ %sum.1, %for.inc ]
+  %rem.lhs.trunc = trunc i32 %i.016 to i16
+  %rem14 = urem i16 %rem.lhs.trunc, 100
+  %cmp1 = icmp eq i16 %rem14, 0
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body
+  %call = tail call i32 @_Z5func1ii(i32 %a, i32 %b), !prof !0
+  %add = add nsw i32 %call, %sum.015
+  br label %for.inc
+
+if.else:                                          ; preds = %for.body
+  %call2 = tail call i32 @_Z5func1ii(i32 %a, i32 %b), !prof !1
+  %add3 = add nsw i32 %call2, %sum.015
+  %call4 = tail call i32 @_Z5func2ii(i32 %a, i32 %b)
+  %sub = sub i32 %add3, %call4
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.then, %if.else
+  %sum.1 = phi i32 [ %add, %if.then ], [ %sub, %if.else ]
+  %inc = add nuw nsw i32 %i.016, 1
+  %exitcond.not = icmp eq i32 %inc, 1000
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+declare i32 @_Z5func1ii(i32, i32)
+
+declare i32 @_Z5func2ii(i32, i32)
+
+!0 = !{!"branch_weights", i32 10}
+!1 = !{!"branch_weights", i32 990}

llvm/test/Transforms/SimplifyCFG/merge-direct-call-branch-weights-in-sink.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt < %s -passes='simplifycfg<sink-common-insts;no-hoist-common-insts>' -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s --check-prefix=HOIST
+
+define  i32 @_Z4funcii(i32 %a, i32 %b) {
+; HOIST-LABEL: define i32 @_Z4funcii
+; HOIST-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; HOIST-NEXT:  entry:
+; HOIST-NEXT:    br label [[FOR_BODY:%.*]]
+; HOIST:       for.cond.cleanup:
+; HOIST-NEXT:    [[SUM_1_LCSSA:%.*]] = phi i32 [ [[SUM_1:%.*]], [[FOR_INC:%.*]] ]
+; HOIST-NEXT:    ret i32 [[SUM_1_LCSSA]]
+; HOIST:       for.body:
+; HOIST-NEXT:    [[I_017:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[FOR_INC]] ]
+; HOIST-NEXT:    [[SUM_016:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[SUM_1]], [[FOR_INC]] ]
+; HOIST-NEXT:    [[B_ADDR_015:%.*]] = phi i32 [ [[B]], [[ENTRY]] ], [ [[SUB_SINK:%.*]], [[FOR_INC]] ]
+; HOIST-NEXT:    [[REM_LHS_TRUNC:%.*]] = trunc i32 [[I_017]] to i16
+; HOIST-NEXT:    [[REM14:%.*]] = urem i16 [[REM_LHS_TRUNC]], 100
+; HOIST-NEXT:    [[CMP1:%.*]] = icmp eq i16 [[REM14]], 0
+; HOIST-NEXT:    br i1 [[CMP1]], label [[FOR_INC]], label [[IF_ELSE:%.*]]
+; HOIST:       if.else:
+; HOIST-NEXT:    [[CALL2:%.*]] = tail call i32 @_Z5func2ii(i32 [[A]], i32 [[B_ADDR_015]])
+; HOIST-NEXT:    [[SUB:%.*]] = sub nsw i32 [[B_ADDR_015]], [[CALL2]]
+; HOIST-NEXT:    br label [[FOR_INC]]
+; HOIST:       for.inc:
+; HOIST-NEXT:    [[SUB_SINK]] = phi i32 [ [[SUB]], [[IF_ELSE]] ], [ [[B_ADDR_015]], [[FOR_BODY]] ]
+; HOIST-NEXT:    [[CALL3:%.*]] = tail call i32 @_Z5func1ii(i32 [[A]], i32 [[SUB_SINK]]), !prof [[PROF0:![0-9]+]]
+; HOIST-NEXT:    [[SUM_1]] = add nsw i32 [[CALL3]], [[SUM_016]]
+; HOIST-NEXT:    [[INC]] = add nuw nsw i32 [[I_017]], 1
+; HOIST-NEXT:    [[EXITCOND_NOT:%.*]] = icmp eq i32 [[INC]], 1000
+; HOIST-NEXT:    br i1 [[EXITCOND_NOT]], label [[FOR_COND_CLEANUP:%.*]], label [[FOR_BODY]]
+;
+entry:
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.inc
+  %sum.1.lcssa = phi i32 [ %sum.1, %for.inc ]
+  ret i32 %sum.1.lcssa
+
+for.body:                                         ; preds = %entry, %for.inc
+  %i.017 = phi i32 [ 0, %entry ], [ %inc, %for.inc ]
+  %sum.016 = phi i32 [ 0, %entry ], [ %sum.1, %for.inc ]
+  %b.addr.015 = phi i32 [ %b, %entry ], [ %b.addr.1, %for.inc ]
+  %rem.lhs.trunc = trunc i32 %i.017 to i16
+  %rem14 = urem i16 %rem.lhs.trunc, 100
+  %cmp1 = icmp eq i16 %rem14, 0
+  br i1 %cmp1, label %if.then, label %if.else
+
+if.then:                                          ; preds = %for.body
+  %call = tail call i32 @_Z5func1ii(i32 %a, i32 %b.addr.015), !prof !0
+  br label %for.inc
+
+if.else:                                          ; preds = %for.body
+  %call2 = tail call i32 @_Z5func2ii(i32 %a, i32 %b.addr.015)
+  %sub = sub nsw i32 %b.addr.015, %call2
+  %call3 = tail call i32 @_Z5func1ii(i32 %a, i32 %sub), !prof !1
+  br label %for.inc
+
+for.inc:                                          ; preds = %if.then, %if.else
+  %b.addr.1 = phi i32 [ %b.addr.015, %if.then ], [ %sub, %if.else ]
+  %call.pn = phi i32 [ %call, %if.then ], [ %call3, %if.else ]
+  %sum.1 = add nsw i32 %call.pn, %sum.016
+  %inc = add nuw nsw i32 %i.017, 1
+  %exitcond.not = icmp eq i32 %inc, 1000
+  br i1 %exitcond.not, label %for.cond.cleanup, label %for.body
+}
+
+declare i32 @_Z5func1ii(i32, i32)
+
+declare i32 @_Z5func2ii(i32, i32)
+
+!0 = !{!"branch_weights", i32 10}
+!1 = !{!"branch_weights", i32 990}

llvm/test/Transforms/SimplifyCFG/preserve-call-metadata-in-hoist.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt < %s -passes='simplifycfg<no-sink-common-insts;hoist-common-insts>' -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s --check-prefix=HOIST
+; RUN: opt < %s -passes='simplifycfg<no-sink-common-insts;hoist-common-insts;preserve-indirect-call-inst-with-prof-in-hoist-and-sink>' -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s --check-prefix=HOIST_P
+
+; IR @call_not_hoist is generated based on following C++ with manually-annotated !prof
+; Without preserving call instructions, `d->func1` is hoisted while it may not make sense
+; to do so. For example, the candidate calls are different based on derived type.
+; Note merging meta data will make the profile data less precise and not desirable either.
+; class Base {
+;    public:
+;    virtual int gettype() = 0;
+;    virtual int func1(int a, int b) = 0;
+;};
+;
+; int func2(int x, int y);
+;
+; Base* createptr(int c);
+;
+; int func(int x, int a, int b, int c) {
+;    Base* d = createptr(c);
+;    if (d->gettype() % 5 == 0) {
+;      auto ret = d->func1(a, b);
+;      return ret + func2(b, a);
+;    }
+;    return d->func1(a, b);
+; }
+define i32 @call_not_hoist(i32 %x, i32 %a, i32 %b, i32 %c) {
+; HOIST-LABEL: define i32 @call_not_hoist
+; HOIST-SAME: (i32 [[X:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
+; HOIST-NEXT:  entry:
+; HOIST-NEXT:    [[CALL:%.*]] = tail call ptr @createptr(i32 [[C]])
+; HOIST-NEXT:    [[VTABLE:%.*]] = load ptr, ptr [[CALL]], align 8
+; HOIST-NEXT:    [[TMP0:%.*]] = load ptr, ptr [[VTABLE]], align 8
+; HOIST-NEXT:    [[CALL1:%.*]] = tail call i32 [[TMP0]](ptr [[CALL]])
+; HOIST-NEXT:    [[REM:%.*]] = srem i32 [[CALL1]], 5
+; HOIST-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 0
+; HOIST-NEXT:    [[VTABLE2:%.*]] = load ptr, ptr [[CALL]], align 8
+; HOIST-NEXT:    [[VFN3:%.*]] = getelementptr inbounds ptr, ptr [[VTABLE2]], i64 1
+; HOIST-NEXT:    [[TMP1:%.*]] = load ptr, ptr [[VFN3]], align 8
+; HOIST-NEXT:    [[CALL4:%.*]] = tail call i32 [[TMP1]](ptr [[CALL]], i32 [[A]], i32 [[B]])
+; HOIST-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[CLEANUP:%.*]]
+; HOIST:       if.then:
+; HOIST-NEXT:    [[CALL5:%.*]] = tail call i32 @func2(i32 [[B]], i32 [[A]])
+; HOIST-NEXT:    [[ADD:%.*]] = add nsw i32 [[CALL5]], [[CALL4]]
+; HOIST-NEXT:    br label [[CLEANUP]]
+; HOIST:       cleanup:
+; HOIST-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[ADD]], [[IF_THEN]] ], [ [[CALL4]], [[ENTRY:%.*]] ]
+; HOIST-NEXT:    ret i32 [[RETVAL_0]]
+;
+; HOIST_P-LABEL: define i32 @call_not_hoist
+; HOIST_P-SAME: (i32 [[X:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
+; HOIST_P-NEXT:  entry:
+; HOIST_P-NEXT:    [[CALL:%.*]] = tail call ptr @createptr(i32 [[C]])
+; HOIST_P-NEXT:    [[VTABLE:%.*]] = load ptr, ptr [[CALL]], align 8
+; HOIST_P-NEXT:    [[TMP0:%.*]] = load ptr, ptr [[VTABLE]], align 8
+; HOIST_P-NEXT:    [[CALL1:%.*]] = tail call i32 [[TMP0]](ptr [[CALL]])
+; HOIST_P-NEXT:    [[REM:%.*]] = srem i32 [[CALL1]], 5
+; HOIST_P-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 0
+; HOIST_P-NEXT:    [[VTABLE2:%.*]] = load ptr, ptr [[CALL]], align 8
+; HOIST_P-NEXT:    [[VFN3:%.*]] = getelementptr inbounds ptr, ptr [[VTABLE2]], i64 1
+; HOIST_P-NEXT:    [[TMP1:%.*]] = load ptr, ptr [[VFN3]], align 8
+; HOIST_P-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; HOIST_P:       if.then:
+; HOIST_P-NEXT:    [[CALL4:%.*]] = tail call i32 [[TMP1]](ptr [[CALL]], i32 [[A]], i32 [[B]]), !prof [[PROF0:![0-9]+]]
+; HOIST_P-NEXT:    [[CALL5:%.*]] = tail call i32 @func2(i32 [[B]], i32 [[A]])
+; HOIST_P-NEXT:    [[ADD:%.*]] = add nsw i32 [[CALL5]], [[CALL4]]
+; HOIST_P-NEXT:    br label [[CLEANUP:%.*]]
+; HOIST_P:       if.end:
+; HOIST_P-NEXT:    [[CALL8:%.*]] = tail call i32 [[TMP1]](ptr [[CALL]], i32 [[A]], i32 [[B]]), !prof [[PROF1:![0-9]+]]
+; HOIST_P-NEXT:    br label [[CLEANUP]]
+; HOIST_P:       cleanup:
+; HOIST_P-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[ADD]], [[IF_THEN]] ], [ [[CALL8]], [[IF_END]] ]
+; HOIST_P-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %call = tail call ptr @createptr(i32 %c)
+  %vtable = load ptr, ptr %call, align 8
+  %0 = load ptr, ptr %vtable, align 8
+  %call1 = tail call i32 %0(ptr %call)
+  %rem = srem i32 %call1, 5
+  %cmp = icmp eq i32 %rem, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %vtable2 = load ptr, ptr %call, align 8
+  %vfn3 = getelementptr inbounds ptr, ptr %vtable2, i64 1
+  %1 = load ptr, ptr %vfn3, align 8
+  %call4 = tail call i32 %1(ptr %call, i32 %a, i32 %b), !prof !0
+  %call5 = tail call i32 @func2(i32 %b, i32 %a)
+  %add = add nsw i32 %call5, %call4
+  br label %cleanup
+
+if.end:                                           ; preds = %entry
+  %vtable6 = load ptr, ptr %call, align 8
+  %vfn7 = getelementptr inbounds ptr, ptr %vtable6, i64 1
+  %2 = load ptr, ptr %vfn7, align 8
+  %call8 = tail call i32 %2(ptr %call, i32 %a, i32 %b), !prof !1
+  br label %cleanup
+
+cleanup:                                          ; preds = %if.end, %if.then
+  %retval.0 = phi i32 [ %add, %if.then ], [ %call8, %if.end ]
+  ret i32 %retval.0
+}
+
+declare ptr @createptr(i32)
+declare i32 @func2(i32, i32)
+
+!0 =!{!"VP", i32 0, i64 1600, i64 12345, i64 1030, i64 678, i64 410}
+!1 =!{!"VP", i32 0, i64 1601, i64 54321, i64 1030, i64 678, i64 410}

llvm/test/Transforms/SimplifyCFG/preserve-call-metadata-in-sink.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --version 2
+; RUN: opt < %s -passes='simplifycfg<sink-common-insts;no-hoist-common-insts>' -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s --check-prefix=SINK
+; RUN: opt < %s -passes='simplifycfg<sink-common-insts;no-hoist-common-insts;preserve-indirect-call-inst-with-prof-in-hoist-and-sink>' -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s --check-prefix=SINK_P
+
+; IR @call_not_sinked is generated based on the following C++ code, with manually annotated !prof
+; Note 'd->func1' and 'd->func2' are two virtual functions with different offsets so could have different value profiles.
+; Without preserving call instructions with !prof, call instructions are simplified to one with selected offsets.
+; class Base {
+;    public:
+;    virtual int func() = 0;
+;    virtual int func1(int a, int b) = 0;
+;    virtual int func2(int a, int b) = 0;
+; };
+;
+; Base* createptr(int c);
+;
+; int func(int x, int a, int b, int c) {
+;    Base* d = createptr(c);
+;    if (x % 1000 == 0)
+;      return d->func1(a, b);
+;    return d->func2(a, b);
+; }
+define i32 @call_not_sinked(i32 %x, i32 %a, i32 %b, i32 %c) {
+; SINK-LABEL: define i32 @call_not_sinked
+; SINK-SAME: (i32 [[X:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
+; SINK-NEXT:  entry:
+; SINK-NEXT:    [[CALL:%.*]] = tail call ptr @createptr(i32 [[C]])
+; SINK-NEXT:    [[REM:%.*]] = srem i32 [[X]], 1000
+; SINK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 0
+; SINK-NEXT:    [[DOT:%.*]] = select i1 [[CMP]], i64 1, i64 2
+; SINK-NEXT:    [[VTABLE2:%.*]] = load ptr, ptr [[CALL]], align 8
+; SINK-NEXT:    [[VFN3:%.*]] = getelementptr inbounds ptr, ptr [[VTABLE2]], i64 [[DOT]]
+; SINK-NEXT:    [[TMP0:%.*]] = load ptr, ptr [[VFN3]], align 8
+; SINK-NEXT:    [[CALL4:%.*]] = tail call i32 [[TMP0]](ptr [[CALL]], i32 [[A]], i32 [[B]])
+; SINK-NEXT:    ret i32 [[CALL4]]
+;
+; SINK_P-LABEL: define i32 @call_not_sinked
+; SINK_P-SAME: (i32 [[X:%.*]], i32 [[A:%.*]], i32 [[B:%.*]], i32 [[C:%.*]]) {
+; SINK_P-NEXT:  entry:
+; SINK_P-NEXT:    [[CALL:%.*]] = tail call ptr @createptr(i32 [[C]])
+; SINK_P-NEXT:    [[REM:%.*]] = srem i32 [[X]], 1000
+; SINK_P-NEXT:    [[CMP:%.*]] = icmp eq i32 [[REM]], 0
+; SINK_P-NEXT:    br i1 [[CMP]], label [[IF_THEN:%.*]], label [[IF_END:%.*]]
+; SINK_P:       if.then:
+; SINK_P-NEXT:    [[VTABLE:%.*]] = load ptr, ptr [[CALL]], align 8
+; SINK_P-NEXT:    [[VFN:%.*]] = getelementptr inbounds ptr, ptr [[VTABLE]], i64 1
+; SINK_P-NEXT:    [[TMP0:%.*]] = load ptr, ptr [[VFN]], align 8
+; SINK_P-NEXT:    [[CALL1:%.*]] = tail call i32 [[TMP0]](ptr [[CALL]], i32 [[A]], i32 [[B]])
+; SINK_P-NEXT:    br label [[CLEANUP:%.*]]
+; SINK_P:       if.end:
+; SINK_P-NEXT:    [[VTABLE2:%.*]] = load ptr, ptr [[CALL]], align 8
+; SINK_P-NEXT:    [[VFN3:%.*]] = getelementptr inbounds ptr, ptr [[VTABLE2]], i64 2
+; SINK_P-NEXT:    [[TMP1:%.*]] = load ptr, ptr [[VFN3]], align 8
+; SINK_P-NEXT:    [[CALL4:%.*]] = tail call i32 [[TMP1]](ptr [[CALL]], i32 [[A]], i32 [[B]]), !prof [[PROF0:![0-9]+]]
+; SINK_P-NEXT:    br label [[CLEANUP]]
+; SINK_P:       cleanup:
+; SINK_P-NEXT:    [[RETVAL_0:%.*]] = phi i32 [ [[CALL1]], [[IF_THEN]] ], [ [[CALL4]], [[IF_END]] ]
+; SINK_P-NEXT:    ret i32 [[RETVAL_0]]
+;
+entry:
+  %call = tail call ptr @createptr(i32 %c)
+  %rem = srem i32 %x, 1000
+  %cmp = icmp eq i32 %rem, 0
+  br i1 %cmp, label %if.then, label %if.end
+
+if.then:                                          ; preds = %entry
+  %vtable = load ptr, ptr %call, align 8
+  %vfn = getelementptr inbounds ptr, ptr %vtable, i64 1
+  %0 = load ptr, ptr %vfn
+  %call1 = tail call i32 %0(ptr %call, i32 %a, i32 %b)
+  br label %cleanup
+
+if.end:                                           ; preds = %entry
+  %vtable2 = load ptr, ptr %call, align 8
+  %vfn3 = getelementptr inbounds ptr, ptr %vtable2, i64 2
+  %1 = load ptr, ptr %vfn3
+  %call4 = tail call i32 %1(ptr %call, i32 %a, i32 %b), !prof !0
+  br label %cleanup
+
+cleanup:                                          ; preds = %if.end, %if.then
+  %retval.0 = phi i32 [ %call1, %if.then ], [ %call4, %if.end ]
+  ret i32 %retval.0
+}
+
+declare ptr @createptr(i32)
+
+!0 =!{!"VP", i32 0, i64 1600, i64 12345, i64 1030, i64 678, i64 410}