1 //== RangeConstraintManager.cpp - Manage range constraints.------*- 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 defines RangeConstraintManager, a class that tracks simple
11 // equality and inequality constraints on symbolic values of GRState.
13 //===----------------------------------------------------------------------===//
15 #include "SimpleConstraintManager.h"
16 #include "clang/GR/PathSensitive/GRState.h"
17 #include "clang/GR/PathSensitive/GRStateTrait.h"
18 #include "clang/GR/PathSensitive/GRTransferFuncs.h"
19 #include "clang/GR/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"
25 using namespace clang
;
28 namespace { class ConstraintRange
{}; }
29 static int ConstraintRangeIndex
= 0;
31 /// A Range represents the closed range [from, to]. The caller must
32 /// guarantee that from <= to. Note that Range is immutable, so as not
33 /// to subvert RangeSet's immutability.
35 class Range
: public std::pair
<const llvm::APSInt
*,
36 const llvm::APSInt
*> {
38 Range(const llvm::APSInt
&from
, const llvm::APSInt
&to
)
39 : std::pair
<const llvm::APSInt
*, const llvm::APSInt
*>(&from
, &to
) {
42 bool Includes(const llvm::APSInt
&v
) const {
43 return *first
<= v
&& v
<= *second
;
45 const llvm::APSInt
&From() const {
48 const llvm::APSInt
&To() const {
51 const llvm::APSInt
*getConcreteValue() const {
52 return &From() == &To() ? &From() : NULL
;
55 void Profile(llvm::FoldingSetNodeID
&ID
) const {
56 ID
.AddPointer(&From());
62 class RangeTrait
: public llvm::ImutContainerInfo
<Range
> {
64 // When comparing if one Range is less than another, we should compare
65 // the actual APSInt values instead of their pointers. This keeps the order
66 // consistent (instead of comparing by pointer values) and can potentially
67 // be used to speed up some of the operations in RangeSet.
68 static inline bool isLess(key_type_ref lhs
, key_type_ref rhs
) {
69 return *lhs
.first
< *rhs
.first
|| (!(*rhs
.first
< *lhs
.first
) &&
70 *lhs
.second
< *rhs
.second
);
74 /// RangeSet contains a set of ranges. If the set is empty, then
75 /// there the value of a symbol is overly constrained and there are no
76 /// possible values for that symbol.
78 typedef llvm::ImmutableSet
<Range
, RangeTrait
> PrimRangeSet
;
79 PrimRangeSet ranges
; // no need to make const, since it is an
80 // ImmutableSet - this allows default operator=
83 typedef PrimRangeSet::Factory Factory
;
84 typedef PrimRangeSet::iterator iterator
;
86 RangeSet(PrimRangeSet RS
) : ranges(RS
) {}
88 iterator
begin() const { return ranges
.begin(); }
89 iterator
end() const { return ranges
.end(); }
91 bool isEmpty() const { return ranges
.isEmpty(); }
93 /// Construct a new RangeSet representing '{ [from, to] }'.
94 RangeSet(Factory
&F
, const llvm::APSInt
&from
, const llvm::APSInt
&to
)
95 : ranges(F
.add(F
.getEmptySet(), Range(from
, to
))) {}
97 /// Profile - Generates a hash profile of this RangeSet for use
99 void Profile(llvm::FoldingSetNodeID
&ID
) const { ranges
.Profile(ID
); }
101 /// getConcreteValue - If a symbol is contrained to equal a specific integer
102 /// constant then this method returns that value. Otherwise, it returns
104 const llvm::APSInt
* getConcreteValue() const {
105 return ranges
.isSingleton() ? ranges
.begin()->getConcreteValue() : 0;
109 void IntersectInRange(BasicValueFactory
&BV
, Factory
&F
,
110 const llvm::APSInt
&Lower
,
111 const llvm::APSInt
&Upper
,
112 PrimRangeSet
&newRanges
,
113 PrimRangeSet::iterator
&i
,
114 PrimRangeSet::iterator
&e
) const {
115 // There are six cases for each range R in the set:
116 // 1. R is entirely before the intersection range.
117 // 2. R is entirely after the intersection range.
118 // 3. R contains the entire intersection range.
119 // 4. R starts before the intersection range and ends in the middle.
120 // 5. R starts in the middle of the intersection range and ends after it.
121 // 6. R is entirely contained in the intersection range.
122 // These correspond to each of the conditions below.
123 for (/* i = begin(), e = end() */; i
!= e
; ++i
) {
124 if (i
->To() < Lower
) {
127 if (i
->From() > Upper
) {
131 if (i
->Includes(Lower
)) {
132 if (i
->Includes(Upper
)) {
133 newRanges
= F
.add(newRanges
, Range(BV
.getValue(Lower
),
134 BV
.getValue(Upper
)));
137 newRanges
= F
.add(newRanges
, Range(BV
.getValue(Lower
), i
->To()));
139 if (i
->Includes(Upper
)) {
140 newRanges
= F
.add(newRanges
, Range(i
->From(), BV
.getValue(Upper
)));
143 newRanges
= F
.add(newRanges
, *i
);
149 // Returns a set containing the values in the receiving set, intersected with
150 // the closed range [Lower, Upper]. Unlike the Range type, this range uses
151 // modular arithmetic, corresponding to the common treatment of C integer
152 // overflow. Thus, if the Lower bound is greater than the Upper bound, the
153 // range is taken to wrap around. This is equivalent to taking the
154 // intersection with the two ranges [Min, Upper] and [Lower, Max],
155 // or, alternatively, /removing/ all integers between Upper and Lower.
156 RangeSet
Intersect(BasicValueFactory
&BV
, Factory
&F
,
157 const llvm::APSInt
&Lower
,
158 const llvm::APSInt
&Upper
) const {
159 PrimRangeSet newRanges
= F
.getEmptySet();
161 PrimRangeSet::iterator i
= begin(), e
= end();
163 IntersectInRange(BV
, F
, Lower
, Upper
, newRanges
, i
, e
);
165 // The order of the next two statements is important!
166 // IntersectInRange() does not reset the iteration state for i and e.
167 // Therefore, the lower range most be handled first.
168 IntersectInRange(BV
, F
, BV
.getMinValue(Upper
), Upper
, newRanges
, i
, e
);
169 IntersectInRange(BV
, F
, Lower
, BV
.getMaxValue(Lower
), newRanges
, i
, e
);
174 void print(llvm::raw_ostream
&os
) const {
177 for (iterator i
= begin(), e
= end(); i
!= e
; ++i
) {
183 os
<< '[' << i
->From().toString(10) << ", " << i
->To().toString(10)
189 bool operator==(const RangeSet
&other
) const {
190 return ranges
== other
.ranges
;
193 } // end anonymous namespace
195 typedef llvm::ImmutableMap
<SymbolRef
,RangeSet
> ConstraintRangeTy
;
200 struct GRStateTrait
<ConstraintRange
>
201 : public GRStatePartialTrait
<ConstraintRangeTy
> {
202 static inline void* GDMIndex() { return &ConstraintRangeIndex
; }
208 class RangeConstraintManager
: public SimpleConstraintManager
{
209 RangeSet
GetRange(const GRState
*state
, SymbolRef sym
);
211 RangeConstraintManager(GRSubEngine
&subengine
)
212 : SimpleConstraintManager(subengine
) {}
214 const GRState
*assumeSymNE(const GRState
* state
, SymbolRef sym
,
215 const llvm::APSInt
& Int
,
216 const llvm::APSInt
& Adjustment
);
218 const GRState
*assumeSymEQ(const GRState
* state
, SymbolRef sym
,
219 const llvm::APSInt
& Int
,
220 const llvm::APSInt
& Adjustment
);
222 const GRState
*assumeSymLT(const GRState
* state
, SymbolRef sym
,
223 const llvm::APSInt
& Int
,
224 const llvm::APSInt
& Adjustment
);
226 const GRState
*assumeSymGT(const GRState
* state
, SymbolRef sym
,
227 const llvm::APSInt
& Int
,
228 const llvm::APSInt
& Adjustment
);
230 const GRState
*assumeSymGE(const GRState
* state
, SymbolRef sym
,
231 const llvm::APSInt
& Int
,
232 const llvm::APSInt
& Adjustment
);
234 const GRState
*assumeSymLE(const GRState
* state
, SymbolRef sym
,
235 const llvm::APSInt
& Int
,
236 const llvm::APSInt
& Adjustment
);
238 const llvm::APSInt
* getSymVal(const GRState
* St
, SymbolRef sym
) const;
240 // FIXME: Refactor into SimpleConstraintManager?
241 bool isEqual(const GRState
* St
, SymbolRef sym
, const llvm::APSInt
& V
) const {
242 const llvm::APSInt
*i
= getSymVal(St
, sym
);
243 return i
? *i
== V
: false;
246 const GRState
* RemoveDeadBindings(const GRState
* St
, SymbolReaper
& SymReaper
);
248 void print(const GRState
* St
, llvm::raw_ostream
& Out
,
249 const char* nl
, const char *sep
);
255 } // end anonymous namespace
257 ConstraintManager
* GR::CreateRangeConstraintManager(GRStateManager
&,
258 GRSubEngine
&subeng
) {
259 return new RangeConstraintManager(subeng
);
262 const llvm::APSInt
* RangeConstraintManager::getSymVal(const GRState
* St
,
263 SymbolRef sym
) const {
264 const ConstraintRangeTy::data_type
*T
= St
->get
<ConstraintRange
>(sym
);
265 return T
? T
->getConcreteValue() : NULL
;
268 /// Scan all symbols referenced by the constraints. If the symbol is not alive
269 /// as marked in LSymbols, mark it as dead in DSymbols.
271 RangeConstraintManager::RemoveDeadBindings(const GRState
* state
,
272 SymbolReaper
& SymReaper
) {
274 ConstraintRangeTy CR
= state
->get
<ConstraintRange
>();
275 ConstraintRangeTy::Factory
& CRFactory
= state
->get_context
<ConstraintRange
>();
277 for (ConstraintRangeTy::iterator I
= CR
.begin(), E
= CR
.end(); I
!= E
; ++I
) {
278 SymbolRef sym
= I
.getKey();
279 if (SymReaper
.maybeDead(sym
))
280 CR
= CRFactory
.remove(CR
, sym
);
283 return state
->set
<ConstraintRange
>(CR
);
287 RangeConstraintManager::GetRange(const GRState
*state
, SymbolRef sym
) {
288 if (ConstraintRangeTy::data_type
* V
= state
->get
<ConstraintRange
>(sym
))
291 // Lazily generate a new RangeSet representing all possible values for the
292 // given symbol type.
293 QualType T
= state
->getSymbolManager().getType(sym
);
294 BasicValueFactory
& BV
= state
->getBasicVals();
295 return RangeSet(F
, BV
.getMinValue(T
), BV
.getMaxValue(T
));
298 //===------------------------------------------------------------------------===
299 // assumeSymX methods: public interface for RangeConstraintManager.
300 //===------------------------------------------------------------------------===/
302 // The syntax for ranges below is mathematical, using [x, y] for closed ranges
303 // and (x, y) for open ranges. These ranges are modular, corresponding with
304 // a common treatment of C integer overflow. This means that these methods
305 // do not have to worry about overflow; RangeSet::Intersect can handle such a
306 // "wraparound" range.
307 // As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1,
308 // UINT_MAX, 0, 1, and 2.
311 RangeConstraintManager::assumeSymNE(const GRState
* state
, SymbolRef sym
,
312 const llvm::APSInt
& Int
,
313 const llvm::APSInt
& Adjustment
) {
314 BasicValueFactory
&BV
= state
->getBasicVals();
316 llvm::APSInt Lower
= Int
-Adjustment
;
317 llvm::APSInt Upper
= Lower
;
321 // [Int-Adjustment+1, Int-Adjustment-1]
322 // Notice that the lower bound is greater than the upper bound.
323 RangeSet New
= GetRange(state
, sym
).Intersect(BV
, F
, Upper
, Lower
);
324 return New
.isEmpty() ? NULL
: state
->set
<ConstraintRange
>(sym
, New
);
328 RangeConstraintManager::assumeSymEQ(const GRState
* state
, SymbolRef sym
,
329 const llvm::APSInt
& Int
,
330 const llvm::APSInt
& Adjustment
) {
331 // [Int-Adjustment, Int-Adjustment]
332 BasicValueFactory
&BV
= state
->getBasicVals();
333 llvm::APSInt AdjInt
= Int
-Adjustment
;
334 RangeSet New
= GetRange(state
, sym
).Intersect(BV
, F
, AdjInt
, AdjInt
);
335 return New
.isEmpty() ? NULL
: state
->set
<ConstraintRange
>(sym
, New
);
339 RangeConstraintManager::assumeSymLT(const GRState
* state
, SymbolRef sym
,
340 const llvm::APSInt
& Int
,
341 const llvm::APSInt
& Adjustment
) {
342 BasicValueFactory
&BV
= state
->getBasicVals();
344 QualType T
= state
->getSymbolManager().getType(sym
);
345 const llvm::APSInt
&Min
= BV
.getMinValue(T
);
347 // Special case for Int == Min. This is always false.
351 llvm::APSInt Lower
= Min
-Adjustment
;
352 llvm::APSInt Upper
= Int
-Adjustment
;
355 RangeSet New
= GetRange(state
, sym
).Intersect(BV
, F
, Lower
, Upper
);
356 return New
.isEmpty() ? NULL
: state
->set
<ConstraintRange
>(sym
, New
);
360 RangeConstraintManager::assumeSymGT(const GRState
* state
, SymbolRef sym
,
361 const llvm::APSInt
& Int
,
362 const llvm::APSInt
& Adjustment
) {
363 BasicValueFactory
&BV
= state
->getBasicVals();
365 QualType T
= state
->getSymbolManager().getType(sym
);
366 const llvm::APSInt
&Max
= BV
.getMaxValue(T
);
368 // Special case for Int == Max. This is always false.
372 llvm::APSInt Lower
= Int
-Adjustment
;
373 llvm::APSInt Upper
= Max
-Adjustment
;
376 RangeSet New
= GetRange(state
, sym
).Intersect(BV
, F
, Lower
, Upper
);
377 return New
.isEmpty() ? NULL
: state
->set
<ConstraintRange
>(sym
, New
);
381 RangeConstraintManager::assumeSymGE(const GRState
* state
, SymbolRef sym
,
382 const llvm::APSInt
& Int
,
383 const llvm::APSInt
& Adjustment
) {
384 BasicValueFactory
&BV
= state
->getBasicVals();
386 QualType T
= state
->getSymbolManager().getType(sym
);
387 const llvm::APSInt
&Min
= BV
.getMinValue(T
);
389 // Special case for Int == Min. This is always feasible.
393 const llvm::APSInt
&Max
= BV
.getMaxValue(T
);
395 llvm::APSInt Lower
= Int
-Adjustment
;
396 llvm::APSInt Upper
= Max
-Adjustment
;
398 RangeSet New
= GetRange(state
, sym
).Intersect(BV
, F
, Lower
, Upper
);
399 return New
.isEmpty() ? NULL
: state
->set
<ConstraintRange
>(sym
, New
);
403 RangeConstraintManager::assumeSymLE(const GRState
* state
, SymbolRef sym
,
404 const llvm::APSInt
& Int
,
405 const llvm::APSInt
& Adjustment
) {
406 BasicValueFactory
&BV
= state
->getBasicVals();
408 QualType T
= state
->getSymbolManager().getType(sym
);
409 const llvm::APSInt
&Max
= BV
.getMaxValue(T
);
411 // Special case for Int == Max. This is always feasible.
415 const llvm::APSInt
&Min
= BV
.getMinValue(T
);
417 llvm::APSInt Lower
= Min
-Adjustment
;
418 llvm::APSInt Upper
= Int
-Adjustment
;
420 RangeSet New
= GetRange(state
, sym
).Intersect(BV
, F
, Lower
, Upper
);
421 return New
.isEmpty() ? NULL
: state
->set
<ConstraintRange
>(sym
, New
);
424 //===------------------------------------------------------------------------===
426 //===------------------------------------------------------------------------===/
428 void RangeConstraintManager::print(const GRState
* St
, llvm::raw_ostream
& Out
,
429 const char* nl
, const char *sep
) {
431 ConstraintRangeTy Ranges
= St
->get
<ConstraintRange
>();
433 if (Ranges
.isEmpty())
436 Out
<< nl
<< sep
<< "ranges of symbol values:";
438 for (ConstraintRangeTy::iterator I
=Ranges
.begin(), E
=Ranges
.end(); I
!=E
; ++I
){
439 Out
<< nl
<< ' ' << I
.getKey() << " : ";
440 I
.getData().print(Out
);