This resurrects PR #148758. I'll address previous issues shortly.

✅ With the latest revision this PR passed the C/C++ code formatter.

I believe I have addressed most issues raised in PR #148758.

For now, this PR shows what the pass pipeline tests (e.g., llvm/test/Other/new-pm-defaults.ll) look like after recent changes. As @nikic pointed out, there are still changes to where DominatorTreeAnalysis and LoopAnalysis run. LastRunTrackingAnalysis too.

I have not addressed the general issue raised there about whether pgo-estimated-trip-counts is actually worthwhile and whether we should constrain it or disable it by default. What do people think now after seeing the above changes?

Please rebase out the merge commits so I can test this. Found a way to apply it.

I have not addressed the general issue raised there about whether pgo-estimated-trip-counts is actually worthwhile and whether we should constrain it or disable it by default. What do people think now after seeing the above changes?

I think we should at least start by not having the pass and only doing on the fly updates. I assume that this patch is intended to be NFC-ish, but it does cause codegen changes, and as-is it's hard to tell whether that's because of the new loop metadata that is present everywhere, or due to divergence between branch weights and the metadata. (A sample to look at would be libclamav_nsis_LZMADecode.c from llvm-test-suite.)

I assume that this patch is intended to be NFC-ish, but it does cause codegen changes, and as-is it's hard to tell whether that's because of the new loop metadata that is present everywhere, or due to divergence between branch weights and the metadata. (A sample to look at would be libclamav_nsis_LZMADecode.c from llvm-test-suite.)

Thanks. I took a look at libclamav_nsis_LZMADecode.c, using the results you previously sent as a reference. For -O3, that shows that the previously landed version of this PR reduced the instruction count by 25.84%.

Following the instructions at the About page there, I used valgrind --tool=callgrind to try to reproduce the results.

For the current PR, I saw the following summary:

==2593500== I   refs:      909,055,484

I commented out all runs of PGOEstimateTripCountsPass and saw:

==2600705== I   refs:      1,203,023,203

So running PGOEstimateTripCountsPass still has roughly the same impact as in the previous results: 24.4% reduction.

I then tried to determine what in PGOEstimateTripCountsPass causes the change. In setLoopEstimatedTripCount's addStringMetadataToLoop call, I renamed the loop metadata from llvm.loop.estimated_trip_count to foo, which I believe should be semantically ignored by the rest of LLVM, including getLoopEstimatedTripCount:

==2674918== I   refs:      909,054,727

So, it appears that it is the up-front loop metadata creation that produces the change rather any changes related to estimated trip counts or branch weights.

To rule out anything else from the PR, I went back to the main branch and added a new function pass into the pipeline where this PR adds PGOEstimateTripCountsPass. The new pass merely calls addStringMetadataToLoop to add the bogus "foo" loop metadata to all loops. For any function containing loops, it preserves only CFGAnalyses and LazyCallGraphAnalysis, and it preserves all analyses otherwise.

==2797012== I   refs:      909,223,730

I then removed the addStringMetadataToLoop call from that pass to confirm that it not the analysis invalidation causes the change:

==2800546== I   refs:      1,206,601,523

I think we should at least start by not having the pass and only doing on the fly updates.

Do you think we should remove the pass or just disable it by default, as was previously suggested? I am leery of the latter because I am afraid it will just end up being unused code, unless someone else commits to continuing to investigate it.

@jdenny-ornl Thanks for looking into it. So this is indeed related to the fact that merely adding loop metadata can change optimization behavior. A likely culprit for this is this hack:

With that in mind, I don't think we should be doing early attachment of this metadata unless this issue can be fixed (as the comment indicates, by introducing block metadata).

Adding it lazily can also cause issues, but I'm hoping it would be to a lesser degree than adding it to every single loop. We should probably look out for the case where the latch is part of two loops though, so we don't mistakenly assign the same trip count to both an inner and an outer loop.

Do you think we should remove the pass or just disable it by default, as was previously suggested? I am leery of the latter because I am afraid it will just end up being unused code, unless someone else commits to continuing to investigate it.

I agree. Based on past experience, either a pass needs to be enabled right away, or it will never get enabled.

@jdenny-ornl Thanks for looking into it. So this is indeed related to the fact that merely adding loop metadata can change optimization behavior. A likely culprit for this is this hack:

llvm-project/llvm/lib/Transforms/Utils/Local.cpp

Line 1200 in 65ffa53

// 'BB' and 'BB->Pred' are loop latches, bail out to presrve inner loop

With that in mind, I don't think we should be doing early attachment of this metadata unless this issue can be fixed (as the comment indicates, by introducing block metadata).

Thanks for the reference. Fixing that issue seems orthogonal to my BFI fixes, and it would surely be a major distraction from them.

Adding it lazily can also cause issues, but I'm hoping it would be to a lesser degree than adding it to every single loop. We should probably look out for the case where the latch is part of two loops though, so we don't mistakenly assign the same trip count to both an inner and an outer loop.

With or without this PR, {get,set}LoopEstimatedTripCount operate on the branch weights of a loop's only latch (and they reject loops with more latches). My expectation is that merely moving the estimated trip count to loop metadata on that latch for each of the same loops should not worsen the above issue.

Do you think we should remove the pass or just disable it by default, as was previously suggested? I am leery of the latter because I am afraid it will just end up being unused code, unless someone else commits to continuing to investigate it.

I agree. Based on past experience, either a pass needs to be enabled right away, or it will never get enabled.

I have dropped PGOEstimateTripCountsPass for now. If someone implements header block metadata for loops in the future, we can revisit the possibility of PGOEstimateTripCountsPass then.

With or without this PR, {get,set}LoopEstimatedTripCount operate on the branch weights of a loop's only latch (and they reject loops with more latches). My expectation is that merely moving the estimated trip count to loop metadata on that latch for each of the same loops should not worsen the above issue.

To be clear, the concern is not about loops with multiple latches, but two loops sharing one latch. You can have an inner loop latch that exits into an outer loop and is the latch of the outer loop. IIRC that's possible even in loop simplify form.

With or without this PR, {get,set}LoopEstimatedTripCount operate on the branch weights of a loop's only latch (and they reject loops with more latches). My expectation is that merely moving the estimated trip count to loop metadata on that latch for each of the same loops should not worsen the above issue.

To be clear, the concern is not about loops with multiple latches, but two loops sharing one latch. You can have an inner loop latch that exits into an outer loop and is the latch of the outer loop. IIRC that's possible even in loop simplify form.

I was trying to make a point about how, for a loop with one latch, all this PR is doing is changing which metadata on that latch encodes the estimated trip count.

After further thought, I realize that the branch_weights metadata on a latch distinguishes an outer loop from an inner loop because each loop header is a different successor of the latch. But llvm.loop.estimated_trip_count does not distinguish the loops.

I think I have a workaround. I have adjusted getExpectedExitLoopLatchBranch to guard {get,set}LoopEstimatedTripCount as it does without this PR. getExpectedExitLoopLatchBranch will not recognize the same latch for both loops unless the latch exits both loops and has only two successors. However, to exit both loops, the latch must have at least three successors: the inner loop header, the outer loop header (exit for the inner loop), and an exit for the outer loop.

Does that seem reasonable?

@nikic Any further thoughts on this PR?