[MemoryDependency] Relax the re-ordering of atomic store and unordered load/store

[skatkov]

Summary

Atomic store with Release semantic allows re-ordering of unordered load/store before the store.
Implement it.

[reames]

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

565–573

I don't this comment holds. We can get here with SI being e.g. a ceq_cst store. Reordering that with just about anything is illegal.

The prior change to check is non-unordered instead of non-simple looks reasonable, but the change below doesn't seem to follow.

[skatkov]

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

565–573

Thank you, Philip for starting review.

I tend to disagree with you. This is how I read specs.
Lang Ref:
seq_cst (sequentially consistent)
In addition to the guarantees of acq_rel (acquire for an operation that only reads, release for an operation that only writes), there is a global total order on all sequentially-consistent operations on all addresses, which is consistent with the happens-before partial order and with the modification orders of all the affected addresses. Each sequentially-consistent read sees the last preceding write to the same address in this global order. This corresponds to the C++0x/C1x memory_order_seq_cst and Java volatile.

c++(https://en.cppreference.com/w/c/atomic/memory_order):
memory_order_seq_cst A load operation with this memory order performs an acquire operation, a store performs a release operation, and read-modify-write performs both an acquire operation and a release operation, plus a single total order exists in which all threads observe all modifications in the same order (see Sequentially-consistent ordering below)

So Store with seq_cst is a Store Release and prohibit re-ordering with any another seq_sct instruction.

Do I miss anything?

[skatkov]

test update

[skatkov]

update a comment with explicitly mentioning of seq_cst.

[reames]

LGTM

I'm convinced on the seq_cst case.

I went ahead and landed an expanded version of your new test file. Please rebase and sanity check that none of the new tests give unexpected results before committing. No further review needed unless you see something weird.

llvm/lib/Analysis/MemoryDependenceAnalysis.cpp

MemDepResult MemoryDependenceResults::getSimplePointerDependencyFrom(
   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 and only if the instruction I is either a non-unordered
+  // load or a non-unordered store.
+  auto isNonUnorderedLoadOrStore = [](Instruction *I) -> bool {
+    if (auto *LI = dyn_cast<LoadInst>(I))
+      return !LI->isUnordered();
+    if (auto *SI = dyn_cast<StoreInst>(I))
+      return !SI->isUnordered();
+    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()) {
if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
       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() && SI->isAtomic()) {
-        if (!QueryInst || isNonSimpleLoadOrStore(QueryInst) ||
+        if (!QueryInst || isNonUnorderedLoadOrStore(QueryInst) ||
             isOtherMemAccess(QueryInst))
           return MemDepResult::getClobber(SI);
-        if (SI->getOrdering() != AtomicOrdering::Monotonic)
-          return MemDepResult::getClobber(SI);
+        // Ok, if we are here the guard above guarantee us that
+        // QueryInst is a non-atomic or unordered load/store.
+        // SI is atomic with monotonic or release semantic (seq_cst for store
+        // is actually a release semantic plus total order over other seq_cst
+        // instructions, as soon as QueryInst is not seq_cst we can consider it
+        // as simple release semantic).
+        // Monotonic and Release semantic allows re-ordering before store
+        // so we are safe to go further and check the aliasing. It will prohibit
+        // re-ordering in case locations are may or must alias.
       }
 
       // 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 || QueryInst->isVolatile())
           return MemDepResult::getClobber(SI);

llvm/test/Analysis/MemoryDependenceAnalysis/reorder-over-store-atomic.ll

;
   %l2 = load atomic i32, i32* @w unordered, align 4
   %res.1 = sub i32 %l1, %l2
   %res = add i32 %res.1, %lv
   ret i32 %res
 }
 
 define i32 @test_store_cst_unordered(i32 %x) {
 ; CHECK-LABEL: @test_store_cst_unordered(
-; CHECK-NEXT:    [[L1:%.*]] = load atomic i32, i32* @w unordered, align 4
 ; CHECK-NEXT:    store atomic i32 [[X:%.*]], i32* @u seq_cst, align 4
-; CHECK-NEXT:    [[L2:%.*]] = load atomic i32, i32* @w unordered, align 4
-; CHECK-NEXT:    [[RES:%.*]] = sub i32 [[L1]], [[L2]]
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 0
 ;
   %l1 = load atomic i32, i32* @w unordered, align 4
   store atomic i32 %x, i32* @u seq_cst, align 4
   %l2 = load atomic i32, i32* @w unordered, align 4
   %res = sub i32 %l1, %l2
   ret i32 %res
 }
 
 define i32 @test_store_release_unordered(i32 %x) {
 ; CHECK-LABEL: @test_store_release_unordered(
-; CHECK-NEXT:    [[L1:%.*]] = load atomic i32, i32* @w unordered, align 4
 ; CHECK-NEXT:    store atomic i32 [[X:%.*]], i32* @u release, align 4
-; CHECK-NEXT:    [[L2:%.*]] = load atomic i32, i32* @w unordered, align 4
-; CHECK-NEXT:    [[RES:%.*]] = sub i32 [[L1]], [[L2]]
-; CHECK-NEXT:    ret i32 [[RES]]
+; CHECK-NEXT:    ret i32 0
 ;
   %l1 = load atomic i32, i32* @w unordered, align 4
   store atomic i32 %x, i32* @u release, align 4
   %l2 = load atomic i32, i32* @w unordered, align 4
   %res = sub i32 %l1, %l2
   ret i32 %res
 }