This is an archive of the discontinued LLVM Phabricator instance.

[BPI][NFC] Reuse post dominantor tree from analysis manager when available
ClosedPublic

Authored by ebrevnov on Apr 28 2020, 2:35 AM.

Details

Summary

Currenlty BPI unconditionally creates post dominator tree each time. While this is not incorrect we can save compile time by reusing existing post dominator tree (when it's valid) provided by analysis manager.

Diff Detail

Unit TestsFailed

Event Timeline

ebrevnov created this revision.Apr 28 2020, 2:35 AM
skatkov added inline comments.Apr 28 2020, 4:03 AM
llvm/include/llvm/Analysis/BranchProbabilityInfo.h
139

why not nullptr by default?

llvm/lib/Analysis/OptimizationRemarkEmitter.cpp
39

If nullptr by default above, no need in this change...

skatkov added inline comments.Apr 28 2020, 4:10 AM
llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
1775–1776

why nullptr instead of request Pass manager for analysis if it is created anyway?

llvm/lib/Transforms/Scalar/LoopPredication.cpp
365

ditto

ebrevnov marked 3 inline comments as done.Apr 29 2020, 12:50 AM
ebrevnov added inline comments.
llvm/include/llvm/Analysis/BranchProbabilityInfo.h
139

In general, default initialization is considered bad programming practice and should avoided in most cases. That doesn't mean it should never be used but this case doesn't qualify for this. In this case "nullptr" is bad default because analysis results will have lower accuracy than could. We should not "encouraging" callers to omit this argument.

llvm/lib/Analysis/OptimizationRemarkEmitter.cpp
39

Let me do a trick here. Instead of calling calculate explicitly we can pass required arguments to the constructor directly. Note that I haven't removed defaults from the constructor (at least for now). In fact the only reason stopping me from doing that is number of affected places (which is way more than for 'calculate').

llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
1775–1776

Even though current implementation of BPI.calculate uses post dominator tree unconditionally we can potentially switch to conditional use. In particular in presence of profile information on branches we give it a priority and don't actually need post dominator tree to compute probabilities. Yes, currently there is one exception from this rule but this is discussable.

ebrevnov updated this revision to Diff 260855.Apr 29 2020, 12:52 AM

Pass arguments directly to constructor.

skatkov added inline comments.Apr 29 2020, 1:49 AM
llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
1775–1776

I'm a bit confused.

In a previous comment you say that you do not introduce nullptr by default because it might give a chance for user to use less precise result.

Why we should not provide additional information here to get the more precise result?

ebrevnov marked an inline comment as done.Apr 29 2020, 2:54 AM
ebrevnov added inline comments.
llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp
1775–1776

There is a little difference between TLI and PDT arguments. If TLI is not provided it won't be built and results can be less accurate. If PDT is not provided it will be created inside BPI any way. That might change in future though and we may decide to create PDT in some cases only. Thus creating it upfront may be overkill.

To summarize the caller has control over number of input data and desired accuracy of results.

ebrevnov updated this revision to Diff 260882.Apr 29 2020, 4:29 AM

Request cached PDT through AM

skatkov accepted this revision.Apr 29 2020, 4:50 AM
This revision is now accepted and ready to land.Apr 29 2020, 4:50 AM
ebrevnov updated this revision to Diff 260901.Apr 29 2020, 6:17 AM

Fix Other/new-pm-thinlto-prelink-pgo-defaults.ll failing on AMD.

ebrevnov updated this revision to Diff 260943.Apr 29 2020, 9:33 AM

Another attempt to fix failing lit test.

This revision was automatically updated to reflect the committed changes.

I'm very confused by this patch. This does not look like an NFC.

  1. You are introducing a mandatory dependency on the postdom and the testcase changes do not look NFC. Please see inline comments for how to address this. To match your patch description the pass should not be required and you should be getting the cached analysis.
  1. This is also adding the creation of a postdom inside BPI when it's not available. This is questionable, for a pass to create a postdom inside and not something I think is acceptable.

If it is in fact needed to add it as required in order to address imprecise results, then motivate that and title/describe the patch appropriately.

Please either revert or address comments, and split up such changes in behavior into separate patches.

llvm/lib/Analysis/BranchProbabilityInfo.cpp
1067

Remove

1076

getCachedAnalysis

Hi Alina,
to me the patch seems to be NFC.

Before the patch, BranchProbabilityInfo::calculate built PDT unconditionally and this was not reflected in pipeline (that is the reason test for pipeline changed).

If I understand correctly patch does the following two modifications:

  1. in BranchProbabilityInfo::calculate, if PDT is provided -> use it. Otherwise unconditionally build it.
  2. In usage of BranchProbabilityInfo::calculate, Analysis manager is requested for PDT and it is provided as argument to BranchProbabilityInfo::calculate.

Your proposed change is actually, request the cached analysis and if it does not exist BranchProbabilityInfo::calculate will build it anyway.

So in both cases (Yevgeny's patch and your proposal) PDT will be built anyway, the only question when.
In Yevgeny's patch it will be built as analysis. In your proposal, it will be built inside BranchProbabilityInfo::calculate.

To me there is no difference.

Do I miss anything?

llvm/lib/Analysis/BranchProbabilityInfo.cpp
1011

Unconditionally build PDT.

Hi Alina,

I think you misread the patch. As Serguei already noted, PDT was unconditionally created by BPI even before my change. That means PDT is actually required analysis for BPI. But in order to support lazy BPI we still allow null PDT and do deferred creation of PDT if none was provided. Note also there are many other places in the code which explicitly creates BPI instance (not through analysis manager) and don't provide PDT as before.

Thanks
Evgeniy

Hi Serguei, Evgheniy,

Thank you for the explanations!
You're right, I missed the fact that the PDT was already built unconditionally before. Please disregard the previous comments. The change is actually a big improvement in logistic, as the analysis is retrieved through the analysis manager when it's already cached.

Thanks,
Alina

Hi!
PR 46098 started occuring wiith this patch:
https://bugs.llvm.org/show_bug.cgi?id=46098