SVals.h revision 08780078183ae4b2534c69a3e0ded596cdb695ba
13345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick//== SVals.h - Abstract Values for Static Analysis ---------*- C++ -*--==// 2c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// 3c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// The LLVM Compiler Infrastructure 4c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// 5c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// This file is distributed under the University of Illinois Open Source 6c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// License. See LICENSE.TXT for details. 73345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick// 8c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch//===----------------------------------------------------------------------===// 9c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// 10c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// This file defines SVal, Loc, and NonLoc, classes that represent 11c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// abstract r-values for use with path-sensitive value tracking. 12c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// 13c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch//===----------------------------------------------------------------------===// 14c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 15c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#ifndef LLVM_CLANG_ANALYSIS_RVALUE_H 16c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#define LLVM_CLANG_ANALYSIS_RVALUE_H 17c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 18c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch#include "clang/Analysis/PathSensitive/SymbolManager.h" 193345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick#include "llvm/Support/Casting.h" 203345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick#include "llvm/ADT/ImmutableList.h" 213345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrick 22c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochnamespace llvm { 23c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch class raw_ostream; 24c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch} 25c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 26c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch//==------------------------------------------------------------------------==// 27c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch// Base SVal types. 28c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch//==------------------------------------------------------------------------==// 29c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 30c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochnamespace clang { 31c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 32c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass CompoundValData; 333345a6884c488ff3a535c2c9acdd33d74b37e311Iain Merrickclass LazyCompoundValData; 34c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass GRState; 35c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass BasicValueFactory; 36c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass MemRegion; 37c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass TypedRegion; 38c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass MemRegionManager; 39c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass GRStateManager; 40c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass ValueManager; 41c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 42c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochclass SVal { 43c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochpublic: 44c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch enum BaseKind { UndefinedKind, UnknownKind, LocKind, NonLocKind }; 45c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch enum { BaseBits = 2, BaseMask = 0x3 }; 46c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdoch 47c407dc5cd9bdc5668497f21b26b09d988ab439deBen Murdochprotected: 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 DefinedSVal : public SVal { 177protected: 178 DefinedSVal(const void* d, bool isLoc, unsigned ValKind) 179 : SVal(d, isLoc, ValKind) {} 180public: 181 // Implement isa<T> support. 182 static inline bool classof(const SVal *V) { 183 return !V->isUnknownOrUndef(); 184 } 185}; 186 187class NonLoc : public DefinedSVal { 188protected: 189 NonLoc(unsigned SubKind, const void* d) : DefinedSVal(d, false, SubKind) {} 190 191public: 192 void dumpToStream(llvm::raw_ostream& Out) const; 193 194 // Implement isa<T> support. 195 static inline bool classof(const SVal* V) { 196 return V->getBaseKind() == NonLocKind; 197 } 198}; 199 200class Loc : public DefinedSVal { 201protected: 202 Loc(unsigned SubKind, const void* D) 203 : DefinedSVal(const_cast<void*>(D), true, SubKind) {} 204 205public: 206 void dumpToStream(llvm::raw_ostream& Out) const; 207 208 Loc(const Loc& X) : DefinedSVal(X.Data, true, X.getSubKind()) {} 209 Loc& operator=(const Loc& X) { memcpy(this, &X, sizeof(Loc)); return *this; } 210 211 // Implement isa<T> support. 212 static inline bool classof(const SVal* V) { 213 return V->getBaseKind() == LocKind; 214 } 215 216 static inline bool IsLocType(QualType T) { 217 return T->isAnyPointerType() || T->isBlockPointerType(); 218 } 219}; 220 221//==------------------------------------------------------------------------==// 222// Subclasses of NonLoc. 223//==------------------------------------------------------------------------==// 224 225namespace nonloc { 226 227enum Kind { ConcreteIntKind, SymbolValKind, SymExprValKind, 228 LocAsIntegerKind, CompoundValKind, LazyCompoundValKind }; 229 230class SymbolVal : public NonLoc { 231public: 232 SymbolVal(SymbolRef sym) : NonLoc(SymbolValKind, sym) {} 233 234 SymbolRef getSymbol() const { 235 return (const SymbolData*) Data; 236 } 237 238 static inline bool classof(const SVal* V) { 239 return V->getBaseKind() == NonLocKind && 240 V->getSubKind() == SymbolValKind; 241 } 242 243 static inline bool classof(const NonLoc* V) { 244 return V->getSubKind() == SymbolValKind; 245 } 246}; 247 248class SymExprVal : public NonLoc { 249public: 250 SymExprVal(const SymExpr *SE) 251 : NonLoc(SymExprValKind, reinterpret_cast<const void*>(SE)) {} 252 253 const SymExpr *getSymbolicExpression() const { 254 return reinterpret_cast<SymExpr*>(Data); 255 } 256 257 static inline bool classof(const SVal* V) { 258 return V->getBaseKind() == NonLocKind && 259 V->getSubKind() == SymExprValKind; 260 } 261 262 static inline bool classof(const NonLoc* V) { 263 return V->getSubKind() == SymExprValKind; 264 } 265}; 266 267class ConcreteInt : public NonLoc { 268public: 269 ConcreteInt(const llvm::APSInt& V) : NonLoc(ConcreteIntKind, &V) {} 270 271 const llvm::APSInt& getValue() const { 272 return *static_cast<llvm::APSInt*>(Data); 273 } 274 275 // Transfer functions for binary/unary operations on ConcreteInts. 276 SVal evalBinOp(ValueManager &ValMgr, BinaryOperator::Opcode Op, 277 const ConcreteInt& R) const; 278 279 ConcreteInt evalComplement(ValueManager &ValMgr) const; 280 281 ConcreteInt evalMinus(ValueManager &ValMgr) const; 282 283 // Implement isa<T> support. 284 static inline bool classof(const SVal* V) { 285 return V->getBaseKind() == NonLocKind && 286 V->getSubKind() == ConcreteIntKind; 287 } 288 289 static inline bool classof(const NonLoc* V) { 290 return V->getSubKind() == ConcreteIntKind; 291 } 292}; 293 294class LocAsInteger : public NonLoc { 295 friend class clang::ValueManager; 296 297 LocAsInteger(const std::pair<SVal, uintptr_t>& data) : 298 NonLoc(LocAsIntegerKind, &data) { 299 assert (isa<Loc>(data.first)); 300 } 301 302public: 303 304 Loc getLoc() const { 305 return cast<Loc>(((std::pair<SVal, uintptr_t>*) Data)->first); 306 } 307 308 const Loc& getPersistentLoc() const { 309 const SVal& V = ((std::pair<SVal, uintptr_t>*) Data)->first; 310 return cast<Loc>(V); 311 } 312 313 unsigned getNumBits() const { 314 return ((std::pair<SVal, unsigned>*) Data)->second; 315 } 316 317 // Implement isa<T> support. 318 static inline bool classof(const SVal* V) { 319 return V->getBaseKind() == NonLocKind && 320 V->getSubKind() == LocAsIntegerKind; 321 } 322 323 static inline bool classof(const NonLoc* V) { 324 return V->getSubKind() == LocAsIntegerKind; 325 } 326}; 327 328class CompoundVal : public NonLoc { 329 friend class clang::ValueManager; 330 331 CompoundVal(const CompoundValData* D) : NonLoc(CompoundValKind, D) {} 332 333public: 334 const CompoundValData* getValue() const { 335 return static_cast<CompoundValData*>(Data); 336 } 337 338 typedef llvm::ImmutableList<SVal>::iterator iterator; 339 iterator begin() const; 340 iterator end() const; 341 342 static bool classof(const SVal* V) { 343 return V->getBaseKind() == NonLocKind && V->getSubKind() == CompoundValKind; 344 } 345 346 static bool classof(const NonLoc* V) { 347 return V->getSubKind() == CompoundValKind; 348 } 349}; 350 351class LazyCompoundVal : public NonLoc { 352 friend class clang::ValueManager; 353 354 LazyCompoundVal(const LazyCompoundValData *D) 355 : NonLoc(LazyCompoundValKind, D) {} 356public: 357 const LazyCompoundValData *getCVData() const { 358 return static_cast<const LazyCompoundValData*>(Data); 359 } 360 const GRState *getState() const; 361 const TypedRegion *getRegion() const; 362 363 static bool classof(const SVal *V) { 364 return V->getBaseKind() == NonLocKind && 365 V->getSubKind() == LazyCompoundValKind; 366 } 367 static bool classof(const NonLoc *V) { 368 return V->getSubKind() == LazyCompoundValKind; 369 } 370}; 371 372} // end namespace clang::nonloc 373 374//==------------------------------------------------------------------------==// 375// Subclasses of Loc. 376//==------------------------------------------------------------------------==// 377 378namespace loc { 379 380enum Kind { GotoLabelKind, MemRegionKind, ConcreteIntKind }; 381 382class GotoLabel : public Loc { 383public: 384 GotoLabel(LabelStmt* Label) : Loc(GotoLabelKind, Label) {} 385 386 LabelStmt* getLabel() const { 387 return static_cast<LabelStmt*>(Data); 388 } 389 390 static inline bool classof(const SVal* V) { 391 return V->getBaseKind() == LocKind && 392 V->getSubKind() == GotoLabelKind; 393 } 394 395 static inline bool classof(const Loc* V) { 396 return V->getSubKind() == GotoLabelKind; 397 } 398}; 399 400 401class MemRegionVal : public Loc { 402public: 403 MemRegionVal(const MemRegion* r) : Loc(MemRegionKind, r) {} 404 405 const MemRegion* getRegion() const { 406 return static_cast<MemRegion*>(Data); 407 } 408 409 const MemRegion* getBaseRegion() const; 410 411 template <typename REGION> 412 const REGION* getRegionAs() const { 413 return llvm::dyn_cast<REGION>(getRegion()); 414 } 415 416 inline bool operator==(const MemRegionVal& R) const { 417 return getRegion() == R.getRegion(); 418 } 419 420 inline bool operator!=(const MemRegionVal& R) const { 421 return getRegion() != R.getRegion(); 422 } 423 424 // Implement isa<T> support. 425 static inline bool classof(const SVal* V) { 426 return V->getBaseKind() == LocKind && 427 V->getSubKind() == MemRegionKind; 428 } 429 430 static inline bool classof(const Loc* V) { 431 return V->getSubKind() == MemRegionKind; 432 } 433}; 434 435class ConcreteInt : public Loc { 436public: 437 ConcreteInt(const llvm::APSInt& V) : Loc(ConcreteIntKind, &V) {} 438 439 const llvm::APSInt& getValue() const { 440 return *static_cast<llvm::APSInt*>(Data); 441 } 442 443 // Transfer functions for binary/unary operations on ConcreteInts. 444 SVal EvalBinOp(BasicValueFactory& BasicVals, BinaryOperator::Opcode Op, 445 const ConcreteInt& R) const; 446 447 // Implement isa<T> support. 448 static inline bool classof(const SVal* V) { 449 return V->getBaseKind() == LocKind && 450 V->getSubKind() == ConcreteIntKind; 451 } 452 453 static inline bool classof(const Loc* V) { 454 return V->getSubKind() == ConcreteIntKind; 455 } 456}; 457 458} // end clang::loc namespace 459} // end clang namespace 460 461namespace llvm { 462static inline llvm::raw_ostream& operator<<(llvm::raw_ostream& os, 463 clang::SVal V) { 464 V.dumpToStream(os); 465 return os; 466} 467} // end llvm namespace 468#endif 469