More detailed memory dependence checking between volatile and non-volatile accesses

[kparzysz]

Summary

Don't automatically assume depedency if only one of the memory accesses in question is volatile. Defer the final determination of dependency to the alias analysis.
The (very simple) motivating example is added as a lit test.

[• dberlin]

This looks correct to me, but nick and philip understand the ordering guarantees a lot better than I do :)

[kparzysz]

Philip, Nick---could you please review this?

[kparzysz]

Ping.

[reames]

Minor code comments inline. Once addressed should be good to go after quick round of review.

The following is mostly to record my though process... no response needed and no action required.

The key issue here is one of semantics. We've been a bit unclear in the past as to whether volatile applied to *memory locations* or *memory accesses*. At first, it looks like your change is dependent on the location model, but it's not. You're simply allowing the non-ordered accessed to fall down into the generic may-alias handling below. This works with both models, but is optional for volatile-locations and required for volatile-access.

If we were going to move towards the volatile-locations model, that's something we'd need to discuss widely on llvm-dev. I'm mildly in favour of a volatile-access model, but don't know the C++ spec well enough to know what's actually required here. I'm also of the opinion that if we're going to treat a volatile as applying to *locations* we should consider teaching AA about this fact.

lib/Analysis/MemoryDependenceAnalysis.cpp

648 ↗

(On Diff #46793)

This isn't quite right. You can't be less precise when lacking information about the querying instruction.

This needs to be:
if (SI->isVolatile()) {

if (!QueryInst)
  return a clobber;
if (!isSimple(QueryInst))
 return a clobber;

}

649 ↗

(On Diff #46793)

Given we've got this same pattern in several places, please pull out a helper function along the lines of "bool isSimple(Instruction* I)". Could be a lambda, or a static function.

test/Transforms/GVN/volatile-nonvolatile.ll

3 ↗

(On Diff #46793)

Stylistic suggestion: put the check lines immediate next to the function, add a CHECK-LABEL: @foo.

16 ↗

(On Diff #46793)

Please add a couple of negative tests as well.

[kparzysz]

Addressed Philip's comments.

[reames]

LGTM w/comment addressed.

lib/Analysis/MemoryDependenceAnalysis.cpp

654 ↗

(On Diff #48725)

Huh, there's actually another bug here I hadn't noticed. We should be checking to see if the query instruction is another (potentially volatile) memory access. Simple reusing the isOtherMemoryAccess helper function would fix this.

(To be clear, this is not a new bug, but since we'll be exercising the code more, we should fix it here. Please add a test case as well.)

[kparzysz]

Added the call to isOtherMemAccess.

I couldn't create a testcase. It seems like all cases of non-trivial memory accessing instructions (i.e. other than loads and stores) are handled in other parts of the code.

[kparzysz]

To clarify last comment: I tried creating a testcase using GVN and DSE, and in both cases, either the non-load-or-store instruction was handled by the optimization itself, or the "getDependence" function did not follow the desired path within the memory dependence analysis.

[nicholas]

Krzysztof Parzyszek wrote:

kparzysz added a comment.

Philip, Nick---could you please review this?

It looks correct to me, but please wait for Philip.

I wish there were a testcase which demonstrated that two non-aliasing
volatile accesses were dependent, but I don't see any way to write that
test (maybe you can add more debug print statements to MemDep).

Nick

[thakis]

Hi,

in Chromium we have this snippet to force a heap overflow (to test asan instrumentation):

62	void AsanHeapOverflow() {
63	  scoped_ptr<int[]> array(new int[kArraySize]);
64	  // Declares the dummy value as volatile to make sure it doesn't get optimized
65	  // away.
66	  int volatile dummy = 0;
67	  dummy = array[kArraySize];
68	  base::debug::Alias(const_cast<int*>(&dummy));
69	}

This now no longer does an invalid write. I'm guessing this is an expected consequence of this change – what's the new way to express this?

[kparzysz]

I'm not sure that I understand this code---where is the invalid write? There is an out-of-bounds load, but I can't see any questionable stores.

[thakis]

Sorry, I meant "invalid read", not "invalid write".

[kparzysz]

GVN removes the load and replaces the uses of it with "undef". I guess the only certain way to keep the load is to make the array volatile:

void AsanHeapOverflow() {
  scoped_ptr<volatile int[]> array(new int[kArraySize]);
  int dummy = array[kArraySize];
}

I'm not sure what the last line does so my example does not include it.

llvm/trunk/lib/Analysis/MemoryDependenceAnalysis.cpp

MemDepResult MemoryDependenceAnalysis::getSimplePointerDependencyFrom(
   const DataLayout &DL = BB->getModule()->getDataLayout();
 
   // Create a numbered basic block to lazily compute and cache instruction
   // positions inside a BB. This is used to provide fast queries for relative
   // position between two instructions in a BB and can be used by
   // AliasAnalysis::callCapturesBefore.
   OrderedBasicBlock OBB(BB);
 
+  // Return "true" if and only if the instruction I is either a non-simple
+  // load or a non-simple store.
+  auto isNonSimpleLoadOrStore = [] (Instruction *I) -> bool {
+    if (auto *LI = dyn_cast<LoadInst>(I))
+      return !LI->isSimple();
+    if (auto *SI = dyn_cast<StoreInst>(I))
+      return !SI->isSimple();
+    return false;
+  };
+
+  // Return "true" if I is not a load and not a store, but it does access
+  // memory.
+  auto isOtherMemAccess = [] (Instruction *I) -> bool {
+    return !isa<LoadInst>(I) && !isa<StoreInst>(I) && I->mayReadOrWriteMemory();
+  };
+
   // Walk backwards through the basic block, looking for dependencies.
   while (ScanIt != BB->begin()) {
     Instruction *Inst = &*--ScanIt;
 
     if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
       // Debug intrinsics don't (and can't) cause dependencies.
       if (isa<DbgInfoIntrinsic>(II)) continue;
 
if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
         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.
       // FIXME: This is overly conservative.
       if (LI->isAtomic() && LI->getOrdering() > Unordered) {
-        if (!QueryInst)
+        if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
+            isOtherMemAccess(QueryInst))
           return MemDepResult::getClobber(LI);
         if (LI->getOrdering() != Monotonic)
           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);
-        }
       }
 
       MemoryLocation LoadLoc = MemoryLocation::get(LI);
 
       // If we found a pointer, check if it could be the same as our pointer.
       AliasResult R = AA->alias(LoadLoc, MemLoc);
 
       if (isLoad) {
#endif
       // Stores depend on may/must aliased loads.
       return MemDepResult::getDef(Inst);
     }
 
     if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
       // Atomic stores have complications involved.
       // A Monotonic store is OK if the query inst is itself not atomic.
       // FIXME: This is overly conservative.
-      if (!SI->isUnordered()) {
-        if (!QueryInst)
+      if (!SI->isUnordered() && SI->isAtomic()) {
+        if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
+            isOtherMemAccess(QueryInst))
           return MemDepResult::getClobber(SI);
         if (SI->getOrdering() != Monotonic)
           return MemDepResult::getClobber(SI);
-        if (auto *QueryLI = dyn_cast<LoadInst>(QueryInst)) {
-          if (!QueryLI->isSimple())
-            return MemDepResult::getClobber(SI);
-        } else if (auto *QuerySI = dyn_cast<StoreInst>(QueryInst)) {
-          if (!QuerySI->isSimple())
-            return MemDepResult::getClobber(SI);
-        } else if (QueryInst->mayReadOrWriteMemory()) {
-          return MemDepResult::getClobber(SI);
-        }
       }
 
       // 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 (SI->isVolatile())
+        if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
+            isOtherMemAccess(QueryInst))
           return MemDepResult::getClobber(SI);
 
       // If alias analysis can tell that this store is guaranteed to not modify
       // the query pointer, ignore it.  Use getModRefInfo to handle cases where
       // the query pointer points to constant memory etc.
       if (AA->getModRefInfo(SI, MemLoc) == MRI_NoModRef)
         continue;
 
       // Ok, this store might clobber the query pointer.  Check to see if it is
getNonLocalPointerDependency(Instruction *QueryInst,
   const MemoryLocation Loc = MemoryLocation::get(QueryInst);
   bool isLoad = isa<LoadInst>(QueryInst);
   BasicBlock *FromBB = QueryInst->getParent();
   assert(FromBB);
 
   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.
 
   // We currently give up on any instruction which is ordered, but we do handle
   // atomic instructions which are unordered.
   // TODO: Handle ordered instructions

llvm/trunk/test/Transforms/GVN/volatile-nonvolatile.ll

+; RUN: opt -tbaa -gvn -S < %s | FileCheck %s
+
+%struct.t = type { i32* }
+
+; The loaded address and the location of the address itself are not aliased,
+; so the second reload is not necessary. Check that it can be eliminated.
+; CHECK-LABEL: test1
+; CHECK: load
+; CHECK-NOT: load
+define void @test1(%struct.t* nocapture readonly %p, i32 %v) #0 {
+entry:
+  %m = getelementptr inbounds %struct.t, %struct.t* %p, i32 0, i32 0
+  %0 = load i32*, i32** %m, align 4, !tbaa !1
+  store volatile i32 %v, i32* %0, align 4, !tbaa !6
+  %1 = load i32*, i32** %m, align 4, !tbaa !1
+  store volatile i32 %v, i32* %1, align 4, !tbaa !6
+  ret void
+}
+
+; The store via the loaded address may overwrite the address itself.
+; Make sure that both loads remain.
+; CHECK-LABEL: test2
+; CHECK: load
+; CHECK: store
+; CHECK: load
+define void @test2(%struct.t* nocapture readonly %p, i32 %v) #0 {
+entry:
+  %m = getelementptr inbounds %struct.t, %struct.t* %p, i32 0, i32 0
+  %0 = load i32*, i32** %m, align 4, !tbaa !1
+  store volatile i32 %v, i32* %0, align 4, !tbaa !1
+  %1 = load i32*, i32** %m, align 4, !tbaa !1
+  store volatile i32 %v, i32* %1, align 4, !tbaa !1
+  ret void
+}
+
+; The loads are ordered and non-monotonic. Although they are not aliased to
+; the stores, make sure both are preserved.
+; CHECK-LABEL: test3
+; CHECK: load
+; CHECK: store
+; CHECK: load
+define void @test3(%struct.t* nocapture readonly %p, i32 %v) #0 {
+entry:
+  %m = getelementptr inbounds %struct.t, %struct.t* %p, i32 0, i32 0
+  %0 = load atomic i32*, i32** %m acquire, align 4, !tbaa !1
+  store volatile i32 %v, i32* %0, align 4, !tbaa !6
+  %1 = load atomic i32*, i32** %m acquire, align 4, !tbaa !1
+  store volatile i32 %v, i32* %1, align 4, !tbaa !6
+  ret void
+}
+
+attributes #0 = { norecurse nounwind }
+
+!1 = !{!2, !3, i64 0}
+!2 = !{!"", !3, i64 0}
+!3 = !{!"any pointer", !4, i64 0}
+!4 = !{!"omnipotent char", !5, i64 0}
+!5 = !{!"Simple C/C++ TBAA"}
+!6 = !{!7, !7, i64 0}
+!7 = !{!"int", !4, i64 0}
+