This is an archive of the discontinued LLVM Phabricator instance.

[JT][CT] Preserve exisiting BPI/BFI during JumpThreading
ClosedPublic

Authored by ebrevnov on Oct 27 2022, 2:39 AM.

Details

Summary

Currently, JT creates and updates local instances of BPI\BFI. As a result global ones have to be invalidated if JT made any changes.
In fact, JT doesn't use any information from BPI/BFI for the sake of the transformation itself. It only creates BPI/BFI to keep them up to date. But since it updates local copies (besides cases when it updates profile metadata) it just waste of time.

Current patch is a rework of D124439. D124439 makes one step and replaces local copies with global ones retrieved through AnalysisPassManager. Here we do one more step and don't create BPI/BFI if the only reason of creation is to keep BPI/BFI up to date. Overall logic is the following. If there is cached BPI/BFI then update it along the transformations. If there is no existing BPI/BFI, then create it only if it is required to update profile metadata.

Please note if BPI/BFI exists on exit from JT (either cached or created) it is always up to date and no reason to invalidate it.

Diff Detail

Event Timeline

ebrevnov created this revision.Oct 27 2022, 2:39 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 27 2022, 2:39 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
ebrevnov requested review of this revision.Oct 27 2022, 2:39 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 27 2022, 2:39 AM
ebrevnov retitled this revision from [JT] Preserve exisiting BPI/BFI during JumpThreading to [JT][CT] Preserve exisiting BPI/BFI during JumpThreading.
mkazantsev added inline comments.Nov 2 2022, 5:03 AM
llvm/lib/Transforms/Scalar/JumpThreading.cpp
326

I guess old PM support is in decline, not sure if we want this here...

2563

nit: auto *

3183

Would be nice to verify DT here in assertion mode.

3189

They are only called together; do we really need two separate functions?

llvm/test/Transforms/JumpThreading/threading_prof2.ll
41

This looks strange. What's the explanation here, is the old profile wrong?

ebrevnov added inline comments.Nov 3 2022, 1:42 AM
llvm/lib/Transforms/Scalar/JumpThreading.cpp
326

We don't change legacy behavior in any change. This is just a mechanical change to keep code compilable.

2563

Ok, will fix

3189

There are number of place where we request BPI only...

ebrevnov added inline comments.Nov 3 2022, 1:42 AM
llvm/lib/Transforms/Scalar/JumpThreading.cpp
326

"in any change." -> "in any way."

3183

I think it makes sense to perform "fast" verification here and "full" at the end of the pass under EXPENSIVE_CHECKS guard. WDYT?

llvm/test/Transforms/JumpThreading/threading_prof2.ll
41

Yes, old behavior is wrong. Essentially it's just stale initial profile. Since initial probability to go from bb5 to bb7 is equal to calculated probability to go from bb to bb7 that means new probability to go from bb5 to bb7 is 0.

ebrevnov updated this revision to Diff 473220.Nov 4 2022, 6:44 AM

Added DominatorTree verification. Do not preserve BPI/BFI after JumpThreading.

ebrevnov updated this revision to Diff 473223.Nov 4 2022, 6:50 AM

Minor update

Put some nits & potential bug comments. Do we know the actual CT impact of that?

@nikic could you please run your CT machinery to see if it gives something?

llvm/include/llvm/Transforms/Scalar/JumpThreading.h
79–88

Can be &Function (less changes below)

177

nit: three slashes before comments, makes sense to write them separately for both (yes, it's mostly copy-paste).

llvm/lib/Transforms/Scalar/JumpThreading.cpp
363

Why this is under NDEBUG?

364

Bad formatting

430

I think we should skil unreachable blocks here.

430

skip

1154–1155

Is it guaranteed that BPI is created by this moment? How?

Should be getOrCreateBPI?

2777

auto *

3161

nit: with out -> without (same below)

llvm/test/Transforms/JumpThreading/threading_prof2.ll
41

Got it, thanks.

ebrevnov marked 3 inline comments as done.Nov 11 2022, 1:52 AM
ebrevnov added inline comments.
llvm/include/llvm/Transforms/Scalar/JumpThreading.h
79–88

Can be &Function (less changes below)

79–88

No, it can't. It's not initialized in the constructor.

llvm/lib/Transforms/Scalar/JumpThreading.cpp
363

Because we need to flush DT at this point only if verification follows. Otherwise it's up to DTU to decide when to flush.

364

Not sure what LLVM Coding Standard says about that situation but I intentionally formatted this way to keep visual separation between real comments and commented out code.

1154–1155

No it's not guaranteed. JT doesn't use BPI/BFI for its needs. It only creates it to update BPI/BFI and profile metadata if exists. Thus if BPI exists it will be updated, otherwise no need to do anything.

Put some nits & potential bug comments. Do we know the actual CT impact of that?

@nikic could you please run your CT machinery to see if it gives something?

I don't test PGO builds, so all I can say is that this at least doesn't regress non-PGO builds...

mkazantsev accepted this revision.Nov 16 2022, 2:51 AM

LG in general, good that it won't regress standard builds. Let's give it a try.

Some nits inline, I still think that getOrCreate... could be one method.

llvm/lib/Transforms/Scalar/JumpThreading.cpp
363

Yeah, but I mean it's the end of the line anyways, and DTU will flush in the end of this function. We could just flush it here.

364

Maybe just write "we want to preserve BranchProbabilityAnalysis and BlockFrequencyAnalysis here..." and not leave the commented code? Any static analyzer will complain about it.

3183

Yes, sounds good.

3189

getOrCreateBPI/BFI are only called together.

3194

Same as above, add verification?

And if you unite them in one method, it's only needed once.

This revision is now accepted and ready to land.Nov 16 2022, 2:51 AM
ebrevnov marked an inline comment as done.Nov 16 2022, 9:57 PM
ebrevnov added inline comments.
llvm/lib/Transforms/Scalar/JumpThreading.cpp
364

Sure, can do that.

3189

Indeed, getOrCreateBPI/BFI are called together at the moment but it can change in the future. I feel in favor of leaving it as is. I don't think this is super critical. Let's leave as is if you don't mind.

3194

Fixed.

ebrevnov updated this revision to Diff 476008.Nov 16 2022, 10:04 PM
ebrevnov marked an inline comment as done.

Addressed review comments

This revision was landed with ongoing or failed builds.Nov 17 2022, 2:03 AM
This revision was automatically updated to reflect the committed changes.
ebrevnov reopened this revision.Nov 25 2022, 2:39 AM
This revision is now accepted and ready to land.Nov 25 2022, 2:39 AM
ebrevnov updated this revision to Diff 477900.Nov 25 2022, 2:39 AM

Invalidate all existing not preserved analysis before running "extrnal" analysis

ebrevnov added inline comments.Nov 25 2022, 2:42 AM
llvm/lib/Transforms/Scalar/JumpThreading.cpp
2586

This is unintentional formatting change. Please skip.

2592

This is unintentional formatting change. Please skip.

2597

This is unintentional formatting change. Please skip.

2605

This is unintentional formatting change. Please skip.

mkazantsev requested changes to this revision.Jan 10 2023, 12:38 AM

PDT seems completely irrelevant to what you are doing in this patch. If you have plans about it, I propose to split off PDT-related part into a separate patch, and make this one dedicated to BPI/BFI only.

llvm/lib/Transforms/Scalar/JumpThreading.cpp
2425

/*name boolean parameter*/?

This revision now requires changes to proceed.Jan 10 2023, 12:38 AM
ebrevnov updated this revision to Diff 488099.Jan 11 2023, 12:45 AM

Removed code related to PostDomTree + rebase

ebrevnov updated this revision to Diff 488107.Jan 11 2023, 12:57 AM

Check that (TrueWeight + FalseWeight) are not zero.

mkazantsev accepted this revision.Jan 16 2023, 3:11 AM

LG with some nits

llvm/lib/Transforms/Scalar/JumpThreading.cpp
33

Do you still need this?

422

{ } not needed

3232

{} not needed

3243

same

llvm/test/Transforms/JumpThreading/select.ll
2

Add new configuration in addition to old one?

This revision is now accepted and ready to land.Jan 16 2023, 3:11 AM
ebrevnov updated this revision to Diff 492643.Jan 26 2023, 10:26 PM
ebrevnov marked an inline comment as done.

Rebase

ebrevnov updated this revision to Diff 492652.Jan 26 2023, 11:55 PM

Added extra RUN; line into select.ll test as requested

ebrevnov marked an inline comment as done.Jan 26 2023, 11:56 PM
This revision was landed with ongoing or failed builds.Jan 27 2023, 12:00 AM
This revision was automatically updated to reflect the committed changes.
ebrevnov reopened this revision.Feb 16 2023, 12:58 AM
This revision is now accepted and ready to land.Feb 16 2023, 12:58 AM
ebrevnov updated this revision to Diff 497920.Feb 16 2023, 12:58 AM

Fixed fuchsia-x86_64-linux, ppc64le-lld-multistage-test, clang-with-lto-ubuntu buildbot failures

This revision was landed with ongoing or failed builds.Feb 16 2023, 1:08 AM
This revision was automatically updated to reflect the committed changes.