1 //===- PointerTracking.h - Pointer Bounds Tracking --------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements tracking of pointer bounds.
11 // It knows that the libc functions "calloc" and "realloc" allocate memory, thus
12 // you should avoid using this pass if they mean something else for your
15 // All methods assume that the pointer is not NULL, if it is then the returned
16 // allocation size is wrong, and the result from checkLimits is wrong too.
17 // It also assumes that pointers are valid, and that it is not analyzing a
18 // use-after-free scenario.
19 // Due to these limitations the "size" returned by these methods should be
20 // considered as either 0 or the returned size.
22 // Another analysis pass should be used to find use-after-free/NULL dereference
25 //===----------------------------------------------------------------------===//
27 #ifndef LLVM_ANALYSIS_POINTERTRACKING_H
28 #define LLVM_ANALYSIS_POINTERTRACKING_H
30 #include "llvm/ADT/SmallSet.h"
31 #include "llvm/Analysis/Dominators.h"
32 #include "llvm/Instructions.h"
33 #include "llvm/Pass.h"
34 #include "llvm/Support/PredIteratorCache.h"
38 class ScalarEvolution;
44 // Result from solver, assuming pointer is not NULL,
45 // and it is not a use-after-free situation.
47 AlwaysFalse,// always false with above constraints
48 AlwaysTrue,// always true with above constraints
49 Unknown // it can sometimes be true, sometimes false, or it is undecided
52 class PointerTracking : public FunctionPass {
54 typedef ICmpInst::Predicate Predicate;
58 virtual bool doInitialization(Module &M);
60 // If this pointer directly points to an allocation, return
61 // the number of elements of type Ty allocated.
62 // Otherwise return CouldNotCompute.
63 // Since allocations can fail by returning NULL, the real element count
64 // for every allocation is either 0 or the value returned by this function.
65 const SCEV *getAllocationElementCount(Value *P) const;
67 // Same as getAllocationSize() but returns size in bytes.
68 // We consider one byte as 8 bits.
69 const SCEV *getAllocationSizeInBytes(Value *V) const;
71 // Given a Pointer, determine a base pointer of known size, and an offset
73 // When unable to determine, sets Base to NULL, and Limit/Offset to
75 // BaseSize, and Offset are in bytes: Pointer == Base + Offset
76 void getPointerOffset(Value *Pointer, Value *&Base, const SCEV *& BaseSize,
77 const SCEV *&Offset) const;
79 // Compares the 2 scalar evolution expressions according to predicate,
80 // and if it can prove that the result is always true or always false
81 // return AlwaysTrue/AlwaysFalse. Otherwise it returns Unknown.
82 enum SolverResult compareSCEV(const SCEV *A, Predicate Pred, const SCEV *B,
85 // Determines whether the condition LHS <Pred> RHS is sufficient
86 // for the condition A <Pred> B to hold.
87 // Currently only ULT/ULE is supported.
88 // This errs on the side of returning false.
89 bool conditionSufficient(const SCEV *LHS, Predicate Pred1, const SCEV *RHS,
90 const SCEV *A, Predicate Pred2, const SCEV *B,
93 // Determines whether Offset is known to be always in [0, Limit) bounds.
94 // This errs on the side of returning Unknown.
95 enum SolverResult checkLimits(const SCEV *Offset, const SCEV *Limit,
98 virtual bool runOnFunction(Function &F);
99 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
100 void print(raw_ostream &OS, const Module* = 0) const;
108 Function *callocFunc;
109 Function *reallocFunc;
110 PredIteratorCache predCache;
112 SmallPtrSet<const SCEV*, 1> analyzing;
114 enum SolverResult isLoopGuardedBy(const Loop *L, Predicate Pred,
115 const SCEV *A, const SCEV *B) const;
116 static bool isMonotonic(const SCEV *S);
117 bool scevPositive(const SCEV *A, const Loop *L, bool strict=true) const;
118 bool conditionSufficient(Value *Cond, bool negated,
119 const SCEV *A, Predicate Pred, const SCEV *B);
120 Value *getConditionToReach(BasicBlock *A,
121 DomTreeNodeBase<BasicBlock> *B,
123 Value *getConditionToReach(BasicBlock *A,
126 const SCEV *computeAllocationCount(Value *P, const Type *&Ty) const;
127 const SCEV *computeAllocationCountForType(Value *P, const Type *Ty) const;