Page MenuHomePhabricator

[SampleFDO] Another fix to prevent repeated indirect call promotion in sample loader pass
ClosedPublic

Authored by wmi on Feb 23 2021, 5:45 PM.

Details

Summary

In https://reviews.llvm.org/rG5fb65c02ca5e91e7e1a00e0efdb8edc899f3e4b9, to prevent repeated indirect call promotion for the same indirect call and the same target, we use zero-count value profile to indicate an indirect call has been promoted for a certain target. We removed PromotedInsns cache in the same patch. However, there was a problem in that patch described below, and that problem led me to add PromotedInsns back as a mitigation in https://reviews.llvm.org/rG4ffad1fb489f691825d6c7d78e1626de142f26cf.

When we get value profile from metadata by calling getValueProfDataFromInst, we need to specify the maximum possible number of values we expect to read. We uses MaxNumPromotions in the last patch so the maximum number of value information extracted from metadata is MaxNumPromotions. If we have many values including zero-count values when we write the metadata, some of them will be dropped when we read them because we only read MaxNumPromotions values. It will allow repeated indirect call promotion again. We need to make sure if there are zero-count values, those values need to be saved into or extracted from metadata with higher priority than other non-zero count values.

The patch fixed that problem. When we prepare to update the metadata in updateIDTMetaData, we will sort the values first and extract only MaxNumPromotions values to write into metadata. We will select values in such order: first try to extract zero-count values, then extract the values with the highest profile count, until we have MaxNumPromotions values to write. In this way, if we have equal to or less than MaxNumPromotions of zero-count values, they will all be kept in metadata and will be read without problem. If we have more than MaxNumPromotions of zero-count values, we will only save MaxNumPromotions zero-count values maximally. In such case, we have logic in place in doesHistoryAllowICP to guarantee no more indirect call promotion in sample loader pass will happen for the indirect call, because it has been promoted enough.

With this change, now we can remove PromotedInsns without problem.

Diff Detail

Event Timeline

wmi created this revision.Feb 23 2021, 5:45 PM
wmi requested review of this revision.Feb 23 2021, 5:45 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 23 2021, 5:45 PM

The logic seems complicated. Is it better to use (uint64)-1 as the special value to mark promoted candidates?
( I posted this comment on the wrong thread).

wmi added a comment.Feb 23 2021, 8:53 PM

The logic seems complicated. Is it better to use (uint64)-1 as the special value to mark promoted candidates?
( I posted this comment on the wrong thread).

That is a very good suggestion and should simplify selectCallTargets a lot. Will try it.

wmi updated this revision to Diff 327938.Mar 3 2021, 3:05 PM

Address David's comment. By using -1 to represent targets which have been promoted in the value profile, we only have to sort the values in count descending order, and choose the top MaxNumPromotions values whenever we store or load the values from value profile.

hoy added a comment.Mar 3 2021, 4:18 PM

Thank for the fix. I've been seeing an assert failure related to ICP. Do you think that can be fixed by this patch?

llvm/lib/Analysis/IndirectCallPromotionAnalysis.cpp:78: uint32_t llvm::ICallPromotionAnalysis::getProfitablePromotionCandidates(const llvm::Instruction*, uint32_t, uint64_t): Assertion `Count <= RemainingCount' failed.

davidxl added inline comments.Mar 3 2021, 4:26 PM
llvm/lib/ProfileData/InstrProf.cpp
1017

Does total count include the magic num? It should not.

llvm/lib/Transforms/IPO/SampleProfile.cpp
716–717

early return if not valid

747–748

document 'Sum' What is the difference to TotalCount?

782

= NOMORE_ICP_MAGICNUM

785

can it become negative?

wmi added a comment.Mar 3 2021, 4:39 PM
In D97350#2601716, @hoy wrote:

Thank for the fix. I've been seeing an assert failure related to ICP. Do you think that can be fixed by this patch?

llvm/lib/Analysis/IndirectCallPromotionAnalysis.cpp:78: uint32_t llvm::ICallPromotionAnalysis::getProfitablePromotionCandidates(const llvm::Instruction*, uint32_t, uint64_t): Assertion `Count <= RemainingCount' failed.

Likely. I don't know the exact reason why the old patch triggered the assertion, but it is likely the patch will fix it because it makes the value count logic more easy to follow.

wenlei added inline comments.Mar 3 2021, 4:41 PM
llvm/lib/Transforms/IPO/SampleProfile.cpp
716–717

bail out the loop if NumPromoted > MaxNumPromotions?

wmi marked 2 inline comments as done.Mar 3 2021, 5:21 PM
wmi added inline comments.
llvm/lib/ProfileData/InstrProf.cpp
1017

total count won't include the magic number. It is not got by adding all the value counts in the value profile, but precomputed before the value profile is written.

llvm/lib/Transforms/IPO/SampleProfile.cpp
716–717

Good idea.

747–748

Done. Also rename TotalCount to OldSum so it is clearer that is the old total count in value profile and will be replaced by Sum if Sum is not 0.

785

It won't. Sum is got by adding up the counts of all the targets so it should never be less than Data.Count. I add an assertion for it.

wmi updated this revision to Diff 327969.Mar 3 2021, 5:23 PM

Address David, Wenlei and Hongtao's comments.

hoy added inline comments.Mar 3 2021, 6:07 PM
llvm/lib/Transforms/IPO/SampleProfile.cpp
780

IIUC, Data is from profile, why can it be -1?

785

Looks like Sum could be zero in one of the callsites of updateIDTMetaData where no value is passed and the default value 0 is used.

wmi added inline comments.Mar 3 2021, 7:34 PM
llvm/lib/Transforms/IPO/SampleProfile.cpp
780

It is used to mark a target as being promoted (updateIDTMetaData is called in two places, one place to update the profile and another place to mark a target being promoted)

785

If Sum is zero, it is used to mark a specific target to be promoted already. In that case, CallTargets will only contain one element and the count of the element is NOMORE_ICP_MAGICNUM, so it won't take this branch.

I will add an assertion to make the assumption explicit.
assert(Sum != 0 || (CallTargets.size() == 1 && CallTargets[0].Count == NOMORE_ICP_MAGICNUM));

wmi updated this revision to Diff 328008.Mar 3 2021, 8:18 PM

Address Hongtao's comment.

hoy added inline comments.Mar 3 2021, 10:38 PM
llvm/lib/Transforms/IPO/SampleProfile.cpp
780

I see.

785

I see. Maybe don't give Sum a default value, instead, explicit pass the value 0 in one of the callsite?

790

Nit: overriden.

wmi added inline comments.Mar 4 2021, 1:23 PM
llvm/lib/Transforms/IPO/SampleProfile.cpp
785

Ok, done.

790

Fixed.

wmi updated this revision to Diff 328293.Mar 4 2021, 1:24 PM

Address Hongtao's comment.

hoy accepted this revision.Mar 4 2021, 1:41 PM

LGTM, thanks.

This revision is now accepted and ready to land.Mar 4 2021, 1:41 PM
This revision was landed with ongoing or failed builds.Mar 4 2021, 6:44 PM
This revision was automatically updated to reflect the committed changes.