Thank you for adding this information!!

Latest diff looks good to me.

LGTM.

Changes LGTM with inline nits.
@nikic I have not verified compile time impact with the latest diff.

Following up on the regression I was seeing with https://reviews.llvm.org/D114171, the only meaningful IR change seems to be:
Before the patch (after slp):

%65 = shufflevector <2 x float> %9, <2 x float> poison, <4 x i32> <i32 0, i32 1, i32 undef, i32 undef>
%66 = insertelement <4 x float> %65, float %16, i32 2  
%67 = insertelement <4 x float> %66, float %15, i32 3
%68 = call <4 x float> @llvm.fabs.v4f32(<4 x float> %67)
%69 = fcmp oeq <4 x float> %68, <float 0x7FF0000000000000, float 0x7FF0000000000000, float 0x7FF0000000000000, float 0x7FF0000000000000>
%70 = freeze <4 x i1> %69 
%71 = call i1 @llvm.vector.reduce.or.v4i1(<4 x i1> %70)

In D100780#3508147, @aeubanks wrote:

In D100780#3504820, @xbolva00 wrote:

This could be done by either exposing a simplifyLoopCFG helper function ...

This variant sounds better, if possible.

+1, at least for this case where it's a simple cleanup

in other cases, such as D125293 and D115052 where we want to do more general cleanup due to added/lowered code, I believe @asbirlea has future plans to add new PM infra to conditionally run passes for simplification pipeline work

In D100486#3495174, @ABataev wrote:

In D100486#3495157, @asbirlea wrote:

In D100486#3494746, @ABataev wrote:

In D100486#3494581, @asbirlea wrote:

We currently root-caused a 20% regression in eigen complex to this patch and it is blocking our compiler release.
I need some time to do additional testing, given there are at least a few patches on top of this. So far I see a crash fix, two NFCs and two additional changes that may also affect performance (https://reviews.llvm.org/D114171 and https://reviews.llvm.org/D115750).
Can you please hold off on any additional changes while we test further, or include them here for review so I can check if they resolve the regressions seen so far?

Most probably, some overoptimistic cost model estimations turned on some extra vectorization. The reproducer will help, if you can provide it.

The reproducer is open source: https://gitlab.com/libeigen/eigen
Regressions are on haswell platform, xfdo configuration; the compiler used is bootstrapped against itself; revision tested includes this patch and all follow-up changes to the SLPVectorizer including D114171 and excluding D115750.
A few number samples:
BM_MatrixVectorMultiply_Complex_EigenRowMajorDynamic_float_16x64_ 16%
BM_MatrixVectorMultiply_Complex_EigenRowMajorDynamic_float_64x64_ 17%
BM_MatrixVectorMultiply_Complex_EigenRowMajorFixed_float_64x64_ 15%
BM_MatrixVectorMultiply_Complex_EigenRowMajorFixed_float_16x64_ 14%

Could you at least extract the llvm ir code for one of these functions before the changes and after, so I coukd at least compare them?

In D124284#3500259, @ABataev wrote:

In D124284#3499844, @asbirlea wrote:

In D124284#3496381, @RKSimon wrote:

@asbirlea How are you specifying the SSE/AVX level for your benchmark runs - are you running with -march=native the x86-64-v* levels or something else?

I believe the runs are using -target-cpu k8 and -target-cpu haswell.

The latest performance testing still shows one regression in a benchmark from singlesource, but there are many improvements that offset it in non-public benchmarks. So this latest diff is good to go from my side.

Hi, thanks for the testing. What's the name of the regressed single source test?

In D124284#3496381, @RKSimon wrote:

@asbirlea How are you specifying the SSE/AVX level for your benchmark runs - are you running with -march=native the x86-64-v* levels or something else?

In D100486#3494746, @ABataev wrote:

In D100486#3494581, @asbirlea wrote:

We currently root-caused a 20% regression in eigen complex to this patch and it is blocking our compiler release.
I need some time to do additional testing, given there are at least a few patches on top of this. So far I see a crash fix, two NFCs and two additional changes that may also affect performance (https://reviews.llvm.org/D114171 and https://reviews.llvm.org/D115750).
Can you please hold off on any additional changes while we test further, or include them here for review so I can check if they resolve the regressions seen so far?

Most probably, some overoptimistic cost model estimations turned on some extra vectorization. The reproducer will help, if you can provide it.

We currently root-caused a 20% regression in eigen complex to this patch and it is blocking our compiler release.
I need some time to do additional testing, given there are at least a few patches on top of this. So far I see a crash fix, two NFCs and two additional changes that may also affect performance (https://reviews.llvm.org/D114171 and https://reviews.llvm.org/D115750).
Can you please hold off on any additional changes while we test further, or include them here for review so I can check if they resolve the regressions seen so far?

In D124284#3493607, @RKSimon wrote:

@asbirlea Do you have an update on the regressions you were seeing vs latest patch?

I'm seeing some fairly big regressions with this patch, specifically on Rome (AMD) architecture.
A couple of examples that are public in the test suite: SingleSource/Benchmarks/Shootout: for sieve I'm seeing a 20% performance regression in an opt build and an xfdo one, and for MicroBenchmarks/ImageProcessing/Dither 10% regression (opt, thinlto and xfdo).
I'm seeing also a couple on Skylake, opt build, in the range of 5-13 %, an example being eigen with 13% regression; this may be harder to track down as it's in a specific configuration but let me know if you want to reproduce this one.

Noted, I will run some testing this week.

Thank you for the cleanup!
Maybe worth a mention that this effectively enables SimpleLoopUnswitch for the legacy PM, in case any users need this clarification; more of a nit, considering the LPM is being removed.

As a side note, the fact the freeze instruction needs licm and simple loop unswitch interleaved, will likely affect the plan we had around splitting off the non-trivial unswitch functionality into a separate function pass (the context for that is regarding using divergence analysis: https://reviews.llvm.org/D109762)
It seems like tracking the added freeze instructions and including the functionality of hoisting them as part of the "new" non-trivial SLU pass will resolve this, but I'd like to hear folks feedback on this.

+ 1 to please clarify in the test why this is necessary.
Without the context, the question will be: why not generate the IR after LICM and only test SLU? Clarify the test needs the sequence SLU on inner loop, licm to hoist freeze condition and then SLU on outer loop can be done.

Added nits, but happy if this goes in as is too.

This cleanup is beautiful!
Thank you!!

+1 to the additional cleanup.

Thank you!

Looks good to me as well.

lgtm

I'm seeing no meaningful difference in performance from this as is. Let's see if there are other reports and we can increase the limit if this is the case.

As discussed offline, the potential issue with this change is whether we encounter a pathological case in the "opposite direction".

Update based on comments.

Thanks for the suggestions, updated a couple more places.

LGTM with a couple nits.

Sent out https://reviews.llvm.org/D121740.

LGTM for this patch on the impact side, testing looks good.

LGTM.

Reading the details in your post and looking at the SLPVectorizer code I think there's the potential for the pass to benefit from using MemorySSA. However I do not understand enough of the SLPVectorizer mechanics to guess if this will work out or not.
In this context, I think it makes sense to have incremental changes while keeping building and updating MSSA off by default; as you mentioned in the post, all changes can (and should) be reverted if a later decision is to pursue something else.

Given the situation, I agree this is a reasonable way to handle it.

Thank you for sending this out!

In rG87753cebf5f861eee418d6bce155dfa0b00f9878#1062523, @RKSimon wrote:

In rG87753cebf5f861eee418d6bce155dfa0b00f9878#1062368, @asbirlea wrote:

Affected code is close to or identical to the modules in: https://github.com/llvm/llvm-test-suite/tree/main/Bitcode/Regression/fft

OK - any in particular? And again, what cpu/avx-level is being targetted?

Affected code is close to or identical to the modules in: https://github.com/llvm/llvm-test-suite/tree/main/Bitcode/Regression/fft

Thank you for looking at this! Please see inline.

In D116825#3343187, @anna wrote:

Do we have any compile time measurements for this change with O3?

@chill mentioned he did some early testing on that, so he might have some numbers.
From my side, it's too early. I'm seeing a correctness issue in the early testing that needs resolving. I'm looking into getting @chill something actionable there.

I have couple of high level comments/clarifications:

• Are all mini-transforms within GVN moving to MSSA in this case?

Is they needed MemDep before, yes.

• Is the move to MemorySSA for performance of cases not caught through MDA?

It should address at least one or both. Primary goal is remove last user of MDA and remove the analysis from trunk. The implementation for the transition should be such that it either catches more cases or provides improved performance (or both). From previous experience with switching DSE, this is possible if implemented right.

@asbirlea, a question to clarify my understanding around enabling MSSA for a pass:

• We optimistically build memorySSA for passes that unconditionally require it. This building and preservation can be costly from compile time perspective. Also, we may have possible invalidation by later function passes which do not preserve GVN, thereby having different implications for pipelines depending on where GVN is present. For example, if we end up with something like:

LPM {
 ...
 LICM <-- requires MSSA.

}
instcombine <-- invalidates MSSA
GVNPass() <-- build MSSA again
simplifyCFG <-- invalidates MSSA

is arguably much worse in compile time than:

LPM {
 ...
 LICM <-- requires MSSA.

}
GVNPass() <-- use preserved MSSA
instcombine <-- invalidates MSSA
simplifyCFG

Thank you for starting this!
From my side, LGTM.

lgtm

I think the clearing should be added at the beginning of insertDef and insertUse. A similar clearing is done on visited phis at the same two places. I didn't get a chance to test it yet though.

lgtm.

Just a couple of quick comments:

• Why take out the option to DisableGVNLoadPRE?
• Can the MemDep and MSSA be mutually exclusive options? (i.e. enabling one disables the other)

AFAICT, this patch doesn't make any difference for https://github.com/llvm/llvm-project/issues/52858.

Reproducer with llc -O2: https://reviews.llvm.org/P8277

Thank you for sending this fix!
It feels like a pretty big hammer, but some of the tests being modified here are exact examples of the miscompile I was seeing. I'm good with it at this point.

Any chance you could profile where most time is spent?

Quick update: I'm not seeing any major run time regressions, but there are a few unrelated issues that may make the results I'm seeing incomplete.
I'm seeing some compile-time regressions, I'd be curious to see what the updated compiler-tracker results look like.

Thank you!

A very broad comment for a smooth transition

• the patches should be split into changes to GVN independent of the switch, e.g. a) factoring out components/methods where the differences between MSSA and MD occur and b) things that need to be added for the transition
• we should keep the MD implementation and have a flag for switching between the current one and the MSSA one being added
• once the flag flip sticks, then we'd remove the MD implementation

Thank you for resolving all the issues raised! Could you rebase this patch on ToT? (to include the MSSA update and the move to LPM1?)

Changes LGTM.
Nit: clang-format.
A simpler way to check all verification is now to pass VerificationLevel::Full to verifyMemorySSA(); I'm mentioning this for your local testing, in case your build doesn't have EXPENSIVE_CHECKS on already, not to include in this patch.

Thank you for this work!

In D112313#3125662, @fhahn wrote:

In D112313#3125182, @asbirlea wrote:

Allowing passes to do this is a slippery slope...
We already have the issue that it is sometimes hard to reproduce an issue with a single pass, due to the cached state in MemorySSA. This cached state is already dependent on what other passes do, a mix between queries and transforms, which may leave MemorySSA either "over-optimized" (has stored info beyond what it could deduce if built from scratch) or "under-optimized" (could deduce more). Having DSE optimize more is not that far fetched considering this.
I'm inclined to let DSE do this, only because 1) the traversals and inferences are beyond what MSSA alone does now and 2) they're "free" (i.e. DSE does them anyway).
However, I would not be ok with any pass being able to set optimized accesses.

That policy sounds good to me, thanks for sharing! Should we add something like that to the MemorySSA docs?

Allowing passes to do this is a slippery slope...
We already have the issue that it is sometimes hard to reproduce an issue with a single pass, due to the cached state in MemorySSA. This cached state is already dependent on what other passes do, a mix between queries and transforms, which may leave MemorySSA either "over-optimized" (has stored info beyond what it could deduce if built from scratch) or "under-optimized" (could deduce more). Having DSE optimize more is not that far fetched considering this.
I'm inclined to let DSE do this, only because 1) the traversals and inferences are beyond what MSSA alone does now and 2) they're "free" (i.e. DSE does them anyway).
However, I would not be ok with any pass being able to set optimized accesses.

Thank you for all the clarifications. I'm convinced this is the right way to move forward at this point.

LGTM, but please wait to see if @nikic has additional comments.

In D110822#3116954, @chill wrote:

In D110822#3116785, @asbirlea wrote:

The request changes is for the use of getID() in MemorySSA(). Other optimizations should never rely on the value of the IDs assigned by MemorySSA.

The getID() was already a public method in derived classes and the ID is used according to its description "Guaranteed unique among MemoryAccesses".

How about value numbering the BasicBlock that corresponds to a MemoryPhi ? It's a little bit of overhead and not strictly necessary if we have an ID readily available, but, fair enough, I don't mind doing it this way.

Thank you for the additional clarifications in the comments and descriptions!

The request changes is for the use of getID() in MemorySSA(). Other optimizations should never rely on the value of the IDs assigned by MemorySSA.

Can you also update lib/LTO/LTOBackend.cpp to something like:

// Parse a custom AA pipeline if asked to, otherwise the default will be used.
if (!Conf.AAPipeline.empty()) {
  AAManager AA;
  if (auto Err = PB.parseAAPipeline(AA, Conf.AAPipeline)) {
    report_fatal_error(Twine("unable to parse AA pipeline description '") +
                       Conf.AAPipeline + "': " + toString(std::move(Err)));
  }
  // Register the AA manager first so that our version is the one used.
  FAM.registerPass([&] { return std::move(AA); });
}

This change's numbers look better overall. The compile-time regressions are smaller across the board and the memory gains are still there, in some cases reduced and in some cases improved. I don't think the level of noise is that high.
Overall, this change is the right approach both conceptually (only invalidate in these adaptors) and given the practical results.

Adding a few items/questions discussed in the open meeting:

In D109762#3070676, @aeubanks wrote:

In D109762#3069261, @sameerds wrote:

In D109762#3059988, @aeubanks wrote:

I talked to some people and we've decided that the best thing to do would be to refactor out the nontrivial unswitching part into a function pass. Nontrivial unswitching is fairly special in the kinds of transforms it does.

Will that always work as expected? The real dependency is that the divergence analysis is not incrementally updated. So even if this is a function pass, we may want to rerun it on the whole function every time it manages to unswitch a loop.

With this patch, we have to rerun DivergenceAnalysis every time we run the pass on every loop. If we change nontrivial unswitching into a function pass, we can upgrade that to only having to be rerun every time we actually unswitch something.
To be more specific, with the function pass, we'd have to invalidate most analyses anyway after every successful unswitch.

for every loop
  DA = FAM.getAnalysis<DivergenceAnalysis>(); // this will not rerun the analysis if we haven't invalidated below because we didn't successfully unswitch
  if successful unswitch
    auto PA = PreservedAnalyases::none();
    PA.preserve<SCEV>();
    // and all the other existing analyses we preserved
    FAM.invalidate(PA);

This broke upstream bazel: https://buildkite.com/llvm-project/upstream-bazel-rbe/builds/10376#98340937-c4c7-4bd7-997e-dd56691da9d8
Was the header file missed?