[BasicAA] Use PhiValuesAnalysis if available when handling phi alias

[john.brawn]

Summary

By using PhiValuesAnalysis we can get all the values reachable from a phi, so we can be more precise instead of giving up when a phi has phi operands. We can't make BaseicAA directly use PhiValuesAnalysis though, as the user of BasicAA may modify the function in ways that PhiValuesAnalysis can't cope with.

For this optional usage to work correctly BasicAAWrapperPass now needs to be not marked as CFG-only (i.e. it is now invalidated even when CFG is preserved) due to how the legacy pass manager handles dependent passes being invalidated, namely the depending pass still has a pointer to the now-dead dependent pass.

[• dberlin]

What you've implemented (or trying to) is really the SCC algorithm from from "Simple and Efficient
Construction of Static Single Assignment Form" at
http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf

That will find the values you seek here :)
(you don't have to do the recursive simplification it does)

[• dberlin]

https://reviews.llvm.org/D28934 has a version of the SCC finder you can
borrow if you want (TarjanSCC class)

[efriedma]

My primary concern here is that SimplifyInstruction needs to be "constant" time; if you put a linear traversal over the entire function here, you'll cause compile-time explosions all over the compiler.

[• dberlin]

Yeah, that is why on the other thread i suggested it probably makes sense
to just change how AA is doing it rather than all simplification users

[mkazantsev]

I also agree that InstCombine is expected to have O(1) complexity of its operations, and this code attempts to traverse the entire tree consisting of Phi nodes which is O(N), and it can actually start from any node of this tree. I don't feel that this is right.

lib/Analysis/InstructionSimplify.cpp

3956 ↗

(On Diff #138694)

Please use SmallPtrSet here.

3961 ↗

(On Diff #138694)

Before that, assert that PHINodesSeen does not contain ThisPN?

3982 ↗

(On Diff #138694)

Why not else if instead of continue?

3989 ↗

(On Diff #138694)

{} not needed.

[john.brawn]

I've gone for the approach of doing this in alias analysis, which works without any test failures. I'd also considered doing it in GetUnderlyingObject, or adjusting aliasCheck to use GetUnderlyingObjects instead, but the problem there is that they look also through GEPs and there would have to be a parallel change to DecomposeGEPExpression to add a bunch of PHI handling there as well.

[mkazantsev]

lib/Analysis/BasicAliasAnalysis.cpp

1538

Please follow LLVM naming convention.

1599

V1Srcs.empty()?

1599

How do we know that V1Srcs is not empty at this point?

[john.brawn]

lib/Analysis/BasicAliasAnalysis.cpp

1599

For that to happen we would have to have a phi with no underlying non-phi values, which I'm pretty sure can only happen in unreachable blocks, e.g. something like

define void @fn(i32* %p) {
entry:
  br label %exit

exit:
  ret void

unreachable:
  %phi = phi i32* [ %phi, %unreachable ]
  %load1 = load i32, i32* %p, align 4
  %load2 = load i32, i32* %phi, align 4
  %cmp = icmp ne i32 %load1, %load2
  br i1 %cmp, label %exit, label %unreachable
}

Which we shouldn't ever normally see, but it is possible to manually craft such IR (e.g. the above) and it currently causes a crash so I'll adjust it to fix that.

[john.brawn]

Address review comments.

[mkazantsev]

I don't see any more problems, but I'm not the best person to give reviews in BasicAA. Please wait for someone else to take a look.

[john.brawn]

Ping.

[john.brawn]

Ping.

[mkazantsev]

I've added some people who made commits to BasicAA recently. Could you please take a look into this patch? It has been on review for a while with no progress.

[john.brawn]

Ping.

[efriedma]

Hmm. I don't see anything wrong with the code, but how often will this trigger? instcombine will remove the PHI nodes in your testcase, so this is only a problem if you have a pass which creates PHI cycles like this. I guess GVN does in some cases? Can we avoid doing that?

[• dberlin]

Yeah, i'd really like to understand the value of this before make this code more complex and handle more cases.

Really, as we've discussed many times, BasicAA's complex phi/cycle handling should probably be moved out to a caching forward pass that properly resolves cycles, instead of a lazy backwards pass that tries depth limiting to handle cycles. This was waiting on the new pass manager work, AFAIK (because you couldn't cache it otherwise)

Now that this is done (again, AFAIK), one way to start doing that would be to make PhiAA here, have it handle the cycles you are talking about (it's trivial to compute phi-induced cycles and it's not going to affect compile time in any meaningful way even if you invalidate it a lot. There is code to do it already if you want it, it's <100 lines) and do caching, and fall back to BasicAA.

Then we can slowly move functionality into that, from BasicAA.

[john.brawn]

In D44564#1078564, @efriedma wrote:

Hmm. I don't see anything wrong with the code, but how often will this trigger? instcombine will remove the PHI nodes in your testcase, so this is only a problem if you have a pass which creates PHI cycles like this. I guess GVN does in some cases? Can we avoid doing that?

Yes, this comes from GVN where it temporarily introduces phi nodes like this that are later removed, but which in the meantime prevent PRE from happening because of this inaccurate alias analysis. I'd previously gone for the approach of fixing this in GVN in D44160, but the conclusion there was to do it in alias analysis.

In D44564#1078585, @dberlin wrote:

Yeah, i'd really like to understand the value of this before make this code more complex and handle more cases.

Really, as we've discussed many times, BasicAA's complex phi/cycle handling should probably be moved out to a caching forward pass that properly resolves cycles, instead of a lazy backwards pass that tries depth limiting to handle cycles. This was waiting on the new pass manager work, AFAIK (because you couldn't cache it otherwise)

Now that this is done (again, AFAIK), one way to start doing that would be to make PhiAA here, have it handle the cycles you are talking about (it's trivial to compute phi-induced cycles and it's not going to affect compile time in any meaningful way even if you invalidate it a lot. There is code to do it already if you want it, it's <100 lines) and do caching, and fall back to BasicAA.

Then we can slowly move functionality into that, from BasicAA.

If I understand you correctly, you're suggesting adding a new alias analysis pass which just handles phis (but by analyising them forwards, instead of backwards as BasicAA does), yes? This alias analysis would have to make use of the results of other alias analyses though: what we're doing is comparing a phi P against a value V by finding the underlying values of P then calling aliasCheck for those values and V. Is one alias analysis using the results of another alias analysis something that works?

Actually thinking about this while writing the above, it would probably make more sense to do things the other way around: have an analysis which gets the underlying values for a phi, and have BasicAA use that. So instead of building up V1Srcs here, we would instead do something like V1Srcs = PhiAnalysis.getUnderlyingValues(PN). I think that would be better?

[• dberlin]

In D44564#1079811, @john.brawn wrote:

In D44564#1078564, @efriedma wrote:

Hmm. I don't see anything wrong with the code, but how often will this trigger? instcombine will remove the PHI nodes in your testcase, so this is only a problem if you have a pass which creates PHI cycles like this. I guess GVN does in some cases? Can we avoid doing that?

Yes, this comes from GVN where it temporarily introduces phi nodes like this that are later removed, but which in the meantime prevent PRE from happening because of this inaccurate alias analysis. I'd previously gone for the approach of fixing this in GVN in D44160, but the conclusion there was to do it in alias analysis.

In D44564#1078585, @dberlin wrote:

Yeah, i'd really like to understand the value of this before make this code more complex and handle more cases.

Really, as we've discussed many times, BasicAA's complex phi/cycle handling should probably be moved out to a caching forward pass that properly resolves cycles, instead of a lazy backwards pass that tries depth limiting to handle cycles. This was waiting on the new pass manager work, AFAIK (because you couldn't cache it otherwise)

Now that this is done (again, AFAIK), one way to start doing that would be to make PhiAA here, have it handle the cycles you are talking about (it's trivial to compute phi-induced cycles and it's not going to affect compile time in any meaningful way even if you invalidate it a lot. There is code to do it already if you want it, it's <100 lines) and do caching, and fall back to BasicAA.

Then we can slowly move functionality into that, from BasicAA.

If I understand you correctly, you're suggesting adding a new alias analysis pass which just handles phis (but by analyising them forwards, instead of backwards as BasicAA does), yes?

Yes.

This alias analysis would have to make use of the results of other alias analyses though: what we're doing is comparing a phi P against a value V by finding the underlying values of P then calling aliasCheck for those values and V.

FWIW: What we do is actually not great.
What you really *want* to do is build the SCC's formed solely by the phi nodes so you collapse any cycles and only have to look at the operands that aren't phis.
You can see an example of this kind of algorithm in the scc based phi minimization here:
https://pp.info.uni-karlsruhe.de/uploads/publikationen/braun13cc.pdf

Then, somewhat similar to what you see driving that, the outerops is the set of stuff to check what the phi can alias.

Is one alias analysis using the results of another alias analysis something that works?

Yes, this works fine, AFAIK. We definitely do it right now :)

Actually thinking about this while writing the above, it would probably make more sense to do things the other way around: have an analysis which gets the underlying values for a phi, and have BasicAA use that. So instead of building up V1Srcs here, we would instead do something like V1Srcs = PhiAnalysis.getUnderlyingValues(PN). I think that would be better?

This is actually not possible, but that isn't going to be obvious to someone who hasn't delved into this.

Let me also try to back up and give a little context and see if you still come to that answer:
The way it works right now is that the AA code walks through a hierarchy of AA analysis, and keeps asking each until it gets NoAlias or MustAlias.
BasicAA is one of those passes.

Because of <technical reasons not worth getting into>, it used to be hard to build another AA that reused results from another analysis, and so people shoved more and more complex stuff stuff in BasicAA :)

Unfortunately, BasicAA is meant to be stateless and explicitly does no caching, and so these expensive computations occur every time you ask it an aliasing question.
You can't really have something it uses do caching, because there is no way to "invalidate" BasicAA.
The long term goal is to move those expensive computations somewhere else where they can be cached, and where the AA can be invalidated.

The personal way i viewed it was you have something like:

BasicAA <- gives simple, stateless AA answers that are ideally, constant time.
<One or more CachingAA depending on what we discover as we do this > <- gives the answers that are currently linear time or worse.

Right now, because BasicAA is so slow, it's at the *bottom* and not *the top*. We actually ask everything *before* we ask BasicAA, because it's N^2 (excepting depth limiting trying to keep it linear).

In this new world orders, BasicAA is at the top, doing quick checks, and checks get more expensive as you get down (similar to dependence analysis)

[john.brawn]

In D44564#1079954, @dberlin wrote:

You can't really have something it uses do caching, because there is no way to "invalidate" BasicAA.

But it looks like that's already happening? Looking at BasicAA::run it uses DominatorTreeAnalysis, and BasicAAResult::invalidate returns true if DominatorTreeAnalysis is invalidated.

Also, with regards to invalidation, how is this supposed to happen in the middle of a pass? What's happening in GVN currently is:

• A load is determined to be partially redundant
• A chain of phis is inserted, which ends up using the load
• The load is removed and all uses replaced with the end of the phi chain, which causes the phi chain to contain a loop with only one underlying value
• GVN then goes on to analyze another load which used to use the value of the first load but which now uses this phi chain
• GVN asks MemoryDependenceAnalysis about the dependencies of this load
• MemoryDependenceAnalysis asks AAResults
• AAResults asks BasicAAResult
• BasicAAResult now has to figure out this phi chain

If we have some analysis which looks at phis and caches the results (either PhiAnalysis calculating the underlying values of phis, or PhiAA calculating what phis alias with) then it needs to be recalculated somewhere between GVN removing the load and AAResults being asked about the phi that's been inserted. How is this supposed to happen?

[• dberlin]

In D44564#1083070, @john.brawn wrote:

In D44564#1079954, @dberlin wrote:

You can't really have something it uses do caching, because there is no way to "invalidate" BasicAA.

But it looks like that's already happening?

Not really intentionally, it just grew this way :-)

Looking at BasicAA::run it uses DominatorTreeAnalysis, and BasicAAResult::invalidate returns true if DominatorTreeAnalysis is invalidated.

Right, but that doesn't help your problem below either :)

Also, with regards to invalidation, how is this supposed to happen in the middle of a pass?

Which?
BasicAA invalidation or PhiAA invalidation?
Because you actually have the same problem below if the assumptions or dominator tree change in the middle of GVN.
Nothing will invalidate BasicAA in that case right now.
In that regard, we are not actually worse off.

What's happening in GVN currently is:

• A load is determined to be partially redundant
• A chain of phis is inserted, which ends up using the load
• The load is removed and all uses replaced with the end of the phi chain, which causes the phi chain to contain a loop with only one underlying value
• GVN then goes on to analyze another load which used to use the value of the first load but which now uses this phi chain
• GVN asks MemoryDependenceAnalysis about the dependencies of this load
• MemoryDependenceAnalysis asks AAResults
• AAResults asks BasicAAResult
• BasicAAResult now has to figure out this phi chain

If we have some analysis which looks at phis and caches the results (either PhiAnalysis calculating the underlying values of phis, or PhiAA calculating what phis alias with) then it needs to be recalculated somewhere between GVN removing the load and AAResults being asked about the phi that's been inserted.

Again, besides BasicAA *already* having this problem (and it just happens that you aren't touching a part that uses assumes or domtree), memdep has this problem too, and tries to provide an incremental invalidation/update interface.
Similarly, we would do the same for PhiAA.
In this case, MemDep's invalidation interface would invalidate PhiAA.
This also assumes a bunch of stuff (for example, that more powerful analysis can't resolve this regardless of the load being there, etc)

How is this supposed to happen?

Nothing here, in any way, is an entirely well designed and architected complete solution to these problems :)
You are welcome to suggest one :)

[john.brawn]

After some tinkering I've come up with the following solution (I have something that seems to work, but it needs cleaning up and testing):

• Add a PhiAnalysis analysis pass which returns a PhiInfo
• PhiInfo::getUnderlyingPhiValues takes a PHINode and returns the set of non-phi values reachable from that phi
• PhiInfo stores a map of PHINode->values which is initially empty, but is incrementally updated whenever getUnderlyingPhiValues is called on a phi we haven't yet calculated
• BasicAA uses PhiAnalysis if it's available
• When it is BasicAAResults::aliasPHI populates V1Srcs from getUnderlyingPhiValues, otherwise it does what it currently does
• MemoryDependenceAnalysis uses PhiAnalysis, which then makes it available to BasicAA
• MemoryDependenceResults::removeInstruction clears the PhiInfo map, to make sure later queries are correct

Doing all this gets me what I want, which is GVN getting correct aliasing information for the phis that it inserts. I've avoided doing this by adding another alias analysis to basically limit how much work I need to do to get this working, and it means whoever does do that in the future can just make the new alias analysis use PhiAnalysis for that part of it. Also there's maybe other parts of the compiler that want this kind of information.

Does this seem reasonable?

[sebpop]

In D44564#1085363, @john.brawn wrote:

After some tinkering I've come up with the following solution (I have something that seems to work, but it needs cleaning up and testing):

• Add a PhiAnalysis analysis pass which returns a PhiInfo

I think this makes sense as Danny suggested to move everything that is not constant time
away from BasicAA in different analysis passes whose results could be cached and invalidated.

• PhiInfo::getUnderlyingPhiValues takes a PHINode and returns the set of non-phi values reachable from that phi

I think this makes sense as it goes in the same direction where Danny was pointing earlier:
"What you really *want* to do is build the SCC's formed solely by the phi nodes so you collapse any cycles and only have to look at the operands that aren't phis."

• PhiInfo stores a map of PHINode->values which is initially empty, but is incrementally updated whenever getUnderlyingPhiValues is called on a phi we haven't yet calculated
• BasicAA uses PhiAnalysis if it's available
• When it is BasicAAResults::aliasPHI populates V1Srcs from getUnderlyingPhiValues, otherwise it does what it currently does
• MemoryDependenceAnalysis uses PhiAnalysis, which then makes it available to BasicAA
• MemoryDependenceResults::removeInstruction clears the PhiInfo map, to make sure later queries are correct

Doing all this gets me what I want, which is GVN getting correct aliasing information for the phis that it inserts. I've avoided doing this by adding another alias analysis to basically limit how much work I need to do to get this working, and it means whoever does do that in the future can just make the new alias analysis use PhiAnalysis for that part of it. Also there's maybe other parts of the compiler that want this kind of information.

Does this seem reasonable?

I think this proposal is reasonable, although Danny should comment on it.
In the mean time, could you please post the updated patch? Thanks!

[john.brawn]

A bit of an update on this: instead of the circuitous route of having PhiInfo be optionally used by BasicAA then having MemoryDependenceAnalysis use PhiInfo in order to make it available to BasicAA I've gone for making BasicAA use it directly but have PhiInfo use ValueHandles (in a way rather similar to AssumptionCache does) in a way that gets it automatically updated if the function changes. This makes everything much simpler in terms of how it gets used, but it's been taking a while to get the implementation right.

[john.brawn]

Modify this so that it uses the PhiValuesAnalysis pass added by D47893. This patch also now depends on D44160 as this modifies a test added by that.

[john.brawn]

It turns out that we can't safely use PhiValuesAnalysis always from BasicAA, so instead a pass has to explicitly use it if it knows it is safe. I have a follow-on patch from this to make MemoryDependenceAnalysis do that, but it's not quite finished yet (I need to adjust some tests).

[john.brawn]

Making memory dependence analysis use phi values analysis so basicaa can use it is in D48489.

[john.brawn]

@brzycki pointed out to me a test case where we get a crash with this patch which turns out to be due to BasicAA using stale PhiValuesAnalysis results due to how the legacy pass manager handles pass dependencies. Updated this patch to fix that problem by marking BasicAA as not CFG-only.

[john.brawn]

Rebased patch on top of recent changes.

[hfinkel]

We have a check in aliasSameBasePointerGEPs to avoid PR32314 (which I'll glibly summarize as: we need to be careful about looking through PHIs so that we don't, without realizing it, end up comparing values from different loop iterations). The fact that this looks back through an unknown number of PHIs makes me concerned that we'll get into a similar situation.

I apologize for ignoring this review for so long, but I think that this is really important. Even with the PR32314 check currently there, I suspect that the fundamental algorithm for looking back through PHIs in BasicAA is still not sound, and we need to be careful going forward. As such, I'd like to see this patch updated with additional comments explaining:

1. Can we get back values from different loop iterations from PhiValues.
2. If so, is there special care that must be taken in handling them.
3. Are we currently doing what's necessary to handle them correctly.

Thanks!

[john.brawn]

In D44564#1162264, @hfinkel wrote:

We have a check in aliasSameBasePointerGEPs to avoid PR32314 (which I'll glibly summarize as: we need to be careful about looking through PHIs so that we don't, without realizing it, end up comparing values from different loop iterations). The fact that this looks back through an unknown number of PHIs makes me concerned that we'll get into a similar situation.

I apologize for ignoring this review for so long, but I think that this is really important. Even with the PR32314 check currently there, I suspect that the fundamental algorithm for looking back through PHIs in BasicAA is still not sound, and we need to be careful going forward. As such, I'd like to see this patch updated with additional comments explaining:

1. Can we get back values from different loop iterations from PhiValues.
2. If so, is there special care that must be taken in handling them.
3. Are we currently doing what's necessary to handle them correctly.

Thanks!

I've been looking looking around basicaa for a while and how it's handling this kind of thing, and I think the short answer here is that this patch means we're doing more of the same thing that we're already doing so it doesn't introduce any new bugs but could possibly make already-existing bugs (if there are any) reveal themselves in more situations, but if so the fix would be elsewhere not here.

The long answer (which I've written mostly to make sure I have my own thoughts in order, so possibly not especially coherent):

The general structure of BasicAAResult::aliasCheck, the main alias-checking function, seems to be:

• See if, by looking at V1 and V2 as atomic things, we can determine if V1 and V2 definitely point to either the same or different things.
• If not, and V1 or V2 is a gep, phi, or select, try breaking up V1 or V2 into component parts and comparing it with the other.
• If that doesn't give us MustAlias or NoAlias, go check the other alias analyses.

What we have to be careful about then is that we don't have a situation where we break up V1 into individual components, see that there's no alias with V2, then conclude that there's no alias between V1 and V2 as a whole but actually there is.

Going and looking at PR32314 specifically, a simplified version of that is

loop:
 %phi1 = phi [ undef, %entry ], [ %gep2, %loop ]
 %phi2 = phi [ 1, %entry ], [ %inc, %loop ]
 %inc = add %phi2, 1
 %sub = add %phi2, -1
 %gep1 = getelementptr %arr, %sub
 %gep2 = getelementptr %arr, %phi2
 store %foo, %gep1
 %bar = load %phi1

The problem here is that for the same value of %phi2, %gep1 and %gep2 point to different memory locations, but when comparing %phi1 and %gep1 we can't just say "given that %phi's only value is %gep2, we can check if %phi1 and %gep1 alias by checking if %gep1 and %gep2 alias" because the value of %phi2 in the context of the value of %gep2 on the loop back-edge is different to the value of %phi2 in the %gep1 not on that back-edge.

The question then is: is it the responsibility of the phi node handling when it's doing the recursive aliasCheck to do something special to handle this, or is it the responsibility of aliasCheck to realise that the same sub-expression in V1 and V2 may have different values? Currently, it looks like it's the responsibility of aliasCheck, or at least the fix for PR32314 was done by making a specific part of aliasSameBasePointerGEPs aware that the same phi in a subexpression of the indices of two geps could have different values.

So, getting back to this patch, what's changed? Instead of just looking at the direct incoming values of a phi, and giving up if one of those is a phi, we get the total set of non-phi values gotten by traversing the phi tree. From the perspective of avoiding path-sensitive value difference there's no change to before: it's up to the recursive aliasCheck call to get things right, and doing things differently in this way doesn't fundamentally change things as far as I can tell: we either get it right, or we get it wrong, and if we get it wrong there would have been some other situation where originally we would have got it wrong as well.

So to answer your specific questions:

Can we get back values from different loop iterations from PhiValues.

Yes, but that's no change to how things were before.

If so, is there special care that must be taken in handling them.

Nothing that we didn't already need to do.

Are we currently doing what's necessary to handle them correctly.

I assume so, but the necessary handling would be in the recursive aliasCheck call, not here.

[john.brawn]

Ping.

[sebpop]

Looks good to me. Thanks!

[asbirlea]

In D44564#1153048, @john.brawn wrote:

@brzycki pointed out to me a test case where we get a crash with this patch which turns out to be due to BasicAA using stale PhiValuesAnalysis results due to how the legacy pass manager handles pass dependencies. Updated this patch to fix that problem by marking BasicAA as not CFG-only.

Would you mind sharing this test case if this is still the case?
I'd like to understand if we can lift the restriction of marking BasicAA as not CFG-only, and I see no test crashes from making this change at ToT.
Did the changes in https://reviews.llvm.org/rL340613 resolve this?

include/llvm/Analysis/BasicAliasAnalysis.h

 class DataLayout;
 class DominatorTree;
 class Function;
 class GEPOperator;
 class LoopInfo;
 class PHINode;
 class SelectInst;
 class TargetLibraryInfo;
+class PhiValues;
 class Value;
 
 /// This is the AA result object for the basic, local, and stateless alias
 /// analysis. It implements the AA query interface in an entirely stateless
 /// manner. As one consequence, it is never invalidated due to IR changes.
 /// While it does retain some storage, that is used as an optimization and not
 /// to preserve information from query to query. However it does retain handles
 /// to various other analyses and must be recomputed when those analyses are.
 class BasicAAResult : public AAResultBase<BasicAAResult> {
   friend AAResultBase<BasicAAResult>;
 
   const DataLayout &DL;
   const TargetLibraryInfo &TLI;
   AssumptionCache &AC;
   DominatorTree *DT;
   LoopInfo *LI;
+  PhiValues *PV;
 
 public:
   BasicAAResult(const DataLayout &DL, const TargetLibraryInfo &TLI,
                 AssumptionCache &AC, DominatorTree *DT = nullptr,
-                LoopInfo *LI = nullptr)
-      : AAResultBase(), DL(DL), TLI(TLI), AC(AC), DT(DT), LI(LI) {}
+                LoopInfo *LI = nullptr, PhiValues *PV = nullptr)
+      : AAResultBase(), DL(DL), TLI(TLI), AC(AC), DT(DT), LI(LI), PV(PV) {}
 
   BasicAAResult(const BasicAAResult &Arg)
       : AAResultBase(Arg), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC), DT(Arg.DT),
-        LI(Arg.LI) {}
+        LI(Arg.LI), PV(Arg.PV) {}
   BasicAAResult(BasicAAResult &&Arg)
       : AAResultBase(std::move(Arg)), DL(Arg.DL), TLI(Arg.TLI), AC(Arg.AC),
-        DT(Arg.DT), LI(Arg.LI) {}
+        DT(Arg.DT), LI(Arg.LI), PV(Arg.PV) {}
 
   /// Handle invalidation events in the new pass manager.
   bool invalidate(Function &F, const PreservedAnalyses &PA,
                   FunctionAnalysisManager::Invalidator &Inv);
 
   AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB);
 
   ModRefInfo getModRefInfo(ImmutableCallSite CS, const MemoryLocation &Loc);

lib/Analysis/BasicAliasAnalysis.cpp

 #include "llvm/Analysis/CFG.h"
 #include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
 #include "llvm/Analysis/MemoryLocation.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/Analysis/PhiValues.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"

 bool BasicAAResult::invalidate(Function &F, const PreservedAnalyses &PA,
                                FunctionAnalysisManager::Invalidator &Inv) {
   // We don't care if this analysis itself is preserved, it has no state. But
   // we need to check that the analyses it depends on have been. Note that we
   // may be created without handles to some analyses and in that case don't
   // depend on them.
   if (Inv.invalidate<AssumptionAnalysis>(F, PA) ||
       (DT && Inv.invalidate<DominatorTreeAnalysis>(F, PA)) ||
-      (LI && Inv.invalidate<LoopAnalysis>(F, PA)))
+      (LI && Inv.invalidate<LoopAnalysis>(F, PA)) ||
+      (PV && Inv.invalidate<PhiValuesAnalysis>(F, PA)))
     return true;
 
   // Otherwise this analysis result remains valid.
   return false;
 }
 
 //===----------------------------------------------------------------------===//
 // Useful predicates
if (PN2->getParent() == PN->getParent()) {
 
       // Reset if speculation failed.
       if (Alias != NoAlias)
         AliasCache[Locs] = OrigAliasResult;
 
       return Alias;
     }
 
-  SmallPtrSet<Value *, 4> UniqueSrc;
   SmallVector<Value *, 4> V1Srcs;
   bool isRecursive = false;
+  if (PV)  {
+    // If we have PhiValues then use it to get the underlying phi values.
+    const PhiValues::ValueSet &PhiValueSet = PV->getValuesForPhi(PN);
+    // If we have more phi values than the search depth then return MayAlias
+    // conservatively to avoid compile time explosion. The worst possible case
+    // is if both sides are PHI nodes. In which case, this is O(m x n) time
+    // where 'm' and 'n' are the number of PHI sources.
+    if (PhiValueSet.size() > MaxLookupSearchDepth)
+      return MayAlias;
+    // Add the values to V1Srcs
+    for (Value *PV1 : PhiValueSet) {
+      if (EnableRecPhiAnalysis) {
+        if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
+          // Check whether the incoming value is a GEP that advances the pointer
+          // result of this PHI node (e.g. in a loop). If this is the case, we
+          // would recurse and always get a MayAlias. Handle this case specially
+          // below.
+          if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 &&
+              isa<ConstantInt>(PV1GEP->idx_begin())) {
+            isRecursive = true;
+            continue;
+          }
+        }
+      }
+      V1Srcs.push_back(PV1);
+    }
+  } else {
+    // If we don't have PhiInfo then just look at the operands of the phi itself
+    // FIXME: Remove this once we can guarantee that we have PhiInfo always
+    SmallPtrSet<Value *, 4> UniqueSrc;
     for (Value *PV1 : PN->incoming_values()) {
       if (isa<PHINode>(PV1))
         // If any of the source itself is a PHI, return MayAlias conservatively
         // to avoid compile time explosion. The worst possible case is if both
         // sides are PHI nodes. In which case, this is O(m x n) time where 'm'
         // and 'n' are the number of PHI sources.
         return MayAlias;
 
       if (EnableRecPhiAnalysis)
         if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
           // Check whether the incoming value is a GEP that advances the pointer
           // result of this PHI node (e.g. in a loop). If this is the case, we
           // would recurse and always get a MayAlias. Handle this case specially
           // below.
           if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 &&
               isa<ConstantInt>(PV1GEP->idx_begin())) {
             isRecursive = true;
             continue;
           }
         }
 
       if (UniqueSrc.insert(PV1).second)
         V1Srcs.push_back(PV1);
     }
+  }
+
+  // If V1Srcs is empty then that means that the phi has no underlying non-phi
+  // value. This should only be possible in blocks unreachable from the entry
+  // block, but return MayAlias just in case.
+  if (V1Srcs.empty())
+    return MayAlias;
 
   // If this PHI node is recursive, set the size of the accessed memory to
   // unknown to represent all the possible values the GEP could advance the
   // pointer to.
   if (isRecursive)
     PNSize = MemoryLocation::UnknownSize;
 
   AliasResult Alias =
       aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0],
                  PNSize, PNAAInfo, UnderV2);
 
   // Early exit if the check of the first PHI source against V2 is MayAlias.
   // Other results are not possible.
   if (Alias == MayAlias)
     return MayAlias;
 
   // If all sources of the PHI node NoAlias or MustAlias V2, then returns

 
 AnalysisKey BasicAA::Key;
 
 BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) {
   return BasicAAResult(F.getParent()->getDataLayout(),
                        AM.getResult<TargetLibraryAnalysis>(F),
                        AM.getResult<AssumptionAnalysis>(F),
                        &AM.getResult<DominatorTreeAnalysis>(F),
-                       AM.getCachedResult<LoopAnalysis>(F));
+                       AM.getCachedResult<LoopAnalysis>(F),
+                       AM.getCachedResult<PhiValuesAnalysis>(F));
 }
 
 BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) {
     initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry());
 }
 
 char BasicAAWrapperPass::ID = 0;
 
 void BasicAAWrapperPass::anchor() {}
 
 INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa",
-                      "Basic Alias Analysis (stateless AA impl)", true, true)
+                      "Basic Alias Analysis (stateless AA impl)", false, true)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa",
-                    "Basic Alias Analysis (stateless AA impl)", true, true)
+                    "Basic Alias Analysis (stateless AA impl)", false, true)
 
 FunctionPass *llvm::createBasicAAWrapperPass() {
   return new BasicAAWrapperPass();
 }
 
 bool BasicAAWrapperPass::runOnFunction(Function &F) {
   auto &ACT = getAnalysis<AssumptionCacheTracker>();
   auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
   auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
   auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
+  auto *PVWP = getAnalysisIfAvailable<PhiValuesWrapperPass>();
 
   Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), TLIWP.getTLI(),
                                  ACT.getAssumptionCache(F), &DTWP.getDomTree(),
-                                 LIWP ? &LIWP->getLoopInfo() : nullptr));
+                                 LIWP ? &LIWP->getLoopInfo() : nullptr,
+                                 PVWP ? &PVWP->getResult() : nullptr));
 
   return false;
 }
 
 void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
   AU.setPreservesAll();
   AU.addRequired<AssumptionCacheTracker>();
   AU.addRequired<DominatorTreeWrapperPass>();
   AU.addRequired<TargetLibraryInfoWrapperPass>();
+  AU.addUsedIfAvailable<PhiValuesWrapperPass>();
 }
 
 BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) {
   return BasicAAResult(
       F.getParent()->getDataLayout(),
       P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
       P.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F));
 }

test/Analysis/BasicAA/invalidation.ll

 ; RUN:     | FileCheck %s --check-prefix=CHECK-LI-INVALIDATE
 ; CHECK-LI-INVALIDATE: Running pass: RequireAnalysisPass
 ; CHECK-LI-INVALIDATE: Running analysis: BasicAA
 ; CHECK-LI-INVALIDATE: Running pass: InvalidateAnalysisPass
 ; CHECK-LI-INVALIDATE: Invalidating analysis: LoopAnalysis
 ; CHECK-LI-INVALIDATE: Invalidating analysis: BasicAA
 ; CHECK-LI-INVALIDATE: Running pass: AAEvaluator
 ; CHECK-LI-INVALIDATE: Running analysis: BasicAA
+;
+; Check PhiValues specifically.
+; RUN: opt -disable-output -disable-verify -debug-pass-manager %s 2>&1 \
+; RUN:     -passes='require<phi-values>,require<aa>,invalidate<phi-values>,aa-eval' -aa-pipeline='basic-aa' \
+; RUN:     | FileCheck %s --check-prefix=CHECK-PV-INVALIDATE
+; CHECK-PV-INVALIDATE: Running pass: RequireAnalysisPass
+; CHECK-PV-INVALIDATE: Running analysis: BasicAA
+; CHECK-PV-INVALIDATE: Running pass: InvalidateAnalysisPass
+; CHECK-PV-INVALIDATE: Invalidating analysis: PhiValuesAnalysis
+; CHECK-PV-INVALIDATE: Invalidating analysis: BasicAA
+; CHECK-PV-INVALIDATE: Running pass: AAEvaluator
+; CHECK-PV-INVALIDATE: Running analysis: BasicAA
 
 ; Some code that will result in actual AA queries, including inside of a loop.
 ; FIXME: Sadly, none of these queries managed to use either the domtree or
 ; loopinfo that basic-aa cache. But nor does any other test in LLVM. It would
 ; be good to enhance this to actually use these other analyses to make this
 ; a more thorough test.
 define void @foo(i1 %x, i8* %p1, i8* %p2) {
 entry:

test/Analysis/BasicAA/phi-aa.ll

-; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
-; RUN: opt < %s -aa-pipeline=basic-aa -passes=aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -phi-values -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
+; RUN: opt < %s -aa-pipeline=basic-aa -passes='require<phi-values>,aa-eval' -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; rdar://7282591
 
 @X = common global i32 0
 @Y = common global i32 0
 @Z = common global i32 0
bye:
   ret i32 %.reload
 }
 
 declare i1 @cond(i32*)
 
 declare void @inc(i32*)
 
 
+; When we have a chain of phis in nested loops we should recognise if there's
+; actually only one underlying value.
+; CHECK-LABEL: loop_phi_chain
+; CHECK: NoAlias: i32* %val1, i32* @Y
+; CHECK: NoAlias: i32* %val2, i32* @Y
+; CHECK: NoAlias: i32* %val3, i32* @Y
+define void @loop_phi_chain(i32 %a, i32 %b, i32 %c) {
+entry:
+  br label %loop1
+
+loop1:
+  %n1 = phi i32 [ 0, %entry ], [ %add1, %loop2 ]
+  %val1 = phi i32* [ @X, %entry ], [ %val2, %loop2 ]
+  %add1 = add i32 %n1, 1
+  %cmp1 = icmp ne i32 %n1, 32
+  br i1 %cmp1, label %loop2, label %end
+
+loop2:
+  %n2 = phi i32 [ 0, %loop1 ], [ %add2, %loop3 ]
+  %val2 = phi i32* [ %val1, %loop1 ], [ %val3, %loop3 ]
+  %add2 = add i32 %n2, 1
+  %cmp2 = icmp ne i32 %n2, 32
+  br i1 %cmp2, label %loop3, label %loop1
+
+loop3:
+  %n3 = phi i32 [ 0, %loop2 ], [ %add3, %loop3 ]
+  %val3 = phi i32* [ %val2, %loop2 ], [ %val3, %loop3 ]
+  store i32 0, i32* %val3, align 4
+  store i32 0, i32* @Y, align 4
+  %add3 = add i32 %n3, 1
+  %cmp3 = icmp ne i32 %n3, 32
+  br i1 %cmp3, label %loop3, label %loop2
+
+end:
+  ret void
+}

test/Analysis/BasicAA/phi-values-usage.ll

+; RUN: opt -debug-pass=Executions -phi-values -memcpyopt -instcombine -disable-output < %s 2>&1 | FileCheck %s
+
+; Check that phi values is not run when it's not already available, and that
+; basicaa is freed after a pass that preserves CFG.
+
+; CHECK: Executing Pass 'Phi Values Analysis'
+; CHECK: Executing Pass 'Basic Alias Analysis (stateless AA impl)'
+; CHECK: Executing Pass 'Memory Dependence Analysis'
+; CHECK: Executing Pass 'MemCpy Optimization'
+; CHECK-DAG: Freeing Pass 'MemCpy Optimization'
+; CHECK-DAG: Freeing Pass 'Phi Values Analysis'
+; CHECK-DAG: Freeing Pass 'Memory Dependence Analysis'
+; CHECK-DAG: Freeing Pass 'Basic Alias Analysis (stateless AA impl)'
+; CHECK-NOT: Executing Pass 'Phi Values Analysis'
+; CHECK: Executing Pass 'Basic Alias Analysis (stateless AA impl)'
+; CHECK: Executing Pass 'Combine redundant instructions'
+
+declare void @otherfn([4 x i8]*)
+declare i32 @__gxx_personality_v0(...)
+
+; This function is one where if we didn't free basicaa after memcpyopt then the
+; usage of basicaa in instcombine would cause a segfault due to stale phi-values
+; results being used.
+define void @fn(i8* %this, i64* %ptr) personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*) {
+entry:
+  %arr = alloca [4 x i8], align 8
+  %gep1 = getelementptr inbounds [4 x i8], [4 x i8]* %arr, i64 0, i32 0
+  br i1 undef, label %then, label %if
+
+if:
+  br label %then
+
+then:
+  %phi = phi i64* [ %ptr, %if ], [ null, %entry ]
+  store i8 1, i8* %gep1, align 8
+  %load = load i64, i64* %phi, align 8
+  %gep2 = getelementptr inbounds i8, i8* undef, i64 %load
+  %gep3 = getelementptr inbounds i8, i8* %gep2, i64 40
+  invoke i32 undef(i8* undef)
+     to label %invoke unwind label %lpad
+
+invoke:
+  unreachable
+
+lpad:
+  landingpad { i8*, i32 }
+     catch i8* null
+  call void @otherfn([4 x i8]* nonnull %arr)
+  unreachable
+}

test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT:       FunctionPass Manager
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         SROA
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Early CSE w/ MemorySSA
 ; CHECK-NEXT:         Speculatively execute instructions if target has divergent branches
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results

 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Induction Variable Simplification
 ; CHECK-NEXT:           Recognize loop idioms
 ; CHECK-NEXT:           Delete dead loops
 ; CHECK-NEXT:           Unroll loops
 ; CHECK-NEXT:         MergedLoadStoreMotion
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Global Value Numbering
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         MemCpy Optimization
 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
 ; CHECK-NEXT:         Demanded bits analysis
 ; CHECK-NEXT:         Bit-Tracking Dead Code Elimination
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Aggressive Dead Code Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction

test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:       FunctionPass Manager
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         SROA
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Early CSE w/ MemorySSA
 ; CHECK-NEXT:         Speculatively execute instructions if target has divergent branches
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Combine pattern based expressions
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)

 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Induction Variable Simplification
 ; CHECK-NEXT:           Recognize loop idioms
 ; CHECK-NEXT:           Delete dead loops
 ; CHECK-NEXT:           Unroll loops
 ; CHECK-NEXT:         MergedLoadStoreMotion
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Global Value Numbering
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         MemCpy Optimization
 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
 ; CHECK-NEXT:         Demanded bits analysis
 ; CHECK-NEXT:         Bit-Tracking Dead Code Elimination
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Aggressive Dead Code Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction

test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT:       FunctionPass Manager
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         SROA
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory SSA
 ; CHECK-NEXT:         Early CSE w/ MemorySSA
 ; CHECK-NEXT:         Speculatively execute instructions if target has divergent branches
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results

 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Induction Variable Simplification
 ; CHECK-NEXT:           Recognize loop idioms
 ; CHECK-NEXT:           Delete dead loops
 ; CHECK-NEXT:           Unroll loops
 ; CHECK-NEXT:         MergedLoadStoreMotion
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Global Value Numbering
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         MemCpy Optimization
 ; CHECK-NEXT:         Sparse Conditional Constant Propagation
 ; CHECK-NEXT:         Demanded bits analysis
 ; CHECK-NEXT:         Bit-Tracking Dead Code Elimination
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Lazy Branch Probability Analysis
 ; CHECK-NEXT:         Lazy Block Frequency Analysis
 ; CHECK-NEXT:         Optimization Remark Emitter
 ; CHECK-NEXT:         Combine redundant instructions
 ; CHECK-NEXT:         Lazy Value Information Analysis
 ; CHECK-NEXT:         Jump Threading
 ; CHECK-NEXT:         Value Propagation
 ; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Memory Dependence Analysis
 ; CHECK-NEXT:         Dead Store Elimination
 ; CHECK-NEXT:         Natural Loop Information
 ; CHECK-NEXT:         Canonicalize natural loops
 ; CHECK-NEXT:         LCSSA Verifier
 ; CHECK-NEXT:         Loop-Closed SSA Form Pass
+; CHECK-NEXT:         Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:         Function Alias Analysis Results
 ; CHECK-NEXT:         Scalar Evolution Analysis
 ; CHECK-NEXT:         Loop Pass Manager
 ; CHECK-NEXT:           Loop Invariant Code Motion
 ; CHECK-NEXT:         Post-Dominator Tree Construction
 ; CHECK-NEXT:         Aggressive Dead Code Elimination
 ; CHECK-NEXT:         Simplify the CFG
 ; CHECK-NEXT:         Dominator Tree Construction

test/Transforms/SCCP/preserve-analysis.ll

 ; RUN: opt < %s -debug-pass=Structure -globals-aa -loop-vectorize -sccp -loop-vectorize -globals-aa 2>&1 -S | FileCheck %s
 ; RUN: opt < %s -debug-pass-manager -passes='loop-vectorize,sccp,loop-vectorize' 2>&1 -S | FileCheck --check-prefix=NEW-PM %s
 
 ; Check CFG-only analysis are preserved by SCCP by running it between 2
 ; loop-vectorize runs.
 
 ; CHECK: Globals Alias Analysis
 ; CHECK: Dominator Tree Construction
 ; CHECK: Natural Loop Information
-; CHECK: Basic Alias Analysis (stateless AA impl)
 ; CHECK: Sparse Conditional Constant Propagation
 ; CHECK-NOT: Dominator Tree Construction
 ; CHECK-NOT: Natural Loop Information
-; CHECK-NOT: Basic Alias Analysis (stateless AA impl)
 ; CHECK-NOT: Globals Alias Analysis
 ; CHECK: Loop Vectorization
 
 ; NEW-PM-DAG: Running analysis: LoopAnalysis on test
 ; NEW-PM-DAG: Running analysis: DominatorTreeAnalysis on test
 ; NEW-PM-DAG: Running analysis: AssumptionAnalysis on test
 ; NEW-PM-DAG: Running analysis: TargetLibraryAnalysis on test
 ; NEW-PM-DAG: Running analysis: TargetIRAnalysis on test