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
+