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 | |
Ted Kremenek | 1309f9a | 2010-01-25 04:41:41 +0000 | [diff] [blame] | 14 | #include "clang/Checker/PathSensitive/SValuator.h" |
| 15 | #include "clang/Checker/PathSensitive/GRState.h" |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 16 | |
| 17 | using namespace clang; |
| 18 | |
| 19 | namespace { |
Kovarththanan Rajaratnam | ba5fb5a | 2009-11-28 06:07:30 +0000 | [diff] [blame] | 20 | class SimpleSValuator : public SValuator { |
Ted Kremenek | 32c3fa4 | 2009-07-21 21:03:30 +0000 | [diff] [blame] | 21 | protected: |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 22 | virtual SVal EvalCastNL(NonLoc val, QualType castTy); |
| 23 | virtual SVal EvalCastL(Loc val, QualType castTy); |
Ted Kremenek | 32c3fa4 | 2009-07-21 21:03:30 +0000 | [diff] [blame] | 24 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 25 | public: |
| 26 | SimpleSValuator(ValueManager &valMgr) : SValuator(valMgr) {} |
| 27 | virtual ~SimpleSValuator() {} |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 28 | |
| 29 | virtual SVal EvalMinus(NonLoc val); |
| 30 | virtual SVal EvalComplement(NonLoc val); |
Ted Kremenek | cd8f6ac | 2009-10-06 01:39:48 +0000 | [diff] [blame] | 31 | virtual SVal EvalBinOpNN(const GRState *state, BinaryOperator::Opcode op, |
| 32 | NonLoc lhs, NonLoc rhs, QualType resultTy); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 33 | virtual SVal EvalBinOpLL(BinaryOperator::Opcode op, Loc lhs, Loc rhs, |
| 34 | QualType resultTy); |
| 35 | virtual SVal EvalBinOpLN(const GRState *state, BinaryOperator::Opcode op, |
| 36 | Loc lhs, NonLoc rhs, QualType resultTy); |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 37 | |
| 38 | SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op, |
| 39 | const llvm::APSInt &RHS, QualType resultTy); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 40 | }; |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 41 | } // end anonymous namespace |
| 42 | |
| 43 | SValuator *clang::CreateSimpleSValuator(ValueManager &valMgr) { |
| 44 | return new SimpleSValuator(valMgr); |
| 45 | } |
| 46 | |
| 47 | //===----------------------------------------------------------------------===// |
| 48 | // Transfer function for Casts. |
| 49 | //===----------------------------------------------------------------------===// |
| 50 | |
Ted Kremenek | dd66114 | 2009-07-20 21:39:27 +0000 | [diff] [blame] | 51 | SVal SimpleSValuator::EvalCastNL(NonLoc val, QualType castTy) { |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 52 | |
Ted Kremenek | dd66114 | 2009-07-20 21:39:27 +0000 | [diff] [blame] | 53 | bool isLocType = Loc::IsLocType(castTy); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 54 | |
Ted Kremenek | 9031dd7 | 2009-07-21 00:12:07 +0000 | [diff] [blame] | 55 | if (nonloc::LocAsInteger *LI = dyn_cast<nonloc::LocAsInteger>(&val)) { |
| 56 | if (isLocType) |
Ted Kremenek | dd66114 | 2009-07-20 21:39:27 +0000 | [diff] [blame] | 57 | return LI->getLoc(); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 58 | |
Ted Kremenek | c50e6df | 2010-01-11 02:33:26 +0000 | [diff] [blame] | 59 | // FIXME: Correctly support promotions/truncations. |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 60 | ASTContext &Ctx = ValMgr.getContext(); |
Ted Kremenek | c50e6df | 2010-01-11 02:33:26 +0000 | [diff] [blame] | 61 | unsigned castSize = Ctx.getTypeSize(castTy); |
| 62 | if (castSize == LI->getNumBits()) |
Ted Kremenek | 9031dd7 | 2009-07-21 00:12:07 +0000 | [diff] [blame] | 63 | return val; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 64 | |
Ted Kremenek | c50e6df | 2010-01-11 02:33:26 +0000 | [diff] [blame] | 65 | return ValMgr.makeLocAsInteger(LI->getLoc(), castSize); |
Ted Kremenek | 9031dd7 | 2009-07-21 00:12:07 +0000 | [diff] [blame] | 66 | } |
| 67 | |
| 68 | if (const SymExpr *se = val.getAsSymbolicExpression()) { |
| 69 | ASTContext &Ctx = ValMgr.getContext(); |
| 70 | QualType T = Ctx.getCanonicalType(se->getType(Ctx)); |
| 71 | if (T == Ctx.getCanonicalType(castTy)) |
| 72 | return val; |
Ted Kremenek | 8041747 | 2009-09-25 00:18:15 +0000 | [diff] [blame] | 73 | |
| 74 | // FIXME: Remove this hack when we support symbolic truncation/extension. |
| 75 | // HACK: If both castTy and T are integers, ignore the cast. This is |
| 76 | // not a permanent solution. Eventually we want to precisely handle |
| 77 | // extension/truncation of symbolic integers. This prevents us from losing |
| 78 | // precision when we assign 'x = y' and 'y' is symbolic and x and y are |
| 79 | // different integer types. |
| 80 | if (T->isIntegerType() && castTy->isIntegerType()) |
| 81 | return val; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 82 | |
Ted Kremenek | 9031dd7 | 2009-07-21 00:12:07 +0000 | [diff] [blame] | 83 | return UnknownVal(); |
| 84 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 85 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 86 | if (!isa<nonloc::ConcreteInt>(val)) |
| 87 | return UnknownVal(); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 88 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 89 | // Only handle casts from integers to integers. |
| 90 | if (!isLocType && !castTy->isIntegerType()) |
| 91 | return UnknownVal(); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 92 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 93 | llvm::APSInt i = cast<nonloc::ConcreteInt>(val).getValue(); |
| 94 | i.setIsUnsigned(castTy->isUnsignedIntegerType() || Loc::IsLocType(castTy)); |
| 95 | i.extOrTrunc(ValMgr.getContext().getTypeSize(castTy)); |
| 96 | |
| 97 | if (isLocType) |
| 98 | return ValMgr.makeIntLocVal(i); |
| 99 | else |
| 100 | return ValMgr.makeIntVal(i); |
| 101 | } |
| 102 | |
Ted Kremenek | 4653739 | 2009-07-16 01:33:37 +0000 | [diff] [blame] | 103 | SVal SimpleSValuator::EvalCastL(Loc val, QualType castTy) { |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 104 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 105 | // Casts from pointers -> pointers, just return the lval. |
| 106 | // |
| 107 | // Casts from pointers -> references, just return the lval. These |
| 108 | // can be introduced by the frontend for corner cases, e.g |
| 109 | // casting from va_list* to __builtin_va_list&. |
| 110 | // |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 111 | if (Loc::IsLocType(castTy) || castTy->isReferenceType()) |
| 112 | return val; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 113 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 114 | // FIXME: Handle transparent unions where a value can be "transparently" |
| 115 | // lifted into a union type. |
| 116 | if (castTy->isUnionType()) |
| 117 | return UnknownVal(); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 118 | |
Ted Kremenek | d617b85 | 2010-04-16 17:54:33 +0000 | [diff] [blame] | 119 | if (castTy->isIntegerType()) { |
| 120 | unsigned BitWidth = ValMgr.getContext().getTypeSize(castTy); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 121 | |
Ted Kremenek | d617b85 | 2010-04-16 17:54:33 +0000 | [diff] [blame] | 122 | if (!isa<loc::ConcreteInt>(val)) |
| 123 | return ValMgr.makeLocAsInteger(val, BitWidth); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 124 | |
Ted Kremenek | d617b85 | 2010-04-16 17:54:33 +0000 | [diff] [blame] | 125 | llvm::APSInt i = cast<loc::ConcreteInt>(val).getValue(); |
| 126 | i.setIsUnsigned(castTy->isUnsignedIntegerType() || Loc::IsLocType(castTy)); |
| 127 | i.extOrTrunc(BitWidth); |
| 128 | return ValMgr.makeIntVal(i); |
| 129 | } |
| 130 | |
| 131 | // All other cases: return 'UnknownVal'. This includes casting pointers |
| 132 | // to floats, which is probably badness it itself, but this is a good |
| 133 | // intermediate solution until we do something better. |
| 134 | return UnknownVal(); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 135 | } |
| 136 | |
| 137 | //===----------------------------------------------------------------------===// |
| 138 | // Transfer function for unary operators. |
| 139 | //===----------------------------------------------------------------------===// |
| 140 | |
| 141 | SVal SimpleSValuator::EvalMinus(NonLoc val) { |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 142 | switch (val.getSubKind()) { |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 143 | case nonloc::ConcreteIntKind: |
| 144 | return cast<nonloc::ConcreteInt>(val).evalMinus(ValMgr); |
| 145 | default: |
| 146 | return UnknownVal(); |
| 147 | } |
| 148 | } |
| 149 | |
| 150 | SVal SimpleSValuator::EvalComplement(NonLoc X) { |
| 151 | switch (X.getSubKind()) { |
| 152 | case nonloc::ConcreteIntKind: |
| 153 | return cast<nonloc::ConcreteInt>(X).evalComplement(ValMgr); |
| 154 | default: |
| 155 | return UnknownVal(); |
| 156 | } |
| 157 | } |
| 158 | |
| 159 | //===----------------------------------------------------------------------===// |
| 160 | // Transfer function for binary operators. |
| 161 | //===----------------------------------------------------------------------===// |
| 162 | |
| 163 | static BinaryOperator::Opcode NegateComparison(BinaryOperator::Opcode op) { |
| 164 | switch (op) { |
| 165 | default: |
| 166 | assert(false && "Invalid opcode."); |
| 167 | case BinaryOperator::LT: return BinaryOperator::GE; |
| 168 | case BinaryOperator::GT: return BinaryOperator::LE; |
| 169 | case BinaryOperator::LE: return BinaryOperator::GT; |
| 170 | case BinaryOperator::GE: return BinaryOperator::LT; |
| 171 | case BinaryOperator::EQ: return BinaryOperator::NE; |
| 172 | case BinaryOperator::NE: return BinaryOperator::EQ; |
| 173 | } |
| 174 | } |
| 175 | |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 176 | // Equality operators for Locs. |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 177 | // FIXME: All this logic will be revamped when we have MemRegion::getLocation() |
| 178 | // implemented. |
| 179 | |
| 180 | static SVal EvalEquality(ValueManager &ValMgr, Loc lhs, Loc rhs, bool isEqual, |
| 181 | QualType resultTy) { |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 182 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 183 | switch (lhs.getSubKind()) { |
| 184 | default: |
| 185 | assert(false && "EQ/NE not implemented for this Loc."); |
| 186 | return UnknownVal(); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 187 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 188 | case loc::ConcreteIntKind: { |
| 189 | if (SymbolRef rSym = rhs.getAsSymbol()) |
| 190 | return ValMgr.makeNonLoc(rSym, |
| 191 | isEqual ? BinaryOperator::EQ |
| 192 | : BinaryOperator::NE, |
| 193 | cast<loc::ConcreteInt>(lhs).getValue(), |
| 194 | resultTy); |
| 195 | break; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 196 | } |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 197 | case loc::MemRegionKind: { |
| 198 | if (SymbolRef lSym = lhs.getAsLocSymbol()) { |
| 199 | if (isa<loc::ConcreteInt>(rhs)) { |
| 200 | return ValMgr.makeNonLoc(lSym, |
| 201 | isEqual ? BinaryOperator::EQ |
| 202 | : BinaryOperator::NE, |
| 203 | cast<loc::ConcreteInt>(rhs).getValue(), |
| 204 | resultTy); |
| 205 | } |
| 206 | } |
| 207 | break; |
| 208 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 209 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 210 | case loc::GotoLabelKind: |
| 211 | break; |
| 212 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 213 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 214 | return ValMgr.makeTruthVal(isEqual ? lhs == rhs : lhs != rhs, resultTy); |
| 215 | } |
| 216 | |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 217 | SVal SimpleSValuator::MakeSymIntVal(const SymExpr *LHS, |
| 218 | BinaryOperator::Opcode op, |
| 219 | const llvm::APSInt &RHS, |
| 220 | QualType resultTy) { |
| 221 | bool isIdempotent = false; |
| 222 | |
| 223 | // Check for a few special cases with known reductions first. |
| 224 | switch (op) { |
| 225 | default: |
| 226 | // We can't reduce this case; just treat it normally. |
| 227 | break; |
| 228 | case BinaryOperator::Mul: |
| 229 | // a*0 and a*1 |
| 230 | if (RHS == 0) |
| 231 | return ValMgr.makeIntVal(0, resultTy); |
| 232 | else if (RHS == 1) |
| 233 | isIdempotent = true; |
| 234 | break; |
| 235 | case BinaryOperator::Div: |
| 236 | // a/0 and a/1 |
| 237 | if (RHS == 0) |
| 238 | // This is also handled elsewhere. |
| 239 | return UndefinedVal(); |
| 240 | else if (RHS == 1) |
| 241 | isIdempotent = true; |
| 242 | break; |
| 243 | case BinaryOperator::Rem: |
| 244 | // a%0 and a%1 |
| 245 | if (RHS == 0) |
| 246 | // This is also handled elsewhere. |
| 247 | return UndefinedVal(); |
| 248 | else if (RHS == 1) |
| 249 | return ValMgr.makeIntVal(0, resultTy); |
| 250 | break; |
| 251 | case BinaryOperator::Add: |
| 252 | case BinaryOperator::Sub: |
| 253 | case BinaryOperator::Shl: |
| 254 | case BinaryOperator::Shr: |
| 255 | case BinaryOperator::Xor: |
| 256 | // a+0, a-0, a<<0, a>>0, a^0 |
| 257 | if (RHS == 0) |
| 258 | isIdempotent = true; |
| 259 | break; |
| 260 | case BinaryOperator::And: |
| 261 | // a&0 and a&(~0) |
| 262 | if (RHS == 0) |
| 263 | return ValMgr.makeIntVal(0, resultTy); |
| 264 | else if (RHS.isAllOnesValue()) |
| 265 | isIdempotent = true; |
| 266 | break; |
| 267 | case BinaryOperator::Or: |
| 268 | // a|0 and a|(~0) |
| 269 | if (RHS == 0) |
| 270 | isIdempotent = true; |
| 271 | else if (RHS.isAllOnesValue()) { |
| 272 | BasicValueFactory &BVF = ValMgr.getBasicValueFactory(); |
| 273 | const llvm::APSInt &Result = BVF.Convert(resultTy, RHS); |
| 274 | return nonloc::ConcreteInt(Result); |
| 275 | } |
| 276 | break; |
| 277 | } |
| 278 | |
| 279 | // Idempotent ops (like a*1) can still change the type of an expression. |
| 280 | // Wrap the LHS up in a NonLoc again and let EvalCastNL do the dirty work. |
Benjamin Kramer | 24ada87 | 2010-06-20 10:20:36 +0000 | [diff] [blame] | 281 | if (isIdempotent) { |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 282 | if (SymbolRef LHSSym = dyn_cast<SymbolData>(LHS)) |
| 283 | return EvalCastNL(nonloc::SymbolVal(LHSSym), resultTy); |
Benjamin Kramer | 24ada87 | 2010-06-20 10:20:36 +0000 | [diff] [blame] | 284 | return EvalCastNL(nonloc::SymExprVal(LHS), resultTy); |
| 285 | } |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 286 | |
| 287 | // If we reach this point, the expression cannot be simplified. |
| 288 | // Make a SymExprVal for the entire thing. |
| 289 | return ValMgr.makeNonLoc(LHS, op, RHS, resultTy); |
| 290 | } |
| 291 | |
Ted Kremenek | cd8f6ac | 2009-10-06 01:39:48 +0000 | [diff] [blame] | 292 | SVal SimpleSValuator::EvalBinOpNN(const GRState *state, |
| 293 | BinaryOperator::Opcode op, |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 294 | NonLoc lhs, NonLoc rhs, |
Ted Kremenek | 54ca9b1 | 2009-07-13 21:55:12 +0000 | [diff] [blame] | 295 | QualType resultTy) { |
Ted Kremenek | 54ca9b1 | 2009-07-13 21:55:12 +0000 | [diff] [blame] | 296 | // Handle trivial case where left-side and right-side are the same. |
| 297 | if (lhs == rhs) |
| 298 | switch (op) { |
| 299 | default: |
| 300 | break; |
| 301 | case BinaryOperator::EQ: |
| 302 | case BinaryOperator::LE: |
| 303 | case BinaryOperator::GE: |
| 304 | return ValMgr.makeTruthVal(true, resultTy); |
| 305 | case BinaryOperator::LT: |
| 306 | case BinaryOperator::GT: |
| 307 | case BinaryOperator::NE: |
| 308 | return ValMgr.makeTruthVal(false, resultTy); |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 309 | case BinaryOperator::Xor: |
| 310 | case BinaryOperator::Sub: |
| 311 | return ValMgr.makeIntVal(0, resultTy); |
| 312 | case BinaryOperator::Or: |
| 313 | case BinaryOperator::And: |
| 314 | return EvalCastNL(lhs, resultTy); |
Ted Kremenek | 54ca9b1 | 2009-07-13 21:55:12 +0000 | [diff] [blame] | 315 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 316 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 317 | while (1) { |
| 318 | switch (lhs.getSubKind()) { |
| 319 | default: |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 320 | return UnknownVal(); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 321 | case nonloc::LocAsIntegerKind: { |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 322 | Loc lhsL = cast<nonloc::LocAsInteger>(lhs).getLoc(); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 323 | switch (rhs.getSubKind()) { |
| 324 | case nonloc::LocAsIntegerKind: |
| 325 | return EvalBinOpLL(op, lhsL, cast<nonloc::LocAsInteger>(rhs).getLoc(), |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 326 | resultTy); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 327 | case nonloc::ConcreteIntKind: { |
| 328 | // Transform the integer into a location and compare. |
| 329 | ASTContext& Ctx = ValMgr.getContext(); |
| 330 | llvm::APSInt i = cast<nonloc::ConcreteInt>(rhs).getValue(); |
| 331 | i.setIsUnsigned(true); |
| 332 | i.extOrTrunc(Ctx.getTypeSize(Ctx.VoidPtrTy)); |
| 333 | return EvalBinOpLL(op, lhsL, ValMgr.makeLoc(i), resultTy); |
| 334 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 335 | default: |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 336 | switch (op) { |
| 337 | case BinaryOperator::EQ: |
| 338 | return ValMgr.makeTruthVal(false, resultTy); |
| 339 | case BinaryOperator::NE: |
| 340 | return ValMgr.makeTruthVal(true, resultTy); |
| 341 | default: |
| 342 | // This case also handles pointer arithmetic. |
| 343 | return UnknownVal(); |
| 344 | } |
| 345 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 346 | } |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 347 | case nonloc::SymExprValKind: { |
Jordy Rose | ba0f61c | 2010-06-18 22:49:11 +0000 | [diff] [blame] | 348 | nonloc::SymExprVal *selhs = cast<nonloc::SymExprVal>(&lhs); |
| 349 | |
| 350 | // Only handle LHS of the form "$sym op constant", at least for now. |
| 351 | const SymIntExpr *symIntExpr = |
| 352 | dyn_cast<SymIntExpr>(selhs->getSymbolicExpression()); |
| 353 | |
| 354 | if (!symIntExpr) |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 355 | return UnknownVal(); |
| 356 | |
Jordy Rose | ba0f61c | 2010-06-18 22:49:11 +0000 | [diff] [blame] | 357 | // Is this a logical not? (!x is represented as x == 0.) |
| 358 | if (op == BinaryOperator::EQ && rhs.isZeroConstant()) { |
| 359 | // We know how to negate certain expressions. Simplify them here. |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 360 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 361 | BinaryOperator::Opcode opc = symIntExpr->getOpcode(); |
| 362 | switch (opc) { |
Jordy Rose | ba0f61c | 2010-06-18 22:49:11 +0000 | [diff] [blame] | 363 | default: |
| 364 | // We don't know how to negate this operation. |
| 365 | // Just handle it as if it were a normal comparison to 0. |
| 366 | break; |
| 367 | case BinaryOperator::LAnd: |
| 368 | case BinaryOperator::LOr: |
| 369 | assert(false && "Logical operators handled by branching logic."); |
| 370 | return UnknownVal(); |
| 371 | case BinaryOperator::Assign: |
| 372 | case BinaryOperator::MulAssign: |
| 373 | case BinaryOperator::DivAssign: |
| 374 | case BinaryOperator::RemAssign: |
| 375 | case BinaryOperator::AddAssign: |
| 376 | case BinaryOperator::SubAssign: |
| 377 | case BinaryOperator::ShlAssign: |
| 378 | case BinaryOperator::ShrAssign: |
| 379 | case BinaryOperator::AndAssign: |
| 380 | case BinaryOperator::XorAssign: |
| 381 | case BinaryOperator::OrAssign: |
| 382 | case BinaryOperator::Comma: |
| 383 | assert(false && "'=' and ',' operators handled by GRExprEngine."); |
| 384 | return UnknownVal(); |
| 385 | case BinaryOperator::PtrMemD: |
| 386 | case BinaryOperator::PtrMemI: |
| 387 | assert(false && "Pointer arithmetic not handled here."); |
| 388 | return UnknownVal(); |
| 389 | case BinaryOperator::LT: |
| 390 | case BinaryOperator::GT: |
| 391 | case BinaryOperator::LE: |
| 392 | case BinaryOperator::GE: |
| 393 | case BinaryOperator::EQ: |
| 394 | case BinaryOperator::NE: |
| 395 | // Negate the comparison and make a value. |
| 396 | opc = NegateComparison(opc); |
| 397 | assert(symIntExpr->getType(ValMgr.getContext()) == resultTy); |
| 398 | return ValMgr.makeNonLoc(symIntExpr->getLHS(), opc, |
| 399 | symIntExpr->getRHS(), resultTy); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 400 | } |
| 401 | } |
Jordy Rose | ba0f61c | 2010-06-18 22:49:11 +0000 | [diff] [blame] | 402 | |
| 403 | // For now, only handle expressions whose RHS is a constant. |
| 404 | const nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs); |
| 405 | if (!rhsInt) |
| 406 | return UnknownVal(); |
| 407 | |
| 408 | // If both the LHS and the current expression are additive, |
| 409 | // fold their constants. |
| 410 | if (BinaryOperator::isAdditiveOp(op)) { |
| 411 | BinaryOperator::Opcode lop = symIntExpr->getOpcode(); |
| 412 | if (BinaryOperator::isAdditiveOp(lop)) { |
| 413 | BasicValueFactory &BVF = ValMgr.getBasicValueFactory(); |
Jordy Rose | b4954a4 | 2010-06-21 20:15:15 +0000 | [diff] [blame] | 414 | |
| 415 | // resultTy may not be the best type to convert to, but it's |
| 416 | // probably the best choice in expressions with mixed type |
| 417 | // (such as x+1U+2LL). The rules for implicit conversions should |
| 418 | // choose a reasonable type to preserve the expression, and will |
| 419 | // at least match how the value is going to be used. |
| 420 | const llvm::APSInt &first = |
| 421 | BVF.Convert(resultTy, symIntExpr->getRHS()); |
| 422 | const llvm::APSInt &second = |
| 423 | BVF.Convert(resultTy, rhsInt->getValue()); |
| 424 | |
Jordy Rose | ba0f61c | 2010-06-18 22:49:11 +0000 | [diff] [blame] | 425 | const llvm::APSInt *newRHS; |
| 426 | if (lop == op) |
Jordy Rose | b4954a4 | 2010-06-21 20:15:15 +0000 | [diff] [blame] | 427 | newRHS = BVF.EvaluateAPSInt(BinaryOperator::Add, first, second); |
Jordy Rose | ba0f61c | 2010-06-18 22:49:11 +0000 | [diff] [blame] | 428 | else |
Jordy Rose | b4954a4 | 2010-06-21 20:15:15 +0000 | [diff] [blame] | 429 | newRHS = BVF.EvaluateAPSInt(BinaryOperator::Sub, first, second); |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 430 | return MakeSymIntVal(symIntExpr->getLHS(), lop, *newRHS, resultTy); |
Jordy Rose | ba0f61c | 2010-06-18 22:49:11 +0000 | [diff] [blame] | 431 | } |
| 432 | } |
| 433 | |
| 434 | // Otherwise, make a SymExprVal out of the expression. |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 435 | return MakeSymIntVal(symIntExpr, op, rhsInt->getValue(), resultTy); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 436 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 437 | case nonloc::ConcreteIntKind: { |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 438 | const nonloc::ConcreteInt& lhsInt = cast<nonloc::ConcreteInt>(lhs); |
| 439 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 440 | if (isa<nonloc::ConcreteInt>(rhs)) { |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 441 | return lhsInt.evalBinOp(ValMgr, op, cast<nonloc::ConcreteInt>(rhs)); |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 442 | } else { |
| 443 | const llvm::APSInt& lhsValue = lhsInt.getValue(); |
| 444 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 445 | // Swap the left and right sides and flip the operator if doing so |
| 446 | // allows us to better reason about the expression (this is a form |
| 447 | // of expression canonicalization). |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 448 | // While we're at it, catch some special cases for non-commutative ops. |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 449 | NonLoc tmp = rhs; |
| 450 | rhs = lhs; |
| 451 | lhs = tmp; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 452 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 453 | switch (op) { |
| 454 | case BinaryOperator::LT: op = BinaryOperator::GT; continue; |
| 455 | case BinaryOperator::GT: op = BinaryOperator::LT; continue; |
| 456 | case BinaryOperator::LE: op = BinaryOperator::GE; continue; |
| 457 | case BinaryOperator::GE: op = BinaryOperator::LE; continue; |
| 458 | case BinaryOperator::EQ: |
| 459 | case BinaryOperator::NE: |
| 460 | case BinaryOperator::Add: |
| 461 | case BinaryOperator::Mul: |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 462 | case BinaryOperator::And: |
| 463 | case BinaryOperator::Xor: |
| 464 | case BinaryOperator::Or: |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 465 | continue; |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 466 | case BinaryOperator::Shr: |
| 467 | if (lhsValue.isAllOnesValue() && lhsValue.isSigned()) |
| 468 | // At this point lhs and rhs have been swapped. |
| 469 | return rhs; |
| 470 | // FALL-THROUGH |
| 471 | case BinaryOperator::Shl: |
| 472 | if (lhsValue == 0) |
| 473 | // At this point lhs and rhs have been swapped. |
| 474 | return rhs; |
| 475 | return UnknownVal(); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 476 | default: |
| 477 | return UnknownVal(); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 478 | } |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 479 | } |
| 480 | } |
| 481 | case nonloc::SymbolValKind: { |
Ted Kremenek | cd8f6ac | 2009-10-06 01:39:48 +0000 | [diff] [blame] | 482 | nonloc::SymbolVal *slhs = cast<nonloc::SymbolVal>(&lhs); |
| 483 | SymbolRef Sym = slhs->getSymbol(); |
| 484 | |
Ted Kremenek | 9b02034 | 2009-10-17 07:39:35 +0000 | [diff] [blame] | 485 | // Does the symbol simplify to a constant? If so, "fold" the constant |
| 486 | // by setting 'lhs' to a ConcreteInt and try again. |
Ted Kremenek | cd8f6ac | 2009-10-06 01:39:48 +0000 | [diff] [blame] | 487 | if (Sym->getType(ValMgr.getContext())->isIntegerType()) |
| 488 | if (const llvm::APSInt *Constant = state->getSymVal(Sym)) { |
Ted Kremenek | 9b02034 | 2009-10-17 07:39:35 +0000 | [diff] [blame] | 489 | // The symbol evaluates to a constant. If necessary, promote the |
| 490 | // folded constant (LHS) to the result type. |
| 491 | BasicValueFactory &BVF = ValMgr.getBasicValueFactory(); |
| 492 | const llvm::APSInt &lhs_I = BVF.Convert(resultTy, *Constant); |
| 493 | lhs = nonloc::ConcreteInt(lhs_I); |
Ted Kremenek | b5deae5 | 2009-10-16 20:46:24 +0000 | [diff] [blame] | 494 | |
Ted Kremenek | 9b02034 | 2009-10-17 07:39:35 +0000 | [diff] [blame] | 495 | // Also promote the RHS (if necessary). |
| 496 | |
| 497 | // For shifts, it necessary promote the RHS to the result type. |
| 498 | if (BinaryOperator::isShiftOp(op)) |
| 499 | continue; |
| 500 | |
| 501 | // Other operators: do an implicit conversion. This shouldn't be |
Ted Kremenek | b5deae5 | 2009-10-16 20:46:24 +0000 | [diff] [blame] | 502 | // necessary once we support truncation/extension of symbolic values. |
Ted Kremenek | b1d0422 | 2009-10-06 03:44:49 +0000 | [diff] [blame] | 503 | if (nonloc::ConcreteInt *rhs_I = dyn_cast<nonloc::ConcreteInt>(&rhs)){ |
Ted Kremenek | 9b02034 | 2009-10-17 07:39:35 +0000 | [diff] [blame] | 504 | rhs = nonloc::ConcreteInt(BVF.Convert(resultTy, rhs_I->getValue())); |
Ted Kremenek | b1d0422 | 2009-10-06 03:44:49 +0000 | [diff] [blame] | 505 | } |
Ted Kremenek | 9b02034 | 2009-10-17 07:39:35 +0000 | [diff] [blame] | 506 | |
| 507 | continue; |
Ted Kremenek | cd8f6ac | 2009-10-06 01:39:48 +0000 | [diff] [blame] | 508 | } |
| 509 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 510 | if (isa<nonloc::ConcreteInt>(rhs)) { |
Jordy Rose | 43fdb7f | 2010-06-20 04:56:29 +0000 | [diff] [blame] | 511 | return MakeSymIntVal(slhs->getSymbol(), op, |
| 512 | cast<nonloc::ConcreteInt>(rhs).getValue(), |
| 513 | resultTy); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 514 | } |
| 515 | |
| 516 | return UnknownVal(); |
| 517 | } |
| 518 | } |
| 519 | } |
| 520 | } |
| 521 | |
| 522 | SVal SimpleSValuator::EvalBinOpLL(BinaryOperator::Opcode op, Loc lhs, Loc rhs, |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 523 | QualType resultTy) { |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 524 | switch (op) { |
| 525 | default: |
| 526 | return UnknownVal(); |
| 527 | case BinaryOperator::EQ: |
| 528 | case BinaryOperator::NE: |
| 529 | return EvalEquality(ValMgr, lhs, rhs, op == BinaryOperator::EQ, resultTy); |
Ted Kremenek | cd8f6ac | 2009-10-06 01:39:48 +0000 | [diff] [blame] | 530 | case BinaryOperator::LT: |
| 531 | case BinaryOperator::GT: |
| 532 | // FIXME: Generalize. For now, just handle the trivial case where |
| 533 | // the two locations are identical. |
| 534 | if (lhs == rhs) |
| 535 | return ValMgr.makeTruthVal(false, resultTy); |
| 536 | return UnknownVal(); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 537 | } |
| 538 | } |
| 539 | |
| 540 | SVal SimpleSValuator::EvalBinOpLN(const GRState *state, |
| 541 | BinaryOperator::Opcode op, |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 542 | Loc lhs, NonLoc rhs, QualType resultTy) { |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 543 | // Special case: 'rhs' is an integer that has the same width as a pointer and |
| 544 | // we are using the integer location in a comparison. Normally this cannot be |
| 545 | // triggered, but transfer functions like those for OSCommpareAndSwapBarrier32 |
| 546 | // can generate comparisons that trigger this code. |
| 547 | // FIXME: Are all locations guaranteed to have pointer width? |
| 548 | if (BinaryOperator::isEqualityOp(op)) { |
| 549 | if (nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs)) { |
| 550 | const llvm::APSInt *x = &rhsInt->getValue(); |
| 551 | ASTContext &ctx = ValMgr.getContext(); |
| 552 | if (ctx.getTypeSize(ctx.VoidPtrTy) == x->getBitWidth()) { |
| 553 | // Convert the signedness of the integer (if necessary). |
| 554 | if (x->isSigned()) |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 555 | x = &ValMgr.getBasicValueFactory().getValue(*x, true); |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 556 | |
| 557 | return EvalBinOpLL(op, lhs, loc::ConcreteInt(*x), resultTy); |
| 558 | } |
| 559 | } |
| 560 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 561 | |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 562 | // Delegate pointer arithmetic to the StoreManager. |
Zhongxing Xu | 461147f | 2010-02-05 05:24:20 +0000 | [diff] [blame] | 563 | return state->getStateManager().getStoreManager().EvalBinOp(op, lhs, |
Ted Kremenek | e839172 | 2009-06-26 00:25:05 +0000 | [diff] [blame] | 564 | rhs, resultTy); |
| 565 | } |