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/IR/DebugLoc.h"
37 #include "llvm/Pass.h"
38 #include "llvm/ProfileData/InstrProf.h"
39 #include "llvm/Support/raw_ostream.h"
40 #include "llvm/Support/AtomicOrdering.h"
41 #include "llvm/Support/Debug.h"
42 #include "llvm/Transforms/Scalar.h"
43 #include "llvm/Transforms/Utils/Local.h"
44 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
45 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
48 #define DEBUG_TYPE "CDS"
51 #define FUNCARRAYSIZE 4
53 STATISTIC(NumInstrumentedReads, "Number of instrumented reads");
54 STATISTIC(NumInstrumentedWrites, "Number of instrumented writes");
55 // STATISTIC(NumInstrumentedVtableWrites, "Number of vtable ptr writes");
56 // STATISTIC(NumInstrumentedVtableReads, "Number of vtable ptr reads");
58 STATISTIC(NumOmittedReadsBeforeWrite,
59 "Number of reads ignored due to following writes");
60 STATISTIC(NumOmittedReadsFromConstantGlobals,
61 "Number of reads from constant globals");
62 STATISTIC(NumOmittedReadsFromVtable, "Number of vtable reads");
63 STATISTIC(NumOmittedNonCaptured, "Number of accesses ignored due to capturing");
78 Constant * CDSLoad[FUNCARRAYSIZE];
79 Constant * CDSStore[FUNCARRAYSIZE];
80 Constant * CDSAtomicInit[FUNCARRAYSIZE];
81 Constant * CDSAtomicLoad[FUNCARRAYSIZE];
82 Constant * CDSAtomicStore[FUNCARRAYSIZE];
83 Constant * CDSAtomicRMW[AtomicRMWInst::LAST_BINOP + 1][FUNCARRAYSIZE];
84 Constant * CDSAtomicCAS_V1[FUNCARRAYSIZE];
85 Constant * CDSAtomicCAS_V2[FUNCARRAYSIZE];
86 Constant * CDSAtomicThreadFence;
90 int getAtomicOrderIndex(AtomicOrdering order){
92 case AtomicOrdering::Monotonic:
93 return (int)AtomicOrderingCABI::relaxed;
94 // case AtomicOrdering::Consume: // not specified yet
95 // return AtomicOrderingCABI::consume;
96 case AtomicOrdering::Acquire:
97 return (int)AtomicOrderingCABI::acquire;
98 case AtomicOrdering::Release:
99 return (int)AtomicOrderingCABI::release;
100 case AtomicOrdering::AcquireRelease:
101 return (int)AtomicOrderingCABI::acq_rel;
102 case AtomicOrdering::SequentiallyConsistent:
103 return (int)AtomicOrderingCABI::seq_cst;
105 // unordered or Not Atomic
110 int getTypeSize(Type* type) {
111 if (type == Int8PtrTy) {
112 return sizeof(char)*8;
113 } else if (type == Int16PtrTy) {
114 return sizeof(short)*8;
115 } else if (type == Int32PtrTy) {
116 return sizeof(int)*8;
117 } else if (type == Int64PtrTy) {
118 return sizeof(long long int)*8;
120 return sizeof(void*)*8;
126 static int sizetoindex(int size) {
137 struct CDSPass : public FunctionPass {
139 CDSPass() : FunctionPass(ID) {}
140 bool runOnFunction(Function &F) override;
143 void initializeCallbacks(Module &M);
144 bool instrumentLoadOrStore(Instruction *I, const DataLayout &DL);
145 bool instrumentAtomic(Instruction *I, const DataLayout &DL);
146 bool instrumentAtomicCall(CallInst *CI, const DataLayout &DL);
147 void chooseInstructionsToInstrument(SmallVectorImpl<Instruction *> &Local,
148 SmallVectorImpl<Instruction *> &All,
149 const DataLayout &DL);
150 bool addrPointsToConstantData(Value *Addr);
151 int getMemoryAccessFuncIndex(Value *Addr, const DataLayout &DL);
155 static bool isVtableAccess(Instruction *I) {
156 if (MDNode *Tag = I->getMetadata(LLVMContext::MD_tbaa))
157 return Tag->isTBAAVtableAccess();
161 #include "initializeCallbacks.hpp"
162 #include "isAtomicCall.hpp"
163 #include "instrumentAtomicCall.hpp"
165 static bool shouldInstrumentReadWriteFromAddress(const Module *M, Value *Addr) {
166 // Peel off GEPs and BitCasts.
167 Addr = Addr->stripInBoundsOffsets();
169 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
170 if (GV->hasSection()) {
171 StringRef SectionName = GV->getSection();
172 // Check if the global is in the PGO counters section.
173 auto OF = Triple(M->getTargetTriple()).getObjectFormat();
174 if (SectionName.endswith(
175 getInstrProfSectionName(IPSK_cnts, OF, /*AddSegmentInfo=*/false)))
179 // Check if the global is private gcov data.
180 if (GV->getName().startswith("__llvm_gcov") ||
181 GV->getName().startswith("__llvm_gcda"))
185 // Do not instrument acesses from different address spaces; we cannot deal
188 Type *PtrTy = cast<PointerType>(Addr->getType()->getScalarType());
189 if (PtrTy->getPointerAddressSpace() != 0)
196 bool CDSPass::addrPointsToConstantData(Value *Addr) {
197 // If this is a GEP, just analyze its pointer operand.
198 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Addr))
199 Addr = GEP->getPointerOperand();
201 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
202 if (GV->isConstant()) {
203 // Reads from constant globals can not race with any writes.
204 NumOmittedReadsFromConstantGlobals++;
207 } else if (LoadInst *L = dyn_cast<LoadInst>(Addr)) {
208 if (isVtableAccess(L)) {
209 // Reads from a vtable pointer can not race with any writes.
210 NumOmittedReadsFromVtable++;
217 bool CDSPass::runOnFunction(Function &F) {
218 if (F.getName() == "main") {
219 F.setName("user_main");
220 errs() << "main replaced by user_main\n";
224 initializeCallbacks( *F.getParent() );
226 SmallVector<Instruction*, 8> AllLoadsAndStores;
227 SmallVector<Instruction*, 8> LocalLoadsAndStores;
228 SmallVector<Instruction*, 8> AtomicAccesses;
230 std::vector<Instruction *> worklist;
233 const DataLayout &DL = F.getParent()->getDataLayout();
235 errs() << "--- " << F.getName() << "---\n";
239 if ( (&I)->isAtomic() || isAtomicCall(&I) ) {
240 AtomicAccesses.push_back(&I);
242 const llvm::DebugLoc & debug_location = I.getDebugLoc();
243 std::string position_string;
245 llvm::raw_string_ostream position_stream (position_string);
246 debug_location . print (position_stream);
249 errs() << I << "\n" << (position_string) << "\n\n";
250 } else if (isa<LoadInst>(I) || isa<StoreInst>(I)) {
251 LocalLoadsAndStores.push_back(&I);
252 } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
253 // not implemented yet
257 chooseInstructionsToInstrument(LocalLoadsAndStores, AllLoadsAndStores, DL);
260 for (auto Inst : AllLoadsAndStores) {
261 // Res |= instrumentLoadOrStore(Inst, DL);
262 // errs() << "load and store are replaced\n";
265 for (auto Inst : AtomicAccesses) {
266 Res |= instrumentAtomic(Inst, DL);
269 if (F.getName() == "user_main") {
278 void CDSPass::chooseInstructionsToInstrument(
279 SmallVectorImpl<Instruction *> &Local, SmallVectorImpl<Instruction *> &All,
280 const DataLayout &DL) {
281 SmallPtrSet<Value*, 8> WriteTargets;
282 // Iterate from the end.
283 for (Instruction *I : reverse(Local)) {
284 if (StoreInst *Store = dyn_cast<StoreInst>(I)) {
285 Value *Addr = Store->getPointerOperand();
286 if (!shouldInstrumentReadWriteFromAddress(I->getModule(), Addr))
288 WriteTargets.insert(Addr);
290 LoadInst *Load = cast<LoadInst>(I);
291 Value *Addr = Load->getPointerOperand();
292 if (!shouldInstrumentReadWriteFromAddress(I->getModule(), Addr))
294 if (WriteTargets.count(Addr)) {
295 // We will write to this temp, so no reason to analyze the read.
296 NumOmittedReadsBeforeWrite++;
299 if (addrPointsToConstantData(Addr)) {
300 // Addr points to some constant data -- it can not race with any writes.
304 Value *Addr = isa<StoreInst>(*I)
305 ? cast<StoreInst>(I)->getPointerOperand()
306 : cast<LoadInst>(I)->getPointerOperand();
307 if (isa<AllocaInst>(GetUnderlyingObject(Addr, DL)) &&
308 !PointerMayBeCaptured(Addr, true, true)) {
309 // The variable is addressable but not captured, so it cannot be
310 // referenced from a different thread and participate in a data race
311 // (see llvm/Analysis/CaptureTracking.h for details).
312 NumOmittedNonCaptured++;
321 bool CDSPass::instrumentLoadOrStore(Instruction *I,
322 const DataLayout &DL) {
324 bool IsWrite = isa<StoreInst>(*I);
325 Value *Addr = IsWrite
326 ? cast<StoreInst>(I)->getPointerOperand()
327 : cast<LoadInst>(I)->getPointerOperand();
329 // swifterror memory addresses are mem2reg promoted by instruction selection.
330 // As such they cannot have regular uses like an instrumentation function and
331 // it makes no sense to track them as memory.
332 if (Addr->isSwiftError())
335 int size = getTypeSize(Addr->getType());
336 int index = sizetoindex(size);
338 // not supported by CDS yet
339 /* if (IsWrite && isVtableAccess(I)) {
340 LLVM_DEBUG(dbgs() << " VPTR : " << *I << "\n");
341 Value *StoredValue = cast<StoreInst>(I)->getValueOperand();
342 // StoredValue may be a vector type if we are storing several vptrs at once.
343 // In this case, just take the first element of the vector since this is
344 // enough to find vptr races.
345 if (isa<VectorType>(StoredValue->getType()))
346 StoredValue = IRB.CreateExtractElement(
347 StoredValue, ConstantInt::get(IRB.getInt32Ty(), 0));
348 if (StoredValue->getType()->isIntegerTy())
349 StoredValue = IRB.CreateIntToPtr(StoredValue, IRB.getInt8PtrTy());
350 // Call TsanVptrUpdate.
351 IRB.CreateCall(TsanVptrUpdate,
352 {IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()),
353 IRB.CreatePointerCast(StoredValue, IRB.getInt8PtrTy())});
354 NumInstrumentedVtableWrites++;
358 if (!IsWrite && isVtableAccess(I)) {
359 IRB.CreateCall(TsanVptrLoad,
360 IRB.CreatePointerCast(Addr, IRB.getInt8PtrTy()));
361 NumInstrumentedVtableReads++;
366 Value *OnAccessFunc = nullptr;
367 OnAccessFunc = IsWrite ? CDSStore[index] : CDSLoad[index];
369 Type *ArgType = IRB.CreatePointerCast(Addr, Addr->getType())->getType();
371 if ( ArgType != Int8PtrTy && ArgType != Int16PtrTy &&
372 ArgType != Int32PtrTy && ArgType != Int64PtrTy ) {
373 //errs() << "A load or store of type ";
374 //errs() << *ArgType;
375 //errs() << " is passed in\n";
376 return false; // if other types of load or stores are passed in
378 IRB.CreateCall(OnAccessFunc, IRB.CreatePointerCast(Addr, Addr->getType()));
379 if (IsWrite) NumInstrumentedWrites++;
380 else NumInstrumentedReads++;
384 // todo: replace getTypeSize with the getMemoryAccessFuncIndex
385 bool CDSPass::instrumentAtomic(Instruction * I, const DataLayout &DL) {
387 // LLVMContext &Ctx = IRB.getContext();
389 if (auto *CI = dyn_cast<CallInst>(I)) {
390 return instrumentAtomicCall(CI, DL);
393 if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
394 int atomic_order_index = getAtomicOrderIndex(SI->getOrdering());
396 Value *val = SI->getValueOperand();
397 Value *ptr = SI->getPointerOperand();
398 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
399 Value *args[] = {ptr, val, order};
401 int size=getTypeSize(ptr->getType());
402 int index=sizetoindex(size);
404 Instruction* funcInst=CallInst::Create(CDSAtomicStore[index], args,"");
405 ReplaceInstWithInst(SI, funcInst);
406 // errs() << "Store replaced\n";
407 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
408 int atomic_order_index = getAtomicOrderIndex(LI->getOrdering());
410 Value *ptr = LI->getPointerOperand();
411 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
412 Value *args[] = {ptr, order};
414 int size=getTypeSize(ptr->getType());
415 int index=sizetoindex(size);
417 Instruction* funcInst=CallInst::Create(CDSAtomicLoad[index], args, "");
418 ReplaceInstWithInst(LI, funcInst);
419 // errs() << "Load Replaced\n";
420 } else if (AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(I)) {
421 int atomic_order_index = getAtomicOrderIndex(RMWI->getOrdering());
423 Value *val = RMWI->getValOperand();
424 Value *ptr = RMWI->getPointerOperand();
425 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
426 Value *args[] = {ptr, val, order};
428 int size = getTypeSize(ptr->getType());
429 int index = sizetoindex(size);
431 Instruction* funcInst = CallInst::Create(CDSAtomicRMW[RMWI->getOperation()][index], args, "");
432 ReplaceInstWithInst(RMWI, funcInst);
433 // errs() << RMWI->getOperationName(RMWI->getOperation());
434 // errs() << " replaced\n";
435 } else if (AtomicCmpXchgInst *CASI = dyn_cast<AtomicCmpXchgInst>(I)) {
436 IRBuilder<> IRB(CASI);
438 Value *Addr = CASI->getPointerOperand();
440 int size = getTypeSize(Addr->getType());
441 int index = sizetoindex(size);
442 const unsigned ByteSize = 1U << index;
443 const unsigned BitSize = ByteSize * 8;
444 Type *Ty = Type::getIntNTy(IRB.getContext(), BitSize);
445 Type *PtrTy = Ty->getPointerTo();
447 Value *CmpOperand = IRB.CreateBitOrPointerCast(CASI->getCompareOperand(), Ty);
448 Value *NewOperand = IRB.CreateBitOrPointerCast(CASI->getNewValOperand(), Ty);
450 int atomic_order_index_succ = getAtomicOrderIndex(CASI->getSuccessOrdering());
451 int atomic_order_index_fail = getAtomicOrderIndex(CASI->getFailureOrdering());
452 Value *order_succ = ConstantInt::get(OrdTy, atomic_order_index_succ);
453 Value *order_fail = ConstantInt::get(OrdTy, atomic_order_index_fail);
455 Value *Args[] = {IRB.CreatePointerCast(Addr, PtrTy),
456 CmpOperand, NewOperand,
457 order_succ, order_fail};
459 CallInst *funcInst = IRB.CreateCall(CDSAtomicCAS_V1[index], Args);
460 Value *Success = IRB.CreateICmpEQ(funcInst, CmpOperand);
462 Value *OldVal = funcInst;
463 Type *OrigOldValTy = CASI->getNewValOperand()->getType();
464 if (Ty != OrigOldValTy) {
465 // The value is a pointer, so we need to cast the return value.
466 OldVal = IRB.CreateIntToPtr(funcInst, OrigOldValTy);
470 IRB.CreateInsertValue(UndefValue::get(CASI->getType()), OldVal, 0);
471 Res = IRB.CreateInsertValue(Res, Success, 1);
473 I->replaceAllUsesWith(Res);
474 I->eraseFromParent();
475 } else if (FenceInst *FI = dyn_cast<FenceInst>(I)) {
476 int atomic_order_index = getAtomicOrderIndex(FI->getOrdering());
477 Value *order = ConstantInt::get(OrdTy, atomic_order_index);
478 Value *Args[] = {order};
480 CallInst *funcInst = CallInst::Create(CDSAtomicThreadFence, Args);
481 ReplaceInstWithInst(FI, funcInst);
482 // errs() << "Thread Fences replaced\n";
487 int CDSPass::getMemoryAccessFuncIndex(Value *Addr,
488 const DataLayout &DL) {
489 Type *OrigPtrTy = Addr->getType();
490 Type *OrigTy = cast<PointerType>(OrigPtrTy)->getElementType();
491 assert(OrigTy->isSized());
492 uint32_t TypeSize = DL.getTypeStoreSizeInBits(OrigTy);
493 if (TypeSize != 8 && TypeSize != 16 &&
494 TypeSize != 32 && TypeSize != 64 && TypeSize != 128) {
495 // NumAccessesWithBadSize++;
496 // Ignore all unusual sizes.
499 size_t Idx = countTrailingZeros(TypeSize / 8);
500 // assert(Idx < FUNCARRAYSIZE);
505 char CDSPass::ID = 0;
507 // Automatically enable the pass.
508 static void registerCDSPass(const PassManagerBuilder &,
509 legacy::PassManagerBase &PM) {
510 PM.add(new CDSPass());
512 static RegisterStandardPasses
513 RegisterMyPass(PassManagerBuilder::EP_OptimizerLast,