blob: dc7eaf6a5fe7ec05cc1d5db31419b72778d857c6 [file] [log] [blame]
Eugene Zelenkof1933322017-09-22 23:46:57 +00001//===- AtomicExpandPass.cpp - Expand atomic instructions ------------------===//
Tim Northoverc882eb02014-04-03 11:44:58 +00002//
Chandler Carruth2946cd72019-01-19 08:50:56 +00003// 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
Tim Northoverc882eb02014-04-03 11:44:58 +00006//
7//===----------------------------------------------------------------------===//
8//
9// This file contains a pass (at IR level) to replace atomic instructions with
James Y Knight19f6cce2016-04-12 20:18:48 +000010// __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.
Tim Northoverc882eb02014-04-03 11:44:58 +000014//
15//===----------------------------------------------------------------------===//
16
Eugene Zelenkof1933322017-09-22 23:46:57 +000017#include "llvm/ADT/ArrayRef.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
JF Bastiene8aad292015-08-03 15:29:47 +000020#include "llvm/CodeGen/AtomicExpandUtils.h"
Eugene Zelenkof1933322017-09-22 23:46:57 +000021#include "llvm/CodeGen/RuntimeLibcalls.h"
David Blaikieb3bde2e2017-11-17 01:07:10 +000022#include "llvm/CodeGen/TargetLowering.h"
Francis Visoiu Mistrih8b617642017-05-18 17:21:13 +000023#include "llvm/CodeGen/TargetPassConfig.h"
David Blaikieb3bde2e2017-11-17 01:07:10 +000024#include "llvm/CodeGen/TargetSubtargetInfo.h"
Craig Topper2fa14362018-03-29 17:21:10 +000025#include "llvm/CodeGen/ValueTypes.h"
Eugene Zelenkof1933322017-09-22 23:46:57 +000026#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"
Tim Northoverc882eb02014-04-03 11:44:58 +000032#include "llvm/IR/Function.h"
33#include "llvm/IR/IRBuilder.h"
Robin Morisseted3d48f2014-09-03 21:29:59 +000034#include "llvm/IR/InstIterator.h"
Eugene Zelenkof1933322017-09-22 23:46:57 +000035#include "llvm/IR/Instruction.h"
Tim Northoverc882eb02014-04-03 11:44:58 +000036#include "llvm/IR/Instructions.h"
Tim Northoverc882eb02014-04-03 11:44:58 +000037#include "llvm/IR/Module.h"
Eugene Zelenkof1933322017-09-22 23:46:57 +000038#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"
Tim Northoverc882eb02014-04-03 11:44:58 +000044#include "llvm/Support/Debug.h"
Eugene Zelenkof1933322017-09-22 23:46:57 +000045#include "llvm/Support/ErrorHandling.h"
Philip Reames23319012015-12-16 01:24:05 +000046#include "llvm/Support/raw_ostream.h"
Tim Northoverc882eb02014-04-03 11:44:58 +000047#include "llvm/Target/TargetMachine.h"
Eugene Zelenkof1933322017-09-22 23:46:57 +000048#include <cassert>
49#include <cstdint>
50#include <iterator>
Eric Christopherc40e5ed2014-06-19 21:03:04 +000051
Tim Northoverc882eb02014-04-03 11:44:58 +000052using namespace llvm;
53
Robin Morisset59c23cd2014-08-21 21:50:01 +000054#define DEBUG_TYPE "atomic-expand"
Chandler Carruth1b9dde02014-04-22 02:02:50 +000055
Tim Northoverc882eb02014-04-03 11:44:58 +000056namespace {
Eugene Zelenkof1933322017-09-22 23:46:57 +000057
Robin Morisset59c23cd2014-08-21 21:50:01 +000058 class AtomicExpand: public FunctionPass {
Eugene Zelenkof1933322017-09-22 23:46:57 +000059 const TargetLowering *TLI = nullptr;
60
Tim Northoverc882eb02014-04-03 11:44:58 +000061 public:
62 static char ID; // Pass identification, replacement for typeid
Eugene Zelenkof1933322017-09-22 23:46:57 +000063
64 AtomicExpand() : FunctionPass(ID) {
Robin Morisset59c23cd2014-08-21 21:50:01 +000065 initializeAtomicExpandPass(*PassRegistry::getPassRegistry());
Tim Northover037f26f22014-04-17 18:22:47 +000066 }
Tim Northoverc882eb02014-04-03 11:44:58 +000067
68 bool runOnFunction(Function &F) override;
Tim Northoverc882eb02014-04-03 11:44:58 +000069
Robin Morisseted3d48f2014-09-03 21:29:59 +000070 private:
Tim Shen04de70d2017-05-09 15:27:17 +000071 bool bracketInstWithFences(Instruction *I, AtomicOrdering Order);
Philip Reames61a24ab2015-12-16 00:49:36 +000072 IntegerType *getCorrespondingIntegerType(Type *T, const DataLayout &DL);
73 LoadInst *convertAtomicLoadToIntegerType(LoadInst *LI);
Ahmed Bougacha52468672015-09-11 17:08:28 +000074 bool tryExpandAtomicLoad(LoadInst *LI);
Robin Morisset6dbbbc22014-09-23 20:59:25 +000075 bool expandAtomicLoadToLL(LoadInst *LI);
76 bool expandAtomicLoadToCmpXchg(LoadInst *LI);
Philip Reames61a24ab2015-12-16 00:49:36 +000077 StoreInst *convertAtomicStoreToIntegerType(StoreInst *SI);
Robin Morisseted3d48f2014-09-03 21:29:59 +000078 bool expandAtomicStore(StoreInst *SI);
JF Bastienf14889e2015-03-04 15:47:57 +000079 bool tryExpandAtomicRMW(AtomicRMWInst *AI);
James Y Knight148a6462016-06-17 18:11:48 +000080 Value *
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,
Benjamin Kramerd3f4c052016-06-12 16:13:55 +000086 function_ref<Value *(IRBuilder<> &, Value *)> PerformOp);
James Y Knight148a6462016-06-17 18:11:48 +000087 void expandPartwordAtomicRMW(
88 AtomicRMWInst *I,
89 TargetLoweringBase::AtomicExpansionKind ExpansionKind);
Alex Bradbury3291f9a2018-08-17 14:03:37 +000090 AtomicRMWInst *widenPartwordAtomicRMW(AtomicRMWInst *AI);
James Y Knight148a6462016-06-17 18:11:48 +000091 void expandPartwordCmpXchg(AtomicCmpXchgInst *I);
Alex Bradbury21aea512018-09-19 10:54:22 +000092 void expandAtomicRMWToMaskedIntrinsic(AtomicRMWInst *AI);
Alex Bradbury66d9a752018-11-29 20:43:42 +000093 void expandAtomicCmpXchgToMaskedIntrinsic(AtomicCmpXchgInst *CI);
James Y Knight148a6462016-06-17 18:11:48 +000094
Philip Reames1960cfd2016-02-19 00:06:41 +000095 AtomicCmpXchgInst *convertCmpXchgToIntegerType(AtomicCmpXchgInst *CI);
James Y Knight148a6462016-06-17 18:11:48 +000096 static Value *insertRMWCmpXchgLoop(
97 IRBuilder<> &Builder, Type *ResultType, Value *Addr,
98 AtomicOrdering MemOpOrder,
99 function_ref<Value *(IRBuilder<> &, Value *)> PerformOp,
100 CreateCmpXchgInstFun CreateCmpXchg);
Alex Bradbury79518b02018-09-19 14:51:42 +0000101 bool tryExpandAtomicCmpXchg(AtomicCmpXchgInst *CI);
James Y Knight148a6462016-06-17 18:11:48 +0000102
Tim Northoverc882eb02014-04-03 11:44:58 +0000103 bool expandAtomicCmpXchg(AtomicCmpXchgInst *CI);
Fangrui Songcb0bab82018-07-16 18:51:40 +0000104 bool isIdempotentRMW(AtomicRMWInst *RMWI);
105 bool simplifyIdempotentRMW(AtomicRMWInst *RMWI);
James Y Knight19f6cce2016-04-12 20:18:48 +0000106
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);
James Y Knight148a6462016-06-17 18:11:48 +0000116
117 friend bool
118 llvm::expandAtomicRMWToCmpXchg(AtomicRMWInst *AI,
119 CreateCmpXchgInstFun CreateCmpXchg);
Tim Northoverc882eb02014-04-03 11:44:58 +0000120 };
Eugene Zelenkof1933322017-09-22 23:46:57 +0000121
122} // end anonymous namespace
Tim Northoverc882eb02014-04-03 11:44:58 +0000123
Robin Morisset59c23cd2014-08-21 21:50:01 +0000124char AtomicExpand::ID = 0;
Eugene Zelenkof1933322017-09-22 23:46:57 +0000125
Robin Morisset59c23cd2014-08-21 21:50:01 +0000126char &llvm::AtomicExpandID = AtomicExpand::ID;
Eugene Zelenkof1933322017-09-22 23:46:57 +0000127
Matthias Braun1527baa2017-05-25 21:26:32 +0000128INITIALIZE_PASS(AtomicExpand, DEBUG_TYPE, "Expand Atomic instructions",
Francis Visoiu Mistrih8b617642017-05-18 17:21:13 +0000129 false, false)
Tim Northover037f26f22014-04-17 18:22:47 +0000130
Francis Visoiu Mistrih8b617642017-05-18 17:21:13 +0000131FunctionPass *llvm::createAtomicExpandPass() { return new AtomicExpand(); }
Tim Northover037f26f22014-04-17 18:22:47 +0000132
James Y Knight19f6cce2016-04-12 20:18:48 +0000133// Helper functions to retrieve the size of atomic instructions.
Eugene Zelenkof1933322017-09-22 23:46:57 +0000134static unsigned getAtomicOpSize(LoadInst *LI) {
James Y Knight19f6cce2016-04-12 20:18:48 +0000135 const DataLayout &DL = LI->getModule()->getDataLayout();
136 return DL.getTypeStoreSize(LI->getType());
137}
138
Eugene Zelenkof1933322017-09-22 23:46:57 +0000139static unsigned getAtomicOpSize(StoreInst *SI) {
James Y Knight19f6cce2016-04-12 20:18:48 +0000140 const DataLayout &DL = SI->getModule()->getDataLayout();
141 return DL.getTypeStoreSize(SI->getValueOperand()->getType());
142}
143
Eugene Zelenkof1933322017-09-22 23:46:57 +0000144static unsigned getAtomicOpSize(AtomicRMWInst *RMWI) {
James Y Knight19f6cce2016-04-12 20:18:48 +0000145 const DataLayout &DL = RMWI->getModule()->getDataLayout();
146 return DL.getTypeStoreSize(RMWI->getValOperand()->getType());
147}
148
Eugene Zelenkof1933322017-09-22 23:46:57 +0000149static unsigned getAtomicOpSize(AtomicCmpXchgInst *CASI) {
James Y Knight19f6cce2016-04-12 20:18:48 +0000150 const DataLayout &DL = CASI->getModule()->getDataLayout();
151 return DL.getTypeStoreSize(CASI->getCompareOperand()->getType());
152}
153
154// Helper functions to retrieve the alignment of atomic instructions.
Eugene Zelenkof1933322017-09-22 23:46:57 +0000155static unsigned getAtomicOpAlign(LoadInst *LI) {
James Y Knight19f6cce2016-04-12 20:18:48 +0000156 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
159 // value.
160 assert(Align != 0 && "An atomic LoadInst always has an explicit alignment");
161 return Align;
162}
163
Eugene Zelenkof1933322017-09-22 23:46:57 +0000164static unsigned getAtomicOpAlign(StoreInst *SI) {
James Y Knight19f6cce2016-04-12 20:18:48 +0000165 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
168 // value.
169 assert(Align != 0 && "An atomic StoreInst always has an explicit alignment");
170 return Align;
171}
172
Eugene Zelenkof1933322017-09-22 23:46:57 +0000173static unsigned getAtomicOpAlign(AtomicRMWInst *RMWI) {
James Y Knight19f6cce2016-04-12 20:18:48 +0000174 // 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());
179}
180
Eugene Zelenkof1933322017-09-22 23:46:57 +0000181static unsigned getAtomicOpAlign(AtomicCmpXchgInst *CASI) {
James Y Knight19f6cce2016-04-12 20:18:48 +0000182 // TODO(PR27168): same comment as above.
183 const DataLayout &DL = CASI->getModule()->getDataLayout();
184 return DL.getTypeStoreSize(CASI->getCompareOperand()->getType());
185}
186
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)
190template <typename Inst>
Eugene Zelenkof1933322017-09-22 23:46:57 +0000191static bool atomicSizeSupported(const TargetLowering *TLI, Inst *I) {
James Y Knight19f6cce2016-04-12 20:18:48 +0000192 unsigned Size = getAtomicOpSize(I);
193 unsigned Align = getAtomicOpAlign(I);
194 return Align >= Size && Size <= TLI->getMaxAtomicSizeInBitsSupported() / 8;
195}
196
Robin Morisset59c23cd2014-08-21 21:50:01 +0000197bool AtomicExpand::runOnFunction(Function &F) {
Francis Visoiu Mistrih8b617642017-05-18 17:21:13 +0000198 auto *TPC = getAnalysisIfAvailable<TargetPassConfig>();
199 if (!TPC)
Tim Northover037f26f22014-04-17 18:22:47 +0000200 return false;
Francis Visoiu Mistrih8b617642017-05-18 17:21:13 +0000201
202 auto &TM = TPC->getTM<TargetMachine>();
203 if (!TM.getSubtargetImpl(F)->enableAtomicExpand())
204 return false;
205 TLI = TM.getSubtargetImpl(F)->getTargetLowering();
Tim Northover037f26f22014-04-17 18:22:47 +0000206
Tim Northoverc882eb02014-04-03 11:44:58 +0000207 SmallVector<Instruction *, 1> AtomicInsts;
208
209 // Changing control-flow while iterating through it is a bad idea, so gather a
210 // list of all atomic instructions before we start.
James Y Knight01f2ca52016-03-28 15:05:30 +0000211 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);
Tim Northoverc882eb02014-04-03 11:44:58 +0000215 }
216
Robin Morisseted3d48f2014-09-03 21:29:59 +0000217 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);
James Y Knight01f2ca52016-03-28 15:05:30 +0000223 assert((LI || SI || RMWI || CASI) && "Unknown atomic instruction");
Robin Morisseted3d48f2014-09-03 21:29:59 +0000224
James Y Knight19f6cce2016-04-12 20:18:48 +0000225 // If the Size/Alignment is not supported, replace with a libcall.
226 if (LI) {
227 if (!atomicSizeSupported(TLI, LI)) {
228 expandAtomicLoadToLibcall(LI);
229 MadeChange = true;
230 continue;
231 }
232 } else if (SI) {
233 if (!atomicSizeSupported(TLI, SI)) {
234 expandAtomicStoreToLibcall(SI);
235 MadeChange = true;
236 continue;
237 }
238 } else if (RMWI) {
239 if (!atomicSizeSupported(TLI, RMWI)) {
240 expandAtomicRMWToLibcall(RMWI);
241 MadeChange = true;
242 continue;
243 }
244 } else if (CASI) {
245 if (!atomicSizeSupported(TLI, CASI)) {
246 expandAtomicCASToLibcall(CASI);
247 MadeChange = true;
248 continue;
249 }
250 }
251
James Y Knightf44fc522016-03-16 22:12:04 +0000252 if (TLI->shouldInsertFencesForAtomic(I)) {
JF Bastien800f87a2016-04-06 21:19:33 +0000253 auto FenceOrdering = AtomicOrdering::Monotonic;
JF Bastien800f87a2016-04-06 21:19:33 +0000254 if (LI && isAcquireOrStronger(LI->getOrdering())) {
Robin Morissetdedef332014-09-23 20:31:14 +0000255 FenceOrdering = LI->getOrdering();
JF Bastien800f87a2016-04-06 21:19:33 +0000256 LI->setOrdering(AtomicOrdering::Monotonic);
JF Bastien800f87a2016-04-06 21:19:33 +0000257 } else if (SI && isReleaseOrStronger(SI->getOrdering())) {
Robin Morissetdedef332014-09-23 20:31:14 +0000258 FenceOrdering = SI->getOrdering();
JF Bastien800f87a2016-04-06 21:19:33 +0000259 SI->setOrdering(AtomicOrdering::Monotonic);
JF Bastien800f87a2016-04-06 21:19:33 +0000260 } else if (RMWI && (isReleaseOrStronger(RMWI->getOrdering()) ||
261 isAcquireOrStronger(RMWI->getOrdering()))) {
Robin Morissetdedef332014-09-23 20:31:14 +0000262 FenceOrdering = RMWI->getOrdering();
JF Bastien800f87a2016-04-06 21:19:33 +0000263 RMWI->setOrdering(AtomicOrdering::Monotonic);
Alex Bradbury79518b02018-09-19 14:51:42 +0000264 } else if (CASI &&
265 TLI->shouldExpandAtomicCmpXchgInIR(CASI) ==
266 TargetLoweringBase::AtomicExpansionKind::None &&
JF Bastien800f87a2016-04-06 21:19:33 +0000267 (isReleaseOrStronger(CASI->getSuccessOrdering()) ||
268 isAcquireOrStronger(CASI->getSuccessOrdering()))) {
Robin Morissetdedef332014-09-23 20:31:14 +0000269 // 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();
JF Bastien800f87a2016-04-06 21:19:33 +0000274 CASI->setSuccessOrdering(AtomicOrdering::Monotonic);
275 CASI->setFailureOrdering(AtomicOrdering::Monotonic);
Robin Morissetdedef332014-09-23 20:31:14 +0000276 }
277
JF Bastien800f87a2016-04-06 21:19:33 +0000278 if (FenceOrdering != AtomicOrdering::Monotonic) {
Tim Shen04de70d2017-05-09 15:27:17 +0000279 MadeChange |= bracketInstWithFences(I, FenceOrdering);
Robin Morissetdedef332014-09-23 20:31:14 +0000280 }
281 }
282
Ahmed Bougacha52468672015-09-11 17:08:28 +0000283 if (LI) {
Philip Reames61a24ab2015-12-16 00:49:36 +0000284 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");
289 MadeChange = true;
290 }
James Y Knight19f6cce2016-04-12 20:18:48 +0000291
Ahmed Bougacha52468672015-09-11 17:08:28 +0000292 MadeChange |= tryExpandAtomicLoad(LI);
Philip Reames61a24ab2015-12-16 00:49:36 +0000293 } else if (SI) {
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() &&
299 "invariant broken");
300 MadeChange = true;
301 }
302
303 if (TLI->shouldExpandAtomicStoreInIR(SI))
304 MadeChange |= expandAtomicStore(SI);
Robin Morisset810739d2014-09-25 17:27:43 +0000305 } else if (RMWI) {
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.
JF Bastienf14889e2015-03-04 15:47:57 +0000310
311 if (isIdempotentRMW(RMWI) && simplifyIdempotentRMW(RMWI)) {
312 MadeChange = true;
313 } else {
Alex Bradbury3291f9a2018-08-17 14:03:37 +0000314 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);
321 MadeChange = true;
322 }
323
JF Bastienf14889e2015-03-04 15:47:57 +0000324 MadeChange |= tryExpandAtomicRMW(RMWI);
325 }
Philip Reames1960cfd2016-02-19 00:06:41 +0000326 } else if (CASI) {
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() &&
336 "invariant broken");
337 MadeChange = true;
338 }
James Y Knight148a6462016-06-17 18:11:48 +0000339
Alex Bradbury79518b02018-09-19 14:51:42 +0000340 MadeChange |= tryExpandAtomicCmpXchg(CASI);
Robin Morisseted3d48f2014-09-03 21:29:59 +0000341 }
342 }
Tim Northoverc882eb02014-04-03 11:44:58 +0000343 return MadeChange;
344}
345
Tim Shen04de70d2017-05-09 15:27:17 +0000346bool AtomicExpand::bracketInstWithFences(Instruction *I, AtomicOrdering Order) {
Robin Morissetdedef332014-09-23 20:31:14 +0000347 IRBuilder<> Builder(I);
348
Tim Shen04de70d2017-05-09 15:27:17 +0000349 auto LeadingFence = TLI->emitLeadingFence(Builder, I, Order);
Robin Morissetdedef332014-09-23 20:31:14 +0000350
Tim Shen04de70d2017-05-09 15:27:17 +0000351 auto TrailingFence = TLI->emitTrailingFence(Builder, I, Order);
Robin Morissetdedef332014-09-23 20:31:14 +0000352 // We have a guard here because not every atomic operation generates a
353 // trailing fence.
Sanjay Patel674d2c22017-08-29 14:07:48 +0000354 if (TrailingFence)
355 TrailingFence->moveAfter(I);
Robin Morissetdedef332014-09-23 20:31:14 +0000356
357 return (LeadingFence || TrailingFence);
358}
359
Philip Reames61a24ab2015-12-16 00:49:36 +0000360/// Get the iX type with the same bitwidth as T.
361IntegerType *AtomicExpand::getCorrespondingIntegerType(Type *T,
362 const DataLayout &DL) {
Tim Northoveree2474d2019-05-01 12:37:30 +0000363 EVT VT = TLI->getMemValueType(DL, T);
Philip Reames61a24ab2015-12-16 00:49:36 +0000364 unsigned BitWidth = VT.getStoreSizeInBits();
365 assert(BitWidth == VT.getSizeInBits() && "must be a power of two");
366 return IntegerType::get(T->getContext(), BitWidth);
367}
368
369/// Convert an atomic load of a non-integral type to an integer load of the
Philip Reames1960cfd2016-02-19 00:06:41 +0000370/// equivalent bitwidth. See the function comment on
Fangrui Songf78650a2018-07-30 19:41:25 +0000371/// convertAtomicStoreToIntegerType for background.
Philip Reames61a24ab2015-12-16 00:49:36 +0000372LoadInst *AtomicExpand::convertAtomicLoadToIntegerType(LoadInst *LI) {
373 auto *M = LI->getModule();
374 Type *NewTy = getCorrespondingIntegerType(LI->getType(),
375 M->getDataLayout());
376
377 IRBuilder<> Builder(LI);
Fangrui Songf78650a2018-07-30 19:41:25 +0000378
Philip Reames61a24ab2015-12-16 00:49:36 +0000379 Value *Addr = LI->getPointerOperand();
380 Type *PT = PointerType::get(NewTy,
381 Addr->getType()->getPointerAddressSpace());
382 Value *NewAddr = Builder.CreateBitCast(Addr, PT);
Fangrui Songf78650a2018-07-30 19:41:25 +0000383
James Y Knight14359ef2019-02-01 20:44:24 +0000384 auto *NewLI = Builder.CreateLoad(NewTy, NewAddr);
Philip Reames61a24ab2015-12-16 00:49:36 +0000385 NewLI->setAlignment(LI->getAlignment());
386 NewLI->setVolatile(LI->isVolatile());
Konstantin Zhuravlyovbb80d3e2017-07-11 22:23:00 +0000387 NewLI->setAtomic(LI->getOrdering(), LI->getSyncScopeID());
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000388 LLVM_DEBUG(dbgs() << "Replaced " << *LI << " with " << *NewLI << "\n");
389
Philip Reames61a24ab2015-12-16 00:49:36 +0000390 Value *NewVal = Builder.CreateBitCast(NewLI, LI->getType());
391 LI->replaceAllUsesWith(NewVal);
392 LI->eraseFromParent();
393 return NewLI;
394}
395
Ahmed Bougacha52468672015-09-11 17:08:28 +0000396bool AtomicExpand::tryExpandAtomicLoad(LoadInst *LI) {
397 switch (TLI->shouldExpandAtomicLoadInIR(LI)) {
398 case TargetLoweringBase::AtomicExpansionKind::None:
399 return false;
Tim Northoverf520eff2015-12-02 18:12:57 +0000400 case TargetLoweringBase::AtomicExpansionKind::LLSC:
James Y Knight148a6462016-06-17 18:11:48 +0000401 expandAtomicOpToLLSC(
402 LI, LI->getType(), LI->getPointerOperand(), LI->getOrdering(),
Tim Northoverf520eff2015-12-02 18:12:57 +0000403 [](IRBuilder<> &Builder, Value *Loaded) { return Loaded; });
James Y Knight148a6462016-06-17 18:11:48 +0000404 return true;
Tim Northoverf520eff2015-12-02 18:12:57 +0000405 case TargetLoweringBase::AtomicExpansionKind::LLOnly:
Robin Morisset6dbbbc22014-09-23 20:59:25 +0000406 return expandAtomicLoadToLL(LI);
Tim Northoverf520eff2015-12-02 18:12:57 +0000407 case TargetLoweringBase::AtomicExpansionKind::CmpXChg:
Robin Morisset6dbbbc22014-09-23 20:59:25 +0000408 return expandAtomicLoadToCmpXchg(LI);
Alex Bradbury21aea512018-09-19 10:54:22 +0000409 default:
410 llvm_unreachable("Unhandled case in tryExpandAtomicLoad");
Ahmed Bougacha52468672015-09-11 17:08:28 +0000411 }
Robin Morisset6dbbbc22014-09-23 20:59:25 +0000412}
413
414bool AtomicExpand::expandAtomicLoadToLL(LoadInst *LI) {
Tim Northoverc882eb02014-04-03 11:44:58 +0000415 IRBuilder<> Builder(LI);
Tim Northoverc882eb02014-04-03 11:44:58 +0000416
Robin Morissetdedef332014-09-23 20:31:14 +0000417 // 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).
Robin Morisseta47cb412014-09-03 21:01:03 +0000420 Value *Val =
Robin Morissetdedef332014-09-23 20:31:14 +0000421 TLI->emitLoadLinked(Builder, LI->getPointerOperand(), LI->getOrdering());
Tim Northoverf520eff2015-12-02 18:12:57 +0000422 TLI->emitAtomicCmpXchgNoStoreLLBalance(Builder);
Tim Northoverc882eb02014-04-03 11:44:58 +0000423
424 LI->replaceAllUsesWith(Val);
425 LI->eraseFromParent();
426
427 return true;
428}
429
Robin Morisset6dbbbc22014-09-23 20:59:25 +0000430bool AtomicExpand::expandAtomicLoadToCmpXchg(LoadInst *LI) {
431 IRBuilder<> Builder(LI);
432 AtomicOrdering Order = LI->getOrdering();
Philip Reames2153c4b2019-03-19 17:20:49 +0000433 if (Order == AtomicOrdering::Unordered)
434 Order = AtomicOrdering::Monotonic;
435
Robin Morisset6dbbbc22014-09-23 20:59:25 +0000436 Value *Addr = LI->getPointerOperand();
437 Type *Ty = cast<PointerType>(Addr->getType())->getElementType();
438 Constant *DummyVal = Constant::getNullValue(Ty);
439
440 Value *Pair = Builder.CreateAtomicCmpXchg(
441 Addr, DummyVal, DummyVal, Order,
442 AtomicCmpXchgInst::getStrongestFailureOrdering(Order));
443 Value *Loaded = Builder.CreateExtractValue(Pair, 0, "loaded");
444
445 LI->replaceAllUsesWith(Loaded);
446 LI->eraseFromParent();
447
448 return true;
449}
450
Philip Reames61a24ab2015-12-16 00:49:36 +0000451/// Convert an atomic store of a non-integral type to an integer store of the
Philip Reames1960cfd2016-02-19 00:06:41 +0000452/// equivalent bitwidth. We used to not support floating point or vector
Philip Reames61a24ab2015-12-16 00:49:36 +0000453/// 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.
459StoreInst *AtomicExpand::convertAtomicStoreToIntegerType(StoreInst *SI) {
460 IRBuilder<> Builder(SI);
461 auto *M = SI->getModule();
462 Type *NewTy = getCorrespondingIntegerType(SI->getValueOperand()->getType(),
463 M->getDataLayout());
464 Value *NewVal = Builder.CreateBitCast(SI->getValueOperand(), NewTy);
Fangrui Songf78650a2018-07-30 19:41:25 +0000465
Philip Reames61a24ab2015-12-16 00:49:36 +0000466 Value *Addr = SI->getPointerOperand();
467 Type *PT = PointerType::get(NewTy,
468 Addr->getType()->getPointerAddressSpace());
469 Value *NewAddr = Builder.CreateBitCast(Addr, PT);
470
471 StoreInst *NewSI = Builder.CreateStore(NewVal, NewAddr);
472 NewSI->setAlignment(SI->getAlignment());
473 NewSI->setVolatile(SI->isVolatile());
Konstantin Zhuravlyovbb80d3e2017-07-11 22:23:00 +0000474 NewSI->setAtomic(SI->getOrdering(), SI->getSyncScopeID());
Nicola Zaghend34e60c2018-05-14 12:53:11 +0000475 LLVM_DEBUG(dbgs() << "Replaced " << *SI << " with " << *NewSI << "\n");
Philip Reames61a24ab2015-12-16 00:49:36 +0000476 SI->eraseFromParent();
477 return NewSI;
478}
479
Robin Morisset59c23cd2014-08-21 21:50:01 +0000480bool AtomicExpand::expandAtomicStore(StoreInst *SI) {
Robin Morisset25c8e312014-09-17 00:06:58 +0000481 // 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.
JF Bastienf14889e2015-03-04 15:47:57 +0000485 // It is the responsibility of the target to only signal expansion via
Robin Morisset25c8e312014-09-17 00:06:58 +0000486 // shouldExpandAtomicRMW in cases where this is required and possible.
Tim Northoverc882eb02014-04-03 11:44:58 +0000487 IRBuilder<> Builder(SI);
488 AtomicRMWInst *AI =
489 Builder.CreateAtomicRMW(AtomicRMWInst::Xchg, SI->getPointerOperand(),
490 SI->getValueOperand(), SI->getOrdering());
491 SI->eraseFromParent();
492
493 // Now we have an appropriate swap instruction, lower it as usual.
JF Bastienf14889e2015-03-04 15:47:57 +0000494 return tryExpandAtomicRMW(AI);
Tim Northoverc882eb02014-04-03 11:44:58 +0000495}
496
JF Bastiene8aad292015-08-03 15:29:47 +0000497static void createCmpXchgInstFun(IRBuilder<> &Builder, Value *Addr,
498 Value *Loaded, Value *NewVal,
499 AtomicOrdering MemOpOrder,
500 Value *&Success, Value *&NewLoaded) {
Matt Arsenault0cb08e42019-01-17 10:49:01 +0000501 Type *OrigTy = NewVal->getType();
502
503 // This code can go away when cmpxchg supports FP types.
504 bool NeedBitcast = OrigTy->isFloatingPointTy();
505 if (NeedBitcast) {
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);
511 }
512
JF Bastiene8aad292015-08-03 15:29:47 +0000513 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");
Matt Arsenault0cb08e42019-01-17 10:49:01 +0000518
519 if (NeedBitcast)
520 NewLoaded = Builder.CreateBitCast(NewLoaded, OrigTy);
JF Bastiene8aad292015-08-03 15:29:47 +0000521}
522
Robin Morisset25c8e312014-09-17 00:06:58 +0000523/// Emit IR to implement the given atomicrmw operation on values in registers,
524/// returning the new value.
525static Value *performAtomicOp(AtomicRMWInst::BinOp Op, IRBuilder<> &Builder,
526 Value *Loaded, Value *Inc) {
527 Value *NewVal;
528 switch (Op) {
529 case AtomicRMWInst::Xchg:
530 return Inc;
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");
Matt Arsenault39508332019-01-22 18:18:02 +0000555 case AtomicRMWInst::FAdd:
556 return Builder.CreateFAdd(Loaded, Inc, "new");
557 case AtomicRMWInst::FSub:
558 return Builder.CreateFSub(Loaded, Inc, "new");
Robin Morisset25c8e312014-09-17 00:06:58 +0000559 default:
560 llvm_unreachable("Unknown atomic op");
561 }
562}
563
Tim Northoverf520eff2015-12-02 18:12:57 +0000564bool AtomicExpand::tryExpandAtomicRMW(AtomicRMWInst *AI) {
565 switch (TLI->shouldExpandAtomicRMWInIR(AI)) {
566 case TargetLoweringBase::AtomicExpansionKind::None:
567 return false;
James Y Knight148a6462016-06-17 18:11:48 +0000568 case TargetLoweringBase::AtomicExpansionKind::LLSC: {
569 unsigned MinCASSize = TLI->getMinCmpXchgSizeInBits() / 8;
570 unsigned ValueSize = getAtomicOpSize(AI);
571 if (ValueSize < MinCASSize) {
572 llvm_unreachable(
573 "MinCmpXchgSizeInBits not yet supported for LL/SC architectures.");
574 } else {
575 auto PerformOp = [&](IRBuilder<> &Builder, Value *Loaded) {
576 return performAtomicOp(AI->getOperation(), Builder, Loaded,
577 AI->getValOperand());
578 };
579 expandAtomicOpToLLSC(AI, AI->getType(), AI->getPointerOperand(),
580 AI->getOrdering(), PerformOp);
581 }
582 return true;
583 }
584 case TargetLoweringBase::AtomicExpansionKind::CmpXChg: {
585 unsigned MinCASSize = TLI->getMinCmpXchgSizeInBits() / 8;
586 unsigned ValueSize = getAtomicOpSize(AI);
587 if (ValueSize < MinCASSize) {
Matt Arsenault383e72f2019-06-11 01:35:00 +0000588 // TODO: Handle atomicrmw fadd/fsub
589 if (AI->getType()->isFloatingPointTy())
590 return false;
591
James Y Knight148a6462016-06-17 18:11:48 +0000592 expandPartwordAtomicRMW(AI,
593 TargetLoweringBase::AtomicExpansionKind::CmpXChg);
594 } else {
595 expandAtomicRMWToCmpXchg(AI, createCmpXchgInstFun);
596 }
597 return true;
598 }
Alex Bradbury21aea512018-09-19 10:54:22 +0000599 case TargetLoweringBase::AtomicExpansionKind::MaskedIntrinsic: {
600 expandAtomicRMWToMaskedIntrinsic(AI);
601 return true;
602 }
Tim Northoverf520eff2015-12-02 18:12:57 +0000603 default:
604 llvm_unreachable("Unhandled case in tryExpandAtomicRMW");
605 }
606}
607
James Y Knight148a6462016-06-17 18:11:48 +0000608namespace {
609
610/// Result values from createMaskInstrs helper.
611struct PartwordMaskValues {
612 Type *WordType;
613 Type *ValueType;
614 Value *AlignedAddr;
615 Value *ShiftAmt;
616 Value *Mask;
617 Value *Inv_Mask;
618};
Eugene Zelenkof1933322017-09-22 23:46:57 +0000619
James Y Knight148a6462016-06-17 18:11:48 +0000620} // end anonymous namespace
621
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
626/// WordSize.
627///
628/// AlignedAddr: Addr rounded down to a multiple of WordSize
629///
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.
633///
634/// Mask: Value to mask with the value loaded from AlignAddr to
635/// include only the part that would've been loaded from Addr.
636///
637/// Inv_Mask: The inverse of Mask.
James Y Knight148a6462016-06-17 18:11:48 +0000638static PartwordMaskValues createMaskInstrs(IRBuilder<> &Builder, Instruction *I,
639 Type *ValueType, Value *Addr,
640 unsigned WordSize) {
641 PartwordMaskValues Ret;
642
Tim Northoverf520eff2015-12-02 18:12:57 +0000643 BasicBlock *BB = I->getParent();
Tim Northoverc882eb02014-04-03 11:44:58 +0000644 Function *F = BB->getParent();
James Y Knight148a6462016-06-17 18:11:48 +0000645 Module *M = I->getModule();
646
Tim Northoverc882eb02014-04-03 11:44:58 +0000647 LLVMContext &Ctx = F->getContext();
James Y Knight148a6462016-06-17 18:11:48 +0000648 const DataLayout &DL = M->getDataLayout();
649
650 unsigned ValueSize = DL.getTypeStoreSize(ValueType);
651
652 assert(ValueSize < WordSize);
653
654 Ret.ValueType = ValueType;
655 Ret.WordType = Type::getIntNTy(Ctx, WordSize * 8);
656
657 Type *WordPtrType =
658 Ret.WordType->getPointerTo(Addr->getType()->getPointerAddressSpace());
659
660 Value *AddrInt = Builder.CreatePtrToInt(Addr, DL.getIntPtrType(Ctx));
661 Ret.AlignedAddr = Builder.CreateIntToPtr(
662 Builder.CreateAnd(AddrInt, ~(uint64_t)(WordSize - 1)), WordPtrType,
663 "AlignedAddr");
664
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);
669 } else {
670 // turn bytes into bits, and count from the other side.
671 Ret.ShiftAmt =
672 Builder.CreateShl(Builder.CreateXor(PtrLSB, WordSize - ValueSize), 3);
673 }
674
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,
678 "Mask");
679 Ret.Inv_Mask = Builder.CreateNot(Ret.Mask, "Inv_Mask");
680
681 return Ret;
682}
683
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)
687static Value *performMaskedAtomicOp(AtomicRMWInst::BinOp Op,
688 IRBuilder<> &Builder, Value *Loaded,
689 Value *Shifted_Inc, Value *Inc,
690 const PartwordMaskValues &PMV) {
Alex Bradbury21aea512018-09-19 10:54:22 +0000691 // 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.
James Y Knight148a6462016-06-17 18:11:48 +0000694 switch (Op) {
695 case AtomicRMWInst::Xchg: {
696 Value *Loaded_MaskOut = Builder.CreateAnd(Loaded, PMV.Inv_Mask);
697 Value *FinalVal = Builder.CreateOr(Loaded_MaskOut, Shifted_Inc);
698 return FinalVal;
699 }
700 case AtomicRMWInst::Or:
701 case AtomicRMWInst::Xor:
Alex Bradbury3291f9a2018-08-17 14:03:37 +0000702 case AtomicRMWInst::And:
703 llvm_unreachable("Or/Xor/And handled by widenPartwordAtomicRMW");
James Y Knight148a6462016-06-17 18:11:48 +0000704 case AtomicRMWInst::Add:
705 case AtomicRMWInst::Sub:
James Y Knight148a6462016-06-17 18:11:48 +0000706 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);
712 return FinalVal;
713 }
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);
728 return FinalVal;
729 }
730 default:
731 llvm_unreachable("Unknown atomic op");
732 }
733}
734
735/// Expand a sub-word atomicrmw operation into an appropriate
736/// word-sized operation.
737///
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.
742void AtomicExpand::expandPartwordAtomicRMW(
743 AtomicRMWInst *AI, TargetLoweringBase::AtomicExpansionKind ExpansionKind) {
James Y Knight148a6462016-06-17 18:11:48 +0000744 assert(ExpansionKind == TargetLoweringBase::AtomicExpansionKind::CmpXChg);
745
746 AtomicOrdering MemOpOrder = AI->getOrdering();
747
748 IRBuilder<> Builder(AI);
749
750 PartwordMaskValues PMV =
751 createMaskInstrs(Builder, AI, AI->getType(), AI->getPointerOperand(),
752 TLI->getMinCmpXchgSizeInBits() / 8);
753
754 Value *ValOperand_Shifted =
755 Builder.CreateShl(Builder.CreateZExt(AI->getValOperand(), PMV.WordType),
756 PMV.ShiftAmt, "ValOperand_Shifted");
757
758 auto PerformPartwordOp = [&](IRBuilder<> &Builder, Value *Loaded) {
759 return performMaskedAtomicOp(AI->getOperation(), Builder, Loaded,
760 ValOperand_Shifted, AI->getValOperand(), PMV);
761 };
762
763 // TODO: When we're ready to support LLSC conversions too, use
764 // insertRMWLLSCLoop here for ExpansionKind==LLSC.
765 Value *OldResult =
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();
772}
773
Alex Bradbury3291f9a2018-08-17 14:03:37 +0000774// Widen the bitwise atomicrmw (or/xor/and) to the minimum supported width.
775AtomicRMWInst *AtomicExpand::widenPartwordAtomicRMW(AtomicRMWInst *AI) {
776 IRBuilder<> Builder(AI);
777 AtomicRMWInst::BinOp Op = AI->getOperation();
778
779 assert((Op == AtomicRMWInst::Or || Op == AtomicRMWInst::Xor ||
780 Op == AtomicRMWInst::And) &&
781 "Unable to widen operation");
782
783 PartwordMaskValues PMV =
784 createMaskInstrs(Builder, AI, AI->getType(), AI->getPointerOperand(),
785 TLI->getMinCmpXchgSizeInBits() / 8);
786
787 Value *ValOperand_Shifted =
788 Builder.CreateShl(Builder.CreateZExt(AI->getValOperand(), PMV.WordType),
789 PMV.ShiftAmt, "ValOperand_Shifted");
790
791 Value *NewOperand;
792
793 if (Op == AtomicRMWInst::And)
794 NewOperand =
795 Builder.CreateOr(PMV.Inv_Mask, ValOperand_Shifted, "AndOperand");
796 else
797 NewOperand = ValOperand_Shifted;
798
799 AtomicRMWInst *NewAI = Builder.CreateAtomicRMW(Op, PMV.AlignedAddr,
800 NewOperand, AI->getOrdering());
801
802 Value *FinalOldResult = Builder.CreateTrunc(
803 Builder.CreateLShr(NewAI, PMV.ShiftAmt), PMV.ValueType);
804 AI->replaceAllUsesWith(FinalOldResult);
805 AI->eraseFromParent();
806 return NewAI;
807}
808
James Y Knight148a6462016-06-17 18:11:48 +0000809void 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
814 // failure.
815
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
844
845 Value *Addr = CI->getPointerOperand();
846 Value *Cmp = CI->getCompareOperand();
847 Value *NewVal = CI->getNewValOperand();
848
849 BasicBlock *BB = CI->getParent();
850 Function *F = BB->getParent();
851 IRBuilder<> Builder(CI);
852 LLVMContext &Ctx = Builder.getContext();
853
854 const int WordSize = TLI->getMinCmpXchgSizeInBits() / 8;
855
856 BasicBlock *EndBB =
857 BB->splitBasicBlock(CI->getIterator(), "partword.cmpxchg.end");
858 auto FailureBB =
859 BasicBlock::Create(Ctx, "partword.cmpxchg.failure", F, EndBB);
860 auto LoopBB = BasicBlock::Create(Ctx, "partword.cmpxchg.loop", F, FailureBB);
861
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);
866
867 PartwordMaskValues PMV = createMaskInstrs(
868 Builder, CI, CI->getCompareOperand()->getType(), Addr, WordSize);
869
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);
873 Value *Cmp_Shifted =
874 Builder.CreateShl(Builder.CreateZExt(Cmp, PMV.WordType), PMV.ShiftAmt);
875
876 // Load the entire current word, and mask into place the expected and new
877 // values
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);
882
883 // partword.cmpxchg.loop:
884 Builder.SetInsertPoint(LoopBB);
885 PHINode *Loaded_MaskOut = Builder.CreatePHI(PMV.WordType, 2);
886 Loaded_MaskOut->addIncoming(InitLoaded_MaskOut, BB);
887
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(),
Konstantin Zhuravlyovbb80d3e2017-07-11 22:23:00 +0000893 CI->getFailureOrdering(), CI->getSyncScopeID());
James Y Knight148a6462016-06-17 18:11:48 +0000894 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());
901
902 Value *OldVal = Builder.CreateExtractValue(NewCI, 0);
903 Value *Success = Builder.CreateExtractValue(NewCI, 1);
904
905 if (CI->isWeak())
906 Builder.CreateBr(EndBB);
907 else
908 Builder.CreateCondBr(Success, EndBB, FailureBB);
909
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);
918
919 // Add the second value to the phi from above
920 Loaded_MaskOut->addIncoming(OldVal_MaskOut, FailureBB);
921
922 // partword.cmpxchg.end:
923 Builder.SetInsertPoint(CI);
924
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);
930
931 CI->replaceAllUsesWith(Res);
932 CI->eraseFromParent();
933}
934
935void AtomicExpand::expandAtomicOpToLLSC(
936 Instruction *I, Type *ResultType, Value *Addr, AtomicOrdering MemOpOrder,
937 function_ref<Value *(IRBuilder<> &, Value *)> PerformOp) {
938 IRBuilder<> Builder(I);
939 Value *Loaded =
940 insertRMWLLSCLoop(Builder, ResultType, Addr, MemOpOrder, PerformOp);
941
942 I->replaceAllUsesWith(Loaded);
943 I->eraseFromParent();
944}
945
Alex Bradbury21aea512018-09-19 10:54:22 +0000946void AtomicExpand::expandAtomicRMWToMaskedIntrinsic(AtomicRMWInst *AI) {
947 IRBuilder<> Builder(AI);
948
949 PartwordMaskValues PMV =
950 createMaskInstrs(Builder, AI, AI->getType(), AI->getPointerOperand(),
951 TLI->getMinCmpXchgSizeInBits() / 8);
952
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
955 // zero-ext.
956 Instruction::CastOps CastOp = Instruction::ZExt;
957 AtomicRMWInst::BinOp RMWOp = AI->getOperation();
958 if (RMWOp == AtomicRMWInst::Max || RMWOp == AtomicRMWInst::Min)
959 CastOp = Instruction::SExt;
960
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,
966 AI->getOrdering());
967 Value *FinalOldResult = Builder.CreateTrunc(
968 Builder.CreateLShr(OldResult, PMV.ShiftAmt), PMV.ValueType);
969 AI->replaceAllUsesWith(FinalOldResult);
970 AI->eraseFromParent();
971}
972
Alex Bradbury66d9a752018-11-29 20:43:42 +0000973void AtomicExpand::expandAtomicCmpXchgToMaskedIntrinsic(AtomicCmpXchgInst *CI) {
974 IRBuilder<> Builder(CI);
975
976 PartwordMaskValues PMV = createMaskInstrs(
977 Builder, CI, CI->getCompareOperand()->getType(), CI->getPointerOperand(),
978 TLI->getMinCmpXchgSizeInBits() / 8);
979
980 Value *CmpVal_Shifted = Builder.CreateShl(
981 Builder.CreateZExt(CI->getCompareOperand(), PMV.WordType), PMV.ShiftAmt,
982 "CmpVal_Shifted");
983 Value *NewVal_Shifted = Builder.CreateShl(
984 Builder.CreateZExt(CI->getNewValOperand(), PMV.WordType), PMV.ShiftAmt,
985 "NewVal_Shifted");
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);
991
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);
997
998 CI->replaceAllUsesWith(Res);
999 CI->eraseFromParent();
1000}
1001
James Y Knight148a6462016-06-17 18:11:48 +00001002Value *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();
Tim Northoverc882eb02014-04-03 11:44:58 +00001009
1010 // Given: atomicrmw some_op iN* %addr, iN %incr ordering
1011 //
1012 // The standard expansion we produce is:
1013 // [...]
Tim Northoverc882eb02014-04-03 11:44:58 +00001014 // atomicrmw.start:
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
1020 // atomicrmw.end:
Tim Northoverc882eb02014-04-03 11:44:58 +00001021 // [...]
James Y Knight148a6462016-06-17 18:11:48 +00001022 BasicBlock *ExitBB =
1023 BB->splitBasicBlock(Builder.GetInsertPoint(), "atomicrmw.end");
Tim Northoverc882eb02014-04-03 11:44:58 +00001024 BasicBlock *LoopBB = BasicBlock::Create(Ctx, "atomicrmw.start", F, ExitBB);
1025
Tim Northoverc882eb02014-04-03 11:44:58 +00001026 // The split call above "helpfully" added a branch at the end of BB (to the
James Y Knight148a6462016-06-17 18:11:48 +00001027 // wrong place).
Tim Northoverc882eb02014-04-03 11:44:58 +00001028 std::prev(BB->end())->eraseFromParent();
1029 Builder.SetInsertPoint(BB);
Tim Northoverc882eb02014-04-03 11:44:58 +00001030 Builder.CreateBr(LoopBB);
1031
1032 // Start the main loop block now that we've taken care of the preliminaries.
1033 Builder.SetInsertPoint(LoopBB);
Robin Morisseta47cb412014-09-03 21:01:03 +00001034 Value *Loaded = TLI->emitLoadLinked(Builder, Addr, MemOpOrder);
Tim Northoverc882eb02014-04-03 11:44:58 +00001035
Tim Northoverf520eff2015-12-02 18:12:57 +00001036 Value *NewVal = PerformOp(Builder, Loaded);
Tim Northoverc882eb02014-04-03 11:44:58 +00001037
Eric Christopherd9134482014-08-04 21:25:23 +00001038 Value *StoreSuccess =
Robin Morisseta47cb412014-09-03 21:01:03 +00001039 TLI->emitStoreConditional(Builder, NewVal, Addr, MemOpOrder);
Tim Northoverc882eb02014-04-03 11:44:58 +00001040 Value *TryAgain = Builder.CreateICmpNE(
1041 StoreSuccess, ConstantInt::get(IntegerType::get(Ctx, 32), 0), "tryagain");
1042 Builder.CreateCondBr(TryAgain, LoopBB, ExitBB);
1043
1044 Builder.SetInsertPoint(ExitBB, ExitBB->begin());
James Y Knight148a6462016-06-17 18:11:48 +00001045 return Loaded;
Tim Northoverc882eb02014-04-03 11:44:58 +00001046}
1047
Philip Reames1960cfd2016-02-19 00:06:41 +00001048/// 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
Fangrui Songf78650a2018-07-30 19:41:25 +00001052/// one.
Philip Reames1960cfd2016-02-19 00:06:41 +00001053AtomicCmpXchgInst *AtomicExpand::convertCmpXchgToIntegerType(AtomicCmpXchgInst *CI) {
1054 auto *M = CI->getModule();
1055 Type *NewTy = getCorrespondingIntegerType(CI->getCompareOperand()->getType(),
1056 M->getDataLayout());
1057
1058 IRBuilder<> Builder(CI);
Fangrui Songf78650a2018-07-30 19:41:25 +00001059
Philip Reames1960cfd2016-02-19 00:06:41 +00001060 Value *Addr = CI->getPointerOperand();
1061 Type *PT = PointerType::get(NewTy,
1062 Addr->getType()->getPointerAddressSpace());
1063 Value *NewAddr = Builder.CreateBitCast(Addr, PT);
1064
1065 Value *NewCmp = Builder.CreatePtrToInt(CI->getCompareOperand(), NewTy);
1066 Value *NewNewVal = Builder.CreatePtrToInt(CI->getNewValOperand(), NewTy);
Fangrui Songf78650a2018-07-30 19:41:25 +00001067
1068
Philip Reames1960cfd2016-02-19 00:06:41 +00001069 auto *NewCI = Builder.CreateAtomicCmpXchg(NewAddr, NewCmp, NewNewVal,
1070 CI->getSuccessOrdering(),
1071 CI->getFailureOrdering(),
Konstantin Zhuravlyovbb80d3e2017-07-11 22:23:00 +00001072 CI->getSyncScopeID());
Philip Reames1960cfd2016-02-19 00:06:41 +00001073 NewCI->setVolatile(CI->isVolatile());
1074 NewCI->setWeak(CI->isWeak());
Nicola Zaghend34e60c2018-05-14 12:53:11 +00001075 LLVM_DEBUG(dbgs() << "Replaced " << *CI << " with " << *NewCI << "\n");
Philip Reames1960cfd2016-02-19 00:06:41 +00001076
1077 Value *OldVal = Builder.CreateExtractValue(NewCI, 0);
1078 Value *Succ = Builder.CreateExtractValue(NewCI, 1);
1079
1080 OldVal = Builder.CreateIntToPtr(OldVal, CI->getCompareOperand()->getType());
1081
1082 Value *Res = UndefValue::get(CI->getType());
1083 Res = Builder.CreateInsertValue(Res, OldVal, 0);
1084 Res = Builder.CreateInsertValue(Res, Succ, 1);
1085
1086 CI->replaceAllUsesWith(Res);
1087 CI->eraseFromParent();
1088 return NewCI;
1089}
1090
Robin Morisset59c23cd2014-08-21 21:50:01 +00001091bool AtomicExpand::expandAtomicCmpXchg(AtomicCmpXchgInst *CI) {
Tim Northover70450c52014-04-03 13:06:54 +00001092 AtomicOrdering SuccessOrder = CI->getSuccessOrdering();
1093 AtomicOrdering FailureOrder = CI->getFailureOrdering();
Tim Northoverc882eb02014-04-03 11:44:58 +00001094 Value *Addr = CI->getPointerOperand();
1095 BasicBlock *BB = CI->getParent();
1096 Function *F = BB->getParent();
1097 LLVMContext &Ctx = F->getContext();
James Y Knightf44fc522016-03-16 22:12:04 +00001098 // 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
Robin Morisseted3d48f2014-09-03 21:29:59 +00001101 // should preserve the ordering.
James Y Knightf44fc522016-03-16 22:12:04 +00001102 bool ShouldInsertFencesForAtomic = TLI->shouldInsertFencesForAtomic(CI);
Robin Morisseta47cb412014-09-03 21:01:03 +00001103 AtomicOrdering MemOpOrder =
JF Bastien800f87a2016-04-06 21:19:33 +00001104 ShouldInsertFencesForAtomic ? AtomicOrdering::Monotonic : SuccessOrder;
Tim Northoverc882eb02014-04-03 11:44:58 +00001105
Tim Northoverd32f8e62016-02-22 20:55:50 +00001106 // 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.
1110 //
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.
James Y Knightf44fc522016-03-16 22:12:04 +00001115 bool HasReleasedLoadBB = !CI->isWeak() && ShouldInsertFencesForAtomic &&
JF Bastien800f87a2016-04-06 21:19:33 +00001116 SuccessOrder != AtomicOrdering::Monotonic &&
1117 SuccessOrder != AtomicOrdering::Acquire &&
Evandro Menezes85bd3972019-04-04 22:40:06 +00001118 !F->hasMinSize();
Tim Northoverd32f8e62016-02-22 20:55:50 +00001119
1120 // There's no overhead for sinking the release barrier in a weak cmpxchg, so
1121 // do it even on minsize.
Evandro Menezes85bd3972019-04-04 22:40:06 +00001122 bool UseUnconditionalReleaseBarrier = F->hasMinSize() && !CI->isWeak();
Tim Northoverd32f8e62016-02-22 20:55:50 +00001123
Tim Northoverc882eb02014-04-03 11:44:58 +00001124 // Given: cmpxchg some_op iN* %addr, iN %desired, iN %new success_ord fail_ord
1125 //
Tim Northover70450c52014-04-03 13:06:54 +00001126 // The full expansion we produce is:
Tim Northoverc882eb02014-04-03 11:44:58 +00001127 // [...]
Tim Northoverc882eb02014-04-03 11:44:58 +00001128 // cmpxchg.start:
Tim Northoverd32f8e62016-02-22 20:55:50 +00001129 // %unreleasedload = @load.linked(%addr)
1130 // %should_store = icmp eq %unreleasedload, %desired
1131 // br i1 %should_store, label %cmpxchg.fencedstore,
Ahmed Bougacha07a844d2015-09-22 17:21:44 +00001132 // label %cmpxchg.nostore
Tim Northoverd32f8e62016-02-22 20:55:50 +00001133 // cmpxchg.releasingstore:
1134 // fence?
1135 // br label cmpxchg.trystore
Tim Northoverc882eb02014-04-03 11:44:58 +00001136 // cmpxchg.trystore:
Tim Northoverd32f8e62016-02-22 20:55:50 +00001137 // %loaded.trystore = phi [%unreleasedload, %releasingstore],
1138 // [%releasedload, %cmpxchg.releasedload]
Tim Northoverc882eb02014-04-03 11:44:58 +00001139 // %stored = @store_conditional(%new, %addr)
Tim Northover20b9f732014-06-13 16:45:52 +00001140 // %success = icmp eq i32 %stored, 0
Tim Northoverd32f8e62016-02-22 20:55:50 +00001141 // 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
Tim Northover20b9f732014-06-13 16:45:52 +00001148 // cmpxchg.success:
1149 // fence?
1150 // br label %cmpxchg.end
Ahmed Bougacha07a844d2015-09-22 17:21:44 +00001151 // cmpxchg.nostore:
Tim Northoverd32f8e62016-02-22 20:55:50 +00001152 // %loaded.nostore = phi [%unreleasedload, %cmpxchg.start],
1153 // [%releasedload,
1154 // %cmpxchg.releasedload/%cmpxchg.trystore]
Ahmed Bougacha07a844d2015-09-22 17:21:44 +00001155 // @load_linked_fail_balance()?
1156 // br label %cmpxchg.failure
Tim Northover20b9f732014-06-13 16:45:52 +00001157 // cmpxchg.failure:
Tim Northoverc882eb02014-04-03 11:44:58 +00001158 // fence?
Tim Northover70450c52014-04-03 13:06:54 +00001159 // br label %cmpxchg.end
1160 // cmpxchg.end:
Tim Northoverd32f8e62016-02-22 20:55:50 +00001161 // %loaded = phi [%loaded.nostore, %cmpxchg.failure],
1162 // [%loaded.trystore, %cmpxchg.trystore]
Tim Northover20b9f732014-06-13 16:45:52 +00001163 // %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
Tim Northoverc882eb02014-04-03 11:44:58 +00001166 // [...]
Duncan P. N. Exon Smith8f11e1a2015-10-09 16:54:49 +00001167 BasicBlock *ExitBB = BB->splitBasicBlock(CI->getIterator(), "cmpxchg.end");
Tim Northover20b9f732014-06-13 16:45:52 +00001168 auto FailureBB = BasicBlock::Create(Ctx, "cmpxchg.failure", F, ExitBB);
Ahmed Bougacha07a844d2015-09-22 17:21:44 +00001169 auto NoStoreBB = BasicBlock::Create(Ctx, "cmpxchg.nostore", F, FailureBB);
1170 auto SuccessBB = BasicBlock::Create(Ctx, "cmpxchg.success", F, NoStoreBB);
Tim Northoverd32f8e62016-02-22 20:55:50 +00001171 auto ReleasedLoadBB =
1172 BasicBlock::Create(Ctx, "cmpxchg.releasedload", F, SuccessBB);
1173 auto TryStoreBB =
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);
Tim Northoverc882eb02014-04-03 11:44:58 +00001178
1179 // This grabs the DebugLoc from CI
1180 IRBuilder<> Builder(CI);
1181
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);
James Y Knightf44fc522016-03-16 22:12:04 +00001187 if (ShouldInsertFencesForAtomic && UseUnconditionalReleaseBarrier)
Tim Shen04de70d2017-05-09 15:27:17 +00001188 TLI->emitLeadingFence(Builder, CI, SuccessOrder);
Tim Northoverd32f8e62016-02-22 20:55:50 +00001189 Builder.CreateBr(StartBB);
Tim Northoverc882eb02014-04-03 11:44:58 +00001190
1191 // Start the main loop block now that we've taken care of the preliminaries.
Tim Northoverd32f8e62016-02-22 20:55:50 +00001192 Builder.SetInsertPoint(StartBB);
1193 Value *UnreleasedLoad = TLI->emitLoadLinked(Builder, Addr, MemOpOrder);
1194 Value *ShouldStore = Builder.CreateICmpEQ(
1195 UnreleasedLoad, CI->getCompareOperand(), "should_store");
Tim Northover70450c52014-04-03 13:06:54 +00001196
Eric Christopher572e03a2015-06-19 01:53:21 +00001197 // If the cmpxchg doesn't actually need any ordering when it fails, we can
Tim Northover70450c52014-04-03 13:06:54 +00001198 // jump straight past that fence instruction (if it exists).
Tim Northoverd32f8e62016-02-22 20:55:50 +00001199 Builder.CreateCondBr(ShouldStore, ReleasingStoreBB, NoStoreBB);
1200
1201 Builder.SetInsertPoint(ReleasingStoreBB);
James Y Knightf44fc522016-03-16 22:12:04 +00001202 if (ShouldInsertFencesForAtomic && !UseUnconditionalReleaseBarrier)
Tim Shen04de70d2017-05-09 15:27:17 +00001203 TLI->emitLeadingFence(Builder, CI, SuccessOrder);
Tim Northoverd32f8e62016-02-22 20:55:50 +00001204 Builder.CreateBr(TryStoreBB);
Tim Northoverc882eb02014-04-03 11:44:58 +00001205
1206 Builder.SetInsertPoint(TryStoreBB);
Robin Morisseta47cb412014-09-03 21:01:03 +00001207 Value *StoreSuccess = TLI->emitStoreConditional(
1208 Builder, CI->getNewValOperand(), Addr, MemOpOrder);
Tim Northoverd039abd2014-06-13 16:45:36 +00001209 StoreSuccess = Builder.CreateICmpEQ(
Tim Northoverc882eb02014-04-03 11:44:58 +00001210 StoreSuccess, ConstantInt::get(Type::getInt32Ty(Ctx), 0), "success");
Tim Northoverd32f8e62016-02-22 20:55:50 +00001211 BasicBlock *RetryBB = HasReleasedLoadBB ? ReleasedLoadBB : StartBB;
Tim Northover20b9f732014-06-13 16:45:52 +00001212 Builder.CreateCondBr(StoreSuccess, SuccessBB,
Tim Northoverd32f8e62016-02-22 20:55:50 +00001213 CI->isWeak() ? FailureBB : RetryBB);
Tim Northoverc882eb02014-04-03 11:44:58 +00001214
Tim Northoverd32f8e62016-02-22 20:55:50 +00001215 Builder.SetInsertPoint(ReleasedLoadBB);
1216 Value *SecondLoad;
1217 if (HasReleasedLoadBB) {
1218 SecondLoad = TLI->emitLoadLinked(Builder, Addr, MemOpOrder);
1219 ShouldStore = Builder.CreateICmpEQ(SecondLoad, CI->getCompareOperand(),
1220 "should_store");
1221
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);
1225 } else
1226 Builder.CreateUnreachable();
1227
1228 // Make sure later instructions don't get reordered with a fence if
1229 // necessary.
Tim Northover20b9f732014-06-13 16:45:52 +00001230 Builder.SetInsertPoint(SuccessBB);
James Y Knightf44fc522016-03-16 22:12:04 +00001231 if (ShouldInsertFencesForAtomic)
Tim Shen04de70d2017-05-09 15:27:17 +00001232 TLI->emitTrailingFence(Builder, CI, SuccessOrder);
Tim Northover70450c52014-04-03 13:06:54 +00001233 Builder.CreateBr(ExitBB);
Tim Northoverc882eb02014-04-03 11:44:58 +00001234
Ahmed Bougacha07a844d2015-09-22 17:21:44 +00001235 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);
1241
Tim Northover20b9f732014-06-13 16:45:52 +00001242 Builder.SetInsertPoint(FailureBB);
James Y Knightf44fc522016-03-16 22:12:04 +00001243 if (ShouldInsertFencesForAtomic)
Tim Shen04de70d2017-05-09 15:27:17 +00001244 TLI->emitTrailingFence(Builder, CI, FailureOrder);
Tim Northover20b9f732014-06-13 16:45:52 +00001245 Builder.CreateBr(ExitBB);
1246
Tim Northoverb4ddc082014-05-30 10:09:59 +00001247 // Finally, we have control-flow based knowledge of whether the cmpxchg
1248 // succeeded or not. We expose this to later passes by converting any
Tim Northoverd32f8e62016-02-22 20:55:50 +00001249 // subsequent "icmp eq/ne %loaded, %oldval" into a use of an appropriate
1250 // PHI.
Tim Northover20b9f732014-06-13 16:45:52 +00001251 Builder.SetInsertPoint(ExitBB, ExitBB->begin());
Tim Northover420a2162014-06-13 14:24:07 +00001252 PHINode *Success = Builder.CreatePHI(Type::getInt1Ty(Ctx), 2);
1253 Success->addIncoming(ConstantInt::getTrue(Ctx), SuccessBB);
Tim Northover20b9f732014-06-13 16:45:52 +00001254 Success->addIncoming(ConstantInt::getFalse(Ctx), FailureBB);
Tim Northoverb4ddc082014-05-30 10:09:59 +00001255
Tim Northoverd32f8e62016-02-22 20:55:50 +00001256 // Setup the builder so we can create any PHIs we need.
1257 Value *Loaded;
1258 if (!HasReleasedLoadBB)
1259 Loaded = UnreleasedLoad;
1260 else {
1261 Builder.SetInsertPoint(TryStoreBB, TryStoreBB->begin());
1262 PHINode *TryStoreLoaded = Builder.CreatePHI(UnreleasedLoad->getType(), 2);
1263 TryStoreLoaded->addIncoming(UnreleasedLoad, ReleasingStoreBB);
1264 TryStoreLoaded->addIncoming(SecondLoad, ReleasedLoadBB);
1265
1266 Builder.SetInsertPoint(NoStoreBB, NoStoreBB->begin());
1267 PHINode *NoStoreLoaded = Builder.CreatePHI(UnreleasedLoad->getType(), 2);
1268 NoStoreLoaded->addIncoming(UnreleasedLoad, StartBB);
1269 NoStoreLoaded->addIncoming(SecondLoad, ReleasedLoadBB);
1270
1271 Builder.SetInsertPoint(ExitBB, ++ExitBB->begin());
1272 PHINode *ExitLoaded = Builder.CreatePHI(UnreleasedLoad->getType(), 2);
1273 ExitLoaded->addIncoming(TryStoreLoaded, SuccessBB);
1274 ExitLoaded->addIncoming(NoStoreLoaded, FailureBB);
1275
1276 Loaded = ExitLoaded;
1277 }
1278
Tim Northoverb4ddc082014-05-30 10:09:59 +00001279 // 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.
Tim Northover420a2162014-06-13 14:24:07 +00001281 SmallVector<ExtractValueInst *, 2> PrunedInsts;
Tim Northoverb4ddc082014-05-30 10:09:59 +00001282 for (auto User : CI->users()) {
Tim Northover420a2162014-06-13 14:24:07 +00001283 ExtractValueInst *EV = dyn_cast<ExtractValueInst>(User);
1284 if (!EV)
Tim Northoverb4ddc082014-05-30 10:09:59 +00001285 continue;
1286
Tim Northover420a2162014-06-13 14:24:07 +00001287 assert(EV->getNumIndices() == 1 && EV->getIndices()[0] <= 1 &&
1288 "weird extraction from { iN, i1 }");
Tim Northoverb4ddc082014-05-30 10:09:59 +00001289
Tim Northover420a2162014-06-13 14:24:07 +00001290 if (EV->getIndices()[0] == 0)
1291 EV->replaceAllUsesWith(Loaded);
1292 else
1293 EV->replaceAllUsesWith(Success);
1294
1295 PrunedInsts.push_back(EV);
Tim Northoverb4ddc082014-05-30 10:09:59 +00001296 }
1297
Tim Northover420a2162014-06-13 14:24:07 +00001298 // We can remove the instructions now we're no longer iterating through them.
1299 for (auto EV : PrunedInsts)
1300 EV->eraseFromParent();
Tim Northoverc882eb02014-04-03 11:44:58 +00001301
Tim Northover420a2162014-06-13 14:24:07 +00001302 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.
1305 Value *Res;
1306 Res = Builder.CreateInsertValue(UndefValue::get(CI->getType()), Loaded, 0);
1307 Res = Builder.CreateInsertValue(Res, Success, 1);
1308
1309 CI->replaceAllUsesWith(Res);
1310 }
1311
1312 CI->eraseFromParent();
Tim Northoverc882eb02014-04-03 11:44:58 +00001313 return true;
1314}
Robin Morisset810739d2014-09-25 17:27:43 +00001315
1316bool AtomicExpand::isIdempotentRMW(AtomicRMWInst* RMWI) {
1317 auto C = dyn_cast<ConstantInt>(RMWI->getValOperand());
1318 if(!C)
1319 return false;
1320
1321 AtomicRMWInst::BinOp Op = RMWI->getOperation();
1322 switch(Op) {
1323 case AtomicRMWInst::Add:
1324 case AtomicRMWInst::Sub:
1325 case AtomicRMWInst::Or:
1326 case AtomicRMWInst::Xor:
1327 return C->isZero();
1328 case AtomicRMWInst::And:
1329 return C->isMinusOne();
1330 // FIXME: we could also treat Min/Max/UMin/UMax by the INT_MIN/INT_MAX/...
1331 default:
1332 return false;
1333 }
1334}
1335
1336bool AtomicExpand::simplifyIdempotentRMW(AtomicRMWInst* RMWI) {
Ahmed Bougacha49b531a2015-09-12 18:51:23 +00001337 if (auto ResultingLoad = TLI->lowerIdempotentRMWIntoFencedLoad(RMWI)) {
1338 tryExpandAtomicLoad(ResultingLoad);
1339 return true;
1340 }
Robin Morisset810739d2014-09-25 17:27:43 +00001341 return false;
1342}
JF Bastiene8aad292015-08-03 15:29:47 +00001343
James Y Knight148a6462016-06-17 18:11:48 +00001344Value *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();
JF Bastiene8aad292015-08-03 15:29:47 +00001351 Function *F = BB->getParent();
JF Bastiene8aad292015-08-03 15:29:47 +00001352
1353 // Given: atomicrmw some_op iN* %addr, iN %incr ordering
1354 //
1355 // The standard expansion we produce is:
1356 // [...]
1357 // %init_loaded = load atomic iN* %addr
1358 // br label %loop
1359 // loop:
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
1366 // atomicrmw.end:
1367 // [...]
James Y Knight148a6462016-06-17 18:11:48 +00001368 BasicBlock *ExitBB =
1369 BB->splitBasicBlock(Builder.GetInsertPoint(), "atomicrmw.end");
JF Bastiene8aad292015-08-03 15:29:47 +00001370 BasicBlock *LoopBB = BasicBlock::Create(Ctx, "atomicrmw.start", F, ExitBB);
1371
JF Bastiene8aad292015-08-03 15:29:47 +00001372 // 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);
James Y Knight148a6462016-06-17 18:11:48 +00001377 LoadInst *InitLoaded = Builder.CreateLoad(ResultTy, Addr);
JF Bastiene8aad292015-08-03 15:29:47 +00001378 // Atomics require at least natural alignment.
James Y Knight148a6462016-06-17 18:11:48 +00001379 InitLoaded->setAlignment(ResultTy->getPrimitiveSizeInBits() / 8);
JF Bastiene8aad292015-08-03 15:29:47 +00001380 Builder.CreateBr(LoopBB);
1381
1382 // Start the main loop block now that we've taken care of the preliminaries.
1383 Builder.SetInsertPoint(LoopBB);
James Y Knight148a6462016-06-17 18:11:48 +00001384 PHINode *Loaded = Builder.CreatePHI(ResultTy, 2, "loaded");
JF Bastiene8aad292015-08-03 15:29:47 +00001385 Loaded->addIncoming(InitLoaded, BB);
1386
James Y Knight148a6462016-06-17 18:11:48 +00001387 Value *NewVal = PerformOp(Builder, Loaded);
JF Bastiene8aad292015-08-03 15:29:47 +00001388
1389 Value *NewLoaded = nullptr;
1390 Value *Success = nullptr;
1391
James Y Knight148a6462016-06-17 18:11:48 +00001392 CreateCmpXchg(Builder, Addr, Loaded, NewVal,
1393 MemOpOrder == AtomicOrdering::Unordered
1394 ? AtomicOrdering::Monotonic
1395 : MemOpOrder,
JF Bastiene8aad292015-08-03 15:29:47 +00001396 Success, NewLoaded);
1397 assert(Success && NewLoaded);
1398
1399 Loaded->addIncoming(NewLoaded, LoopBB);
1400
1401 Builder.CreateCondBr(Success, ExitBB, LoopBB);
1402
1403 Builder.SetInsertPoint(ExitBB, ExitBB->begin());
James Y Knight148a6462016-06-17 18:11:48 +00001404 return NewLoaded;
1405}
JF Bastiene8aad292015-08-03 15:29:47 +00001406
Alex Bradbury79518b02018-09-19 14:51:42 +00001407bool AtomicExpand::tryExpandAtomicCmpXchg(AtomicCmpXchgInst *CI) {
1408 unsigned MinCASSize = TLI->getMinCmpXchgSizeInBits() / 8;
1409 unsigned ValueSize = getAtomicOpSize(CI);
1410
1411 switch (TLI->shouldExpandAtomicCmpXchgInIR(CI)) {
1412 default:
1413 llvm_unreachable("Unhandled case in tryExpandAtomicCmpXchg");
1414 case TargetLoweringBase::AtomicExpansionKind::None:
1415 if (ValueSize < MinCASSize)
1416 expandPartwordCmpXchg(CI);
1417 return false;
1418 case TargetLoweringBase::AtomicExpansionKind::LLSC: {
1419 assert(ValueSize >= MinCASSize &&
1420 "MinCmpXchgSizeInBits not yet supported for LL/SC expansions.");
1421 return expandAtomicCmpXchg(CI);
1422 }
1423 case TargetLoweringBase::AtomicExpansionKind::MaskedIntrinsic:
Alex Bradbury66d9a752018-11-29 20:43:42 +00001424 expandAtomicCmpXchgToMaskedIntrinsic(CI);
1425 return true;
Alex Bradbury79518b02018-09-19 14:51:42 +00001426 }
1427}
1428
James Y Knight148a6462016-06-17 18:11:48 +00001429// Note: This function is exposed externally by AtomicExpandUtils.h
1430bool 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());
1438 },
1439 CreateCmpXchg);
1440
1441 AI->replaceAllUsesWith(Loaded);
JF Bastiene8aad292015-08-03 15:29:47 +00001442 AI->eraseFromParent();
JF Bastiene8aad292015-08-03 15:29:47 +00001443 return true;
1444}
James Y Knight19f6cce2016-04-12 20:18:48 +00001445
James Y Knight19f6cce2016-04-12 20:18:48 +00001446// 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.)
1451static 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...
Jun Bum Limbe11bdc2016-05-13 18:38:35 +00001460 unsigned LargestSize = DL.getLargestLegalIntTypeSizeInBits() >= 64 ? 16 : 8;
James Y Knight19f6cce2016-04-12 20:18:48 +00001461 return Align >= Size &&
1462 (Size == 1 || Size == 2 || Size == 4 || Size == 8 || Size == 16) &&
1463 Size <= LargestSize;
1464}
1465
1466void 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);
1472
1473 bool expanded = expandAtomicOpToLibcall(
1474 I, Size, Align, I->getPointerOperand(), nullptr, nullptr,
1475 I->getOrdering(), AtomicOrdering::NotAtomic, Libcalls);
1476 (void)expanded;
1477 assert(expanded && "expandAtomicOpToLibcall shouldn't fail tor Load");
1478}
1479
1480void 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);
1486
1487 bool expanded = expandAtomicOpToLibcall(
1488 I, Size, Align, I->getPointerOperand(), I->getValueOperand(), nullptr,
1489 I->getOrdering(), AtomicOrdering::NotAtomic, Libcalls);
1490 (void)expanded;
1491 assert(expanded && "expandAtomicOpToLibcall shouldn't fail tor Store");
1492}
1493
1494void 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);
1501
1502 bool expanded = expandAtomicOpToLibcall(
1503 I, Size, Align, I->getPointerOperand(), I->getNewValOperand(),
1504 I->getCompareOperand(), I->getSuccessOrdering(), I->getFailureOrdering(),
1505 Libcalls);
1506 (void)expanded;
1507 assert(expanded && "expandAtomicOpToLibcall shouldn't fail tor CAS");
1508}
1509
1510static 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};
1539
1540 switch (Op) {
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:
Matt Arsenault39508332019-01-22 18:18:02 +00001561 case AtomicRMWInst::FAdd:
1562 case AtomicRMWInst::FSub:
James Y Knight19f6cce2016-04-12 20:18:48 +00001563 // No atomic libcalls are available for max/min/umax/umin.
1564 return {};
1565 }
1566 llvm_unreachable("Unexpected AtomicRMW operation.");
1567}
1568
1569void AtomicExpand::expandAtomicRMWToLibcall(AtomicRMWInst *I) {
1570 ArrayRef<RTLIB::Libcall> Libcalls = GetRMWLibcall(I->getOperation());
1571
1572 unsigned Size = getAtomicOpSize(I);
1573 unsigned Align = getAtomicOpAlign(I);
1574
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);
1580
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.
1585 if (!Success) {
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");
1596
1597 // ...and then expand the CAS into a libcall.
1598 expandAtomicCASToLibcall(Pair);
1599 });
1600 }
1601}
1602
1603// A helper routine for the above expandAtomic*ToLibcall functions.
1604//
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.
1609bool 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);
1614
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());
1620
1621 bool UseSizedLibcall = canUseSizedAtomicCall(Size, Align, DL);
1622 Type *SizedIntTy = Type::getIntNTy(Ctx, Size * 8);
1623
1624 unsigned AllocaAlignment = DL.getPrefTypeAlignment(SizedIntTy);
1625
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);
JF Bastienbbb0aee62016-04-18 18:01:43 +00001629 assert(Ordering != AtomicOrdering::NotAtomic && "expect atomic MO");
James Y Knight19f6cce2016-04-12 20:18:48 +00001630 Constant *OrderingVal =
JF Bastienbbb0aee62016-04-18 18:01:43 +00001631 ConstantInt::get(Type::getInt32Ty(Ctx), (int)toCABI(Ordering));
1632 Constant *Ordering2Val = nullptr;
1633 if (CASExpected) {
1634 assert(Ordering2 != AtomicOrdering::NotAtomic && "expect atomic MO");
1635 Ordering2Val =
1636 ConstantInt::get(Type::getInt32Ty(Ctx), (int)toCABI(Ordering2));
1637 }
James Y Knight19f6cce2016-04-12 20:18:48 +00001638 bool HasResult = I->getType() != Type::getVoidTy(Ctx);
1639
1640 RTLIB::Libcall RTLibType;
1641 if (UseSizedLibcall) {
1642 switch (Size) {
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;
1648 }
1649 } else if (Libcalls[0] != RTLIB::UNKNOWN_LIBCALL) {
1650 RTLibType = Libcalls[0];
1651 } else {
1652 // Can't use sized function, and there's no generic for this
1653 // operation, so give up.
1654 return false;
1655 }
1656
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
1659 // N=1,2,4,8,16):
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)
1665 //
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
1668 // way in and out.
1669 //
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,
1674 // int ordering)
1675 // bool __atomic_compare_exchange(size_t size, void *ptr, void *expected,
1676 // void *desired, int success_order,
1677 // int failure_order)
1678 //
1679 // The different signatures are built up depending on the
1680 // 'UseSizedLibcall', 'CASExpected', 'ValueOperand', and 'HasResult'
1681 // variables.
1682
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;
1689
1690 Type *ResultTy;
1691 SmallVector<Value *, 6> Args;
Reid Klecknerb5180542017-03-21 16:57:19 +00001692 AttributeList Attr;
James Y Knight19f6cce2016-04-12 20:18:48 +00001693
1694 // 'size' argument.
1695 if (!UseSizedLibcall) {
1696 // Note, getIntPtrType is assumed equivalent to size_t.
1697 Args.push_back(ConstantInt::get(DL.getIntPtrType(Ctx), Size));
1698 }
1699
1700 // 'ptr' argument.
Philip Reames9549f752019-03-06 19:27:13 +00001701 // 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));
James Y Knight19f6cce2016-04-12 20:18:48 +00001709 Args.push_back(PtrVal);
1710
1711 // 'expected' argument, if present.
1712 if (CASExpected) {
1713 AllocaCASExpected = AllocaBuilder.CreateAlloca(CASExpected->getType());
1714 AllocaCASExpected->setAlignment(AllocaAlignment);
Matt Arsenaultc5830f52019-06-11 01:35:07 +00001715 unsigned AllocaAS = AllocaCASExpected->getType()->getPointerAddressSpace();
1716
James Y Knight19f6cce2016-04-12 20:18:48 +00001717 AllocaCASExpected_i8 =
Matt Arsenaultc5830f52019-06-11 01:35:07 +00001718 Builder.CreateBitCast(AllocaCASExpected,
1719 Type::getInt8PtrTy(Ctx, AllocaAS));
James Y Knight19f6cce2016-04-12 20:18:48 +00001720 Builder.CreateLifetimeStart(AllocaCASExpected_i8, SizeVal64);
1721 Builder.CreateAlignedStore(CASExpected, AllocaCASExpected, AllocaAlignment);
1722 Args.push_back(AllocaCASExpected_i8);
1723 }
1724
1725 // 'val' argument ('desired' for cas), if present.
1726 if (ValueOperand) {
1727 if (UseSizedLibcall) {
1728 Value *IntValue =
1729 Builder.CreateBitOrPointerCast(ValueOperand, SizedIntTy);
1730 Args.push_back(IntValue);
1731 } else {
1732 AllocaValue = AllocaBuilder.CreateAlloca(ValueOperand->getType());
1733 AllocaValue->setAlignment(AllocaAlignment);
1734 AllocaValue_i8 =
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);
1739 }
1740 }
1741
1742 // 'ret' argument.
1743 if (!CASExpected && HasResult && !UseSizedLibcall) {
1744 AllocaResult = AllocaBuilder.CreateAlloca(I->getType());
1745 AllocaResult->setAlignment(AllocaAlignment);
Matt Arsenaultc5830f52019-06-11 01:35:07 +00001746 unsigned AllocaAS = AllocaResult->getType()->getPointerAddressSpace();
James Y Knight19f6cce2016-04-12 20:18:48 +00001747 AllocaResult_i8 =
Matt Arsenaultc5830f52019-06-11 01:35:07 +00001748 Builder.CreateBitCast(AllocaResult, Type::getInt8PtrTy(Ctx, AllocaAS));
James Y Knight19f6cce2016-04-12 20:18:48 +00001749 Builder.CreateLifetimeStart(AllocaResult_i8, SizeVal64);
1750 Args.push_back(AllocaResult_i8);
1751 }
1752
1753 // 'ordering' ('success_order' for cas) argument.
1754 Args.push_back(OrderingVal);
1755
1756 // 'failure_order' argument, if present.
1757 if (Ordering2Val)
1758 Args.push_back(Ordering2Val);
1759
1760 // Now, the return type.
1761 if (CASExpected) {
1762 ResultTy = Type::getInt1Ty(Ctx);
Reid Klecknerb5180542017-03-21 16:57:19 +00001763 Attr = Attr.addAttribute(Ctx, AttributeList::ReturnIndex, Attribute::ZExt);
James Y Knight19f6cce2016-04-12 20:18:48 +00001764 } else if (HasResult && UseSizedLibcall)
1765 ResultTy = SizedIntTy;
1766 else
1767 ResultTy = Type::getVoidTy(Ctx);
1768
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);
James Y Knight13680222019-02-01 02:28:03 +00001774 FunctionCallee LibcallFn =
James Y Knight19f6cce2016-04-12 20:18:48 +00001775 M->getOrInsertFunction(TLI->getLibcallName(RTLibType), FnType, Attr);
1776 CallInst *Call = Builder.CreateCall(LibcallFn, Args);
1777 Call->setAttributes(Attr);
1778 Value *Result = Call;
1779
1780 // And then, extract the results...
1781 if (ValueOperand && !UseSizedLibcall)
1782 Builder.CreateLifetimeEnd(AllocaValue_i8, SizeVal64);
1783
1784 if (CASExpected) {
1785 // The final result from the CAS is {load of 'expected' alloca, bool result
1786 // from call}
1787 Type *FinalResultTy = I->getType();
1788 Value *V = UndefValue::get(FinalResultTy);
James Y Knight14359ef2019-02-01 20:44:24 +00001789 Value *ExpectedOut = Builder.CreateAlignedLoad(
1790 CASExpected->getType(), AllocaCASExpected, AllocaAlignment);
James Y Knight19f6cce2016-04-12 20:18:48 +00001791 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) {
1796 Value *V;
1797 if (UseSizedLibcall)
1798 V = Builder.CreateBitOrPointerCast(Result, I->getType());
1799 else {
James Y Knight14359ef2019-02-01 20:44:24 +00001800 V = Builder.CreateAlignedLoad(I->getType(), AllocaResult,
1801 AllocaAlignment);
James Y Knight19f6cce2016-04-12 20:18:48 +00001802 Builder.CreateLifetimeEnd(AllocaResult_i8, SizeVal64);
1803 }
1804 I->replaceAllUsesWith(V);
1805 }
1806 I->eraseFromParent();
1807 return true;
1808}