Do you have an idea if there is overhead of adding the AAR object to each query (each query info object)? (vs the setAAResults being done once for all the AAs available).

lgtm.
Runtime impact results look good.

Thank you for confirming @SjoerdMeijer.

Could you test clang as well, and update test?

I'm curious if the compile time impact is complemented by impact in run time. Looking into that for O3.

lgtm.

The changes LGTM, but I'd rather defer final review to ahatanak@.
It would be good to have some testing but it could be addressed in a separate patch, potentially by folks more familiar with the ObjCARC passes.

I believe for the NPM this should work fine.
@nikic @fhahn Any objections?

lgtm.

Looks reasonable to me as well, that the metadata info should hold at the same loop level.

Apologies for the delay, I spent some more time understanding how the assumptions changed in the new implementation.

I'll look into regenerating the bitcode files, but in the mean time this looks good.

Thank you for pushing the fix. Based on a quick look, it seems reasonable to not do the renaming for unreachable blocks. I'll look in more depth next week.

Thanks!

This seems like a useful utility to add to BasicBlock itself if it doesn't exit? (e.g. getNonEmptyName or getNameOrAsOperand).

Address comments.

Many thanks!

We've bisected a test failure to this revision.

Thank you for adding this support.

In D92796#2440988, @aeubanks wrote:

Currently LSR is not tested with the NPM in any circumstance.
There are no tests with -passes=loop-reduce, and LSR is only used in the codegen pass manager, so even with -DEXPERIMENTAL_NEW_PASS_MANAGER=ON, it's never in a NPM context.

Fix clang-tidy warning (lowercase method names; the file needs a lot of other functions names fixed, but might as well start with these)

Discussed this offline, and proposed this solution to make progress and resolve the failing tests.
This does need exploring further though as:

1. the behavior of current LSR will no longer be tested in the new pass manager, due to LCSSA being run as a canonicalization pass.
2. adding it to a loop pass manager in the npm will be problematic, because it doesn't preserve LCSSA.

lgtm.

According to: https://clang.llvm.org/docs/AttributeReference.html#nomerge, the existance of the attribute should prevent call site merging, so the change makes sense.
However, in the test example then, if there was branching and two @f calls inside @bar, it would be correct to merge the @f call sites (no attribute preventing that inside) when processing @bar. But after inlining, that's no longer allowed if the attribute is distributed to all callsites inside the function.
This is a contradiction that needs clarification from folks more familiar with the Inliner.

In D92488#2437692, @reames wrote:

Hard reject. This patch will not be accepted. This is a major design change.

Hoisting operations out of loops is treated as a canonicalization transform in LLVM. If the register pressure is problematic, the MachineLICM pass is supposed to undo the transformation. If you have cases where that is not happening, please explore why.

If after doing so, you still feel this is the right approach, please raise the design change on llvm-dev.

A few comments inline.

Yes.

EarlySimplificationEPCallback?

Unblocking the fixing of the tests under NPM. Additional changes can be done as follow ups.

This is great, thank you for this fix!

sgtm too.

Ack.

lgtm.
Please wait in case fhahn@ has additional comments.

One more comment, the others look good.

I don't think "ModuleOptimizer" in the name makes sense, the association can come from the "Early" part. Either keep the naming as is, or "EarlyAfterStart" if you want to define order against the other callbacks.
ychen@ so you have a better naming suggestion?

Thank you for the cleanup!

In D89207#2408995, @nikic wrote:

In D89207#2370224, @asbirlea wrote:

Since this is using MSSA walker API with a MemoryLocation (which does not cache), could this become costly in a pathologically constructed example? If so, could we have a (reasonably large) upper bound on the number of getClobbering (Access, Location) calls to avoid such cases?

I've started implementing this (by returning a DoNothingMemorySSAWalker when a limit is hit), but ended up wondering if it really makes sense: I believe that the number of MSSA walker queries we do in this pass is roughly proportional to the number of memsets/memcpys in the IR. For very big functions we may end up performing many queries, but the overall runtime should still be linear (each individual query is limited by the walker limit). Having a limit would make sense to me if something here had quadratic runtime (like e.g. the AST limit in LICM), but I don't think that's the case here.

Algorithm lgtm.
+ @kuhar for additional review.

In D91649#2401902, @nikic wrote:

In D91649#2401252, @asbirlea wrote:

• LocationSize::unknownMaybeNegative() seems somewhat ambiguous in isolation; unless I see the other name or have the context from this patch. I'm either keep LocationSize::unknown or make it even more verbose LocationSize::unknownPositiveOrNegative().

I'd like to not reuse the existing unknown() name, to force all users (including out of tree users) to make a decision one way or another. Not particularly attached to the names though. We could also drop the "unknown" prefix and make them LocationSize::nonNegative() and LocationSize::positiveOrNegative() for example.

Generally I'm not really fond of "negative" sizes as a concept, it just seemed like the most concise way to explain it. It would be more accurate to say that the size is always positive, but there may be a negative offset. So maybe LocationSize::nonNegative(), LocationSize::withNonNegativeOffset() and LocationSize::withAnyOffset(), where the first two are aliases but can be used according to desired semantics. Can't say I really like this either though.

Or maybe LocationSize::afterPointer() and LocationSize::beforeOrAfterPointer().

In D89587#2400646, @aeubanks wrote:

In D89587#2398531, @asbirlea wrote:

Could you clarify why a map and not a SmallVector?

I was expecting the indirect calls to be added by all CGSCC passes, e.g. lib/Transforms/IPO/Inliner.cpp:750. Adding the calls in updateCG... instead, introduces a single point of failure so less chances of having passes forget to add them; the one thing I'm not clear is if the updateCG... call may be added too late in a CGSCC pass; for the inliner, it seems fine (thank you for adding the tests) but I'm not clear if this will hold for other passes. I don't have a use case now, just making a note to verify this for coroutines.
The check that all accesses are still indirect on the return looks good.

It is definitely possible to have a call to updateCG... miss a devirtualization in a CGSCC pass if an indirect call is introduced and then promoted before the call to updateCG..., but the inliner looks ok. I think other CGSCC passes don't really devirtualize much. As long as we call updateCG... after passes that can devirtualize (inliner, function passes like instcombine, etc) we should be good. And we can always revisit if we find missed cases.

This makes sense to me too. The additional comment was helpful with the gcd/difference condition.

• LocationSize::unknownMaybeNegative() seems somewhat ambiguous in isolation; unless I see the other name or have the context from this patch. I'm either keep LocationSize::unknown or make it even more verbose LocationSize::unknownPositiveOrNegative(). I think the most restrictive case ( LocationSize::unknownMaybeNegative() or renamed version) should be the default ~uint64_t(0), but don't feel strongly about it.
• clang-format

No objections.

As talked offline, this lgtm.

Could you clarify why a map and not a SmallVector?

I wouldn't be surprised if there are other asymmetries, thank you for digging further here.

AFAICT all issues were addressed.
@Meinersbur: are there any concerns left with this patch?

This is great, thank you!

Resulting dot file for the test looks good.

Thank you for the fix.

lgtm.
Looking forward to having it enabled in a future patch.

lgtm

Thank you for detailed tests, this looks good!

Thank you, just a couple of small comments below.

Thank you for working on this, the compile times look very promising and the tests results are great!

The current behavior is:

• for the NPM, always use MSSA for LoopSink, which is a Function pass.
• for the LPM, LoopSink is a Loop pass and it will use MSSA conditioned on the EnableMSSALoopDependency flag which is set to true, hence this patch is switching loop sink to use MSSA.

This looks like a nice approach to clean up the recursion, thank you for working on this!

I guess my question was more regarding consistency. Why not use MSSA in the LPM as well and drop the AST usage entirely? Or provide a flag that can be used to switch between MSSA and AST version (see LICM or DSE for similar flags using MSSA or alternative analyses), just in case there are users of the AST version.

Thank you!

• Could you separate the SinkHoistFlag refactoring into an NFC?
• Could you clang-format and fix lints?
• LICM changes look good. AFAICT the MSSA changes in LoopSink are accurate, but it may need more testing than the existing unit tests.
• Why do you want the legacy pass manager to use the AST and the new pass manager MSSA?

I checked in the changes adding AAQI as authored by you.
The change clearing the cache is not right, as discussed on llvm-dev, so I think this patch is not obsolete.

Neat!

lgtm

This LGTM.
I'd like to understand better what you mean by not calling partialOverwrite. If the functionality in that call would be included in the isOverwrite call, note that there are call-paths that would do more work than they do now, and I thought there was a previous refactoring done to avoid this.
I may be mis-understanding though, so feel free to send the additional changes and we can discuss on those.

This is an interesting point. IIUC, your argument is that the entry point into AA is always through AAResults and can rely on the invocation result for TBAA or ScopedAA from there, while the recursive invocations into these same analyses cannot yield stricter results. I cannot think of a case when this is not true.