This is an archive of the discontinued LLVM Phabricator instance.

Use getEdgeProbability() instead of getEdgeWeight() in BFI and remove getEdgeWeight() interfaces from MBPI.
ClosedPublic

Authored by congh on Dec 14 2015, 2:34 AM.

Details

Summary

This patch remove all getEdgeWeight() interfaces from CodeGen directory. As getEdgeProbability() is a little more expensive than getEdgeWeight(), I will compose a patch soon in which BPI only stores probabilities instead of edge weights so that getEdgeProbability() will have O(1) time.

Diff Detail

Repository
rL LLVM

Event Timeline

congh updated this revision to Diff 42696.Dec 14 2015, 2:34 AM
congh retitled this revision from to Use getEdgeProbability() instead of getEdgeWeight() in BFI and remove getEdgeWeight() interfaces from MBPI..
congh updated this object.
congh added a reviewer: davidxl.
congh added a subscriber: llvm-commits.
davidxl added inline comments.Dec 14 2015, 12:21 PM
include/llvm/Analysis/BlockFrequencyInfoImpl.h
1193 ↗(On Diff #42696)

Can you add a file local wrapper function in this file

inline static uint32_t getEdgeWeight(... ) { return ... getNumerator()...)

test/Analysis/BlockFrequencyInfo/bad_input.ll
13 ↗(On Diff #42696)

What makes this diff?

congh updated this revision to Diff 42793.Dec 14 2015, 3:47 PM

Update the patch according to David's comment.

include/llvm/Analysis/BlockFrequencyInfoImpl.h
1193 ↗(On Diff #42696)

This function will have some weird parameters like successor iterator and BPI, I instead created a wrapper convertBranchProbabilityToWeight() to convert BP into weight.

test/Analysis/BlockFrequencyInfo/bad_input.ll
13 ↗(On Diff #42696)

The weights 0 will be transformed into 1 in BFI so we will get 1 and 3 as the actual weights that are used to calculate frequencies. With this patch the numerators of BP are used as weight so we will get 0 and 1<<31 (representing BP 0% and 100%) as edge weights, which are then transformed into 1 and 1<<31 later.

davidxl added inline comments.Dec 14 2015, 3:53 PM
include/llvm/Analysis/BlockFrequencyInfoImpl.h
1178 ↗(On Diff #42793)

The name is too long. How about just getWeightFromBranchProb?

test/Analysis/BlockFrequencyInfo/bad_input.ll
13 ↗(On Diff #42793)

The original code also calls into Src->getSuccProbability(Dst).getNumerator() eventually -- so the change looks like NFC -- I missed something obvious here ..

congh added inline comments.Dec 14 2015, 4:01 PM
include/llvm/Analysis/BlockFrequencyInfoImpl.h
1178 ↗(On Diff #42793)

OK.

test/Analysis/BlockFrequencyInfo/bad_input.ll
13 ↗(On Diff #42793)

The original code doesn't call Src->getSuccProbability(Dst).getNumerator(). Note that here we are using BPI not MBPI, and MBPI does have an interface getEdgeWeight() that calls getNumerator() from BP. But for BPI we don't do similar things.

congh updated this revision to Diff 42795.Dec 14 2015, 4:03 PM

Change the name convertBranchProbabilityToWeight() into getWeightFromBranchProb().

davidxl added inline comments.Dec 14 2015, 5:08 PM
test/Analysis/BlockFrequencyInfo/bad_input.ll
13 ↗(On Diff #42795)

I know FE does that (0->1) when creating MD_prof metadata. Where in BFI that does similar thing?

congh added inline comments.Dec 14 2015, 5:16 PM
test/Analysis/BlockFrequencyInfo/bad_input.ll
13 ↗(On Diff #42795)

It is done in BlockFrequencyInfoImplBase::addToDist():

bool BlockFrequencyInfoImplBase::addToDist(Distribution &Dist,

                                         const LoopData *OuterLoop,
                                         const BlockNode &Pred,
                                         const BlockNode &Succ,
                                         uint64_t Weight) {
if (!Weight)
  Weight = 1;

auto isLoopHeader = [&OuterLoop](const BlockNode &Node) {
  return OuterLoop && OuterLoop->isHeader(Node);
};

...
davidxl edited edge metadata.Dec 14 2015, 9:58 PM

Ok. This is a case where loop exit edge is 'never' taken where the loop backedge is executed. With instrumentation based PGO, even without FE fix up of the 0 weight edge, such as scenario (aka, bad meta data) will never occur, so whatever output of BFI will be fine.

However, with AutoFDO, such MD_prof data can actually be generated . For instance, the function has a single BB loop, and only the BB in the loop has some samples but the entry/exit BB has none.

The BFI result before this patch will most likely under-estimate the loop trip count, while with this patch, it will most likely over-estimate it. I think neither results are ideal, and AutoFDO needs to do something (apply some heuristic) to prevent such case from being generated. +dehao and +dnovillo for comments.

For the following CFG:

BB1(weight:100)
BB2(weight:1000)
BB3(weight:100)

BB1->BB2(probability: 0%)
BB1->BB3(probability: 100%)
BB2->BB2(probability: 100%)
BB2->BB3(probability: 0%)

Is there a way we can rebuild BB weights from probability?
Dehao

davidxl accepted this revision.Dec 18 2015, 11:40 AM
davidxl edited edge metadata.

Looks good to me, but make sure AutoFDO handles (0 weight) case as well.

This revision is now accepted and ready to land.Dec 18 2015, 11:40 AM
congh added a comment.Dec 18 2015, 1:21 PM

Looks good to me, but make sure AutoFDO handles (0 weight) case as well.

I will work with Dehao to make sure this will be done.

This revision was automatically updated to reflect the committed changes.