[AliasSetTracker] Store AliasResult and pass it on mergeSetIn.

[asbirlea]

Summary

This saves an alias() call for must sets.
[Part of a series of clean-up patches]

[reames]

lib/Analysis/AliasSetTracker.cpp

76

I don't believe this is correct. The problem is that you're replacing an alias check between two sets with one between a one set and a pointer. We know that the pointer must become a member of the set, and with your new API, we know that it's a member of that set. However, we *don't* know it's a member of the other set.

Consider adding the pointer {p, 8} to the following sets:
{{p, 16}}, and {{p, 8}}.

Your code would conclude that the result set {{p, 16}} is MustAlias, which is incorrect.

A cleanup which would fix this would be to add the pointer *before* merging alias sets, not after.

194–196

The changes in signature to this function are obviously useful regardless of the rest of the patch. Feel free to separate them and commit without further review.

[asbirlea]

lib/Analysis/AliasSetTracker.cpp

313–314

I see your point above, thanks for noticing!
I believe the issue is resolved over here with adding:

if (AR != MustAlias)
   FoundSet.Alias = SetMayAlias;

What do you think?

[asbirlea]

lib/Analysis/AliasSetTracker.cpp

76

On a second review, I think this is correct without the change I suggested below.

When deciding to merge 2 sets, we do check aliasing of the pointer, so we know it belongs to both sets. The issue that may come up, as you suggest, is that the merged set may no longer be MustAlias, because we don't check the first "FoundSet" at the callsite.
But when we do the actual adding, in addPointer, there is an alias check there against "any pointer" in that set, and a "downgrade" to MayAlias if that is not satisfied.

Now, after D56613, even that check will go away. But it's being replaced with the intersection of alias information of *all* sets that were merged, including that first "FoundSet". So, if MustAlias is not found for *all* merged sets, then the set is downgraded to MayAlias.

I believe that is correct. Did I miss something?

[chandlerc]

(peanut gallery comments)

lib/Analysis/AliasSetTracker.cpp

194–196

+1, happy to see that factored out.

[asbirlea]

Rebase on top of NFC commit.

[asbirlea]

Rebase.

[asbirlea]

lib/Analysis/AliasSetTracker.cpp

76

Ping.

[reames]

Response to outstanding discussion point inline, but I want to suggest an alternate approach for the review so that we can make progress.

The entire concern here is because we can try to merge two alias sets which *don't* contain the exact pointerrec triggering the merging. Let's just stop doing that. If we simple called addPointer and addUnknown on each AliasSet we found which aliased *before* merging, all of our concerns disappear. This is what the two callers of this function - aside from merge all - actually want anyways, so let's just do that. It should be a simple refactor, followed by a rebase of this patch, at which point this patch becomes obviously correct. In fact, you can the entirely remove the problematic if block from mergeSetIn, rather than try to optimize it's performance.

lib/Analysis/AliasSetTracker.cpp

76

Reading back through the (original) code, I believe the problem was valid. Here are two example codepaths:
addUknown->findAliasSetForUnknownInst-<mergeIn
getAliasSetFor->mergeAliasSetsForPointer->mergeIn

The core problem is that the first AS is never downgraded to MayAlias if the pointer added to it aliases, but does not may alias. We never call mergeSetIn to that first set.

Note that in both cases, the instruction being queried for *has not* been added to any alias set before merging. Also note that the alias result passed in is with respect to *one* of the two sets, not both.

[reames]

lib/Analysis/AliasSetTracker.cpp

76

Refining this slightly, look specifically at the codepath in getAliasSetFor where we have an existing AS, but with the wrong Size and/or AA info. We update the info on the set, and then call mergeAliasSetForPointer, but we never actually downgrade the AS which corresponds to the entry to MayAlias.

Or to say it differently, the result of merging two alias sets is wrong when both are MustAlias w/the pointer, and this is a codepath which exposes that bug to it's caller in turn.

[asbirlea]

Update.

[asbirlea]

I'm sorry, I don't really understand your alternative approach.
If we're adding the pointer to *all* sets aliased *before* merging, we will have that pointer duplicated to the number of aliasing sets. We never remove pointers. And these are not real sets, they're lists. They're intentionally implemented this way to make merging fast. We can't remove duplicates without walking the whole list.
Could you clarify?

I've updated the patch to essentially avoid the problem on the code path which updates the size. This should match existing behavior.

lib/Analysis/AliasSetTracker.cpp

76

Let me try to explain this back to see if we're on the same page.

When we call addUnknown, we always call addUnknownInst which sets the set to MayAlias always, so no issue here.

When we call getAliasSetFor, then call mergeAliasSetsForPointer, then follow a code path that also calls addPointer afterwards, all is good.

There is one call path where we don't call addPointer afterwards. That's when we update the size and/or AA, then attempt to merge sets. What can happen in this scenario:

1. We update the pointer and the set is still MustAlias. We proceed to try to merge, find nothing, set remains MustAlias, all good.
2. We update the pointer and the set is still MustAlias. We proceed to try to merge, find another set. Now since the first set is still MustAlias, if we find a MustAlias on the second set, passing that info to mergeSetIn should be valid.
3. We update the pointer and the set is no longer MustAlias. There is no need to merge with any other set, but we should check any 2 pointers in the set to see if the set is still MustAlias. This never happens, set remains MustAlias.
4. We update the pointer and the set is no longer MustAlias. We proceed to merge, find another set. Current mergeSetIn will do an alias() check, find MayAlias and downgrade the set. Passing AR to mergeSet, if MustAlias is found with the second set will not downgrade the set. This is the problem that you say this patch exposes.

Is this right?

Assuming yes, is 3. valid behavior?

[reames]

lib/Analysis/AliasSetTracker.cpp

76

The concern I have is about the codepath you describe as "When we call getAliasSetFor, then call mergeAliasSetsForPointer, then follow a code path that also calls addPointer afterwards, all is good."

I'm not at all sure that codepath is correct since it allows us to construct an incorrect intermediate result before calling addPointer.

However, when trying to further write up an explanation for the case which concerns me, I think I've come to an interesting conclusion. I think the piece of code you're trying to improve here is simply redundant and can be removed.

For the must alias check in the original code to trigger, we must have constructed two alias sets (AS1, AS2) which are both individually mustalias and also at least mayalias w/respect to some memory location "ML". In order for the result of merging these three values to mustalias, then "ML" must be mustalias w/both AS1 and AS2. Given AS1 and AS2 are (by assumption of construction) noalias w/each other, that would seem to be a contradiction.

I'm testing a patch at a moment w/an assertion of to test the previous theory. I've run across what appears to be an unrelated bug though, so I need to fix that before confirming my theory.

[asbirlea]

lib/Analysis/AliasSetTracker.cpp

76

SG, thank you for following up!

I'll remove this cleanup patch as dependency to unblock the others in the mean time.

[reames]

Assumed inactive, cleaning out review list, please readd if needed.

[mkazantsev]

Same as above.

include/llvm/Analysis/AliasSetTracker.h

public:
   bool isMustAlias() const { return Alias == SetMustAlias; }
   bool isMayAlias()  const { return Alias == SetMayAlias; }
 
   /// Return true if this alias set should be ignored as part of the
   /// AliasSetTracker object.
   bool isForwardingAliasSet() const { return Forward; }
 
   /// Merge the specified alias set into this alias set.
-  void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
+  void mergeSetIn(AliasSet &AS, AliasSetTracker &AST, AliasResult AR,
+                  bool EntryUpdated = false);
 
   // Alias Set iteration - Allow access to all of the pointers which are part of
   // this alias set.
   class iterator;
   iterator begin() const { return iterator(PtrList); }
   iterator end()   const { return iterator(); }
   bool empty() const { return PtrList == nullptr; }
 
AliasSet::PointerRec &getEntryFor(Value *V) {
     AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
     if (!Entry)
       Entry = new AliasSet::PointerRec(V);
     return *Entry;
   }
 
   AliasSet &addPointer(MemoryLocation Loc, AliasSet::AccessLattice E);
   AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
-                                     const AAMDNodes &AAInfo);
+                                     const AAMDNodes &AAInfo,
+                                     bool EntryUpdated = false);
 
   /// Merge all alias sets into a single set that is considered to alias any
   /// pointer.
   AliasSet &mergeAllAliasSets();
 
   AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
 };
 
 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
   AST.print(OS);
   return OS;
 }
 
 } // end namespace llvm
 
 #endif // LLVM_ANALYSIS_ALIASSETTRACKER_H

lib/Analysis/AliasSetTracker.cpp

 static cl::opt<unsigned>
     SaturationThreshold("alias-set-saturation-threshold", cl::Hidden,
                         cl::init(250),
                         cl::desc("The maximum number of pointers may-alias "
                                  "sets may contain before degradation"));
 
 /// mergeSetIn - Merge the specified alias set into this alias set.
 ///
-void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
+void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST, AliasResult AR,
+                          bool EntryUpdated) {
   assert(!AS.Forward && "Alias set is already forwarding!");
   assert(!Forward && "This set is a forwarding set!!");
 
   bool WasMustAlias = (Alias == SetMustAlias);
   // Update the alias and access types of this set...
   Access |= AS.Access;
   Alias  |= AS.Alias;
 
   if (Alias == SetMustAlias) {
+    if (EntryUpdated) {
       // Check that these two merged sets really are must aliases.  Since both
       // used to be must-alias sets, we can just check any pointer from each set
       // for aliasing.
       AliasAnalysis &AA = AST.getAliasAnalysis();
       PointerRec *L = getSomePointer();
       PointerRec *R = AS.getSomePointer();
 
       // If the pointers are not a must-alias pair, this set becomes a may alias.
       if (AA.alias(MemoryLocation(L->getValue(), L->getSize(), L->getAAInfo()),
                    MemoryLocation(R->getValue(), R->getSize(), R->getAAInfo())) !=
           MustAlias)
         Alias = SetMayAlias;
+    } else if (AR != MustAlias)
+      Alias = SetMayAlias;
   }
 
   if (Alias == SetMayAlias) {
     if (WasMustAlias)
       AST.TotalMayAliasSetSize += size();
     if (AS.Alias == SetMustAlias)
       AST.TotalMayAliasSetSize += AS.size();
   }
 
void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
   Alias = SetMayAlias;
   Access = ModRefAccess;
 }
 
 /// aliasesPointer - If the specified pointer "may" (or must) alias one of the
 /// members in the set return the appropriate AliasResult. Otherwise return
 /// NoAlias.
 ///
 AliasResult AliasSet::aliasesPointer(const Value *Ptr, LocationSize Size,
                                      const AAMDNodes &AAInfo,
                                      AliasAnalysis &AA) const {
   if (AliasAny)
     return MayAlias;
 
   if (Alias == SetMustAlias) {
     assert(UnknownInsts.empty() && "Illegal must alias set!");
 
     // If this is a set of MustAliases, only check to see if the pointer aliases
     // SOME value in the set.

 }
 
 
 /// mergeAliasSetsForPointer - Given a pointer, merge all alias sets that may
 /// alias the pointer. Return the unified set, or nullptr if no set that aliases
 /// the pointer was found.
 AliasSet *AliasSetTracker::mergeAliasSetsForPointer(const Value *Ptr,
                                                     LocationSize Size,
-                                                    const AAMDNodes &AAInfo) {
+                                                    const AAMDNodes &AAInfo,
+                                                    bool EntryUpdated) {
   AliasSet *FoundSet = nullptr;
   for (iterator I = begin(), E = end(); I != E;) {
     iterator Cur = I++;
-    if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue;
+    if (Cur->Forward)
+      continue;
+
+    AliasResult AR = Cur->aliasesPointer(Ptr, Size, AAInfo, AA);
+    if (AR == NoAlias)
+      continue;
 
     if (!FoundSet) {
       // If this is the first alias set ptr can go into, remember it.
       FoundSet = &*Cur;
     } else {
       // Otherwise, we must merge the sets.
-      FoundSet->mergeSetIn(*Cur, *this);
+      FoundSet->mergeSetIn(*Cur, *this, AR, EntryUpdated);
     }
   }
 
   return FoundSet;
 }
 
 AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
   AliasSet *FoundSet = nullptr;
   for (iterator I = begin(), E = end(); I != E;) {
     iterator Cur = I++;
     if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
       continue;
     if (!FoundSet) {
       // If this is the first alias set ptr can go into, remember it.
       FoundSet = &*Cur;
     } else {
       // Otherwise, we must merge the sets.
-      FoundSet->mergeSetIn(*Cur, *this);
+      FoundSet->mergeSetIn(*Cur, *this, MayAlias);
     }
   }
   return FoundSet;
 }
 
 AliasSet &AliasSetTracker::getAliasSetFor(const MemoryLocation &MemLoc) {
 
   Value * const Pointer = const_cast<Value*>(MemLoc.Ptr);
AliasSet &AliasSetTracker::getAliasSetFor(const MemoryLocation &MemLoc) {
   // Check to see if the pointer is already known.
   if (Entry.hasAliasSet()) {
     // If the size 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);
+      mergeAliasSetsForPointer(Pointer, Size, AAInfo, true);
     // Return the set!
     return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
   }
 
   if (AliasSet *AS = mergeAliasSetsForPointer(Pointer, Size, AAInfo)) {
     // Add it to the alias set it aliases.
     AS->addPointer(*this, Entry, Size, AAInfo);
     return *AS;
for (auto Cur : ASVector) {
     if (FwdTo) {
       Cur->Forward = AliasAnyAS;
       AliasAnyAS->addRef();
       FwdTo->dropRef(*this);
       continue;
     }
 
     // Otherwise, perform the actual merge.
-    AliasAnyAS->mergeSetIn(*Cur, *this);
+    AliasAnyAS->mergeSetIn(*Cur, *this, MayAlias);
   }
 
   return *AliasAnyAS;
 }
 
 AliasSet &AliasSetTracker::addPointer(MemoryLocation Loc,
                                       AliasSet::AccessLattice E) {
   AliasSet &AS = getAliasSetFor(Loc);