diff options
author | rdivacky <rdivacky@FreeBSD.org> | 2009-10-14 17:57:32 +0000 |
---|---|---|
committer | rdivacky <rdivacky@FreeBSD.org> | 2009-10-14 17:57:32 +0000 |
commit | cd749a9c07f1de2fb8affde90537efa4bc3e7c54 (patch) | |
tree | b21f6de4e08b89bb7931806bab798fc2a5e3a686 /include/llvm/Analysis/PointerTracking.h | |
parent | 72621d11de5b873f1695f391eb95f0b336c3d2d4 (diff) | |
download | FreeBSD-src-cd749a9c07f1de2fb8affde90537efa4bc3e7c54.zip FreeBSD-src-cd749a9c07f1de2fb8affde90537efa4bc3e7c54.tar.gz |
Update llvm to r84119.
Diffstat (limited to 'include/llvm/Analysis/PointerTracking.h')
-rw-r--r-- | include/llvm/Analysis/PointerTracking.h | 131 |
1 files changed, 131 insertions, 0 deletions
diff --git a/include/llvm/Analysis/PointerTracking.h b/include/llvm/Analysis/PointerTracking.h new file mode 100644 index 0000000..a14bbf0 --- /dev/null +++ b/include/llvm/Analysis/PointerTracking.h @@ -0,0 +1,131 @@ +//===- PointerTracking.h - Pointer Bounds Tracking --------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements tracking of pointer bounds. +// It knows that the libc functions "calloc" and "realloc" allocate memory, thus +// you should avoid using this pass if they mean something else for your +// language. +// +// All methods assume that the pointer is not NULL, if it is then the returned +// allocation size is wrong, and the result from checkLimits is wrong too. +// It also assumes that pointers are valid, and that it is not analyzing a +// use-after-free scenario. +// Due to these limitations the "size" returned by these methods should be +// considered as either 0 or the returned size. +// +// Another analysis pass should be used to find use-after-free/NULL dereference +// bugs. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_POINTERTRACKING_H +#define LLVM_ANALYSIS_POINTERTRACKING_H + +#include "llvm/ADT/SmallSet.h" +#include "llvm/Analysis/Dominators.h" +#include "llvm/Instructions.h" +#include "llvm/Pass.h" +#include "llvm/Support/PredIteratorCache.h" + +namespace llvm { + class DominatorTree; + class ScalarEvolution; + class SCEV; + class Loop; + class LoopInfo; + class TargetData; + + // Result from solver, assuming pointer is not NULL, + // and it is not a use-after-free situation. + enum SolverResult { + AlwaysFalse,// always false with above constraints + AlwaysTrue,// always true with above constraints + Unknown // it can sometimes be true, sometimes false, or it is undecided + }; + + class PointerTracking : public FunctionPass { + public: + typedef ICmpInst::Predicate Predicate; + static char ID; + PointerTracking(); + + virtual bool doInitialization(Module &M); + + // If this pointer directly points to an allocation, return + // the number of elements of type Ty allocated. + // Otherwise return CouldNotCompute. + // Since allocations can fail by returning NULL, the real element count + // for every allocation is either 0 or the value returned by this function. + const SCEV *getAllocationElementCount(Value *P) const; + + // Same as getAllocationSize() but returns size in bytes. + // We consider one byte as 8 bits. + const SCEV *getAllocationSizeInBytes(Value *V) const; + + // Given a Pointer, determine a base pointer of known size, and an offset + // therefrom. + // When unable to determine, sets Base to NULL, and Limit/Offset to + // CouldNotCompute. + // BaseSize, and Offset are in bytes: Pointer == Base + Offset + void getPointerOffset(Value *Pointer, Value *&Base, const SCEV *& BaseSize, + const SCEV *&Offset) const; + + // Compares the 2 scalar evolution expressions according to predicate, + // and if it can prove that the result is always true or always false + // return AlwaysTrue/AlwaysFalse. Otherwise it returns Unknown. + enum SolverResult compareSCEV(const SCEV *A, Predicate Pred, const SCEV *B, + const Loop *L); + + // Determines whether the condition LHS <Pred> RHS is sufficient + // for the condition A <Pred> B to hold. + // Currently only ULT/ULE is supported. + // This errs on the side of returning false. + bool conditionSufficient(const SCEV *LHS, Predicate Pred1, const SCEV *RHS, + const SCEV *A, Predicate Pred2, const SCEV *B, + const Loop *L); + + // Determines whether Offset is known to be always in [0, Limit) bounds. + // This errs on the side of returning Unknown. + enum SolverResult checkLimits(const SCEV *Offset, const SCEV *Limit, + BasicBlock *BB); + + virtual bool runOnFunction(Function &F); + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + void print(raw_ostream &OS, const Module* = 0) const; + private: + Function *FF; + TargetData *TD; + ScalarEvolution *SE; + LoopInfo *LI; + DominatorTree *DT; + + Function *callocFunc; + Function *reallocFunc; + PredIteratorCache predCache; + + SmallPtrSet<const SCEV*, 1> analyzing; + + enum SolverResult isLoopGuardedBy(const Loop *L, Predicate Pred, + const SCEV *A, const SCEV *B) const; + static bool isMonotonic(const SCEV *S); + bool scevPositive(const SCEV *A, const Loop *L, bool strict=true) const; + bool conditionSufficient(Value *Cond, bool negated, + const SCEV *A, Predicate Pred, const SCEV *B); + Value *getConditionToReach(BasicBlock *A, + DomTreeNodeBase<BasicBlock> *B, + bool &negated); + Value *getConditionToReach(BasicBlock *A, + BasicBlock *B, + bool &negated); + const SCEV *computeAllocationCount(Value *P, const Type *&Ty) const; + const SCEV *computeAllocationCountForType(Value *P, const Type *Ty) const; + }; +} +#endif + |