This is an archive of the discontinued LLVM Phabricator instance.

[PGO] Handle cases of non-instrument BBs
ClosedPublic

Authored by xur on May 30 2019, 1:51 PM.

Details

Summary

As shown in PR41279, some basic blocks (such as catchswitch) cannot be instrumented.
This patch filters out these BBs in PGO instrumentation.

Diff Detail

Repository
rL LLVM

Event Timeline

xur created this revision.May 30 2019, 1:51 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 30 2019, 1:51 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
xur added a comment.May 30 2019, 1:53 PM

Another change of this patch is to move down statistic collection code for critical edge. I think this is a better place.

davidxl added inline comments.May 30 2019, 2:02 PM
llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp
783 ↗(On Diff #202293)

Add a comment here explaining the predicate.

xur updated this revision to Diff 202748.Jun 3 2019, 10:16 AM

My previous patch was not complete -- we need to set the profile count to the fail-to-instrument edge. Otherwise, we cannot propagate the counts in the CFG.
The new patch has this part of change.
Updated the test to test the profile-use.

Also added comments suggested by David.

davidxl added inline comments.Jun 6 2019, 11:12 AM
llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp
1090 ↗(On Diff #202748)

The change seems pretty substantial. Is it enough just do one pass and set all edges not already with a valid count to zero count?

xur marked an inline comment as done.Jun 7 2019, 10:18 AM
xur added inline comments.
llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp
1090 ↗(On Diff #202748)

After MST, we mark the edges that will be instrumented. The instrumentation needs to be done in BB. So we have getInstrBB() to decide which BB to instrument. in getInstrBB, we split BB for critical edges, so edges can be added and remove. BB could be added too.

Previous implementation assumes that all edges that marked instrument will be instrumented. So we have one pass that sets the instrumented BB and the instrumented edges.
With that assumption, all the instrumented edges will have a valid count. After that we can populate the count to all the remaining edges.

Now, some of the BBs that supposed to instrumented has no count. Some of the instrumented edges have no count, so the population fails.
I fix this by setting counts in two steps: first step to read all the counts in profile files to set count for the instrumented BB.
In the second step, I check all the instrumented edges: I should get the counts from source or sink. Otherwise, it should be case of not able to instrument. I set the count to 0.

Doing this in one step is more tricky. Note that previously set the population data structure (OutEdges, InEdges) after the getInstrBB(). This way we don't need to update them for split BBs.

I think doing this in two steps simplifies the code and is clearly conceptually.

We probably should not mark all edges as valid in reading count step. This could mask some errors in count population. The valid bit should be set by count population, I think.

davidxl added inline comments.Jun 7 2019, 10:25 AM
llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp
1090 ↗(On Diff #202748)

I understand the need to do two pass annotation, but in the first pass when BB is annotated with count, setting inedge and outedge count like

if (Info.InEdges.size() == 1) {

   ....
}

is still correct.

What I meant is that why can't the second pass be as simple as just mark remaining edges (not annotated in the first pass) with zero count?

xur marked an inline comment as done.Jun 7 2019, 10:33 AM
xur added inline comments.
llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp
1090 ↗(On Diff #202748)

InEdges is initialized after the first step. So that piece code is effectively dead code.

davidxl added inline comments.Jun 10 2019, 9:33 AM
llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp
1090 ↗(On Diff #202748)

Can the InEdges/OutEdges be set in getInstrumentedBBs? It seems a natural place to set the CFG after critical edge split.

xur marked an inline comment as done.Jun 10 2019, 9:47 AM
xur added inline comments.
llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp
1090 ↗(On Diff #202748)

Do you mean setting the InEdges/OutEdges before getInstrumentedBBs() and updating them when splitting?
Yes. It can be done.

I chose not to that for two reasons:
(1) the edges are stored in vectors. Deletion in a vector is not efficient.
(2) InEdges/OutEdges are only used in fdo-use compilation. getInstrumentedBBs() is shared by fdo-use and fdo-instrument. Doing it in instrumentation is redundant.

davidxl added inline comments.Jun 10 2019, 9:51 AM
llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp
1090 ↗(On Diff #202748)

No need to update. Just split the following from popluteCounters and put it at the end of getInstrumentedBBs:

for (auto &E : FuncInfo.MST.AllEdges) {
  if (E->Removed)
    continue;

  const BasicBlock *SrcBB = E->SrcBB;
  const BasicBlock *DestBB = E->DestBB;
  UseBBInfo &SrcInfo = getBBInfo(SrcBB);
  UseBBInfo &DestInfo = getBBInfo(DestBB);
  SrcInfo.OutEdges.push_back(E.get());
  DestInfo.InEdges.push_back(E.get());

}

xur marked an inline comment as done.Jun 10 2019, 10:24 AM
xur added inline comments.
llvm/lib/Transforms/Instrumentation/PGOInstrumentation.cpp
1090 ↗(On Diff #202748)

getInstrumentedBBs() is a template funciton. The one instantiated for instrumentation does not have InEdges/OutEdges (it uses BBInfo). We would need a specialization for UseBBInfo type.

This can be handled this way:

BBInfo &SrcInfo = getBBInfo(SrcBB);    // BBInfo is the template type
BBInfo &DestInfo = getBBInfo(DestBB);
SrcInfo.addOutEdge(E.get());
DestInfo.addInEdge(E.get());

For base class BBInfo, addOutEdge, addInEdge will be empty, while it is defined for UseBBInfo class.

By so doing, the code is more readable.

xur updated this revision to Diff 203903.Jun 10 2019, 2:53 PM

Integrated David's review suggestions.

xur added a comment.Jun 10 2019, 2:54 PM

This can be handled this way:

BBInfo &SrcInfo = getBBInfo(SrcBB);    // BBInfo is the template type
BBInfo &DestInfo = getBBInfo(DestBB);
SrcInfo.addOutEdge(E.get());
DestInfo.addInEdge(E.get());

For base class BBInfo, addOutEdge, addInEdge will be empty, while it is defined for UseBBInfo class.

By so doing, the code is more readable.

Done.

davidxl accepted this revision.Jun 10 2019, 2:58 PM

lgtm

This revision is now accepted and ready to land.Jun 10 2019, 2:58 PM
This revision was automatically updated to reflect the committed changes.