1 //===- AtomicExpandPass.cpp - Expand atomic instructions ------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file contains a pass (at IR level) to replace atomic instructions with
10 // __atomic_* library calls, or target specific instruction which implement the
11 // same semantics in a way which better fits the target backend. This can
12 // include the use of (intrinsic-based) load-linked/store-conditional loops,
13 // AtomicCmpXchg, or type coercions.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/CodeGen/AtomicExpandUtils.h"
21 #include "llvm/CodeGen/RuntimeLibcalls.h"
22 #include "llvm/CodeGen/TargetLowering.h"
23 #include "llvm/CodeGen/TargetPassConfig.h"
24 #include "llvm/CodeGen/TargetSubtargetInfo.h"
25 #include "llvm/CodeGen/ValueTypes.h"
26 #include "llvm/IR/Attributes.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/Constant.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/IR/DataLayout.h"
31 #include "llvm/IR/DerivedTypes.h"
32 #include "llvm/IR/Function.h"
33 #include "llvm/IR/IRBuilder.h"
34 #include "llvm/IR/InstIterator.h"
35 #include "llvm/IR/Instruction.h"
36 #include "llvm/IR/Instructions.h"
37 #include "llvm/IR/Module.h"
38 #include "llvm/IR/Type.h"
39 #include "llvm/IR/User.h"
40 #include "llvm/IR/Value.h"
41 #include "llvm/Pass.h"
42 #include "llvm/Support/AtomicOrdering.h"
43 #include "llvm/Support/Casting.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Support/ErrorHandling.h"
46 #include "llvm/Support/raw_ostream.h"
47 #include "llvm/Target/TargetMachine.h"
54 #define DEBUG_TYPE "atomic-expand"
58 class AtomicExpand
: public FunctionPass
{
59 const TargetLowering
*TLI
= nullptr;
62 static char ID
; // Pass identification, replacement for typeid
64 AtomicExpand() : FunctionPass(ID
) {
65 initializeAtomicExpandPass(*PassRegistry::getPassRegistry());
68 bool runOnFunction(Function
&F
) override
;
71 bool bracketInstWithFences(Instruction
*I
, AtomicOrdering Order
);
72 IntegerType
*getCorrespondingIntegerType(Type
*T
, const DataLayout
&DL
);
73 LoadInst
*convertAtomicLoadToIntegerType(LoadInst
*LI
);
74 bool tryExpandAtomicLoad(LoadInst
*LI
);
75 bool expandAtomicLoadToLL(LoadInst
*LI
);
76 bool expandAtomicLoadToCmpXchg(LoadInst
*LI
);
77 StoreInst
*convertAtomicStoreToIntegerType(StoreInst
*SI
);
78 bool expandAtomicStore(StoreInst
*SI
);
79 bool tryExpandAtomicRMW(AtomicRMWInst
*AI
);
81 insertRMWLLSCLoop(IRBuilder
<> &Builder
, Type
*ResultTy
, Value
*Addr
,
82 AtomicOrdering MemOpOrder
,
83 function_ref
<Value
*(IRBuilder
<> &, Value
*)> PerformOp
);
84 void expandAtomicOpToLLSC(
85 Instruction
*I
, Type
*ResultTy
, Value
*Addr
, AtomicOrdering MemOpOrder
,
86 function_ref
<Value
*(IRBuilder
<> &, Value
*)> PerformOp
);
87 void expandPartwordAtomicRMW(
89 TargetLoweringBase::AtomicExpansionKind ExpansionKind
);
90 AtomicRMWInst
*widenPartwordAtomicRMW(AtomicRMWInst
*AI
);
91 void expandPartwordCmpXchg(AtomicCmpXchgInst
*I
);
92 void expandAtomicRMWToMaskedIntrinsic(AtomicRMWInst
*AI
);
93 void expandAtomicCmpXchgToMaskedIntrinsic(AtomicCmpXchgInst
*CI
);
95 AtomicCmpXchgInst
*convertCmpXchgToIntegerType(AtomicCmpXchgInst
*CI
);
96 static Value
*insertRMWCmpXchgLoop(
97 IRBuilder
<> &Builder
, Type
*ResultType
, Value
*Addr
,
98 AtomicOrdering MemOpOrder
,
99 function_ref
<Value
*(IRBuilder
<> &, Value
*)> PerformOp
,
100 CreateCmpXchgInstFun CreateCmpXchg
);
101 bool tryExpandAtomicCmpXchg(AtomicCmpXchgInst
*CI
);
103 bool expandAtomicCmpXchg(AtomicCmpXchgInst
*CI
);
104 bool isIdempotentRMW(AtomicRMWInst
*RMWI
);
105 bool simplifyIdempotentRMW(AtomicRMWInst
*RMWI
);
107 bool expandAtomicOpToLibcall(Instruction
*I
, unsigned Size
, unsigned Align
,
108 Value
*PointerOperand
, Value
*ValueOperand
,
109 Value
*CASExpected
, AtomicOrdering Ordering
,
110 AtomicOrdering Ordering2
,
111 ArrayRef
<RTLIB::Libcall
> Libcalls
);
112 void expandAtomicLoadToLibcall(LoadInst
*LI
);
113 void expandAtomicStoreToLibcall(StoreInst
*LI
);
114 void expandAtomicRMWToLibcall(AtomicRMWInst
*I
);
115 void expandAtomicCASToLibcall(AtomicCmpXchgInst
*I
);
118 llvm::expandAtomicRMWToCmpXchg(AtomicRMWInst
*AI
,
119 CreateCmpXchgInstFun CreateCmpXchg
);
122 } // end anonymous namespace
124 char AtomicExpand::ID
= 0;
126 char &llvm::AtomicExpandID
= AtomicExpand::ID
;
128 INITIALIZE_PASS(AtomicExpand
, DEBUG_TYPE
, "Expand Atomic instructions",
131 FunctionPass
*llvm::createAtomicExpandPass() { return new AtomicExpand(); }
133 // Helper functions to retrieve the size of atomic instructions.
134 static unsigned getAtomicOpSize(LoadInst
*LI
) {
135 const DataLayout
&DL
= LI
->getModule()->getDataLayout();
136 return DL
.getTypeStoreSize(LI
->getType());
139 static unsigned getAtomicOpSize(StoreInst
*SI
) {
140 const DataLayout
&DL
= SI
->getModule()->getDataLayout();
141 return DL
.getTypeStoreSize(SI
->getValueOperand()->getType());
144 static unsigned getAtomicOpSize(AtomicRMWInst
*RMWI
) {
145 const DataLayout
&DL
= RMWI
->getModule()->getDataLayout();
146 return DL
.getTypeStoreSize(RMWI
->getValOperand()->getType());
149 static unsigned getAtomicOpSize(AtomicCmpXchgInst
*CASI
) {
150 const DataLayout
&DL
= CASI
->getModule()->getDataLayout();
151 return DL
.getTypeStoreSize(CASI
->getCompareOperand()->getType());
154 // Helper functions to retrieve the alignment of atomic instructions.
155 static unsigned getAtomicOpAlign(LoadInst
*LI
) {
156 unsigned Align
= LI
->getAlignment();
157 // In the future, if this IR restriction is relaxed, we should
158 // return DataLayout::getABITypeAlignment when there's no align
160 assert(Align
!= 0 && "An atomic LoadInst always has an explicit alignment");
164 static unsigned getAtomicOpAlign(StoreInst
*SI
) {
165 unsigned Align
= SI
->getAlignment();
166 // In the future, if this IR restriction is relaxed, we should
167 // return DataLayout::getABITypeAlignment when there's no align
169 assert(Align
!= 0 && "An atomic StoreInst always has an explicit alignment");
173 static unsigned getAtomicOpAlign(AtomicRMWInst
*RMWI
) {
174 // TODO(PR27168): This instruction has no alignment attribute, but unlike the
175 // default alignment for load/store, the default here is to assume
176 // it has NATURAL alignment, not DataLayout-specified alignment.
177 const DataLayout
&DL
= RMWI
->getModule()->getDataLayout();
178 return DL
.getTypeStoreSize(RMWI
->getValOperand()->getType());
181 static unsigned getAtomicOpAlign(AtomicCmpXchgInst
*CASI
) {
182 // TODO(PR27168): same comment as above.
183 const DataLayout
&DL
= CASI
->getModule()->getDataLayout();
184 return DL
.getTypeStoreSize(CASI
->getCompareOperand()->getType());
187 // Determine if a particular atomic operation has a supported size,
188 // and is of appropriate alignment, to be passed through for target
189 // lowering. (Versus turning into a __atomic libcall)
190 template <typename Inst
>
191 static bool atomicSizeSupported(const TargetLowering
*TLI
, Inst
*I
) {
192 unsigned Size
= getAtomicOpSize(I
);
193 unsigned Align
= getAtomicOpAlign(I
);
194 return Align
>= Size
&& Size
<= TLI
->getMaxAtomicSizeInBitsSupported() / 8;
197 bool AtomicExpand::runOnFunction(Function
&F
) {
198 auto *TPC
= getAnalysisIfAvailable
<TargetPassConfig
>();
202 auto &TM
= TPC
->getTM
<TargetMachine
>();
203 if (!TM
.getSubtargetImpl(F
)->enableAtomicExpand())
205 TLI
= TM
.getSubtargetImpl(F
)->getTargetLowering();
207 SmallVector
<Instruction
*, 1> AtomicInsts
;
209 // Changing control-flow while iterating through it is a bad idea, so gather a
210 // list of all atomic instructions before we start.
211 for (inst_iterator II
= inst_begin(F
), E
= inst_end(F
); II
!= E
; ++II
) {
212 Instruction
*I
= &*II
;
213 if (I
->isAtomic() && !isa
<FenceInst
>(I
))
214 AtomicInsts
.push_back(I
);
217 bool MadeChange
= false;
218 for (auto I
: AtomicInsts
) {
219 auto LI
= dyn_cast
<LoadInst
>(I
);
220 auto SI
= dyn_cast
<StoreInst
>(I
);
221 auto RMWI
= dyn_cast
<AtomicRMWInst
>(I
);
222 auto CASI
= dyn_cast
<AtomicCmpXchgInst
>(I
);
223 assert((LI
|| SI
|| RMWI
|| CASI
) && "Unknown atomic instruction");
225 // If the Size/Alignment is not supported, replace with a libcall.
227 if (!atomicSizeSupported(TLI
, LI
)) {
228 expandAtomicLoadToLibcall(LI
);
233 if (!atomicSizeSupported(TLI
, SI
)) {
234 expandAtomicStoreToLibcall(SI
);
239 if (!atomicSizeSupported(TLI
, RMWI
)) {
240 expandAtomicRMWToLibcall(RMWI
);
245 if (!atomicSizeSupported(TLI
, CASI
)) {
246 expandAtomicCASToLibcall(CASI
);
252 if (TLI
->shouldInsertFencesForAtomic(I
)) {
253 auto FenceOrdering
= AtomicOrdering::Monotonic
;
254 if (LI
&& isAcquireOrStronger(LI
->getOrdering())) {
255 FenceOrdering
= LI
->getOrdering();
256 LI
->setOrdering(AtomicOrdering::Monotonic
);
257 } else if (SI
&& isReleaseOrStronger(SI
->getOrdering())) {
258 FenceOrdering
= SI
->getOrdering();
259 SI
->setOrdering(AtomicOrdering::Monotonic
);
260 } else if (RMWI
&& (isReleaseOrStronger(RMWI
->getOrdering()) ||
261 isAcquireOrStronger(RMWI
->getOrdering()))) {
262 FenceOrdering
= RMWI
->getOrdering();
263 RMWI
->setOrdering(AtomicOrdering::Monotonic
);
265 TLI
->shouldExpandAtomicCmpXchgInIR(CASI
) ==
266 TargetLoweringBase::AtomicExpansionKind::None
&&
267 (isReleaseOrStronger(CASI
->getSuccessOrdering()) ||
268 isAcquireOrStronger(CASI
->getSuccessOrdering()))) {
269 // If a compare and swap is lowered to LL/SC, we can do smarter fence
270 // insertion, with a stronger one on the success path than on the
271 // failure path. As a result, fence insertion is directly done by
272 // expandAtomicCmpXchg in that case.
273 FenceOrdering
= CASI
->getSuccessOrdering();
274 CASI
->setSuccessOrdering(AtomicOrdering::Monotonic
);
275 CASI
->setFailureOrdering(AtomicOrdering::Monotonic
);
278 if (FenceOrdering
!= AtomicOrdering::Monotonic
) {
279 MadeChange
|= bracketInstWithFences(I
, FenceOrdering
);
284 if (LI
->getType()->isFloatingPointTy()) {
285 // TODO: add a TLI hook to control this so that each target can
286 // convert to lowering the original type one at a time.
287 LI
= convertAtomicLoadToIntegerType(LI
);
288 assert(LI
->getType()->isIntegerTy() && "invariant broken");
292 MadeChange
|= tryExpandAtomicLoad(LI
);
294 if (SI
->getValueOperand()->getType()->isFloatingPointTy()) {
295 // TODO: add a TLI hook to control this so that each target can
296 // convert to lowering the original type one at a time.
297 SI
= convertAtomicStoreToIntegerType(SI
);
298 assert(SI
->getValueOperand()->getType()->isIntegerTy() &&
303 if (TLI
->shouldExpandAtomicStoreInIR(SI
))
304 MadeChange
|= expandAtomicStore(SI
);
306 // There are two different ways of expanding RMW instructions:
307 // - into a load if it is idempotent
308 // - into a Cmpxchg/LL-SC loop otherwise
309 // we try them in that order.
311 if (isIdempotentRMW(RMWI
) && simplifyIdempotentRMW(RMWI
)) {
314 unsigned MinCASSize
= TLI
->getMinCmpXchgSizeInBits() / 8;
315 unsigned ValueSize
= getAtomicOpSize(RMWI
);
316 AtomicRMWInst::BinOp Op
= RMWI
->getOperation();
317 if (ValueSize
< MinCASSize
&&
318 (Op
== AtomicRMWInst::Or
|| Op
== AtomicRMWInst::Xor
||
319 Op
== AtomicRMWInst::And
)) {
320 RMWI
= widenPartwordAtomicRMW(RMWI
);
324 MadeChange
|= tryExpandAtomicRMW(RMWI
);
327 // TODO: when we're ready to make the change at the IR level, we can
328 // extend convertCmpXchgToInteger for floating point too.
329 assert(!CASI
->getCompareOperand()->getType()->isFloatingPointTy() &&
330 "unimplemented - floating point not legal at IR level");
331 if (CASI
->getCompareOperand()->getType()->isPointerTy() ) {
332 // TODO: add a TLI hook to control this so that each target can
333 // convert to lowering the original type one at a time.
334 CASI
= convertCmpXchgToIntegerType(CASI
);
335 assert(CASI
->getCompareOperand()->getType()->isIntegerTy() &&
340 MadeChange
|= tryExpandAtomicCmpXchg(CASI
);
346 bool AtomicExpand::bracketInstWithFences(Instruction
*I
, AtomicOrdering Order
) {
347 IRBuilder
<> Builder(I
);
349 auto LeadingFence
= TLI
->emitLeadingFence(Builder
, I
, Order
);
351 auto TrailingFence
= TLI
->emitTrailingFence(Builder
, I
, Order
);
352 // We have a guard here because not every atomic operation generates a
355 TrailingFence
->moveAfter(I
);
357 return (LeadingFence
|| TrailingFence
);
360 /// Get the iX type with the same bitwidth as T.
361 IntegerType
*AtomicExpand::getCorrespondingIntegerType(Type
*T
,
362 const DataLayout
&DL
) {
363 EVT VT
= TLI
->getMemValueType(DL
, T
);
364 unsigned BitWidth
= VT
.getStoreSizeInBits();
365 assert(BitWidth
== VT
.getSizeInBits() && "must be a power of two");
366 return IntegerType::get(T
->getContext(), BitWidth
);
369 /// Convert an atomic load of a non-integral type to an integer load of the
370 /// equivalent bitwidth. See the function comment on
371 /// convertAtomicStoreToIntegerType for background.
372 LoadInst
*AtomicExpand::convertAtomicLoadToIntegerType(LoadInst
*LI
) {
373 auto *M
= LI
->getModule();
374 Type
*NewTy
= getCorrespondingIntegerType(LI
->getType(),
377 IRBuilder
<> Builder(LI
);
379 Value
*Addr
= LI
->getPointerOperand();
380 Type
*PT
= PointerType::get(NewTy
,
381 Addr
->getType()->getPointerAddressSpace());
382 Value
*NewAddr
= Builder
.CreateBitCast(Addr
, PT
);
384 auto *NewLI
= Builder
.CreateLoad(NewTy
, NewAddr
);
385 NewLI
->setAlignment(MaybeAlign(LI
->getAlignment()));
386 NewLI
->setVolatile(LI
->isVolatile());
387 NewLI
->setAtomic(LI
->getOrdering(), LI
->getSyncScopeID());
388 LLVM_DEBUG(dbgs() << "Replaced " << *LI
<< " with " << *NewLI
<< "\n");
390 Value
*NewVal
= Builder
.CreateBitCast(NewLI
, LI
->getType());
391 LI
->replaceAllUsesWith(NewVal
);
392 LI
->eraseFromParent();
396 bool AtomicExpand::tryExpandAtomicLoad(LoadInst
*LI
) {
397 switch (TLI
->shouldExpandAtomicLoadInIR(LI
)) {
398 case TargetLoweringBase::AtomicExpansionKind::None
:
400 case TargetLoweringBase::AtomicExpansionKind::LLSC
:
401 expandAtomicOpToLLSC(
402 LI
, LI
->getType(), LI
->getPointerOperand(), LI
->getOrdering(),
403 [](IRBuilder
<> &Builder
, Value
*Loaded
) { return Loaded
; });
405 case TargetLoweringBase::AtomicExpansionKind::LLOnly
:
406 return expandAtomicLoadToLL(LI
);
407 case TargetLoweringBase::AtomicExpansionKind::CmpXChg
:
408 return expandAtomicLoadToCmpXchg(LI
);
410 llvm_unreachable("Unhandled case in tryExpandAtomicLoad");
414 bool AtomicExpand::expandAtomicLoadToLL(LoadInst
*LI
) {
415 IRBuilder
<> Builder(LI
);
417 // On some architectures, load-linked instructions are atomic for larger
418 // sizes than normal loads. For example, the only 64-bit load guaranteed
419 // to be single-copy atomic by ARM is an ldrexd (A3.5.3).
421 TLI
->emitLoadLinked(Builder
, LI
->getPointerOperand(), LI
->getOrdering());
422 TLI
->emitAtomicCmpXchgNoStoreLLBalance(Builder
);
424 LI
->replaceAllUsesWith(Val
);
425 LI
->eraseFromParent();
430 bool AtomicExpand::expandAtomicLoadToCmpXchg(LoadInst
*LI
) {
431 IRBuilder
<> Builder(LI
);
432 AtomicOrdering Order
= LI
->getOrdering();
433 if (Order
== AtomicOrdering::Unordered
)
434 Order
= AtomicOrdering::Monotonic
;
436 Value
*Addr
= LI
->getPointerOperand();
437 Type
*Ty
= cast
<PointerType
>(Addr
->getType())->getElementType();
438 Constant
*DummyVal
= Constant::getNullValue(Ty
);
440 Value
*Pair
= Builder
.CreateAtomicCmpXchg(
441 Addr
, DummyVal
, DummyVal
, Order
,
442 AtomicCmpXchgInst::getStrongestFailureOrdering(Order
));
443 Value
*Loaded
= Builder
.CreateExtractValue(Pair
, 0, "loaded");
445 LI
->replaceAllUsesWith(Loaded
);
446 LI
->eraseFromParent();
451 /// Convert an atomic store of a non-integral type to an integer store of the
452 /// equivalent bitwidth. We used to not support floating point or vector
453 /// atomics in the IR at all. The backends learned to deal with the bitcast
454 /// idiom because that was the only way of expressing the notion of a atomic
455 /// float or vector store. The long term plan is to teach each backend to
456 /// instruction select from the original atomic store, but as a migration
457 /// mechanism, we convert back to the old format which the backends understand.
458 /// Each backend will need individual work to recognize the new format.
459 StoreInst
*AtomicExpand::convertAtomicStoreToIntegerType(StoreInst
*SI
) {
460 IRBuilder
<> Builder(SI
);
461 auto *M
= SI
->getModule();
462 Type
*NewTy
= getCorrespondingIntegerType(SI
->getValueOperand()->getType(),
464 Value
*NewVal
= Builder
.CreateBitCast(SI
->getValueOperand(), NewTy
);
466 Value
*Addr
= SI
->getPointerOperand();
467 Type
*PT
= PointerType::get(NewTy
,
468 Addr
->getType()->getPointerAddressSpace());
469 Value
*NewAddr
= Builder
.CreateBitCast(Addr
, PT
);
471 StoreInst
*NewSI
= Builder
.CreateStore(NewVal
, NewAddr
);
472 NewSI
->setAlignment(MaybeAlign(SI
->getAlignment()));
473 NewSI
->setVolatile(SI
->isVolatile());
474 NewSI
->setAtomic(SI
->getOrdering(), SI
->getSyncScopeID());
475 LLVM_DEBUG(dbgs() << "Replaced " << *SI
<< " with " << *NewSI
<< "\n");
476 SI
->eraseFromParent();
480 bool AtomicExpand::expandAtomicStore(StoreInst
*SI
) {
481 // This function is only called on atomic stores that are too large to be
482 // atomic if implemented as a native store. So we replace them by an
483 // atomic swap, that can be implemented for example as a ldrex/strex on ARM
484 // or lock cmpxchg8/16b on X86, as these are atomic for larger sizes.
485 // It is the responsibility of the target to only signal expansion via
486 // shouldExpandAtomicRMW in cases where this is required and possible.
487 IRBuilder
<> Builder(SI
);
489 Builder
.CreateAtomicRMW(AtomicRMWInst::Xchg
, SI
->getPointerOperand(),
490 SI
->getValueOperand(), SI
->getOrdering());
491 SI
->eraseFromParent();
493 // Now we have an appropriate swap instruction, lower it as usual.
494 return tryExpandAtomicRMW(AI
);
497 static void createCmpXchgInstFun(IRBuilder
<> &Builder
, Value
*Addr
,
498 Value
*Loaded
, Value
*NewVal
,
499 AtomicOrdering MemOpOrder
,
500 Value
*&Success
, Value
*&NewLoaded
) {
501 Type
*OrigTy
= NewVal
->getType();
503 // This code can go away when cmpxchg supports FP types.
504 bool NeedBitcast
= OrigTy
->isFloatingPointTy();
506 IntegerType
*IntTy
= Builder
.getIntNTy(OrigTy
->getPrimitiveSizeInBits());
507 unsigned AS
= Addr
->getType()->getPointerAddressSpace();
508 Addr
= Builder
.CreateBitCast(Addr
, IntTy
->getPointerTo(AS
));
509 NewVal
= Builder
.CreateBitCast(NewVal
, IntTy
);
510 Loaded
= Builder
.CreateBitCast(Loaded
, IntTy
);
513 Value
* Pair
= Builder
.CreateAtomicCmpXchg(
514 Addr
, Loaded
, NewVal
, MemOpOrder
,
515 AtomicCmpXchgInst::getStrongestFailureOrdering(MemOpOrder
));
516 Success
= Builder
.CreateExtractValue(Pair
, 1, "success");
517 NewLoaded
= Builder
.CreateExtractValue(Pair
, 0, "newloaded");
520 NewLoaded
= Builder
.CreateBitCast(NewLoaded
, OrigTy
);
523 /// Emit IR to implement the given atomicrmw operation on values in registers,
524 /// returning the new value.
525 static Value
*performAtomicOp(AtomicRMWInst::BinOp Op
, IRBuilder
<> &Builder
,
526 Value
*Loaded
, Value
*Inc
) {
529 case AtomicRMWInst::Xchg
:
531 case AtomicRMWInst::Add
:
532 return Builder
.CreateAdd(Loaded
, Inc
, "new");
533 case AtomicRMWInst::Sub
:
534 return Builder
.CreateSub(Loaded
, Inc
, "new");
535 case AtomicRMWInst::And
:
536 return Builder
.CreateAnd(Loaded
, Inc
, "new");
537 case AtomicRMWInst::Nand
:
538 return Builder
.CreateNot(Builder
.CreateAnd(Loaded
, Inc
), "new");
539 case AtomicRMWInst::Or
:
540 return Builder
.CreateOr(Loaded
, Inc
, "new");
541 case AtomicRMWInst::Xor
:
542 return Builder
.CreateXor(Loaded
, Inc
, "new");
543 case AtomicRMWInst::Max
:
544 NewVal
= Builder
.CreateICmpSGT(Loaded
, Inc
);
545 return Builder
.CreateSelect(NewVal
, Loaded
, Inc
, "new");
546 case AtomicRMWInst::Min
:
547 NewVal
= Builder
.CreateICmpSLE(Loaded
, Inc
);
548 return Builder
.CreateSelect(NewVal
, Loaded
, Inc
, "new");
549 case AtomicRMWInst::UMax
:
550 NewVal
= Builder
.CreateICmpUGT(Loaded
, Inc
);
551 return Builder
.CreateSelect(NewVal
, Loaded
, Inc
, "new");
552 case AtomicRMWInst::UMin
:
553 NewVal
= Builder
.CreateICmpULE(Loaded
, Inc
);
554 return Builder
.CreateSelect(NewVal
, Loaded
, Inc
, "new");
555 case AtomicRMWInst::FAdd
:
556 return Builder
.CreateFAdd(Loaded
, Inc
, "new");
557 case AtomicRMWInst::FSub
:
558 return Builder
.CreateFSub(Loaded
, Inc
, "new");
560 llvm_unreachable("Unknown atomic op");
564 bool AtomicExpand::tryExpandAtomicRMW(AtomicRMWInst
*AI
) {
565 switch (TLI
->shouldExpandAtomicRMWInIR(AI
)) {
566 case TargetLoweringBase::AtomicExpansionKind::None
:
568 case TargetLoweringBase::AtomicExpansionKind::LLSC
: {
569 unsigned MinCASSize
= TLI
->getMinCmpXchgSizeInBits() / 8;
570 unsigned ValueSize
= getAtomicOpSize(AI
);
571 if (ValueSize
< MinCASSize
) {
573 "MinCmpXchgSizeInBits not yet supported for LL/SC architectures.");
575 auto PerformOp
= [&](IRBuilder
<> &Builder
, Value
*Loaded
) {
576 return performAtomicOp(AI
->getOperation(), Builder
, Loaded
,
577 AI
->getValOperand());
579 expandAtomicOpToLLSC(AI
, AI
->getType(), AI
->getPointerOperand(),
580 AI
->getOrdering(), PerformOp
);
584 case TargetLoweringBase::AtomicExpansionKind::CmpXChg
: {
585 unsigned MinCASSize
= TLI
->getMinCmpXchgSizeInBits() / 8;
586 unsigned ValueSize
= getAtomicOpSize(AI
);
587 if (ValueSize
< MinCASSize
) {
588 // TODO: Handle atomicrmw fadd/fsub
589 if (AI
->getType()->isFloatingPointTy())
592 expandPartwordAtomicRMW(AI
,
593 TargetLoweringBase::AtomicExpansionKind::CmpXChg
);
595 expandAtomicRMWToCmpXchg(AI
, createCmpXchgInstFun
);
599 case TargetLoweringBase::AtomicExpansionKind::MaskedIntrinsic
: {
600 expandAtomicRMWToMaskedIntrinsic(AI
);
604 llvm_unreachable("Unhandled case in tryExpandAtomicRMW");
610 /// Result values from createMaskInstrs helper.
611 struct PartwordMaskValues
{
620 } // end anonymous namespace
622 /// This is a helper function which builds instructions to provide
623 /// values necessary for partword atomic operations. It takes an
624 /// incoming address, Addr, and ValueType, and constructs the address,
625 /// shift-amounts and masks needed to work with a larger value of size
628 /// AlignedAddr: Addr rounded down to a multiple of WordSize
630 /// ShiftAmt: Number of bits to right-shift a WordSize value loaded
631 /// from AlignAddr for it to have the same value as if
632 /// ValueType was loaded from Addr.
634 /// Mask: Value to mask with the value loaded from AlignAddr to
635 /// include only the part that would've been loaded from Addr.
637 /// Inv_Mask: The inverse of Mask.
638 static PartwordMaskValues
createMaskInstrs(IRBuilder
<> &Builder
, Instruction
*I
,
639 Type
*ValueType
, Value
*Addr
,
641 PartwordMaskValues Ret
;
643 BasicBlock
*BB
= I
->getParent();
644 Function
*F
= BB
->getParent();
645 Module
*M
= I
->getModule();
647 LLVMContext
&Ctx
= F
->getContext();
648 const DataLayout
&DL
= M
->getDataLayout();
650 unsigned ValueSize
= DL
.getTypeStoreSize(ValueType
);
652 assert(ValueSize
< WordSize
);
654 Ret
.ValueType
= ValueType
;
655 Ret
.WordType
= Type::getIntNTy(Ctx
, WordSize
* 8);
658 Ret
.WordType
->getPointerTo(Addr
->getType()->getPointerAddressSpace());
660 Value
*AddrInt
= Builder
.CreatePtrToInt(Addr
, DL
.getIntPtrType(Ctx
));
661 Ret
.AlignedAddr
= Builder
.CreateIntToPtr(
662 Builder
.CreateAnd(AddrInt
, ~(uint64_t)(WordSize
- 1)), WordPtrType
,
665 Value
*PtrLSB
= Builder
.CreateAnd(AddrInt
, WordSize
- 1, "PtrLSB");
666 if (DL
.isLittleEndian()) {
667 // turn bytes into bits
668 Ret
.ShiftAmt
= Builder
.CreateShl(PtrLSB
, 3);
670 // turn bytes into bits, and count from the other side.
672 Builder
.CreateShl(Builder
.CreateXor(PtrLSB
, WordSize
- ValueSize
), 3);
675 Ret
.ShiftAmt
= Builder
.CreateTrunc(Ret
.ShiftAmt
, Ret
.WordType
, "ShiftAmt");
676 Ret
.Mask
= Builder
.CreateShl(
677 ConstantInt::get(Ret
.WordType
, (1 << ValueSize
* 8) - 1), Ret
.ShiftAmt
,
679 Ret
.Inv_Mask
= Builder
.CreateNot(Ret
.Mask
, "Inv_Mask");
684 /// Emit IR to implement a masked version of a given atomicrmw
685 /// operation. (That is, only the bits under the Mask should be
686 /// affected by the operation)
687 static Value
*performMaskedAtomicOp(AtomicRMWInst::BinOp Op
,
688 IRBuilder
<> &Builder
, Value
*Loaded
,
689 Value
*Shifted_Inc
, Value
*Inc
,
690 const PartwordMaskValues
&PMV
) {
691 // TODO: update to use
692 // https://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge in order
693 // to merge bits from two values without requiring PMV.Inv_Mask.
695 case AtomicRMWInst::Xchg
: {
696 Value
*Loaded_MaskOut
= Builder
.CreateAnd(Loaded
, PMV
.Inv_Mask
);
697 Value
*FinalVal
= Builder
.CreateOr(Loaded_MaskOut
, Shifted_Inc
);
700 case AtomicRMWInst::Or
:
701 case AtomicRMWInst::Xor
:
702 case AtomicRMWInst::And
:
703 llvm_unreachable("Or/Xor/And handled by widenPartwordAtomicRMW");
704 case AtomicRMWInst::Add
:
705 case AtomicRMWInst::Sub
:
706 case AtomicRMWInst::Nand
: {
707 // The other arithmetic ops need to be masked into place.
708 Value
*NewVal
= performAtomicOp(Op
, Builder
, Loaded
, Shifted_Inc
);
709 Value
*NewVal_Masked
= Builder
.CreateAnd(NewVal
, PMV
.Mask
);
710 Value
*Loaded_MaskOut
= Builder
.CreateAnd(Loaded
, PMV
.Inv_Mask
);
711 Value
*FinalVal
= Builder
.CreateOr(Loaded_MaskOut
, NewVal_Masked
);
714 case AtomicRMWInst::Max
:
715 case AtomicRMWInst::Min
:
716 case AtomicRMWInst::UMax
:
717 case AtomicRMWInst::UMin
: {
718 // Finally, comparison ops will operate on the full value, so
719 // truncate down to the original size, and expand out again after
720 // doing the operation.
721 Value
*Loaded_Shiftdown
= Builder
.CreateTrunc(
722 Builder
.CreateLShr(Loaded
, PMV
.ShiftAmt
), PMV
.ValueType
);
723 Value
*NewVal
= performAtomicOp(Op
, Builder
, Loaded_Shiftdown
, Inc
);
724 Value
*NewVal_Shiftup
= Builder
.CreateShl(
725 Builder
.CreateZExt(NewVal
, PMV
.WordType
), PMV
.ShiftAmt
);
726 Value
*Loaded_MaskOut
= Builder
.CreateAnd(Loaded
, PMV
.Inv_Mask
);
727 Value
*FinalVal
= Builder
.CreateOr(Loaded_MaskOut
, NewVal_Shiftup
);
731 llvm_unreachable("Unknown atomic op");
735 /// Expand a sub-word atomicrmw operation into an appropriate
736 /// word-sized operation.
738 /// It will create an LL/SC or cmpxchg loop, as appropriate, the same
739 /// way as a typical atomicrmw expansion. The only difference here is
740 /// that the operation inside of the loop must operate only upon a
741 /// part of the value.
742 void AtomicExpand::expandPartwordAtomicRMW(
743 AtomicRMWInst
*AI
, TargetLoweringBase::AtomicExpansionKind ExpansionKind
) {
744 assert(ExpansionKind
== TargetLoweringBase::AtomicExpansionKind::CmpXChg
);
746 AtomicOrdering MemOpOrder
= AI
->getOrdering();
748 IRBuilder
<> Builder(AI
);
750 PartwordMaskValues PMV
=
751 createMaskInstrs(Builder
, AI
, AI
->getType(), AI
->getPointerOperand(),
752 TLI
->getMinCmpXchgSizeInBits() / 8);
754 Value
*ValOperand_Shifted
=
755 Builder
.CreateShl(Builder
.CreateZExt(AI
->getValOperand(), PMV
.WordType
),
756 PMV
.ShiftAmt
, "ValOperand_Shifted");
758 auto PerformPartwordOp
= [&](IRBuilder
<> &Builder
, Value
*Loaded
) {
759 return performMaskedAtomicOp(AI
->getOperation(), Builder
, Loaded
,
760 ValOperand_Shifted
, AI
->getValOperand(), PMV
);
763 // TODO: When we're ready to support LLSC conversions too, use
764 // insertRMWLLSCLoop here for ExpansionKind==LLSC.
766 insertRMWCmpXchgLoop(Builder
, PMV
.WordType
, PMV
.AlignedAddr
, MemOpOrder
,
767 PerformPartwordOp
, createCmpXchgInstFun
);
768 Value
*FinalOldResult
= Builder
.CreateTrunc(
769 Builder
.CreateLShr(OldResult
, PMV
.ShiftAmt
), PMV
.ValueType
);
770 AI
->replaceAllUsesWith(FinalOldResult
);
771 AI
->eraseFromParent();
774 // Widen the bitwise atomicrmw (or/xor/and) to the minimum supported width.
775 AtomicRMWInst
*AtomicExpand::widenPartwordAtomicRMW(AtomicRMWInst
*AI
) {
776 IRBuilder
<> Builder(AI
);
777 AtomicRMWInst::BinOp Op
= AI
->getOperation();
779 assert((Op
== AtomicRMWInst::Or
|| Op
== AtomicRMWInst::Xor
||
780 Op
== AtomicRMWInst::And
) &&
781 "Unable to widen operation");
783 PartwordMaskValues PMV
=
784 createMaskInstrs(Builder
, AI
, AI
->getType(), AI
->getPointerOperand(),
785 TLI
->getMinCmpXchgSizeInBits() / 8);
787 Value
*ValOperand_Shifted
=
788 Builder
.CreateShl(Builder
.CreateZExt(AI
->getValOperand(), PMV
.WordType
),
789 PMV
.ShiftAmt
, "ValOperand_Shifted");
793 if (Op
== AtomicRMWInst::And
)
795 Builder
.CreateOr(PMV
.Inv_Mask
, ValOperand_Shifted
, "AndOperand");
797 NewOperand
= ValOperand_Shifted
;
799 AtomicRMWInst
*NewAI
= Builder
.CreateAtomicRMW(Op
, PMV
.AlignedAddr
,
800 NewOperand
, AI
->getOrdering());
802 Value
*FinalOldResult
= Builder
.CreateTrunc(
803 Builder
.CreateLShr(NewAI
, PMV
.ShiftAmt
), PMV
.ValueType
);
804 AI
->replaceAllUsesWith(FinalOldResult
);
805 AI
->eraseFromParent();
809 void AtomicExpand::expandPartwordCmpXchg(AtomicCmpXchgInst
*CI
) {
810 // The basic idea here is that we're expanding a cmpxchg of a
811 // smaller memory size up to a word-sized cmpxchg. To do this, we
812 // need to add a retry-loop for strong cmpxchg, so that
813 // modifications to other parts of the word don't cause a spurious
816 // This generates code like the following:
817 // [[Setup mask values PMV.*]]
818 // %NewVal_Shifted = shl i32 %NewVal, %PMV.ShiftAmt
819 // %Cmp_Shifted = shl i32 %Cmp, %PMV.ShiftAmt
820 // %InitLoaded = load i32* %addr
821 // %InitLoaded_MaskOut = and i32 %InitLoaded, %PMV.Inv_Mask
822 // br partword.cmpxchg.loop
823 // partword.cmpxchg.loop:
824 // %Loaded_MaskOut = phi i32 [ %InitLoaded_MaskOut, %entry ],
825 // [ %OldVal_MaskOut, %partword.cmpxchg.failure ]
826 // %FullWord_NewVal = or i32 %Loaded_MaskOut, %NewVal_Shifted
827 // %FullWord_Cmp = or i32 %Loaded_MaskOut, %Cmp_Shifted
828 // %NewCI = cmpxchg i32* %PMV.AlignedAddr, i32 %FullWord_Cmp,
829 // i32 %FullWord_NewVal success_ordering failure_ordering
830 // %OldVal = extractvalue { i32, i1 } %NewCI, 0
831 // %Success = extractvalue { i32, i1 } %NewCI, 1
832 // br i1 %Success, label %partword.cmpxchg.end,
833 // label %partword.cmpxchg.failure
834 // partword.cmpxchg.failure:
835 // %OldVal_MaskOut = and i32 %OldVal, %PMV.Inv_Mask
836 // %ShouldContinue = icmp ne i32 %Loaded_MaskOut, %OldVal_MaskOut
837 // br i1 %ShouldContinue, label %partword.cmpxchg.loop,
838 // label %partword.cmpxchg.end
839 // partword.cmpxchg.end:
840 // %tmp1 = lshr i32 %OldVal, %PMV.ShiftAmt
841 // %FinalOldVal = trunc i32 %tmp1 to i8
842 // %tmp2 = insertvalue { i8, i1 } undef, i8 %FinalOldVal, 0
843 // %Res = insertvalue { i8, i1 } %25, i1 %Success, 1
845 Value
*Addr
= CI
->getPointerOperand();
846 Value
*Cmp
= CI
->getCompareOperand();
847 Value
*NewVal
= CI
->getNewValOperand();
849 BasicBlock
*BB
= CI
->getParent();
850 Function
*F
= BB
->getParent();
851 IRBuilder
<> Builder(CI
);
852 LLVMContext
&Ctx
= Builder
.getContext();
854 const int WordSize
= TLI
->getMinCmpXchgSizeInBits() / 8;
857 BB
->splitBasicBlock(CI
->getIterator(), "partword.cmpxchg.end");
859 BasicBlock::Create(Ctx
, "partword.cmpxchg.failure", F
, EndBB
);
860 auto LoopBB
= BasicBlock::Create(Ctx
, "partword.cmpxchg.loop", F
, FailureBB
);
862 // The split call above "helpfully" added a branch at the end of BB
863 // (to the wrong place).
864 std::prev(BB
->end())->eraseFromParent();
865 Builder
.SetInsertPoint(BB
);
867 PartwordMaskValues PMV
= createMaskInstrs(
868 Builder
, CI
, CI
->getCompareOperand()->getType(), Addr
, WordSize
);
870 // Shift the incoming values over, into the right location in the word.
871 Value
*NewVal_Shifted
=
872 Builder
.CreateShl(Builder
.CreateZExt(NewVal
, PMV
.WordType
), PMV
.ShiftAmt
);
874 Builder
.CreateShl(Builder
.CreateZExt(Cmp
, PMV
.WordType
), PMV
.ShiftAmt
);
876 // Load the entire current word, and mask into place the expected and new
878 LoadInst
*InitLoaded
= Builder
.CreateLoad(PMV
.WordType
, PMV
.AlignedAddr
);
879 InitLoaded
->setVolatile(CI
->isVolatile());
880 Value
*InitLoaded_MaskOut
= Builder
.CreateAnd(InitLoaded
, PMV
.Inv_Mask
);
881 Builder
.CreateBr(LoopBB
);
883 // partword.cmpxchg.loop:
884 Builder
.SetInsertPoint(LoopBB
);
885 PHINode
*Loaded_MaskOut
= Builder
.CreatePHI(PMV
.WordType
, 2);
886 Loaded_MaskOut
->addIncoming(InitLoaded_MaskOut
, BB
);
888 // Mask/Or the expected and new values into place in the loaded word.
889 Value
*FullWord_NewVal
= Builder
.CreateOr(Loaded_MaskOut
, NewVal_Shifted
);
890 Value
*FullWord_Cmp
= Builder
.CreateOr(Loaded_MaskOut
, Cmp_Shifted
);
891 AtomicCmpXchgInst
*NewCI
= Builder
.CreateAtomicCmpXchg(
892 PMV
.AlignedAddr
, FullWord_Cmp
, FullWord_NewVal
, CI
->getSuccessOrdering(),
893 CI
->getFailureOrdering(), CI
->getSyncScopeID());
894 NewCI
->setVolatile(CI
->isVolatile());
895 // When we're building a strong cmpxchg, we need a loop, so you
896 // might think we could use a weak cmpxchg inside. But, using strong
897 // allows the below comparison for ShouldContinue, and we're
898 // expecting the underlying cmpxchg to be a machine instruction,
899 // which is strong anyways.
900 NewCI
->setWeak(CI
->isWeak());
902 Value
*OldVal
= Builder
.CreateExtractValue(NewCI
, 0);
903 Value
*Success
= Builder
.CreateExtractValue(NewCI
, 1);
906 Builder
.CreateBr(EndBB
);
908 Builder
.CreateCondBr(Success
, EndBB
, FailureBB
);
910 // partword.cmpxchg.failure:
911 Builder
.SetInsertPoint(FailureBB
);
912 // Upon failure, verify that the masked-out part of the loaded value
913 // has been modified. If it didn't, abort the cmpxchg, since the
914 // masked-in part must've.
915 Value
*OldVal_MaskOut
= Builder
.CreateAnd(OldVal
, PMV
.Inv_Mask
);
916 Value
*ShouldContinue
= Builder
.CreateICmpNE(Loaded_MaskOut
, OldVal_MaskOut
);
917 Builder
.CreateCondBr(ShouldContinue
, LoopBB
, EndBB
);
919 // Add the second value to the phi from above
920 Loaded_MaskOut
->addIncoming(OldVal_MaskOut
, FailureBB
);
922 // partword.cmpxchg.end:
923 Builder
.SetInsertPoint(CI
);
925 Value
*FinalOldVal
= Builder
.CreateTrunc(
926 Builder
.CreateLShr(OldVal
, PMV
.ShiftAmt
), PMV
.ValueType
);
927 Value
*Res
= UndefValue::get(CI
->getType());
928 Res
= Builder
.CreateInsertValue(Res
, FinalOldVal
, 0);
929 Res
= Builder
.CreateInsertValue(Res
, Success
, 1);
931 CI
->replaceAllUsesWith(Res
);
932 CI
->eraseFromParent();
935 void AtomicExpand::expandAtomicOpToLLSC(
936 Instruction
*I
, Type
*ResultType
, Value
*Addr
, AtomicOrdering MemOpOrder
,
937 function_ref
<Value
*(IRBuilder
<> &, Value
*)> PerformOp
) {
938 IRBuilder
<> Builder(I
);
940 insertRMWLLSCLoop(Builder
, ResultType
, Addr
, MemOpOrder
, PerformOp
);
942 I
->replaceAllUsesWith(Loaded
);
943 I
->eraseFromParent();
946 void AtomicExpand::expandAtomicRMWToMaskedIntrinsic(AtomicRMWInst
*AI
) {
947 IRBuilder
<> Builder(AI
);
949 PartwordMaskValues PMV
=
950 createMaskInstrs(Builder
, AI
, AI
->getType(), AI
->getPointerOperand(),
951 TLI
->getMinCmpXchgSizeInBits() / 8);
953 // The value operand must be sign-extended for signed min/max so that the
954 // target's signed comparison instructions can be used. Otherwise, just
956 Instruction::CastOps CastOp
= Instruction::ZExt
;
957 AtomicRMWInst::BinOp RMWOp
= AI
->getOperation();
958 if (RMWOp
== AtomicRMWInst::Max
|| RMWOp
== AtomicRMWInst::Min
)
959 CastOp
= Instruction::SExt
;
961 Value
*ValOperand_Shifted
= Builder
.CreateShl(
962 Builder
.CreateCast(CastOp
, AI
->getValOperand(), PMV
.WordType
),
963 PMV
.ShiftAmt
, "ValOperand_Shifted");
964 Value
*OldResult
= TLI
->emitMaskedAtomicRMWIntrinsic(
965 Builder
, AI
, PMV
.AlignedAddr
, ValOperand_Shifted
, PMV
.Mask
, PMV
.ShiftAmt
,
967 Value
*FinalOldResult
= Builder
.CreateTrunc(
968 Builder
.CreateLShr(OldResult
, PMV
.ShiftAmt
), PMV
.ValueType
);
969 AI
->replaceAllUsesWith(FinalOldResult
);
970 AI
->eraseFromParent();
973 void AtomicExpand::expandAtomicCmpXchgToMaskedIntrinsic(AtomicCmpXchgInst
*CI
) {
974 IRBuilder
<> Builder(CI
);
976 PartwordMaskValues PMV
= createMaskInstrs(
977 Builder
, CI
, CI
->getCompareOperand()->getType(), CI
->getPointerOperand(),
978 TLI
->getMinCmpXchgSizeInBits() / 8);
980 Value
*CmpVal_Shifted
= Builder
.CreateShl(
981 Builder
.CreateZExt(CI
->getCompareOperand(), PMV
.WordType
), PMV
.ShiftAmt
,
983 Value
*NewVal_Shifted
= Builder
.CreateShl(
984 Builder
.CreateZExt(CI
->getNewValOperand(), PMV
.WordType
), PMV
.ShiftAmt
,
986 Value
*OldVal
= TLI
->emitMaskedAtomicCmpXchgIntrinsic(
987 Builder
, CI
, PMV
.AlignedAddr
, CmpVal_Shifted
, NewVal_Shifted
, PMV
.Mask
,
988 CI
->getSuccessOrdering());
989 Value
*FinalOldVal
= Builder
.CreateTrunc(
990 Builder
.CreateLShr(OldVal
, PMV
.ShiftAmt
), PMV
.ValueType
);
992 Value
*Res
= UndefValue::get(CI
->getType());
993 Res
= Builder
.CreateInsertValue(Res
, FinalOldVal
, 0);
994 Value
*Success
= Builder
.CreateICmpEQ(
995 CmpVal_Shifted
, Builder
.CreateAnd(OldVal
, PMV
.Mask
), "Success");
996 Res
= Builder
.CreateInsertValue(Res
, Success
, 1);
998 CI
->replaceAllUsesWith(Res
);
999 CI
->eraseFromParent();
1002 Value
*AtomicExpand::insertRMWLLSCLoop(
1003 IRBuilder
<> &Builder
, Type
*ResultTy
, Value
*Addr
,
1004 AtomicOrdering MemOpOrder
,
1005 function_ref
<Value
*(IRBuilder
<> &, Value
*)> PerformOp
) {
1006 LLVMContext
&Ctx
= Builder
.getContext();
1007 BasicBlock
*BB
= Builder
.GetInsertBlock();
1008 Function
*F
= BB
->getParent();
1010 // Given: atomicrmw some_op iN* %addr, iN %incr ordering
1012 // The standard expansion we produce is:
1015 // %loaded = @load.linked(%addr)
1016 // %new = some_op iN %loaded, %incr
1017 // %stored = @store_conditional(%new, %addr)
1018 // %try_again = icmp i32 ne %stored, 0
1019 // br i1 %try_again, label %loop, label %atomicrmw.end
1022 BasicBlock
*ExitBB
=
1023 BB
->splitBasicBlock(Builder
.GetInsertPoint(), "atomicrmw.end");
1024 BasicBlock
*LoopBB
= BasicBlock::Create(Ctx
, "atomicrmw.start", F
, ExitBB
);
1026 // The split call above "helpfully" added a branch at the end of BB (to the
1028 std::prev(BB
->end())->eraseFromParent();
1029 Builder
.SetInsertPoint(BB
);
1030 Builder
.CreateBr(LoopBB
);
1032 // Start the main loop block now that we've taken care of the preliminaries.
1033 Builder
.SetInsertPoint(LoopBB
);
1034 Value
*Loaded
= TLI
->emitLoadLinked(Builder
, Addr
, MemOpOrder
);
1036 Value
*NewVal
= PerformOp(Builder
, Loaded
);
1038 Value
*StoreSuccess
=
1039 TLI
->emitStoreConditional(Builder
, NewVal
, Addr
, MemOpOrder
);
1040 Value
*TryAgain
= Builder
.CreateICmpNE(
1041 StoreSuccess
, ConstantInt::get(IntegerType::get(Ctx
, 32), 0), "tryagain");
1042 Builder
.CreateCondBr(TryAgain
, LoopBB
, ExitBB
);
1044 Builder
.SetInsertPoint(ExitBB
, ExitBB
->begin());
1048 /// Convert an atomic cmpxchg of a non-integral type to an integer cmpxchg of
1049 /// the equivalent bitwidth. We used to not support pointer cmpxchg in the
1050 /// IR. As a migration step, we convert back to what use to be the standard
1051 /// way to represent a pointer cmpxchg so that we can update backends one by
1053 AtomicCmpXchgInst
*AtomicExpand::convertCmpXchgToIntegerType(AtomicCmpXchgInst
*CI
) {
1054 auto *M
= CI
->getModule();
1055 Type
*NewTy
= getCorrespondingIntegerType(CI
->getCompareOperand()->getType(),
1056 M
->getDataLayout());
1058 IRBuilder
<> Builder(CI
);
1060 Value
*Addr
= CI
->getPointerOperand();
1061 Type
*PT
= PointerType::get(NewTy
,
1062 Addr
->getType()->getPointerAddressSpace());
1063 Value
*NewAddr
= Builder
.CreateBitCast(Addr
, PT
);
1065 Value
*NewCmp
= Builder
.CreatePtrToInt(CI
->getCompareOperand(), NewTy
);
1066 Value
*NewNewVal
= Builder
.CreatePtrToInt(CI
->getNewValOperand(), NewTy
);
1069 auto *NewCI
= Builder
.CreateAtomicCmpXchg(NewAddr
, NewCmp
, NewNewVal
,
1070 CI
->getSuccessOrdering(),
1071 CI
->getFailureOrdering(),
1072 CI
->getSyncScopeID());
1073 NewCI
->setVolatile(CI
->isVolatile());
1074 NewCI
->setWeak(CI
->isWeak());
1075 LLVM_DEBUG(dbgs() << "Replaced " << *CI
<< " with " << *NewCI
<< "\n");
1077 Value
*OldVal
= Builder
.CreateExtractValue(NewCI
, 0);
1078 Value
*Succ
= Builder
.CreateExtractValue(NewCI
, 1);
1080 OldVal
= Builder
.CreateIntToPtr(OldVal
, CI
->getCompareOperand()->getType());
1082 Value
*Res
= UndefValue::get(CI
->getType());
1083 Res
= Builder
.CreateInsertValue(Res
, OldVal
, 0);
1084 Res
= Builder
.CreateInsertValue(Res
, Succ
, 1);
1086 CI
->replaceAllUsesWith(Res
);
1087 CI
->eraseFromParent();
1091 bool AtomicExpand::expandAtomicCmpXchg(AtomicCmpXchgInst
*CI
) {
1092 AtomicOrdering SuccessOrder
= CI
->getSuccessOrdering();
1093 AtomicOrdering FailureOrder
= CI
->getFailureOrdering();
1094 Value
*Addr
= CI
->getPointerOperand();
1095 BasicBlock
*BB
= CI
->getParent();
1096 Function
*F
= BB
->getParent();
1097 LLVMContext
&Ctx
= F
->getContext();
1098 // If shouldInsertFencesForAtomic() returns true, then the target does not
1099 // want to deal with memory orders, and emitLeading/TrailingFence should take
1100 // care of everything. Otherwise, emitLeading/TrailingFence are no-op and we
1101 // should preserve the ordering.
1102 bool ShouldInsertFencesForAtomic
= TLI
->shouldInsertFencesForAtomic(CI
);
1103 AtomicOrdering MemOpOrder
=
1104 ShouldInsertFencesForAtomic
? AtomicOrdering::Monotonic
: SuccessOrder
;
1106 // In implementations which use a barrier to achieve release semantics, we can
1107 // delay emitting this barrier until we know a store is actually going to be
1108 // attempted. The cost of this delay is that we need 2 copies of the block
1109 // emitting the load-linked, affecting code size.
1111 // Ideally, this logic would be unconditional except for the minsize check
1112 // since in other cases the extra blocks naturally collapse down to the
1113 // minimal loop. Unfortunately, this puts too much stress on later
1114 // optimisations so we avoid emitting the extra logic in those cases too.
1115 bool HasReleasedLoadBB
= !CI
->isWeak() && ShouldInsertFencesForAtomic
&&
1116 SuccessOrder
!= AtomicOrdering::Monotonic
&&
1117 SuccessOrder
!= AtomicOrdering::Acquire
&&
1120 // There's no overhead for sinking the release barrier in a weak cmpxchg, so
1121 // do it even on minsize.
1122 bool UseUnconditionalReleaseBarrier
= F
->hasMinSize() && !CI
->isWeak();
1124 // Given: cmpxchg some_op iN* %addr, iN %desired, iN %new success_ord fail_ord
1126 // The full expansion we produce is:
1129 // %unreleasedload = @load.linked(%addr)
1130 // %should_store = icmp eq %unreleasedload, %desired
1131 // br i1 %should_store, label %cmpxchg.fencedstore,
1132 // label %cmpxchg.nostore
1133 // cmpxchg.releasingstore:
1135 // br label cmpxchg.trystore
1136 // cmpxchg.trystore:
1137 // %loaded.trystore = phi [%unreleasedload, %releasingstore],
1138 // [%releasedload, %cmpxchg.releasedload]
1139 // %stored = @store_conditional(%new, %addr)
1140 // %success = icmp eq i32 %stored, 0
1141 // br i1 %success, label %cmpxchg.success,
1142 // label %cmpxchg.releasedload/%cmpxchg.failure
1143 // cmpxchg.releasedload:
1144 // %releasedload = @load.linked(%addr)
1145 // %should_store = icmp eq %releasedload, %desired
1146 // br i1 %should_store, label %cmpxchg.trystore,
1147 // label %cmpxchg.failure
1150 // br label %cmpxchg.end
1152 // %loaded.nostore = phi [%unreleasedload, %cmpxchg.start],
1154 // %cmpxchg.releasedload/%cmpxchg.trystore]
1155 // @load_linked_fail_balance()?
1156 // br label %cmpxchg.failure
1159 // br label %cmpxchg.end
1161 // %loaded = phi [%loaded.nostore, %cmpxchg.failure],
1162 // [%loaded.trystore, %cmpxchg.trystore]
1163 // %success = phi i1 [true, %cmpxchg.success], [false, %cmpxchg.failure]
1164 // %restmp = insertvalue { iN, i1 } undef, iN %loaded, 0
1165 // %res = insertvalue { iN, i1 } %restmp, i1 %success, 1
1167 BasicBlock
*ExitBB
= BB
->splitBasicBlock(CI
->getIterator(), "cmpxchg.end");
1168 auto FailureBB
= BasicBlock::Create(Ctx
, "cmpxchg.failure", F
, ExitBB
);
1169 auto NoStoreBB
= BasicBlock::Create(Ctx
, "cmpxchg.nostore", F
, FailureBB
);
1170 auto SuccessBB
= BasicBlock::Create(Ctx
, "cmpxchg.success", F
, NoStoreBB
);
1171 auto ReleasedLoadBB
=
1172 BasicBlock::Create(Ctx
, "cmpxchg.releasedload", F
, SuccessBB
);
1174 BasicBlock::Create(Ctx
, "cmpxchg.trystore", F
, ReleasedLoadBB
);
1175 auto ReleasingStoreBB
=
1176 BasicBlock::Create(Ctx
, "cmpxchg.fencedstore", F
, TryStoreBB
);
1177 auto StartBB
= BasicBlock::Create(Ctx
, "cmpxchg.start", F
, ReleasingStoreBB
);
1179 // This grabs the DebugLoc from CI
1180 IRBuilder
<> Builder(CI
);
1182 // The split call above "helpfully" added a branch at the end of BB (to the
1183 // wrong place), but we might want a fence too. It's easiest to just remove
1184 // the branch entirely.
1185 std::prev(BB
->end())->eraseFromParent();
1186 Builder
.SetInsertPoint(BB
);
1187 if (ShouldInsertFencesForAtomic
&& UseUnconditionalReleaseBarrier
)
1188 TLI
->emitLeadingFence(Builder
, CI
, SuccessOrder
);
1189 Builder
.CreateBr(StartBB
);
1191 // Start the main loop block now that we've taken care of the preliminaries.
1192 Builder
.SetInsertPoint(StartBB
);
1193 Value
*UnreleasedLoad
= TLI
->emitLoadLinked(Builder
, Addr
, MemOpOrder
);
1194 Value
*ShouldStore
= Builder
.CreateICmpEQ(
1195 UnreleasedLoad
, CI
->getCompareOperand(), "should_store");
1197 // If the cmpxchg doesn't actually need any ordering when it fails, we can
1198 // jump straight past that fence instruction (if it exists).
1199 Builder
.CreateCondBr(ShouldStore
, ReleasingStoreBB
, NoStoreBB
);
1201 Builder
.SetInsertPoint(ReleasingStoreBB
);
1202 if (ShouldInsertFencesForAtomic
&& !UseUnconditionalReleaseBarrier
)
1203 TLI
->emitLeadingFence(Builder
, CI
, SuccessOrder
);
1204 Builder
.CreateBr(TryStoreBB
);
1206 Builder
.SetInsertPoint(TryStoreBB
);
1207 Value
*StoreSuccess
= TLI
->emitStoreConditional(
1208 Builder
, CI
->getNewValOperand(), Addr
, MemOpOrder
);
1209 StoreSuccess
= Builder
.CreateICmpEQ(
1210 StoreSuccess
, ConstantInt::get(Type::getInt32Ty(Ctx
), 0), "success");
1211 BasicBlock
*RetryBB
= HasReleasedLoadBB
? ReleasedLoadBB
: StartBB
;
1212 Builder
.CreateCondBr(StoreSuccess
, SuccessBB
,
1213 CI
->isWeak() ? FailureBB
: RetryBB
);
1215 Builder
.SetInsertPoint(ReleasedLoadBB
);
1217 if (HasReleasedLoadBB
) {
1218 SecondLoad
= TLI
->emitLoadLinked(Builder
, Addr
, MemOpOrder
);
1219 ShouldStore
= Builder
.CreateICmpEQ(SecondLoad
, CI
->getCompareOperand(),
1222 // If the cmpxchg doesn't actually need any ordering when it fails, we can
1223 // jump straight past that fence instruction (if it exists).
1224 Builder
.CreateCondBr(ShouldStore
, TryStoreBB
, NoStoreBB
);
1226 Builder
.CreateUnreachable();
1228 // Make sure later instructions don't get reordered with a fence if
1230 Builder
.SetInsertPoint(SuccessBB
);
1231 if (ShouldInsertFencesForAtomic
)
1232 TLI
->emitTrailingFence(Builder
, CI
, SuccessOrder
);
1233 Builder
.CreateBr(ExitBB
);
1235 Builder
.SetInsertPoint(NoStoreBB
);
1236 // In the failing case, where we don't execute the store-conditional, the
1237 // target might want to balance out the load-linked with a dedicated
1238 // instruction (e.g., on ARM, clearing the exclusive monitor).
1239 TLI
->emitAtomicCmpXchgNoStoreLLBalance(Builder
);
1240 Builder
.CreateBr(FailureBB
);
1242 Builder
.SetInsertPoint(FailureBB
);
1243 if (ShouldInsertFencesForAtomic
)
1244 TLI
->emitTrailingFence(Builder
, CI
, FailureOrder
);
1245 Builder
.CreateBr(ExitBB
);
1247 // Finally, we have control-flow based knowledge of whether the cmpxchg
1248 // succeeded or not. We expose this to later passes by converting any
1249 // subsequent "icmp eq/ne %loaded, %oldval" into a use of an appropriate
1251 Builder
.SetInsertPoint(ExitBB
, ExitBB
->begin());
1252 PHINode
*Success
= Builder
.CreatePHI(Type::getInt1Ty(Ctx
), 2);
1253 Success
->addIncoming(ConstantInt::getTrue(Ctx
), SuccessBB
);
1254 Success
->addIncoming(ConstantInt::getFalse(Ctx
), FailureBB
);
1256 // Setup the builder so we can create any PHIs we need.
1258 if (!HasReleasedLoadBB
)
1259 Loaded
= UnreleasedLoad
;
1261 Builder
.SetInsertPoint(TryStoreBB
, TryStoreBB
->begin());
1262 PHINode
*TryStoreLoaded
= Builder
.CreatePHI(UnreleasedLoad
->getType(), 2);
1263 TryStoreLoaded
->addIncoming(UnreleasedLoad
, ReleasingStoreBB
);
1264 TryStoreLoaded
->addIncoming(SecondLoad
, ReleasedLoadBB
);
1266 Builder
.SetInsertPoint(NoStoreBB
, NoStoreBB
->begin());
1267 PHINode
*NoStoreLoaded
= Builder
.CreatePHI(UnreleasedLoad
->getType(), 2);
1268 NoStoreLoaded
->addIncoming(UnreleasedLoad
, StartBB
);
1269 NoStoreLoaded
->addIncoming(SecondLoad
, ReleasedLoadBB
);
1271 Builder
.SetInsertPoint(ExitBB
, ++ExitBB
->begin());
1272 PHINode
*ExitLoaded
= Builder
.CreatePHI(UnreleasedLoad
->getType(), 2);
1273 ExitLoaded
->addIncoming(TryStoreLoaded
, SuccessBB
);
1274 ExitLoaded
->addIncoming(NoStoreLoaded
, FailureBB
);
1276 Loaded
= ExitLoaded
;
1279 // Look for any users of the cmpxchg that are just comparing the loaded value
1280 // against the desired one, and replace them with the CFG-derived version.
1281 SmallVector
<ExtractValueInst
*, 2> PrunedInsts
;
1282 for (auto User
: CI
->users()) {
1283 ExtractValueInst
*EV
= dyn_cast
<ExtractValueInst
>(User
);
1287 assert(EV
->getNumIndices() == 1 && EV
->getIndices()[0] <= 1 &&
1288 "weird extraction from { iN, i1 }");
1290 if (EV
->getIndices()[0] == 0)
1291 EV
->replaceAllUsesWith(Loaded
);
1293 EV
->replaceAllUsesWith(Success
);
1295 PrunedInsts
.push_back(EV
);
1298 // We can remove the instructions now we're no longer iterating through them.
1299 for (auto EV
: PrunedInsts
)
1300 EV
->eraseFromParent();
1302 if (!CI
->use_empty()) {
1303 // Some use of the full struct return that we don't understand has happened,
1304 // so we've got to reconstruct it properly.
1306 Res
= Builder
.CreateInsertValue(UndefValue::get(CI
->getType()), Loaded
, 0);
1307 Res
= Builder
.CreateInsertValue(Res
, Success
, 1);
1309 CI
->replaceAllUsesWith(Res
);
1312 CI
->eraseFromParent();
1316 bool AtomicExpand::isIdempotentRMW(AtomicRMWInst
* RMWI
) {
1317 auto C
= dyn_cast
<ConstantInt
>(RMWI
->getValOperand());
1321 AtomicRMWInst::BinOp Op
= RMWI
->getOperation();
1323 case AtomicRMWInst::Add
:
1324 case AtomicRMWInst::Sub
:
1325 case AtomicRMWInst::Or
:
1326 case AtomicRMWInst::Xor
:
1328 case AtomicRMWInst::And
:
1329 return C
->isMinusOne();
1330 // FIXME: we could also treat Min/Max/UMin/UMax by the INT_MIN/INT_MAX/...
1336 bool AtomicExpand::simplifyIdempotentRMW(AtomicRMWInst
* RMWI
) {
1337 if (auto ResultingLoad
= TLI
->lowerIdempotentRMWIntoFencedLoad(RMWI
)) {
1338 tryExpandAtomicLoad(ResultingLoad
);
1344 Value
*AtomicExpand::insertRMWCmpXchgLoop(
1345 IRBuilder
<> &Builder
, Type
*ResultTy
, Value
*Addr
,
1346 AtomicOrdering MemOpOrder
,
1347 function_ref
<Value
*(IRBuilder
<> &, Value
*)> PerformOp
,
1348 CreateCmpXchgInstFun CreateCmpXchg
) {
1349 LLVMContext
&Ctx
= Builder
.getContext();
1350 BasicBlock
*BB
= Builder
.GetInsertBlock();
1351 Function
*F
= BB
->getParent();
1353 // Given: atomicrmw some_op iN* %addr, iN %incr ordering
1355 // The standard expansion we produce is:
1357 // %init_loaded = load atomic iN* %addr
1360 // %loaded = phi iN [ %init_loaded, %entry ], [ %new_loaded, %loop ]
1361 // %new = some_op iN %loaded, %incr
1362 // %pair = cmpxchg iN* %addr, iN %loaded, iN %new
1363 // %new_loaded = extractvalue { iN, i1 } %pair, 0
1364 // %success = extractvalue { iN, i1 } %pair, 1
1365 // br i1 %success, label %atomicrmw.end, label %loop
1368 BasicBlock
*ExitBB
=
1369 BB
->splitBasicBlock(Builder
.GetInsertPoint(), "atomicrmw.end");
1370 BasicBlock
*LoopBB
= BasicBlock::Create(Ctx
, "atomicrmw.start", F
, ExitBB
);
1372 // The split call above "helpfully" added a branch at the end of BB (to the
1373 // wrong place), but we want a load. It's easiest to just remove
1374 // the branch entirely.
1375 std::prev(BB
->end())->eraseFromParent();
1376 Builder
.SetInsertPoint(BB
);
1377 LoadInst
*InitLoaded
= Builder
.CreateLoad(ResultTy
, Addr
);
1378 // Atomics require at least natural alignment.
1379 InitLoaded
->setAlignment(MaybeAlign(ResultTy
->getPrimitiveSizeInBits() / 8));
1380 Builder
.CreateBr(LoopBB
);
1382 // Start the main loop block now that we've taken care of the preliminaries.
1383 Builder
.SetInsertPoint(LoopBB
);
1384 PHINode
*Loaded
= Builder
.CreatePHI(ResultTy
, 2, "loaded");
1385 Loaded
->addIncoming(InitLoaded
, BB
);
1387 Value
*NewVal
= PerformOp(Builder
, Loaded
);
1389 Value
*NewLoaded
= nullptr;
1390 Value
*Success
= nullptr;
1392 CreateCmpXchg(Builder
, Addr
, Loaded
, NewVal
,
1393 MemOpOrder
== AtomicOrdering::Unordered
1394 ? AtomicOrdering::Monotonic
1396 Success
, NewLoaded
);
1397 assert(Success
&& NewLoaded
);
1399 Loaded
->addIncoming(NewLoaded
, LoopBB
);
1401 Builder
.CreateCondBr(Success
, ExitBB
, LoopBB
);
1403 Builder
.SetInsertPoint(ExitBB
, ExitBB
->begin());
1407 bool AtomicExpand::tryExpandAtomicCmpXchg(AtomicCmpXchgInst
*CI
) {
1408 unsigned MinCASSize
= TLI
->getMinCmpXchgSizeInBits() / 8;
1409 unsigned ValueSize
= getAtomicOpSize(CI
);
1411 switch (TLI
->shouldExpandAtomicCmpXchgInIR(CI
)) {
1413 llvm_unreachable("Unhandled case in tryExpandAtomicCmpXchg");
1414 case TargetLoweringBase::AtomicExpansionKind::None
:
1415 if (ValueSize
< MinCASSize
)
1416 expandPartwordCmpXchg(CI
);
1418 case TargetLoweringBase::AtomicExpansionKind::LLSC
: {
1419 assert(ValueSize
>= MinCASSize
&&
1420 "MinCmpXchgSizeInBits not yet supported for LL/SC expansions.");
1421 return expandAtomicCmpXchg(CI
);
1423 case TargetLoweringBase::AtomicExpansionKind::MaskedIntrinsic
:
1424 expandAtomicCmpXchgToMaskedIntrinsic(CI
);
1429 // Note: This function is exposed externally by AtomicExpandUtils.h
1430 bool llvm::expandAtomicRMWToCmpXchg(AtomicRMWInst
*AI
,
1431 CreateCmpXchgInstFun CreateCmpXchg
) {
1432 IRBuilder
<> Builder(AI
);
1433 Value
*Loaded
= AtomicExpand::insertRMWCmpXchgLoop(
1434 Builder
, AI
->getType(), AI
->getPointerOperand(), AI
->getOrdering(),
1435 [&](IRBuilder
<> &Builder
, Value
*Loaded
) {
1436 return performAtomicOp(AI
->getOperation(), Builder
, Loaded
,
1437 AI
->getValOperand());
1441 AI
->replaceAllUsesWith(Loaded
);
1442 AI
->eraseFromParent();
1446 // In order to use one of the sized library calls such as
1447 // __atomic_fetch_add_4, the alignment must be sufficient, the size
1448 // must be one of the potentially-specialized sizes, and the value
1449 // type must actually exist in C on the target (otherwise, the
1450 // function wouldn't actually be defined.)
1451 static bool canUseSizedAtomicCall(unsigned Size
, unsigned Align
,
1452 const DataLayout
&DL
) {
1453 // TODO: "LargestSize" is an approximation for "largest type that
1454 // you can express in C". It seems to be the case that int128 is
1455 // supported on all 64-bit platforms, otherwise only up to 64-bit
1456 // integers are supported. If we get this wrong, then we'll try to
1457 // call a sized libcall that doesn't actually exist. There should
1458 // really be some more reliable way in LLVM of determining integer
1459 // sizes which are valid in the target's C ABI...
1460 unsigned LargestSize
= DL
.getLargestLegalIntTypeSizeInBits() >= 64 ? 16 : 8;
1461 return Align
>= Size
&&
1462 (Size
== 1 || Size
== 2 || Size
== 4 || Size
== 8 || Size
== 16) &&
1463 Size
<= LargestSize
;
1466 void AtomicExpand::expandAtomicLoadToLibcall(LoadInst
*I
) {
1467 static const RTLIB::Libcall Libcalls
[6] = {
1468 RTLIB::ATOMIC_LOAD
, RTLIB::ATOMIC_LOAD_1
, RTLIB::ATOMIC_LOAD_2
,
1469 RTLIB::ATOMIC_LOAD_4
, RTLIB::ATOMIC_LOAD_8
, RTLIB::ATOMIC_LOAD_16
};
1470 unsigned Size
= getAtomicOpSize(I
);
1471 unsigned Align
= getAtomicOpAlign(I
);
1473 bool expanded
= expandAtomicOpToLibcall(
1474 I
, Size
, Align
, I
->getPointerOperand(), nullptr, nullptr,
1475 I
->getOrdering(), AtomicOrdering::NotAtomic
, Libcalls
);
1477 assert(expanded
&& "expandAtomicOpToLibcall shouldn't fail tor Load");
1480 void AtomicExpand::expandAtomicStoreToLibcall(StoreInst
*I
) {
1481 static const RTLIB::Libcall Libcalls
[6] = {
1482 RTLIB::ATOMIC_STORE
, RTLIB::ATOMIC_STORE_1
, RTLIB::ATOMIC_STORE_2
,
1483 RTLIB::ATOMIC_STORE_4
, RTLIB::ATOMIC_STORE_8
, RTLIB::ATOMIC_STORE_16
};
1484 unsigned Size
= getAtomicOpSize(I
);
1485 unsigned Align
= getAtomicOpAlign(I
);
1487 bool expanded
= expandAtomicOpToLibcall(
1488 I
, Size
, Align
, I
->getPointerOperand(), I
->getValueOperand(), nullptr,
1489 I
->getOrdering(), AtomicOrdering::NotAtomic
, Libcalls
);
1491 assert(expanded
&& "expandAtomicOpToLibcall shouldn't fail tor Store");
1494 void AtomicExpand::expandAtomicCASToLibcall(AtomicCmpXchgInst
*I
) {
1495 static const RTLIB::Libcall Libcalls
[6] = {
1496 RTLIB::ATOMIC_COMPARE_EXCHANGE
, RTLIB::ATOMIC_COMPARE_EXCHANGE_1
,
1497 RTLIB::ATOMIC_COMPARE_EXCHANGE_2
, RTLIB::ATOMIC_COMPARE_EXCHANGE_4
,
1498 RTLIB::ATOMIC_COMPARE_EXCHANGE_8
, RTLIB::ATOMIC_COMPARE_EXCHANGE_16
};
1499 unsigned Size
= getAtomicOpSize(I
);
1500 unsigned Align
= getAtomicOpAlign(I
);
1502 bool expanded
= expandAtomicOpToLibcall(
1503 I
, Size
, Align
, I
->getPointerOperand(), I
->getNewValOperand(),
1504 I
->getCompareOperand(), I
->getSuccessOrdering(), I
->getFailureOrdering(),
1507 assert(expanded
&& "expandAtomicOpToLibcall shouldn't fail tor CAS");
1510 static ArrayRef
<RTLIB::Libcall
> GetRMWLibcall(AtomicRMWInst::BinOp Op
) {
1511 static const RTLIB::Libcall LibcallsXchg
[6] = {
1512 RTLIB::ATOMIC_EXCHANGE
, RTLIB::ATOMIC_EXCHANGE_1
,
1513 RTLIB::ATOMIC_EXCHANGE_2
, RTLIB::ATOMIC_EXCHANGE_4
,
1514 RTLIB::ATOMIC_EXCHANGE_8
, RTLIB::ATOMIC_EXCHANGE_16
};
1515 static const RTLIB::Libcall LibcallsAdd
[6] = {
1516 RTLIB::UNKNOWN_LIBCALL
, RTLIB::ATOMIC_FETCH_ADD_1
,
1517 RTLIB::ATOMIC_FETCH_ADD_2
, RTLIB::ATOMIC_FETCH_ADD_4
,
1518 RTLIB::ATOMIC_FETCH_ADD_8
, RTLIB::ATOMIC_FETCH_ADD_16
};
1519 static const RTLIB::Libcall LibcallsSub
[6] = {
1520 RTLIB::UNKNOWN_LIBCALL
, RTLIB::ATOMIC_FETCH_SUB_1
,
1521 RTLIB::ATOMIC_FETCH_SUB_2
, RTLIB::ATOMIC_FETCH_SUB_4
,
1522 RTLIB::ATOMIC_FETCH_SUB_8
, RTLIB::ATOMIC_FETCH_SUB_16
};
1523 static const RTLIB::Libcall LibcallsAnd
[6] = {
1524 RTLIB::UNKNOWN_LIBCALL
, RTLIB::ATOMIC_FETCH_AND_1
,
1525 RTLIB::ATOMIC_FETCH_AND_2
, RTLIB::ATOMIC_FETCH_AND_4
,
1526 RTLIB::ATOMIC_FETCH_AND_8
, RTLIB::ATOMIC_FETCH_AND_16
};
1527 static const RTLIB::Libcall LibcallsOr
[6] = {
1528 RTLIB::UNKNOWN_LIBCALL
, RTLIB::ATOMIC_FETCH_OR_1
,
1529 RTLIB::ATOMIC_FETCH_OR_2
, RTLIB::ATOMIC_FETCH_OR_4
,
1530 RTLIB::ATOMIC_FETCH_OR_8
, RTLIB::ATOMIC_FETCH_OR_16
};
1531 static const RTLIB::Libcall LibcallsXor
[6] = {
1532 RTLIB::UNKNOWN_LIBCALL
, RTLIB::ATOMIC_FETCH_XOR_1
,
1533 RTLIB::ATOMIC_FETCH_XOR_2
, RTLIB::ATOMIC_FETCH_XOR_4
,
1534 RTLIB::ATOMIC_FETCH_XOR_8
, RTLIB::ATOMIC_FETCH_XOR_16
};
1535 static const RTLIB::Libcall LibcallsNand
[6] = {
1536 RTLIB::UNKNOWN_LIBCALL
, RTLIB::ATOMIC_FETCH_NAND_1
,
1537 RTLIB::ATOMIC_FETCH_NAND_2
, RTLIB::ATOMIC_FETCH_NAND_4
,
1538 RTLIB::ATOMIC_FETCH_NAND_8
, RTLIB::ATOMIC_FETCH_NAND_16
};
1541 case AtomicRMWInst::BAD_BINOP
:
1542 llvm_unreachable("Should not have BAD_BINOP.");
1543 case AtomicRMWInst::Xchg
:
1544 return makeArrayRef(LibcallsXchg
);
1545 case AtomicRMWInst::Add
:
1546 return makeArrayRef(LibcallsAdd
);
1547 case AtomicRMWInst::Sub
:
1548 return makeArrayRef(LibcallsSub
);
1549 case AtomicRMWInst::And
:
1550 return makeArrayRef(LibcallsAnd
);
1551 case AtomicRMWInst::Or
:
1552 return makeArrayRef(LibcallsOr
);
1553 case AtomicRMWInst::Xor
:
1554 return makeArrayRef(LibcallsXor
);
1555 case AtomicRMWInst::Nand
:
1556 return makeArrayRef(LibcallsNand
);
1557 case AtomicRMWInst::Max
:
1558 case AtomicRMWInst::Min
:
1559 case AtomicRMWInst::UMax
:
1560 case AtomicRMWInst::UMin
:
1561 case AtomicRMWInst::FAdd
:
1562 case AtomicRMWInst::FSub
:
1563 // No atomic libcalls are available for max/min/umax/umin.
1566 llvm_unreachable("Unexpected AtomicRMW operation.");
1569 void AtomicExpand::expandAtomicRMWToLibcall(AtomicRMWInst
*I
) {
1570 ArrayRef
<RTLIB::Libcall
> Libcalls
= GetRMWLibcall(I
->getOperation());
1572 unsigned Size
= getAtomicOpSize(I
);
1573 unsigned Align
= getAtomicOpAlign(I
);
1575 bool Success
= false;
1576 if (!Libcalls
.empty())
1577 Success
= expandAtomicOpToLibcall(
1578 I
, Size
, Align
, I
->getPointerOperand(), I
->getValOperand(), nullptr,
1579 I
->getOrdering(), AtomicOrdering::NotAtomic
, Libcalls
);
1581 // The expansion failed: either there were no libcalls at all for
1582 // the operation (min/max), or there were only size-specialized
1583 // libcalls (add/sub/etc) and we needed a generic. So, expand to a
1584 // CAS libcall, via a CAS loop, instead.
1586 expandAtomicRMWToCmpXchg(I
, [this](IRBuilder
<> &Builder
, Value
*Addr
,
1587 Value
*Loaded
, Value
*NewVal
,
1588 AtomicOrdering MemOpOrder
,
1589 Value
*&Success
, Value
*&NewLoaded
) {
1590 // Create the CAS instruction normally...
1591 AtomicCmpXchgInst
*Pair
= Builder
.CreateAtomicCmpXchg(
1592 Addr
, Loaded
, NewVal
, MemOpOrder
,
1593 AtomicCmpXchgInst::getStrongestFailureOrdering(MemOpOrder
));
1594 Success
= Builder
.CreateExtractValue(Pair
, 1, "success");
1595 NewLoaded
= Builder
.CreateExtractValue(Pair
, 0, "newloaded");
1597 // ...and then expand the CAS into a libcall.
1598 expandAtomicCASToLibcall(Pair
);
1603 // A helper routine for the above expandAtomic*ToLibcall functions.
1605 // 'Libcalls' contains an array of enum values for the particular
1606 // ATOMIC libcalls to be emitted. All of the other arguments besides
1607 // 'I' are extracted from the Instruction subclass by the
1608 // caller. Depending on the particular call, some will be null.
1609 bool AtomicExpand::expandAtomicOpToLibcall(
1610 Instruction
*I
, unsigned Size
, unsigned Align
, Value
*PointerOperand
,
1611 Value
*ValueOperand
, Value
*CASExpected
, AtomicOrdering Ordering
,
1612 AtomicOrdering Ordering2
, ArrayRef
<RTLIB::Libcall
> Libcalls
) {
1613 assert(Libcalls
.size() == 6);
1615 LLVMContext
&Ctx
= I
->getContext();
1616 Module
*M
= I
->getModule();
1617 const DataLayout
&DL
= M
->getDataLayout();
1618 IRBuilder
<> Builder(I
);
1619 IRBuilder
<> AllocaBuilder(&I
->getFunction()->getEntryBlock().front());
1621 bool UseSizedLibcall
= canUseSizedAtomicCall(Size
, Align
, DL
);
1622 Type
*SizedIntTy
= Type::getIntNTy(Ctx
, Size
* 8);
1624 unsigned AllocaAlignment
= DL
.getPrefTypeAlignment(SizedIntTy
);
1626 // TODO: the "order" argument type is "int", not int32. So
1627 // getInt32Ty may be wrong if the arch uses e.g. 16-bit ints.
1628 ConstantInt
*SizeVal64
= ConstantInt::get(Type::getInt64Ty(Ctx
), Size
);
1629 assert(Ordering
!= AtomicOrdering::NotAtomic
&& "expect atomic MO");
1630 Constant
*OrderingVal
=
1631 ConstantInt::get(Type::getInt32Ty(Ctx
), (int)toCABI(Ordering
));
1632 Constant
*Ordering2Val
= nullptr;
1634 assert(Ordering2
!= AtomicOrdering::NotAtomic
&& "expect atomic MO");
1636 ConstantInt::get(Type::getInt32Ty(Ctx
), (int)toCABI(Ordering2
));
1638 bool HasResult
= I
->getType() != Type::getVoidTy(Ctx
);
1640 RTLIB::Libcall RTLibType
;
1641 if (UseSizedLibcall
) {
1643 case 1: RTLibType
= Libcalls
[1]; break;
1644 case 2: RTLibType
= Libcalls
[2]; break;
1645 case 4: RTLibType
= Libcalls
[3]; break;
1646 case 8: RTLibType
= Libcalls
[4]; break;
1647 case 16: RTLibType
= Libcalls
[5]; break;
1649 } else if (Libcalls
[0] != RTLIB::UNKNOWN_LIBCALL
) {
1650 RTLibType
= Libcalls
[0];
1652 // Can't use sized function, and there's no generic for this
1653 // operation, so give up.
1657 // Build up the function call. There's two kinds. First, the sized
1658 // variants. These calls are going to be one of the following (with
1660 // iN __atomic_load_N(iN *ptr, int ordering)
1661 // void __atomic_store_N(iN *ptr, iN val, int ordering)
1662 // iN __atomic_{exchange|fetch_*}_N(iN *ptr, iN val, int ordering)
1663 // bool __atomic_compare_exchange_N(iN *ptr, iN *expected, iN desired,
1664 // int success_order, int failure_order)
1666 // Note that these functions can be used for non-integer atomic
1667 // operations, the values just need to be bitcast to integers on the
1670 // And, then, the generic variants. They look like the following:
1671 // void __atomic_load(size_t size, void *ptr, void *ret, int ordering)
1672 // void __atomic_store(size_t size, void *ptr, void *val, int ordering)
1673 // void __atomic_exchange(size_t size, void *ptr, void *val, void *ret,
1675 // bool __atomic_compare_exchange(size_t size, void *ptr, void *expected,
1676 // void *desired, int success_order,
1677 // int failure_order)
1679 // The different signatures are built up depending on the
1680 // 'UseSizedLibcall', 'CASExpected', 'ValueOperand', and 'HasResult'
1683 AllocaInst
*AllocaCASExpected
= nullptr;
1684 Value
*AllocaCASExpected_i8
= nullptr;
1685 AllocaInst
*AllocaValue
= nullptr;
1686 Value
*AllocaValue_i8
= nullptr;
1687 AllocaInst
*AllocaResult
= nullptr;
1688 Value
*AllocaResult_i8
= nullptr;
1691 SmallVector
<Value
*, 6> Args
;
1695 if (!UseSizedLibcall
) {
1696 // Note, getIntPtrType is assumed equivalent to size_t.
1697 Args
.push_back(ConstantInt::get(DL
.getIntPtrType(Ctx
), Size
));
1701 // note: This assumes all address spaces share a common libfunc
1702 // implementation and that addresses are convertable. For systems without
1703 // that property, we'd need to extend this mechanism to support AS-specific
1704 // families of atomic intrinsics.
1705 auto PtrTypeAS
= PointerOperand
->getType()->getPointerAddressSpace();
1706 Value
*PtrVal
= Builder
.CreateBitCast(PointerOperand
,
1707 Type::getInt8PtrTy(Ctx
, PtrTypeAS
));
1708 PtrVal
= Builder
.CreateAddrSpaceCast(PtrVal
, Type::getInt8PtrTy(Ctx
));
1709 Args
.push_back(PtrVal
);
1711 // 'expected' argument, if present.
1713 AllocaCASExpected
= AllocaBuilder
.CreateAlloca(CASExpected
->getType());
1714 AllocaCASExpected
->setAlignment(MaybeAlign(AllocaAlignment
));
1715 unsigned AllocaAS
= AllocaCASExpected
->getType()->getPointerAddressSpace();
1717 AllocaCASExpected_i8
=
1718 Builder
.CreateBitCast(AllocaCASExpected
,
1719 Type::getInt8PtrTy(Ctx
, AllocaAS
));
1720 Builder
.CreateLifetimeStart(AllocaCASExpected_i8
, SizeVal64
);
1721 Builder
.CreateAlignedStore(CASExpected
, AllocaCASExpected
, AllocaAlignment
);
1722 Args
.push_back(AllocaCASExpected_i8
);
1725 // 'val' argument ('desired' for cas), if present.
1727 if (UseSizedLibcall
) {
1729 Builder
.CreateBitOrPointerCast(ValueOperand
, SizedIntTy
);
1730 Args
.push_back(IntValue
);
1732 AllocaValue
= AllocaBuilder
.CreateAlloca(ValueOperand
->getType());
1733 AllocaValue
->setAlignment(MaybeAlign(AllocaAlignment
));
1735 Builder
.CreateBitCast(AllocaValue
, Type::getInt8PtrTy(Ctx
));
1736 Builder
.CreateLifetimeStart(AllocaValue_i8
, SizeVal64
);
1737 Builder
.CreateAlignedStore(ValueOperand
, AllocaValue
, AllocaAlignment
);
1738 Args
.push_back(AllocaValue_i8
);
1743 if (!CASExpected
&& HasResult
&& !UseSizedLibcall
) {
1744 AllocaResult
= AllocaBuilder
.CreateAlloca(I
->getType());
1745 AllocaResult
->setAlignment(MaybeAlign(AllocaAlignment
));
1746 unsigned AllocaAS
= AllocaResult
->getType()->getPointerAddressSpace();
1748 Builder
.CreateBitCast(AllocaResult
, Type::getInt8PtrTy(Ctx
, AllocaAS
));
1749 Builder
.CreateLifetimeStart(AllocaResult_i8
, SizeVal64
);
1750 Args
.push_back(AllocaResult_i8
);
1753 // 'ordering' ('success_order' for cas) argument.
1754 Args
.push_back(OrderingVal
);
1756 // 'failure_order' argument, if present.
1758 Args
.push_back(Ordering2Val
);
1760 // Now, the return type.
1762 ResultTy
= Type::getInt1Ty(Ctx
);
1763 Attr
= Attr
.addAttribute(Ctx
, AttributeList::ReturnIndex
, Attribute::ZExt
);
1764 } else if (HasResult
&& UseSizedLibcall
)
1765 ResultTy
= SizedIntTy
;
1767 ResultTy
= Type::getVoidTy(Ctx
);
1769 // Done with setting up arguments and return types, create the call:
1770 SmallVector
<Type
*, 6> ArgTys
;
1771 for (Value
*Arg
: Args
)
1772 ArgTys
.push_back(Arg
->getType());
1773 FunctionType
*FnType
= FunctionType::get(ResultTy
, ArgTys
, false);
1774 FunctionCallee LibcallFn
=
1775 M
->getOrInsertFunction(TLI
->getLibcallName(RTLibType
), FnType
, Attr
);
1776 CallInst
*Call
= Builder
.CreateCall(LibcallFn
, Args
);
1777 Call
->setAttributes(Attr
);
1778 Value
*Result
= Call
;
1780 // And then, extract the results...
1781 if (ValueOperand
&& !UseSizedLibcall
)
1782 Builder
.CreateLifetimeEnd(AllocaValue_i8
, SizeVal64
);
1785 // The final result from the CAS is {load of 'expected' alloca, bool result
1787 Type
*FinalResultTy
= I
->getType();
1788 Value
*V
= UndefValue::get(FinalResultTy
);
1789 Value
*ExpectedOut
= Builder
.CreateAlignedLoad(
1790 CASExpected
->getType(), AllocaCASExpected
, AllocaAlignment
);
1791 Builder
.CreateLifetimeEnd(AllocaCASExpected_i8
, SizeVal64
);
1792 V
= Builder
.CreateInsertValue(V
, ExpectedOut
, 0);
1793 V
= Builder
.CreateInsertValue(V
, Result
, 1);
1794 I
->replaceAllUsesWith(V
);
1795 } else if (HasResult
) {
1797 if (UseSizedLibcall
)
1798 V
= Builder
.CreateBitOrPointerCast(Result
, I
->getType());
1800 V
= Builder
.CreateAlignedLoad(I
->getType(), AllocaResult
,
1802 Builder
.CreateLifetimeEnd(AllocaResult_i8
, SizeVal64
);
1804 I
->replaceAllUsesWith(V
);
1806 I
->eraseFromParent();