[LICM] Make store promotion work in the face of unordered atomics

[reames]

Summary

Extend our store promotion code to deal with unordered atomic accesses. Ordered atomics continue to be unhandled.

Most of the change is straight-forward, the only complicated bit is in the reasoning around mixing of atomic and non-atomic memory access. Rather than trying to reason about the complex semantics in these cases, I simply disallowed promotion when both atomic and non-atomic accesses are present. This is conservatively correct.

It seems really tempting to just promote all access to atomics, but the original accesses might have been conditional. Since we can't lower an arbitrary atomic type, it might not be safe to promote all access to atomic. Consider a loop like the following:
while(b) {

load i128 ...
if (can lower i128 atomic)
  store atomic i128 ...
else
  store i128

}

It could be there's no race on the location and thus the code is perfectly well defined even if we can't lower a i128 atomically. Promoting the non-atomic accesses to atomic would be incorrect.

[jfb]

Can you add tests which validates that:

• Atomics in a loop aren't moved past a signal fence.
• Volatile atomics aren't affected.

Also, parts of the C++ standards committee thinks that the standard should "discourage non-normatively aggressive optimizations, e.g across large or unbounded loops" in the context of p0062r0. There isn't full consensus on this yet, but I'd be cautious about doing anything too aggressive to relaxed (a.k.a. monotonic) accesses for now. It would be good to also add a test for the example in p0062r0 and make sure it doesn't get optimized for now. I'll ping Hans to see what he thinks.

lib/Transforms/Scalar/LICM.cpp

939

I'm being a bit paranoid here (since this shouldn't happen because you prevent mixing of atomic / non-atomic), but it would be good to assert((Alignment == 0 ? !store->isAtomic() : true) && "atomic alignment can't be 0"); just to make sure that future edits don't introduce bugs.

test/Transforms/LICM/atomics.ll

69

Could you add a similar test where the loop does a monotonic load followed by a monotonic store?

77

CHECK-NOT: store

102

Could you also add a test which has:

loop:
  store i32 5, i32* %x
  %vala = load atomic i32, i32* %y monotonic, align 4
  store atomic i32 %vala, i32* %z unordered, align 4
  %exitcond = icmp ne i32 %vala, 0
  br i1 %exitcond, label %end, label %loop

Note the unordered store is now to %z which should also be noalias.

118

Also check that the unordered atomic is still there.

[jfb]

Hans pointed out another issue worth adding a test for: you can't remove all atomic accesses from loops which aren't proven to terminate (or otherwise have I/O, volatile, synchronization):

[intro.multithread] 24:
The implementation may assume that any thread will eventually do one of 
the following:
— terminate,
— make a call to a library I/O function,
— access or modify a volatile object, or
— perform a synchronization operation or an atomic operation.
[ Note: This is intended to allow compiler transformations such as 
removal of empty loops, even when
termination cannot be proven. —end note ]

Regardless of what the standard says, it's desirable to keep atomic stores inside infinite loops, though IIUC that would be OK for "unordered" (a.k.a. Java) atomics, but not "monotonic" (C++ relaxed)? It all boils down to what LLVM's memory model is compared to C++'s, and I'm not clear on this (at the minimum it should be as strict as the language it's honoring).

He also points at this article which he believes would be more profitable profitable to implement (in separate patches). The problem in the past was that LLVM didn't have enough alias information to make this work in common cases, but offers to put us in contact with the author off-list.

[reames]

JF,

I'm going to respond to your points in more detail at a future point,
but I did want to quickly say that I do not feel it's appropriate to
keep adding tests for every possible combination of ordered atomics
optimizations under the sun. I've gone along so far because the amount
of work has been less than that required to argue the case, but given
I'm working on supporting only the unordered variety, I really don't see
how the ordered ones are relevant beyond a couple of simple tests to
make sure I don't accidentally include ordered where only unordered was
intended.

Philip

[hfinkel]

Promoting the non-atomic accesses to atomic would be incorrect.

Why?

Hans pointed out another issue worth adding a test for: you can't remove all atomic accesses from loops which aren't proven to terminate (or otherwise have I/O, volatile, synchronization):

...

Also, parts of the C++ standards committee thinks that the standard should "discourage non-normatively aggressive optimizations, e.g across large or unbounded loops" in the context of p0062r0.

Philip, can you comment on the original use cases here? Are there cases where indefinitely postponing the write (because, say, the loop ended up not terminating) would be acceptable?

[reames]

In D15592#342294, @hfinkel wrote:

Promoting the non-atomic accesses to atomic would be incorrect.

Why?

Per the example I gave, we might not be able to lower a 128 bit atomic, and the code might be conditional on that fact. Inserting an unconditional i128 atomic which can't be lowered which wasn't in the original code in that case seems "questionable". I didn't have a need to do this and the semantics seemed a bit unclear, so it seemed better to avoid.

Philip, can you comment on the original use cases here? Are there cases where indefinitely postponing the write (because, say, the loop ended up not terminating) would be acceptable?

As I said previous, I consider most of JFs comments to be wildly off topic. Particularly, the "unordered" ordering is not related to C++ at all. As specifically documented in the LangRef: "This is intended to provide a guarantee strong enough to model Java’s non-volatile shared variables. " This is exactly the purpose I'm using it for. To the best of my knowledge (which admittedly isn't that extensive here), there is no way to generate an "unordered" instruction from C++ code.

On the topic of infinite loops, I could go either way. In practice, any infinite loop will have a safepoint or deoptimization point within it, so the loop promotion couldn't trigger anyways. Given that, I don't see any reason why we'd need to treat potentially infinite loops specially here. (Again, C++'s rules are not relevant.)

(Hoping to get back to this line of work soon. Distracted with higher priority tasks at the moment.)

[hfinkel]

In D15592#343574, @reames wrote:

In D15592#342294, @hfinkel wrote:

Promoting the non-atomic accesses to atomic would be incorrect.

Why?

Per the example I gave, we might not be able to lower a 128 bit atomic, and the code might be conditional on that fact. Inserting an unconditional i128 atomic which can't be lowered which wasn't in the original code in that case seems "questionable". I didn't have a need to do this and the semantics seemed a bit unclear, so it seemed better to avoid.

Fair enough, and I'm fine with not doing this. I don't understand your example, however, because if we can't lower the atomic, then the compilation will fail regardless of whether or not the atomic is conditionally executed. We still need to generate code for it if it is present.

Philip, can you comment on the original use cases here? Are there cases where indefinitely postponing the write (because, say, the loop ended up not terminating) would be acceptable?

As I said previous, I consider most of JFs comments to be wildly off topic. Particularly, the "unordered" ordering is not related to C++ at all. As specifically documented in the LangRef: "This is intended to provide a guarantee strong enough to model Java’s non-volatile shared variables. " This is exactly the purpose I'm using it for. To the best of my knowledge (which admittedly isn't that extensive here), there is no way to generate an "unordered" instruction from C++ code.

I agree, the C++ rules here are not strictly relevant.

On the topic of infinite loops, I could go either way. In practice, any infinite loop will have a safepoint or deoptimization point within it, so the loop promotion couldn't trigger anyways. Given that, I don't see any reason why we'd need to treat potentially infinite loops specially here. (Again, C++'s rules are not relevant.)

I understand, and the fact that this can't come up in your environment is interesting. However, from LLVM's perspective, we still need to decide on the semantics here.

(Hoping to get back to this line of work soon. Distracted with higher priority tasks at the moment.)

[reames]

In D15592#343586, @hfinkel wrote:

In D15592#343574, @reames wrote:

In D15592#342294, @hfinkel wrote:

Promoting the non-atomic accesses to atomic would be incorrect.

Why?

Per the example I gave, we might not be able to lower a 128 bit atomic, and the code might be conditional on that fact. Inserting an unconditional i128 atomic which can't be lowered which wasn't in the original code in that case seems "questionable". I didn't have a need to do this and the semantics seemed a bit unclear, so it seemed better to avoid.

Fair enough, and I'm fine with not doing this. I don't understand your example, however, because if we can't lower the atomic, then the compilation will fail regardless of whether or not the atomic is conditionally executed. We still need to generate code for it if it is present.

My reasoning was that the very next thing the optimizer might do is constant fold the "can lower i128 atomically" branch to false. The original program would then not contain a atomic i128 (i.e. codegen failure) while a program we promoted to atomic i128 would. I'm not sure this is strictly speaking legal since the program is relying on optimizer behaviour for correctness.

On the topic of infinite loops, I could go either way. In practice, any infinite loop will have a safepoint or deoptimization point within it, so the loop promotion couldn't trigger anyways. Given that, I don't see any reason why we'd need to treat potentially infinite loops specially here. (Again, C++'s rules are not relevant.)

I understand, and the fact that this can't come up in your environment is interesting. However, from LLVM's perspective, we still need to decide on the semantics here.

I think the answer should be that "unordered" atomics are treated like normal non-atomic instructions in all ways *except* that the actual memory operation is atomic. Thus, there are no special requirement about infinite loops.

I draw a mental distinction between atomicity, ordering, and visibility. All of our "atomics" are atomic, but not all of them are ordered. The visibility rules are essentially unspecified, but in practice, we have to give the "ordered" forms eventual visibility guarantees since that's what the C++ spec requires.

To say this differently, I really don't think we want the optimizer to be in a position where it has to prove a loop is not dynamically infinite before doing store promotion. That seems like a major complication. If we later find we need a unordered, atomic, but eventually visible store, I'd rather add that explicitly to the IR. Having both forms seems potentially useful.

For a code clarity perspective, should we add a predicate like mustBeEventuallyVisible(AtomicOrdering)? This would give a place to describe the result of this discussion - whatever we eventually settle on - in a way future uses might find. :)

p.s. Lest it be confusing, our needs on this changed in the not too distant past. I was at one point arguing that LLVM should allow infinite loops without side effects. I'm no longer of that belief. So long as every infinite loop has a side effect (for us, a potential safepoint, deoptimization point, or call), then we do not need any special handling for the unordered atomic stores.

[jfb]

On the topic of infinite loops, I could go either way. In practice,

any infinite loop will have a safepoint or deoptimization point within it,
so the loop promotion couldn't trigger anyways. Given that, I don't see
any reason why we'd need to treat potentially infinite loops specially
here. (Again, C++'s rules are not relevant.)

I understand, and the fact that this can't come up in your environment

is interesting. However, from LLVM's perspective, we still need to decide
on the semantics here.

I think the answer should be that "unordered" atomics are treated like
normal non-atomic instructions in all ways *except* that the actual memory
operation is atomic. Thus, there are no special requirement about infinite
loops.

That's totally fine by me. My concern is that C++ relaxed atomics
inadvertently gain the same semantics. Maybe not in your patch, but through
further refactoring. That's why I ask for negative tests on relaxed
atomics: to catch if they ever start doing the wrong thing.

[reames]

Add requested tests, address comments, and rebase on ToT.

[sanjoy]

Last update was 3 months ago. Feel free to add me back if you resurrect this review.

[• dberlin]

Is there anything left to do on this? If not, you should commit this :)

[sanjoy]

This LGTM!

lib/Transforms/Scalar/LICM.cpp

781

clang-format?

lib/Transforms/Scalar/LICM.cpp

class LoopPromoter : public LoadAndStorePromoter {
     SmallPtrSetImpl<Value*> &PointerMustAliases;
     SmallVectorImpl<BasicBlock*> &LoopExitBlocks;
     SmallVectorImpl<Instruction*> &LoopInsertPts;
     PredIteratorCache &PredCache;
     AliasSetTracker &AST;
     LoopInfo &LI;
     DebugLoc DL;
     int Alignment;
+    bool UnorderedAtomic;
     AAMDNodes AATags;
 
     Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
       if (Instruction *I = dyn_cast<Instruction>(V))
         if (Loop *L = LI.getLoopFor(I->getParent()))
           if (!L->contains(BB)) {
             // We need to create an LCSSA PHI node for the incoming value and
             // store that.
namespace {
 
   public:
     LoopPromoter(Value *SP,
                  ArrayRef<const Instruction *> Insts,
                  SSAUpdater &S, SmallPtrSetImpl<Value *> &PMA,
                  SmallVectorImpl<BasicBlock *> &LEB,
                  SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC,
                  AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
+                 bool UnorderedAtomic,
                  const AAMDNodes &AATags)
         : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
           LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
-          LI(li), DL(dl), Alignment(alignment), AATags(AATags) {}
+          LI(li), DL(dl), Alignment(alignment),
+          UnorderedAtomic(UnorderedAtomic),AATags(AATags) {}
 
     bool isInstInList(Instruction *I,
                       const SmallVectorImpl<Instruction*> &) const override {
       Value *Ptr;
       if (LoadInst *LI = dyn_cast<LoadInst>(I))
         Ptr = LI->getOperand(0);
       else
         Ptr = cast<StoreInst>(I)->getPointerOperand();
       return PointerMustAliases.count(Ptr);
     }
 
     void doExtraRewritesBeforeFinalDeletion() const override {
       // Insert stores after in the loop exit blocks.  Each exit block gets a
       // store of the live-out values that feed them.  Since we've already told
       // the SSA updater about the defs in the loop and the preheader
       // definition, it is all set and we can start using it.
       for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
         BasicBlock *ExitBlock = LoopExitBlocks[i];
         Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
         LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
         Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
         Instruction *InsertPos = LoopInsertPts[i];
         StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
+        if (UnorderedAtomic)
+          NewSI->setOrdering(AtomicOrdering::Unordered);
         NewSI->setAlignment(Alignment);
         NewSI->setDebugLoc(DL);
         if (AATags) NewSI->setAAMetadata(AATags);
       }
     }
 
     void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
       // Update alias analysis.
bool llvm::promoteLoopAccessesToScalars(AliasSet &AS,
   bool GuaranteedToExecute = false;
 
   SmallVector<Instruction*, 64> LoopUses;
   SmallPtrSet<Value*, 4> PointerMustAliases;
 
   // We start with an alignment of one and try to find instructions that allow
   // us to prove better alignment.
   unsigned Alignment = 1;
+  // Keep track of which types of access we see
+  bool SawUnorderedAtomic = false; 
+  bool SawNotAtomic = false;
   AAMDNodes AATags;
   bool HasDedicatedExits = CurLoop->hasDedicatedExits();
 
   // Check that all of the pointers in the alias set have the same type.  We
   // cannot (yet) promote a memory location that is loaded and stored in
   // different sizes.  While we are at it, collect alignment and AA info.
   for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
     Value *ASIV = ASI->getValue();
for (User *U : ASIV->users()) {
       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 (const LoadInst *load = dyn_cast<LoadInst>(UI)) {
         assert(!load->isVolatile() && "AST broken");
-        if (!load->isSimple())
+        if (!load->isUnordered())
           return Changed;
+        SawUnorderedAtomic |= load->isAtomic();
+        SawNotAtomic |= !load->isAtomic();
       } 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->isSimple())
+        if (!store->isUnordered())
           return Changed;
+        SawUnorderedAtomic |= store->isAtomic();
+        SawNotAtomic |= !store->isAtomic();
         // Don't sink stores from loops without dedicated block exits. Exits
         // containing indirect branches are not transformed by loop simplify,
         // make sure we catch that. An additional load may be generated in the
         // preheader for SSA updater, so also avoid sinking when no preheader
         // is available.
         if (!HasDedicatedExits || !Preheader)
           return Changed;
 
         // Note that we only check GuaranteedToExecute inside the store case
         // so that we do not introduce stores where they did not exist before
         // (which would break the LLVM concurrency model).
 
         // If the alignment of this instruction allows us to specify a more
         // restrictive (and performant) alignment and if we are sure this
         // instruction will be executed, update the alignment.
         // Larger is better, with the exception of 0 being the best alignment.
         unsigned InstAlignment = store->getAlignment();
         if ((InstAlignment > Alignment || InstAlignment == 0) && Alignment != 0)
           if (isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo)) {
             GuaranteedToExecute = true;
             Alignment = InstAlignment;
           }
 
         if (!GuaranteedToExecute)
           GuaranteedToExecute = isGuaranteedToExecute(*UI, DT, 
                                                       CurLoop, SafetyInfo);
 
       } else
         return Changed; // Not a load or store.
 
       // Merge the AA tags.
       if (LoopUses.empty()) {
         // On the first load/store, just take its AA tags.
         UI->getAAMetadata(AATags);
       } else if (AATags) {
         UI->getAAMetadata(AATags, /* Merge = */ true);
       }
 
       LoopUses.push_back(UI);
     }
   }
 
+  // If we found both an unordered atomic instruction and a non-atomic memory
+  // access, bail.  We can't blindly promote non-atomic to atomic since we
+  // might not be able to lower the result.  We can't downgrade since that
+  // would violate memory model.  Also, align 0 is an error for atomics.
+  if (SawUnorderedAtomic && SawNotAtomic)
+    return Changed;
+
   // If there isn't a guaranteed-to-execute instruction, we can't promote.
   if (!GuaranteedToExecute)
     return Changed;
 
   // Otherwise, this is safe to promote, lets do it!
   DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n');
   Changed = true;
   ++NumPromoted;
for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i)
       InsertPts[i] = &*ExitBlocks[i]->getFirstInsertionPt();
   }
 
   // We use the SSAUpdater interface to insert phi nodes as required.
   SmallVector<PHINode*, 16> NewPHIs;
   SSAUpdater SSA(&NewPHIs);
   LoopPromoter Promoter(SomePtr, LoopUses, SSA,
                         PointerMustAliases, ExitBlocks,
-                        InsertPts, PIC, *CurAST, *LI, DL, Alignment, AATags);
+                        InsertPts, PIC, *CurAST, *LI, DL, Alignment,
+                        SawUnorderedAtomic, AATags);
 
   // Set up the preheader to have a definition of the value.  It is the live-out
   // value from the preheader that uses in the loop will use.
   LoadInst *PreheaderLoad =
     new LoadInst(SomePtr, SomePtr->getName()+".promoted",
                  Preheader->getTerminator());
+  if (SawUnorderedAtomic)
+    PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
   PreheaderLoad->setAlignment(Alignment);
   PreheaderLoad->setDebugLoc(DL);
   if (AATags) PreheaderLoad->setAAMetadata(AATags);
   SSA.AddAvailableValue(Preheader, PreheaderLoad);
 
   // Rewrite all the loads in the loop and remember all the definitions from
   // stores in the loop.
   Promoter.run(LoopUses);

test/Transforms/LICM/atomics.ll

 
 end:
   ret i32 %vala
 ; CHECK-LABEL: define i32 @test3(
 ; CHECK: load atomic i32, i32* %x unordered
 ; CHECK-NEXT: br label %loop
 }
 
-; Don't try to "sink" unordered stores yet; it is legal, but the machinery
-; isn't there.
+; We can sink an unordered store
 define i32 @test4(i32* nocapture noalias %x, i32* nocapture %y) nounwind uwtable ssp {
 entry:
   br label %loop
 
 loop:
   %vala = load atomic i32, i32* %y monotonic, align 4
   store atomic i32 %vala, i32* %x unordered, align 4
   %exitcond = icmp ne i32 %vala, 0
   br i1 %exitcond, label %end, label %loop
 
 end:
   ret i32 %vala
 ; CHECK-LABEL: define i32 @test4(
+; CHECK-LABEL: loop:
+; CHECK: load atomic i32, i32* %y monotonic
+; CHECK-LABEL: end:
+; CHECK-NEXT:   %[[LCSSAPHI:.*]] = phi i32 [ %vala
+; CHECK:   store atomic i32 %[[LCSSAPHI]], i32* %x unordered, align 4
+}
+
+; We currently don't handle ordered atomics.
+define i32 @test5(i32* nocapture noalias %x, i32* nocapture %y) nounwind uwtable ssp {
+entry:
+  br label %loop
+
+loop:
+  %vala = load atomic i32, i32* %y monotonic, align 4
+  store atomic i32 %vala, i32* %x release, align 4
+  %exitcond = icmp ne i32 %vala, 0
+  br i1 %exitcond, label %end, label %loop
+
+end:
+  ret i32 %vala
+; CHECK-LABEL: define i32 @test5(
 ; CHECK: load atomic i32, i32* %y monotonic
 ; CHECK-NEXT: store atomic
 }
+
+; Mixing unorder atomics and normal loads/stores is
+; current implemented
+define i32 @test6(i32* nocapture noalias %x, i32* nocapture %y) nounwind uwtable ssp {
+entry:
+  br label %loop
+
+loop:
+  store i32 5, i32* %x
+  %vala = load atomic i32, i32* %y monotonic, align 4
+  store atomic i32 %vala, i32* %x unordered, align 4
+  %exitcond = icmp ne i32 %vala, 0
+  br i1 %exitcond, label %end, label %loop
+
+end:
+  ret i32 %vala
+; CHECK-LABEL: define i32 @test6(
+; CHECK: load atomic i32, i32* %y
+; CHECK-NEXT: store atomic i32
+}

test/Transforms/LICM/scalar_promote.ll

 
 ; CHECK: for.body.lr.ph:
 ; CHECK-NEXT:  %gi.promoted = load i32, i32* %gi, align 4, !tbaa !0
 ; CHECK: for.cond.for.end_crit_edge:
 ; CHECK-NEXT:  %[[LCSSAPHI:.*]] = phi i32 [ %inc
 ; CHECK-NEXT:  store i32 %[[LCSSAPHI]], i32* %gi, align 4, !tbaa !0
 }
 
+
+define void @test7(i32 %i) {
+Entry:
+  br label %Loop
+; CHECK-LABEL: @test7(
+; CHECK: Entry:
+; CHECK-NEXT:   load atomic i32, i32* @X unordered, align 4
+; CHECK-NEXT:   br label %Loop
+
+
+Loop:   ; preds = %Loop, %0
+  %j = phi i32 [ 0, %Entry ], [ %Next, %Loop ]    ; <i32> [#uses=1]
+  %x = load atomic i32, i32* @X unordered, align 4
+  %x2 = add i32 %x, 1
+  store atomic i32 %x2, i32* @X unordered, align 4
+  %Next = add i32 %j, 1
+  %cond = icmp eq i32 %Next, 0
+  br i1 %cond, label %Out, label %Loop
+
+Out:
+  ret void
+; CHECK: Out:
+; CHECK-NEXT:   %[[LCSSAPHI:.*]] = phi i32 [ %x2
+; CHECK-NEXT:   store atomic i32 %[[LCSSAPHI]], i32* @X unordered, align 4
+; CHECK-NEXT:   ret void
+
+}
+
 !0 = !{!4, !4, i64 0}
 !1 = !{!"omnipotent char", !2}
 !2 = !{!"Simple C/C++ TBAA"}
 !3 = !{!5, !5, i64 0}
 !4 = !{!"int", !1}
 !5 = !{!"float", !1}