From 631b441a0feea65b2aa2bd35d129157ede5c6290 Mon Sep 17 00:00:00 2001 From: Peizhao Ou Date: Wed, 13 Jun 2018 13:53:38 -0700 Subject: [PATCH] Refactors tainting analysis to avoid load-followed-by-CAS tainting and also delay tainting after release stores --- include/llvm/IR/Instruction.h | 2 +- include/llvm/IR/Instructions.h | 10 +- lib/CodeGen/AtomicExpandPass.cpp | 8 +- lib/CodeGen/CodeGenPrepare.cpp | 2 +- lib/CodeGen/TaintRelaxedAtomicsUtils.cpp | 190 +++++++++++++++++++---- lib/CodeGen/TaintRelaxedAtomicsUtils.h | 16 +- 6 files changed, 187 insertions(+), 41 deletions(-) diff --git a/include/llvm/IR/Instruction.h b/include/llvm/IR/Instruction.h index c9de9e20055..c317a290986 100644 --- a/include/llvm/IR/Instruction.h +++ b/include/llvm/IR/Instruction.h @@ -299,7 +299,7 @@ public: return NeedTainted; } - bool setNeedTainted() { + void setNeedTainted() { NeedTainted = true; } diff --git a/include/llvm/IR/Instructions.h b/include/llvm/IR/Instructions.h index cc6c25974cd..ae5481db8fc 100644 --- a/include/llvm/IR/Instructions.h +++ b/include/llvm/IR/Instructions.h @@ -228,12 +228,12 @@ public: LoadInst(Value *Ptr, const char *NameStr, bool isVolatile, BasicBlock *InsertAtEnd); - bool getHasSubsequentAcqlRMW() { - return hasSubsequentAcqlRMW_; + bool getHasSubsequentOrderingProtection() { + return hasSubsequentOrderingProtection_; } - void setHasSubsequentAcqlRMW(bool val) { - hasSubsequentAcqlRMW_ = val; + void setHasSubsequentOrderingProtection(bool val) { + hasSubsequentOrderingProtection_ = val; } /// isVolatile - Return true if this is a load from a volatile memory @@ -315,7 +315,7 @@ private: Instruction::setInstructionSubclassData(D); } - bool hasSubsequentAcqlRMW_; + bool hasSubsequentOrderingProtection_; }; //===----------------------------------------------------------------------===// diff --git a/lib/CodeGen/AtomicExpandPass.cpp b/lib/CodeGen/AtomicExpandPass.cpp index 50d289563a0..d3884edd866 100644 --- a/lib/CodeGen/AtomicExpandPass.cpp +++ b/lib/CodeGen/AtomicExpandPass.cpp @@ -100,9 +100,11 @@ bool AtomicExpand::runOnFunction(Function &F) { case Instruction::Load: { auto* LI = dyn_cast(&*I); if (LI->getOrdering() == Monotonic) { - // XXX-modified: If a relaxed load is followed by AcqRel RMWs, we - // don't have to taint the load. - MarkRelaxedLoadBeforeAcqrelRMW(LI); + // XXX-modified: If a relaxed load has subsequent reordering + // protection, mark it and the backend won't taint it. + if (HasSubsequentOrderingProtection(LI)) { + LI->setHasSubsequentOrderingProtection(true); + } } break; } diff --git a/lib/CodeGen/CodeGenPrepare.cpp b/lib/CodeGen/CodeGenPrepare.cpp index 3ae7a1afe28..2f8c6617277 100644 --- a/lib/CodeGen/CodeGenPrepare.cpp +++ b/lib/CodeGen/CodeGenPrepare.cpp @@ -346,7 +346,7 @@ bool CodeGenPrepare::runOnFunction(Function &F) { case Instruction::Load: { auto* LI = dyn_cast(&*I); if (LI->getOrdering() == Monotonic && - !LI->getHasSubsequentAcqlRMW()) { + !LI->getHasSubsequentOrderingProtection()) { MonotonicLoadInsts.insert(LI); } break; diff --git a/lib/CodeGen/TaintRelaxedAtomicsUtils.cpp b/lib/CodeGen/TaintRelaxedAtomicsUtils.cpp index 76f0dd4d02c..1c1b368a603 100644 --- a/lib/CodeGen/TaintRelaxedAtomicsUtils.cpp +++ b/lib/CodeGen/TaintRelaxedAtomicsUtils.cpp @@ -130,7 +130,7 @@ void recursivelyFindDependence(SetType* DepSet, Value* Val, break; } case Instruction::PHI: { - for (int i = 0; i < I->getNumOperands(); i++) { + for (unsigned i = 0; i < I->getNumOperands(); i++) { auto* op = I->getOperand(i); if (DepSet->count(op) == 0) { recursivelyFindDependence(DepSet, I->getOperand(i), @@ -206,8 +206,6 @@ Instruction* getOrAddress(Value* CurrentAddress) { // Is it a cast from integer to pointer type. Instruction* OrAddress = nullptr; Instruction* AndDep = nullptr; - Instruction* CastToInt = nullptr; - Value* ActualAddress = nullptr; Constant* ZeroConst = nullptr; const Instruction* CastToPtr = dyn_cast(CurrentAddress); @@ -383,7 +381,6 @@ Value* getRootDependence(Value* DepVal) { // store i32 1, i32* %5, align 4 bool taintStoreAddress(StoreInst* SI, Value* DepVal) { // Set the insertion point right after the 'DepVal'. - Instruction* Inst = nullptr; IRBuilder Builder(SI); BasicBlock* BB = SI->getParent(); Value* Address = SI->getPointerOperand(); @@ -422,8 +419,6 @@ bool taintStoreAddress(StoreInst* SI, Value* DepVal) { OldDep, createCast(Builder, DepVal, TargetIntegerType)); } - auto* NewDepInst = dyn_cast(NewDep); - // Use the new AND instruction as the dependence AndDep->setOperand(0, NewDep); return true; @@ -434,7 +429,6 @@ bool taintStoreAddress(StoreInst* SI, Value* DepVal) { Value* PtrToIntCast = Builder.CreatePtrToInt(Address, TargetIntegerType); Value* AndDepVal = Builder.CreateAnd(CastDepToInt, ConstantInt::get(TargetIntegerType, 0)); - auto AndInst = dyn_cast(AndDepVal); // XXX-comment: The original IR InstCombiner would change our and instruction // to a select and then the back end optimize the condition out. We attach a // flag to instructions and set it here to inform the InstCombiner to not to @@ -803,7 +797,6 @@ bool NeedExtraConstraints(Instruction* Inst, Instruction* FirstInst) { if (!FirstInst) { return true; } - auto* BB = Inst->getParent(); auto BBI = Inst->getIterator(); BBI++; while (true) { @@ -863,7 +856,18 @@ bool AddFakeConditionalBranchAfterMonotonicLoads( continue; } - // We really need to process the relaxed load now. + // We really need to process the relaxed load now. First see if we can delay + // the tainting. + if (FirstInst) { + auto* FirstInstBBTerm = FirstInst->getParent()->getTerminator(); + while (FirstInst != FirstInstBBTerm) { + if (!CanDelayTainting(LI, FirstInst)) { + break; + } + FirstInst = FirstInst->getNextNode(); + } + } + StoreInst* SI = nullptr; IntrinsicInst* II = nullptr; if (FirstInst) { @@ -930,7 +934,6 @@ Value* GetUntaintedAddress(Value* CurrentAddress) { return CurrentAddress; } - Value* ActualAddress = nullptr; auto* CastToInt = dyn_cast(OrAddress->getOperand(1)); if (CastToInt && CastToInt->getOpcode() == Instruction::PtrToInt) { @@ -1062,7 +1065,6 @@ bool CompressTaintedStore(BasicBlock* BB) { continue; } // Check condition B. - Value* Cond = nullptr; if (OrigAddress == CurrSI->getPointerOperand() || OrigAddress != UntaintedAddress || CurrSIDepCond == nullptr || !dependenceSetInclusion(CurrSI->getValueOperand(), CurrSIDepCond)) { @@ -1167,30 +1169,164 @@ bool StoreDependOnValue(StoreInst* SI, Value* Dep) { return dependenceSetInclusion(SI, Dep); } -// If 'LI' is a relaxed load, and it is immediately followed by a atomic -// read-modify-write that has acq_rel parameter, we don't have to do anything -// since the rmw serves as a natural barrier. -void MarkRelaxedLoadBeforeAcqrelRMW(LoadInst* LI) { +bool ValueDependOnValue(Value* Inst, Value* Dep) { + return dependenceSetInclusion(Inst, Dep); +} + +// XXX-update: Checks whether the relaxed load 'LI' has subsequent instructions +// that naturally prevents it from being reordered across later stores. +bool HasSubsequentOrderingProtection(LoadInst* LI) { auto* BB = LI->getParent(); - auto BBI = LI->getIterator(); - for (BBI++; BBI != BB->end(); BBI++) { - Instruction* CurInst = &*BBI; - if (!CurInst) { - return; + auto* Term = BB->getTerminator(); + for (auto Iter = BasicBlock::iterator(LI->getNextNode()); Iter != BB->end(); + Iter++) { + Instruction* I = &*Iter; + + // Reaching the end of the block. + if (I == Term) { + auto* Branch = dyn_cast(Term); + // The last instruction isn't a branch, end of analysis. + if (!Branch) { + return false; + } + if (Branch->isConditional()) { + if (ValueDependOnValue(Branch, LI)) { + // 'LI' is used in the conditional branch. + return true; + } else { + // Reach the end with a cond branch that doesn't use the result of + // 'LI'. + return false; + } + } else { + // Reach the end with a unconditional branch, keep going to the next + // block. + BB = BB->getSingleSuccessor(); + Term = BB->getTerminator(); + Iter = BB->begin(); + continue; + } + } + + // 'I' is a CAS whose old value depends on 'LI'. We don't need to taint 'LI' + // then. + auto* CAS = dyn_cast(I); + if (CAS) { + if (ValueDependOnValue(CAS->getCompareOperand(), LI)) { + return true; + } + } + + // fetch_* operations that have acquire-release semantics. + auto* RMW = dyn_cast(I); + if (RMW) { + auto Order = RMW->getOrdering(); + if (Order == AcquireRelease || Order == SequentiallyConsistent) { + return true; + } } - if (!CurInst->isAtomic()) { + + // A load whose address depends on 'LI' prevents later stores from being + // reordered. + auto* LdInst = dyn_cast(I); + if (LdInst) { + if (ValueDependOnValue(LdInst->getPointerOperand(), LI)) { + return true; + } + } + + // Other instructions that don't affect the reordering. + if (!I->mayHaveSideEffects()) { continue; } - auto* RMW = dyn_cast(CurInst); - if (!RMW) { - return; + + // A store whose address depends on 'LI' is also protection. + auto* SI = dyn_cast(I); + if (SI) { + if (ValueDependOnValue(SI->getPointerOperand(), LI)) { + return true; + } } - if (RMW->getOrdering() == AcquireRelease || - RMW->getOrdering() == SequentiallyConsistent) { - LI->setHasSubsequentAcqlRMW(true); + + // The following are store/store-like operations. They don't protect later + // stores from being reordered across 'LI', but the analysis can go on if + // they naturally can't be reordered across 'LI' themselves. + { + // Release (or stronger) store. + if (SI) { + auto Order = SI->getOrdering(); + if (Order == Release || Order == SequentiallyConsistent) { + continue; + } + } + + // Release (or stronger) fetch_*. + if (RMW) { + auto Order = RMW->getOrdering(); + if (Order == Release || Order == AcquireRelease || + Order == SequentiallyConsistent) { + continue; + } + } + + // The instruction naturally depends on 'LI'. + if (ValueDependOnValue(I, LI)) { + continue; + } } + // Otherwise, we need to taint 'LI'. + // XXX-comment: It may be a good idea that we can delay the fake conditional + // branch down to this instruction. + return false; } + + // Just in case, the loop should never end without reaching a return. + return false; } +// XXX-update: Checks whether the tainting to instruction 'I' can be delayed +// with respects to the relaxed load 'LI'. This usually means 'I' itself already +// depends on the 'LI' or 'I' is a store/store-like atomic operation that has +// release semantics. +bool CanDelayTainting(LoadInst* LI, Instruction* I) { + if (I == I->getParent()->getTerminator()) { + return false; + } + + if (!I->mayHaveSideEffects()) { + return true; + } + + // The following are store/store-like operations. They don't protect later + // stores from being reordered across 'LI', but the analysis can go on if + // they naturally can't be reordered across 'LI' themselves. + + // Release (or stronger) store. + auto* SI = dyn_cast(I); + if (SI) { + auto Order = SI->getOrdering(); + if (Order == Release || Order == SequentiallyConsistent) { + return true; + } + } + + // Release (or stronger) fetch_*. + auto* RMW = dyn_cast(I); + if (RMW) { + auto Order = RMW->getOrdering(); + if (Order == Release || Order == AcquireRelease || + Order == SequentiallyConsistent) { + return true; + } + } + + // The instruction naturally depends on 'LI'. + if (ValueDependOnValue(I, LI)) { + return true; + } + + // Otherwise, be conservative and say no! + return false; +} } // namespace llvm diff --git a/lib/CodeGen/TaintRelaxedAtomicsUtils.h b/lib/CodeGen/TaintRelaxedAtomicsUtils.h index bcc043119cd..58b5c3d5ae7 100644 --- a/lib/CodeGen/TaintRelaxedAtomicsUtils.h +++ b/lib/CodeGen/TaintRelaxedAtomicsUtils.h @@ -241,10 +241,18 @@ SmallSet FindDependence(Value* Val); bool StoreDependOnValue(StoreInst* SI, Value* Dep); -// If 'LI' is a relaxed load, and it is immediately followed by a -// atomic read-modify-write that has acq_rel parameter, we don't have to do -// anything since the rmw serves as a natural barrier. -void MarkRelaxedLoadBeforeAcqrelRMW(LoadInst* LI); +bool ValueDependOnValue(Value * Inst, Value* Dep); + +// XXX-update: Checks whether the relaxed load 'LI' has subsequent instructions +// that naturally prevents it from being reordered across later stores. +bool HasSubsequentOrderingProtection(LoadInst* LI); + + +// XXX-update: Checks whether the tainting to instruction 'I' can be delayed +// with respects to the relaxed load 'LI'. This usually means 'I' itself already +// depends on the 'LI' or 'I' is a store/store-like atomic operation that has +// release semantics. +bool CanDelayTainting(LoadInst* LI, Instruction* I); } // namespace llvm -- 2.34.1