AliasSetTracker "fixme" fix - using mod/ref information for UnknownInstr

[andrew.zhogin]

Summary

AliasSetTracker now doesn't convert access mode to ModRefAccess if new visited UnknownInst has only 'REF' modrefinfo to existing pointers is sets.

And ref-aliased by call pointers can be hoisted out of loop.

// FIXME: This should use mod/ref information to make this not suck so bad
Alias = SetMayAlias;

• Access = ModRefAccess;

+ Access = (MR & MRI_Mod) ? ModRefAccess : RefAccess;

[hfinkel]

lib/Analysis/AliasSetTracker.cpp

117

If MR == MRI_ModRef, then this will always add only ModAccess. Is this right when Access == RefAccess? (can that happen?)

193

Why is this called "OnMR"? Do you mean OrMR?

213

Lambdas are nice, but not if you need to repeat them ;) -- Please make utility functions for these (static helpers are fine).

[andrew.zhogin]

Updated patch with review comments considered

[andrew.zhogin]

lib/Analysis/AliasSetTracker.cpp

193

Renamed to processMR() anonymous local helper

[hfinkel]

LGTM.

lib/Analysis/AliasSetTracker.cpp

116

This is not your fault, but seems silly. ModRefInfo in AliasAnalysis.h and AccessLattice in AliasSetTracker.h are the *same* enum (modulo the names). We should just fix that (make AccessLattice == ModRefInfo), and eliminate the need for this switch statement.

If you don't want to do that first, please add a FIXME.

[andrew.zhogin]

AccessLattice is now typedef-alias of ModRefInfo

[andrew.zhogin]

As I don't have write access could you please commit this patch for me?

[hfinkel]

r251451. I apologize for the delay.

include/llvm/Analysis/AliasSetTracker.h

 
 class AliasAnalysis;
 class LoadInst;
 class StoreInst;
 class VAArgInst;
 class AliasSetTracker;
 class AliasSet;
 
+enum ModRefInfo;
+
 class AliasSet : public ilist_node<AliasSet> {
   friend class AliasSetTracker;
 
   class PointerRec {
     Value *Val;  // The pointer this record corresponds to.
     PointerRec **PrevInList, *NextInList;
     AliasSet *AS;
     uint64_t Size;
if (Dest != Forward) {
       Forward = Dest;
     }
     return Dest;
   }
 
   void removeFromTracker(AliasSetTracker &AST);
 
   void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size,
-                  const AAMDNodes &AAInfo,
+                  const AAMDNodes &AAInfo, ModRefInfo MR,
                   bool KnownMustAlias = false);
-  void addUnknownInst(Instruction *I, AliasAnalysis &AA);
+  void addUnknownInst(Instruction *I, AliasAnalysis &AA, ModRefInfo MR);
   void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
     bool WasEmpty = UnknownInsts.empty();
     for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
       if (UnknownInsts[i] == I) {
         UnknownInsts[i] = UnknownInsts.back();
         UnknownInsts.pop_back();
         --i; --e;  // Revisit the moved entry.
       }
     if (!WasEmpty && UnknownInsts.empty())
       dropRef(AST);
   }
   void setVolatile() { Volatile = true; }
 
 public:
   /// aliasesPointer - Return true if the specified pointer "may" (or must)
   /// alias one of the members in the set.
-  ///
+  /// MRcommon - if Ptr is aliased by existing UnknownInsts,
+  /// then not-null MRcommon will be set to the worst ModRefInfo met
+  /// 
   bool aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo,
-                      AliasAnalysis &AA) const;
-  bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
+                      AliasAnalysis &AA, ModRefInfo* MRcommon = nullptr) const;
+  /// aliasesUnknownInst - Return true if the specified UnknownInst
+  /// has not-null ModRefInfo (not MRI_NoModRef) with some
+  /// pointer or UnknownInst already existing in AliasSet
+  /// MRcommon - not-null MRcommon will be set to the worst ModRefInfo met
+  /// 
+  bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA,
+                          ModRefInfo* MRcommon = nullptr) const;
 };
 
 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
   AS.print(OS);
   return OS;
 }
 
 
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,
-                                   const AAMDNodes &AAInfo);
+                                   const AAMDNodes &AAInfo,
+                                   ModRefInfo* MRcommonPtr = nullptr);
 
-  AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
+  AliasSet *findAliasSetForUnknownInst(Instruction *Inst,
+                                   ModRefInfo* MRcommonPtr = nullptr);
 };
 
 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
   AST.print(OS);
   return OS;
 }
 
 } // End llvm namespace
 
 #endif

lib/Analysis/AliasSetTracker.cpp

 
 void AliasSet::removeFromTracker(AliasSetTracker &AST) {
   assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!");
   AST.removeAliasSet(this);
 }
 
 void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry,
                           uint64_t Size, const AAMDNodes &AAInfo,
-                          bool KnownMustAlias) {
+                          ModRefInfo MR, bool KnownMustAlias) {
   assert(!Entry.hasAliasSet() && "Entry already in set!");
 
   // Check to see if we have to downgrade to _may_ alias.
   if (isMustAlias() && !KnownMustAlias)
     if (PointerRec *P = getSomePointer()) {
       AliasAnalysis &AA = AST.getAliasAnalysis();
       AliasResult Result =
           AA.alias(MemoryLocation(P->getValue(), P->getSize(), P->getAAInfo()),
                    MemoryLocation(Entry.getValue(), Size, AAInfo));
       if (Result != MustAlias)
         Alias = SetMayAlias;
       else                  // First entry of must alias must have maximum size!
         P->updateSizeAndAAInfo(Size, AAInfo);
       assert(Result != NoAlias && "Cannot be part of must set!");
     }
 
+  // upgrading access if existing UnknownInst has ModRef with new pointer
+  switch (MR) {
+  case MRI_NoModRef: break;
+  case MRI_Ref: Access |= RefAccess; break;
+  case MRI_Mod: Access |= ModAccess; break;
+  case MRI_ModRef: Access |= ModRefAccess; break;
+  }
+
   Entry.setAliasSet(this);
   Entry.updateSizeAndAAInfo(Size, AAInfo);
 
   // Add it to the end of the list...
   assert(*PtrListEnd == nullptr && "End of list is not null?");
   *PtrListEnd = &Entry;
   PtrListEnd = Entry.setPrevInList(PtrListEnd);
   assert(*PtrListEnd == nullptr && "End of list is not null?");
   addRef();               // Entry points to alias set.
 }
 
-void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) {
+void AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA,
+                              ModRefInfo MR) {
   if (UnknownInsts.empty())
     addRef();
   UnknownInsts.emplace_back(I);
 
   if (!I->mayWriteToMemory()) {
     Alias = SetMayAlias;
     Access |= RefAccess;
     return;
   }
 
-  // FIXME: This should use mod/ref information to make this not suck so bad
   Alias = SetMayAlias;
-  Access = ModRefAccess;
+  Access = (MR & MRI_Mod) ? ModRefAccess : RefAccess;
+}
+
+namespace {
+  /// returns true if there is no request of worst ModRefInfo
+  ///   (MRcommonPtr is null)
+  /// or when achieved maximum ModRefInfo (MRI_ModRef).
+  bool processMR(ModRefInfo MR, ModRefInfo* MRcommonPtr, ModRefInfo& MRcommon) {
+    MRcommon = ModRefInfo(MRcommon | MR);
+    return !MRcommonPtr || (MRcommon == MRI_ModRef);
+  }
+  bool fillExitMR(ModRefInfo* MRcommonPtr, ModRefInfo& MRcommon) {
+    if (MRcommonPtr) *MRcommonPtr = MRcommon;
+    return MRcommon != MRI_NoModRef;
+  }
 }
 
 /// aliasesPointer - Return true if the specified pointer "may" (or must)
 /// alias one of the members in the set.
 ///
 bool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size,
                               const AAMDNodes &AAInfo,
-                              AliasAnalysis &AA) const {
+                              AliasAnalysis &AA,
+                              ModRefInfo* MRcommonPtr) const {
   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.
     PointerRec *SomePtr = getSomePointer();
     assert(SomePtr && "Empty must-alias set??");
     return AA.alias(MemoryLocation(SomePtr->getValue(), SomePtr->getSize(),
                                    SomePtr->getAAInfo()),
                     MemoryLocation(Ptr, Size, AAInfo));
   }
 
   // If this is a may-alias set, we have to check all of the pointers in the set
   // to be sure it doesn't alias the set...
   for (iterator I = begin(), E = end(); I != E; ++I)
     if (AA.alias(MemoryLocation(Ptr, Size, AAInfo),
                  MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo())))
       return true;
 
+  // to gather worst ModRefInfo
+  ModRefInfo MRcommon = MRI_NoModRef;
+
   // Check the unknown instructions...
   if (!UnknownInsts.empty()) {
     for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i)
-      if (AA.getModRefInfo(UnknownInsts[i],
-                           MemoryLocation(Ptr, Size, AAInfo)) != MRI_NoModRef)
-        return true;
+      if (processMR(AA.getModRefInfo(UnknownInsts[i],
+          MemoryLocation(Ptr, Size, AAInfo)), MRcommonPtr, MRcommon))
+        return fillExitMR(MRcommonPtr, MRcommon);
   }
 
-  return false;
+  return fillExitMR(MRcommonPtr, MRcommon);
 }
 
 bool AliasSet::aliasesUnknownInst(const Instruction *Inst,
-                                  AliasAnalysis &AA) const {
+                                  AliasAnalysis &AA,
+                                  ModRefInfo* MRcommonPtr) const {
   if (!Inst->mayReadOrWriteMemory())
     return false;
 
+  // to gather worst ModRefInfo
+  ModRefInfo MRcommon = MRI_NoModRef;
+
   for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) {
     ImmutableCallSite C1(getUnknownInst(i)), C2(Inst);
-    if (!C1 || !C2 || AA.getModRefInfo(C1, C2) != MRI_NoModRef ||
-        AA.getModRefInfo(C2, C1) != MRI_NoModRef)
-      return true;
+    if (!C1 || !C2 ||
+      processMR(AA.getModRefInfo(C1, C2), MRcommonPtr, MRcommon) ||
+      processMR(AA.getModRefInfo(C2, C1), MRcommonPtr, MRcommon))
+      return fillExitMR(MRcommonPtr, MRcommon);
   }
 
-  for (iterator I = begin(), E = end(); I != E; ++I)
-    if (AA.getModRefInfo(Inst, MemoryLocation(I.getPointer(), I.getSize(),
-                                              I.getAAInfo())) != MRI_NoModRef)
-      return true;
-
-  return false;
+  for (iterator I = begin(), E = end(); I != E; ++I) {
+    ModRefInfo MR = AA.getModRefInfo(
+      Inst, MemoryLocation(I.getPointer(), I.getSize(), I.getAAInfo()));
+    if (processMR(MR, MRcommonPtr, MRcommon))
+      return fillExitMR(MRcommonPtr, MRcommon);
+  }
+  return fillExitMR(MRcommonPtr, MRcommon);
 }
 
 void AliasSetTracker::clear() {
   // Delete all the PointerRec entries.
   for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end();
        I != E; ++I)
     I->second->eraseFromList();
   
   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,
                                                   uint64_t Size,
-                                                  const AAMDNodes &AAInfo) {
+                                                  const AAMDNodes &AAInfo,
+                                                  ModRefInfo* MRcommonPtr) {
   AliasSet *FoundSet = nullptr;
   for (iterator I = begin(), E = end(); I != E;) {
     iterator Cur = I++;
-    if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA)) continue;
+    ModRefInfo MR = MRI_NoModRef;
+    if (Cur->Forward || !Cur->aliasesPointer(Ptr, Size, AAInfo, AA, &MR))
+      continue;
+    *MRcommonPtr = ModRefInfo(*MRcommonPtr | MR);
     
     if (!FoundSet) {      // If this is the first alias set ptr can go into.
       FoundSet = Cur;     // Remember it.
     } else {              // Otherwise, we must merge the sets.
       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
     }
   }
 

 
 bool AliasSetTracker::containsUnknown(const Instruction *Inst) const {
   for (const_iterator I = begin(), E = end(); I != E; ++I)
     if (!I->Forward && I->aliasesUnknownInst(Inst, AA))
       return true;
   return false;
 }
 
-AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) {
+AliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst,
+                                                      ModRefInfo* MRcommonPtr) {
   AliasSet *FoundSet = nullptr;
   for (iterator I = begin(), E = end(); I != E;) {
     iterator Cur = I++;
-    if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA))
+    ModRefInfo MR = MRI_NoModRef;
+    if (Cur->Forward || !Cur->aliasesUnknownInst(Inst, AA, &MR))
       continue;
+    *MRcommonPtr = ModRefInfo(*MRcommonPtr | MR);
     if (!FoundSet)            // If this is the first alias set ptr can go into.
       FoundSet = Cur;         // Remember it.
     else if (!Cur->Forward)   // Otherwise, we must merge the sets.
       FoundSet->mergeSetIn(*Cur, *this);     // Merge in contents.
   }
   return FoundSet;
 }
 
AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size,
 
   // Check to see if the pointer is already known.
   if (Entry.hasAliasSet()) {
     Entry.updateSizeAndAAInfo(Size, AAInfo);
     // Return the set!
     return *Entry.getAliasSet(*this)->getForwardedTarget(*this);
   }
   
-  if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, AAInfo)) {
+  ModRefInfo MR = MRI_NoModRef;
+  if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, AAInfo, &MR)) {
     // Add it to the alias set it aliases.
-    AS->addPointer(*this, Entry, Size, AAInfo);
+    AS->addPointer(*this, Entry, Size, AAInfo, MR);
     return *AS;
   }
   
   if (New) *New = true;
   // Otherwise create a new alias set to hold the loaded pointer.
   AliasSets.push_back(new AliasSet());
-  AliasSets.back().addPointer(*this, Entry, Size, AAInfo);
+  AliasSets.back().addPointer(*this, Entry, Size, AAInfo, MRI_NoModRef);
   return AliasSets.back();
 }
 
 bool AliasSetTracker::add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo) {
   bool NewPtr;
   addPointer(Ptr, Size, AAInfo, AliasSet::NoAccess, NewPtr);
   return NewPtr;
 }

 
 
 bool AliasSetTracker::addUnknown(Instruction *Inst) {
   if (isa<DbgInfoIntrinsic>(Inst)) 
     return true; // Ignore DbgInfo Intrinsics.
   if (!Inst->mayReadOrWriteMemory())
     return true; // doesn't alias anything
 
-  AliasSet *AS = findAliasSetForUnknownInst(Inst);
+  ModRefInfo MR = MRI_NoModRef;
+  AliasSet *AS = findAliasSetForUnknownInst(Inst, &MR);
   if (AS) {
-    AS->addUnknownInst(Inst, AA);
+    AS->addUnknownInst(Inst, AA, MR);
     return false;
   }
   AliasSets.push_back(new AliasSet());
   AS = &AliasSets.back();
-  AS->addUnknownInst(Inst, AA);
+  AS->addUnknownInst(Inst, AA, MR);
   return true;
 }
 
 bool AliasSetTracker::add(Instruction *I) {
   // Dispatch to one of the other add methods.
   if (LoadInst *LI = dyn_cast<LoadInst>(I))
     return add(LI);
   if (StoreInst *SI = dyn_cast<StoreInst>(I))
void AliasSetTracker::copyValue(Value *From, Value *To) {
 
   AliasSet::PointerRec &Entry = getEntryFor(To);
   if (Entry.hasAliasSet()) return;    // Already in the tracker!
 
   // Add it to the alias set it aliases...
   I = PointerMap.find_as(From);
   AliasSet *AS = I->second->getAliasSet(*this);
   AS->addPointer(*this, Entry, I->second->getSize(),
-                 I->second->getAAInfo(),
+                 I->second->getAAInfo(), MRI_NoModRef,
                  true);
 }
 
 
 
 //===----------------------------------------------------------------------===//
 //               AliasSet/AliasSetTracker Printing Support
 //===----------------------------------------------------------------------===//

test/Transforms/LICM/licm_call_referenced_ptr.ll

+; RUN: opt < %s -basicaa -licm -S | FileCheck %s
+
+declare void @llvm.memcpy.p0i8.p0i8.i64(i8* nocapture, i8* nocapture, i64, i32, i1) nounwind
+
+define i8 @"main"() {
+entry:
+  %A = alloca [64 x i8]
+  %B = alloca [4 x i8]
+  %A0 = getelementptr [64 x i8], [64 x i8]* %A, i32 0, i32 0
+  %B0 = getelementptr [4 x i8], [4 x i8]* %B, i32 0, i32 0
+  %B1 = getelementptr [4 x i8], [4 x i8]* %B, i32 0, i32 1
+  %B2 = getelementptr [4 x i8], [4 x i8]* %B, i32 0, i32 2
+  %B3 = getelementptr [4 x i8], [4 x i8]* %B, i32 0, i32 3
+  store i8 0, i8* %A0
+  store i8 32, i8* %B0
+  store i8 73, i8* %B1
+  store i8 74, i8* %B2
+  store i8 75, i8* %B3
+  br label %loop_begin
+
+loop_begin:
+; CHECK: loop_begin:
+; CHECK-NEXT: call void @llvm.memcpy.p0i8.p0i8.i64(i8* %A0, i8* %B0, i64 4, i32 4, i1 false)
+
+  %b_val = load i8, i8* %B0
+ 
+  ; *B is invariant in loop and limit_val must be hoisted
+  %limit_val_1 = mul i8 %b_val, 3
+  %limit_val = add i8 %limit_val_1, 67
+  
+  call void @llvm.memcpy.p0i8.p0i8.i64(i8* %A0, i8* %B0, i64 4, i32 4, i1 false)
+  
+  %exitcond = icmp ugt i8 164, %limit_val
+  br i1 %exitcond, label %after_loop, label %loop_begin
+
+after_loop:
+  %b_val_result = load i8, i8* %B0
+  ret i8 %b_val_result
+}
+