This is an archive of the discontinued LLVM Phabricator instance.

[BPI] Look-up tables for non-loop branches. NFC.
ClosedPublic

Authored by SjoerdMeijer on Nov 16 2021, 9:17 AM.

Details

Summary

I wanted to check and cross reference which heuristics we have implemented and didn't find it very easy to extract that information because everything is inlined in different functions. That's why I have created different lookup tables that should make this clearer.

Diff Detail

Event Timeline

SjoerdMeijer created this revision.Nov 16 2021, 9:17 AM
SjoerdMeijer requested review of this revision.Nov 16 2021, 9:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptNov 16 2021, 9:17 AM
nikic resigned from this revision.Nov 16 2021, 11:20 AM

This doesn't really look better than the previous code to me personally, but I'm not involved with BPI either...

yrouban added inline comments.Nov 16 2021, 5:12 PM
llvm/lib/Analysis/BranchProbabilityInfo.cpp
132–133

not needed

instead of storing a bool value (swap the probability or not) it would be better to store final array of branch probabilities to set so it would not need to define probabilities every time and optionally swap them.

auto Search = PointerTable.find(CI->getPredicate());
if (Search == PointerTable.end())
  return false;
setEdgeProbability(BB, Search->second);
return true;
llvm/lib/Analysis/BranchProbabilityInfo.cpp
87

+const

Thanks for the suggestion, the probabilities are now encoded directly into the tables.

I thought this table based approach to be compacter and thus easier to check. If this is not the case, we can revisit it, or I can abandon change as as I don't have too strong opinions (but again, I thought it would help a bit) . And while doing this, I noticed tests for pointer heuristics are missing, so added them.

yrouban accepted this revision.Nov 18 2021, 5:56 PM
yrouban added inline comments.
llvm/lib/Analysis/BranchProbabilityInfo.cpp
180–181

I do not see any diff between these two lines. I think one is enough: p != q -> Likely.

182

value followed by comment would be more concise, like the following:

{ ICmpInst::ICMP_NE, { PtrTakenProb, PtrUntakenProb } }, // p != q  ->  Likely.
This revision is now accepted and ready to land.Nov 18 2021, 5:56 PM

Thanks for reviewing, and I will address your comments before committing.

This revision was landed with ongoing or failed builds.Nov 22 2021, 2:31 AM
This revision was automatically updated to reflect the committed changes.