RangeConstraintManager.cpp revision 218887
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/StaticAnalyzer/Core/PathSensitive/GRState.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/GRStateTrait.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/TransferFuncs.h" 19#include "llvm/Support/Debug.h" 20#include "llvm/ADT/FoldingSet.h" 21#include "llvm/ADT/ImmutableSet.h" 22#include "llvm/Support/raw_ostream.h" 23 24using namespace clang; 25using namespace ento; 26 27namespace { class ConstraintRange {}; } 28static 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. 33namespace { 34class Range : public std::pair<const llvm::APSInt*, 35 const llvm::APSInt*> { 36public: 37 Range(const llvm::APSInt &from, const llvm::APSInt &to) 38 : std::pair<const llvm::APSInt*, const llvm::APSInt*>(&from, &to) { 39 assert(from <= to); 40 } 41 bool Includes(const llvm::APSInt &v) const { 42 return *first <= v && v <= *second; 43 } 44 const llvm::APSInt &From() const { 45 return *first; 46 } 47 const llvm::APSInt &To() const { 48 return *second; 49 } 50 const llvm::APSInt *getConcreteValue() const { 51 return &From() == &To() ? &From() : NULL; 52 } 53 54 void Profile(llvm::FoldingSetNodeID &ID) const { 55 ID.AddPointer(&From()); 56 ID.AddPointer(&To()); 57 } 58}; 59 60 61class RangeTrait : public llvm::ImutContainerInfo<Range> { 62public: 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 static inline bool isLess(key_type_ref lhs, key_type_ref rhs) { 68 return *lhs.first < *rhs.first || (!(*rhs.first < *lhs.first) && 69 *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. 76class 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. 81public: 82 typedef PrimRangeSet::Factory Factory; 83 typedef PrimRangeSet::iterator iterator; 84 85 RangeSet(PrimRangeSet RS) : ranges(RS) {} 86 87 iterator begin() const { return ranges.begin(); } 88 iterator end() const { return ranges.end(); } 89 90 bool isEmpty() const { return ranges.isEmpty(); } 91 92 /// Construct a new RangeSet representing '{ [from, to] }'. 93 RangeSet(Factory &F, const llvm::APSInt &from, const llvm::APSInt &to) 94 : ranges(F.add(F.getEmptySet(), Range(from, to))) {} 95 96 /// Profile - Generates a hash profile of this RangeSet for use 97 /// by FoldingSet. 98 void Profile(llvm::FoldingSetNodeID &ID) const { ranges.Profile(ID); } 99 100 /// getConcreteValue - If a symbol is contrained to equal a specific integer 101 /// constant then this method returns that value. Otherwise, it returns 102 /// NULL. 103 const llvm::APSInt* getConcreteValue() const { 104 return ranges.isSingleton() ? ranges.begin()->getConcreteValue() : 0; 105 } 106 107private: 108 void IntersectInRange(BasicValueFactory &BV, Factory &F, 109 const llvm::APSInt &Lower, 110 const llvm::APSInt &Upper, 111 PrimRangeSet &newRanges, 112 PrimRangeSet::iterator &i, 113 PrimRangeSet::iterator &e) const { 114 // There are six cases for each range R in the set: 115 // 1. R is entirely before the intersection range. 116 // 2. R is entirely after the intersection range. 117 // 3. R contains the entire intersection range. 118 // 4. R starts before the intersection range and ends in the middle. 119 // 5. R starts in the middle of the intersection range and ends after it. 120 // 6. R is entirely contained in the intersection range. 121 // These correspond to each of the conditions below. 122 for (/* i = begin(), e = end() */; i != e; ++i) { 123 if (i->To() < Lower) { 124 continue; 125 } 126 if (i->From() > Upper) { 127 break; 128 } 129 130 if (i->Includes(Lower)) { 131 if (i->Includes(Upper)) { 132 newRanges = F.add(newRanges, Range(BV.getValue(Lower), 133 BV.getValue(Upper))); 134 break; 135 } else 136 newRanges = F.add(newRanges, Range(BV.getValue(Lower), i->To())); 137 } else { 138 if (i->Includes(Upper)) { 139 newRanges = F.add(newRanges, Range(i->From(), BV.getValue(Upper))); 140 break; 141 } else 142 newRanges = F.add(newRanges, *i); 143 } 144 } 145 } 146 147public: 148 // Returns a set containing the values in the receiving set, intersected with 149 // the closed range [Lower, Upper]. Unlike the Range type, this range uses 150 // modular arithmetic, corresponding to the common treatment of C integer 151 // overflow. Thus, if the Lower bound is greater than the Upper bound, the 152 // range is taken to wrap around. This is equivalent to taking the 153 // intersection with the two ranges [Min, Upper] and [Lower, Max], 154 // or, alternatively, /removing/ all integers between Upper and Lower. 155 RangeSet Intersect(BasicValueFactory &BV, Factory &F, 156 const llvm::APSInt &Lower, 157 const llvm::APSInt &Upper) const { 158 PrimRangeSet newRanges = F.getEmptySet(); 159 160 PrimRangeSet::iterator i = begin(), e = end(); 161 if (Lower <= Upper) 162 IntersectInRange(BV, F, Lower, Upper, newRanges, i, e); 163 else { 164 // The order of the next two statements is important! 165 // IntersectInRange() does not reset the iteration state for i and e. 166 // Therefore, the lower range most be handled first. 167 IntersectInRange(BV, F, BV.getMinValue(Upper), Upper, newRanges, i, e); 168 IntersectInRange(BV, F, Lower, BV.getMaxValue(Lower), newRanges, i, e); 169 } 170 return newRanges; 171 } 172 173 void print(llvm::raw_ostream &os) const { 174 bool isFirst = true; 175 os << "{ "; 176 for (iterator i = begin(), e = end(); i != e; ++i) { 177 if (isFirst) 178 isFirst = false; 179 else 180 os << ", "; 181 182 os << '[' << i->From().toString(10) << ", " << i->To().toString(10) 183 << ']'; 184 } 185 os << " }"; 186 } 187 188 bool operator==(const RangeSet &other) const { 189 return ranges == other.ranges; 190 } 191}; 192} // end anonymous namespace 193 194typedef llvm::ImmutableMap<SymbolRef,RangeSet> ConstraintRangeTy; 195 196namespace clang { 197namespace ento { 198template<> 199struct GRStateTrait<ConstraintRange> 200 : public GRStatePartialTrait<ConstraintRangeTy> { 201 static inline void* GDMIndex() { return &ConstraintRangeIndex; } 202}; 203} 204} 205 206namespace { 207class RangeConstraintManager : public SimpleConstraintManager{ 208 RangeSet GetRange(const GRState *state, SymbolRef sym); 209public: 210 RangeConstraintManager(SubEngine &subengine) 211 : SimpleConstraintManager(subengine) {} 212 213 const GRState *assumeSymNE(const GRState* state, SymbolRef sym, 214 const llvm::APSInt& Int, 215 const llvm::APSInt& Adjustment); 216 217 const GRState *assumeSymEQ(const GRState* state, SymbolRef sym, 218 const llvm::APSInt& Int, 219 const llvm::APSInt& Adjustment); 220 221 const GRState *assumeSymLT(const GRState* state, SymbolRef sym, 222 const llvm::APSInt& Int, 223 const llvm::APSInt& Adjustment); 224 225 const GRState *assumeSymGT(const GRState* state, SymbolRef sym, 226 const llvm::APSInt& Int, 227 const llvm::APSInt& Adjustment); 228 229 const GRState *assumeSymGE(const GRState* state, SymbolRef sym, 230 const llvm::APSInt& Int, 231 const llvm::APSInt& Adjustment); 232 233 const GRState *assumeSymLE(const GRState* state, SymbolRef sym, 234 const llvm::APSInt& Int, 235 const llvm::APSInt& Adjustment); 236 237 const llvm::APSInt* getSymVal(const GRState* St, SymbolRef sym) const; 238 239 // FIXME: Refactor into SimpleConstraintManager? 240 bool isEqual(const GRState* St, SymbolRef sym, const llvm::APSInt& V) const { 241 const llvm::APSInt *i = getSymVal(St, sym); 242 return i ? *i == V : false; 243 } 244 245 const GRState* removeDeadBindings(const GRState* St, SymbolReaper& SymReaper); 246 247 void print(const GRState* St, llvm::raw_ostream& Out, 248 const char* nl, const char *sep); 249 250private: 251 RangeSet::Factory F; 252}; 253 254} // end anonymous namespace 255 256ConstraintManager* ento::CreateRangeConstraintManager(GRStateManager&, 257 SubEngine &subeng) { 258 return new RangeConstraintManager(subeng); 259} 260 261const llvm::APSInt* RangeConstraintManager::getSymVal(const GRState* St, 262 SymbolRef sym) const { 263 const ConstraintRangeTy::data_type *T = St->get<ConstraintRange>(sym); 264 return T ? T->getConcreteValue() : NULL; 265} 266 267/// Scan all symbols referenced by the constraints. If the symbol is not alive 268/// as marked in LSymbols, mark it as dead in DSymbols. 269const GRState* 270RangeConstraintManager::removeDeadBindings(const GRState* state, 271 SymbolReaper& SymReaper) { 272 273 ConstraintRangeTy CR = state->get<ConstraintRange>(); 274 ConstraintRangeTy::Factory& CRFactory = state->get_context<ConstraintRange>(); 275 276 for (ConstraintRangeTy::iterator I = CR.begin(), E = CR.end(); I != E; ++I) { 277 SymbolRef sym = I.getKey(); 278 if (SymReaper.maybeDead(sym)) 279 CR = CRFactory.remove(CR, sym); 280 } 281 282 return state->set<ConstraintRange>(CR); 283} 284 285RangeSet 286RangeConstraintManager::GetRange(const GRState *state, SymbolRef sym) { 287 if (ConstraintRangeTy::data_type* V = state->get<ConstraintRange>(sym)) 288 return *V; 289 290 // Lazily generate a new RangeSet representing all possible values for the 291 // given symbol type. 292 QualType T = state->getSymbolManager().getType(sym); 293 BasicValueFactory& BV = state->getBasicVals(); 294 return RangeSet(F, BV.getMinValue(T), BV.getMaxValue(T)); 295} 296 297//===------------------------------------------------------------------------=== 298// assumeSymX methods: public interface for RangeConstraintManager. 299//===------------------------------------------------------------------------===/ 300 301// The syntax for ranges below is mathematical, using [x, y] for closed ranges 302// and (x, y) for open ranges. These ranges are modular, corresponding with 303// a common treatment of C integer overflow. This means that these methods 304// do not have to worry about overflow; RangeSet::Intersect can handle such a 305// "wraparound" range. 306// As an example, the range [UINT_MAX-1, 3) contains five values: UINT_MAX-1, 307// UINT_MAX, 0, 1, and 2. 308 309const GRState* 310RangeConstraintManager::assumeSymNE(const GRState* state, SymbolRef sym, 311 const llvm::APSInt& Int, 312 const llvm::APSInt& Adjustment) { 313 BasicValueFactory &BV = state->getBasicVals(); 314 315 llvm::APSInt Lower = Int-Adjustment; 316 llvm::APSInt Upper = Lower; 317 --Lower; 318 ++Upper; 319 320 // [Int-Adjustment+1, Int-Adjustment-1] 321 // Notice that the lower bound is greater than the upper bound. 322 RangeSet New = GetRange(state, sym).Intersect(BV, F, Upper, Lower); 323 return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); 324} 325 326const GRState* 327RangeConstraintManager::assumeSymEQ(const GRState* state, SymbolRef sym, 328 const llvm::APSInt& Int, 329 const llvm::APSInt& Adjustment) { 330 // [Int-Adjustment, Int-Adjustment] 331 BasicValueFactory &BV = state->getBasicVals(); 332 llvm::APSInt AdjInt = Int-Adjustment; 333 RangeSet New = GetRange(state, sym).Intersect(BV, F, AdjInt, AdjInt); 334 return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); 335} 336 337const GRState* 338RangeConstraintManager::assumeSymLT(const GRState* state, SymbolRef sym, 339 const llvm::APSInt& Int, 340 const llvm::APSInt& Adjustment) { 341 BasicValueFactory &BV = state->getBasicVals(); 342 343 QualType T = state->getSymbolManager().getType(sym); 344 const llvm::APSInt &Min = BV.getMinValue(T); 345 346 // Special case for Int == Min. This is always false. 347 if (Int == Min) 348 return NULL; 349 350 llvm::APSInt Lower = Min-Adjustment; 351 llvm::APSInt Upper = Int-Adjustment; 352 --Upper; 353 354 RangeSet New = GetRange(state, sym).Intersect(BV, F, Lower, Upper); 355 return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); 356} 357 358const GRState* 359RangeConstraintManager::assumeSymGT(const GRState* state, SymbolRef sym, 360 const llvm::APSInt& Int, 361 const llvm::APSInt& Adjustment) { 362 BasicValueFactory &BV = state->getBasicVals(); 363 364 QualType T = state->getSymbolManager().getType(sym); 365 const llvm::APSInt &Max = BV.getMaxValue(T); 366 367 // Special case for Int == Max. This is always false. 368 if (Int == Max) 369 return NULL; 370 371 llvm::APSInt Lower = Int-Adjustment; 372 llvm::APSInt Upper = Max-Adjustment; 373 ++Lower; 374 375 RangeSet New = GetRange(state, sym).Intersect(BV, F, Lower, Upper); 376 return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); 377} 378 379const GRState* 380RangeConstraintManager::assumeSymGE(const GRState* state, SymbolRef sym, 381 const llvm::APSInt& Int, 382 const llvm::APSInt& Adjustment) { 383 BasicValueFactory &BV = state->getBasicVals(); 384 385 QualType T = state->getSymbolManager().getType(sym); 386 const llvm::APSInt &Min = BV.getMinValue(T); 387 388 // Special case for Int == Min. This is always feasible. 389 if (Int == Min) 390 return state; 391 392 const llvm::APSInt &Max = BV.getMaxValue(T); 393 394 llvm::APSInt Lower = Int-Adjustment; 395 llvm::APSInt Upper = Max-Adjustment; 396 397 RangeSet New = GetRange(state, sym).Intersect(BV, F, Lower, Upper); 398 return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); 399} 400 401const GRState* 402RangeConstraintManager::assumeSymLE(const GRState* state, SymbolRef sym, 403 const llvm::APSInt& Int, 404 const llvm::APSInt& Adjustment) { 405 BasicValueFactory &BV = state->getBasicVals(); 406 407 QualType T = state->getSymbolManager().getType(sym); 408 const llvm::APSInt &Max = BV.getMaxValue(T); 409 410 // Special case for Int == Max. This is always feasible. 411 if (Int == Max) 412 return state; 413 414 const llvm::APSInt &Min = BV.getMinValue(T); 415 416 llvm::APSInt Lower = Min-Adjustment; 417 llvm::APSInt Upper = Int-Adjustment; 418 419 RangeSet New = GetRange(state, sym).Intersect(BV, F, Lower, Upper); 420 return New.isEmpty() ? NULL : state->set<ConstraintRange>(sym, New); 421} 422 423//===------------------------------------------------------------------------=== 424// Pretty-printing. 425//===------------------------------------------------------------------------===/ 426 427void RangeConstraintManager::print(const GRState* St, llvm::raw_ostream& Out, 428 const char* nl, const char *sep) { 429 430 ConstraintRangeTy Ranges = St->get<ConstraintRange>(); 431 432 if (Ranges.isEmpty()) 433 return; 434 435 Out << nl << sep << "ranges of symbol values:"; 436 437 for (ConstraintRangeTy::iterator I=Ranges.begin(), E=Ranges.end(); I!=E; ++I){ 438 Out << nl << ' ' << I.getKey() << " : "; 439 I.getData().print(Out); 440 } 441} 442