Minor change to test case

Addressed comments

ping

ping

I won't have time to look into this in the near future unfortunately, as I am mainly focused on getting things in good shape to enable DSE & MemorySSA by default. It might be good to file a bug report so this opportunity does not drop off our radar. If anyone is interested in giving implementing it a try, even better :)

@fhahn is this patch supposed to support the following case?

In D79485#2231383, @hiraditya wrote:

Is the test failure related to this patch?

In D79485#2218349, @hiraditya wrote:

..anyway I can try to describe how thing work using some example. Is this what you are looking for?

yes. Thank you.

In D79485#2218350, @hiraditya wrote:

please run clang-format.

Added description of the algorithm to the header + formatting.

I think making 3 transformation passes immune to optnone ruins the whole idea. You really should have mechanism to set very specific and well documented overrides to the default.

I think this should be put on hold until D85781 reworked and relanded again.

In D85781#2220627, @xbolva00 wrote:

In D85781#2220576, @ebrevnov wrote:

How your last commit differs from the approved one? Why you have so many additional changes in the tests?

Patch affects many codegen tests so I updated them mostly with updater scripts.

How your last commit differs from the approved one? Why you have so many additional changes in the tests?

In D79485#2217052, @hiraditya wrote:

Is this work based on any paper/implementation?

I don't propose anything completely new here. New algorithm does essentially the same as existing one but

1. fixes several correctness issues
2. extends the approach to handle loops and invokes in a universal way

LGTM

Added a comment to updateEstimatedBlockWeight

In D79485#2208913, @davidxl wrote:

A lot of test changes can probably be extracted out as NFC (to make the string test more robust) -- this will reduce the size of the patch.

Unfortunately, in most cases, I don't see how this can be done with out loosing current coverage. There are few cases like 'successors: %bb.3(0x80000000), %bb.4(0x00000000)' where we could remove exact numbers and just check block names. I think we better keep exact probabilities in all other cases. That actually helps to catch unintended changes.

Do you have performance numbers related to the change?

I measured performance on bunch of java related benchmarks we have in house including SPECJVM2008, SPECJbb2015, DaCapo9.12 and others. I don't see any noticeable impact on performance.

Any perf data?

Rebase

Updated according to comments + formatting.

It's a bit shorter now. Let's see if it's manageable now. Further reduction would be problematic.

Rebased on top of D84838

In D84977#2186550, @aeubanks wrote:

It seems like the verification is to check either that on the first round, LoopCanonicalizationFPM worked, or on iterations after the first, the loop pass maintained whatever loop invariants.
Since the LoopPassManager itself doesn't check for L->isRecursivelyLCSSAForm(LAR.DT, LI), I don't think we should guard the check with !isSpecialPass(Pass.name(), {"PassManager"}).

This change causes problems to us. Even though "enable-npm-optnone" is false by default it affects us because we use custom pass instrumentation callback which causes passes to be skipped under some conditions.

One more general comment. If we introduce budget for total number of scanned instructions do we still need to limit number of visited blocks?

Marked as WIP since I'm going to extract one more part out from this review.

Rebase

I would suggest to separate an introduction of additional limit for a total number of scanned instructions and reduction of the current limit for number of scanned blocks to a different change sets. Also besides compile time numbers we should evaluate overall impact on performance before making such changes.

Updated as requested.

I have moved part of the change into a separate review D84514. Let's start with that...

In D79485#2162514, @davidxl wrote:

This patch is a little large to review properly. Is there any major refactoring (NFC or mostly NFC) that can be separated out?

I'm glad to see this discussion alive again. Thanks Roman!

ping

I measured performance on bunch of java related benchmarks we have in house including SPECJVM2008, SPECJbb2015, DaCapo9.12 and others. I don't see any noticeable impact on performance. Please let me know if you need more details on these experiments or some additional perf data.

Formatting

In D79485#2114260, @xbolva00 wrote:

Can you provide some performace data (SPEC/llvm suite) ?

Minor update

Sorry for keeping silence for that long. I had to work on higher priority tasks before I got a chance to return back to this. I think I fixed all your remarks. Please take a look.

Fixes according to comments + rebase

This change caused verification to catch "invalid" IR produced by instcombine. Filed a bug for that https://bugs.llvm.org/show_bug.cgi?id=46362

Ping

Thanks! LGTM.

Number of changes:

1. Previous version had an issue and was not able to propagate estimated weight from loop exits (in case more than 1 exit) to its entries. To fix that we introduce LoopData structure and trakc weight for loops explicitly.
2. Returned old behavior for 'invoke' heuristics to dominate 'cold' heuristics.

I think the new API of setting probabilities for all edges "atomically" is a good move. There is one suggestion though. In fact, there is no need to "repack" vector of probabilities into map. We can simply copy or even move (in most cases we have rvalue) entire vector into a map. This can be done as a separate change though.

Hi Alina,

Fix basic.ll

Another attempt to fix failing lit test.

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

Request cached PDT through AM

Pass arguments directly to constructor.

Functionally the change looks ok.
I think we should improve current API of BP (not in this change though) because it's easy to break invariant that sum of all probabilities is 1.
We better disallow cases when only part of edges have probability set and others unset. 1/NumSuccesors will likely be incorrect value in most cases with uneven distribution.