Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 1 | // SimpleSValuator.cpp - A basic SValuator ------------------------*- 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 SimpleSValuator, a basic implementation of SValuator. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #include "clang/Analysis/PathSensitive/SValuator.h" |
| 15 | #include "clang/Analysis/PathSensitive/GRState.h" |
| 16 | #include "llvm/Support/Compiler.h" |
| 17 | |
| 18 | using namespace clang; |
| 19 | |
| 20 | namespace { |
| 21 | class VISIBILITY_HIDDEN SimpleSValuator : public SValuator { |
| 22 | public: |
| 23 | SimpleSValuator(ValueManager &valMgr) : SValuator(valMgr) {} |
| 24 | virtual ~SimpleSValuator() {} |
| 25 | |
| 26 | virtual SVal EvalCast(NonLoc val, QualType castTy); |
| 27 | virtual SVal EvalCast(Loc val, QualType castTy); |
| 28 | virtual SVal EvalMinus(NonLoc val); |
| 29 | virtual SVal EvalComplement(NonLoc val); |
| 30 | virtual SVal EvalBinOpNN(BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, |
| 31 | QualType resultTy); |
| 32 | virtual SVal EvalBinOpLL(BinaryOperator::Opcode op, Loc lhs, Loc rhs, |
| 33 | QualType resultTy); |
| 34 | virtual SVal EvalBinOpLN(const GRState *state, BinaryOperator::Opcode op, |
| 35 | Loc lhs, NonLoc rhs, QualType resultTy); |
| 36 | }; |
| 37 | } // end anonymous namespace |
| 38 | |
| 39 | SValuator *clang::CreateSimpleSValuator(ValueManager &valMgr) { |
| 40 | return new SimpleSValuator(valMgr); |
| 41 | } |
| 42 | |
| 43 | //===----------------------------------------------------------------------===// |
| 44 | // Transfer function for Casts. |
| 45 | //===----------------------------------------------------------------------===// |
| 46 | |
| 47 | SVal SimpleSValuator::EvalCast(NonLoc val, QualType castTy) { |
| 48 | if (!isa<nonloc::ConcreteInt>(val)) |
| 49 | return UnknownVal(); |
| 50 | |
| 51 | bool isLocType = Loc::IsLocType(castTy); |
| 52 | |
| 53 | // Only handle casts from integers to integers. |
| 54 | if (!isLocType && !castTy->isIntegerType()) |
| 55 | return UnknownVal(); |
| 56 | |
| 57 | llvm::APSInt i = cast<nonloc::ConcreteInt>(val).getValue(); |
| 58 | i.setIsUnsigned(castTy->isUnsignedIntegerType() || Loc::IsLocType(castTy)); |
| 59 | i.extOrTrunc(ValMgr.getContext().getTypeSize(castTy)); |
| 60 | |
| 61 | if (isLocType) |
| 62 | return ValMgr.makeIntLocVal(i); |
| 63 | else |
| 64 | return ValMgr.makeIntVal(i); |
| 65 | } |
| 66 | |
| 67 | SVal SimpleSValuator::EvalCast(Loc val, QualType castTy) { |
| 68 | |
| 69 | // Casts from pointers -> pointers, just return the lval. |
| 70 | // |
| 71 | // Casts from pointers -> references, just return the lval. These |
| 72 | // can be introduced by the frontend for corner cases, e.g |
| 73 | // casting from va_list* to __builtin_va_list&. |
| 74 | // |
| 75 | assert(!val.isUnknownOrUndef()); |
| 76 | |
| 77 | if (Loc::IsLocType(castTy) || castTy->isReferenceType()) |
| 78 | return val; |
| 79 | |
| 80 | // FIXME: Handle transparent unions where a value can be "transparently" |
| 81 | // lifted into a union type. |
| 82 | if (castTy->isUnionType()) |
| 83 | return UnknownVal(); |
| 84 | |
| 85 | assert(castTy->isIntegerType()); |
| 86 | unsigned BitWidth = ValMgr.getContext().getTypeSize(castTy); |
| 87 | |
| 88 | if (!isa<loc::ConcreteInt>(val)) |
| 89 | return ValMgr.makeLocAsInteger(val, BitWidth); |
| 90 | |
| 91 | llvm::APSInt i = cast<loc::ConcreteInt>(val).getValue(); |
| 92 | i.setIsUnsigned(castTy->isUnsignedIntegerType() || Loc::IsLocType(castTy)); |
| 93 | i.extOrTrunc(BitWidth); |
| 94 | return ValMgr.makeIntVal(i); |
| 95 | } |
| 96 | |
| 97 | //===----------------------------------------------------------------------===// |
| 98 | // Transfer function for unary operators. |
| 99 | //===----------------------------------------------------------------------===// |
| 100 | |
| 101 | SVal SimpleSValuator::EvalMinus(NonLoc val) { |
| 102 | switch (val.getSubKind()) { |
| 103 | case nonloc::ConcreteIntKind: |
| 104 | return cast<nonloc::ConcreteInt>(val).evalMinus(ValMgr); |
| 105 | default: |
| 106 | return UnknownVal(); |
| 107 | } |
| 108 | } |
| 109 | |
| 110 | SVal SimpleSValuator::EvalComplement(NonLoc X) { |
| 111 | switch (X.getSubKind()) { |
| 112 | case nonloc::ConcreteIntKind: |
| 113 | return cast<nonloc::ConcreteInt>(X).evalComplement(ValMgr); |
| 114 | default: |
| 115 | return UnknownVal(); |
| 116 | } |
| 117 | } |
| 118 | |
| 119 | //===----------------------------------------------------------------------===// |
| 120 | // Transfer function for binary operators. |
| 121 | //===----------------------------------------------------------------------===// |
| 122 | |
| 123 | static BinaryOperator::Opcode NegateComparison(BinaryOperator::Opcode op) { |
| 124 | switch (op) { |
| 125 | default: |
| 126 | assert(false && "Invalid opcode."); |
| 127 | case BinaryOperator::LT: return BinaryOperator::GE; |
| 128 | case BinaryOperator::GT: return BinaryOperator::LE; |
| 129 | case BinaryOperator::LE: return BinaryOperator::GT; |
| 130 | case BinaryOperator::GE: return BinaryOperator::LT; |
| 131 | case BinaryOperator::EQ: return BinaryOperator::NE; |
| 132 | case BinaryOperator::NE: return BinaryOperator::EQ; |
| 133 | } |
| 134 | } |
| 135 | |
| 136 | // Equality operators for Locs. |
| 137 | // FIXME: All this logic will be revamped when we have MemRegion::getLocation() |
| 138 | // implemented. |
| 139 | |
| 140 | static SVal EvalEquality(ValueManager &ValMgr, Loc lhs, Loc rhs, bool isEqual, |
| 141 | QualType resultTy) { |
| 142 | |
| 143 | switch (lhs.getSubKind()) { |
| 144 | default: |
| 145 | assert(false && "EQ/NE not implemented for this Loc."); |
| 146 | return UnknownVal(); |
| 147 | |
| 148 | case loc::ConcreteIntKind: { |
| 149 | if (SymbolRef rSym = rhs.getAsSymbol()) |
| 150 | return ValMgr.makeNonLoc(rSym, |
| 151 | isEqual ? BinaryOperator::EQ |
| 152 | : BinaryOperator::NE, |
| 153 | cast<loc::ConcreteInt>(lhs).getValue(), |
| 154 | resultTy); |
| 155 | break; |
| 156 | } |
| 157 | case loc::MemRegionKind: { |
| 158 | if (SymbolRef lSym = lhs.getAsLocSymbol()) { |
| 159 | if (isa<loc::ConcreteInt>(rhs)) { |
| 160 | return ValMgr.makeNonLoc(lSym, |
| 161 | isEqual ? BinaryOperator::EQ |
| 162 | : BinaryOperator::NE, |
| 163 | cast<loc::ConcreteInt>(rhs).getValue(), |
| 164 | resultTy); |
| 165 | } |
| 166 | } |
| 167 | break; |
| 168 | } |
| 169 | |
| 170 | case loc::GotoLabelKind: |
| 171 | break; |
| 172 | } |
| 173 | |
| 174 | return ValMgr.makeTruthVal(isEqual ? lhs == rhs : lhs != rhs, resultTy); |
| 175 | } |
| 176 | |
| 177 | SVal SimpleSValuator::EvalBinOpNN(BinaryOperator::Opcode op, |
| 178 | NonLoc lhs, NonLoc rhs, |
Ted Kremenek | 54ca9b1 | 2009-07-13 21:55:12 +0000 | [diff] [blame] | 179 | QualType resultTy) { |
| 180 | |
| 181 | assert(!lhs.isUnknownOrUndef()); |
| 182 | assert(!rhs.isUnknownOrUndef()); |
| 183 | |
| 184 | // Handle trivial case where left-side and right-side are the same. |
| 185 | if (lhs == rhs) |
| 186 | switch (op) { |
| 187 | default: |
| 188 | break; |
| 189 | case BinaryOperator::EQ: |
| 190 | case BinaryOperator::LE: |
| 191 | case BinaryOperator::GE: |
| 192 | return ValMgr.makeTruthVal(true, resultTy); |
| 193 | case BinaryOperator::LT: |
| 194 | case BinaryOperator::GT: |
| 195 | case BinaryOperator::NE: |
| 196 | return ValMgr.makeTruthVal(false, resultTy); |
| 197 | } |
| 198 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 199 | while (1) { |
| 200 | switch (lhs.getSubKind()) { |
| 201 | default: |
| 202 | return UnknownVal(); |
| 203 | case nonloc::LocAsIntegerKind: { |
| 204 | Loc lhsL = cast<nonloc::LocAsInteger>(lhs).getLoc(); |
| 205 | switch (rhs.getSubKind()) { |
| 206 | case nonloc::LocAsIntegerKind: |
| 207 | return EvalBinOpLL(op, lhsL, cast<nonloc::LocAsInteger>(rhs).getLoc(), |
| 208 | resultTy); |
| 209 | case nonloc::ConcreteIntKind: { |
| 210 | // Transform the integer into a location and compare. |
| 211 | ASTContext& Ctx = ValMgr.getContext(); |
| 212 | llvm::APSInt i = cast<nonloc::ConcreteInt>(rhs).getValue(); |
| 213 | i.setIsUnsigned(true); |
| 214 | i.extOrTrunc(Ctx.getTypeSize(Ctx.VoidPtrTy)); |
| 215 | return EvalBinOpLL(op, lhsL, ValMgr.makeLoc(i), resultTy); |
| 216 | } |
| 217 | default: |
| 218 | switch (op) { |
| 219 | case BinaryOperator::EQ: |
| 220 | return ValMgr.makeTruthVal(false, resultTy); |
| 221 | case BinaryOperator::NE: |
| 222 | return ValMgr.makeTruthVal(true, resultTy); |
| 223 | default: |
| 224 | // This case also handles pointer arithmetic. |
| 225 | return UnknownVal(); |
| 226 | } |
| 227 | } |
| 228 | } |
| 229 | case nonloc::SymExprValKind: { |
| 230 | // Logical not? |
| 231 | if (!(op == BinaryOperator::EQ && rhs.isZeroConstant())) |
| 232 | return UnknownVal(); |
| 233 | |
| 234 | const SymExpr *symExpr = |
| 235 | cast<nonloc::SymExprVal>(lhs).getSymbolicExpression(); |
| 236 | |
| 237 | // Only handle ($sym op constant) for now. |
| 238 | if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(symExpr)) { |
| 239 | BinaryOperator::Opcode opc = symIntExpr->getOpcode(); |
| 240 | switch (opc) { |
| 241 | case BinaryOperator::LAnd: |
| 242 | case BinaryOperator::LOr: |
| 243 | assert(false && "Logical operators handled by branching logic."); |
| 244 | return UnknownVal(); |
| 245 | case BinaryOperator::Assign: |
| 246 | case BinaryOperator::MulAssign: |
| 247 | case BinaryOperator::DivAssign: |
| 248 | case BinaryOperator::RemAssign: |
| 249 | case BinaryOperator::AddAssign: |
| 250 | case BinaryOperator::SubAssign: |
| 251 | case BinaryOperator::ShlAssign: |
| 252 | case BinaryOperator::ShrAssign: |
| 253 | case BinaryOperator::AndAssign: |
| 254 | case BinaryOperator::XorAssign: |
| 255 | case BinaryOperator::OrAssign: |
| 256 | case BinaryOperator::Comma: |
| 257 | assert(false && "'=' and ',' operators handled by GRExprEngine."); |
| 258 | return UnknownVal(); |
| 259 | case BinaryOperator::PtrMemD: |
| 260 | case BinaryOperator::PtrMemI: |
| 261 | assert(false && "Pointer arithmetic not handled here."); |
| 262 | return UnknownVal(); |
| 263 | case BinaryOperator::Mul: |
| 264 | case BinaryOperator::Div: |
| 265 | case BinaryOperator::Rem: |
| 266 | case BinaryOperator::Add: |
| 267 | case BinaryOperator::Sub: |
| 268 | case BinaryOperator::Shl: |
| 269 | case BinaryOperator::Shr: |
| 270 | case BinaryOperator::And: |
| 271 | case BinaryOperator::Xor: |
| 272 | case BinaryOperator::Or: |
| 273 | // Not handled yet. |
| 274 | return UnknownVal(); |
| 275 | case BinaryOperator::LT: |
| 276 | case BinaryOperator::GT: |
| 277 | case BinaryOperator::LE: |
| 278 | case BinaryOperator::GE: |
| 279 | case BinaryOperator::EQ: |
| 280 | case BinaryOperator::NE: |
| 281 | opc = NegateComparison(opc); |
| 282 | assert(symIntExpr->getType(ValMgr.getContext()) == resultTy); |
| 283 | return ValMgr.makeNonLoc(symIntExpr->getLHS(), opc, |
| 284 | symIntExpr->getRHS(), resultTy); |
| 285 | } |
| 286 | } |
| 287 | } |
| 288 | case nonloc::ConcreteIntKind: { |
| 289 | if (isa<nonloc::ConcreteInt>(rhs)) { |
| 290 | const nonloc::ConcreteInt& lhsInt = cast<nonloc::ConcreteInt>(lhs); |
| 291 | return lhsInt.evalBinOp(ValMgr, op, cast<nonloc::ConcreteInt>(rhs)); |
| 292 | } |
| 293 | else { |
| 294 | // Swap the left and right sides and flip the operator if doing so |
| 295 | // allows us to better reason about the expression (this is a form |
| 296 | // of expression canonicalization). |
| 297 | NonLoc tmp = rhs; |
| 298 | rhs = lhs; |
| 299 | lhs = tmp; |
| 300 | |
| 301 | switch (op) { |
| 302 | case BinaryOperator::LT: op = BinaryOperator::GT; continue; |
| 303 | case BinaryOperator::GT: op = BinaryOperator::LT; continue; |
| 304 | case BinaryOperator::LE: op = BinaryOperator::GE; continue; |
| 305 | case BinaryOperator::GE: op = BinaryOperator::LE; continue; |
| 306 | case BinaryOperator::EQ: |
| 307 | case BinaryOperator::NE: |
| 308 | case BinaryOperator::Add: |
| 309 | case BinaryOperator::Mul: |
| 310 | continue; |
| 311 | default: |
| 312 | return UnknownVal(); |
| 313 | } |
| 314 | } |
| 315 | } |
| 316 | case nonloc::SymbolValKind: { |
| 317 | if (isa<nonloc::ConcreteInt>(rhs)) { |
| 318 | return ValMgr.makeNonLoc(cast<nonloc::SymbolVal>(lhs).getSymbol(), op, |
| 319 | cast<nonloc::ConcreteInt>(rhs).getValue(), |
| 320 | resultTy); |
| 321 | } |
| 322 | |
| 323 | return UnknownVal(); |
| 324 | } |
| 325 | } |
| 326 | } |
| 327 | } |
| 328 | |
| 329 | SVal SimpleSValuator::EvalBinOpLL(BinaryOperator::Opcode op, Loc lhs, Loc rhs, |
| 330 | QualType resultTy) { |
| 331 | switch (op) { |
| 332 | default: |
| 333 | return UnknownVal(); |
| 334 | case BinaryOperator::EQ: |
| 335 | case BinaryOperator::NE: |
| 336 | return EvalEquality(ValMgr, lhs, rhs, op == BinaryOperator::EQ, resultTy); |
| 337 | } |
| 338 | } |
| 339 | |
| 340 | SVal SimpleSValuator::EvalBinOpLN(const GRState *state, |
| 341 | BinaryOperator::Opcode op, |
| 342 | Loc lhs, NonLoc rhs, QualType resultTy) { |
| 343 | // Special case: 'rhs' is an integer that has the same width as a pointer and |
| 344 | // we are using the integer location in a comparison. Normally this cannot be |
| 345 | // triggered, but transfer functions like those for OSCommpareAndSwapBarrier32 |
| 346 | // can generate comparisons that trigger this code. |
| 347 | // FIXME: Are all locations guaranteed to have pointer width? |
| 348 | if (BinaryOperator::isEqualityOp(op)) { |
| 349 | if (nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs)) { |
| 350 | const llvm::APSInt *x = &rhsInt->getValue(); |
| 351 | ASTContext &ctx = ValMgr.getContext(); |
| 352 | if (ctx.getTypeSize(ctx.VoidPtrTy) == x->getBitWidth()) { |
| 353 | // Convert the signedness of the integer (if necessary). |
| 354 | if (x->isSigned()) |
| 355 | x = &ValMgr.getBasicValueFactory().getValue(*x, true); |
| 356 | |
| 357 | return EvalBinOpLL(op, lhs, loc::ConcreteInt(*x), resultTy); |
| 358 | } |
| 359 | } |
| 360 | } |
| 361 | |
| 362 | // Delegate pointer arithmetic to the StoreManager. |
| 363 | return state->getStateManager().getStoreManager().EvalBinOp(state, op, lhs, |
| 364 | rhs, resultTy); |
| 365 | } |