[BasicAA] Avoid calling GetUnderlyingObject, when the result of a previous call can be reused.

[amehsan]

Summary

This fixes the performance problem in PR27740. Also this patch includes code for a compile time opportunity in BasicAA.

Problem in 27740:

for the following pair :
%f35.pre-phi.i = phi float* [ %.pre6.i, %entry.if.else_crit_edge.i ], [ %.pre6.i, %land.lhs.true.if.else_crit_edge.i ]
%f11 = getelementptr inbounds %struct.s, %struct.s* %p1, i64 0, i32 1

where:
%.pre6.i = getelementptr inbounds %struct.s, %struct.s* %p1, i64 0, i32 3

We cannot prove that the pair is not aliased. This is because BasicAA first goes to aliasGEP, which recursively calls aliasCheck to look at aliasing for the base pointer of the GEP (with unknown size) and the phi node in the original pair. The result of that is a MayAlias. A number of alternative solutions have been discussed in this comment and also discussed with Hal.

The solution here, focuses on PHIs with a unique incoming value. This is very similar to what we do in stripPointerCasts, for GEP and some other cases, where we go past the current instruction, when all it does is hiding a pointer. I think potentially this functionality can be added to stripPointerCases, to look beyond phi nodes, but at this point I want to make this change limited, given the long conversations and investigations that we had about 27740.

Also, some of the recursive calls to aliasCheck, from alias[GEP|Select|PHI] pass one of the values for which GetUnderlyingObject is already called, again. So if we keep the underlying object that is already calculated around, we won't need to recompute it, given this is an expensive call.

I will add a test, by reducing the test case of 27740 and add to this.

[• dberlin]

This seems like a bad example.
For that example, the right solution is clearly to not generate a phi with
identical arguments.
Why not fix GVN to do that?

Given %f35.pre-phi.i = phi float* [ %.pre6.i, %entry.if.else_crit_edge.i ],
[ %.pre6.i, %land.lhs.true.if.else_crit_edge.i ]

%pre6.i must dominate this block, or else it would not be available through
both edges.

Thus, the phi is unnecessary, you could simply use %pre6.i instead, and you
would not have to add this code to BasicAA.

Given we generated this phi, we can simply not generate it :)

Do you have an example where that is not the case, and your patch to
BasicAA is needed?
(I would think EarlyCSE would eliminate all the above cases in input files
before other opts saw it)

Past that I'm not sure i believe this is the right thing to do, because
it's not clear to me where it logically ends and why.

IE if we next discover cases where all the phi arguments are redundant
bitcasts of the same value, do we add that?
What about more complex operations?

[• dberlin]

(aside from that, of course, i'm quite appreciative of speeding this up :P)

[hfinkel]

lib/Analysis/BasicAliasAnalysis.cpp

1427

Because GetUnderlyingObject is depth limited, as we walk up the use/def chain, we get closer to the real underlying object (in those somewhat-rare cases where we actually hit the depth cutoff). I'm quite happy to not do redundant work here, but we also don't want to regress on complex code either. I recommend trying something like this:

O1 = GetUnderlyingObject(O1 ? O1 : V1, DL, O1 ? 1 : MaxLookupSearchDepth).

[amehsan]

lib/Analysis/BasicAliasAnalysis.cpp

1427

Unless I am missing something, your suggested code, will change the behavior. MaxLookupSearchDepth is constant and does not change anywhere. So if we call aliasCheck with the exact same V1 again, we will call GetUnderlyingObject with exact same parameters. Given there has been no code change since the first call, the result will be exactly the same. O1 and O2 will be non-null only if we are passing exact same V1 (or V2) again to aliasCheck. So the proposed code change here, does not cause any change in the behavior.

[amehsan]

@dberlin

I see two concerns in your comment:

Why not fix GVN to do that?

Before GVN this phi node has two different incoming values. At some point A in GVN, one of the incoming values change and we get the phi node in the example above. At some point B in the GVN, the phi node is removed. Somewhere between A and B, GVN makes an alias analysis query. So I think there is not really a problem in GVN to fix.

IE if we next discover cases where all the phi arguments are redundant
bitcasts of the same value, do we add that?
What about more complex operations?

I think eventually, this code should be part of stripPointerCasts that we call in lines 1403-1404. There we handle pointers that are hidden behind bitcasts and GEPs where indices are zero.

[hfinkel]

In D22305#483557, @amehsan wrote:

@dberlin

I see two concerns in your comment:

Why not fix GVN to do that?

Before GVN this phi node has two different incoming values. At some point A in GVN, one of the incoming values change and we get the phi node in the example above. At some point B in the GVN, the phi node is removed. Somewhere between A and B, GVN makes an alias analysis query. So I think there is not really a problem in GVN to fix.

On the one hand, we generally don't construct our analyses to deal with trivially-non-canonical IR. One could argue that if GVN expects to use analyses on its intermediate states, then those states need to follow the rules too. On the other hand, arbitrary uses of RAUW can result in these kinds of PHIs, so this is not really a GVN problem, and handling this reduces our phase-ordering sensitivities. While several passes will clean these up, the same is true for several other things that stripPointerCasts handles.

IE if we next discover cases where all the phi arguments are redundant
bitcasts of the same value, do we add that?
What about more complex operations?

I think eventually, this code should be part of stripPointerCasts that we call in lines 1403-1404. There we handle pointers that are hidden behind bitcasts and GEPs where indices are zero.

I agree. If we're going to do this at all, the code should be added to stripPointerCasts. I don't see a good reason to add it here. Please split out the functional change from the performance-related change, and put the functional change in stripPointerCasts so it can be discussed separately.

[amehsan]

Please split out the functional change from the performance-related change, and put the functional change in stripPointerCasts so it can be discussed separately.

OK. I will change this patch to include only compile time speed up change. Then I will post another code review to include the look-past-the-phi change so we can discuss it separately.

[amehsan]

Separating two changes, so they can be discussed separately

[amehsan]

Ping :)
This patch currently only includes the compile time improvement. @hfinkel Did I answer your question?

[hfinkel]

In D22305#491329, @amehsan wrote:

Ping :)
This patch currently only includes the compile time improvement. @hfinkel Did I answer your question?

Yes, thanks, LGTM.

lib/Analysis/BasicAliasAnalysis.cpp

1427–1431

You can just say if (!O1) here, and similar below.

[amehsan]

Committed in 278519

include/llvm/Analysis/BasicAliasAnalysis.h

private:
 
   AliasResult aliasGEP(const GEPOperator *V1, uint64_t V1Size,
                        const AAMDNodes &V1AAInfo, const Value *V2,
                        uint64_t V2Size, const AAMDNodes &V2AAInfo,
                        const Value *UnderlyingV1, const Value *UnderlyingV2);
 
   AliasResult aliasPHI(const PHINode *PN, uint64_t PNSize,
                        const AAMDNodes &PNAAInfo, const Value *V2,
-                       uint64_t V2Size, const AAMDNodes &V2AAInfo);
+                       uint64_t V2Size, const AAMDNodes &V2AAInfo,
+                       const Value *UnderV2);
 
   AliasResult aliasSelect(const SelectInst *SI, uint64_t SISize,
                           const AAMDNodes &SIAAInfo, const Value *V2,
-                          uint64_t V2Size, const AAMDNodes &V2AAInfo);
+                          uint64_t V2Size, const AAMDNodes &V2AAInfo,
+                          const Value *UnderV2);
 
   AliasResult aliasCheck(const Value *V1, uint64_t V1Size, AAMDNodes V1AATag,
-                         const Value *V2, uint64_t V2Size, AAMDNodes V2AATag);
+                         const Value *V2, uint64_t V2Size, AAMDNodes V2AATag,
+                         const Value *O1 = nullptr, const Value *O2 = nullptr);
 };
 
 /// Analysis pass providing a never-invalidated alias analysis result.
 class BasicAA : public AnalysisInfoMixin<BasicAA> {
   friend AnalysisInfoMixin<BasicAA>;
   static char PassID;
 
 public:

lib/Analysis/BasicAliasAnalysis.cpp

if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
     // pointer, we know they cannot alias.
 
     // If both accesses are unknown size, we can't do anything useful here.
     if (V1Size == MemoryLocation::UnknownSize &&
         V2Size == MemoryLocation::UnknownSize)
       return MayAlias;
 
     AliasResult R = aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize,
-                               AAMDNodes(), V2, V2Size, V2AAInfo);
+                               AAMDNodes(), V2, V2Size, V2AAInfo,
+                               nullptr, UnderlyingV2);
     if (R != MustAlias)
       // If V2 may alias GEP base pointer, conservatively returns MayAlias.
       // If V2 is known not to alias GEP base pointer, then the two values
       // cannot alias per GEP semantics: "A pointer value formed from a
       // getelementptr instruction is associated with the addresses associated
       // with the first operand of the getelementptr".
       return R;
 
static AliasResult MergeAliasResults(AliasResult A, AliasResult B) {
   return MayAlias;
 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
 /// against another.
 AliasResult BasicAAResult::aliasSelect(const SelectInst *SI, uint64_t SISize,
                                        const AAMDNodes &SIAAInfo,
                                        const Value *V2, uint64_t V2Size,
-                                       const AAMDNodes &V2AAInfo) {
+                                       const AAMDNodes &V2AAInfo,
+                                       const Value *UnderV2) {
   // If the values are Selects with the same condition, we can do a more precise
   // check: just check for aliases between the values on corresponding arms.
   if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
     if (SI->getCondition() == SI2->getCondition()) {
       AliasResult Alias = aliasCheck(SI->getTrueValue(), SISize, SIAAInfo,
                                      SI2->getTrueValue(), V2Size, V2AAInfo);
       if (Alias == MayAlias)
         return MayAlias;
       AliasResult ThisAlias =
           aliasCheck(SI->getFalseValue(), SISize, SIAAInfo,
                      SI2->getFalseValue(), V2Size, V2AAInfo);
       return MergeAliasResults(ThisAlias, Alias);
     }
 
   // If both arms of the Select node NoAlias or MustAlias V2, then returns
   // NoAlias / MustAlias. Otherwise, returns MayAlias.
   AliasResult Alias =
-      aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(), SISize, SIAAInfo);
+      aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(),
+                 SISize, SIAAInfo, UnderV2);
   if (Alias == MayAlias)
     return MayAlias;
 
   AliasResult ThisAlias =
-      aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(), SISize, SIAAInfo);
+      aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(), SISize, SIAAInfo,
+                 UnderV2);
   return MergeAliasResults(ThisAlias, Alias);
 }
 
+static const Value *stripRedundantPHIs(const Value *V) {
+  const PHINode *PN = dyn_cast<PHINode>(V);
+  if (!PN)
+    return V;
+  for (unsigned i = 1, e = PN->getNumIncomingValues(); i < e; ++i) {
+    if (PN->getIncomingValue(i) != PN->getIncomingValue(0))
+     return V;
+  }
+  return PN->getIncomingValue(0);
+}
+
 /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
 /// another.
 AliasResult BasicAAResult::aliasPHI(const PHINode *PN, uint64_t PNSize,
                                     const AAMDNodes &PNAAInfo, const Value *V2,
-                                    uint64_t V2Size,
-                                    const AAMDNodes &V2AAInfo) {
+                                    uint64_t V2Size, const AAMDNodes &V2AAInfo,
+                                    const Value *UnderV2) {
   // Track phi nodes we have visited. We use this information when we determine
   // value equivalence.
   VisitedPhiBBs.insert(PN->getParent());
 
   // If the values are PHIs in the same block, we can do a more precise
   // as well as efficient check: just check for aliases between the values
   // on corresponding edges.
   if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
AliasResult BasicAAResult::aliasPHI(const PHINode *PN, uint64_t PNSize,
 
   // 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);
+      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
   // NoAlias / MustAlias. Otherwise, returns MayAlias.
   for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
     Value *V = V1Srcs[i];
 
     AliasResult ThisAlias =
-        aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo);
+        aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo, UnderV2);
     Alias = MergeAliasResults(ThisAlias, Alias);
     if (Alias == MayAlias)
       break;
   }
 
   return Alias;
 }
 
 /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
 /// array references.
 AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
                                       AAMDNodes V1AAInfo, const Value *V2,
-                                      uint64_t V2Size, AAMDNodes V2AAInfo) {
+                                      uint64_t V2Size, AAMDNodes V2AAInfo, 
+                                      const Value *O1, const Value *O2) {
   // If either of the memory references is empty, it doesn't matter what the
   // pointer values are.
   if (V1Size == 0 || V2Size == 0)
     return NoAlias;
 
   // Strip off any casts if they exist.
   V1 = V1->stripPointerCasts();
   V2 = V2->stripPointerCasts();
 
+  V1 = stripRedundantPHIs(V1);
+  V2 = stripRedundantPHIs(V2);
+
   // If V1 or V2 is undef, the result is NoAlias because we can always pick a
   // value for undef that aliases nothing in the program.
   if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
     return NoAlias;
 
   // Are we checking for alias of the same value?
   // Because we look 'through' phi nodes, we could look at "Value" pointers from
   // different iterations. We must therefore make sure that this is not the
   // case. The function isValueEqualInPotentialCycles ensures that this cannot
   // happen by looking at the visited phi nodes and making sure they cannot
   // reach the value.
   if (isValueEqualInPotentialCycles(V1, V2))
     return MustAlias;
 
   if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
     return NoAlias; // Scalars cannot alias each other
 
   // Figure out what objects these things are pointing to if we can.
-  const Value *O1 = GetUnderlyingObject(V1, DL, MaxLookupSearchDepth);
-  const Value *O2 = GetUnderlyingObject(V2, DL, MaxLookupSearchDepth);
+  if (O1 == nullptr)
+    O1 = GetUnderlyingObject(V1, DL, MaxLookupSearchDepth);
+
+  if (O2 == nullptr)
+    O2 = GetUnderlyingObject(V2, DL, MaxLookupSearchDepth);
 
   // Null values in the default address space don't point to any object, so they
   // don't alias any other pointer.
   if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
     if (CPN->getType()->getAddressSpace() == 0)
       return NoAlias;
   if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2))
     if (CPN->getType()->getAddressSpace() == 0)
if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
     AliasResult Result =
         aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2);
     if (Result != MayAlias)
       return AliasCache[Locs] = Result;
   }
 
   if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
     std::swap(V1, V2);
+    std::swap(O1, O2);
     std::swap(V1Size, V2Size);
     std::swap(V1AAInfo, V2AAInfo);
   }
   if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
-    AliasResult Result = aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo);
+    AliasResult Result = aliasPHI(PN, V1Size, V1AAInfo,
+                                  V2, V2Size, V2AAInfo, O2);
     if (Result != MayAlias)
       return AliasCache[Locs] = Result;
   }
 
   if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) {
     std::swap(V1, V2);
+    std::swap(O1, O2);
     std::swap(V1Size, V2Size);
     std::swap(V1AAInfo, V2AAInfo);
   }
   if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
     AliasResult Result =
-        aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo);
+        aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2);
     if (Result != MayAlias)
       return AliasCache[Locs] = Result;
   }
 
   // If both pointers are pointing into the same object and one of them
   // accesses the entire object, then the accesses must overlap in some way.
   if (O1 == O2)
     if ((V1Size != MemoryLocation::UnknownSize &&