This is an archive of the discontinued LLVM Phabricator instance.

[JumpThreading] Call eraseBlock when folding a conditional branch
ClosedPublic

Authored by kazu on Nov 15 2020, 6:12 PM.

Details

Summary

This patch teaches the jump threading pass to call BPI->eraseBlock
when it folds a conditional branch.

Without this patch, BranchProbabilityInfo could end up with stale edge
probabilities for the basic block containing the conditional branch --
one edge probability with less than 1.0 and the other for a removed
edge.

This patch is one of the steps before we can safely re-apply D91017.

Diff Detail

Event Timeline

kazu created this revision.Nov 15 2020, 6:12 PM
Herald added a project: Restricted Project. · View Herald TranscriptNov 15 2020, 6:12 PM
kazu requested review of this revision.Nov 15 2020, 6:12 PM

The patch looks good, but I have some concerns.

This patch is one of the steps before we can safely re-apply D91017.

Will there be any other patches? Please add links if any and dependencies to D91017.
Could you please describe the problem that prevents D91017?

llvm/test/Transforms/JumpThreading/thread-prob-2.ll
13

Would it be possible to add checks that describe the CFG change like:
; CHECK-LABEL: @foo
; CHECK: bb.entry:
; CHECK-NEXT: br i1 %cond, label %bb.31, label %bb.12
; CHECK-NOT: bb.cond:

kazu added a comment.Nov 15 2020, 9:31 PM

The patch looks good, but I have some concerns.

This patch is one of the steps before we can safely re-apply D91017.

Will there be any other patches? Please add links if any and dependencies to D91017.
Could you please describe the problem that prevents D91017?

We need more calls to BPI->eraseBlock() if we want to require all basic blocks, including dead ones yet to be removed, to satisfy:

SrcProbs.size() == Src->getTerminator()->getNumSuccessors()

at all times during the jump threading pass except when it is actively modifying the CFG.

If we are OK with the consistency just for those basic blocks that are live, then the call to BPI->eraseBlock() being introduced in this patch may be enough. (I haven't checked.)

The problem caused by D91017 is due to the jump threading pass not updating edge probabilities (as addressed in this patch).

Once this patch lands, I'm going to build large pieces of software with PGO enabled to see what else is broken.

kazu updated this revision to Diff 305412.Nov 15 2020, 9:41 PM

Updated the testcase.

kazu marked an inline comment as done.Nov 15 2020, 9:41 PM

The problem caused by D91017 is due to the jump threading pass not updating edge probabilities (as addressed in this patch).

D91017 is NFC, why does it reveal the bug in JumpThreading while it has not been seen without D91017? Can we create a test case, which passes without D91017 but fails with it?

kazu added a comment.Nov 15 2020, 9:57 PM

The problem caused by D91017 is due to the jump threading pass not updating edge probabilities (as addressed in this patch).

D91017 is NFC, why does it reveal the bug in JumpThreading while it has not been seen without D91017? Can we create a test case, which passes without D91017 but fails with it?

D91017 introduces an additional assert in getEdgeProbability(const BasicBlock *Src, const BasicBlock *Dst), and that's causing trouble. The testcase in this patch should serve the testcase you are describing.

Once I do enough testing with profile guided optimizations to exercise BPI related code in the jump threading pass, I'm going to re-introduce the assert above by itself without D91017, wait for a bit, and then re-apply D91017. Thoughts?

yrouban accepted this revision.Nov 15 2020, 10:10 PM

agree. See my comments in D91017.

This revision is now accepted and ready to land.Nov 15 2020, 10:10 PM
This revision was landed with ongoing or failed builds.Nov 15 2020, 10:29 PM
This revision was automatically updated to reflect the committed changes.