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