 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
77.0% |
77 / 100 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
86.0% |
86 / 100 |
| |
|
Line Coverage: |
81.8% |
112 / 137 |
| |
 |
|
 |
1 : //== RangeConstraintManager.cpp - Manage range constraints.------*- 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 defines RangeConstraintManager, a class that tracks simple
11 : // equality and inequality constraints on symbolic values of GRState.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #include "SimpleConstraintManager.h"
16 : #include "clang/Checker/PathSensitive/GRState.h"
17 : #include "clang/Checker/PathSensitive/GRStateTrait.h"
18 : #include "clang/Checker/PathSensitive/GRTransferFuncs.h"
19 : #include "clang/Checker/ManagerRegistry.h"
20 : #include "llvm/Support/Debug.h"
21 : #include "llvm/ADT/FoldingSet.h"
22 : #include "llvm/ADT/ImmutableSet.h"
23 : #include "llvm/Support/raw_ostream.h"
24 :
25 : using namespace clang;
26 :
27 : namespace { class ConstraintRange {}; }
28 : static int ConstraintRangeIndex = 0;
29 :
30 : /// A Range represents the closed range [from, to]. The caller must
31 : /// guarantee that from <= to. Note that Range is immutable, so as not
32 : /// to subvert RangeSet's immutability.
33 : namespace {
34 : class Range : public std::pair<const llvm::APSInt*,
35 : const llvm::APSInt*> {
36 : public:
37 5611: Range(const llvm::APSInt &from, const llvm::APSInt &to)
38 5611: : std::pair<const llvm::APSInt*, const llvm::APSInt*>(&from, &to) {
0: branch 1 not taken
5611: branch 2 taken
39 5611: assert(from <= to);
40 5611: }
41 4368: bool Includes(const llvm::APSInt &v) const {
3238: branch 1 taken
1130: branch 2 taken
3132: branch 4 taken
106: branch 5 taken
42 4368: return *first <= v && v <= *second;
43 : }
44 10035: const llvm::APSInt &From() const {
45 10035: return *first;
46 : }
47 10837: const llvm::APSInt &To() const {
48 10837: return *second;
49 : }
50 1741: const llvm::APSInt *getConcreteValue() const {
477: branch 2 taken
1264: branch 3 taken
51 1741: return &From() == &To() ? &From() : NULL;
52 : }
53 :
54 5882: void Profile(llvm::FoldingSetNodeID &ID) const {
55 5882: ID.AddPointer(&From());
56 5882: ID.AddPointer(&To());
57 5882: }
58 : };
59 :
60 :
61 : class RangeTrait : public llvm::ImutContainerInfo<Range> {
62 : public:
63 : // When comparing if one Range is less than another, we should compare
64 : // the actual APSInt values instead of their pointers. This keeps the order
65 : // consistent (instead of comparing by pointer values) and can potentially
66 : // be used to speed up some of the operations in RangeSet.
67 255: static inline bool isLess(key_type_ref lhs, key_type_ref rhs) {
68 : return *lhs.first < *rhs.first || (!(*rhs.first < *lhs.first) &&
255: branch 1 taken
0: branch 2 not taken
0: branch 4 not taken
255: branch 5 taken
0: branch 7 not taken
0: branch 8 not taken
69 255: *lhs.second < *rhs.second);
70 : }
71 : };
72 :
73 : /// RangeSet contains a set of ranges. If the set is empty, then
74 : /// there the value of a symbol is overly constrained and there are no
75 : /// possible values for that symbol.
76 : class RangeSet {
77 : typedef llvm::ImmutableSet<Range, RangeTrait> PrimRangeSet;
78 : PrimRangeSet ranges; // no need to make const, since it is an
79 : // ImmutableSet - this allows default operator=
80 : // to work.
81 : public:
82 : typedef PrimRangeSet::Factory Factory;
83 : typedef PrimRangeSet::iterator iterator;
84 :
85 2427: RangeSet(PrimRangeSet RS) : ranges(RS) {}
86 556: RangeSet(Factory& F) : ranges(F.GetEmptySet()) {}
87 :
88 4262: iterator begin() const { return ranges.begin(); }
89 4262: iterator end() const { return ranges.end(); }
90 :
91 4262: bool isEmpty() const { return ranges.isEmpty(); }
92 :
93 : /// Construct a new RangeSet representing '{ [from, to] }'.
94 3855: RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to)
95 3855: : ranges(F.Add(F.GetEmptySet(), Range(from, to))) {}
96 :
97 : /// Profile - Generates a hash profile of this RangeSet for use
98 : /// by FoldingSet.
99 5729: void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); }
100 :
101 : /// getConcreteValue - If a symbol is contrained to equal a specific integer
102 : /// constant then this method returns that value. Otherwise, it returns
103 : /// NULL.
104 1801: const llvm::APSInt* getConcreteValue() const {
1741: branch 1 taken
60: branch 2 taken
1741: branch 6 taken
60: branch 7 taken
105 1801: return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : 0;
106 : }
107 :
108 : /// AddEQ - Create a new RangeSet with the additional constraint that the
109 : /// value be equal to V.
110 1835: RangeSet AddEQ(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) {
111 : // Search for a range that includes 'V'. If so, return a new RangeSet
112 : // representing { [V, V] }.
1870: branch 4 taken
556: branch 5 taken
113 2426: for (PrimRangeSet::iterator i = begin(), e = end(); i!=e; ++i)
1279: branch 2 taken
591: branch 3 taken
114 1870: if (i->Includes(V))
556: branch 2 taken
1279: branch 3 taken
556: branch 5 taken
1279: branch 6 taken
115 4393: return RangeSet(F, V, V);
116 :
117 556: return RangeSet(F);
118 : }
119 :
120 : /// AddNE - Create a new RangeSet with the additional constraint that the
121 : /// value be not be equal to V.
122 2156: RangeSet AddNE(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) {
123 2156: PrimRangeSet newRanges = ranges;
124 :
125 : // FIXME: We can perhaps enhance ImmutableSet to do this search for us
126 : // in log(N) time using the sorted property of the internal AVL tree.
2227: branch 4 taken
542: branch 5 taken
127 2769: for (iterator i = begin(), e = end(); i != e; ++i) {
1614: branch 2 taken
613: branch 3 taken
128 2227: if (i->Includes(V)) {
129 : // Remove the old range.
130 1614: newRanges = F.Remove(newRanges, *i);
131 : // Split the old range into possibly one or two ranges.
170: branch 3 taken
1444: branch 4 taken
132 1614: if (V != i->From())
133 170: newRanges = F.Add(newRanges, Range(i->From(), BV.Sub1(V)));
1357: branch 3 taken
257: branch 4 taken
134 1614: if (V != i->To())
135 1357: newRanges = F.Add(newRanges, Range(BV.Add1(V), i->To()));
136 : // All of the ranges are non-overlapping, so we can stop.
137 1614: break;
138 : }
139 2156: }
140 :
141 2156: return newRanges;
142 : }
143 :
144 : /// AddNE - Create a new RangeSet with the additional constraint that the
145 : /// value be less than V.
146 15: RangeSet AddLT(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) {
147 15: PrimRangeSet newRanges = F.GetEmptySet();
148 :
15: branch 4 taken
15: branch 5 taken
149 30: for (iterator i = begin(), e = end() ; i != e ; ++i) {
15: branch 2 taken
0: branch 3 not taken
12: branch 7 taken
3: branch 8 taken
12: branch 9 taken
3: branch 10 taken
150 15: if (i->Includes(V) && i->From() < V)
151 12: newRanges = F.Add(newRanges, Range(i->From(), BV.Sub1(V)));
0: branch 3 not taken
3: branch 4 taken
152 3: else if (i->To() < V)
153 0: newRanges = F.Add(newRanges, *i);
154 15: }
155 :
156 15: return newRanges;
157 : }
158 :
159 117: RangeSet AddLE(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) {
160 117: PrimRangeSet newRanges = F.GetEmptySet();
161 :
117: branch 4 taken
117: branch 5 taken
162 234: for (iterator i = begin(), e = end(); i != e; ++i) {
163 : // Strictly we should test for includes *V + 1, but no harm is
164 : // done by this formulation
101: branch 2 taken
16: branch 3 taken
165 117: if (i->Includes(V))
166 101: newRanges = F.Add(newRanges, Range(i->From(), V));
0: branch 3 not taken
16: branch 4 taken
167 16: else if (i->To() <= V)
168 0: newRanges = F.Add(newRanges, *i);
169 117: }
170 :
171 117: return newRanges;
172 : }
173 :
174 124: RangeSet AddGT(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) {
175 124: PrimRangeSet newRanges = F.GetEmptySet();
176 :
124: branch 4 taken
124: branch 5 taken
177 248: for (PrimRangeSet::iterator i = begin(), e = end(); i != e; ++i) {
108: branch 2 taken
16: branch 3 taken
101: branch 7 taken
7: branch 8 taken
101: branch 9 taken
23: branch 10 taken
178 124: if (i->Includes(V) && i->To() > V)
179 101: newRanges = F.Add(newRanges, Range(BV.Add1(V), i->To()));
16: branch 3 taken
7: branch 4 taken
180 23: else if (i->From() > V)
181 16: newRanges = F.Add(newRanges, *i);
182 124: }
183 :
184 124: return newRanges;
185 : }
186 :
187 15: RangeSet AddGE(BasicValueFactory &BV, Factory &F, const llvm::APSInt &V) {
188 15: PrimRangeSet newRanges = F.GetEmptySet();
189 :
15: branch 4 taken
15: branch 5 taken
190 30: for (PrimRangeSet::iterator i = begin(), e = end(); i != e; ++i) {
191 : // Strictly we should test for includes *V - 1, but no harm is
192 : // done by this formulation
15: branch 2 taken
0: branch 3 not taken
193 15: if (i->Includes(V))
194 15: newRanges = F.Add(newRanges, Range(V, i->To()));
0: branch 3 not taken
0: branch 4 not taken
195 0: else if (i->From() >= V)
196 0: newRanges = F.Add(newRanges, *i);
197 15: }
198 :
199 15: return newRanges;
200 : }
201 :
202 0: void print(llvm::raw_ostream &os) const {
203 0: bool isFirst = true;
204 0: os << "{ ";
0: branch 4 not taken
0: branch 5 not taken
205 0: for (iterator i = begin(), e = end(); i != e; ++i) {
0: branch 0 not taken
0: branch 1 not taken
206 0: if (isFirst)
207 0: isFirst = false;
208 : else
209 0: os << ", ";
210 :
211 : os << '[' << i->From().toString(10) << ", " << i->To().toString(10)
212 0: << ']';
213 0: }
214 0: os << " }";
215 0: }
216 :
217 1594: bool operator==(const RangeSet &other) const {
218 1594: return ranges == other.ranges;
219 : }
220 : };
221 : } // end anonymous namespace
222 :
223 : typedef llvm::ImmutableMap<SymbolRef,RangeSet> ConstraintRangeTy;
224 :
225 : namespace clang {
226 : template<>
227 : struct GRStateTrait<ConstraintRange>
228 : : public GRStatePartialTrait<ConstraintRangeTy> {
229 38496: static inline void* GDMIndex() { return &ConstraintRangeIndex; }
230 : };
231 : }
232 :
233 : namespace {
1272: branch 2 taken
0: branch 3 not taken
0: branch 7 not taken
0: branch 8 not taken
234 1272: class RangeConstraintManager : public SimpleConstraintManager{
235 : RangeSet GetRange(const GRState *state, SymbolRef sym);
236 : public:
237 1272: RangeConstraintManager(GRSubEngine &subengine)
238 1272: : SimpleConstraintManager(subengine) {}
239 :
240 : const GRState* AssumeSymNE(const GRState* St, SymbolRef sym,
241 : const llvm::APSInt& V);
242 :
243 : const GRState* AssumeSymEQ(const GRState* St, SymbolRef sym,
244 : const llvm::APSInt& V);
245 :
246 : const GRState* AssumeSymLT(const GRState* St, SymbolRef sym,
247 : const llvm::APSInt& V);
248 :
249 : const GRState* AssumeSymGT(const GRState* St, SymbolRef sym,
250 : const llvm::APSInt& V);
251 :
252 : const GRState* AssumeSymGE(const GRState* St, SymbolRef sym,
253 : const llvm::APSInt& V);
254 :
255 : const GRState* AssumeSymLE(const GRState* St, SymbolRef sym,
256 : const llvm::APSInt& V);
257 :
258 : const llvm::APSInt* getSymVal(const GRState* St, SymbolRef sym) const;
259 :
260 : // FIXME: Refactor into SimpleConstraintManager?
261 106: bool isEqual(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const {
262 106: const llvm::APSInt *i = getSymVal(St, sym);
4: branch 0 taken
102: branch 1 taken
263 106: return i ? *i == V : false;
264 : }
265 :
266 : const GRState* RemoveDeadBindings(const GRState* St, SymbolReaper& SymReaper);
267 :
268 : void print(const GRState* St, llvm::raw_ostream& Out,
269 : const char* nl, const char *sep);
270 :
271 : private:
272 : RangeSet::Factory F;
273 : };
274 :
275 : } // end anonymous namespace
276 :
277 : ConstraintManager* clang::CreateRangeConstraintManager(GRStateManager&,
278 1272: GRSubEngine &subeng) {
279 1272: return new RangeConstraintManager(subeng);
280 : }
281 :
282 : const llvm::APSInt* RangeConstraintManager::getSymVal(const GRState* St,
283 3454: SymbolRef sym) const {
284 3454: const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(sym);
1801: branch 0 taken
1653: branch 1 taken
285 3454: return T ? T->getConcreteValue() : NULL;
286 : }
287 :
288 : /// Scan all symbols referenced by the constraints. If the symbol is not alive
289 : /// as marked in LSymbols, mark it as dead in DSymbols.
290 : const GRState*
291 : RangeConstraintManager::RemoveDeadBindings(const GRState* state,
292 6836: SymbolReaper& SymReaper) {
293 :
294 6836: ConstraintRangeTy CR = state->get<ConstraintRange>();
295 6836: ConstraintRangeTy::Factory& CRFactory = state->get_context<ConstraintRange>();
296 :
5543: branch 4 taken
6836: branch 5 taken
297 12379: for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) {
298 5543: SymbolRef sym = I.getKey();
530: branch 1 taken
5013: branch 2 taken
299 5543: if (SymReaper.maybeDead(sym))
300 530: CR = CRFactory.Remove(CR, sym);
301 6836: }
302 :
303 6836: return state->set<ConstraintRange>(CR);
304 : }
305 :
306 : //===------------------------------------------------------------------------===
307 : // AssumeSymX methods: public interface for RangeConstraintManager.
308 : //===------------------------------------------------------------------------===/
309 :
310 : RangeSet
311 4262: RangeConstraintManager::GetRange(const GRState *state, SymbolRef sym) {
1686: branch 1 taken
2576: branch 2 taken
312 4262: if (ConstraintRangeTy::data_type* V = state->get<ConstraintRange>(sym))
313 1686: return *V;
314 :
315 : // Lazily generate a new RangeSet representing all possible values for the
316 : // given symbol type.
317 2576: QualType T = state->getSymbolManager().getType(sym);
318 2576: BasicValueFactory& BV = state->getBasicVals();
319 2576: return RangeSet(F, BV.getMinValue(T), BV.getMaxValue(T));
320 : }
321 :
322 : //===------------------------------------------------------------------------===
323 : // AssumeSymX methods: public interface for RangeConstraintManager.
324 : //===------------------------------------------------------------------------===/
325 :
326 : #define AssumeX(OP)\
327 : const GRState*\
328 : RangeConstraintManager::AssumeSym ## OP(const GRState* state, SymbolRef sym,\
329 : const llvm::APSInt& V){\
330 : const RangeSet& R = GetRange(state, sym).Add##OP(state->getBasicVals(), F, V);\
331 : return !R.isEmpty() ? state->set<ConstraintRange>(sym, R) : NULL;\
332 : }
333 :
1279: branch 4 taken
556: branch 5 taken
334 1835: AssumeX(EQ)
1900: branch 4 taken
256: branch 5 taken
335 2156: AssumeX(NE)
12: branch 4 taken
3: branch 5 taken
336 15: AssumeX(LT)
117: branch 4 taken
7: branch 5 taken
337 124: AssumeX(GT)
101: branch 4 taken
16: branch 5 taken
338 117: AssumeX(LE)
15: branch 4 taken
0: branch 5 not taken
339 15: AssumeX(GE)
340 :
341 : //===------------------------------------------------------------------------===
342 : // Pretty-printing.
343 : //===------------------------------------------------------------------------===/
344 :
345 : void RangeConstraintManager::print(const GRState* St, llvm::raw_ostream& Out,
346 0: const char* nl, const char *sep) {
347 :
348 0: ConstraintRangeTy Ranges = St->get<ConstraintRange>();
349 :
0: branch 1 not taken
0: branch 2 not taken
350 0: if (Ranges.isEmpty())
351 0: return;
352 :
353 0: Out << nl << sep << "ranges of symbol values:";
354 :
0: branch 4 not taken
0: branch 5 not taken
355 0: for (ConstraintRangeTy::iterator I=Ranges.begin(), E=Ranges.end(); I!=E; ++I){
356 0: Out << nl << ' ' << I.getKey() << " : ";
357 0: I.getData().print(Out);
358 0: }
359 0: }
Generated: 2010-02-10 01:31 by zcov