[AST] Remove notion of volatile from alias sets

[reames]

Summary

Volatility is not an aliasing property. We used to model volatile as if it had extremely conservative aliasing implications, but that hasn't been true for several years now. So, it doesn't make sense to be in AliasSet.

It also turns out the code is entirely a noop. Outside of the AST code to update it, there was only one user: load store promotion in LICM. L/S promotion doesn't need the check since it walks all the users of the address anyway. It already checks each load or store via !isUnordered which causes us to bail for volatile accesses. (Look at the lines immediately following the two remove asserts.)

There is the possibility of some small compile time impact here, but the only case which will get noticeably slower is a loop with a large number of loads and stores to the same address where only the last one we inspect is volatile. This is sufficiently rare it's not worth optimizing for..

[hiraditya]

There was discussion sometime back, might be worth looking at: https://groups.google.com/forum/#!topic/llvm-dev/uLvitfqEd_g

[reames]

In D50786#1200886, @hiraditya wrote:

There was discussion sometime back, might be worth looking at: https://groups.google.com/forum/#!topic/llvm-dev/uLvitfqEd_g

I'm missing why this is relevant? It happens to involve a volatile access as an AliasSet, but seems otherwise unrelated. From what I can tell, the "volatile implies mod" thing hasn't been true for years.

[mkazantsev]

test/Transforms/LICM/hoisting.ll

153

Please add CHECK-LABEL: Out after the load, otherwise we cannot be sure that we didn't sink.

test/Transforms/LICM/scalar-promote.ll

80

Two concerns here:

1. If you want to make sure that we don't sink, please add CHECK-LABEL: Out after the check on store.
2. In this particular case, it would be correct to either hoist or sink, just because we *never* go to the 2nd iteration and this code is in fact linear. The optimizer could've recognized this pattern and sunk or hoisted the instruction, and it would not be a bug. Do you mind making a similar test but with a different loop exit condition in which that would be incorrect?

[reames]

Rebase.

Max, I landed the changes for the test separately. I applied your check-label request, but not one about single iteration loops since the test file is filed with such. Anyone who wants to specialize single iteration loops has some work to do later anyways, so I didn't see any value.

[mkazantsev]

LGTM

[reames]

Committed as:
Author: reames
Date: Tue Aug 21 10:59:11 2018
New Revision: 340312

include/llvm/Analysis/AliasSetTracker.h

class AliasSet : public ilist_node<AliasSet> {
   /// of the set. We represent these independently of the values of alias
   /// results in order to pack it into a single bit. Lattice goes from
   /// MustAlias to MayAlias.
   enum AliasLattice {
     SetMustAlias = 0, SetMayAlias = 1
   };
   unsigned Alias : 1;
 
-  /// True if this alias set contains volatile loads or stores.
-  unsigned Volatile : 1;
-
   unsigned SetSize = 0;
 
   void addRef() { ++RefCount; }
 
   void dropRef(AliasSetTracker &AST) {
     assert(RefCount >= 1 && "Invalid reference count detected!");
     if (--RefCount == 0)
       removeFromTracker(AST);
public:
   AliasSet &operator=(const AliasSet &) = delete;
 
   /// Accessors...
   bool isRef() const { return Access & RefAccess; }
   bool isMod() const { return Access & ModAccess; }
   bool isMustAlias() const { return Alias == SetMustAlias; }
   bool isMayAlias()  const { return Alias == SetMayAlias; }
 
-  /// Return true if this alias set contains volatile loads or stores.
-  bool isVolatile() const { return Volatile; }
-
   /// 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);
 
   // Alias Set iteration - Allow access to all of the pointers which are part of
iterator operator++(int) { // Postincrement
       iterator tmp = *this; ++*this; return tmp;
     }
   };
 
 private:
   // Can only be created by AliasSetTracker.
   AliasSet()
       : PtrListEnd(&PtrList), RefCount(0),  AliasAny(false), Access(NoAccess),
-        Alias(SetMustAlias), Volatile(false) {}
+        Alias(SetMustAlias) {}
 
   PointerRec *getSomePointer() const {
     return PtrList;
   }
 
   /// Return the real alias set this represents. If this has been merged with
   /// another set and is forwarding, return the ultimate destination set. This
   /// also implements the union-find collapsing as well.
for (size_t i = 0, e = UnknownInsts.size(); i != e; ++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:
   /// Return true if the specified pointer "may" (or must) alias one of the
   /// members in the set.
   bool aliasesPointer(const Value *Ptr, LocationSize Size,
                       const AAMDNodes &AAInfo, AliasAnalysis &AA) const;
   bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
 };
 

lib/Analysis/AliasSetTracker.cpp

 void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) {
   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;
-  Volatile |= AS.Volatile;
 
   if (Alias == SetMustAlias) {
     // 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();
void AliasSetTracker::add(Value *Ptr, LocationSize Size,
                           const AAMDNodes &AAInfo) {
   addPointer(Ptr, Size, AAInfo, AliasSet::NoAccess);
 }
 
 void AliasSetTracker::add(LoadInst *LI) {
   if (isStrongerThanMonotonic(LI->getOrdering())) return addUnknown(LI);
 
   AliasSet &AS = addPointer(MemoryLocation::get(LI), AliasSet::RefAccess);
-  if (LI->isVolatile()) AS.setVolatile();
 }
 
 void AliasSetTracker::add(StoreInst *SI) {
   if (isStrongerThanMonotonic(SI->getOrdering())) return addUnknown(SI);
 
   AliasSet &AS = addPointer(MemoryLocation::get(SI), AliasSet::ModAccess);
-  if (SI->isVolatile()) AS.setVolatile();
 }
 
 void AliasSetTracker::add(VAArgInst *VAAI) {
   addPointer(MemoryLocation::get(VAAI), AliasSet::ModRefAccess);
 }
 
 void AliasSetTracker::add(AnyMemSetInst *MSI) {
   auto MemLoc = MemoryLocation::getForDest(MSI);
   AliasSet &AS = addPointer(MemLoc, AliasSet::ModAccess);
   auto *MS = dyn_cast<MemSetInst>(MSI);
-  if (MS && MS->isVolatile())
-    AS.setVolatile();
 }
 
 void AliasSetTracker::add(AnyMemTransferInst *MTI) {
   auto SrcLoc = MemoryLocation::getForSource(MTI);
   AliasSet &ASSrc = addPointer(SrcLoc, AliasSet::RefAccess);
 
   auto DestLoc = MemoryLocation::getForDest(MTI);
   AliasSet &ASDst = addPointer(DestLoc, AliasSet::ModAccess);
 
   auto* MT = dyn_cast<MemTransferInst>(MTI);
-  if (MT && MT->isVolatile()) {
-    ASSrc.setVolatile();
-    ASDst.setVolatile();
-  }
 }
 
 void AliasSetTracker::addUnknown(Instruction *Inst) {
   if (isa<DbgInfoIntrinsic>(Inst))
     return; // Ignore DbgInfo Intrinsics.
 
   if (auto *II = dyn_cast<IntrinsicInst>(Inst)) {
     // These intrinsics will show up as affecting memory, but they are just
for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i)
       if (auto *Inst = AS.getUnknownInst(i))
         add(Inst);
 
     // Loop over all of the pointers in this alias set.
     for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
       AliasSet &NewAS =
           addPointer(ASI.getPointer(), ASI.getSize(), ASI.getAAInfo(),
                      (AliasSet::AccessLattice)AS.Access);
-      if (AS.isVolatile()) NewAS.setVolatile();
     }
   }
 }
 
 // deleteValue method - This method is used to remove a pointer value from the
 // AliasSetTracker entirely.  It should be used when an instruction is deleted
 // from the program to update the AST.  If you don't use this, you would have
 // dangling pointers to deleted instructions.
void AliasSet::print(raw_ostream &OS) const {
   OS << (Alias == SetMustAlias ? "must" : "may") << " alias, ";
   switch (Access) {
   case NoAccess:     OS << "No access "; break;
   case RefAccess:    OS << "Ref       "; break;
   case ModAccess:    OS << "Mod       "; break;
   case ModRefAccess: OS << "Mod/Ref   "; break;
   default: llvm_unreachable("Bad value for Access!");
   }
-  if (isVolatile()) OS << "[volatile] ";
   if (Forward)
     OS << " forwarding to " << (void*)Forward;
 
   if (!empty()) {
     OS << "Pointers: ";
     for (iterator I = begin(), E = end(); I != E; ++I) {
       if (I != begin()) OS << ", ";
       I.getPointer()->printAsOperand(OS << "(");

lib/Transforms/Scalar/LICM.cpp

if (!HasCatchSwitch) {
       bool Promoted = false;
 
       // Loop over all of the alias sets in the tracker object.
       for (AliasSet &AS : *CurAST) {
         // We can promote this alias set if it has a store, if it is a "Must"
         // alias set, if the pointer is loop invariant, and if we are not
         // eliminating any volatile loads or stores.
         if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
-            AS.isVolatile() || !L->isLoopInvariant(AS.begin()->getValue()))
+            !L->isLoopInvariant(AS.begin()->getValue()))
           continue;
 
         assert(
             !AS.empty() &&
             "Must alias set should have at least one pointer element in it!");
 
         SmallSetVector<Value *, 8> PointerMustAliases;
         for (const auto &ASI : AS)
for (User *U : ASIV->users()) {
       // Ignore instructions that are outside the loop.
       Instruction *UI = dyn_cast<Instruction>(U);
       if (!UI || !CurLoop->contains(UI))
         continue;
 
       // If there is an non-load/store instruction in the loop, we can't promote
       // it.
       if (LoadInst *Load = dyn_cast<LoadInst>(UI)) {
-        assert(!Load->isVolatile() && "AST broken");
         if (!Load->isUnordered())
           return false;
 
         SawUnorderedAtomic |= Load->isAtomic();
         SawNotAtomic |= !Load->isAtomic();
 
         if (!DereferenceableInPH)
           DereferenceableInPH = isSafeToExecuteUnconditionally(
               *Load, DT, CurLoop, SafetyInfo, ORE, Preheader->getTerminator());
       } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
         // Stores *of* the pointer are not interesting, only stores *to* the
         // pointer.
         if (UI->getOperand(1) != ASIV)
           continue;
-        assert(!Store->isVolatile() && "AST broken");
         if (!Store->isUnordered())
           return false;
 
         SawUnorderedAtomic |= Store->isAtomic();
         SawNotAtomic |= !Store->isAtomic();
 
         // If the store is guaranteed to execute, both properties are satisfied.
         // We may want to check if a store is guaranteed to execute even if we

test/Analysis/AliasSet/memtransfer.ll

entry:
   store atomic i8 1, i8* %b unordered, align 1
   ret void
 }
 
 ; CHECK: Alias sets for function 'test2':
 ; CHECK: Alias Set Tracker: 3 alias sets for 4 pointer values.
 ; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, 1)
 ; CHECK-NOT:    1 Unknown instructions
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref   [volatile] Pointers: (i8* %s, 1), (i8* %d, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref    Pointers: (i8* %s, 1), (i8* %d, 1)
 ; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, 1)
 define void @test2(i8* %s, i8* %d) {
 entry:
   %a = alloca i8, align 1
   %b = alloca i8, align 1
   store i8 1, i8* %a, align 1
   call void @llvm.memcpy.p0i8.p0i8.i64(i8* %d, i8* %s, i64 1, i1 true)
   store i8 1, i8* %b, align 1
entry:
   store atomic i8 1, i8* %b unordered, align 1
   ret void
 }
 
 ; CHECK: Alias sets for function 'test4':
 ; CHECK: Alias Set Tracker: 3 alias sets for 4 pointer values.
 ; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %a, 1)
 ; CHECK-NOT:    1 Unknown instructions
-; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref   [volatile] Pointers: (i8* %s, 1), (i8* %d, 1)
+; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 2] may alias, Mod/Ref    Pointers: (i8* %s, 1), (i8* %d, 1)
 ; CHECK:   AliasSet[0x{{[0-9a-f]+}}, 1] must alias, Mod       Pointers: (i8* %b, 1)
 define void @test4(i8* %s, i8* %d) {
 entry:
   %a = alloca i8, align 1
   %b = alloca i8, align 1
   store i8 1, i8* %a, align 1
   call void @llvm.memmove.p0i8.p0i8.i64(i8* %d, i8* %s, i64 1, i1 true)
   store i8 1, i8* %b, align 1

test/Transforms/LICM/hoisting.ll

 latch:
   %6 = add nsw i32 %2, 1
   br label %header
 
 return:
   ret i32 %sum
 }
 
+; Can neither sink nor hoist
+define i32 @test_volatile(i1 %c) {
+; CHECK-LABEL: @test_volatile(
+; CHECK-LABEL: Loop:
+; CHECK: load volatile i32, i32* @X
+  br label %Loop
+
+Loop:
+  %A = load volatile i32, i32* @X
+  br i1 %c, label %Loop, label %Out
+
+Out:
+  ret i32 %A
+}
+
+
 declare {}* @llvm.invariant.start.p0i8(i64, i8* nocapture) nounwind readonly
 declare void @llvm.invariant.end.p0i8({}*, i64, i8* nocapture) nounwind
 declare void @escaping.invariant.start({}*) nounwind
 ; invariant.start dominates the load, and in this scope, the
 ; load is invariant. So, we can hoist the `addrld` load out of the loop.
 define i32 @test_fence(i8* %addr, i32 %n, i8* %volatile) {
 ; CHECK-LABEL: @test_fence
 ; CHECK-LABEL: entry

test/Transforms/LICM/scalar-promote.ll

 
 ; CHECK: Loop:
 ; CHECK-NEXT: load volatile
 
 Out:    ; preds = %Loop
   ret void
 }
 
+define void @test3b(i32 %i) {
+; CHECK-LABEL: @test3b(
+; CHECK: Loop:
+; CHECK: store volatile
+  br label %Loop
+Loop:
+        ; Should not promote this to a register
+  %x = load i32, i32* @X
+  %x2 = add i32 %x, 1
+  store volatile i32 %x2, i32* @X
+  br i1 true, label %Out, label %Loop
+
+Out:    ; preds = %Loop
+  ret void
+}
+
 ; PR8041
 define void @test4(i8* %x, i8 %n) {
 ; CHECK-LABEL: @test4(
   %handle1 = alloca i8*
   %handle2 = alloca i8*
   store i8* %x, i8** %handle1
   br label %loop