← Back to branch summary

~ubuntu-branches/ubuntu/feisty/clamav/feisty

« back to all changes in this revision

Viewing changes to libclamav/c++/llvm/include/llvm/Analysis/PointerTracking.h

  • Committer: Bazaar Package Importer
  • Author(s): Kees Cook
  • Date: 2007-02-20 10:33:44 UTC
  • mto: This revision was merged to the branch mainline in revision 16.
  • Revision ID: james.westby@ubuntu.com-20070220103344-zgcu2psnx9d98fpa
Tags: upstream-0.90
Import upstream version 0.90

Show diffs side-by-side

added added

removed removed

Lines of Context:
libclamav/c++/llvm/include/llvm/Analysis/PointerTracking.h
1
 
//===- PointerTracking.h - Pointer Bounds Tracking --------------*- C++ -*-===//
2
 
//
3
 
//                     The LLVM Compiler Infrastructure
4
 
//
5
 
// This file is distributed under the University of Illinois Open Source
6
 
// License. See LICENSE.TXT for details.
7
 
//
8
 
//===----------------------------------------------------------------------===//
9
 
//
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
13
 
// language.
14
 
//
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.
21
 
//
22
 
// Another analysis pass should be used to find use-after-free/NULL dereference
23
 
// bugs.
24
 
//
25
 
//===----------------------------------------------------------------------===//
26
 
 
27
 
#ifndef LLVM_ANALYSIS_POINTERTRACKING_H
28
 
#define LLVM_ANALYSIS_POINTERTRACKING_H
29
 
 
30
 
#include "llvm/ADT/SmallPtrSet.h"
31
 
#include "llvm/Analysis/Dominators.h"
32
 
#include "llvm/Instructions.h"
33
 
#include "llvm/Pass.h"
34
 
#include "llvm/Support/PredIteratorCache.h"
35
 
 
36
 
namespace llvm {
37
 
  class DominatorTree;
38
 
  class ScalarEvolution;
39
 
  class SCEV;
40
 
  class Loop;
41
 
  class LoopInfo;
42
 
  class TargetData;
43
 
 
44
 
  // Result from solver, assuming pointer is not NULL,
45
 
  // and it is not a use-after-free situation.
46
 
  enum SolverResult {
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
50
 
  };
51
 
 
52
 
  class PointerTracking : public FunctionPass {
53
 
  public:
54
 
    typedef ICmpInst::Predicate Predicate;
55
 
    static char ID;
56
 
    PointerTracking();
57
 
 
58
 
    virtual bool doInitialization(Module &M);
59
 
 
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;
66
 
 
67
 
    // Same as getAllocationSize() but returns size in bytes.
68
 
    // We consider one byte as 8 bits.
69
 
    const SCEV *getAllocationSizeInBytes(Value *V) const;
70
 
 
71
 
    // Given a Pointer, determine a base pointer of known size, and an offset
72
 
    // therefrom.
73
 
    // When unable to determine, sets Base to NULL, and Limit/Offset to
74
 
    // CouldNotCompute.
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;
78
 
 
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,
83
 
                                  const Loop *L);
84
 
 
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,
91
 
                             const Loop *L);
92
 
 
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,
96
 
                                  BasicBlock *BB);
97
 
 
98
 
    virtual bool runOnFunction(Function &F);
99
 
    virtual void getAnalysisUsage(AnalysisUsage &AU) const;
100
 
    void print(raw_ostream &OS, const Module* = 0) const;
101
 
    Value *computeAllocationCountValue(Value *P, const Type *&Ty) const;
102
 
  private:
103
 
    Function *FF;
104
 
    TargetData *TD;
105
 
    ScalarEvolution *SE;
106
 
    LoopInfo *LI;
107
 
    DominatorTree *DT;
108
 
 
109
 
    Function *callocFunc;
110
 
    Function *reallocFunc;
111
 
    PredIteratorCache predCache;
112
 
 
113
 
    SmallPtrSet<const SCEV*, 1> analyzing;
114
 
 
115
 
    enum SolverResult isLoopGuardedBy(const Loop *L, Predicate Pred,
116
 
                                      const SCEV *A, const SCEV *B) const;
117
 
    static bool isMonotonic(const SCEV *S);
118
 
    bool scevPositive(const SCEV *A, const Loop *L, bool strict=true) const;
119
 
    bool conditionSufficient(Value *Cond, bool negated,
120
 
                             const SCEV *A, Predicate Pred, const SCEV *B);
121
 
    Value *getConditionToReach(BasicBlock *A,
122
 
                               DomTreeNodeBase<BasicBlock> *B,
123
 
                               bool &negated);
124
 
    Value *getConditionToReach(BasicBlock *A,
125
 
                               BasicBlock *B,
126
 
                               bool &negated);
127
 
    const SCEV *computeAllocationCount(Value *P, const Type *&Ty) const;
128
 
    const SCEV *computeAllocationCountForType(Value *P, const Type *Ty) const;
129
 
  };
130
 
}
131
 
#endif
132