1dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines//===-- AtomicExpandLoadLinkedPass.cpp - Expand atomic instructions -------===// 236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// The LLVM Compiler Infrastructure 436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This file is distributed under the University of Illinois Open Source 636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// License. See LICENSE.TXT for details. 736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 1036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// This file contains a pass (at IR level) to replace atomic instructions with 1136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// appropriate (intrinsic-based) ldrex/strex loops. 1236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines// 1336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines//===----------------------------------------------------------------------===// 1436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/CodeGen/Passes.h" 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Function.h" 1736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/IRBuilder.h" 1836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Instructions.h" 1936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Intrinsics.h" 2036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Module.h" 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Support/Debug.h" 2236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Target/TargetLowering.h" 2336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Target/TargetMachine.h" 24cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/Target/TargetSubtargetInfo.h" 25cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 2636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesusing namespace llvm; 2736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "arm-atomic-expand" 29dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 3036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace { 31dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines class AtomicExpandLoadLinked : public FunctionPass { 32cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines const TargetMachine *TM; 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines public: 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static char ID; // Pass identification, replacement for typeid 35dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines explicit AtomicExpandLoadLinked(const TargetMachine *TM = nullptr) 36cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines : FunctionPass(ID), TM(TM) { 37dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines initializeAtomicExpandLoadLinkedPass(*PassRegistry::getPassRegistry()); 38dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 3936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool expandAtomicInsts(Function &F); 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool expandAtomicLoad(LoadInst *LI); 4436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool expandAtomicStore(StoreInst *LI); 4536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool expandAtomicRMW(AtomicRMWInst *AI); 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool expandAtomicCmpXchg(AtomicCmpXchgInst *CI); 4736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 4836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AtomicOrdering insertLeadingFence(IRBuilder<> &Builder, AtomicOrdering Ord); 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void insertTrailingFence(IRBuilder<> &Builder, AtomicOrdering Ord); 50dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines }; 51dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines} 5236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 53dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hineschar AtomicExpandLoadLinked::ID = 0; 54dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hineschar &llvm::AtomicExpandLoadLinkedID = AtomicExpandLoadLinked::ID; 55cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen HinesINITIALIZE_TM_PASS(AtomicExpandLoadLinked, "atomic-ll-sc", 56cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines "Expand Atomic calls in terms of load-linked & store-conditional", 57cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines false, false) 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesFunctionPass *llvm::createAtomicExpandLoadLinkedPass(const TargetMachine *TM) { 60dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return new AtomicExpandLoadLinked(TM); 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 63dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool AtomicExpandLoadLinked::runOnFunction(Function &F) { 64cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!TM || !TM->getSubtargetImpl()->enableAtomicExpandLoadLinked()) 65dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines return false; 66dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<Instruction *, 1> AtomicInsts; 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Changing control-flow while iterating through it is a bad idea, so gather a 7036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // list of all atomic instructions before we start. 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (BasicBlock &BB : F) 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Instruction &Inst : BB) { 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<AtomicRMWInst>(&Inst) || isa<AtomicCmpXchgInst>(&Inst) || 7436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (isa<LoadInst>(&Inst) && cast<LoadInst>(&Inst)->isAtomic()) || 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (isa<StoreInst>(&Inst) && cast<StoreInst>(&Inst)->isAtomic())) 7636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AtomicInsts.push_back(&Inst); 7736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 7836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 7936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool MadeChange = false; 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Instruction *Inst : AtomicInsts) { 81cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!TM->getTargetLowering()->shouldExpandAtomicInIR(Inst)) 8236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(Inst)) 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MadeChange |= expandAtomicRMW(AI); 8636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else if (AtomicCmpXchgInst *CI = dyn_cast<AtomicCmpXchgInst>(Inst)) 8736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MadeChange |= expandAtomicCmpXchg(CI); 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MadeChange |= expandAtomicLoad(LI); 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines MadeChange |= expandAtomicStore(SI); 9236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Unknown atomic instruction"); 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return MadeChange; 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 99dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool AtomicExpandLoadLinked::expandAtomicLoad(LoadInst *LI) { 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Load instructions don't actually need a leading fence, even in the 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // SequentiallyConsistent case. 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AtomicOrdering MemOpOrder = 103cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines TM->getTargetLowering()->getInsertFencesForAtomic() ? Monotonic 104cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines : LI->getOrdering(); 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The only 64-bit load guaranteed to be single-copy atomic by the ARM ARM is 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // an ldrexd (A3.5.3). 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IRBuilder<> Builder(LI); 109cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *Val = TM->getTargetLowering()->emitLoadLinked( 110cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Builder, LI->getPointerOperand(), MemOpOrder); 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines insertTrailingFence(Builder, LI->getOrdering()); 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LI->replaceAllUsesWith(Val); 11536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LI->eraseFromParent(); 11636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 120dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool AtomicExpandLoadLinked::expandAtomicStore(StoreInst *SI) { 12136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The only atomic 64-bit store on ARM is an strexd that succeeds, which means 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // we need a loop and the entire instruction is essentially an "atomicrmw 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // xchg" that ignores the value loaded. 12436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IRBuilder<> Builder(SI); 12536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AtomicRMWInst *AI = 12636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.CreateAtomicRMW(AtomicRMWInst::Xchg, SI->getPointerOperand(), 12736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SI->getValueOperand(), SI->getOrdering()); 12836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SI->eraseFromParent(); 12936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 13036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Now we have an appropriate swap instruction, lower it as usual. 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return expandAtomicRMW(AI); 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 13336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 134dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool AtomicExpandLoadLinked::expandAtomicRMW(AtomicRMWInst *AI) { 13536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AtomicOrdering Order = AI->getOrdering(); 13636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Addr = AI->getPointerOperand(); 13736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *BB = AI->getParent(); 13836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Function *F = BB->getParent(); 13936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LLVMContext &Ctx = F->getContext(); 14036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 14136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Given: atomicrmw some_op iN* %addr, iN %incr ordering 14236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 14336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The standard expansion we produce is: 14436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // [...] 14536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // fence? 14636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // atomicrmw.start: 14736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // %loaded = @load.linked(%addr) 14836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // %new = some_op iN %loaded, %incr 14936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // %stored = @store_conditional(%new, %addr) 15036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // %try_again = icmp i32 ne %stored, 0 15136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // br i1 %try_again, label %loop, label %atomicrmw.end 15236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // atomicrmw.end: 15336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // fence? 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // [...] 15536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *ExitBB = BB->splitBasicBlock(AI, "atomicrmw.end"); 15636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *LoopBB = BasicBlock::Create(Ctx, "atomicrmw.start", F, ExitBB); 15736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 15836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // This grabs the DebugLoc from AI. 15936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IRBuilder<> Builder(AI); 16036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The split call above "helpfully" added a branch at the end of BB (to the 16236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // wrong place), but we might want a fence too. It's easiest to just remove 16336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // the branch entirely. 16436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::prev(BB->end())->eraseFromParent(); 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.SetInsertPoint(BB); 16636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AtomicOrdering MemOpOrder = insertLeadingFence(Builder, Order); 16736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.CreateBr(LoopBB); 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 16936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Start the main loop block now that we've taken care of the preliminaries. 17036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.SetInsertPoint(LoopBB); 171cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *Loaded = 172cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines TM->getTargetLowering()->emitLoadLinked(Builder, Addr, MemOpOrder); 17336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *NewVal; 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines switch (AI->getOperation()) { 17636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case AtomicRMWInst::Xchg: 17736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = AI->getValOperand(); 17836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 17936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case AtomicRMWInst::Add: 18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateAdd(Loaded, AI->getValOperand(), "new"); 18136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 18236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case AtomicRMWInst::Sub: 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateSub(Loaded, AI->getValOperand(), "new"); 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case AtomicRMWInst::And: 18636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateAnd(Loaded, AI->getValOperand(), "new"); 18736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 18836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case AtomicRMWInst::Nand: 189cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines NewVal = Builder.CreateNot(Builder.CreateAnd(Loaded, AI->getValOperand()), 19036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines "new"); 19136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 19236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case AtomicRMWInst::Or: 19336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateOr(Loaded, AI->getValOperand(), "new"); 19436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 19536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case AtomicRMWInst::Xor: 19636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateXor(Loaded, AI->getValOperand(), "new"); 19736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 19836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case AtomicRMWInst::Max: 19936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateICmpSGT(Loaded, AI->getValOperand()); 20036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateSelect(NewVal, Loaded, AI->getValOperand(), "new"); 20136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 20236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case AtomicRMWInst::Min: 20336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateICmpSLE(Loaded, AI->getValOperand()); 20436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateSelect(NewVal, Loaded, AI->getValOperand(), "new"); 20536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 20636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case AtomicRMWInst::UMax: 20736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateICmpUGT(Loaded, AI->getValOperand()); 20836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateSelect(NewVal, Loaded, AI->getValOperand(), "new"); 20936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 21036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines case AtomicRMWInst::UMin: 21136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateICmpULE(Loaded, AI->getValOperand()); 21236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines NewVal = Builder.CreateSelect(NewVal, Loaded, AI->getValOperand(), "new"); 21336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines break; 21436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines default: 21536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines llvm_unreachable("Unknown atomic op"); 21636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 21736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 218cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *StoreSuccess = TM->getTargetLowering()->emitStoreConditional( 219cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Builder, NewVal, Addr, MemOpOrder); 22036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *TryAgain = Builder.CreateICmpNE( 22136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines StoreSuccess, ConstantInt::get(IntegerType::get(Ctx, 32), 0), "tryagain"); 22236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.CreateCondBr(TryAgain, LoopBB, ExitBB); 22336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.SetInsertPoint(ExitBB, ExitBB->begin()); 22536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines insertTrailingFence(Builder, Order); 22636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AI->replaceAllUsesWith(Loaded); 22836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AI->eraseFromParent(); 22936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 23036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 23136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 23236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 233dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesbool AtomicExpandLoadLinked::expandAtomicCmpXchg(AtomicCmpXchgInst *CI) { 23436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AtomicOrdering SuccessOrder = CI->getSuccessOrdering(); 23536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AtomicOrdering FailureOrder = CI->getFailureOrdering(); 23636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *Addr = CI->getPointerOperand(); 23736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *BB = CI->getParent(); 23836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Function *F = BB->getParent(); 23936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LLVMContext &Ctx = F->getContext(); 24036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 24136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Given: cmpxchg some_op iN* %addr, iN %desired, iN %new success_ord fail_ord 24236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // 24336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The full expansion we produce is: 24436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // [...] 24536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // fence? 24636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // cmpxchg.start: 24736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // %loaded = @load.linked(%addr) 24836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // %should_store = icmp eq %loaded, %desired 24936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // br i1 %should_store, label %cmpxchg.trystore, 250cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // label %cmpxchg.failure 25136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // cmpxchg.trystore: 25236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // %stored = @store_conditional(%new, %addr) 253cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // %success = icmp eq i32 %stored, 0 254cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // br i1 %success, label %cmpxchg.success, label %loop/%cmpxchg.failure 255cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // cmpxchg.success: 256cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // fence? 257cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // br label %cmpxchg.end 258cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // cmpxchg.failure: 25936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // fence? 26036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // br label %cmpxchg.end 26136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // cmpxchg.end: 262cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // %success = phi i1 [true, %cmpxchg.success], [false, %cmpxchg.failure] 263cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // %restmp = insertvalue { iN, i1 } undef, iN %loaded, 0 264cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // %res = insertvalue { iN, i1 } %restmp, i1 %success, 1 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // [...] 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *ExitBB = BB->splitBasicBlock(CI, "cmpxchg.end"); 267cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines auto FailureBB = BasicBlock::Create(Ctx, "cmpxchg.failure", F, ExitBB); 268cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines auto SuccessBB = BasicBlock::Create(Ctx, "cmpxchg.success", F, FailureBB); 269cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines auto TryStoreBB = BasicBlock::Create(Ctx, "cmpxchg.trystore", F, SuccessBB); 27036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines auto LoopBB = BasicBlock::Create(Ctx, "cmpxchg.start", F, TryStoreBB); 27136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 27236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // This grabs the DebugLoc from CI 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines IRBuilder<> Builder(CI); 27436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 27536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The split call above "helpfully" added a branch at the end of BB (to the 27636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // wrong place), but we might want a fence too. It's easiest to just remove 27736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // the branch entirely. 27836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines std::prev(BB->end())->eraseFromParent(); 27936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.SetInsertPoint(BB); 28036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AtomicOrdering MemOpOrder = insertLeadingFence(Builder, SuccessOrder); 28136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.CreateBr(LoopBB); 28236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 28336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Start the main loop block now that we've taken care of the preliminaries. 28436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.SetInsertPoint(LoopBB); 285cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *Loaded = 286cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines TM->getTargetLowering()->emitLoadLinked(Builder, Addr, MemOpOrder); 28736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *ShouldStore = 28836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.CreateICmpEQ(Loaded, CI->getCompareOperand(), "should_store"); 28936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 29036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If the the cmpxchg doesn't actually need any ordering when it fails, we can 29136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // jump straight past that fence instruction (if it exists). 29236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.CreateCondBr(ShouldStore, TryStoreBB, FailureBB); 29336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 29436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.SetInsertPoint(TryStoreBB); 295cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *StoreSuccess = TM->getTargetLowering()->emitStoreConditional( 296dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines Builder, CI->getNewValOperand(), Addr, MemOpOrder); 297cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines StoreSuccess = Builder.CreateICmpEQ( 29836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines StoreSuccess, ConstantInt::get(Type::getInt32Ty(Ctx), 0), "success"); 299cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Builder.CreateCondBr(StoreSuccess, SuccessBB, 300cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines CI->isWeak() ? FailureBB : LoopBB); 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 302cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Make sure later instructions don't get reordered with a fence if necessary. 303cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Builder.SetInsertPoint(SuccessBB); 30436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines insertTrailingFence(Builder, SuccessOrder); 30536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.CreateBr(ExitBB); 30636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 307cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Builder.SetInsertPoint(FailureBB); 308cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines insertTrailingFence(Builder, FailureOrder); 309cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Builder.CreateBr(ExitBB); 310cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 311cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Finally, we have control-flow based knowledge of whether the cmpxchg 312cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // succeeded or not. We expose this to later passes by converting any 313cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // subsequent "icmp eq/ne %loaded, %oldval" into a use of an appropriate PHI. 31436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 315cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Setup the builder so we can create any PHIs we need. 316cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Builder.SetInsertPoint(ExitBB, ExitBB->begin()); 317cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines PHINode *Success = Builder.CreatePHI(Type::getInt1Ty(Ctx), 2); 318cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Success->addIncoming(ConstantInt::getTrue(Ctx), SuccessBB); 319cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Success->addIncoming(ConstantInt::getFalse(Ctx), FailureBB); 320cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 321cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Look for any users of the cmpxchg that are just comparing the loaded value 322cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // against the desired one, and replace them with the CFG-derived version. 323cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines SmallVector<ExtractValueInst *, 2> PrunedInsts; 324cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (auto User : CI->users()) { 325cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines ExtractValueInst *EV = dyn_cast<ExtractValueInst>(User); 326cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!EV) 327cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines continue; 328cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 329cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines assert(EV->getNumIndices() == 1 && EV->getIndices()[0] <= 1 && 330cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines "weird extraction from { iN, i1 }"); 331cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 332cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (EV->getIndices()[0] == 0) 333cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines EV->replaceAllUsesWith(Loaded); 334cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines else 335cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines EV->replaceAllUsesWith(Success); 336cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 337cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines PrunedInsts.push_back(EV); 338cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 339cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 340cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // We can remove the instructions now we're no longer iterating through them. 341cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines for (auto EV : PrunedInsts) 342cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines EV->eraseFromParent(); 343cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 344cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!CI->use_empty()) { 345cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // Some use of the full struct return that we don't understand has happened, 346cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines // so we've got to reconstruct it properly. 347cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Value *Res; 348cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Res = Builder.CreateInsertValue(UndefValue::get(CI->getType()), Loaded, 0); 349cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines Res = Builder.CreateInsertValue(Res, Success, 1); 350cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 351cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines CI->replaceAllUsesWith(Res); 352cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines } 353cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines 354cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines CI->eraseFromParent(); 35536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 35636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 35736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 358dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen HinesAtomicOrdering AtomicExpandLoadLinked::insertLeadingFence(IRBuilder<> &Builder, 35936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AtomicOrdering Ord) { 360cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!TM->getTargetLowering()->getInsertFencesForAtomic()) 36136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Ord; 36236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 36336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Ord == Release || Ord == AcquireRelease || Ord == SequentiallyConsistent) 36436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.CreateFence(Release); 36536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 36636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // The exclusive operations don't need any barrier if we're adding separate 36736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // fences. 36836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Monotonic; 36936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 37036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 371dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hinesvoid AtomicExpandLoadLinked::insertTrailingFence(IRBuilder<> &Builder, 37236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AtomicOrdering Ord) { 373cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines if (!TM->getTargetLowering()->getInsertFencesForAtomic()) 37436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return; 37536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 37636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (Ord == Acquire || Ord == AcquireRelease) 37736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.CreateFence(Acquire); 37836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines else if (Ord == SequentiallyConsistent) 37936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Builder.CreateFence(SequentiallyConsistent); 38036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 381