[AliasSetTracker] Correctly handle changing size of an entry

[mkuper]

Summary

If the size of an AST entry changes, we also need to make sure we perform necessary alias set merges, as the new size may overlap pointers in other sets.
We happen to run into this with memset, because memset allows an entry for a i8* pointer to have a decidedly non-i8 size.

There's some ugliness here because even if getEntryFor(Pointer).hasAliasSet() is true, findAliasSetForPointer(Pointer, ...) will not necessarily find an alias set - as a pointer may not alias anything, including itself (e.g. undef). I'm not sure whether that is a bug or a feature...

This fixes PR27262.

[hfinkel]

lib/Analysis/AliasSetTracker.cpp

278 ↗

(On Diff #53163)

Saying "Use findAliasSetForPointer for its merging side effect." implies that findAliasSetForPointer does other things too. If it did, it would be reasonable to split the behavior. However, merging together all alias sets aliasing the provided pointer is exactly what findAliasSetForPointer does. I think this is worth saying. Instead of:

// Use findAliasSetForPointer for its merging side effect.

how about:

// Merging together all alias sets which alias a particular pointer is exactly what findAliasSetForPointer does.

282 ↗

(On Diff #53163)

What is the right alias set for undef?

[mkuper]

lib/Analysis/AliasSetTracker.cpp

278 ↗

(On Diff #53163)

I agree it doesn't make sense to split the behavior out, since it's basically all it does - hence the comment, otherwise I would have just split it out. :-)
The problem is that findAliasSetForPointer is not really a good name for what it does. But I don't have any better ideas, "mergeAliasSetsForPointer" that returns the resulting alias set doesn't look much better.

Anyway, this is bike-shedding, if you prefer just changing the comment, I'm ok with that.
Let me know what you think.

282 ↗

(On Diff #53163)

An alias set that contains only undef - it can never be merged with anything else, since undef aliases nothing.

I guess this makes sense - getAliasSetForPointer() needs to return *something*, and returning a set that contains only undef means we'll get an alias set that aliases nothing else, as expected. I guess this isn't as precise as we'd idally like, because it means we merge "different" undefs, which should not alias each-other.

BTW, this isn't necessarily a problem only for undef. The issue is that alias(X,X) apparently doesn't have to hold, in general.

[hfinkel]

lib/Analysis/AliasSetTracker.cpp

278 ↗

(On Diff #53163)

Indeed :-) -- I also could not think of a better name. Thus I suggested just changing the comment.

FWIW, I do like "mergeAliasSetsForPointer" better than "findAliasSetForPointer".

282 ↗

(On Diff #53163)

An alias set that contains only undef - it can never be merged with anything else, since undef aliases nothing.

I guess this makes sense - getAliasSetForPointer() needs to return *something*, and returning a set that contains only undef means we'll get an alias set that aliases nothing else, as expected. I guess this isn't as precise as we'd idally like, because it means we merge "different" undefs, which should not alias each-other.

Wouldn't it make the most sense for each undef to get its own set? I don't see why we should merge them since different undefs don't mutually alias.

BTW, this isn't necessarily a problem only for undef. The issue is that alias(X,X) apparently doesn't have to hold, in general.

Really? That seems wrong.

[mkuper]

lib/Analysis/AliasSetTracker.cpp

278 ↗

(On Diff #53163)

Then I'd prefer to change the name, and be done with this. :-)

282 ↗

(On Diff #53163)

Wouldn't it make the most sense for each undef to get its own set? I don't see why we should merge them since different undefs don't mutually alias.

AFAIK, we can't actually distinguish between "different" undefs, since there is only one UndefValue of each type. So I don't think there's a way to do that.

Really? That seems wrong.

Yes, it seemed wrong to me too. I talked to Mehdi on IRC about it, and he convinced me that it's reasonable.

In any case, this definitely happens for undefs right now (at least since r236511), and I don't see any guarantee that this can't happen for other values. Another case where basic-aa will return NoAlias is if the size is 0.
Also, if I understand correctly, basic-aa is supposed to give MayAlias (instead of MustAlias) for alias(X,X) if X is loop-iteration dependent, but this doesn't seem enforced, and I'm pretty sure we may get a NoAlias in these cases as well.

[hfinkel]

lib/Analysis/AliasSetTracker.cpp

278 ↗

(On Diff #53163)

Good, please go ahead.

282 ↗

(On Diff #53163)

AFAIK, we can't actually distinguish between "different" undefs, since there is only one UndefValue of each type. So I don't think there's a way to do that.

That's correct. But that does not mean that you can't get back a different alias set whenever you put in an undef pointer.

Another case where basic-aa will return NoAlias is if the size is 0.

That seems okay.

Also, if I understand correctly, basic-aa is supposed to give MayAlias (instead of MustAlias) for alias(X,X) if X is loop-iteration dependent, but this doesn't seem enforced, and I'm pretty sure we may get a NoAlias in these cases as well.

That does not sound right either; I don't see why being loop dependent matters. For the aliasing query to be well defined, it must refer to values within the same loop iteration.

In any case, this LGTM. Please, however, file a bug report on this alias(X, X) uncertainty. We should get some documented resolution on this matter.

[mkuper]

Thanks, Hal, will do.

llvm/trunk/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;
     }
 
-    void updateSizeAndAAInfo(uint64_t NewSize, const AAMDNodes &NewAAInfo) {
-      if (NewSize > Size) Size = NewSize;
+    bool updateSizeAndAAInfo(uint64_t NewSize, const AAMDNodes &NewAAInfo) {
+      bool SizeChanged = false;
+      if (NewSize > Size) {
+        Size = NewSize;
+        SizeChanged = true;
+      }
 
       if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey())
         // We don't have a AAInfo yet. Set it to NewAAInfo.
         AAInfo = NewAAInfo;
       else if (AAInfo != NewAAInfo)
         // NewAAInfo conflicts with AAInfo.
         AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
+
+      return SizeChanged;
     }
 
     uint64_t getSize() const { return Size; }
 
     /// Return the AAInfo, or null if there is no information or conflicting
     /// information.
     AAMDNodes getAAInfo() const {
       // If we have missing or conflicting AAInfo, return null.
public:
   AliasSet &getAliasSetForPointer(Value *P, uint64_t Size,
                                   const AAMDNodes &AAInfo,
                                   bool *New = nullptr);
 
   /// Return the alias set containing the location specified if one exists,
   /// otherwise return null.
   AliasSet *getAliasSetForPointerIfExists(const Value *P, uint64_t Size,
                                           const AAMDNodes &AAInfo) {
-    return findAliasSetForPointer(P, Size, AAInfo);
+    return mergeAliasSetsForPointer(P, Size, AAInfo);
   }
 
   /// Return true if the specified location is represented by this alias set,
   /// false otherwise. This does not modify the AST object or alias sets.
   bool containsPointer(const Value *P, uint64_t Size,
                        const AAMDNodes &AAInfo) const;
 
   /// Return true if the specified instruction "may" (or must) alias one of the
private:
   AliasSet &addPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo,
                        AliasSet::AccessLattice E,
                        bool &NewSet) {
     NewSet = false;
     AliasSet &AS = getAliasSetForPointer(P, Size, AAInfo, &NewSet);
     AS.Access |= E;
     return AS;
   }
-  AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size,
+  AliasSet *mergeAliasSetsForPointer(const Value *Ptr, uint64_t Size,
                                      const AAMDNodes &AAInfo);
 
   AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
 };
 
 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
   AST.print(OS);
   return OS;
 }
 
 } // End llvm namespace
 
 #endif

llvm/trunk/lib/Analysis/AliasSetTracker.cpp

void AliasSetTracker::clear() {
   
   PointerMap.clear();
   
   // The alias sets should all be clear now.
   AliasSets.clear();
 }
 
 
-/// findAliasSetForPointer - Given a pointer, find the one alias set to put the
-/// instruction referring to the pointer into.  If there are multiple alias sets
-/// that may alias the pointer, merge them together and return the unified set.
-///
-AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr,
+/// 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,
                                                     uint64_t Size,
                                                     const AAMDNodes &AAInfo) {
   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 (!FoundSet) {      // If this is the first alias set ptr can go into.
       FoundSet = &*Cur;   // Remember it.
     } else {              // Otherwise, we must merge the sets.

 /// lives in.
 AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size,
                                                  const AAMDNodes &AAInfo,
                                                  bool *New) {
   AliasSet::PointerRec &Entry = getEntryFor(Pointer);
 
   // Check to see if the pointer is already known.
   if (Entry.hasAliasSet()) {
-    Entry.updateSizeAndAAInfo(Size, AAInfo);
+    // 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);
     // Return the set!
     return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
   }
   
-  if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, AAInfo)) {
+  if (AliasSet *AS = mergeAliasSetsForPointer(Pointer, Size, AAInfo)) {
     // Add it to the alias set it aliases.
     AS->addPointer(*this, Entry, Size, AAInfo);
     return *AS;
   }
   
   if (New) *New = true;
   // Otherwise create a new alias set to hold the loaded pointer.
   AliasSets.push_back(new AliasSet());
void AliasSetTracker::remove(AliasSet &AS) {
   // Stop using the alias set, removing it.
   AS.RefCount -= NumRefs;
   if (AS.RefCount == 0)
     AS.removeFromTracker(*this);
 }
 
 bool
 AliasSetTracker::remove(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo) {
-  AliasSet *AS = findAliasSetForPointer(Ptr, Size, AAInfo);
+  AliasSet *AS = mergeAliasSetsForPointer(Ptr, Size, AAInfo);
   if (!AS) return false;
   remove(*AS);
   return true;
 }
 
 bool AliasSetTracker::remove(LoadInst *LI) {
   const DataLayout &DL = LI->getModule()->getDataLayout();
   uint64_t Size = DL.getTypeStoreSize(LI->getType());
 
   AAMDNodes AAInfo;
   LI->getAAMetadata(AAInfo);
 
-  AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size, AAInfo);
+  AliasSet *AS = mergeAliasSetsForPointer(LI->getOperand(0), Size, AAInfo);
   if (!AS) return false;
   remove(*AS);
   return true;
 }
 
 bool AliasSetTracker::remove(StoreInst *SI) {
   const DataLayout &DL = SI->getModule()->getDataLayout();
   uint64_t Size = DL.getTypeStoreSize(SI->getOperand(0)->getType());
 
   AAMDNodes AAInfo;
   SI->getAAMetadata(AAInfo);
 
-  AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size, AAInfo);
+  AliasSet *AS = mergeAliasSetsForPointer(SI->getOperand(1), Size, AAInfo);
   if (!AS) return false;
   remove(*AS);
   return true;
 }
 
 bool AliasSetTracker::remove(VAArgInst *VAAI) {
   AAMDNodes AAInfo;
   VAAI->getAAMetadata(AAInfo);
 
-  AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0),
+  AliasSet *AS = mergeAliasSetsForPointer(VAAI->getOperand(0),
                                           MemoryLocation::UnknownSize, AAInfo);
   if (!AS) return false;
   remove(*AS);
   return true;
 }
 
 bool AliasSetTracker::remove(MemSetInst *MSI) {
   AAMDNodes AAInfo;
   MSI->getAAMetadata(AAInfo);
   uint64_t Len;
 
   if (ConstantInt *C = dyn_cast<ConstantInt>(MSI->getLength()))
     Len = C->getZExtValue();
   else
     Len = MemoryLocation::UnknownSize;
 
-  AliasSet *AS = findAliasSetForPointer(MSI->getRawDest(), Len, AAInfo);
+  AliasSet *AS = mergeAliasSetsForPointer(MSI->getRawDest(), Len, AAInfo);
   if (!AS)
     return false;
   remove(*AS);
   return true;
 }
 
 bool AliasSetTracker::removeUnknown(Instruction *I) {
   if (!I->mayReadOrWriteMemory())

llvm/trunk/test/Transforms/LICM/pr27262.ll

+; RUN: opt -S -basicaa -licm < %s | FileCheck %s
+
+target datalayout = "e-m:x-p:32:32-i64:64-f80:32-n8:16:32-a:0:32-S32"
+target triple = "i686-pc-windows-msvc18.0.0"
+
+; Make sure the store to v is not sunk past the memset
+; CHECK-LABEL: @main
+; CHECK: for.body:
+; CHECK-NEXT: store i8 1, i8* %p
+; CHECK-NEXT: store i8 2, i8* %p1
+; CHECK-NEXT: call void @llvm.memset
+; CHECK: end:
+; CHECK-NEXT: ret i32 0
+
+define i32 @main(i1 %k, i8* %p) {
+entry:
+  %p1 = getelementptr i8, i8* %p, i32 1
+  br label %for.body
+ 
+for.body:
+  store i8 1, i8* %p, align 1
+  store i8 2, i8* %p1, align 1
+  call void @llvm.memset.p0i8.i32(i8* %p, i8 255, i32 4, i32 1, i1 false)  
+  br label %for.latch
+  
+for.latch:
+  br i1 %k, label %for.body, label %end
+
+end:
+  ret i32 0
+}
+
+declare void @llvm.memset.p0i8.i32(i8* nocapture, i8, i32, i32, i1)