Add AtomicExpandPass::bracketInstWithFences, and use it whenever getInsertFencesForAtomic would trigger in SelectionDAGBuilder

[morisset]

Summary

The goal is to eventually remove all the code related to getInsertFencesForAtomic
in SelectionDAGBuilder as it is wrong (designed for ARM, not really portable, works
mostly by accident because the backends are overly conservative), and repeats the
same logic that goes in emitLeading/TrailingFence.

In this patch, I make AtomicExpandPass insert the fences as it knows better
where to put them. Because this requires getting the fences and not just
passing an IRBuilder around, I had to change the return type of
emitLeading/TrailingFence.
This code only triggers on ARM for now. Because it is earlier in the pipeline
than SelectionDAGBuilder, it triggers and lowers atomic accesses to atomic so
SelectionDAGBuilder does not add barriers anymore on ARM.

If this patch is accepted I plan to implement emitLeading/TrailingFence for all
backends that setInsertFencesForAtomic(true), which will allow both making them
less conservative and simplifying SelectionDAGBuilder once they are all using
this interface.

Depends on D5090 (very minor dependency, both just happen to modify
AtomicExpandPass::runOnFunction).

[morisset]

Cleanup of some now redundant code that I had missed.

I would love getting some reviews on this patch, other patches depend on it
(D5180 being one that is otherwise ready to land). Thanks !

[jfb]

include/llvm/Target/TargetLowering.h

963 ↗

(On Diff #13846)

What should the return value be? Are there cases where a backend emits more than one instruction?

lib/CodeGen/AtomicExpandPass.cpp

167 ↗

(On Diff #13846)

Should this still be here, since the code wants to handle more than just ARM?

[morisset]

Thanks for the review, I will fix the comments as described below.

include/llvm/Target/TargetLowering.h

963 ↗

(On Diff #13846)

The return value is either nullptr (if the backend did not insert anything) or a pointer to the inserted (IR-level) instruction. There is no reason for a backend to insert several (IR-level) instructions, the only thing that makes sense for a backend to insert is an intrinsic corresponding to its hardware fence(s). Even if it requires several machine instructions for a fence, it can still be just one IR-level instruction.
I will add a comment to that effect.

lib/CodeGen/AtomicExpandPass.cpp

167 ↗

(On Diff #13846)

Probably not exactly as worded. I will reword it by saying that on some architectures load-linked is atomic for bigger sizes, and that for example on ARM...

[jfb]

Probably worth putting in the commit message: no tests changed because this shouldn't cause any functional changes?

[morisset]

Updated comments.

[jfb]

lib/CodeGen/AtomicExpandPass.cpp

168 ↗

(On Diff #13998)

That reminds me: ARM guarantees that ldrd and strd are atomic if the CPU has LPAE (e.g. A15 has that guarantee, see DDI0406C ARM architecture reference manual, sections A8.8.72-74 LDRD). Could you add this to your list of things to implement (emit ldrd/strd when appropriate)?

lib/Target/ARM/ARMISelLowering.cpp

11052 ↗

(On Diff #13998)

Fold this into the default case for the switch.

11073 ↗

(On Diff #13998)

Same.

[rnk]

lib/Target/ARM/ARMISelLowering.cpp

11052 ↗

(On Diff #13998)

We can't do this because MSVC will warn about falling off the end of the function.

[morisset]

lib/CodeGen/AtomicExpandPass.cpp

168 ↗

(On Diff #13998)

I just commited a FIXME to that effect in r218326.

[jfb]

Looks good.

lib/CodeGen/AtomicExpandPass.cpp

168 ↗

(On Diff #13998)

Thanks!

lib/Target/ARM/ARMISelLowering.cpp

11052 ↗

(On Diff #13998)

Grumble grumble MSVC.

[morisset]

Closed by commit rL218329 (authored by @morisset).

llvm/trunk/include/llvm/Target/TargetLowering.h

virtual Value *emitStoreConditional(IRBuilder<> &Builder, Value *Val,
     llvm_unreachable("Store conditional unimplemented on this target");
   }
 
   /// Inserts in the IR a target-specific intrinsic specifying a fence.
   /// It is called by AtomicExpandPass before expanding an
   ///   AtomicRMW/AtomicCmpXchg/AtomicStore/AtomicLoad.
   /// RMW and CmpXchg set both IsStore and IsLoad to true.
   /// Backends with !getInsertFencesForAtomic() should keep a no-op here.
-  virtual void emitLeadingFence(IRBuilder<> &Builder, AtomicOrdering Ord,
+  /// This function should either return a nullptr, or a pointer to an IR-level
+  ///   Instruction*. Even complex fence sequences can be represented by a
+  ///   single Instruction* through an intrinsic to be lowered later.
+  virtual Instruction* emitLeadingFence(IRBuilder<> &Builder, AtomicOrdering Ord,
           bool IsStore, bool IsLoad) const {
     assert(!getInsertFencesForAtomic());
+    return nullptr;
   }
 
   /// Inserts in the IR a target-specific intrinsic specifying a fence.
   /// It is called by AtomicExpandPass after expanding an
   ///   AtomicRMW/AtomicCmpXchg/AtomicStore/AtomicLoad.
   /// RMW and CmpXchg set both IsStore and IsLoad to true.
   /// Backends with !getInsertFencesForAtomic() should keep a no-op here.
-  virtual void emitTrailingFence(IRBuilder<> &Builder, AtomicOrdering Ord,
+  /// This function should either return a nullptr, or a pointer to an IR-level
+  ///   Instruction*. Even complex fence sequences can be represented by a
+  ///   single Instruction* through an intrinsic to be lowered later.
+  virtual Instruction* emitTrailingFence(IRBuilder<> &Builder, AtomicOrdering Ord,
           bool IsStore, bool IsLoad) const {
     assert(!getInsertFencesForAtomic());
+    return nullptr;
   }
 
   /// Returns true if the given (atomic) store should be expanded by the
   /// IR-level AtomicExpand pass into an "atomic xchg" which ignores its input.
   virtual bool shouldExpandAtomicStoreInIR(StoreInst *SI) const {
     return false;
   }
 

llvm/trunk/lib/CodeGen/AtomicExpandPass.cpp

 //===-- AtomicExpandPass.cpp - Expand atomic instructions -------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains a pass (at IR level) to replace atomic instructions with
-// either (intrinsic-based) ldrex/strex loops or AtomicCmpXchg.
+// either (intrinsic-based) load-linked/store-conditional loops or AtomicCmpXchg.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instructions.h"
public:
     explicit AtomicExpand(const TargetMachine *TM = nullptr)
       : FunctionPass(ID), TM(TM) {
       initializeAtomicExpandPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnFunction(Function &F) override;
 
   private:
+    bool bracketInstWithFences(Instruction *I, AtomicOrdering Order,
+                               bool IsStore, bool IsLoad);
     bool expandAtomicLoad(LoadInst *LI);
     bool expandAtomicStore(StoreInst *SI);
     bool expandAtomicRMW(AtomicRMWInst *AI);
     bool expandAtomicRMWToLLSC(AtomicRMWInst *AI);
     bool expandAtomicRMWToCmpXchg(AtomicRMWInst *AI);
     bool expandAtomicCmpXchg(AtomicCmpXchgInst *CI);
   };
 }
bool AtomicExpand::runOnFunction(Function &F) {
   }
 
   bool MadeChange = false;
   for (auto I : AtomicInsts) {
     auto LI = dyn_cast<LoadInst>(I);
     auto SI = dyn_cast<StoreInst>(I);
     auto RMWI = dyn_cast<AtomicRMWInst>(I);
     auto CASI = dyn_cast<AtomicCmpXchgInst>(I);
-
     assert((LI || SI || RMWI || CASI || isa<FenceInst>(I)) &&
            "Unknown atomic instruction");
 
+    auto FenceOrdering = Monotonic;
+    bool IsStore, IsLoad;
+    if (TargetLowering->getInsertFencesForAtomic()) {
+      if (LI && isAtLeastAcquire(LI->getOrdering())) {
+        FenceOrdering = LI->getOrdering();
+        LI->setOrdering(Monotonic);
+        IsStore = false;
+        IsLoad = true;
+      } else if (SI && isAtLeastRelease(SI->getOrdering())) {
+        FenceOrdering = SI->getOrdering();
+        SI->setOrdering(Monotonic);
+        IsStore = true;
+        IsLoad = false;
+      } else if (RMWI && (isAtLeastRelease(RMWI->getOrdering()) ||
+                          isAtLeastAcquire(RMWI->getOrdering()))) {
+        FenceOrdering = RMWI->getOrdering();
+        RMWI->setOrdering(Monotonic);
+        IsStore = IsLoad = true;
+      } else if (CASI && !TargetLowering->hasLoadLinkedStoreConditional() &&
+                    (isAtLeastRelease(CASI->getSuccessOrdering()) ||
+                     isAtLeastAcquire(CASI->getSuccessOrdering()))) {
+        // If a compare and swap is lowered to LL/SC, we can do smarter fence
+        // insertion, with a stronger one on the success path than on the
+        // failure path. As a result, fence insertion is directly done by
+        // expandAtomicCmpXchg in that case.
+        FenceOrdering = CASI->getSuccessOrdering();
+        CASI->setSuccessOrdering(Monotonic);
+        CASI->setFailureOrdering(Monotonic);
+        IsStore = IsLoad = true;
+      }
+
+      if (FenceOrdering != Monotonic) {
+        MadeChange |= bracketInstWithFences(I, FenceOrdering, IsStore, IsLoad);
+      }
+    }
+
     if (LI && TargetLowering->shouldExpandAtomicLoadInIR(LI)) {
       MadeChange |= expandAtomicLoad(LI);
     } else if (SI && TargetLowering->shouldExpandAtomicStoreInIR(SI)) {
       MadeChange |= expandAtomicStore(SI);
     } else if (RMWI && TargetLowering->shouldExpandAtomicRMWInIR(RMWI)) {
       MadeChange |= expandAtomicRMW(RMWI);
     } else if (CASI && TargetLowering->hasLoadLinkedStoreConditional()) {
       MadeChange |= expandAtomicCmpXchg(CASI);
     }
   }
   return MadeChange;
 }
 
+bool AtomicExpand::bracketInstWithFences(Instruction *I, AtomicOrdering Order,
+                                         bool IsStore, bool IsLoad) {
+  IRBuilder<> Builder(I);
+
+  auto LeadingFence =
+      TM->getSubtargetImpl()->getTargetLowering()->emitLeadingFence(
+      Builder, Order, IsStore, IsLoad);
+
+  auto TrailingFence =
+      TM->getSubtargetImpl()->getTargetLowering()->emitTrailingFence(
+      Builder, Order, IsStore, IsLoad);
+  // The trailing fence is emitted before the instruction instead of after
+  // because there is no easy way of setting Builder insertion point after
+  // an instruction. So we must erase it from the BB, and insert it back
+  // in the right place.
+  // We have a guard here because not every atomic operation generates a
+  // trailing fence.
+  if (TrailingFence) {
+    TrailingFence->removeFromParent();
+    TrailingFence->insertAfter(I);
+  }
+
+  return (LeadingFence || TrailingFence);
+}
+
 bool AtomicExpand::expandAtomicLoad(LoadInst *LI) {
   auto TLI = TM->getSubtargetImpl()->getTargetLowering();
-  // If getInsertFencesForAtomic() returns true, then the target does not want
-  // to deal with memory orders, and emitLeading/TrailingFence should take care
-  // of everything. Otherwise, emitLeading/TrailingFence are no-op and we
-  // should preserve the ordering.
-  AtomicOrdering MemOpOrder =
-      TLI->getInsertFencesForAtomic() ? Monotonic : LI->getOrdering();
   IRBuilder<> Builder(LI);
 
-  // Note that although no fence is required before atomic load on ARM, it is
-  // required before SequentiallyConsistent loads for the recommended Power
-  // mapping (see http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html).
-  // So we let the target choose what to emit.
-  TLI->emitLeadingFence(Builder, LI->getOrdering(),
-                        /*IsStore=*/false, /*IsLoad=*/true);
-
-  // The only 64-bit load guaranteed to be single-copy atomic by ARM is
-  // an ldrexd (A3.5.3).
+  // On some architectures, load-linked instructions are atomic for larger
+  // sizes than normal loads. For example, the only 64-bit load guaranteed
+  // to be single-copy atomic by ARM is an ldrexd (A3.5.3).
   Value *Val =
-      TLI->emitLoadLinked(Builder, LI->getPointerOperand(), MemOpOrder);
-
-  TLI->emitTrailingFence(Builder, LI->getOrdering(),
-                         /*IsStore=*/false, /*IsLoad=*/true);
+      TLI->emitLoadLinked(Builder, LI->getPointerOperand(), LI->getOrdering());
 
   LI->replaceAllUsesWith(Val);
   LI->eraseFromParent();
 
   return true;
 }
 
 bool AtomicExpand::expandAtomicStore(StoreInst *SI) {
case AtomicRMWInst::UMin:
     return Builder.CreateSelect(NewVal, Loaded, Inc, "new");
   default:
     llvm_unreachable("Unknown atomic op");
   }
 }
 
 bool AtomicExpand::expandAtomicRMWToLLSC(AtomicRMWInst *AI) {
   auto TLI = TM->getSubtargetImpl()->getTargetLowering();
-  AtomicOrdering FenceOrder = AI->getOrdering();
+  AtomicOrdering MemOpOrder = AI->getOrdering();
   Value *Addr = AI->getPointerOperand();
   BasicBlock *BB = AI->getParent();
   Function *F = BB->getParent();
   LLVMContext &Ctx = F->getContext();
-  // If getInsertFencesForAtomic() returns true, then the target does not want
-  // to deal with memory orders, and emitLeading/TrailingFence should take care
-  // of everything. Otherwise, emitLeading/TrailingFence are no-op and we
-  // should preserve the ordering.
-  AtomicOrdering MemOpOrder =
-      TLI->getInsertFencesForAtomic() ? Monotonic : FenceOrder;
 
   // Given: atomicrmw some_op iN* %addr, iN %incr ordering
   //
   // The standard expansion we produce is:
   //     [...]
   //     fence?
   // atomicrmw.start:
   //     %loaded = @load.linked(%addr)
bool AtomicExpand::expandAtomicRMWToLLSC(AtomicRMWInst *AI) {
   // This grabs the DebugLoc from AI.
   IRBuilder<> Builder(AI);
 
   // The split call above "helpfully" added a branch at the end of BB (to the
   // wrong place), but we might want a fence too. It's easiest to just remove
   // the branch entirely.
   std::prev(BB->end())->eraseFromParent();
   Builder.SetInsertPoint(BB);
-  TLI->emitLeadingFence(Builder, FenceOrder, /*IsStore=*/true, /*IsLoad=*/true);
   Builder.CreateBr(LoopBB);
 
   // Start the main loop block now that we've taken care of the preliminaries.
   Builder.SetInsertPoint(LoopBB);
   Value *Loaded = TLI->emitLoadLinked(Builder, Addr, MemOpOrder);
 
   Value *NewVal =
       performAtomicOp(AI->getOperation(), Builder, Loaded, AI->getValOperand());
 
   Value *StoreSuccess =
       TLI->emitStoreConditional(Builder, NewVal, Addr, MemOpOrder);
   Value *TryAgain = Builder.CreateICmpNE(
       StoreSuccess, ConstantInt::get(IntegerType::get(Ctx, 32), 0), "tryagain");
   Builder.CreateCondBr(TryAgain, LoopBB, ExitBB);
 
   Builder.SetInsertPoint(ExitBB, ExitBB->begin());
-  TLI->emitTrailingFence(Builder, FenceOrder, /*IsStore=*/true, /*IsLoad=*/true);
 
   AI->replaceAllUsesWith(Loaded);
   AI->eraseFromParent();
 
   return true;
 }
 
 bool AtomicExpand::expandAtomicRMWToCmpXchg(AtomicRMWInst *AI) {
-  auto TargetLowering = TM->getSubtargetImpl()->getTargetLowering();
-  AtomicOrdering FenceOrder =
-      AI->getOrdering() == Unordered ? Monotonic : AI->getOrdering();
   AtomicOrdering MemOpOrder =
-      TargetLowering->getInsertFencesForAtomic() ? Monotonic : FenceOrder;
+      AI->getOrdering() == Unordered ? Monotonic : AI->getOrdering();
   Value *Addr = AI->getPointerOperand();
   BasicBlock *BB = AI->getParent();
   Function *F = BB->getParent();
   LLVMContext &Ctx = F->getContext();
 
   // Given: atomicrmw some_op iN* %addr, iN %incr ordering
   //
   // The standard expansion we produce is:
bool AtomicExpand::expandAtomicRMWToCmpXchg(AtomicRMWInst *AI) {
   // This grabs the DebugLoc from AI.
   IRBuilder<> Builder(AI);
 
   // The split call above "helpfully" added a branch at the end of BB (to the
   // wrong place), but we want a load. It's easiest to just remove
   // the branch entirely.
   std::prev(BB->end())->eraseFromParent();
   Builder.SetInsertPoint(BB);
-  TargetLowering->emitLeadingFence(Builder, FenceOrder,
-                                   /*IsStore=*/true, /*IsLoad=*/true);
   LoadInst *InitLoaded = Builder.CreateLoad(Addr);
   // Atomics require at least natural alignment.
   InitLoaded->setAlignment(AI->getType()->getPrimitiveSizeInBits());
   Builder.CreateBr(LoopBB);
 
   // Start the main loop block now that we've taken care of the preliminaries.
   Builder.SetInsertPoint(LoopBB);
   PHINode *Loaded = Builder.CreatePHI(AI->getType(), 2, "loaded");
   Loaded->addIncoming(InitLoaded, BB);
 
   Value *NewVal =
       performAtomicOp(AI->getOperation(), Builder, Loaded, AI->getValOperand());
 
   Value *Pair = Builder.CreateAtomicCmpXchg(
       Addr, Loaded, NewVal, MemOpOrder,
       AtomicCmpXchgInst::getStrongestFailureOrdering(MemOpOrder));
   Value *NewLoaded = Builder.CreateExtractValue(Pair, 0, "newloaded");
   Loaded->addIncoming(NewLoaded, LoopBB);
 
   Value *Success = Builder.CreateExtractValue(Pair, 1, "success");
   Builder.CreateCondBr(Success, ExitBB, LoopBB);
 
   Builder.SetInsertPoint(ExitBB, ExitBB->begin());
-  TargetLowering->emitTrailingFence(Builder, FenceOrder,
-                                    /*IsStore=*/true, /*IsLoad=*/true);
 
   AI->replaceAllUsesWith(NewLoaded);
   AI->eraseFromParent();
 
   return true;
 }
 
 bool AtomicExpand::expandAtomicCmpXchg(AtomicCmpXchgInst *CI) {

llvm/trunk/lib/Target/ARM/ARMISelLowering.h

public:
 
     bool hasLoadLinkedStoreConditional() const override;
     Instruction *makeDMB(IRBuilder<> &Builder, ARM_MB::MemBOpt Domain) const;
     Value *emitLoadLinked(IRBuilder<> &Builder, Value *Addr,
                           AtomicOrdering Ord) const override;
     Value *emitStoreConditional(IRBuilder<> &Builder, Value *Val,
                                 Value *Addr, AtomicOrdering Ord) const override;
 
-    void emitLeadingFence(IRBuilder<> &Builder, AtomicOrdering Ord,
+    Instruction* emitLeadingFence(IRBuilder<> &Builder, AtomicOrdering Ord,
                           bool IsStore, bool IsLoad) const override;
-    void emitTrailingFence(IRBuilder<> &Builder, AtomicOrdering Ord,
+    Instruction* emitTrailingFence(IRBuilder<> &Builder, AtomicOrdering Ord,
                            bool IsStore, bool IsLoad) const override;
 
     bool shouldExpandAtomicLoadInIR(LoadInst *LI) const override;
     bool shouldExpandAtomicStoreInIR(StoreInst *SI) const override;
     bool shouldExpandAtomicRMWInIR(AtomicRMWInst *AI) const override;
 
     bool useLoadStackGuardNode() const override;
 

llvm/trunk/lib/Target/ARM/ARMISelLowering.cpp

if (!Subtarget->hasDataBarrier()) {
     // Only a full system barrier exists in the M-class architectures.
     Domain = Subtarget->isMClass() ? ARM_MB::SY : Domain;
     Constant *CDomain = Builder.getInt32(Domain);
     return Builder.CreateCall(DMB, CDomain);
   }
 }
 
 // Based on http://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
-void ARMTargetLowering::emitLeadingFence(IRBuilder<> &Builder,
+Instruction* ARMTargetLowering::emitLeadingFence(IRBuilder<> &Builder,
                                          AtomicOrdering Ord, bool IsStore,
                                          bool IsLoad) const {
   if (!getInsertFencesForAtomic())
-    return;
+    return nullptr;
 
   switch (Ord) {
   case NotAtomic:
   case Unordered:
     llvm_unreachable("Invalid fence: unordered/non-atomic");
   case Monotonic:
   case Acquire:
-    return; // Nothing to do
+    return nullptr; // Nothing to do
   case SequentiallyConsistent:
     if (!IsStore)
-      return; // Nothing to do
-              /*FALLTHROUGH*/
+      return nullptr; // Nothing to do
   case Release:
   case AcquireRelease:
     if (Subtarget->isSwift())
-      makeDMB(Builder, ARM_MB::ISHST);
+      return makeDMB(Builder, ARM_MB::ISHST);
     // FIXME: add a comment with a link to documentation justifying this.
     else
-      makeDMB(Builder, ARM_MB::ISH);
-    return;
+      return makeDMB(Builder, ARM_MB::ISH);
   }
+  llvm_unreachable("Unknown fence ordering in emitLeadingFence");
 }
 
-void ARMTargetLowering::emitTrailingFence(IRBuilder<> &Builder,
+Instruction* ARMTargetLowering::emitTrailingFence(IRBuilder<> &Builder,
                                           AtomicOrdering Ord, bool IsStore,
                                           bool IsLoad) const {
   if (!getInsertFencesForAtomic())
-    return;
+    return nullptr;
 
   switch (Ord) {
   case NotAtomic:
   case Unordered:
     llvm_unreachable("Invalid fence: unordered/not-atomic");
   case Monotonic:
   case Release:
-    return; // Nothing to do
+    return nullptr; // Nothing to do
   case Acquire:
   case AcquireRelease:
-    case SequentiallyConsistent:
-    makeDMB(Builder, ARM_MB::ISH);
-    return;
+    return makeDMB(Builder, ARM_MB::ISH);
   }
+  llvm_unreachable("Unknown fence ordering in emitTrailingFence");
 }
 
 // Loads and stores less than 64-bits are already atomic; ones above that
 // are doomed anyway, so defer to the default libcall and blame the OS when
 // things go wrong. Cortex M doesn't have ldrexd/strexd though, so don't emit
 // anything for those.
 bool ARMTargetLowering::shouldExpandAtomicStoreInIR(StoreInst *SI) const {
   unsigned Size = SI->getValueOperand()->getType()->getPrimitiveSizeInBits();