I thought the zero count is from the most significant bit but I may be wrong. In any case, your point is valid. I see how you can construct an example where the .first fields are not equal, but then the popcount and countl_zero are both equal, leading to a "false" on the LessThan call for both (a,b) and (b,a) comparison.
The change proposed here does provide an absolute ordering so it resolves the issue you found and it's reasonable to go with it. I'm not sure it's the "desired" one (or if it even matters). It will rely more often on the Idx default, than on the two comparisons, and perhaps that's ok.
A more classical comparison would be for LessThan to provide a full <; so comparing on the .first for equivalency, but then determining the follow up on conditions which defines a strict ordering (e.g. bitsToDouble()?).

Proving the size is non-zero is a higher bar than proving the zero case and eliminating the memcpy in those cases. So this seems reasonable to me.

LGTM.
Another alternative is creating a createMemoryAccess API which does not take the defining access, but likely not worth it.
I'm fairly certain we cannot keep the defining access when inserting Defs in the general case, in particular when needing to insert new Phis.

Can you replace this with an assert instead?

lgtm

In D152743#4415131, @nikic wrote:

I'm concerned that this will cause us problems in the future, e.g. if we want to do MemorySSA-based GVN, because we will no longer have MemoryUses for these loads at all, even though we may want to do load CSE on them.

This went through a few rounds of testing on our internal benchmarks and it's at a point where there are no meaningful run-time regressions observed, but the compile-time improvements remain and are significant enough to move fwd with the change.
Approving to move things forward. If folks do encounter regressions from this change before or after landing, please flag them here.

Thank you, no issues after the fix patches afaict.

Confirmed test is back to green at d1dc3e1, with 494dee0 reverted. Reverted now.
I'll continue to look into IR differences. Please let me know if the above is helpful in the mean time.

I still don't have all the answers, here's what I know so far:

• The test in question is publicly available in https://github.com/google/jax/blob/main/tests/lax_scipy_test.py
• With the 3 patches reverted from yesterday, the test passes up until https://github.com/llvm/llvm-project/commit/494dee0f7a7701a57f7c5b755b4133844d0dcbdf, when it fails again
• With local revert of 494dee0f vs ToT now, and looking only at one of the failures (with 201 modules) I only see a difference in the attached module (
  module_0088.jit_wrapped_fun.ir-no-opt.ll5 KBDownload
  )
• Running opt -O3 at ToT gives different output than the one dumped by that test, so here's the optimized with at 494dee0f (
  module_0088.jit_wrapped_fun.ir-with-opt.ll13 KBDownload
  ) and at the revision right before (
  module_0088.jit_wrapped_fun.ir-with-opt_good.ll13 KBDownload
  )

Hi Matt,

lgtm.

Nit: the diffs would be easier to analyze with "-fno-discard-value-names".

Adding a line in release notes might be useful; next to a note with the removal of legacy PM pieces (e.g. PassManagerBuilder).

Yeah, I noticed right after I sent this patch out :-).

Thank you for updating this!

Wondering if having the flag would still be useful if you want this statistic and not everything else in stats. But I don't think we particularly need that now, so works for me and flag can always be re-added.

lgtm with comments addressed.

SGTM, thank you Florian!

Following this change, the following emits warnings: https://godbolt.org/z/cvGdMWqEa, https://godbolt.org/z/GhTP85WzE

Heads-up that we're seeing crashes due to the recommit of this change.
msan reports "use-of-uninitialized-value" in multiple places, where input is clearly initialized.

Re-ping to current reviewers. Any thoughts on the above @cor3ntin? Is there someone who you recommend look into this issue?

Thank you @fhahn!

Reverting should be acceptable here.
AFAIU, the norm for work with high impact (adding a pass to the pipeline is one) is to do the work itself under a flag so the work itself does not get reverted if there are issues, and for the flag flip patch (such as this one) to be reverted if issues arise.
When the issue is resolved, the flag flip patch should be re-landed.
Regressing a test by ~1000%, seems like a solid reason to revert if a solution is not immediately available, especially with having a reproducer available that confirms the issue.

I'm ok to not bikeshed this one at this time :-).

In my opinion, this is fine.

I did now and it also looks clean. Commit with 200?

I'm curious where all the time is spent in the 200s to 2s case. Is Eager strategy just as slow?

Seeing a regression after this change. Filed: https://github.com/llvm/llvm-project/issues/59951

I'm seeing one instance of increase in compile-time with the 100 limit and a couple of small run time regressions. The results look somewhat cleaner with a cap of 300. Could we use 300 as an intermediate step?

Gentle ping. Can you propose an alternate patch to fix this crash? The github issue is 6 months old and similar crashes are reported due to this.

Rebase to trigger pre-merge checks?

lgtm.

Reducing this limit is certainly the right thing to do. To what value so as to not cause large regressions is a question I'd like to answer with some experimental data.
I'll start some experiments and come back to this.

lgtm.

Considering the previous reviewer comments, this lgtm.

Could you add updated compile-time impact measurements after the latest rebase?

Green light perf-wise.
I cannot comment on whether the position is "the right" one though. I'm deferring to the other reviewers.

As far as performance, this looks fine. Not seeing measurable gains.

Makes sense to use BAA at call sites if the usage is such!

Missed the dependent patch on LoopAccessAnalysis, now it makes sense :-)

+1 on making the AST only work on immutable IR.

IIUC compile time impact for adding another SROA (the one outside LTO) is negligible?

The original starts crashing with -O2 with this revision, but crashes with -O0 before and after this revision, so the issue looks preexisting.
The reduced test from @rupprecht no longer crashes with -O0 before this revision.
If this becomes an issue for resolving, we could share the un-reduced offline.

It seems unnecessary to force all uses to instantiate and pass the BatchAA.
Can this remain part of the ClobberWalkerBase instead? Default the calls to getClobberingMemoryAccess to instantiate a BatchAA internally and pass to the ClobberWalker.
Then, there can be an additional API added to override the above behavior when useful (known as safe): either passing a given BatchAA like current patch, or, keeping a BatchAA in the ClobberWalker itself instead of the AA, and being able to "set" it to not re-initialize it on each call (and perhaps "reset" to reseting each time).
What do you think?

LGTM.

Thank you for adding this!

Simplify conditions in canPeel.

Simplified to only the changes in canPeel.