From a6da3ff896640b7bd3693748ee5685b0527483a0 Mon Sep 17 00:00:00 2001 From: Nuno Lopes Date: Fri, 25 May 2012 16:54:04 +0000 Subject: [PATCH] boundschecking: add support for select add experimental support for alloc_size metadata llvm-svn: 157481 --- llvm/lib/Transforms/Scalar/BoundsChecking.cpp | 154 +++++++++++++++------- llvm/test/Transforms/BoundsChecking/alloc_size.ll | 43 ++++++ llvm/test/Transforms/BoundsChecking/lit.local.cfg | 1 + llvm/test/Transforms/BoundsChecking/simple.ll | 31 +++++ 4 files changed, 179 insertions(+), 50 deletions(-) create mode 100644 llvm/test/Transforms/BoundsChecking/alloc_size.ll create mode 100644 llvm/test/Transforms/BoundsChecking/lit.local.cfg diff --git a/llvm/lib/Transforms/Scalar/BoundsChecking.cpp b/llvm/lib/Transforms/Scalar/BoundsChecking.cpp index 85c5e11..4c3dea2 100644 --- a/llvm/lib/Transforms/Scalar/BoundsChecking.cpp +++ b/llvm/lib/Transforms/Scalar/BoundsChecking.cpp @@ -26,6 +26,7 @@ #include "llvm/GlobalVariable.h" #include "llvm/Instructions.h" #include "llvm/Intrinsics.h" +#include "llvm/Metadata.h" #include "llvm/Operator.h" #include "llvm/Pass.h" using namespace llvm; @@ -118,6 +119,9 @@ void BoundsChecking::emitBranchToTrap(Value *Cmp) { /// incurr at run-time. ConstTriState BoundsChecking::computeAllocSize(Value *Alloc, uint64_t &Size, Value* &SizeValue) { + IntegerType *RetTy = TD->getIntPtrType(Fn->getContext()); + + // global variable with definitive size if (GlobalVariable *GV = dyn_cast(Alloc)) { if (GV->hasDefinitiveInitializer()) { Constant *C = GV->getInitializer(); @@ -126,6 +130,7 @@ ConstTriState BoundsChecking::computeAllocSize(Value *Alloc, uint64_t &Size, } return Dunno; + // stack allocation } else if (AllocaInst *AI = dyn_cast(Alloc)) { if (!AI->getAllocatedType()->isSized()) return Dunno; @@ -147,68 +152,117 @@ ConstTriState BoundsChecking::computeAllocSize(Value *Alloc, uint64_t &Size, SizeValue = Builder->CreateMul(SizeValue, ArraySize); return NotConst; - } else if (CallInst *CI = dyn_cast(Alloc)) { - Function *Callee = CI->getCalledFunction(); - if (!Callee || !Callee->isDeclaration()) + // ptr = select(ptr1, ptr2) + } else if (SelectInst *SI = dyn_cast(Alloc)) { + uint64_t SizeFalse; + Value *SizeValueFalse; + ConstTriState TrueConst = computeAllocSize(SI->getTrueValue(), Size, + SizeValue); + ConstTriState FalseConst = computeAllocSize(SI->getFalseValue(), SizeFalse, + SizeValueFalse); + + if (TrueConst == Const && FalseConst == Const && Size == SizeFalse) + return Const; + + if (Penalty < 2 || (TrueConst == Dunno && FalseConst == Dunno)) return Dunno; - FunctionType *FTy = Callee->getFunctionType(); - if (FTy->getNumParams() == 1) { + // if one of the branches is Dunno, assume it is ok and check just the other + APInt MaxSize = APInt::getMaxValue(TD->getTypeSizeInBits(RetTy)); + + if (TrueConst == Const) + SizeValue = ConstantInt::get(RetTy, Size); + else if (TrueConst == Dunno) + SizeValue = ConstantInt::get(RetTy, MaxSize); + + if (FalseConst == Const) + SizeValueFalse = ConstantInt::get(RetTy, SizeFalse); + else if (FalseConst == Dunno) + SizeValueFalse = ConstantInt::get(RetTy, MaxSize); + + SizeValue = Builder->CreateSelect(SI->getCondition(), SizeValue, + SizeValueFalse); + return NotConst; + + // call allocation function + } else if (CallInst *CI = dyn_cast(Alloc)) { + SmallVector Args; + + if (MDNode *MD = CI->getMetadata("alloc_size")) { + for (unsigned i = 0, e = MD->getNumOperands(); i != e; ++i) + Args.push_back(cast(MD->getOperand(i))->getZExtValue()); + + } else if (Function *Callee = CI->getCalledFunction()) { + FunctionType *FTy = Callee->getFunctionType(); + // alloc(size) - if ((FTy->getParamType(0)->isIntegerTy(32) || - FTy->getParamType(0)->isIntegerTy(64)) && - (Callee->getName() == "malloc" || - Callee->getName() == "valloc" || - Callee->getName() == "_Znwj" || // operator new(unsigned int) - Callee->getName() == "_Znwm" || // operator new(unsigned long) - Callee->getName() == "_Znaj" || // operator new[](unsigned int) - Callee->getName() == "_Znam")) { // operator new[](unsigned long) - SizeValue = CI->getArgOperand(0); - if (ConstantInt *Arg = dyn_cast(SizeValue)) { - Size = Arg->getZExtValue(); - return Const; + if (FTy->getNumParams() == 1 && FTy->getParamType(0)->isIntegerTy()) { + if ((Callee->getName() == "malloc" || + Callee->getName() == "valloc" || + Callee->getName() == "_Znwj" || // operator new(unsigned int) + Callee->getName() == "_Znwm" || // operator new(unsigned long) + Callee->getName() == "_Znaj" || // operator new[](unsigned int) + Callee->getName() == "_Znam")) { + Args.push_back(0); + } + } else if (FTy->getNumParams() == 2) { + // alloc(_, x) + if (FTy->getParamType(1)->isIntegerTy() && + ((Callee->getName() == "realloc" || + Callee->getName() == "reallocf"))) { + Args.push_back(1); + + // alloc(x, y) + } else if (FTy->getParamType(0)->isIntegerTy() && + FTy->getParamType(1)->isIntegerTy() && + Callee->getName() == "calloc") { + Args.push_back(0); + Args.push_back(1); } - return Penalty >= 2 ? NotConst : Dunno; } - return Dunno; } - if (FTy->getNumParams() == 2) { - // alloc(x, y) and return buffer of size x * y - if (((FTy->getParamType(0)->isIntegerTy(32) && - FTy->getParamType(1)->isIntegerTy(32)) || - (FTy->getParamType(0)->isIntegerTy(64) && - FTy->getParamType(1)->isIntegerTy(64))) && - Callee->getName() == "calloc") { - Value *Arg1 = CI->getArgOperand(0); - Value *Arg2 = CI->getArgOperand(1); - if (ConstantInt *CI1 = dyn_cast(Arg1)) { - if (ConstantInt *CI2 = dyn_cast(Arg2)) { - Size = (CI1->getValue() * CI2->getValue()).getZExtValue(); - return Const; - } - } + if (Args.empty()) + return Dunno; - if (Penalty < 2) - return Dunno; + // check if all arguments are constant. if so, the object size is also const + bool AllConst = true; + for (SmallVectorImpl::iterator I = Args.begin(), E = Args.end(); + I != E; ++I) { + if (!isa(CI->getArgOperand(*I))) { + AllConst = false; + break; + } + } - SizeValue = Builder->CreateMul(Arg1, Arg2); - return NotConst; + if (AllConst) { + Size = 1; + for (SmallVectorImpl::iterator I = Args.begin(), E = Args.end(); + I != E; ++I) { + ConstantInt *Arg = cast(CI->getArgOperand(*I)); + Size *= (size_t)Arg->getZExtValue(); } + return Const; + } - // realloc(ptr, size) - if ((FTy->getParamType(1)->isIntegerTy(32) || - FTy->getParamType(1)->isIntegerTy(64)) && - (Callee->getName() == "realloc" || - Callee->getName() == "reallocf")) { - SizeValue = CI->getArgOperand(1); - if (ConstantInt *Arg = dyn_cast(SizeValue)) { - Size = Arg->getZExtValue(); - return Const; - } - return Penalty >= 2 ? NotConst : Dunno; + if (Penalty < 2) + return Dunno; + + // not all arguments are constant, so create a sequence of multiplications + bool First = true; + for (SmallVectorImpl::iterator I = Args.begin(), E = Args.end(); + I != E; ++I) { + Value *Arg = CI->getArgOperand(*I); + if (First) { + SizeValue = Arg; + First = false; + continue; } + SizeValue = Builder->CreateMul(SizeValue, Arg); } + + return NotConst; + // TODO: handle more standard functions: // - strdup / strndup // - strcpy / strncpy @@ -216,7 +270,7 @@ ConstTriState BoundsChecking::computeAllocSize(Value *Alloc, uint64_t &Size, // - strcat / strncat } - DEBUG(dbgs() << "computeAllocSize failed:\n" << *Alloc); + DEBUG(dbgs() << "computeAllocSize failed:\n" << *Alloc << "\n"); return Dunno; } diff --git a/llvm/test/Transforms/BoundsChecking/alloc_size.ll b/llvm/test/Transforms/BoundsChecking/alloc_size.ll new file mode 100644 index 0000000..71910bc --- /dev/null +++ b/llvm/test/Transforms/BoundsChecking/alloc_size.ll @@ -0,0 +1,43 @@ +; RUN: opt < %s -bounds-checking -S | FileCheck %s +target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" + +declare i64* @alloc(i32, i8, i32) +declare i32* @alloc2(i32, i32) + +; CHECK: @f1 +define void @f1(i32 %x) { + %call = tail call i32* @alloc2(i32 %x, i32 4) nounwind, !alloc_size !0 +; CHECK: trap + store i32 3, i32* %call, align 4 + ret void +} + +; CHECK: @f2 +define void @f2() { + %call1 = tail call i32* @alloc2(i32 2, i32 4) nounwind, !alloc_size !0 + %arrayidx = getelementptr i32* %call1, i64 2 +; CHECK: br label + store i32 3, i32* %arrayidx, align 4 + ret void +} + +; CHECK: @f3 +define void @f3(i32 %x, i8 %y) { + %call = tail call i64* @alloc(i32 %x, i8 %y, i32 7) nounwind, !alloc_size !1 +; CHECK: trap + store i64 27, i64* %call, align 4 + ret void +} + +; CHECK: @f4 +define void @f4() { + %call1 = tail call i32* @alloc2(i32 2, i32 4) nounwind, !alloc_size !0 + %arrayidx = getelementptr i32* %call1, i64 1 +; CHECK-NOT: trap + store i32 3, i32* %arrayidx, align 4 +; CHECK: ret + ret void +} + +!0 = metadata !{i32 0, i32 1} +!1 = metadata !{i32 2} diff --git a/llvm/test/Transforms/BoundsChecking/lit.local.cfg b/llvm/test/Transforms/BoundsChecking/lit.local.cfg new file mode 100644 index 0000000..19eebc0 --- /dev/null +++ b/llvm/test/Transforms/BoundsChecking/lit.local.cfg @@ -0,0 +1 @@ +config.suffixes = ['.ll', '.c', '.cpp'] diff --git a/llvm/test/Transforms/BoundsChecking/simple.ll b/llvm/test/Transforms/BoundsChecking/simple.ll index 7cfe6ec..f24d9e1 100644 --- a/llvm/test/Transforms/BoundsChecking/simple.ll +++ b/llvm/test/Transforms/BoundsChecking/simple.ll @@ -76,3 +76,34 @@ define void @f7(i64 %x) nounwind { %2 = load i128* %1, align 4 ret void } + +; CHECK: @f8 +define void @f8() nounwind { + %1 = alloca i128 + %2 = alloca i128 + %3 = select i1 undef, i128* %1, i128* %2 +; CHECK-NOT: trap + %4 = load i128* %3, align 4 + ret void +} + +; CHECK: @f9 +define void @f9(i128* %arg) nounwind { + %1 = alloca i128 + %2 = select i1 undef, i128* %arg, i128* %1 +; CHECK: br i1 false + %3 = load i128* %2, align 4 + ret void +} + +; CHECK: @f10 +define void @f10(i64 %x, i64 %y) nounwind { + %1 = alloca i128, i64 %x + %2 = alloca i128, i64 %y + %3 = select i1 undef, i128* %1, i128* %2 +; CHECK: select +; CHECK: select +; CHECK: trap + %4 = load i128* %3, align 4 + ret void +} -- 2.7.4