LLVM API Documentation

PointerTracking.h

Go to the documentation of this file.
00001 //===- PointerTracking.h - Pointer Bounds Tracking --------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements tracking of pointer bounds.
00011 // It knows that the libc functions "calloc" and "realloc" allocate memory, thus
00012 // you should avoid using this pass if they mean something else for your
00013 // language.
00014 //
00015 // All methods assume that the pointer is not NULL, if it is then the returned
00016 // allocation size is wrong, and the result from checkLimits is wrong too.
00017 // It also assumes that pointers are valid, and that it is not analyzing a
00018 // use-after-free scenario.
00019 // Due to these limitations the "size" returned by these methods should be
00020 // considered as either 0 or the returned size.
00021 //
00022 // Another analysis pass should be used to find use-after-free/NULL dereference
00023 // bugs.
00024 //
00025 //===----------------------------------------------------------------------===//
00026 
00027 #ifndef LLVM_ANALYSIS_POINTERTRACKING_H
00028 #define LLVM_ANALYSIS_POINTERTRACKING_H
00029 
00030 #include "llvm/ADT/SmallSet.h"
00031 #include "llvm/Analysis/Dominators.h"
00032 #include "llvm/Instructions.h"
00033 #include "llvm/Pass.h"
00034 #include "llvm/Support/PredIteratorCache.h"
00035 
00036 namespace llvm {
00037   class DominatorTree;
00038   class ScalarEvolution;
00039   class SCEV;
00040   class Loop;
00041   class LoopInfo;
00042   class TargetData;
00043 
00044   // Result from solver, assuming pointer is not NULL,
00045   // and it is not a use-after-free situation.
00046   enum SolverResult {
00047     AlwaysFalse,// always false with above constraints
00048     AlwaysTrue,// always true with above constraints
00049     Unknown // it can sometimes be true, sometimes false, or it is undecided
00050   };
00051 
00052   class PointerTracking : public FunctionPass {
00053   public:
00054     typedef ICmpInst::Predicate Predicate;
00055     static char ID;
00056     PointerTracking();
00057 
00058     virtual bool doInitialization(Module &M);
00059 
00060     // If this pointer directly points to an allocation, return
00061     // the number of elements of type Ty allocated.
00062     // Otherwise return CouldNotCompute.
00063     // Since allocations can fail by returning NULL, the real element count
00064     // for every allocation is either 0 or the value returned by this function.
00065     const SCEV *getAllocationElementCount(Value *P) const;
00066 
00067     // Same as getAllocationSize() but returns size in bytes.
00068     // We consider one byte as 8 bits.
00069     const SCEV *getAllocationSizeInBytes(Value *V) const;
00070 
00071     // Given a Pointer, determine a base pointer of known size, and an offset
00072     // therefrom.
00073     // When unable to determine, sets Base to NULL, and Limit/Offset to
00074     // CouldNotCompute.
00075     // BaseSize, and Offset are in bytes: Pointer == Base + Offset
00076     void getPointerOffset(Value *Pointer, Value *&Base, const SCEV *& BaseSize,
00077                           const SCEV *&Offset) const;
00078 
00079     // Compares the 2 scalar evolution expressions according to predicate,
00080     // and if it can prove that the result is always true or always false
00081     // return AlwaysTrue/AlwaysFalse. Otherwise it returns Unknown.
00082     enum SolverResult compareSCEV(const SCEV *A, Predicate Pred, const SCEV *B,
00083                                   const Loop *L);
00084 
00085     // Determines whether the condition LHS <Pred> RHS is sufficient
00086     // for the condition A <Pred> B to hold.
00087     // Currently only ULT/ULE is supported.
00088     // This errs on the side of returning false.
00089     bool conditionSufficient(const SCEV *LHS, Predicate Pred1, const SCEV *RHS,
00090                              const SCEV *A, Predicate Pred2, const SCEV *B,
00091                              const Loop *L);
00092 
00093     // Determines whether Offset is known to be always in [0, Limit) bounds.
00094     // This errs on the side of returning Unknown.
00095     enum SolverResult checkLimits(const SCEV *Offset, const SCEV *Limit,
00096                                   BasicBlock *BB);
00097 
00098     virtual bool runOnFunction(Function &F);
00099     virtual void getAnalysisUsage(AnalysisUsage &AU) const;
00100     void print(raw_ostream &OS, const Module* = 0) const;
00101     virtual void print(std::ostream &OS, const Module* = 0) const;
00102   private:
00103     Function *FF;
00104     TargetData *TD;
00105     ScalarEvolution *SE;
00106     LoopInfo *LI;
00107     DominatorTree *DT;
00108 
00109     Function *callocFunc;
00110     Function *reallocFunc;
00111     PredIteratorCache predCache;
00112 
00113     SmallPtrSet<const SCEV*, 1> analyzing;
00114 
00115     enum SolverResult isLoopGuardedBy(const Loop *L, Predicate Pred,
00116                                       const SCEV *A, const SCEV *B) const;
00117     static bool isMonotonic(const SCEV *S);
00118     bool scevPositive(const SCEV *A, const Loop *L, bool strict=true) const;
00119     bool conditionSufficient(Value *Cond, bool negated,
00120                              const SCEV *A, Predicate Pred, const SCEV *B);
00121     Value *getConditionToReach(BasicBlock *A,
00122                                DomTreeNodeBase<BasicBlock> *B,
00123                                bool &negated);
00124     Value *getConditionToReach(BasicBlock *A,
00125                                BasicBlock *B,
00126                                bool &negated);
00127     const SCEV *computeAllocationCount(Value *P, const Type *&Ty) const;
00128     const SCEV *computeAllocationCountForType(Value *P, const Type *Ty) const;
00129   };
00130 }
00131 #endif
00132