SVals.h revision a5e81f1240bcc5b9b0721fc6275075ad7cadaf5e
1b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdoch//== SVals.h - Abstract Values for Static Analysis ---------*- C++ -*--==// 281362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen// 381362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen// The LLVM Compiler Infrastructure 481362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen// 581362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen// This file is distributed under the University of Illinois Open Source 681362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen// License. See LICENSE.TXT for details. 781362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen// 881362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen//===----------------------------------------------------------------------===// 981362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen// 1081362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen// This file defines SVal, Loc, and NonLoc, classes that represent 1181362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen// abstract r-values for use with path-sensitive value tracking. 1281362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen// 1381362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen//===----------------------------------------------------------------------===// 1481362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen 1581362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen#ifndef LLVM_CLANG_ANALYSIS_RVALUE_H 1681362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen#define LLVM_CLANG_ANALYSIS_RVALUE_H 1781362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen 1881362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen#include "clang/Analysis/PathSensitive/SymbolManager.h" 1981362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen#include "llvm/Support/Casting.h" 2081362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen#include "llvm/ADT/ImmutableList.h" 2181362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen 2281362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsennamespace llvm { 2381362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen class raw_ostream; 2481362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen} 2581362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen 2681362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen//==------------------------------------------------------------------------==// 2781362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen// Base SVal types. 288b112d2025046f85ef7f6be087c6129c872ebad2Ben Murdoch//==------------------------------------------------------------------------==// 2981362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsen 308b112d2025046f85ef7f6be087c6129c872ebad2Ben Murdochnamespace clang { 318b112d2025046f85ef7f6be087c6129c872ebad2Ben Murdoch 328b112d2025046f85ef7f6be087c6129c872ebad2Ben Murdochclass CompoundValData; 338b112d2025046f85ef7f6be087c6129c872ebad2Ben Murdochclass LazyCompoundValData; 3481362e16c30e9e970af6b17592f627ad8cdee4d8Kristian Monsenclass GRState; 358b112d2025046f85ef7f6be087c6129c872ebad2Ben Murdochclass BasicValueFactory; 36b0fe1620dcb4135ac3ab2d66ff93072373911299Ben Murdochclass MemRegion; 37class TypedRegion; 38class MemRegionManager; 39class GRStateManager; 40class ValueManager; 41 42class SVal { 43public: 44 enum BaseKind { UndefinedKind, UnknownKind, LocKind, NonLocKind }; 45 enum { BaseBits = 2, BaseMask = 0x3 }; 46 47protected: 48 void* Data; 49 unsigned Kind; 50 51protected: 52 SVal(const void* d, bool isLoc, unsigned ValKind) 53 : Data(const_cast<void*>(d)), 54 Kind((isLoc ? LocKind : NonLocKind) | (ValKind << BaseBits)) {} 55 56 explicit SVal(BaseKind k, void* D = NULL) 57 : Data(D), Kind(k) {} 58 59public: 60 SVal() : Data(0), Kind(0) {} 61 ~SVal() {}; 62 63 /// BufferTy - A temporary buffer to hold a set of SVals. 64 typedef llvm::SmallVector<SVal,5> BufferTy; 65 66 inline unsigned getRawKind() const { return Kind; } 67 inline BaseKind getBaseKind() const { return (BaseKind) (Kind & BaseMask); } 68 inline unsigned getSubKind() const { return (Kind & ~BaseMask) >> BaseBits; } 69 70 inline void Profile(llvm::FoldingSetNodeID& ID) const { 71 ID.AddInteger((unsigned) getRawKind()); 72 ID.AddPointer(reinterpret_cast<void*>(Data)); 73 } 74 75 inline bool operator==(const SVal& R) const { 76 return getRawKind() == R.getRawKind() && Data == R.Data; 77 } 78 79 inline bool operator!=(const SVal& R) const { 80 return !(*this == R); 81 } 82 83 inline bool isUnknown() const { 84 return getRawKind() == UnknownKind; 85 } 86 87 inline bool isUndef() const { 88 return getRawKind() == UndefinedKind; 89 } 90 91 inline bool isUnknownOrUndef() const { 92 return getRawKind() <= UnknownKind; 93 } 94 95 inline bool isValid() const { 96 return getRawKind() > UnknownKind; 97 } 98 99 bool isZeroConstant() const; 100 101 /// hasConjuredSymbol - If this SVal wraps a conjured symbol, return true; 102 bool hasConjuredSymbol() const; 103 104 /// getAsFunctionDecl - If this SVal is a MemRegionVal and wraps a 105 /// CodeTextRegion wrapping a FunctionDecl, return that FunctionDecl. 106 /// Otherwise return 0. 107 const FunctionDecl* getAsFunctionDecl() const; 108 109 /// getAsLocSymbol - If this SVal is a location (subclasses Loc) and 110 /// wraps a symbol, return that SymbolRef. Otherwise return a SymbolData* 111 SymbolRef getAsLocSymbol() const; 112 113 /// getAsSymbol - If this Sval wraps a symbol return that SymbolRef. 114 /// Otherwise return a SymbolRef where 'isValid()' returns false. 115 SymbolRef getAsSymbol() const; 116 117 /// getAsSymbolicExpression - If this Sval wraps a symbolic expression then 118 /// return that expression. Otherwise return NULL. 119 const SymExpr *getAsSymbolicExpression() const; 120 121 const MemRegion *getAsRegion() const; 122 123 void dumpToStream(llvm::raw_ostream& OS) const; 124 void dump() const; 125 126 // Iterators. 127 class symbol_iterator { 128 llvm::SmallVector<const SymExpr*, 5> itr; 129 void expand(); 130 public: 131 symbol_iterator() {} 132 symbol_iterator(const SymExpr* SE); 133 134 symbol_iterator& operator++(); 135 SymbolRef operator*(); 136 137 bool operator==(const symbol_iterator& X) const; 138 bool operator!=(const symbol_iterator& X) const; 139 }; 140 141 symbol_iterator symbol_begin() const { 142 const SymExpr *SE = getAsSymbolicExpression(); 143 if (SE) 144 return symbol_iterator(SE); 145 else 146 return symbol_iterator(); 147 } 148 149 symbol_iterator symbol_end() const { return symbol_iterator(); } 150 151 // Implement isa<T> support. 152 static inline bool classof(const SVal*) { return true; } 153}; 154 155class UnknownVal : public SVal { 156public: 157 UnknownVal() : SVal(UnknownKind) {} 158 159 static inline bool classof(const SVal* V) { 160 return V->getBaseKind() == UnknownKind; 161 } 162}; 163 164class UndefinedVal : public SVal { 165public: 166 UndefinedVal() : SVal(UndefinedKind) {} 167 UndefinedVal(void* D) : SVal(UndefinedKind, D) {} 168 169 static inline bool classof(const SVal* V) { 170 return V->getBaseKind() == UndefinedKind; 171 } 172 173 void* getData() const { return Data; } 174}; 175 176class NonLoc : public SVal { 177protected: 178 NonLoc(unsigned SubKind, const void* d) : SVal(d, false, SubKind) {} 179 180public: 181 void dumpToStream(llvm::raw_ostream& Out) const; 182 183 // Implement isa<T> support. 184 static inline bool classof(const SVal* V) { 185 return V->getBaseKind() == NonLocKind; 186 } 187}; 188 189class Loc : public SVal { 190protected: 191 Loc(unsigned SubKind, const void* D) 192 : SVal(const_cast<void*>(D), true, SubKind) {} 193 194public: 195 void dumpToStream(llvm::raw_ostream& Out) const; 196 197 Loc(const Loc& X) : SVal(X.Data, true, X.getSubKind()) {} 198 Loc& operator=(const Loc& X) { memcpy(this, &X, sizeof(Loc)); return *this; } 199 200 // Implement isa<T> support. 201 static inline bool classof(const SVal* V) { 202 return V->getBaseKind() == LocKind; 203 } 204 205 static inline bool IsLocType(QualType T) { 206 return T->isAnyPointerType() || T->isBlockPointerType(); 207 } 208}; 209 210//==------------------------------------------------------------------------==// 211// Subclasses of NonLoc. 212//==------------------------------------------------------------------------==// 213 214namespace nonloc { 215 216enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind, 217 LocAsIntegerKind, CompoundValKind, LazyCompoundValKind }; 218 219class SymbolVal : public NonLoc { 220public: 221 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {} 222 223 SymbolRef getSymbol() const { 224 return (const SymbolData*) Data; 225 } 226 227 static inline bool classof(const SVal* V) { 228 return V->getBaseKind() == NonLocKind && 229 V->getSubKind() == SymbolValKind; 230 } 231 232 static inline bool classof(const NonLoc* V) { 233 return V->getSubKind() == SymbolValKind; 234 } 235}; 236 237class SymExprVal : public NonLoc { 238public: 239 SymExprVal(const SymExpr *SE) 240 : NonLoc(SymExprValKind, reinterpret_cast<const void*>(SE)) {} 241 242 const SymExpr *getSymbolicExpression() const { 243 return reinterpret_cast<SymExpr*>(Data); 244 } 245 246 static inline bool classof(const SVal* V) { 247 return V->getBaseKind() == NonLocKind && 248 V->getSubKind() == SymExprValKind; 249 } 250 251 static inline bool classof(const NonLoc* V) { 252 return V->getSubKind() == SymExprValKind; 253 } 254}; 255 256class ConcreteInt : public NonLoc { 257public: 258 ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} 259 260 const llvm::APSInt& getValue() const { 261 return *static_cast<llvm::APSInt*>(Data); 262 } 263 264 // Transfer functions for binary/unary operations on ConcreteInts. 265 SVal evalBinOp(ValueManager &ValMgr, BinaryOperator::Opcode Op, 266 const ConcreteInt& R) const; 267 268 ConcreteInt evalComplement(ValueManager &ValMgr) const; 269 270 ConcreteInt evalMinus(ValueManager &ValMgr) const; 271 272 // Implement isa<T> support. 273 static inline bool classof(const SVal* V) { 274 return V->getBaseKind() == NonLocKind && 275 V->getSubKind() == ConcreteIntKind; 276 } 277 278 static inline bool classof(const NonLoc* V) { 279 return V->getSubKind() == ConcreteIntKind; 280 } 281}; 282 283class LocAsInteger : public NonLoc { 284 friend class clang::ValueManager; 285 286 LocAsInteger(const std::pair<SVal, uintptr_t>& data) : 287 NonLoc(LocAsIntegerKind, &data) { 288 assert (isa<Loc>(data.first)); 289 } 290 291public: 292 293 Loc getLoc() const { 294 return cast<Loc>(((std::pair<SVal, uintptr_t>*) Data)->first); 295 } 296 297 const Loc& getPersistentLoc() const { 298 const SVal& V = ((std::pair<SVal, uintptr_t>*) Data)->first; 299 return cast<Loc>(V); 300 } 301 302 unsigned getNumBits() const { 303 return ((std::pair<SVal, unsigned>*) Data)->second; 304 } 305 306 // Implement isa<T> support. 307 static inline bool classof(const SVal* V) { 308 return V->getBaseKind() == NonLocKind && 309 V->getSubKind() == LocAsIntegerKind; 310 } 311 312 static inline bool classof(const NonLoc* V) { 313 return V->getSubKind() == LocAsIntegerKind; 314 } 315}; 316 317class CompoundVal : public NonLoc { 318 friend class clang::ValueManager; 319 320 CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} 321 322public: 323 const CompoundValData* getValue() const { 324 return static_cast<CompoundValData*>(Data); 325 } 326 327 typedef llvm::ImmutableList<SVal>::iterator iterator; 328 iterator begin() const; 329 iterator end() const; 330 331 static bool classof(const SVal* V) { 332 return V->getBaseKind() == NonLocKind && V->getSubKind() == CompoundValKind; 333 } 334 335 static bool classof(const NonLoc* V) { 336 return V->getSubKind() == CompoundValKind; 337 } 338}; 339 340class LazyCompoundVal : public NonLoc { 341 friend class clang::ValueManager; 342 343 LazyCompoundVal(const LazyCompoundValData *D) 344 : NonLoc(LazyCompoundValKind, D) {} 345public: 346 const GRState *getState() const; 347 const TypedRegion *getRegion() const; 348 349 static bool classof(const SVal *V) { 350 return V->getBaseKind() == NonLocKind && 351 V->getSubKind() == LazyCompoundValKind; 352 } 353 static bool classof(const NonLoc *V) { 354 return V->getSubKind() == LazyCompoundValKind; 355 } 356}; 357 358} // end namespace clang::nonloc 359 360//==------------------------------------------------------------------------==// 361// Subclasses of Loc. 362//==------------------------------------------------------------------------==// 363 364namespace loc { 365 366enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind }; 367 368class GotoLabel : public Loc { 369public: 370 GotoLabel(LabelStmt* Label) : Loc(GotoLabelKind, Label) {} 371 372 LabelStmt* getLabel() const { 373 return static_cast<LabelStmt*>(Data); 374 } 375 376 static inline bool classof(const SVal* V) { 377 return V->getBaseKind() == LocKind && 378 V->getSubKind() == GotoLabelKind; 379 } 380 381 static inline bool classof(const Loc* V) { 382 return V->getSubKind() == GotoLabelKind; 383 } 384}; 385 386 387class MemRegionVal : public Loc { 388public: 389 MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {} 390 391 const MemRegion* getRegion() const { 392 return static_cast<MemRegion*>(Data); 393 } 394 395 const MemRegion* getBaseRegion() const; 396 397 template <typename REGION> 398 const REGION* getRegionAs() const { 399 return llvm::dyn_cast<REGION>(getRegion()); 400 } 401 402 inline bool operator==(const MemRegionVal& R) const { 403 return getRegion() == R.getRegion(); 404 } 405 406 inline bool operator!=(const MemRegionVal& R) const { 407 return getRegion() != R.getRegion(); 408 } 409 410 // Implement isa<T> support. 411 static inline bool classof(const SVal* V) { 412 return V->getBaseKind() == LocKind && 413 V->getSubKind() == MemRegionKind; 414 } 415 416 static inline bool classof(const Loc* V) { 417 return V->getSubKind() == MemRegionKind; 418 } 419}; 420 421class ConcreteInt : public Loc { 422public: 423 ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {} 424 425 const llvm::APSInt& getValue() const { 426 return *static_cast<llvm::APSInt*>(Data); 427 } 428 429 // Transfer functions for binary/unary operations on ConcreteInts. 430 SVal EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, 431 const ConcreteInt& R) const; 432 433 // Implement isa<T> support. 434 static inline bool classof(const SVal* V) { 435 return V->getBaseKind() == LocKind && 436 V->getSubKind() == ConcreteIntKind; 437 } 438 439 static inline bool classof(const Loc* V) { 440 return V->getSubKind() == ConcreteIntKind; 441 } 442}; 443 444} // end clang::loc namespace 445} // end clang namespace 446 447namespace llvm { 448static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os, 449 clang::SVal V) { 450 V.dumpToStream(os); 451 return os; 452} 453} // end llvm namespace 454#endif 455