[AliasSetTracker] Correctly handle changing the size of an entry

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.

This fixes PR27262.

Differential Revision: http://reviews.llvm.org/D18939

llvm-svn: 266381

3 files changed, 64 insertions, 20 deletions

diff --git a/llvm/include/llvm/Analysis/AliasSetTracker.h b/llvm/include/llvm/Analysis/AliasSetTracker.h
index 1a71dc5..760a764 100644
--- a/llvm/include/llvm/Analysis/AliasSetTracker.h
+++ b/llvm/include/llvm/Analysis/AliasSetTracker.h
@@ -59,8 +59,12 @@ class AliasSet : public ilist_node<AliasSet> {
       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.
@@ -68,6 +72,8 @@ class AliasSet : public ilist_node<AliasSet> {
       else if (AAInfo != NewAAInfo)
         // NewAAInfo conflicts with AAInfo.
         AAInfo = DenseMapInfo<AAMDNodes>::getTombstoneKey();
+
+      return SizeChanged;
     }
 
     uint64_t getSize() const { return Size; }
@@ -365,7 +371,7 @@ public:
   /// 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,
@@ -425,8 +431,8 @@ private:
     AS.Access |= E;
     return AS;
   }
-  AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size,
-                                   const AAMDNodes &AAInfo);
+  AliasSet *mergeAliasSetsForPointer(const Value *Ptr, uint64_t Size,
+                                     const AAMDNodes &AAInfo);
 
   AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
 };
diff --git a/llvm/lib/Analysis/AliasSetTracker.cpp b/llvm/lib/Analysis/AliasSetTracker.cpp
index 3cafb46..4cf7641 100644
--- a/llvm/lib/Analysis/AliasSetTracker.cpp
+++ b/llvm/lib/Analysis/AliasSetTracker.cpp
@@ -208,13 +208,12 @@ void AliasSetTracker::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,
-                                                  uint64_t Size,
-                                                  const AAMDNodes &AAInfo) {
+/// 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++;
@@ -274,12 +273,18 @@ AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size,
 
   // 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;
@@ -457,7 +462,7 @@ void AliasSetTracker::remove(AliasSet &AS) {
 
 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;
@@ -470,7 +475,7 @@ bool AliasSetTracker::remove(LoadInst *LI) {
   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;
@@ -483,7 +488,7 @@ bool AliasSetTracker::remove(StoreInst *SI) {
   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;
@@ -493,8 +498,8 @@ bool AliasSetTracker::remove(VAArgInst *VAAI) {
   AAMDNodes AAInfo;
   VAAI->getAAMetadata(AAInfo);
 
-  AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0),
-                                        MemoryLocation::UnknownSize, AAInfo);
+  AliasSet *AS = mergeAliasSetsForPointer(VAAI->getOperand(0),
+                                          MemoryLocation::UnknownSize, AAInfo);
   if (!AS) return false;
   remove(*AS);
   return true;
@@ -510,7 +515,7 @@ bool AliasSetTracker::remove(MemSetInst *MSI) {
   else
     Len = MemoryLocation::UnknownSize;
 
-  AliasSet *AS = findAliasSetForPointer(MSI->getRawDest(), Len, AAInfo);
+  AliasSet *AS = mergeAliasSetsForPointer(MSI->getRawDest(), Len, AAInfo);
   if (!AS)
     return false;
   remove(*AS);
diff --git a/llvm/test/Transforms/LICM/pr27262.ll b/llvm/test/Transforms/LICM/pr27262.ll
new file mode 100644
index 0000000..5fc6d93
--- /dev/null
+++ b/llvm/test/Transforms/LICM/pr27262.ll
@@ -0,0 +1,33 @@
+; 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)