1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
//===- 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/SmallPtrSet.h"
#if LLVM_VERSION < 35
#include "llvm/Analysis/Dominators.h"
#include "llvm/Support/PredIteratorCache.h"
#else
#include "llvm/IR/Dominators.h"
#include "llvm/IR/PredIteratorCache.h"
#include "llvm/IR/DataLayout.h"
#endif
#include "llvm/Pass.h"
#include "llvm30_compat.h"
#if LLVM_VERSION < 33
#include "llvm/Instructions.h"
#else
#include "llvm/IR/Instructions.h"
#endif
namespace llvm {
class DominatorTree;
class ScalarEvolution;
class SCEV;
class Loop;
class LoopInfo;
#if LLVM_VERSION < 32
class TargetData;
#else
class DataLayout;
#endif
// 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
};
#if LLVM_VERSION >= 29
void initializePointerTrackingPass(PassRegistry&);
#endif
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;
Value *computeAllocationCountValue(Value *P, constType *&Ty) const;
private:
Function *FF;
#if LLVM_VERSION < 32
TargetData *TD;
#elif LLVM_VERSION < 35
DataLayout *TD;
#else
const DataLayout *TD;
#endif
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, constType *&Ty) const;
const SCEV *computeAllocationCountForType(Value *P, constType *Ty) const;
};
}
#endif
|
