1 //===-- CDSPass.cpp - xxx -------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file is a modified version of ThreadSanitizer.cpp, a part of a race detector.
12 // The tool is under development, for the details about previous versions see
13 // http://code.google.com/p/data-race-test
15 // The instrumentation phase is quite simple:
16 // - Insert calls to run-time library before every memory access.
17 // - Optimizations may apply to avoid instrumenting some of the accesses.
18 // - Insert calls at function entry/exit.
19 // The rest is handled by the run-time library.
20 //===----------------------------------------------------------------------===//
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/ADT/StringExtras.h"
24 #include "llvm/ADT/SmallString.h"
25 #include "llvm/Analysis/ValueTracking.h"
26 #include "llvm/Analysis/CaptureTracking.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/CFG.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/Local.h"
43 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
44 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
47 // #include "llvm/Support/MathExtras.h"
49 #define DEBUG_TYPE "CDS"
52 #define FUNCARRAYSIZE 4
54 STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
55 STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
56 // STATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes");
57 // STATISTIC(NumInstrumentedVtableReads, "Number of vtable ptr reads");
59 STATISTIC(NumOmittedReadsBeforeWrite,
60 "Number of reads ignored due to following writes");
61 STATISTIC(NumOmittedReadsFromConstantGlobals,
62 "Number of reads from constant globals");
63 STATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads");
64 STATISTIC(NumOmittedNonCaptured, "Number of accesses ignored due to capturing");
79 Constant * CDSLoad[FUNCARRAYSIZE];
80 Constant * CDSStore[FUNCARRAYSIZE];
81 Constant * CDSAtomicLoad[FUNCARRAYSIZE];
82 Constant * CDSAtomicStore[FUNCARRAYSIZE];
83 Constant * CDSAtomicRMW[AtomicRMWInst::LAST_BINOP + 1][FUNCARRAYSIZE];
84 Constant * CDSAtomicCAS[FUNCARRAYSIZE];
85 Constant * CDSAtomicThreadFence;
89 int getAtomicOrderIndex(AtomicOrdering order){
91 case AtomicOrdering::Monotonic:
92 return (int)AtomicOrderingCABI::relaxed;
93 // case AtomicOrdering::Consume: // not specified yet
94 // return AtomicOrderingCABI::consume;
95 case AtomicOrdering::Acquire:
96 return (int)AtomicOrderingCABI::acquire;
97 case AtomicOrdering::Release:
98 return (int)AtomicOrderingCABI::release;
99 case AtomicOrdering::AcquireRelease:
100 return (int)AtomicOrderingCABI::acq_rel;
101 case AtomicOrdering::SequentiallyConsistent:
102 return (int)AtomicOrderingCABI::seq_cst;
104 // unordered or Not Atomic
109 int getTypeSize(Type* type) {
110 if (type==Int32PtrTy) {
111 return sizeof(int)*8;
112 } else if (type==Int8PtrTy) {
113 return sizeof(char)*8;
114 } else if (type==Int16PtrTy) {
115 return sizeof(short)*8;
116 } else if (type==Int64PtrTy) {
117 return sizeof(long long int)*8;
119 return sizeof(void*)*8;
125 static int sizetoindex(int size) {
136 struct CDSPass : public FunctionPass {
138 CDSPass() : FunctionPass(ID) {}
139 bool runOnFunction(Function &F) override;
142 void initializeCallbacks(Module &M);
143 bool instrumentLoadOrStore(Instruction *I, const DataLayout &DL);
144 bool instrumentAtomic(Instruction *I);
145 void chooseInstructionsToInstrument(SmallVectorImpl<Instruction *> &Local,
146 SmallVectorImpl<Instruction *> &All,
147 const DataLayout &DL);
148 bool addrPointsToConstantData(Value *Addr);
152 void CDSPass::initializeCallbacks(Module &M) {
153 LLVMContext &Ctx = M.getContext();
155 Int8Ty = Type::getInt8Ty(Ctx);
156 Int16Ty = Type::getInt16Ty(Ctx);
157 Int32Ty = Type::getInt32Ty(Ctx);
158 Int64Ty = Type::getInt64Ty(Ctx);
159 OrdTy = Type::getInt32Ty(Ctx);
161 Int8PtrTy = Type::getInt8PtrTy(Ctx);
162 Int16PtrTy = Type::getInt16PtrTy(Ctx);
163 Int32PtrTy = Type::getInt32PtrTy(Ctx);
164 Int64PtrTy = Type::getInt64PtrTy(Ctx);
166 VoidTy = Type::getVoidTy(Ctx);
169 // Get the function to call from our untime library.
170 for (unsigned i = 0; i < FUNCARRAYSIZE; i++) {
171 const unsigned ByteSize = 1U << i;
172 const unsigned BitSize = ByteSize * 8;
173 // errs() << BitSize << "\n";
174 std::string ByteSizeStr = utostr(ByteSize);
175 std::string BitSizeStr = utostr(BitSize);
177 Type *Ty = Type::getIntNTy(Ctx, BitSize);
178 Type *PtrTy = Ty->getPointerTo();
180 // uint8_t cds_atomic_load8 (void * obj, int atomic_index)
181 // void cds_atomic_store8 (void * obj, int atomic_index, uint8_t val)
182 SmallString<32> LoadName("cds_load" + BitSizeStr);
183 SmallString<32> StoreName("cds_store" + BitSizeStr);
184 SmallString<32> AtomicLoadName("cds_atomic_load" + BitSizeStr);
185 SmallString<32> AtomicStoreName("cds_atomic_store" + BitSizeStr);
187 CDSLoad[i] = M.getOrInsertFunction(LoadName, VoidTy, PtrTy);
188 CDSStore[i] = M.getOrInsertFunction(StoreName, VoidTy, PtrTy);
189 CDSAtomicLoad[i] = M.getOrInsertFunction(AtomicLoadName, Ty, PtrTy, OrdTy);
190 CDSAtomicStore[i] = M.getOrInsertFunction(AtomicStoreName, VoidTy, PtrTy, OrdTy, Ty);
192 for (int op = AtomicRMWInst::FIRST_BINOP; op <= AtomicRMWInst::LAST_BINOP; ++op) {
193 CDSAtomicRMW[op][i] = nullptr;
194 std::string NamePart;
196 if (op == AtomicRMWInst::Xchg)
197 NamePart = "_exchange";
198 else if (op == AtomicRMWInst::Add)
199 NamePart = "_fetch_add";
200 else if (op == AtomicRMWInst::Sub)
201 NamePart = "_fetch_sub";
202 else if (op == AtomicRMWInst::And)
203 NamePart = "_fetch_and";
204 else if (op == AtomicRMWInst::Or)
205 NamePart = "_fetch_or";
206 else if (op == AtomicRMWInst::Xor)
207 NamePart = "_fetch_xor";
211 SmallString<32> AtomicRMWName("cds_atomic" + NamePart + BitSizeStr);
212 CDSAtomicRMW[op][i] = M.getOrInsertFunction(AtomicRMWName, Ty, PtrTy, OrdTy, Ty);
215 // only supportes strong version
216 SmallString<32> AtomicCASName("cds_atomic_compare_exchange" + BitSizeStr);
217 CDSAtomicCAS[i] = M.getOrInsertFunction(AtomicCASName, Ty, PtrTy, Ty, Ty, OrdTy, OrdTy);
220 CDSAtomicThreadFence = M.getOrInsertFunction("cds_atomic_thread_fence", VoidTy, OrdTy);
223 static bool isVtableAccess(Instruction *I) {
224 if (MDNode *Tag = I->getMetadata(LLVMContext::MD_tbaa))
225 return Tag->isTBAAVtableAccess();
229 static bool shouldInstrumentReadWriteFromAddress(const Module *M, Value *Addr) {
230 // Peel off GEPs and BitCasts.
231 Addr = Addr->stripInBoundsOffsets();
233 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
234 if (GV->hasSection()) {
235 StringRef SectionName = GV->getSection();
236 // Check if the global is in the PGO counters section.
237 auto OF = Triple(M->getTargetTriple()).getObjectFormat();
238 if (SectionName.endswith(
239 getInstrProfSectionName(IPSK_cnts, OF, /*AddSegmentInfo=*/false)))
243 // Check if the global is private gcov data.
244 if (GV->getName().startswith("__llvm_gcov") ||
245 GV->getName().startswith("__llvm_gcda"))
249 // Do not instrument acesses from different address spaces; we cannot deal
252 Type *PtrTy = cast<PointerType>(Addr->getType()->getScalarType());
253 if (PtrTy->getPointerAddressSpace() != 0)
260 bool CDSPass::addrPointsToConstantData(Value *Addr) {
261 // If this is a GEP, just analyze its pointer operand.
262 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr))
263 Addr = GEP->getPointerOperand();
265 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
266 if (GV->isConstant()) {
267 // Reads from constant globals can not race with any writes.
268 NumOmittedReadsFromConstantGlobals++;
271 } else if (LoadInst *L = dyn_cast<LoadInst>(Addr)) {
272 if (isVtableAccess(L)) {
273 // Reads from a vtable pointer can not race with any writes.
274 NumOmittedReadsFromVtable++;
281 bool CDSPass::runOnFunction(Function &F) {
282 if (F.getName() == "main") {
283 F.setName("user_main");
284 // errs() << "main replaced by user_main\n";
289 initializeCallbacks( *F.getParent() );
291 SmallVector<Instruction*, 8> AllLoadsAndStores;
292 SmallVector<Instruction*, 8> LocalLoadsAndStores;
293 SmallVector<Instruction*, 8> AtomicAccesses;
295 std::vector<Instruction *> worklist;
298 const DataLayout &DL = F.getParent()->getDataLayout();
302 if ( (&I)->isAtomic() ) {
303 AtomicAccesses.push_back(&I);
304 } else if (isa<LoadInst>(I) || isa<StoreInst>(I)) {
305 LocalLoadsAndStores.push_back(&I);
306 } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
307 // not implemented yet
310 chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores, DL);
313 for (auto Inst : AllLoadsAndStores) {
314 // Res |= instrumentLoadOrStore(Inst, DL);
315 // errs() << "load and store are replaced\n";
318 for (auto Inst : AtomicAccesses) {
319 Res |= instrumentAtomic(Inst);
325 errs() << F.getName();
326 errs() << " has above instructions replaced\n";
333 void CDSPass::chooseInstructionsToInstrument(
334 SmallVectorImpl<Instruction *> &Local, SmallVectorImpl<Instruction *> &All,
335 const DataLayout &DL) {
336 SmallPtrSet<Value*, 8> WriteTargets;
337 // Iterate from the end.
338 for (Instruction *I : reverse(Local)) {
339 if (StoreInst *Store = dyn_cast<StoreInst>(I)) {
340 Value *Addr = Store->getPointerOperand();
341 if (!shouldInstrumentReadWriteFromAddress(I->getModule(), Addr))
343 WriteTargets.insert(Addr);
345 LoadInst *Load = cast<LoadInst>(I);
346 Value *Addr = Load->getPointerOperand();
347 if (!shouldInstrumentReadWriteFromAddress(I->getModule(), Addr))
349 if (WriteTargets.count(Addr)) {
350 // We will write to this temp, so no reason to analyze the read.
351 NumOmittedReadsBeforeWrite++;
354 if (addrPointsToConstantData(Addr)) {
355 // Addr points to some constant data -- it can not race with any writes.
359 Value *Addr = isa<StoreInst>(*I)
360 ? cast<StoreInst>(I)->getPointerOperand()
361 : cast<LoadInst>(I)->getPointerOperand();
362 if (isa<AllocaInst>(GetUnderlyingObject(Addr, DL)) &&
363 !PointerMayBeCaptured(Addr, true, true)) {
364 // The variable is addressable but not captured, so it cannot be
365 // referenced from a different thread and participate in a data race
366 // (see llvm/Analysis/CaptureTracking.h for details).
367 NumOmittedNonCaptured++;
376 bool CDSPass::instrumentLoadOrStore(Instruction *I,
377 const DataLayout &DL) {
379 bool IsWrite = isa<StoreInst>(*I);
380 Value *Addr = IsWrite
381 ? cast<StoreInst>(I)->getPointerOperand()
382 : cast<LoadInst>(I)->getPointerOperand();
384 // swifterror memory addresses are mem2reg promoted by instruction selection.
385 // As such they cannot have regular uses like an instrumentation function and
386 // it makes no sense to track them as memory.
387 if (Addr->isSwiftError())
390 int size = getTypeSize(Addr->getType());
391 int index = sizetoindex(size);
393 // not supported by CDS yet
394 /* if (IsWrite && isVtableAccess(I)) {
395 LLVM_DEBUG(dbgs() << " VPTR : " << *I << "\n");
396 Value *StoredValue = cast<StoreInst>(I)->getValueOperand();
397 // StoredValue may be a vector type if we are storing several vptrs at once.
398 // In this case, just take the first element of the vector since this is
399 // enough to find vptr races.
400 if (isa<VectorType>(StoredValue->getType()))
401 StoredValue = IRB.CreateExtractElement(
402 StoredValue, ConstantInt::get(IRB.getInt32Ty(), 0));
403 if (StoredValue->getType()->isIntegerTy())
404 StoredValue = IRB.CreateIntToPtr(StoredValue, IRB.getInt8PtrTy());
405 // Call TsanVptrUpdate.
406 IRB.CreateCall(TsanVptrUpdate,
407 {IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()),
408 IRB.CreatePointerCast(StoredValue, IRB.getInt8PtrTy())});
409 NumInstrumentedVtableWrites++;
413 if (!IsWrite && isVtableAccess(I)) {
414 IRB.CreateCall(TsanVptrLoad,
415 IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()));
416 NumInstrumentedVtableReads++;
421 Value *OnAccessFunc = nullptr;
422 OnAccessFunc = IsWrite ? CDSStore[index] : CDSLoad[index];
424 Type *ArgType = IRB.CreatePointerCast(Addr, Addr->getType())->getType();
426 if ( ArgType != Int8PtrTy && ArgType != Int16PtrTy &&
427 ArgType != Int32PtrTy && ArgType != Int64PtrTy ) {
428 //errs() << "A load or store of type ";
429 //errs() << *ArgType;
430 //errs() << " is passed in\n";
431 return false; // if other types of load or stores are passed in
433 IRB.CreateCall(OnAccessFunc, IRB.CreatePointerCast(Addr, Addr->getType()));
434 if (IsWrite) NumInstrumentedWrites++;
435 else NumInstrumentedReads++;
440 bool CDSPass::instrumentAtomic(Instruction * I) {
442 // LLVMContext &Ctx = IRB.getContext();
444 if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
445 int atomic_order_index = getAtomicOrderIndex(SI->getOrdering());
447 Value *val = SI->getValueOperand();
448 Value *ptr = SI->getPointerOperand();
449 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
450 Value *args[] = {ptr, order, val};
452 int size=getTypeSize(ptr->getType());
453 int index=sizetoindex(size);
455 Instruction* funcInst=CallInst::Create(CDSAtomicStore[index], args,"");
456 ReplaceInstWithInst(SI, funcInst);
457 // errs() << "Store replaced\n";
458 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
459 int atomic_order_index = getAtomicOrderIndex(LI->getOrdering());
461 Value *ptr = LI->getPointerOperand();
462 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
463 Value *args[] = {ptr, order};
465 int size=getTypeSize(ptr->getType());
466 int index=sizetoindex(size);
468 Instruction* funcInst=CallInst::Create(CDSAtomicLoad[index], args, "");
469 ReplaceInstWithInst(LI, funcInst);
470 // errs() << "Load Replaced\n";
471 } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I)) {
472 int atomic_order_index = getAtomicOrderIndex(RMWI->getOrdering());
474 Value *val = RMWI->getValOperand();
475 Value *ptr = RMWI->getPointerOperand();
476 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
477 Value *args[] = {ptr, order, val};
479 int size = getTypeSize(ptr->getType());
480 int index = sizetoindex(size);
482 Instruction* funcInst = CallInst::Create(CDSAtomicRMW[RMWI->getOperation()][index], args, "");
483 ReplaceInstWithInst(RMWI, funcInst);
484 // errs() << RMWI->getOperationName(RMWI->getOperation());
485 // errs() << " replaced\n";
486 } else if (AtomicCmpXchgInst *CASI = dyn_cast<AtomicCmpXchgInst>(I)) {
487 IRBuilder<> IRB(CASI);
489 Value *Addr = CASI->getPointerOperand();
491 int size = getTypeSize(Addr->getType());
492 int index = sizetoindex(size);
493 const unsigned ByteSize = 1U << index;
494 const unsigned BitSize = ByteSize * 8;
495 Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
496 Type *PtrTy = Ty->getPointerTo();
498 Value *CmpOperand = IRB.CreateBitOrPointerCast(CASI->getCompareOperand(), Ty);
499 Value *NewOperand = IRB.CreateBitOrPointerCast(CASI->getNewValOperand(), Ty);
501 int atomic_order_index_succ = getAtomicOrderIndex(CASI->getSuccessOrdering());
502 int atomic_order_index_fail = getAtomicOrderIndex(CASI->getFailureOrdering());
503 Value *order_succ = ConstantInt::get(OrdTy, atomic_order_index_succ);
504 Value *order_fail = ConstantInt::get(OrdTy, atomic_order_index_fail);
506 Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
507 CmpOperand, NewOperand,
508 order_succ, order_fail};
510 CallInst *funcInst = IRB.CreateCall(CDSAtomicCAS[index], Args);
511 Value *Success = IRB.CreateICmpEQ(funcInst, CmpOperand);
513 Value *OldVal = funcInst;
514 Type *OrigOldValTy = CASI->getNewValOperand()->getType();
515 if (Ty != OrigOldValTy) {
516 // The value is a pointer, so we need to cast the return value.
517 OldVal = IRB.CreateIntToPtr(funcInst, OrigOldValTy);
521 IRB.CreateInsertValue(UndefValue::get(CASI->getType()), OldVal, 0);
522 Res = IRB.CreateInsertValue(Res, Success, 1);
524 I->replaceAllUsesWith(Res);
525 I->eraseFromParent();
526 } else if (FenceInst *FI = dyn_cast<FenceInst>(I)) {
527 int atomic_order_index = getAtomicOrderIndex(FI->getOrdering());
528 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
529 Value *Args[] = {order};
531 CallInst *funcInst = CallInst::Create(CDSAtomicThreadFence, Args);
532 ReplaceInstWithInst(FI, funcInst);
533 // errs() << "Thread Fences replaced\n";
540 char CDSPass::ID = 0;
542 // Automatically enable the pass.
543 // http://adriansampson.net/blog/clangpass.html
544 static void registerCDSPass(const PassManagerBuilder &,
545 legacy::PassManagerBase &PM) {
546 PM.add(new CDSPass());
548 static RegisterStandardPasses
549 RegisterMyPass(PassManagerBuilder::EP_EarlyAsPossible,