1 //===-- CDSPass.cpp - xxx -------------------------------===//
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
6 // This file is distributed under the University of Illinois Open Source
7 // License. See LICENSE.TXT for details.
9 //===----------------------------------------------------------------------===//
11 // This file is a modified version of ThreadSanitizer.cpp, a part of a race detector.
13 // The tool is under development, for the details about previous versions see
14 // http://code.google.com/p/data-race-test
16 // The instrumentation phase is quite simple:
17 // - Insert calls to run-time library before every memory access.
18 // - Optimizations may apply to avoid instrumenting some of the accesses.
19 // - Insert calls at function entry/exit.
20 // The rest is handled by the run-time library.
21 //===----------------------------------------------------------------------===//
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/ADT/StringExtras.h"
25 #include "llvm/ADT/SmallString.h"
26 #include "llvm/Analysis/ValueTracking.h"
27 #include "llvm/Analysis/CaptureTracking.h"
28 #include "llvm/IR/BasicBlock.h"
29 #include "llvm/IR/Function.h"
30 #include "llvm/IR/IRBuilder.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/LLVMContext.h"
33 #include "llvm/IR/LegacyPassManager.h"
34 #include "llvm/IR/Module.h"
35 #include "llvm/IR/PassManager.h"
36 #include "llvm/Pass.h"
37 #include "llvm/ProfileData/InstrProf.h"
38 #include "llvm/Support/raw_ostream.h"
39 #include "llvm/Support/AtomicOrdering.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Transforms/Scalar.h"
42 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
43 #include "llvm/Transforms/Utils/EscapeEnumerator.h"
44 // #include "llvm/Transforms/Utils/ModuleUtils.h"
45 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
50 #define DEBUG_TYPE "CDS"
51 #include <llvm/IR/DebugLoc.h>
53 Value *getPosition( Instruction * I, IRBuilder <> IRB, bool print = false)
55 const DebugLoc & debug_location = I->getDebugLoc ();
56 std::string position_string;
58 llvm::raw_string_ostream position_stream (position_string);
59 debug_location . print (position_stream);
63 errs() << position_string << "\n";
66 return IRB.CreateGlobalStringPtr (position_string);
69 STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
70 STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
71 STATISTIC(NumOmittedReadsBeforeWrite,
72 "Number of reads ignored due to following writes");
73 STATISTIC(NumAccessesWithBadSize, "Number of accesses with bad size");
74 // STATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes");
75 // STATISTIC(NumInstrumentedVtableReads, "Number of vtable ptr reads");
76 STATISTIC(NumOmittedReadsFromConstantGlobals,
77 "Number of reads from constant globals");
78 STATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads");
79 STATISTIC(NumOmittedNonCaptured, "Number of accesses ignored due to capturing");
81 // static const char *const kCDSModuleCtorName = "cds.module_ctor";
82 // static const char *const kCDSInitName = "cds_init";
93 static const size_t kNumberOfAccessSizes = 4;
95 int getAtomicOrderIndex(AtomicOrdering order) {
97 case AtomicOrdering::Monotonic:
98 return (int)AtomicOrderingCABI::relaxed;
99 // case AtomicOrdering::Consume: // not specified yet
100 // return AtomicOrderingCABI::consume;
101 case AtomicOrdering::Acquire:
102 return (int)AtomicOrderingCABI::acquire;
103 case AtomicOrdering::Release:
104 return (int)AtomicOrderingCABI::release;
105 case AtomicOrdering::AcquireRelease:
106 return (int)AtomicOrderingCABI::acq_rel;
107 case AtomicOrdering::SequentiallyConsistent:
108 return (int)AtomicOrderingCABI::seq_cst;
110 // unordered or Not Atomic
115 AtomicOrderingCABI indexToAtomicOrder(int index) {
118 return AtomicOrderingCABI::relaxed;
120 return AtomicOrderingCABI::consume;
122 return AtomicOrderingCABI::acquire;
124 return AtomicOrderingCABI::release;
126 return AtomicOrderingCABI::acq_rel;
128 return AtomicOrderingCABI::seq_cst;
130 errs() << "Bad Atomic index\n";
131 return AtomicOrderingCABI::seq_cst;
135 /* According to atomic_base.h: __cmpexch_failure_order */
136 int AtomicCasFailureOrderIndex(int index) {
137 AtomicOrderingCABI succ_order = indexToAtomicOrder(index);
138 AtomicOrderingCABI fail_order;
139 if (succ_order == AtomicOrderingCABI::acq_rel)
140 fail_order = AtomicOrderingCABI::acquire;
141 else if (succ_order == AtomicOrderingCABI::release)
142 fail_order = AtomicOrderingCABI::relaxed;
144 fail_order = succ_order;
146 return (int) fail_order;
149 /* The original function checkSanitizerInterfaceFunction was defined
150 * in llvm/Transforms/Utils/ModuleUtils.h
152 static Function * checkCDSPassInterfaceFunction(Constant *FuncOrBitcast) {
153 if (isa<Function>(FuncOrBitcast))
154 return cast<Function>(FuncOrBitcast);
155 FuncOrBitcast->print(errs());
158 raw_string_ostream Stream(Err);
159 Stream << "CDSPass interface function redefined: " << *FuncOrBitcast;
160 report_fatal_error(Err);
164 struct CDSPass : public FunctionPass {
165 CDSPass() : FunctionPass(ID) {}
166 StringRef getPassName() const override;
167 bool runOnFunction(Function &F) override;
168 bool doInitialization(Module &M) override;
172 void initializeCallbacks(Module &M);
173 bool instrumentLoadOrStore(Instruction *I, const DataLayout &DL);
174 bool instrumentVolatile(Instruction *I, const DataLayout &DL);
175 bool isAtomicCall(Instruction *I);
176 bool instrumentAtomic(Instruction *I, const DataLayout &DL);
177 bool instrumentAtomicCall(CallInst *CI, const DataLayout &DL);
178 void chooseInstructionsToInstrument(SmallVectorImpl<Instruction *> &Local,
179 SmallVectorImpl<Instruction *> &All,
180 const DataLayout &DL);
181 bool addrPointsToConstantData(Value *Addr);
182 int getMemoryAccessFuncIndex(Value *Addr, const DataLayout &DL);
184 Function * CDSFuncEntry;
185 Function * CDSFuncExit;
187 Function * CDSLoad[kNumberOfAccessSizes];
188 Function * CDSStore[kNumberOfAccessSizes];
189 Function * CDSVolatileLoad[kNumberOfAccessSizes];
190 Function * CDSVolatileStore[kNumberOfAccessSizes];
191 Function * CDSAtomicInit[kNumberOfAccessSizes];
192 Function * CDSAtomicLoad[kNumberOfAccessSizes];
193 Function * CDSAtomicStore[kNumberOfAccessSizes];
194 Function * CDSAtomicRMW[AtomicRMWInst::LAST_BINOP + 1][kNumberOfAccessSizes];
195 Function * CDSAtomicCAS_V1[kNumberOfAccessSizes];
196 Function * CDSAtomicCAS_V2[kNumberOfAccessSizes];
197 Function * CDSAtomicThreadFence;
198 Function * CDSCtorFunction;
200 std::vector<StringRef> AtomicFuncNames;
201 std::vector<StringRef> PartialAtomicFuncNames;
205 StringRef CDSPass::getPassName() const {
209 void CDSPass::initializeCallbacks(Module &M) {
210 LLVMContext &Ctx = M.getContext();
212 Type * Int1Ty = Type::getInt1Ty(Ctx);
213 OrdTy = Type::getInt32Ty(Ctx);
215 Int8PtrTy = Type::getInt8PtrTy(Ctx);
216 Int16PtrTy = Type::getInt16PtrTy(Ctx);
217 Int32PtrTy = Type::getInt32PtrTy(Ctx);
218 Int64PtrTy = Type::getInt64PtrTy(Ctx);
220 VoidTy = Type::getVoidTy(Ctx);
222 CDSFuncEntry = checkCDSPassInterfaceFunction(
223 M.getOrInsertFunction("cds_func_entry",
225 CDSFuncExit = checkCDSPassInterfaceFunction(
226 M.getOrInsertFunction("cds_func_exit",
229 // Get the function to call from our untime library.
230 for (unsigned i = 0; i < kNumberOfAccessSizes; i++) {
231 const unsigned ByteSize = 1U << i;
232 const unsigned BitSize = ByteSize * 8;
234 std::string ByteSizeStr = utostr(ByteSize);
235 std::string BitSizeStr = utostr(BitSize);
237 Type *Ty = Type::getIntNTy(Ctx, BitSize);
238 Type *PtrTy = Ty->getPointerTo();
240 // uint8_t cds_atomic_load8 (void * obj, int atomic_index)
241 // void cds_atomic_store8 (void * obj, int atomic_index, uint8_t val)
242 SmallString<32> LoadName("cds_load" + BitSizeStr);
243 SmallString<32> StoreName("cds_store" + BitSizeStr);
244 SmallString<32> VolatileLoadName("cds_volatile_load" + BitSizeStr);
245 SmallString<32> VolatileStoreName("cds_volatile_store" + BitSizeStr);
246 SmallString<32> AtomicInitName("cds_atomic_init" + BitSizeStr);
247 SmallString<32> AtomicLoadName("cds_atomic_load" + BitSizeStr);
248 SmallString<32> AtomicStoreName("cds_atomic_store" + BitSizeStr);
250 CDSLoad[i] = checkCDSPassInterfaceFunction(
251 M.getOrInsertFunction(LoadName, VoidTy, PtrTy));
252 CDSStore[i] = checkCDSPassInterfaceFunction(
253 M.getOrInsertFunction(StoreName, VoidTy, PtrTy));
254 CDSVolatileLoad[i] = checkCDSPassInterfaceFunction(
255 M.getOrInsertFunction(VolatileLoadName,
256 Ty, PtrTy, Int8PtrTy));
257 CDSVolatileStore[i] = checkCDSPassInterfaceFunction(
258 M.getOrInsertFunction(VolatileStoreName,
259 VoidTy, PtrTy, Ty, Int8PtrTy));
260 CDSAtomicInit[i] = checkCDSPassInterfaceFunction(
261 M.getOrInsertFunction(AtomicInitName,
262 VoidTy, PtrTy, Ty, Int8PtrTy));
263 CDSAtomicLoad[i] = checkCDSPassInterfaceFunction(
264 M.getOrInsertFunction(AtomicLoadName,
265 Ty, PtrTy, OrdTy, Int8PtrTy));
266 CDSAtomicStore[i] = checkCDSPassInterfaceFunction(
267 M.getOrInsertFunction(AtomicStoreName,
268 VoidTy, PtrTy, Ty, OrdTy, Int8PtrTy));
270 for (int op = AtomicRMWInst::FIRST_BINOP;
271 op <= AtomicRMWInst::LAST_BINOP; ++op) {
272 CDSAtomicRMW[op][i] = nullptr;
273 std::string NamePart;
275 if (op == AtomicRMWInst::Xchg)
276 NamePart = "_exchange";
277 else if (op == AtomicRMWInst::Add)
278 NamePart = "_fetch_add";
279 else if (op == AtomicRMWInst::Sub)
280 NamePart = "_fetch_sub";
281 else if (op == AtomicRMWInst::And)
282 NamePart = "_fetch_and";
283 else if (op == AtomicRMWInst::Or)
284 NamePart = "_fetch_or";
285 else if (op == AtomicRMWInst::Xor)
286 NamePart = "_fetch_xor";
290 SmallString<32> AtomicRMWName("cds_atomic" + NamePart + BitSizeStr);
291 CDSAtomicRMW[op][i] = checkCDSPassInterfaceFunction(
292 M.getOrInsertFunction(AtomicRMWName,
293 Ty, PtrTy, Ty, OrdTy, Int8PtrTy));
296 // only supportes strong version
297 SmallString<32> AtomicCASName_V1("cds_atomic_compare_exchange" + BitSizeStr + "_v1");
298 SmallString<32> AtomicCASName_V2("cds_atomic_compare_exchange" + BitSizeStr + "_v2");
299 CDSAtomicCAS_V1[i] = checkCDSPassInterfaceFunction(
300 M.getOrInsertFunction(AtomicCASName_V1,
301 Ty, PtrTy, Ty, Ty, OrdTy, OrdTy, Int8PtrTy));
302 CDSAtomicCAS_V2[i] = checkCDSPassInterfaceFunction(
303 M.getOrInsertFunction(AtomicCASName_V2,
304 Int1Ty, PtrTy, PtrTy, Ty, OrdTy, OrdTy, Int8PtrTy));
307 CDSAtomicThreadFence = checkCDSPassInterfaceFunction(
308 M.getOrInsertFunction("cds_atomic_thread_fence",
309 VoidTy, OrdTy, Int8PtrTy));
312 bool CDSPass::doInitialization(Module &M) {
313 const DataLayout &DL = M.getDataLayout();
314 IntPtrTy = DL.getIntPtrType(M.getContext());
316 // createSanitizerCtorAndInitFunctions is defined in "llvm/Transforms/Utils/ModuleUtils.h"
317 // We do not support it yet
319 std::tie(CDSCtorFunction, std::ignore) = createSanitizerCtorAndInitFunctions(
320 M, kCDSModuleCtorName, kCDSInitName, {}, {});
322 appendToGlobalCtors(M, CDSCtorFunction, 0);
327 "atomic_init", "atomic_load", "atomic_store",
328 "atomic_fetch_", "atomic_exchange", "atomic_compare_exchange_"
331 PartialAtomicFuncNames =
333 "load", "store", "fetch", "exchange", "compare_exchange_"
339 static bool isVtableAccess(Instruction *I) {
340 if (MDNode *Tag = I->getMetadata(LLVMContext::MD_tbaa))
341 return Tag->isTBAAVtableAccess();
345 // Do not instrument known races/"benign races" that come from compiler
346 // instrumentatin. The user has no way of suppressing them.
347 static bool shouldInstrumentReadWriteFromAddress(const Module *M, Value *Addr) {
348 // Peel off GEPs and BitCasts.
349 Addr = Addr->stripInBoundsOffsets();
351 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
352 if (GV->hasSection()) {
353 StringRef SectionName = GV->getSection();
354 // Check if the global is in the PGO counters section.
355 auto OF = Triple(M->getTargetTriple()).getObjectFormat();
356 if (SectionName.endswith(
357 getInstrProfSectionName(IPSK_cnts, OF, /*AddSegmentInfo=*/false)))
361 // Check if the global is private gcov data.
362 if (GV->getName().startswith("__llvm_gcov") ||
363 GV->getName().startswith("__llvm_gcda"))
367 // Do not instrument acesses from different address spaces; we cannot deal
370 Type *PtrTy = cast<PointerType>(Addr->getType()->getScalarType());
371 if (PtrTy->getPointerAddressSpace() != 0)
378 bool CDSPass::addrPointsToConstantData(Value *Addr) {
379 // If this is a GEP, just analyze its pointer operand.
380 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr))
381 Addr = GEP->getPointerOperand();
383 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
384 if (GV->isConstant()) {
385 // Reads from constant globals can not race with any writes.
386 NumOmittedReadsFromConstantGlobals++;
389 } else if (LoadInst *L = dyn_cast<LoadInst>(Addr)) {
390 if (isVtableAccess(L)) {
391 // Reads from a vtable pointer can not race with any writes.
392 NumOmittedReadsFromVtable++;
399 void CDSPass::chooseInstructionsToInstrument(
400 SmallVectorImpl<Instruction *> &Local, SmallVectorImpl<Instruction *> &All,
401 const DataLayout &DL) {
402 SmallPtrSet<Value*, 8> WriteTargets;
403 // Iterate from the end.
404 for (Instruction *I : reverse(Local)) {
405 if (StoreInst *Store = dyn_cast<StoreInst>(I)) {
406 Value *Addr = Store->getPointerOperand();
407 if (!shouldInstrumentReadWriteFromAddress(I->getModule(), Addr))
409 WriteTargets.insert(Addr);
411 LoadInst *Load = cast<LoadInst>(I);
412 Value *Addr = Load->getPointerOperand();
413 if (!shouldInstrumentReadWriteFromAddress(I->getModule(), Addr))
415 if (WriteTargets.count(Addr)) {
416 // We will write to this temp, so no reason to analyze the read.
417 NumOmittedReadsBeforeWrite++;
420 if (addrPointsToConstantData(Addr)) {
421 // Addr points to some constant data -- it can not race with any writes.
425 Value *Addr = isa<StoreInst>(*I)
426 ? cast<StoreInst>(I)->getPointerOperand()
427 : cast<LoadInst>(I)->getPointerOperand();
428 if (isa<AllocaInst>(GetUnderlyingObject(Addr, DL)) &&
429 !PointerMayBeCaptured(Addr, true, true)) {
430 // The variable is addressable but not captured, so it cannot be
431 // referenced from a different thread and participate in a data race
432 // (see llvm/Analysis/CaptureTracking.h for details).
433 NumOmittedNonCaptured++;
442 void CDSPass::InsertRuntimeIgnores(Function &F) {
443 IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
444 IRB.CreateCall(CDSIgnoreBegin);
445 EscapeEnumerator EE(F, "cds_ignore_cleanup", ClHandleCxxExceptions);
446 while (IRBuilder<> *AtExit = EE.Next()) {
447 AtExit->CreateCall(CDSIgnoreEnd);
451 bool CDSPass::runOnFunction(Function &F) {
452 if (F.getName() == "main") {
453 F.setName("user_main");
454 errs() << "main replaced by user_main\n";
457 initializeCallbacks( *F.getParent() );
458 SmallVector<Instruction*, 8> AllLoadsAndStores;
459 SmallVector<Instruction*, 8> LocalLoadsAndStores;
460 SmallVector<Instruction*, 8> VolatileLoadsAndStores;
461 SmallVector<Instruction*, 8> AtomicAccesses;
464 bool HasCall = false;
465 bool HasAtomic = false;
466 bool HasVolatile = false;
467 const DataLayout &DL = F.getParent()->getDataLayout();
470 for (auto &Inst : BB) {
471 if ( (&Inst)->isAtomic() || isAtomicCall(&Inst) ) {
472 AtomicAccesses.push_back(&Inst);
474 } else if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst)) {
475 LoadInst *LI = dyn_cast<LoadInst>(&Inst);
476 StoreInst *SI = dyn_cast<StoreInst>(&Inst);
477 bool isVolatile = ( LI ? LI->isVolatile() : SI->isVolatile() );
480 VolatileLoadsAndStores.push_back(&Inst);
483 LocalLoadsAndStores.push_back(&Inst);
484 } else if (isa<CallInst>(Inst) || isa<InvokeInst>(Inst)) {
486 if (CallInst *CI = dyn_cast<CallInst>(&Inst))
487 maybeMarkSanitizerLibraryCallNoBuiltin(CI, TLI);
488 if (isa<MemIntrinsic>(Inst))
489 MemIntrinCalls.push_back(&Inst);
491 chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores,
497 chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores, DL);
500 for (auto Inst : AllLoadsAndStores) {
501 Res |= instrumentLoadOrStore(Inst, DL);
504 for (auto Inst : VolatileLoadsAndStores) {
505 Res |= instrumentVolatile(Inst, DL);
508 for (auto Inst : AtomicAccesses) {
509 Res |= instrumentAtomic(Inst, DL);
513 for (auto Inst : MemIntrinCalls) {
514 Res |= instrumentMemIntrinsic(Inst);
518 // Only instrument functions that contain atomics or volatiles
519 if (Res && ( HasAtomic || HasVolatile) ) {
520 IRBuilder<> IRB(F.getEntryBlock().getFirstNonPHI());
522 Value *ReturnAddress = IRB.CreateCall(
523 Intrinsic::getDeclaration(F.getParent(), Intrinsic::returnaddress),
527 Value * FuncName = IRB.CreateGlobalStringPtr(F.getName());
528 IRB.CreateCall(CDSFuncEntry, FuncName);
530 EscapeEnumerator EE(F, "cds_cleanup", true);
531 while (IRBuilder<> *AtExit = EE.Next()) {
532 AtExit->CreateCall(CDSFuncExit, FuncName);
541 bool CDSPass::instrumentLoadOrStore(Instruction *I,
542 const DataLayout &DL) {
544 bool IsWrite = isa<StoreInst>(*I);
545 Value *Addr = IsWrite
546 ? cast<StoreInst>(I)->getPointerOperand()
547 : cast<LoadInst>(I)->getPointerOperand();
549 // swifterror memory addresses are mem2reg promoted by instruction selection.
550 // As such they cannot have regular uses like an instrumentation function and
551 // it makes no sense to track them as memory.
552 if (Addr->isSwiftError())
555 int Idx = getMemoryAccessFuncIndex(Addr, DL);
559 // not supported by CDS yet
560 /* if (IsWrite && isVtableAccess(I)) {
561 LLVM_DEBUG(dbgs() << " VPTR : " << *I << "\n");
562 Value *StoredValue = cast<StoreInst>(I)->getValueOperand();
563 // StoredValue may be a vector type if we are storing several vptrs at once.
564 // In this case, just take the first element of the vector since this is
565 // enough to find vptr races.
566 if (isa<VectorType>(StoredValue->getType()))
567 StoredValue = IRB.CreateExtractElement(
568 StoredValue, ConstantInt::get(IRB.getInt32Ty(), 0));
569 if (StoredValue->getType()->isIntegerTy())
570 StoredValue = IRB.CreateIntToPtr(StoredValue, IRB.getInt8PtrTy());
571 // Call TsanVptrUpdate.
572 IRB.CreateCall(TsanVptrUpdate,
573 {IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()),
574 IRB.CreatePointerCast(StoredValue, IRB.getInt8PtrTy())});
575 NumInstrumentedVtableWrites++;
579 if (!IsWrite && isVtableAccess(I)) {
580 IRB.CreateCall(TsanVptrLoad,
581 IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()));
582 NumInstrumentedVtableReads++;
587 Value *OnAccessFunc = nullptr;
588 OnAccessFunc = IsWrite ? CDSStore[Idx] : CDSLoad[Idx];
590 Type *ArgType = IRB.CreatePointerCast(Addr, Addr->getType())->getType();
592 if ( ArgType != Int8PtrTy && ArgType != Int16PtrTy &&
593 ArgType != Int32PtrTy && ArgType != Int64PtrTy ) {
594 // if other types of load or stores are passed in
598 IRB.CreateCall(OnAccessFunc, IRB.CreatePointerCast(Addr, Addr->getType()));
599 if (IsWrite) NumInstrumentedWrites++;
600 else NumInstrumentedReads++;
604 bool CDSPass::instrumentVolatile(Instruction * I, const DataLayout &DL) {
606 Value *position = getPosition(I, IRB);
608 if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
609 assert( LI->isVolatile() );
610 Value *Addr = LI->getPointerOperand();
611 int Idx=getMemoryAccessFuncIndex(Addr, DL);
615 Value *args[] = {Addr, position};
616 Instruction* funcInst = CallInst::Create(CDSVolatileLoad[Idx], args);
617 ReplaceInstWithInst(LI, funcInst);
618 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
619 assert( SI->isVolatile() );
620 Value *Addr = SI->getPointerOperand();
621 int Idx=getMemoryAccessFuncIndex(Addr, DL);
625 Value *val = SI->getValueOperand();
626 Value *args[] = {Addr, val, position};
627 Instruction* funcInst = CallInst::Create(CDSVolatileStore[Idx], args);
628 ReplaceInstWithInst(SI, funcInst);
636 bool CDSPass::instrumentAtomic(Instruction * I, const DataLayout &DL) {
639 if (auto *CI = dyn_cast<CallInst>(I)) {
640 return instrumentAtomicCall(CI, DL);
643 Value *position = getPosition(I, IRB);
645 if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
646 Value *Addr = LI->getPointerOperand();
647 int Idx=getMemoryAccessFuncIndex(Addr, DL);
651 int atomic_order_index = getAtomicOrderIndex(LI->getOrdering());
652 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
653 Value *args[] = {Addr, order, position};
654 Instruction* funcInst = CallInst::Create(CDSAtomicLoad[Idx], args);
655 ReplaceInstWithInst(LI, funcInst);
656 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
657 Value *Addr = SI->getPointerOperand();
658 int Idx=getMemoryAccessFuncIndex(Addr, DL);
662 int atomic_order_index = getAtomicOrderIndex(SI->getOrdering());
663 Value *val = SI->getValueOperand();
664 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
665 Value *args[] = {Addr, val, order, position};
666 Instruction* funcInst = CallInst::Create(CDSAtomicStore[Idx], args);
667 ReplaceInstWithInst(SI, funcInst);
668 } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I)) {
669 Value *Addr = RMWI->getPointerOperand();
670 int Idx=getMemoryAccessFuncIndex(Addr, DL);
674 int atomic_order_index = getAtomicOrderIndex(RMWI->getOrdering());
675 Value *val = RMWI->getValOperand();
676 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
677 Value *args[] = {Addr, val, order, position};
678 Instruction* funcInst = CallInst::Create(CDSAtomicRMW[RMWI->getOperation()][Idx], args);
679 ReplaceInstWithInst(RMWI, funcInst);
680 } else if (AtomicCmpXchgInst *CASI = dyn_cast<AtomicCmpXchgInst>(I)) {
681 IRBuilder<> IRB(CASI);
683 Value *Addr = CASI->getPointerOperand();
684 int Idx=getMemoryAccessFuncIndex(Addr, DL);
688 const unsigned ByteSize = 1U << Idx;
689 const unsigned BitSize = ByteSize * 8;
690 Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
691 Type *PtrTy = Ty->getPointerTo();
693 Value *CmpOperand = IRB.CreateBitOrPointerCast(CASI->getCompareOperand(), Ty);
694 Value *NewOperand = IRB.CreateBitOrPointerCast(CASI->getNewValOperand(), Ty);
696 int atomic_order_index_succ = getAtomicOrderIndex(CASI->getSuccessOrdering());
697 int atomic_order_index_fail = getAtomicOrderIndex(CASI->getFailureOrdering());
698 Value *order_succ = ConstantInt::get(OrdTy, atomic_order_index_succ);
699 Value *order_fail = ConstantInt::get(OrdTy, atomic_order_index_fail);
701 Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
702 CmpOperand, NewOperand,
703 order_succ, order_fail, position};
705 CallInst *funcInst = IRB.CreateCall(CDSAtomicCAS_V1[Idx], Args);
706 Value *Success = IRB.CreateICmpEQ(funcInst, CmpOperand);
708 Value *OldVal = funcInst;
709 Type *OrigOldValTy = CASI->getNewValOperand()->getType();
710 if (Ty != OrigOldValTy) {
711 // The value is a pointer, so we need to cast the return value.
712 OldVal = IRB.CreateIntToPtr(funcInst, OrigOldValTy);
716 IRB.CreateInsertValue(UndefValue::get(CASI->getType()), OldVal, 0);
717 Res = IRB.CreateInsertValue(Res, Success, 1);
719 I->replaceAllUsesWith(Res);
720 I->eraseFromParent();
721 } else if (FenceInst *FI = dyn_cast<FenceInst>(I)) {
722 int atomic_order_index = getAtomicOrderIndex(FI->getOrdering());
723 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
724 Value *Args[] = {order, position};
726 CallInst *funcInst = CallInst::Create(CDSAtomicThreadFence, Args);
727 ReplaceInstWithInst(FI, funcInst);
728 // errs() << "Thread Fences replaced\n";
733 bool CDSPass::isAtomicCall(Instruction *I) {
734 if ( auto *CI = dyn_cast<CallInst>(I) ) {
735 Function *fun = CI->getCalledFunction();
739 StringRef funName = fun->getName();
741 // todo: come up with better rules for function name checking
742 for (StringRef name : AtomicFuncNames) {
743 if ( funName.contains(name) )
747 for (StringRef PartialName : PartialAtomicFuncNames) {
748 if (funName.contains(PartialName) &&
749 funName.contains("atomic") )
757 bool CDSPass::instrumentAtomicCall(CallInst *CI, const DataLayout &DL) {
759 Function *fun = CI->getCalledFunction();
760 StringRef funName = fun->getName();
761 std::vector<Value *> parameters;
763 User::op_iterator begin = CI->arg_begin();
764 User::op_iterator end = CI->arg_end();
765 for (User::op_iterator it = begin; it != end; ++it) {
767 parameters.push_back(param);
770 // obtain source line number of the CallInst
771 Value *position = getPosition(CI, IRB);
773 // the pointer to the address is always the first argument
774 Value *OrigPtr = parameters[0];
776 int Idx = getMemoryAccessFuncIndex(OrigPtr, DL);
780 const unsigned ByteSize = 1U << Idx;
781 const unsigned BitSize = ByteSize * 8;
782 Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
783 Type *PtrTy = Ty->getPointerTo();
785 // atomic_init; args = {obj, order}
786 if (funName.contains("atomic_init")) {
787 Value *OrigVal = parameters[1];
789 Value *ptr = IRB.CreatePointerCast(OrigPtr, PtrTy);
791 if (OrigVal->getType()->isPtrOrPtrVectorTy())
792 val = IRB.CreatePointerCast(OrigVal, Ty);
794 val = IRB.CreateIntCast(OrigVal, Ty, true);
796 Value *args[] = {ptr, val, position};
798 Instruction* funcInst = CallInst::Create(CDSAtomicInit[Idx], args);
799 ReplaceInstWithInst(CI, funcInst);
804 // atomic_load; args = {obj, order}
805 if (funName.contains("atomic_load")) {
806 bool isExplicit = funName.contains("atomic_load_explicit");
808 Value *ptr = IRB.CreatePointerCast(OrigPtr, PtrTy);
811 order = IRB.CreateBitOrPointerCast(parameters[1], OrdTy);
813 order = ConstantInt::get(OrdTy,
814 (int) AtomicOrderingCABI::seq_cst);
815 Value *args[] = {ptr, order, position};
817 Instruction* funcInst = CallInst::Create(CDSAtomicLoad[Idx], args);
818 ReplaceInstWithInst(CI, funcInst);
821 } else if (funName.contains("atomic") &&
822 funName.contains("load") ) {
823 // does this version of call always have an atomic order as an argument?
824 Value *ptr = IRB.CreatePointerCast(OrigPtr, PtrTy);
825 Value *order = IRB.CreateBitOrPointerCast(parameters[1], OrdTy);
826 Value *args[] = {ptr, order, position};
828 if (!CI->getType()->isPointerTy()) {
832 CallInst *funcInst = IRB.CreateCall(CDSAtomicLoad[Idx], args);
833 Value *RetVal = IRB.CreateIntToPtr(funcInst, CI->getType());
835 CI->replaceAllUsesWith(RetVal);
836 CI->eraseFromParent();
841 // atomic_store; args = {obj, val, order}
842 if (funName.contains("atomic_store")) {
843 bool isExplicit = funName.contains("atomic_store_explicit");
844 Value *OrigVal = parameters[1];
846 Value *ptr = IRB.CreatePointerCast(OrigPtr, PtrTy);
847 Value *val = IRB.CreatePointerCast(OrigVal, Ty);
850 order = IRB.CreateBitOrPointerCast(parameters[2], OrdTy);
852 order = ConstantInt::get(OrdTy,
853 (int) AtomicOrderingCABI::seq_cst);
854 Value *args[] = {ptr, val, order, position};
856 Instruction* funcInst = CallInst::Create(CDSAtomicStore[Idx], args);
857 ReplaceInstWithInst(CI, funcInst);
860 } else if (funName.contains("atomic") &&
861 funName.contains("store") ) {
862 // does this version of call always have an atomic order as an argument?
863 Value *OrigVal = parameters[1];
865 Value *ptr = IRB.CreatePointerCast(OrigPtr, PtrTy);
867 if (OrigVal->getType()->isPtrOrPtrVectorTy())
868 val = IRB.CreatePointerCast(OrigVal, Ty);
870 val = IRB.CreateIntCast(OrigVal, Ty, true);
872 Value *order = IRB.CreateBitOrPointerCast(parameters[2], OrdTy);
873 Value *args[] = {ptr, val, order, position};
875 Instruction* funcInst = CallInst::Create(CDSAtomicStore[Idx], args);
876 ReplaceInstWithInst(CI, funcInst);
881 // atomic_fetch_*; args = {obj, val, order}
882 if (funName.contains("atomic_fetch_") ||
883 funName.contains("atomic_exchange")) {
885 /* TODO: implement stricter function name checking */
886 if (funName.contains("non"))
889 bool isExplicit = funName.contains("_explicit");
890 Value *OrigVal = parameters[1];
893 if ( funName.contains("_fetch_add") )
894 op = AtomicRMWInst::Add;
895 else if ( funName.contains("_fetch_sub") )
896 op = AtomicRMWInst::Sub;
897 else if ( funName.contains("_fetch_and") )
898 op = AtomicRMWInst::And;
899 else if ( funName.contains("_fetch_or") )
900 op = AtomicRMWInst::Or;
901 else if ( funName.contains("_fetch_xor") )
902 op = AtomicRMWInst::Xor;
903 else if ( funName.contains("atomic_exchange") )
904 op = AtomicRMWInst::Xchg;
906 errs() << "Unknown atomic read-modify-write operation\n";
910 Value *ptr = IRB.CreatePointerCast(OrigPtr, PtrTy);
912 if (OrigVal->getType()->isPtrOrPtrVectorTy())
913 val = IRB.CreatePointerCast(OrigVal, Ty);
915 val = IRB.CreateIntCast(OrigVal, Ty, true);
919 order = IRB.CreateBitOrPointerCast(parameters[2], OrdTy);
921 order = ConstantInt::get(OrdTy,
922 (int) AtomicOrderingCABI::seq_cst);
923 Value *args[] = {ptr, val, order, position};
925 Instruction* funcInst = CallInst::Create(CDSAtomicRMW[op][Idx], args);
926 ReplaceInstWithInst(CI, funcInst);
929 } else if (funName.contains("fetch")) {
930 errs() << "atomic fetch captured. Not implemented yet. ";
931 errs() << "See source file :";
932 getPosition(CI, IRB, true);
934 } else if (funName.contains("exchange") &&
935 !funName.contains("compare_exchange") ) {
936 if (CI->getType()->isPointerTy()) {
937 // Can not deal with this now
938 errs() << "atomic exchange captured. Not implemented yet. ";
939 errs() << "See source file :";
940 getPosition(CI, IRB, true);
945 Value *OrigVal = parameters[1];
947 Value *ptr = IRB.CreatePointerCast(OrigPtr, PtrTy);
949 if (OrigVal->getType()->isPtrOrPtrVectorTy())
950 val = IRB.CreatePointerCast(OrigVal, Ty);
952 val = IRB.CreateIntCast(OrigVal, Ty, true);
954 Value *order = IRB.CreateBitOrPointerCast(parameters[2], OrdTy);
955 Value *args[] = {ptr, val, order, position};
956 int op = AtomicRMWInst::Xchg;
958 Instruction* funcInst = CallInst::Create(CDSAtomicRMW[op][Idx], args);
959 ReplaceInstWithInst(CI, funcInst);
962 /* atomic_compare_exchange_*;
963 args = {obj, expected, new value, order1, order2}
965 if ( funName.contains("atomic_compare_exchange_") ) {
966 bool isExplicit = funName.contains("_explicit");
968 Value *Addr = IRB.CreatePointerCast(OrigPtr, PtrTy);
969 Value *CmpOperand = IRB.CreatePointerCast(parameters[1], PtrTy);
970 Value *NewOperand = IRB.CreateBitOrPointerCast(parameters[2], Ty);
972 Value *order_succ, *order_fail;
974 order_succ = IRB.CreateBitOrPointerCast(parameters[3], OrdTy);
976 if (parameters.size() > 4) {
977 order_fail = IRB.CreateBitOrPointerCast(parameters[4], OrdTy);
979 /* The failure order is not provided */
980 order_fail = order_succ;
981 ConstantInt * order_succ_cast = dyn_cast<ConstantInt>(order_succ);
982 int index = order_succ_cast->getSExtValue();
984 order_fail = ConstantInt::get(OrdTy,
985 AtomicCasFailureOrderIndex(index));
988 order_succ = ConstantInt::get(OrdTy,
989 (int) AtomicOrderingCABI::seq_cst);
990 order_fail = ConstantInt::get(OrdTy,
991 (int) AtomicOrderingCABI::seq_cst);
994 Value *args[] = {Addr, CmpOperand, NewOperand,
995 order_succ, order_fail, position};
997 Instruction* funcInst = CallInst::Create(CDSAtomicCAS_V2[Idx], args);
998 ReplaceInstWithInst(CI, funcInst);
1001 } else if ( funName.contains("compare_exchange_strong") ||
1002 funName.contains("compare_exchange_weak") ) {
1003 Value *Addr = IRB.CreatePointerCast(OrigPtr, PtrTy);
1004 Value *CmpOperand = IRB.CreatePointerCast(parameters[1], PtrTy);
1005 Value *NewOperand = IRB.CreateBitOrPointerCast(parameters[2], Ty);
1007 Value *order_succ, *order_fail;
1008 order_succ = IRB.CreateBitOrPointerCast(parameters[3], OrdTy);
1010 if (parameters.size() > 4) {
1011 order_fail = IRB.CreateBitOrPointerCast(parameters[4], OrdTy);
1013 /* The failure order is not provided */
1014 order_fail = order_succ;
1015 ConstantInt * order_succ_cast = dyn_cast<ConstantInt>(order_succ);
1016 int index = order_succ_cast->getSExtValue();
1018 order_fail = ConstantInt::get(OrdTy,
1019 AtomicCasFailureOrderIndex(index));
1022 Value *args[] = {Addr, CmpOperand, NewOperand,
1023 order_succ, order_fail, position};
1024 Instruction* funcInst = CallInst::Create(CDSAtomicCAS_V2[Idx], args);
1025 ReplaceInstWithInst(CI, funcInst);
1033 int CDSPass::getMemoryAccessFuncIndex(Value *Addr,
1034 const DataLayout &DL) {
1035 Type *OrigPtrTy = Addr->getType();
1036 Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType();
1037 assert(OrigTy->isSized());
1038 uint32_t TypeSize = DL.getTypeStoreSizeInBits(OrigTy);
1039 if (TypeSize != 8 && TypeSize != 16 &&
1040 TypeSize != 32 && TypeSize != 64 && TypeSize != 128) {
1041 NumAccessesWithBadSize++;
1042 // Ignore all unusual sizes.
1045 size_t Idx = countTrailingZeros(TypeSize / 8);
1046 //assert(Idx < kNumberOfAccessSizes);
1047 if (Idx >= kNumberOfAccessSizes) {
1054 char CDSPass::ID = 0;
1056 // Automatically enable the pass.
1057 static void registerCDSPass(const PassManagerBuilder &,
1058 legacy::PassManagerBase &PM) {
1059 PM.add(new CDSPass());
1062 /* Enable the pass when opt level is greater than 0 */
1063 static RegisterStandardPasses
1064 RegisterMyPass1(PassManagerBuilder::EP_OptimizerLast,
1067 /* Enable the pass when opt level is 0 */
1068 static RegisterStandardPasses
1069 RegisterMyPass2(PassManagerBuilder::EP_EnabledOnOptLevel0,