[AliasSetTracker] Update AAInfo check.

[asbirlea]

Summary

The correction of the AAInfo check in r371139 resolved a bug but may be
too restrictive if existing MDNodes are already null.
Also, AAInfo should either be a tombstone if a mismatch exists or the
old AAInfo otherwise.

[hfinkel]

include/llvm/Analysis/AliasSetTracker.h

91–92

This seems overly restrictive. The intersection might return a valid combination of the two metadata nodes (as a conservative combination). I thought that it only returned null if there's no valid way to combine them.

[asbirlea]

include/llvm/Analysis/AliasSetTracker.h

91–92

The intersection method does this:

AAMDNodes Result;
Result.TBAA = Other.TBAA == TBAA ? TBAA : nullptr;
Result.Scope = Other.Scope == Scope ? Scope : nullptr;
Result.NoAlias = Other.NoAlias == NoAlias ? NoAlias : nullptr;
return Result;

This is its only callsite.
I don't really know what a valid combination of two metadata nodes is TBH.

The "before" state was "if all fields are null, use tombstonekey, otherwise, use above intersection (fields set to null if different)". This is incomplete because any different field may need to merge sets (return SizeChanged = true;).

After I amended the above (current state), now we may return tombstonekey even when a field was nullptr to begin with in both AAInfo and NewAAInfo. Hence the change below to check for any difference.

Could you help me out with suggesting a less restrictive check?

[hfinkel]

include/llvm/Analysis/AliasSetTracker.h

91–92

Why can't we keep the fields that are the same? Perhaps this was the problematic behavior, but we should at least have some comments explaining why we can't.

In the bug report (PR42969), you wrote:

The metadata is correct in both cases. In the vector block the load/store do not alias because of the noscope metadata added by vectorization (vectorization "guarantees" the two do not alias even though basicaaa would find they do). In the scalar block they alias due to basicaa. The metadata was simply not being checked properly. Even if we can prove no-alias between two pointers, if a metadata change occurs, then we need to check if we need to merge the sets.

And so part of the situation here may be phrased as the AST supporting context/flow-insensitive AA?

91–92

Given what we know about the code below, is this sound?

91–92

First, in general, I think that we really need better comments in this function. It does not document the meaning of its return value or arguments, and clearly this is non-trivial.

Second, SizeChanged now seems like a somewhat-misleading name for this variable (because it is not just the size). We should probably rename it.

Third, the return value of this function is not always used. In AliasSet::addPointer it is ignored (and, thus, does not affect the subsequent behavior of adding the pointer to the set). In AliasSetTracker::getAliasSetFor it causes merging when true. Maybe we want different behaviors in these different cases?

[asbirlea]

Update based on comments.

include/llvm/Analysis/AliasSetTracker.h

91–92

Would you mind elaborating?

91–92

Updated for the first and second comments.
For the third, I think this is WAI. The other calls are updating an existing Entry; other needed updates were already done in these cases (a potential merge, or we're in saturated mode).
I tried to better document this in the method.

91–92

I think it's correct to keep the fields that are the same.

And so part of the situation here may be phrased as the AST supporting context/flow-insensitive AA?

Yes.
I'm not sure if a correct situation exists where contradictory AAInfo can break the AST...it's probably beyond the scope of this patch, but worth thinking about it.

[hfinkel]

include/llvm/Analysis/AliasSetTracker.h

91–92

If an AAMD field going from non-null to null requires a merge, why does going from null to non-null not require a merge?

[asbirlea]

include/llvm/Analysis/AliasSetTracker.h

91–92

I don't think in this case we ever go from null to non-null.
It seems right after some thinking to do merge (set to null) when the fields are different vs tombstone key, so I updated below.

[asbirlea]

Gentle ping on this.

include/llvm/Analysis/AliasSetTracker.h

public:
     PointerRec *getNext() const { return NextInList; }
     bool hasAliasSet() const { return AS != nullptr; }
 
     PointerRec** setPrevInList(PointerRec **PIL) {
       PrevInList = PIL;
       return &NextInList;
     }
 
+    /// Update the size and aainfo for the current PointerRec, and return true
+    /// if a change was made that would trigger the need to merge alias sets.
     bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
-      bool SizeChanged = false;
+      bool SizeChanged = false, AAInfoChanged = false;
+      // If the new size is different, update the size of the current pointer
+      // record to the union of the old and new sizes.
       if (NewSize != Size) {
         LocationSize OldSize = Size;
         Size = isSizeSet() ? Size.unionWith(NewSize) : NewSize;
         SizeChanged = OldSize != Size;
       }
 
       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
         // We don't have a AAInfo yet. Set it to NewAAInfo.
         AAInfo = NewAAInfo;
-      else {
-        AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
-        if (!Intersection.TBAA || !Intersection.Scope ||
-            !Intersection.NoAlias) {
-          // NewAAInfo conflicts with AAInfo.
-          AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
-          SizeChanged = true;
-        }
-        AAInfo = Intersection;
-      }
-      return SizeChanged;
+      else if (AAInfo.TBAA != NewAAInfo.TBAA ||
+            AAInfo.Scope != NewAAInfo.Scope ||
+            AAInfo.NoAlias != NewAAInfo.NoAlias) {
+        // If there is a mismatch in AAInfo, use the intersection (set to
+        // nullptr all the AAInfo nodes that are different).
+        AAInfo = AAInfo.intersect(NewAAInfo);
+        AAInfoChanged = true;
+      return SizeChanged || AAInfoChanged;
     }
 
     LocationSize getSize() const {
       assert(isSizeSet() && "Getting an unset size!");
       return Size;
     }
 
     /// Return the AAInfo, or null if there is no information or conflicting

lib/Analysis/AliasSetTracker.cpp

void AliasSetTracker::removeAliasSet(AliasSet *AS) {
   AliasSets.erase(AS);
 }
 
 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
   assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
   AST.removeAliasSet(this);
 }
 
+/// Add Entry to the current AliasSet, all potential set merges needed were done
+/// prior to this call. Update the info stored in Entry.
 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
                           LocationSize Size, const AAMDNodes &AAInfo,
                           bool KnownMustAlias, bool SkipSizeUpdate) {
   assert(!Entry.hasAliasSet() && "Entry already in set!");
 
   // Check to see if we have to downgrade to _may_ alias.
   if (isMustAlias())
     if (PointerRec *P = getSomePointer()) {
if (Entry.hasAliasSet()) {
       AliasAnyAS->addPointer(*this, Entry, Size, AAInfo);
     }
     return *AliasAnyAS;
   }
 
   bool MustAliasAll = false;
   // Check to see if the pointer is already known.
   if (Entry.hasAliasSet()) {
-    // If the size changed, we may need to merge several alias sets.
+    // If the size or aainfo changed, we may need to merge several alias sets.
     // Note that we can *not* return the result of mergeAliasSetsForPointer
     // due to a quirk of alias analysis behavior. Since alias(undef, undef)
     // is NoAlias, mergeAliasSetsForPointer(undef, ...) will not find the
     // the right set for undef, even if it exists.
     if (Entry.updateSizeAndAAInfo(Size, AAInfo))
       mergeAliasSetsForPointer(Pointer, Size, AAInfo, MustAliasAll);
     // Return the set!
     return *Entry.getAliasSet(*this)->getForwardedTarget(*this);