This is an archive of the discontinued LLVM Phabricator instance.

Split IndirectBr critical edges before PGO gen/use passes.
ClosedPublic

Authored by hjyamauchi on Nov 30 2017, 6:12 PM.

Details

Summary

The PGO gen/use passes currently fail with an assert failure if there's a
critical edge whose source is an IndirectBr instruction and that edge
needs to be instrumented.

To avoid this in certain cases, split IndirectBr critical edges in the PGO
gen/use passes. This works for blocks with single indirectbr predecessors,
but not for those with multiple indirectbr predecessors (splitting an
IndirectBr critical edge isn't always possible.)

Event Timeline

hjyamauchi created this revision.Nov 30 2017, 6:12 PM

The PGO gen/use passes currently fail with an assert failure if there's a critical edge whose source is an IndirectBr instruction.

findIBRPredecessor will fail for blocks with multiple multiple indirectbr predecessors. And then you're back at square one, with an assertion failure.

davidxl edited edge metadata.Dec 1 2017, 10:28 AM
  1. As Eli pointed out, findIBRpredecessor may return null when there are multiple such predecessors, so perhaps create a new interface to return all such predecessors?
  1. it is probably better to split out the refactoring part of the patch.
lib/Passes/PassBuilder.cpp
519

this is common to Use and Gen, so it is possible to move it into the previous SCC pipeline after InstCombinePass.

The PGO gen/use passes currently fail with an assert failure if there's a critical edge whose source is an IndirectBr instruction.

findIBRPredecessor will fail for blocks with multiple multiple indirectbr predecessors. And then you're back at square one, with an assertion failure.

True. This change (and SplitIndirectBrCriticalEdges) isn't intended to handle all possible cases (see the comment in BasicBlockUtils.h). It's an improvement in that it can handle single indirectbr predecessor cases.

hjyamauchi added inline comments.Dec 4 2017, 10:44 AM
lib/Passes/PassBuilder.cpp
519

Do you mean moving this to after line 498 above? If so, would it not work if isOptimizingForSize() is true?

Created https://reviews.llvm.org/D40750 for the refactoring part.

hjyamauchi updated this revision to Diff 125431.Dec 4 2017, 3:26 PM

Rebased after D40750.

Changed the SplitIndirectBrCriticalEdges pass to a function pass.

Moved the SplitIndirectBrCriticalEdges pass into the previous SCC pipeline.

hjyamauchi marked an inline comment as done.Dec 4 2017, 3:26 PM
hjyamauchi edited the summary of this revision. (Show Details)Dec 4 2017, 3:30 PM
hjyamauchi edited the summary of this revision. (Show Details)

It's an improvement in that it can handle single indirectbr predecessor cases.

It's not good to kick the can down the road like this. If an IR optimization pass is crashing, you should fix it by fixing that pass, not by changing the default pass pipeline to avoid generating IR which triggers the crash.

This can be done in the PGO pass itself before the MST is formed. BFI has update interface such as setBlockFreq. The update can use simple heuristic to distribute the frequency.

hjyamauchi updated this revision to Diff 125662.Dec 5 2017, 6:05 PM

Split indirectbr critical edges in the PGO gen/use passes.

hjyamauchi edited the summary of this revision. (Show Details)Dec 5 2017, 6:06 PM
hjyamauchi updated this revision to Diff 125842.Dec 6 2017, 4:27 PM

Split only the IndirectBr critical edges that need to be split rather than
all. This avoids changing the indirectbr.ll test.

Minor cleanup.

hjyamauchi edited the summary of this revision. (Show Details)Dec 6 2017, 4:49 PM
davidxl added inline comments.Dec 7 2017, 5:21 PM
lib/Transforms/Instrumentation/PGOInstrumentation.cpp
567

Why not splitting the edges before MST is computed?

hjyamauchi updated this revision to Diff 126079.Dec 7 2017, 5:26 PM

Detect indirectbr critical non-MST edges in CFGMST and if none, avoid iterating
over the edges in FuncPGOInstrumentation().

hjyamauchi added inline comments.Dec 7 2017, 5:41 PM
lib/Transforms/Instrumentation/PGOInstrumentation.cpp
567

This is trying to not split unless it's necessary (that is, if it's a non-MST indirectbr critical edges.) For that, we need to compute the MST once before making a decision to split. We could split all indirectbr critical edges unconditionally before computing the MST, but I thought it may be somewhat nicer that way as it would minimize CFG changes (eg, the indirectbr.ll test previously had to be changed even though it didn't suffer from this assert failure.)

davidxl added inline comments.Dec 8 2017, 9:30 AM
lib/Transforms/Instrumentation/PGOInstrumentation.cpp
572

It seems cleaner to move the IndirectBrTargets collection inside MST's buildEdges method.

576

There seems no guarantee that the non-split indirectBR critical edges will be be in MST when cfgmst is recomputed.

hjyamauchi added inline comments.Dec 11 2017, 10:47 AM
lib/Transforms/Instrumentation/PGOInstrumentation.cpp
576

Good point. I'll go back to splitting all indirectBR critical edges before computing the MST (the previous diff).

Going back to Diff 125662.

hjyamauchi edited the summary of this revision. (Show Details)Dec 11 2017, 2:52 PM
hjyamauchi marked 2 inline comments as done.
hjyamauchi added inline comments.
lib/Transforms/Instrumentation/PGOInstrumentation.cpp
572

This comment doesn't apply any more.

davidxl accepted this revision.Dec 11 2017, 6:54 PM

lgtm

This revision is now accepted and ready to land.Dec 11 2017, 6:54 PM
hjyamauchi marked an inline comment as done.

Rebased.

hjyamauchi closed this revision.Dec 12 2017, 11:08 AM

You still never answered the question of what happens when there's multiple indirectbrs whose edges can't be split.

I think it will be an assert failure like before. Like said above, this patch isn't intended to handle that case.