Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Use SCEV to avoid inserting some bounds checks.
This patch uses SCEV to avoid inserting some bounds checks when they are not needed.  This slightly improves the performance of code compiled with the bounds check sanitizer.

Differential Revision: https://reviews.llvm.org/D49602

llvm-svn: 337830
  • Loading branch information
jgalenson committed Jul 24, 2018
1 parent 3241724 commit 8dbcc58
Show file tree
Hide file tree
Showing 2 changed files with 386 additions and 12 deletions.
40 changes: 28 additions & 12 deletions llvm/lib/Transforms/Instrumentation/BoundsChecking.cpp
Expand Up @@ -11,6 +11,7 @@
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/Twine.h"
#include "llvm/Analysis/MemoryBuiltins.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/TargetFolder.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/BasicBlock.h"
Expand Down Expand Up @@ -59,8 +60,8 @@ template <typename GetTrapBBT>
static bool instrumentMemAccess(Value *Ptr, Value *InstVal,
const DataLayout &DL, TargetLibraryInfo &TLI,
ObjectSizeOffsetEvaluator &ObjSizeEval,
BuilderTy &IRB,
GetTrapBBT GetTrapBB) {
BuilderTy &IRB, GetTrapBBT GetTrapBB,
ScalarEvolution &SE) {
uint64_t NeededSize = DL.getTypeStoreSize(InstVal->getType());
LLVM_DEBUG(dbgs() << "Instrument " << *Ptr << " for " << Twine(NeededSize)
<< " bytes\n");
Expand All @@ -79,6 +80,10 @@ static bool instrumentMemAccess(Value *Ptr, Value *InstVal,
Type *IntTy = DL.getIntPtrType(Ptr->getType());
Value *NeededSizeVal = ConstantInt::get(IntTy, NeededSize);

auto SizeRange = SE.getUnsignedRange(SE.getSCEV(Size));
auto OffsetRange = SE.getUnsignedRange(SE.getSCEV(Offset));
auto NeededSizeRange = SE.getUnsignedRange(SE.getSCEV(NeededSizeVal));

// three checks are required to ensure safety:
// . Offset >= 0 (since the offset is given from the base ptr)
// . Size >= Offset (unsigned)
Expand All @@ -87,10 +92,17 @@ static bool instrumentMemAccess(Value *Ptr, Value *InstVal,
// optimization: if Size >= 0 (signed), skip 1st check
// FIXME: add NSW/NUW here? -- we dont care if the subtraction overflows
Value *ObjSize = IRB.CreateSub(Size, Offset);
Value *Cmp2 = IRB.CreateICmpULT(Size, Offset);
Value *Cmp3 = IRB.CreateICmpULT(ObjSize, NeededSizeVal);
Value *Cmp2 = SizeRange.getUnsignedMin().uge(OffsetRange.getUnsignedMax())
? ConstantInt::getFalse(Ptr->getContext())
: IRB.CreateICmpULT(Size, Offset);
Value *Cmp3 = SizeRange.sub(OffsetRange)
.getUnsignedMin()
.uge(NeededSizeRange.getUnsignedMax())
? ConstantInt::getFalse(Ptr->getContext())
: IRB.CreateICmpULT(ObjSize, NeededSizeVal);
Value *Or = IRB.CreateOr(Cmp2, Cmp3);
if (!SizeCI || SizeCI->getValue().slt(0)) {
if ((!SizeCI || SizeCI->getValue().slt(0)) &&
!SizeRange.getSignedMin().isNonNegative()) {
Value *Cmp1 = IRB.CreateICmpSLT(Offset, ConstantInt::get(IntTy, 0));
Or = IRB.CreateOr(Cmp1, Or);
}
Expand Down Expand Up @@ -123,7 +135,8 @@ static bool instrumentMemAccess(Value *Ptr, Value *InstVal,
return true;
}

static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI) {
static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI,
ScalarEvolution &SE) {
const DataLayout &DL = F.getParent()->getDataLayout();
ObjectSizeOffsetEvaluator ObjSizeEval(DL, &TLI, F.getContext(),
/*RoundToAlign=*/true);
Expand Down Expand Up @@ -168,19 +181,19 @@ static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI) {
BuilderTy IRB(Inst->getParent(), BasicBlock::iterator(Inst), TargetFolder(DL));
if (LoadInst *LI = dyn_cast<LoadInst>(Inst)) {
MadeChange |= instrumentMemAccess(LI->getPointerOperand(), LI, DL, TLI,
ObjSizeEval, IRB, GetTrapBB);
ObjSizeEval, IRB, GetTrapBB, SE);
} else if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
MadeChange |=
instrumentMemAccess(SI->getPointerOperand(), SI->getValueOperand(),
DL, TLI, ObjSizeEval, IRB, GetTrapBB);
DL, TLI, ObjSizeEval, IRB, GetTrapBB, SE);
} else if (AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(Inst)) {
MadeChange |=
instrumentMemAccess(AI->getPointerOperand(), AI->getCompareOperand(),
DL, TLI, ObjSizeEval, IRB, GetTrapBB);
DL, TLI, ObjSizeEval, IRB, GetTrapBB, SE);
} else if (AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(Inst)) {
MadeChange |=
instrumentMemAccess(AI->getPointerOperand(), AI->getValOperand(), DL,
TLI, ObjSizeEval, IRB, GetTrapBB);
TLI, ObjSizeEval, IRB, GetTrapBB, SE);
} else {
llvm_unreachable("unknown Instruction type");
}
Expand All @@ -190,8 +203,9 @@ static bool addBoundsChecking(Function &F, TargetLibraryInfo &TLI) {

PreservedAnalyses BoundsCheckingPass::run(Function &F, FunctionAnalysisManager &AM) {
auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);

if (!addBoundsChecking(F, TLI))
if (!addBoundsChecking(F, TLI, SE))
return PreservedAnalyses::all();

return PreservedAnalyses::none();
Expand All @@ -207,11 +221,13 @@ struct BoundsCheckingLegacyPass : public FunctionPass {

bool runOnFunction(Function &F) override {
auto &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
return addBoundsChecking(F, TLI);
auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
return addBoundsChecking(F, TLI, SE);
}

void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<TargetLibraryInfoWrapperPass>();
AU.addRequired<ScalarEvolutionWrapperPass>();
}
};
} // namespace
Expand Down

0 comments on commit 8dbcc58

Please sign in to comment.