SValBuilder.cpp revision b71d1570417d81de7b064ad788bea690e2c89111
1// SValBuilder.cpp - Basic class for all SValBuilder implementations -*- 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 SValBuilder, the base class for all (complete) SValBuilder 11// implementations. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" 16#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 17#include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h" 18#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h" 19#include "clang/StaticAnalyzer/Core/PathSensitive/BasicValueFactory.h" 20 21using namespace clang; 22using namespace ento; 23 24//===----------------------------------------------------------------------===// 25// Basic SVal creation. 26//===----------------------------------------------------------------------===// 27 28void SValBuilder::anchor() { } 29 30DefinedOrUnknownSVal SValBuilder::makeZeroVal(QualType type) { 31 if (Loc::isLocType(type)) 32 return makeNull(); 33 34 if (type->isIntegerType()) 35 return makeIntVal(0, type); 36 37 // FIXME: Handle floats. 38 // FIXME: Handle structs. 39 return UnknownVal(); 40} 41 42NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, 43 const llvm::APSInt& rhs, QualType type) { 44 // The Environment ensures we always get a persistent APSInt in 45 // BasicValueFactory, so we don't need to get the APSInt from 46 // BasicValueFactory again. 47 assert(lhs); 48 assert(!Loc::isLocType(type)); 49 return nonloc::SymbolVal(SymMgr.getSymIntExpr(lhs, op, rhs, type)); 50} 51 52NonLoc SValBuilder::makeNonLoc(const llvm::APSInt& lhs, 53 BinaryOperator::Opcode op, const SymExpr *rhs, 54 QualType type) { 55 assert(rhs); 56 assert(!Loc::isLocType(type)); 57 return nonloc::SymbolVal(SymMgr.getIntSymExpr(lhs, op, rhs, type)); 58} 59 60NonLoc SValBuilder::makeNonLoc(const SymExpr *lhs, BinaryOperator::Opcode op, 61 const SymExpr *rhs, QualType type) { 62 assert(lhs && rhs); 63 assert(haveSameType(lhs->getType(Context), rhs->getType(Context)) == true); 64 assert(!Loc::isLocType(type)); 65 return nonloc::SymbolVal(SymMgr.getSymSymExpr(lhs, op, rhs, type)); 66} 67 68NonLoc SValBuilder::makeNonLoc(const SymExpr *operand, 69 QualType fromTy, QualType toTy) { 70 assert(operand); 71 assert(!Loc::isLocType(toTy)); 72 return nonloc::SymbolVal(SymMgr.getCastSymbol(operand, fromTy, toTy)); 73} 74 75SVal SValBuilder::convertToArrayIndex(SVal val) { 76 if (val.isUnknownOrUndef()) 77 return val; 78 79 // Common case: we have an appropriately sized integer. 80 if (nonloc::ConcreteInt* CI = dyn_cast<nonloc::ConcreteInt>(&val)) { 81 const llvm::APSInt& I = CI->getValue(); 82 if (I.getBitWidth() == ArrayIndexWidth && I.isSigned()) 83 return val; 84 } 85 86 return evalCastFromNonLoc(cast<NonLoc>(val), ArrayIndexTy); 87} 88 89DefinedOrUnknownSVal 90SValBuilder::getRegionValueSymbolVal(const TypedValueRegion* region) { 91 QualType T = region->getValueType(); 92 93 if (!SymbolManager::canSymbolicate(T)) 94 return UnknownVal(); 95 96 SymbolRef sym = SymMgr.getRegionValueSymbol(region); 97 98 if (Loc::isLocType(T)) 99 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 100 101 return nonloc::SymbolVal(sym); 102} 103 104DefinedOrUnknownSVal SValBuilder::getConjuredSymbolVal(const void *symbolTag, 105 const Expr *expr, 106 unsigned count) { 107 QualType T = expr->getType(); 108 return getConjuredSymbolVal(symbolTag, expr, T, count); 109} 110 111DefinedOrUnknownSVal SValBuilder::getConjuredSymbolVal(const void *symbolTag, 112 const Expr *expr, 113 QualType type, 114 unsigned count) { 115 if (!SymbolManager::canSymbolicate(type)) 116 return UnknownVal(); 117 118 SymbolRef sym = SymMgr.getConjuredSymbol(expr, type, count, symbolTag); 119 120 if (Loc::isLocType(type)) 121 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 122 123 return nonloc::SymbolVal(sym); 124} 125 126DefinedSVal SValBuilder::getMetadataSymbolVal(const void *symbolTag, 127 const MemRegion *region, 128 const Expr *expr, QualType type, 129 unsigned count) { 130 assert(SymbolManager::canSymbolicate(type) && "Invalid metadata symbol type"); 131 132 SymbolRef sym = 133 SymMgr.getMetadataSymbol(region, expr, type, count, symbolTag); 134 135 if (Loc::isLocType(type)) 136 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 137 138 return nonloc::SymbolVal(sym); 139} 140 141DefinedOrUnknownSVal 142SValBuilder::getDerivedRegionValueSymbolVal(SymbolRef parentSymbol, 143 const TypedValueRegion *region) { 144 QualType T = region->getValueType(); 145 146 if (!SymbolManager::canSymbolicate(T)) 147 return UnknownVal(); 148 149 SymbolRef sym = SymMgr.getDerivedSymbol(parentSymbol, region); 150 151 if (Loc::isLocType(T)) 152 return loc::MemRegionVal(MemMgr.getSymbolicRegion(sym)); 153 154 return nonloc::SymbolVal(sym); 155} 156 157DefinedSVal SValBuilder::getFunctionPointer(const FunctionDecl *func) { 158 return loc::MemRegionVal(MemMgr.getFunctionTextRegion(func)); 159} 160 161DefinedSVal SValBuilder::getBlockPointer(const BlockDecl *block, 162 CanQualType locTy, 163 const LocationContext *locContext) { 164 const BlockTextRegion *BC = 165 MemMgr.getBlockTextRegion(block, locTy, locContext->getAnalysisDeclContext()); 166 const BlockDataRegion *BD = MemMgr.getBlockDataRegion(BC, locContext); 167 return loc::MemRegionVal(BD); 168} 169 170//===----------------------------------------------------------------------===// 171 172SVal SValBuilder::makeGenericVal(const ProgramState *State, 173 BinaryOperator::Opcode Op, 174 NonLoc LHS, NonLoc RHS, 175 QualType ResultTy) { 176 // If operands are tainted, create a symbol to ensure that we propagate taint. 177 if (State->isTainted(RHS) || State->isTainted(LHS)) { 178 const SymExpr *symLHS; 179 const SymExpr *symRHS; 180 181 if (const nonloc::ConcreteInt *rInt = dyn_cast<nonloc::ConcreteInt>(&RHS)) { 182 symLHS = LHS.getAsSymExpr(); 183 return makeNonLoc(symLHS, Op, rInt->getValue(), ResultTy); 184 } 185 186 if (const nonloc::ConcreteInt *lInt = dyn_cast<nonloc::ConcreteInt>(&LHS)) { 187 symRHS = RHS.getAsSymExpr(); 188 return makeNonLoc(lInt->getValue(), Op, symRHS, ResultTy); 189 } 190 191 symLHS = LHS.getAsSymExpr(); 192 symRHS = RHS.getAsSymExpr(); 193 return makeNonLoc(symLHS, Op, symRHS, ResultTy); 194 } 195 return UnknownVal(); 196} 197 198 199SVal SValBuilder::evalBinOp(const ProgramState *state, BinaryOperator::Opcode op, 200 SVal lhs, SVal rhs, QualType type) { 201 202 if (lhs.isUndef() || rhs.isUndef()) 203 return UndefinedVal(); 204 205 if (lhs.isUnknown() || rhs.isUnknown()) 206 return UnknownVal(); 207 208 if (isa<Loc>(lhs)) { 209 if (isa<Loc>(rhs)) 210 return evalBinOpLL(state, op, cast<Loc>(lhs), cast<Loc>(rhs), type); 211 212 return evalBinOpLN(state, op, cast<Loc>(lhs), cast<NonLoc>(rhs), type); 213 } 214 215 if (isa<Loc>(rhs)) { 216 // Support pointer arithmetic where the addend is on the left 217 // and the pointer on the right. 218 assert(op == BO_Add); 219 220 // Commute the operands. 221 return evalBinOpLN(state, op, cast<Loc>(rhs), cast<NonLoc>(lhs), type); 222 } 223 224 return evalBinOpNN(state, op, cast<NonLoc>(lhs), cast<NonLoc>(rhs), type); 225} 226 227DefinedOrUnknownSVal SValBuilder::evalEQ(const ProgramState *state, 228 DefinedOrUnknownSVal lhs, 229 DefinedOrUnknownSVal rhs) { 230 return cast<DefinedOrUnknownSVal>(evalBinOp(state, BO_EQ, lhs, rhs, 231 Context.IntTy)); 232} 233 234/// Recursively check if the pointer types are equal modulo const, volatile, 235/// and restrict qualifiers. Assumes the input types are canonical. 236/// TODO: This is based off of code in SemaCast; can we reuse it. 237static bool haveSimilarTypes(ASTContext &Context, QualType T1, 238 QualType T2) { 239 while (Context.UnwrapSimilarPointerTypes(T1, T2)) { 240 Qualifiers Quals1, Quals2; 241 T1 = Context.getUnqualifiedArrayType(T1, Quals1); 242 T2 = Context.getUnqualifiedArrayType(T2, Quals2); 243 244 // Make sure that non cvr-qualifiers the other qualifiers (e.g., address 245 // spaces) are identical. 246 Quals1.removeCVRQualifiers(); 247 Quals2.removeCVRQualifiers(); 248 if (Quals1 != Quals2) 249 return false; 250 } 251 252 if (T1 != T2) 253 return false; 254 255 return true; 256} 257 258// FIXME: should rewrite according to the cast kind. 259SVal SValBuilder::evalCast(SVal val, QualType castTy, QualType originalTy) { 260 castTy = Context.getCanonicalType(castTy); 261 originalTy = Context.getCanonicalType(originalTy); 262 if (val.isUnknownOrUndef() || castTy == originalTy) 263 return val; 264 265 // For const casts, just propagate the value. 266 if (!castTy->isVariableArrayType() && !originalTy->isVariableArrayType()) 267 if (haveSimilarTypes(Context, Context.getPointerType(castTy), 268 Context.getPointerType(originalTy))) 269 return val; 270 271 // Check for casts from pointers to integers. 272 if (castTy->isIntegerType() && Loc::isLocType(originalTy)) 273 return evalCastFromLoc(cast<Loc>(val), castTy); 274 275 // Check for casts from integers to pointers. 276 if (Loc::isLocType(castTy) && originalTy->isIntegerType()) { 277 if (nonloc::LocAsInteger *LV = dyn_cast<nonloc::LocAsInteger>(&val)) { 278 if (const MemRegion *R = LV->getLoc().getAsRegion()) { 279 StoreManager &storeMgr = StateMgr.getStoreManager(); 280 R = storeMgr.castRegion(R, castTy); 281 return R ? SVal(loc::MemRegionVal(R)) : UnknownVal(); 282 } 283 return LV->getLoc(); 284 } 285 return dispatchCast(val, castTy); 286 } 287 288 // Just pass through function and block pointers. 289 if (originalTy->isBlockPointerType() || originalTy->isFunctionPointerType()) { 290 assert(Loc::isLocType(castTy)); 291 return val; 292 } 293 294 // Check for casts from array type to another type. 295 if (originalTy->isArrayType()) { 296 // We will always decay to a pointer. 297 val = StateMgr.ArrayToPointer(cast<Loc>(val)); 298 299 // Are we casting from an array to a pointer? If so just pass on 300 // the decayed value. 301 if (castTy->isPointerType()) 302 return val; 303 304 // Are we casting from an array to an integer? If so, cast the decayed 305 // pointer value to an integer. 306 assert(castTy->isIntegerType()); 307 308 // FIXME: Keep these here for now in case we decide soon that we 309 // need the original decayed type. 310 // QualType elemTy = cast<ArrayType>(originalTy)->getElementType(); 311 // QualType pointerTy = C.getPointerType(elemTy); 312 return evalCastFromLoc(cast<Loc>(val), castTy); 313 } 314 315 // Check for casts from a region to a specific type. 316 if (const MemRegion *R = val.getAsRegion()) { 317 // FIXME: We should handle the case where we strip off view layers to get 318 // to a desugared type. 319 320 if (!Loc::isLocType(castTy)) { 321 // FIXME: There can be gross cases where one casts the result of a function 322 // (that returns a pointer) to some other value that happens to fit 323 // within that pointer value. We currently have no good way to 324 // model such operations. When this happens, the underlying operation 325 // is that the caller is reasoning about bits. Conceptually we are 326 // layering a "view" of a location on top of those bits. Perhaps 327 // we need to be more lazy about mutual possible views, even on an 328 // SVal? This may be necessary for bit-level reasoning as well. 329 return UnknownVal(); 330 } 331 332 // We get a symbolic function pointer for a dereference of a function 333 // pointer, but it is of function type. Example: 334 335 // struct FPRec { 336 // void (*my_func)(int * x); 337 // }; 338 // 339 // int bar(int x); 340 // 341 // int f1_a(struct FPRec* foo) { 342 // int x; 343 // (*foo->my_func)(&x); 344 // return bar(x)+1; // no-warning 345 // } 346 347 assert(Loc::isLocType(originalTy) || originalTy->isFunctionType() || 348 originalTy->isBlockPointerType() || castTy->isReferenceType()); 349 350 StoreManager &storeMgr = StateMgr.getStoreManager(); 351 352 // Delegate to store manager to get the result of casting a region to a 353 // different type. If the MemRegion* returned is NULL, this expression 354 // Evaluates to UnknownVal. 355 R = storeMgr.castRegion(R, castTy); 356 return R ? SVal(loc::MemRegionVal(R)) : UnknownVal(); 357 } 358 359 return dispatchCast(val, castTy); 360} 361