Refine memory dependence's notion of volatile semantics

[reames]

Summary

(For reviewers who get duplicates, sorry! Forgot to add llvm-commits to the first review and had to close it and open another.)

According to my reading of the LangRef, volatiles are only ordered with respect to other volatiles. It is entirely legal and profitable to forward unrelated loads over the volatile load. This patch implements this for GVN by refining the transition rules MemoryDependenceAnalysis uses when encountering a volatile.

The added test cases show where the extra flexibility is profitable for local dependence optimizations. I have a related patch (http://reviews.llvm.org/D6895) which will extend this to non-local dependence (i.e. PRE), but that's essentially orthogonal to the semantic change in this patch. I have tested the two together and can confirm that PRE works over a volatile load with both changes.

One question for reviewers: should a load being volatile change the default handling for a *may* alias load? For a non-volatile load, we'll keep scanning past looking for an actual mustalias dependency. Is this the behaviour we want for volatiles? While I think this matches the letter of the LangRef, I'm not entirely sure it matches the expectations of mapping C volatile to LLVM volatile. In particular, should the following code always return 0? With my current patch, we can and will forward the first load to third without changing the second.
int example(int* p, int *q) { // q == p at runtime

int x = *p;
*(volatile int*)q
int y = *p;
return x-y;

}

[reames]

ping

[reames]

ping x2

[hfinkel]

LGTM.

One question for reviewers: should a load being volatile change the default handling for a *may* alias load?

No, it should not.

FWIW, LLVM's volatile is even more strict than C's volatile. LLVM's volatile is meaningful on loads, and is specified as:

The optimizers must not change the number of volatile operations or change their order of execution relative to other volatile operations. The optimizers may change the order of volatile operations relative to non-volatile operations.

Whereas C's volatile says (5.1.2.3):

An actual implementation need not evaluate part of an expression if it can deduce that its value is not used and that no needed side effects are produced (including any caused by calling a function or accessing a volatile object).

Which is made even more explicit under the specification of assignment semantics 6.5.16:

An assignment operator stores a value in the object designated by the left operand. An assignment expression has the value of the left operand after the assignment (The implementation is permitted to read the object to determine the value but is not required to, even when the object has volatile-qualified type.)

and, thus, is not really meaningful on loads.

lib/Analysis/MemoryDependenceAnalysis.cpp

     // If a load of this width would include all of MemLoc, then we succeed.
     if (LIOffs+NewLoadByteSize >= MemLocEnd)
       return NewLoadByteSize;
 
     NewLoadByteSize <<= 1;
   }
 }
 
+static bool isVolatile(Instruction *Inst) {
+  if (LoadInst *LI = dyn_cast<LoadInst>(Inst))
+    return LI->isVolatile();
+  else if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
+    return SI->isVolatile();
+  return false;
+}
+
+
 /// getPointerDependencyFrom - Return the instruction on which a memory
 /// location depends.  If isLoad is true, this routine ignores may-aliases with
 /// read-only operations.  If isLoad is false, this routine ignores may-aliases
 /// with reads from read-only locations.  If possible, pass the query
 /// instruction as well; this function may take advantage of the metadata
 /// annotated to the query instruction to refine the result.
 MemDepResult MemoryDependenceAnalysis::
 getPointerDependencyFrom(const AliasAnalysis::Location &MemLoc, bool isLoad,

     }
 
     // Values depend on loads if the pointers are must aliased.  This means that
     // a load depends on another must aliased load from the same value.
     // One exception is atomic loads: a value can depend on an atomic load that it
     // does not alias with when this atomic load indicates that another thread may
     // be accessing the location.
     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
+
+      // While volatile access cannot be eliminated, they do not have to clobber
+      // non-aliasing locations, as normal accesses can for example be reordered
+      // with volatile accesses.
+      if (LI->isVolatile()) {
+        if (!QueryInst)
+          // Original QueryInst *may* be volatile
+          return MemDepResult::getClobber(LI);
+        if (isVolatile(QueryInst))
+          // Ordering required if QueryInst is itself volatile
+          return MemDepResult::getClobber(LI);
+        // Otherwise, volatile doesn't imply any special ordering
+      }
+      
       // Atomic loads have complications involved.
       // A Monotonic (or higher) load is OK if the query inst is itself not atomic.
       // An Acquire (or higher) load sets the HasSeenAcquire flag, so that any
       //   release store will know to return getClobber.
       // FIXME: This is overly conservative.
-      if (!LI->isUnordered()) {
+      if (LI->isAtomic() && LI->getOrdering() > Unordered) {
         if (!QueryInst)
           return MemDepResult::getClobber(LI);
         if (auto *QueryLI = dyn_cast<LoadInst>(QueryInst)) {
           if (!QueryLI->isSimple())
             return MemDepResult::getClobber(LI);
         } else if (auto *QuerySI = dyn_cast<StoreInst>(QueryInst)) {
           if (!QuerySI->isSimple())
             return MemDepResult::getClobber(LI);
         } else if (QueryInst->mayReadOrWriteMemory()) {
           return MemDepResult::getClobber(LI);
         }
 
         if (isAtLeastAcquire(LI->getOrdering()))
           HasSeenAcquire = true;
       }
 
-      // FIXME: this is overly conservative.
-      // While volatile access cannot be eliminated, they do not have to clobber
-      // non-aliasing locations, as normal accesses can for example be reordered
-      // with volatile accesses.
-      if (LI->isVolatile())
-        return MemDepResult::getClobber(LI);
-
       AliasAnalysis::Location LoadLoc = AA->getLocation(LI);
 
       // If we found a pointer, check if it could be the same as our pointer.
       AliasAnalysis::AliasResult R = AA->alias(LoadLoc, MemLoc);
 
       if (isLoad) {
         if (R == AliasAnalysis::NoAlias) {
           // If this is an over-aligned integer load (for example,

   assert(Loc.Ptr->getType()->isPointerTy() &&
          "Can't get pointer deps of a non-pointer!");
   Result.clear();
   
   // This routine does not expect to deal with volatile instructions.
   // Doing so would require piping through the QueryInst all the way through.
   // TODO: volatiles can't be elided, but they can be reordered with other
   // non-volatile accesses.
-  auto isVolatile = [](Instruction *Inst) {
-    if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
-      return LI->isVolatile();
-    } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
-      return SI->isVolatile();
-    }
-    return false;
-  };
+
   // We currently give up on any instruction which is ordered, but we do handle
   // atomic instructions which are unordered.
   // TODO: Handle ordered instructions
   auto isOrdered = [](Instruction *Inst) {
     if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
       return !LI->isUnordered();
     } else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       return !SI->isUnordered();

test/Transforms/GVN/volatile.ll

+; Tests that check our handling of volatile instructions encountered
+; when scanning for dependencies
+; RUN: opt -basicaa -gvn -S < %s | FileCheck %s
+
+; Check that we can bypass a volatile load when searching
+; for dependencies of a non-volatile load
+define i32 @test1(i32* nocapture %p, i32* nocapture %q) {
+; CHECK-LABEL: test1
+; CHECK:      %0 = load volatile i32* %q
+; CHECK-NEXT: ret i32 0
+entry:
+  %x = load i32* %p
+  load volatile i32* %q
+  %y = load i32* %p
+  %add = sub i32 %y, %x
+  ret i32 %add
+}
+
+; We can not value forward if the query instruction is 
+; volatile, this would be (in effect) removing the volatile load
+define i32 @test2(i32* nocapture %p, i32* nocapture %q) {
+; CHECK-LABEL: test2
+; CHECK:      %x = load i32* %p
+; CHECK-NEXT: %y = load volatile i32* %p
+; CHECK-NEXT: %add = sub i32 %y, %x
+entry:
+  %x = load i32* %p
+  %y = load volatile i32* %p
+  %add = sub i32 %y, %x
+  ret i32 %add
+}
+
+; If the query instruction is itself volatile, we *cannot*
+; reorder it even if p and q are noalias
+define i32 @test3(i32* noalias nocapture %p, i32* noalias nocapture %q) {
+; CHECK-LABEL: test3
+; CHECK:      %x = load i32* %p
+; CHECK-NEXT: %0 = load volatile i32* %q
+; CHECK-NEXT: %y = load volatile i32* %p
+entry:
+  %x = load i32* %p
+  load volatile i32* %q
+  %y = load volatile i32* %p
+  %add = sub i32 %y, %x
+  ret i32 %add
+}
+
+; If an encountered instruction is both volatile and ordered, 
+; we need to use the strictest ordering of either.  In this 
+; case, the ordering prevents forwarding.
+define i32 @test4(i32* noalias nocapture %p, i32* noalias nocapture %q) {
+; CHECK-LABEL: test4
+; CHECK:      %x = load i32* %p
+; CHECK-NEXT: %0 = load atomic volatile i32* %q seq_cst 
+; CHECK-NEXT: %y = load atomic i32* %p seq_cst
+entry:
+  %x = load i32* %p
+  load atomic volatile i32* %q seq_cst, align 4
+  %y = load atomic i32* %p seq_cst, align 4
+  %add = sub i32 %y, %x
+  ret i32 %add
+}
+
+; Value forwarding from a volatile load is perfectly legal
+define i32 @test5(i32* nocapture %p, i32* nocapture %q) {
+; CHECK-LABEL: test5
+; CHECK:      %x = load volatile i32* %p
+; CHECK-NEXT: ret i32 0
+entry:
+  %x = load volatile i32* %p
+  %y = load i32* %p
+  %add = sub i32 %y, %x
+  ret i32 %add
+}
+