X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FLint.cpp;h=9393508a9e67edbdde900ae20180f92a0b866659;hb=85f6cbd1a5dc0071b3b4a7387e66479bbdfb3d13;hp=0cdb4b1a1c91bf62d6ec413959ac72fcf6c11329;hpb=23a19572b2839ee3a6a3520d60d62a465cec7d53;p=oota-llvm.git diff --git a/lib/Analysis/Lint.cpp b/lib/Analysis/Lint.cpp index 0cdb4b1a1c9..9393508a9e6 100644 --- a/lib/Analysis/Lint.cpp +++ b/lib/Analysis/Lint.cpp @@ -34,25 +34,26 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/Lint.h" +#include "llvm/ADT/STLExtras.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/Dominators.h" -#include "llvm/Analysis/Lint.h" +#include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/Loads.h" +#include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ValueTracking.h" #include "llvm/Assembly/Writer.h" -#include "llvm/Target/TargetData.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Function.h" +#include "llvm/IR/IntrinsicInst.h" +#include "llvm/InstVisitor.h" #include "llvm/Pass.h" #include "llvm/PassManager.h" -#include "llvm/IntrinsicInst.h" -#include "llvm/Function.h" #include "llvm/Support/CallSite.h" #include "llvm/Support/Debug.h" -#include "llvm/Support/InstVisitor.h" #include "llvm/Support/raw_ostream.h" -#include "llvm/ADT/STLExtras.h" +#include "llvm/Target/TargetLibraryInfo.h" using namespace llvm; namespace { @@ -71,7 +72,7 @@ namespace { void visitCallSite(CallSite CS); void visitMemoryReference(Instruction &I, Value *Ptr, uint64_t Size, unsigned Align, - const Type *Ty, unsigned Flags); + Type *Ty, unsigned Flags); void visitCallInst(CallInst &I); void visitInvokeInst(InvokeInst &I); @@ -102,7 +103,8 @@ namespace { Module *Mod; AliasAnalysis *AA; DominatorTree *DT; - TargetData *TD; + DataLayout *TD; + TargetLibraryInfo *TLI; std::string Messages; raw_string_ostream MessagesStr; @@ -117,6 +119,7 @@ namespace { virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired(); + AU.addRequired(); AU.addRequired(); } virtual void print(raw_ostream &O, const Module *M) const {} @@ -149,6 +152,7 @@ namespace { char Lint::ID = 0; INITIALIZE_PASS_BEGIN(Lint, "lint", "Statically lint-checks LLVM IR", false, true) +INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) INITIALIZE_PASS_DEPENDENCY(DominatorTree) INITIALIZE_AG_DEPENDENCY(AliasAnalysis) INITIALIZE_PASS_END(Lint, "lint", "Statically lint-checks LLVM IR", @@ -173,7 +177,8 @@ bool Lint::runOnFunction(Function &F) { Mod = F.getParent(); AA = &getAnalysis(); DT = &getAnalysis(); - TD = getAnalysisIfAvailable(); + TD = getAnalysisIfAvailable(); + TLI = &getAnalysis(); visit(F); dbgs() << MessagesStr.str(); Messages.clear(); @@ -201,7 +206,7 @@ void Lint::visitCallSite(CallSite CS) { "Undefined behavior: Caller and callee calling convention differ", &I); - const FunctionType *FT = F->getFunctionType(); + FunctionType *FT = F->getFunctionType(); unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin()); Assert1(FT->isVarArg() ? @@ -226,20 +231,21 @@ void Lint::visitCallSite(CallSite CS) { "Undefined behavior: Call argument type mismatches " "callee parameter type", &I); - // Check that noalias arguments don't alias other arguments. The - // AliasAnalysis API isn't expressive enough for what we really want - // to do. Known partial overlap is not distinguished from the case - // where nothing is known. + // Check that noalias arguments don't alias other arguments. This is + // not fully precise because we don't know the sizes of the dereferenced + // memory regions. if (Formal->hasNoAliasAttr() && Actual->getType()->isPointerTy()) for (CallSite::arg_iterator BI = CS.arg_begin(); BI != AE; ++BI) - Assert1(AI == BI || - !(*BI)->getType()->isPointerTy() || - AA->alias(*AI, *BI) != AliasAnalysis::MustAlias, - "Unusual: noalias argument aliases another argument", &I); + if (AI != BI && (*BI)->getType()->isPointerTy()) { + AliasAnalysis::AliasResult Result = AA->alias(*AI, *BI); + Assert1(Result != AliasAnalysis::MustAlias && + Result != AliasAnalysis::PartialAlias, + "Unusual: noalias argument aliases another argument", &I); + } // Check that an sret argument points to valid memory. if (Formal->hasStructRetAttr() && Actual->getType()->isPointerTy()) { - const Type *Ty = + Type *Ty = cast(Formal->getType())->getElementType(); visitMemoryReference(I, Actual, AA->getTypeStoreSize(Ty), TD ? TD->getABITypeAlignment(Ty) : 0, @@ -363,7 +369,7 @@ void Lint::visitReturnInst(ReturnInst &I) { // TODO: Check readnone/readonly function attributes. void Lint::visitMemoryReference(Instruction &I, Value *Ptr, uint64_t Size, unsigned Align, - const Type *Ty, unsigned Flags) { + Type *Ty, unsigned Flags) { // If no memory is being referenced, it doesn't matter if the pointer // is valid. if (Size == 0) @@ -405,17 +411,50 @@ void Lint::visitMemoryReference(Instruction &I, "Undefined behavior: Branch to non-blockaddress", &I); } - if (TD) { - if (Align == 0 && Ty) Align = TD->getABITypeAlignment(Ty); - - if (Align != 0) { - unsigned BitWidth = TD->getTypeSizeInBits(Ptr->getType()); - APInt Mask = APInt::getAllOnesValue(BitWidth), - KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); - ComputeMaskedBits(Ptr, Mask, KnownZero, KnownOne, TD); - Assert1(!(KnownOne & APInt::getLowBitsSet(BitWidth, Log2_32(Align))), - "Undefined behavior: Memory reference address is misaligned", &I); + // Check for buffer overflows and misalignment. + // Only handles memory references that read/write something simple like an + // alloca instruction or a global variable. + int64_t Offset = 0; + if (Value *Base = GetPointerBaseWithConstantOffset(Ptr, Offset, TD)) { + // OK, so the access is to a constant offset from Ptr. Check that Ptr is + // something we can handle and if so extract the size of this base object + // along with its alignment. + uint64_t BaseSize = AliasAnalysis::UnknownSize; + unsigned BaseAlign = 0; + + if (AllocaInst *AI = dyn_cast(Base)) { + Type *ATy = AI->getAllocatedType(); + if (TD && !AI->isArrayAllocation() && ATy->isSized()) + BaseSize = TD->getTypeAllocSize(ATy); + BaseAlign = AI->getAlignment(); + if (TD && BaseAlign == 0 && ATy->isSized()) + BaseAlign = TD->getABITypeAlignment(ATy); + } else if (GlobalVariable *GV = dyn_cast(Base)) { + // If the global may be defined differently in another compilation unit + // then don't warn about funky memory accesses. + if (GV->hasDefinitiveInitializer()) { + Type *GTy = GV->getType()->getElementType(); + if (TD && GTy->isSized()) + BaseSize = TD->getTypeAllocSize(GTy); + BaseAlign = GV->getAlignment(); + if (TD && BaseAlign == 0 && GTy->isSized()) + BaseAlign = TD->getABITypeAlignment(GTy); + } } + + // Accesses from before the start or after the end of the object are not + // defined. + Assert1(Size == AliasAnalysis::UnknownSize || + BaseSize == AliasAnalysis::UnknownSize || + (Offset >= 0 && Offset + Size <= BaseSize), + "Undefined behavior: Buffer overflow", &I); + + // Accesses that say that the memory is more aligned than it is are not + // defined. + if (TD && Align == 0 && Ty && Ty->isSized()) + Align = TD->getABITypeAlignment(Ty); + Assert1(!BaseAlign || Align <= MinAlign(BaseAlign, Offset), + "Undefined behavior: Memory reference address is misaligned", &I); } } @@ -465,14 +504,13 @@ void Lint::visitShl(BinaryOperator &I) { "Undefined result: Shift count out of range", &I); } -static bool isZero(Value *V, TargetData *TD) { +static bool isZero(Value *V, DataLayout *TD) { // Assume undef could be zero. if (isa(V)) return true; unsigned BitWidth = cast(V->getType())->getBitWidth(); - APInt Mask = APInt::getAllOnesValue(BitWidth), - KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); - ComputeMaskedBits(V, Mask, KnownZero, KnownOne, TD); + APInt KnownZero(BitWidth, 0), KnownOne(BitWidth, 0); + ComputeMaskedBits(V, KnownZero, KnownOne, TD); return KnownZero.isAllOnesValue(); } @@ -566,7 +604,7 @@ Value *Lint::findValueImpl(Value *V, bool OffsetOk, // TODO: Look through eliminable cast pairs. // TODO: Look through calls with unique return values. // TODO: Look through vector insert/extract/shuffle. - V = OffsetOk ? V->getUnderlyingObject() : V->stripPointerCasts(); + V = OffsetOk ? GetUnderlyingObject(V, TD) : V->stripPointerCasts(); if (LoadInst *L = dyn_cast(V)) { BasicBlock::iterator BBI = L; BasicBlock *BB = L->getParent(); @@ -591,8 +629,7 @@ Value *Lint::findValueImpl(Value *V, bool OffsetOk, return findValueImpl(CI->getOperand(0), OffsetOk, Visited); } else if (ExtractValueInst *Ex = dyn_cast(V)) { if (Value *W = FindInsertedValue(Ex->getAggregateOperand(), - Ex->idx_begin(), - Ex->idx_end())) + Ex->getIndices())) if (W != V) return findValueImpl(W, OffsetOk, Visited); } else if (ConstantExpr *CE = dyn_cast(V)) { @@ -605,10 +642,8 @@ Value *Lint::findValueImpl(Value *V, bool OffsetOk, Type::getInt64Ty(V->getContext()))) return findValueImpl(CE->getOperand(0), OffsetOk, Visited); } else if (CE->getOpcode() == Instruction::ExtractValue) { - const SmallVector &Indices = CE->getIndices(); - if (Value *W = FindInsertedValue(CE->getOperand(0), - Indices.begin(), - Indices.end())) + ArrayRef Indices = CE->getIndices(); + if (Value *W = FindInsertedValue(CE->getOperand(0), Indices)) if (W != V) return findValueImpl(W, OffsetOk, Visited); } @@ -616,10 +651,10 @@ Value *Lint::findValueImpl(Value *V, bool OffsetOk, // As a last resort, try SimplifyInstruction or constant folding. if (Instruction *Inst = dyn_cast(V)) { - if (Value *W = SimplifyInstruction(Inst, TD, DT)) + if (Value *W = SimplifyInstruction(Inst, TD, TLI, DT)) return findValueImpl(W, OffsetOk, Visited); } else if (ConstantExpr *CE = dyn_cast(V)) { - if (Value *W = ConstantFoldConstantExpression(CE, TD)) + if (Value *W = ConstantFoldConstantExpression(CE, TD, TLI)) if (W != V) return findValueImpl(W, OffsetOk, Visited); }