[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

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

What is the right alias set for undef?

[mkuper]

lib/Analysis/AliasSetTracker.cpp

278

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

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

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

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

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

282

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

Good, please go ahead.

282

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.

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.

lib/Analysis/AliasSetTracker.cpp

 /// 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.
+    // Use findAliasSetForPointer for its merging side effect.
+    // Note that we can *not* return the result of findAliasSetForPointer
+    // due to a quirk of alias analysis behavior. Since alias(undef, undef)
+    // is NoAlias, findAliasSetForPointer(undef, ...) will not find the
+    // the right set for undef, even if it exists.
+    if (Entry.updateSizeAndAAInfo(Size, AAInfo))
+      findAliasSetForPointer(Pointer, Size, AAInfo);
     // Return the set!
     return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
   }
   
   if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, AAInfo)) {
     // Add it to the alias set it aliases.
     AS->addPointer(*this, Entry, Size, AAInfo);
     return *AS;

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)