blob: 6632c8eb1aaac0b60755f836c34eb0d5d574f40c [file] [log] [blame]
Ted Kremenek846eabd2010-12-01 21:28:31 +00001// SimpleSValBuilder.cpp - A basic SValBuilder -----------------------*- C++ -*-
Ted Kremeneke8391722009-06-26 00:25:05 +00002//
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//
Ted Kremenek846eabd2010-12-01 21:28:31 +000010// This file defines SimpleSValBuilder, a basic implementation of SValBuilder.
Ted Kremeneke8391722009-06-26 00:25:05 +000011//
12//===----------------------------------------------------------------------===//
13
Ted Kremenek846eabd2010-12-01 21:28:31 +000014#include "clang/Checker/PathSensitive/SValBuilder.h"
Ted Kremenek1309f9a2010-01-25 04:41:41 +000015#include "clang/Checker/PathSensitive/GRState.h"
Ted Kremeneke8391722009-06-26 00:25:05 +000016
17using namespace clang;
18
19namespace {
Ted Kremenek846eabd2010-12-01 21:28:31 +000020class SimpleSValBuilder : public SValBuilder {
Ted Kremenek32c3fa42009-07-21 21:03:30 +000021protected:
Ted Kremenek9c149532010-12-01 21:57:22 +000022 virtual SVal evalCastNL(NonLoc val, QualType castTy);
23 virtual SVal evalCastL(Loc val, QualType castTy);
Ted Kremenek32c3fa42009-07-21 21:03:30 +000024
Ted Kremeneke8391722009-06-26 00:25:05 +000025public:
Ted Kremenekc8413fd2010-12-02 07:49:45 +000026 SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
27 GRStateManager &stateMgr)
28 : SValBuilder(alloc, context, stateMgr) {}
Ted Kremenek846eabd2010-12-01 21:28:31 +000029 virtual ~SimpleSValBuilder() {}
Mike Stump1eb44332009-09-09 15:08:12 +000030
Ted Kremenek9c149532010-12-01 21:57:22 +000031 virtual SVal evalMinus(NonLoc val);
32 virtual SVal evalComplement(NonLoc val);
33 virtual SVal evalBinOpNN(const GRState *state, BinaryOperator::Opcode op,
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +000034 NonLoc lhs, NonLoc rhs, QualType resultTy);
Ted Kremenek9c149532010-12-01 21:57:22 +000035 virtual SVal evalBinOpLL(const GRState *state, BinaryOperator::Opcode op,
Jordy Roseeac4a002010-06-28 08:26:15 +000036 Loc lhs, Loc rhs, QualType resultTy);
Ted Kremenek9c149532010-12-01 21:57:22 +000037 virtual SVal evalBinOpLN(const GRState *state, BinaryOperator::Opcode op,
Ted Kremeneke8391722009-06-26 00:25:05 +000038 Loc lhs, NonLoc rhs, QualType resultTy);
Jordy Rose32f26562010-07-04 00:00:41 +000039
Ted Kremenek9c149532010-12-01 21:57:22 +000040 /// getKnownValue - evaluates a given SVal. If the SVal has only one possible
Jordy Rose32f26562010-07-04 00:00:41 +000041 /// (integer) value, that value is returned. Otherwise, returns NULL.
42 virtual const llvm::APSInt *getKnownValue(const GRState *state, SVal V);
Jordy Rose43fdb7f2010-06-20 04:56:29 +000043
44 SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op,
45 const llvm::APSInt &RHS, QualType resultTy);
Mike Stump1eb44332009-09-09 15:08:12 +000046};
Ted Kremeneke8391722009-06-26 00:25:05 +000047} // end anonymous namespace
48
Ted Kremenekc8413fd2010-12-02 07:49:45 +000049SValBuilder *clang::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
50 ASTContext &context,
51 GRStateManager &stateMgr) {
52 return new SimpleSValBuilder(alloc, context, stateMgr);
Ted Kremeneke8391722009-06-26 00:25:05 +000053}
54
55//===----------------------------------------------------------------------===//
56// Transfer function for Casts.
57//===----------------------------------------------------------------------===//
58
Ted Kremenek9c149532010-12-01 21:57:22 +000059SVal SimpleSValBuilder::evalCastNL(NonLoc val, QualType castTy) {
Mike Stump1eb44332009-09-09 15:08:12 +000060
Ted Kremenekdd661142009-07-20 21:39:27 +000061 bool isLocType = Loc::IsLocType(castTy);
Mike Stump1eb44332009-09-09 15:08:12 +000062
Ted Kremenek9031dd72009-07-21 00:12:07 +000063 if (nonloc::LocAsInteger *LI = dyn_cast<nonloc::LocAsInteger>(&val)) {
64 if (isLocType)
Ted Kremenekdd661142009-07-20 21:39:27 +000065 return LI->getLoc();
Mike Stump1eb44332009-09-09 15:08:12 +000066
Ted Kremenekc50e6df2010-01-11 02:33:26 +000067 // FIXME: Correctly support promotions/truncations.
Ted Kremenekc8413fd2010-12-02 07:49:45 +000068 unsigned castSize = Context.getTypeSize(castTy);
Ted Kremenekc50e6df2010-01-11 02:33:26 +000069 if (castSize == LI->getNumBits())
Ted Kremenek9031dd72009-07-21 00:12:07 +000070 return val;
Ted Kremenekc8413fd2010-12-02 07:49:45 +000071 return makeLocAsInteger(LI->getLoc(), castSize);
Ted Kremenek9031dd72009-07-21 00:12:07 +000072 }
73
74 if (const SymExpr *se = val.getAsSymbolicExpression()) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +000075 QualType T = Context.getCanonicalType(se->getType(Context));
76 if (T == Context.getCanonicalType(castTy))
Ted Kremenek9031dd72009-07-21 00:12:07 +000077 return val;
Ted Kremenek80417472009-09-25 00:18:15 +000078
79 // FIXME: Remove this hack when we support symbolic truncation/extension.
80 // HACK: If both castTy and T are integers, ignore the cast. This is
81 // not a permanent solution. Eventually we want to precisely handle
82 // extension/truncation of symbolic integers. This prevents us from losing
83 // precision when we assign 'x = y' and 'y' is symbolic and x and y are
84 // different integer types.
85 if (T->isIntegerType() && castTy->isIntegerType())
86 return val;
Mike Stump1eb44332009-09-09 15:08:12 +000087
Ted Kremenek9031dd72009-07-21 00:12:07 +000088 return UnknownVal();
89 }
Mike Stump1eb44332009-09-09 15:08:12 +000090
Ted Kremeneke8391722009-06-26 00:25:05 +000091 if (!isa<nonloc::ConcreteInt>(val))
92 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +000093
Ted Kremeneke8391722009-06-26 00:25:05 +000094 // Only handle casts from integers to integers.
95 if (!isLocType && !castTy->isIntegerType())
96 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +000097
Ted Kremeneke8391722009-06-26 00:25:05 +000098 llvm::APSInt i = cast<nonloc::ConcreteInt>(val).getValue();
99 i.setIsUnsigned(castTy->isUnsignedIntegerType() || Loc::IsLocType(castTy));
Jay Foad9f71a8f2010-12-07 08:25:34 +0000100 i = i.extOrTrunc(Context.getTypeSize(castTy));
Ted Kremeneke8391722009-06-26 00:25:05 +0000101
102 if (isLocType)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000103 return makeIntLocVal(i);
Ted Kremeneke8391722009-06-26 00:25:05 +0000104 else
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000105 return makeIntVal(i);
Ted Kremeneke8391722009-06-26 00:25:05 +0000106}
107
Ted Kremenek9c149532010-12-01 21:57:22 +0000108SVal SimpleSValBuilder::evalCastL(Loc val, QualType castTy) {
Mike Stump1eb44332009-09-09 15:08:12 +0000109
Ted Kremeneke8391722009-06-26 00:25:05 +0000110 // Casts from pointers -> pointers, just return the lval.
111 //
112 // Casts from pointers -> references, just return the lval. These
113 // can be introduced by the frontend for corner cases, e.g
114 // casting from va_list* to __builtin_va_list&.
115 //
Ted Kremeneke8391722009-06-26 00:25:05 +0000116 if (Loc::IsLocType(castTy) || castTy->isReferenceType())
117 return val;
Mike Stump1eb44332009-09-09 15:08:12 +0000118
Ted Kremeneke8391722009-06-26 00:25:05 +0000119 // FIXME: Handle transparent unions where a value can be "transparently"
120 // lifted into a union type.
121 if (castTy->isUnionType())
122 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000123
Ted Kremenekd617b852010-04-16 17:54:33 +0000124 if (castTy->isIntegerType()) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000125 unsigned BitWidth = Context.getTypeSize(castTy);
Ted Kremeneke8391722009-06-26 00:25:05 +0000126
Ted Kremenekd617b852010-04-16 17:54:33 +0000127 if (!isa<loc::ConcreteInt>(val))
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000128 return makeLocAsInteger(val, BitWidth);
Mike Stump1eb44332009-09-09 15:08:12 +0000129
Ted Kremenekd617b852010-04-16 17:54:33 +0000130 llvm::APSInt i = cast<loc::ConcreteInt>(val).getValue();
131 i.setIsUnsigned(castTy->isUnsignedIntegerType() || Loc::IsLocType(castTy));
Jay Foad9f71a8f2010-12-07 08:25:34 +0000132 i = i.extOrTrunc(BitWidth);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000133 return makeIntVal(i);
Ted Kremenekd617b852010-04-16 17:54:33 +0000134 }
135
136 // All other cases: return 'UnknownVal'. This includes casting pointers
137 // to floats, which is probably badness it itself, but this is a good
138 // intermediate solution until we do something better.
139 return UnknownVal();
Ted Kremeneke8391722009-06-26 00:25:05 +0000140}
141
142//===----------------------------------------------------------------------===//
143// Transfer function for unary operators.
144//===----------------------------------------------------------------------===//
145
Ted Kremenek9c149532010-12-01 21:57:22 +0000146SVal SimpleSValBuilder::evalMinus(NonLoc val) {
Mike Stump1eb44332009-09-09 15:08:12 +0000147 switch (val.getSubKind()) {
Ted Kremeneke8391722009-06-26 00:25:05 +0000148 case nonloc::ConcreteIntKind:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000149 return cast<nonloc::ConcreteInt>(val).evalMinus(*this);
Ted Kremeneke8391722009-06-26 00:25:05 +0000150 default:
151 return UnknownVal();
152 }
153}
154
Ted Kremenek9c149532010-12-01 21:57:22 +0000155SVal SimpleSValBuilder::evalComplement(NonLoc X) {
Ted Kremeneke8391722009-06-26 00:25:05 +0000156 switch (X.getSubKind()) {
157 case nonloc::ConcreteIntKind:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000158 return cast<nonloc::ConcreteInt>(X).evalComplement(*this);
Ted Kremeneke8391722009-06-26 00:25:05 +0000159 default:
160 return UnknownVal();
161 }
162}
163
164//===----------------------------------------------------------------------===//
165// Transfer function for binary operators.
166//===----------------------------------------------------------------------===//
167
168static BinaryOperator::Opcode NegateComparison(BinaryOperator::Opcode op) {
169 switch (op) {
170 default:
171 assert(false && "Invalid opcode.");
John McCall2de56d12010-08-25 11:45:40 +0000172 case BO_LT: return BO_GE;
173 case BO_GT: return BO_LE;
174 case BO_LE: return BO_GT;
175 case BO_GE: return BO_LT;
176 case BO_EQ: return BO_NE;
177 case BO_NE: return BO_EQ;
Ted Kremeneke8391722009-06-26 00:25:05 +0000178 }
179}
180
Jordy Roseeac4a002010-06-28 08:26:15 +0000181static BinaryOperator::Opcode ReverseComparison(BinaryOperator::Opcode op) {
182 switch (op) {
183 default:
184 assert(false && "Invalid opcode.");
John McCall2de56d12010-08-25 11:45:40 +0000185 case BO_LT: return BO_GT;
186 case BO_GT: return BO_LT;
187 case BO_LE: return BO_GE;
188 case BO_GE: return BO_LE;
189 case BO_EQ:
190 case BO_NE:
Jordy Roseeac4a002010-06-28 08:26:15 +0000191 return op;
Ted Kremeneke8391722009-06-26 00:25:05 +0000192 }
Ted Kremeneke8391722009-06-26 00:25:05 +0000193}
194
Ted Kremenek846eabd2010-12-01 21:28:31 +0000195SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS,
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000196 BinaryOperator::Opcode op,
197 const llvm::APSInt &RHS,
198 QualType resultTy) {
199 bool isIdempotent = false;
200
201 // Check for a few special cases with known reductions first.
202 switch (op) {
203 default:
204 // We can't reduce this case; just treat it normally.
205 break;
John McCall2de56d12010-08-25 11:45:40 +0000206 case BO_Mul:
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000207 // a*0 and a*1
208 if (RHS == 0)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000209 return makeIntVal(0, resultTy);
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000210 else if (RHS == 1)
211 isIdempotent = true;
212 break;
John McCall2de56d12010-08-25 11:45:40 +0000213 case BO_Div:
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000214 // a/0 and a/1
215 if (RHS == 0)
216 // This is also handled elsewhere.
217 return UndefinedVal();
218 else if (RHS == 1)
219 isIdempotent = true;
220 break;
John McCall2de56d12010-08-25 11:45:40 +0000221 case BO_Rem:
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000222 // a%0 and a%1
223 if (RHS == 0)
224 // This is also handled elsewhere.
225 return UndefinedVal();
226 else if (RHS == 1)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000227 return makeIntVal(0, resultTy);
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000228 break;
John McCall2de56d12010-08-25 11:45:40 +0000229 case BO_Add:
230 case BO_Sub:
231 case BO_Shl:
232 case BO_Shr:
233 case BO_Xor:
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000234 // a+0, a-0, a<<0, a>>0, a^0
235 if (RHS == 0)
236 isIdempotent = true;
237 break;
John McCall2de56d12010-08-25 11:45:40 +0000238 case BO_And:
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000239 // a&0 and a&(~0)
240 if (RHS == 0)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000241 return makeIntVal(0, resultTy);
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000242 else if (RHS.isAllOnesValue())
243 isIdempotent = true;
244 break;
John McCall2de56d12010-08-25 11:45:40 +0000245 case BO_Or:
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000246 // a|0 and a|(~0)
247 if (RHS == 0)
248 isIdempotent = true;
249 else if (RHS.isAllOnesValue()) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000250 const llvm::APSInt &Result = BasicVals.Convert(resultTy, RHS);
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000251 return nonloc::ConcreteInt(Result);
252 }
253 break;
254 }
255
256 // Idempotent ops (like a*1) can still change the type of an expression.
Ted Kremenek9c149532010-12-01 21:57:22 +0000257 // Wrap the LHS up in a NonLoc again and let evalCastNL do the dirty work.
Benjamin Kramer24ada872010-06-20 10:20:36 +0000258 if (isIdempotent) {
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000259 if (SymbolRef LHSSym = dyn_cast<SymbolData>(LHS))
Ted Kremenek9c149532010-12-01 21:57:22 +0000260 return evalCastNL(nonloc::SymbolVal(LHSSym), resultTy);
261 return evalCastNL(nonloc::SymExprVal(LHS), resultTy);
Benjamin Kramer24ada872010-06-20 10:20:36 +0000262 }
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000263
264 // If we reach this point, the expression cannot be simplified.
265 // Make a SymExprVal for the entire thing.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000266 return makeNonLoc(LHS, op, RHS, resultTy);
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000267}
268
Ted Kremenek9c149532010-12-01 21:57:22 +0000269SVal SimpleSValBuilder::evalBinOpNN(const GRState *state,
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000270 BinaryOperator::Opcode op,
Ted Kremeneke8391722009-06-26 00:25:05 +0000271 NonLoc lhs, NonLoc rhs,
Ted Kremenek54ca9b12009-07-13 21:55:12 +0000272 QualType resultTy) {
Ted Kremenek54ca9b12009-07-13 21:55:12 +0000273 // Handle trivial case where left-side and right-side are the same.
274 if (lhs == rhs)
275 switch (op) {
276 default:
277 break;
John McCall2de56d12010-08-25 11:45:40 +0000278 case BO_EQ:
279 case BO_LE:
280 case BO_GE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000281 return makeTruthVal(true, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000282 case BO_LT:
283 case BO_GT:
284 case BO_NE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000285 return makeTruthVal(false, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000286 case BO_Xor:
287 case BO_Sub:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000288 return makeIntVal(0, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000289 case BO_Or:
290 case BO_And:
Ted Kremenek9c149532010-12-01 21:57:22 +0000291 return evalCastNL(lhs, resultTy);
Ted Kremenek54ca9b12009-07-13 21:55:12 +0000292 }
Mike Stump1eb44332009-09-09 15:08:12 +0000293
Ted Kremeneke8391722009-06-26 00:25:05 +0000294 while (1) {
295 switch (lhs.getSubKind()) {
296 default:
Mike Stump1eb44332009-09-09 15:08:12 +0000297 return UnknownVal();
Ted Kremeneke8391722009-06-26 00:25:05 +0000298 case nonloc::LocAsIntegerKind: {
Mike Stump1eb44332009-09-09 15:08:12 +0000299 Loc lhsL = cast<nonloc::LocAsInteger>(lhs).getLoc();
Ted Kremeneke8391722009-06-26 00:25:05 +0000300 switch (rhs.getSubKind()) {
301 case nonloc::LocAsIntegerKind:
Ted Kremenek9c149532010-12-01 21:57:22 +0000302 return evalBinOpLL(state, op, lhsL,
Jordy Roseeac4a002010-06-28 08:26:15 +0000303 cast<nonloc::LocAsInteger>(rhs).getLoc(),
Mike Stump1eb44332009-09-09 15:08:12 +0000304 resultTy);
Ted Kremeneke8391722009-06-26 00:25:05 +0000305 case nonloc::ConcreteIntKind: {
306 // Transform the integer into a location and compare.
Ted Kremeneke8391722009-06-26 00:25:05 +0000307 llvm::APSInt i = cast<nonloc::ConcreteInt>(rhs).getValue();
308 i.setIsUnsigned(true);
Jay Foad9f71a8f2010-12-07 08:25:34 +0000309 i = i.extOrTrunc(Context.getTypeSize(Context.VoidPtrTy));
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000310 return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy);
Ted Kremeneke8391722009-06-26 00:25:05 +0000311 }
Mike Stump1eb44332009-09-09 15:08:12 +0000312 default:
Ted Kremeneke8391722009-06-26 00:25:05 +0000313 switch (op) {
John McCall2de56d12010-08-25 11:45:40 +0000314 case BO_EQ:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000315 return makeTruthVal(false, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000316 case BO_NE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000317 return makeTruthVal(true, resultTy);
Ted Kremeneke8391722009-06-26 00:25:05 +0000318 default:
319 // This case also handles pointer arithmetic.
320 return UnknownVal();
321 }
322 }
Mike Stump1eb44332009-09-09 15:08:12 +0000323 }
Ted Kremeneke8391722009-06-26 00:25:05 +0000324 case nonloc::SymExprValKind: {
Jordy Roseba0f61c2010-06-18 22:49:11 +0000325 nonloc::SymExprVal *selhs = cast<nonloc::SymExprVal>(&lhs);
326
327 // Only handle LHS of the form "$sym op constant", at least for now.
328 const SymIntExpr *symIntExpr =
329 dyn_cast<SymIntExpr>(selhs->getSymbolicExpression());
330
331 if (!symIntExpr)
Ted Kremeneke8391722009-06-26 00:25:05 +0000332 return UnknownVal();
333
Jordy Roseba0f61c2010-06-18 22:49:11 +0000334 // Is this a logical not? (!x is represented as x == 0.)
John McCall2de56d12010-08-25 11:45:40 +0000335 if (op == BO_EQ && rhs.isZeroConstant()) {
Jordy Roseba0f61c2010-06-18 22:49:11 +0000336 // We know how to negate certain expressions. Simplify them here.
Mike Stump1eb44332009-09-09 15:08:12 +0000337
Ted Kremeneke8391722009-06-26 00:25:05 +0000338 BinaryOperator::Opcode opc = symIntExpr->getOpcode();
339 switch (opc) {
Jordy Roseba0f61c2010-06-18 22:49:11 +0000340 default:
341 // We don't know how to negate this operation.
342 // Just handle it as if it were a normal comparison to 0.
343 break;
John McCall2de56d12010-08-25 11:45:40 +0000344 case BO_LAnd:
345 case BO_LOr:
Jordy Roseba0f61c2010-06-18 22:49:11 +0000346 assert(false && "Logical operators handled by branching logic.");
347 return UnknownVal();
John McCall2de56d12010-08-25 11:45:40 +0000348 case BO_Assign:
349 case BO_MulAssign:
350 case BO_DivAssign:
351 case BO_RemAssign:
352 case BO_AddAssign:
353 case BO_SubAssign:
354 case BO_ShlAssign:
355 case BO_ShrAssign:
356 case BO_AndAssign:
357 case BO_XorAssign:
358 case BO_OrAssign:
359 case BO_Comma:
Jordy Roseba0f61c2010-06-18 22:49:11 +0000360 assert(false && "'=' and ',' operators handled by GRExprEngine.");
361 return UnknownVal();
John McCall2de56d12010-08-25 11:45:40 +0000362 case BO_PtrMemD:
363 case BO_PtrMemI:
Jordy Roseba0f61c2010-06-18 22:49:11 +0000364 assert(false && "Pointer arithmetic not handled here.");
365 return UnknownVal();
John McCall2de56d12010-08-25 11:45:40 +0000366 case BO_LT:
367 case BO_GT:
368 case BO_LE:
369 case BO_GE:
370 case BO_EQ:
371 case BO_NE:
Jordy Roseba0f61c2010-06-18 22:49:11 +0000372 // Negate the comparison and make a value.
373 opc = NegateComparison(opc);
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000374 assert(symIntExpr->getType(Context) == resultTy);
375 return makeNonLoc(symIntExpr->getLHS(), opc,
Jordy Roseba0f61c2010-06-18 22:49:11 +0000376 symIntExpr->getRHS(), resultTy);
Ted Kremeneke8391722009-06-26 00:25:05 +0000377 }
378 }
Jordy Roseba0f61c2010-06-18 22:49:11 +0000379
380 // For now, only handle expressions whose RHS is a constant.
381 const nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs);
382 if (!rhsInt)
383 return UnknownVal();
384
385 // If both the LHS and the current expression are additive,
386 // fold their constants.
387 if (BinaryOperator::isAdditiveOp(op)) {
388 BinaryOperator::Opcode lop = symIntExpr->getOpcode();
389 if (BinaryOperator::isAdditiveOp(lop)) {
Jordy Roseb4954a42010-06-21 20:15:15 +0000390 // resultTy may not be the best type to convert to, but it's
391 // probably the best choice in expressions with mixed type
392 // (such as x+1U+2LL). The rules for implicit conversions should
393 // choose a reasonable type to preserve the expression, and will
394 // at least match how the value is going to be used.
395 const llvm::APSInt &first =
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000396 BasicVals.Convert(resultTy, symIntExpr->getRHS());
Jordy Roseb4954a42010-06-21 20:15:15 +0000397 const llvm::APSInt &second =
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000398 BasicVals.Convert(resultTy, rhsInt->getValue());
Jordy Roseba0f61c2010-06-18 22:49:11 +0000399 const llvm::APSInt *newRHS;
400 if (lop == op)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000401 newRHS = BasicVals.evalAPSInt(BO_Add, first, second);
Jordy Roseba0f61c2010-06-18 22:49:11 +0000402 else
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000403 newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000404 return MakeSymIntVal(symIntExpr->getLHS(), lop, *newRHS, resultTy);
Jordy Roseba0f61c2010-06-18 22:49:11 +0000405 }
406 }
407
408 // Otherwise, make a SymExprVal out of the expression.
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000409 return MakeSymIntVal(symIntExpr, op, rhsInt->getValue(), resultTy);
Ted Kremeneke8391722009-06-26 00:25:05 +0000410 }
Mike Stump1eb44332009-09-09 15:08:12 +0000411 case nonloc::ConcreteIntKind: {
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000412 const nonloc::ConcreteInt& lhsInt = cast<nonloc::ConcreteInt>(lhs);
413
Ted Kremeneke8391722009-06-26 00:25:05 +0000414 if (isa<nonloc::ConcreteInt>(rhs)) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000415 return lhsInt.evalBinOp(*this, op, cast<nonloc::ConcreteInt>(rhs));
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000416 } else {
417 const llvm::APSInt& lhsValue = lhsInt.getValue();
418
Ted Kremeneke8391722009-06-26 00:25:05 +0000419 // Swap the left and right sides and flip the operator if doing so
420 // allows us to better reason about the expression (this is a form
421 // of expression canonicalization).
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000422 // While we're at it, catch some special cases for non-commutative ops.
Ted Kremeneke8391722009-06-26 00:25:05 +0000423 NonLoc tmp = rhs;
424 rhs = lhs;
425 lhs = tmp;
Mike Stump1eb44332009-09-09 15:08:12 +0000426
Ted Kremeneke8391722009-06-26 00:25:05 +0000427 switch (op) {
John McCall2de56d12010-08-25 11:45:40 +0000428 case BO_LT:
429 case BO_GT:
430 case BO_LE:
431 case BO_GE:
Jordy Roseeac4a002010-06-28 08:26:15 +0000432 op = ReverseComparison(op);
433 continue;
John McCall2de56d12010-08-25 11:45:40 +0000434 case BO_EQ:
435 case BO_NE:
436 case BO_Add:
437 case BO_Mul:
438 case BO_And:
439 case BO_Xor:
440 case BO_Or:
Ted Kremeneke8391722009-06-26 00:25:05 +0000441 continue;
John McCall2de56d12010-08-25 11:45:40 +0000442 case BO_Shr:
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000443 if (lhsValue.isAllOnesValue() && lhsValue.isSigned())
444 // At this point lhs and rhs have been swapped.
445 return rhs;
446 // FALL-THROUGH
John McCall2de56d12010-08-25 11:45:40 +0000447 case BO_Shl:
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000448 if (lhsValue == 0)
449 // At this point lhs and rhs have been swapped.
450 return rhs;
451 return UnknownVal();
Ted Kremeneke8391722009-06-26 00:25:05 +0000452 default:
453 return UnknownVal();
Mike Stump1eb44332009-09-09 15:08:12 +0000454 }
Ted Kremeneke8391722009-06-26 00:25:05 +0000455 }
456 }
457 case nonloc::SymbolValKind: {
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000458 nonloc::SymbolVal *slhs = cast<nonloc::SymbolVal>(&lhs);
459 SymbolRef Sym = slhs->getSymbol();
Ted Kremenek9b020342009-10-17 07:39:35 +0000460 // Does the symbol simplify to a constant? If so, "fold" the constant
461 // by setting 'lhs' to a ConcreteInt and try again.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000462 if (Sym->getType(Context)->isIntegerType())
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000463 if (const llvm::APSInt *Constant = state->getSymVal(Sym)) {
Ted Kremenek9b020342009-10-17 07:39:35 +0000464 // The symbol evaluates to a constant. If necessary, promote the
465 // folded constant (LHS) to the result type.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000466 const llvm::APSInt &lhs_I = BasicVals.Convert(resultTy, *Constant);
Ted Kremenek9b020342009-10-17 07:39:35 +0000467 lhs = nonloc::ConcreteInt(lhs_I);
Ted Kremenekb5deae52009-10-16 20:46:24 +0000468
Ted Kremenek9b020342009-10-17 07:39:35 +0000469 // Also promote the RHS (if necessary).
470
Jordy Rosea277e772010-08-09 20:31:57 +0000471 // For shifts, it is not necessary to promote the RHS.
Ted Kremenek9b020342009-10-17 07:39:35 +0000472 if (BinaryOperator::isShiftOp(op))
473 continue;
474
475 // Other operators: do an implicit conversion. This shouldn't be
Ted Kremenekb5deae52009-10-16 20:46:24 +0000476 // necessary once we support truncation/extension of symbolic values.
Ted Kremenekb1d04222009-10-06 03:44:49 +0000477 if (nonloc::ConcreteInt *rhs_I = dyn_cast<nonloc::ConcreteInt>(&rhs)){
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000478 rhs = nonloc::ConcreteInt(BasicVals.Convert(resultTy,
479 rhs_I->getValue()));
Ted Kremenekb1d04222009-10-06 03:44:49 +0000480 }
Ted Kremenek9b020342009-10-17 07:39:35 +0000481
482 continue;
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000483 }
Jordy Rosea277e772010-08-09 20:31:57 +0000484
485 // Is the RHS a symbol we can simplify?
486 if (const nonloc::SymbolVal *srhs = dyn_cast<nonloc::SymbolVal>(&rhs)) {
487 SymbolRef RSym = srhs->getSymbol();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000488 if (RSym->getType(Context)->isIntegerType()) {
Jordy Rosea277e772010-08-09 20:31:57 +0000489 if (const llvm::APSInt *Constant = state->getSymVal(RSym)) {
490 // The symbol evaluates to a constant.
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000491 const llvm::APSInt &rhs_I = BasicVals.Convert(resultTy, *Constant);
Jordy Rosea277e772010-08-09 20:31:57 +0000492 rhs = nonloc::ConcreteInt(rhs_I);
493 }
494 }
495 }
496
Ted Kremeneke8391722009-06-26 00:25:05 +0000497 if (isa<nonloc::ConcreteInt>(rhs)) {
Jordy Rose43fdb7f2010-06-20 04:56:29 +0000498 return MakeSymIntVal(slhs->getSymbol(), op,
499 cast<nonloc::ConcreteInt>(rhs).getValue(),
500 resultTy);
Ted Kremeneke8391722009-06-26 00:25:05 +0000501 }
502
503 return UnknownVal();
504 }
505 }
506 }
507}
508
Jordy Roseeac4a002010-06-28 08:26:15 +0000509// FIXME: all this logic will change if/when we have MemRegion::getLocation().
Ted Kremenek9c149532010-12-01 21:57:22 +0000510SVal SimpleSValBuilder::evalBinOpLL(const GRState *state,
Jordy Roseeac4a002010-06-28 08:26:15 +0000511 BinaryOperator::Opcode op,
512 Loc lhs, Loc rhs,
Mike Stump1eb44332009-09-09 15:08:12 +0000513 QualType resultTy) {
Jordy Roseeac4a002010-06-28 08:26:15 +0000514 // Only comparisons and subtractions are valid operations on two pointers.
515 // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
Ted Kremenek9c149532010-12-01 21:57:22 +0000516 // However, if a pointer is casted to an integer, evalBinOpNN may end up
Jordy Rosea2741482010-06-30 01:35:20 +0000517 // calling this function with another operation (PR7527). We don't attempt to
518 // model this for now, but it could be useful, particularly when the
519 // "location" is actually an integer value that's been passed through a void*.
John McCall2de56d12010-08-25 11:45:40 +0000520 if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub))
Jordy Rosea2741482010-06-30 01:35:20 +0000521 return UnknownVal();
Jordy Roseeac4a002010-06-28 08:26:15 +0000522
523 // Special cases for when both sides are identical.
524 if (lhs == rhs) {
525 switch (op) {
Ted Kremeneke8391722009-06-26 00:25:05 +0000526 default:
Jordy Roseeac4a002010-06-28 08:26:15 +0000527 assert(false && "Unimplemented operation for two identical values");
Ted Kremeneke8391722009-06-26 00:25:05 +0000528 return UnknownVal();
John McCall2de56d12010-08-25 11:45:40 +0000529 case BO_Sub:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000530 return makeZeroVal(resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000531 case BO_EQ:
532 case BO_LE:
533 case BO_GE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000534 return makeTruthVal(true, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000535 case BO_NE:
536 case BO_LT:
537 case BO_GT:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000538 return makeTruthVal(false, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000539 }
540 }
541
542 switch (lhs.getSubKind()) {
543 default:
544 assert(false && "Ordering not implemented for this Loc.");
545 return UnknownVal();
546
547 case loc::GotoLabelKind:
548 // The only thing we know about labels is that they're non-null.
549 if (rhs.isZeroConstant()) {
550 switch (op) {
551 default:
552 break;
John McCall2de56d12010-08-25 11:45:40 +0000553 case BO_Sub:
Ted Kremenek9c149532010-12-01 21:57:22 +0000554 return evalCastL(lhs, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000555 case BO_EQ:
556 case BO_LE:
557 case BO_LT:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000558 return makeTruthVal(false, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000559 case BO_NE:
560 case BO_GT:
561 case BO_GE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000562 return makeTruthVal(true, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000563 }
564 }
565 // There may be two labels for the same location, and a function region may
566 // have the same address as a label at the start of the function (depending
567 // on the ABI).
568 // FIXME: we can probably do a comparison against other MemRegions, though.
569 // FIXME: is there a way to tell if two labels refer to the same location?
570 return UnknownVal();
571
572 case loc::ConcreteIntKind: {
573 // If one of the operands is a symbol and the other is a constant,
574 // build an expression for use by the constraint manager.
575 if (SymbolRef rSym = rhs.getAsLocSymbol()) {
576 // We can only build expressions with symbols on the left,
577 // so we need a reversible operator.
578 if (!BinaryOperator::isComparisonOp(op))
579 return UnknownVal();
580
581 const llvm::APSInt &lVal = cast<loc::ConcreteInt>(lhs).getValue();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000582 return makeNonLoc(rSym, ReverseComparison(op), lVal, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000583 }
584
585 // If both operands are constants, just perform the operation.
586 if (loc::ConcreteInt *rInt = dyn_cast<loc::ConcreteInt>(&rhs)) {
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000587 SVal ResultVal = cast<loc::ConcreteInt>(lhs).evalBinOp(BasicVals, op,
588 *rInt);
Jordy Roseeac4a002010-06-28 08:26:15 +0000589 if (Loc *Result = dyn_cast<Loc>(&ResultVal))
Ted Kremenek9c149532010-12-01 21:57:22 +0000590 return evalCastL(*Result, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000591 else
592 return UnknownVal();
593 }
594
595 // Special case comparisons against NULL.
596 // This must come after the test if the RHS is a symbol, which is used to
597 // build constraints. The address of any non-symbolic region is guaranteed
598 // to be non-NULL, as is any label.
599 assert(isa<loc::MemRegionVal>(rhs) || isa<loc::GotoLabel>(rhs));
600 if (lhs.isZeroConstant()) {
601 switch (op) {
602 default:
603 break;
John McCall2de56d12010-08-25 11:45:40 +0000604 case BO_EQ:
605 case BO_GT:
606 case BO_GE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000607 return makeTruthVal(false, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000608 case BO_NE:
609 case BO_LT:
610 case BO_LE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000611 return makeTruthVal(true, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000612 }
613 }
614
615 // Comparing an arbitrary integer to a region or label address is
616 // completely unknowable.
617 return UnknownVal();
618 }
619 case loc::MemRegionKind: {
620 if (loc::ConcreteInt *rInt = dyn_cast<loc::ConcreteInt>(&rhs)) {
621 // If one of the operands is a symbol and the other is a constant,
622 // build an expression for use by the constraint manager.
623 if (SymbolRef lSym = lhs.getAsLocSymbol())
624 return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);
625
626 // Special case comparisons to NULL.
627 // This must come after the test if the LHS is a symbol, which is used to
628 // build constraints. The address of any non-symbolic region is guaranteed
629 // to be non-NULL.
630 if (rInt->isZeroConstant()) {
631 switch (op) {
632 default:
633 break;
John McCall2de56d12010-08-25 11:45:40 +0000634 case BO_Sub:
Ted Kremenek9c149532010-12-01 21:57:22 +0000635 return evalCastL(lhs, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000636 case BO_EQ:
637 case BO_LT:
638 case BO_LE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000639 return makeTruthVal(false, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000640 case BO_NE:
641 case BO_GT:
642 case BO_GE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000643 return makeTruthVal(true, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000644 }
645 }
646
647 // Comparing a region to an arbitrary integer is completely unknowable.
Ted Kremenekcd8f6ac2009-10-06 01:39:48 +0000648 return UnknownVal();
Jordy Roseeac4a002010-06-28 08:26:15 +0000649 }
650
651 // Get both values as regions, if possible.
652 const MemRegion *LeftMR = lhs.getAsRegion();
653 assert(LeftMR && "MemRegionKind SVal doesn't have a region!");
654
655 const MemRegion *RightMR = rhs.getAsRegion();
656 if (!RightMR)
657 // The RHS is probably a label, which in theory could address a region.
658 // FIXME: we can probably make a more useful statement about non-code
659 // regions, though.
660 return UnknownVal();
661
662 // If both values wrap regions, see if they're from different base regions.
663 const MemRegion *LeftBase = LeftMR->getBaseRegion();
664 const MemRegion *RightBase = RightMR->getBaseRegion();
665 if (LeftBase != RightBase &&
666 !isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) {
667 switch (op) {
668 default:
669 return UnknownVal();
John McCall2de56d12010-08-25 11:45:40 +0000670 case BO_EQ:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000671 return makeTruthVal(false, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000672 case BO_NE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000673 return makeTruthVal(true, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000674 }
675 }
676
677 // The two regions are from the same base region. See if they're both a
678 // type of region we know how to compare.
679
680 // FIXME: If/when there is a getAsRawOffset() for FieldRegions, this
681 // ElementRegion path and the FieldRegion path below should be unified.
682 if (const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR)) {
683 // First see if the right region is also an ElementRegion.
684 const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR);
685 if (!RightER)
686 return UnknownVal();
687
688 // Next, see if the two ERs have the same super-region and matching types.
689 // FIXME: This should do something useful even if the types don't match,
690 // though if both indexes are constant the RegionRawOffset path will
691 // give the correct answer.
692 if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
693 LeftER->getElementType() == RightER->getElementType()) {
694 // Get the left index and cast it to the correct type.
695 // If the index is unknown or undefined, bail out here.
696 SVal LeftIndexVal = LeftER->getIndex();
697 NonLoc *LeftIndex = dyn_cast<NonLoc>(&LeftIndexVal);
698 if (!LeftIndex)
699 return UnknownVal();
Ted Kremenek9c149532010-12-01 21:57:22 +0000700 LeftIndexVal = evalCastNL(*LeftIndex, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000701 LeftIndex = dyn_cast<NonLoc>(&LeftIndexVal);
702 if (!LeftIndex)
703 return UnknownVal();
704
705 // Do the same for the right index.
706 SVal RightIndexVal = RightER->getIndex();
707 NonLoc *RightIndex = dyn_cast<NonLoc>(&RightIndexVal);
708 if (!RightIndex)
709 return UnknownVal();
Ted Kremenek9c149532010-12-01 21:57:22 +0000710 RightIndexVal = evalCastNL(*RightIndex, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000711 RightIndex = dyn_cast<NonLoc>(&RightIndexVal);
712 if (!RightIndex)
713 return UnknownVal();
714
715 // Actually perform the operation.
Ted Kremenek9c149532010-12-01 21:57:22 +0000716 // evalBinOpNN expects the two indexes to already be the right type.
717 return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000718 }
719
720 // If the element indexes aren't comparable, see if the raw offsets are.
Zhongxing Xu7caf9b32010-08-02 04:56:14 +0000721 RegionRawOffset LeftOffset = LeftER->getAsArrayOffset();
722 RegionRawOffset RightOffset = RightER->getAsArrayOffset();
Jordy Roseeac4a002010-06-28 08:26:15 +0000723
724 if (LeftOffset.getRegion() != NULL &&
725 LeftOffset.getRegion() == RightOffset.getRegion()) {
726 int64_t left = LeftOffset.getByteOffset();
727 int64_t right = RightOffset.getByteOffset();
728
729 switch (op) {
730 default:
731 return UnknownVal();
John McCall2de56d12010-08-25 11:45:40 +0000732 case BO_LT:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000733 return makeTruthVal(left < right, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000734 case BO_GT:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000735 return makeTruthVal(left > right, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000736 case BO_LE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000737 return makeTruthVal(left <= right, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000738 case BO_GE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000739 return makeTruthVal(left >= right, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000740 case BO_EQ:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000741 return makeTruthVal(left == right, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000742 case BO_NE:
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000743 return makeTruthVal(left != right, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000744 }
745 }
746
747 // If we get here, we have no way of comparing the ElementRegions.
748 return UnknownVal();
749 }
750
751 // See if both regions are fields of the same structure.
752 // FIXME: This doesn't handle nesting, inheritance, or Objective-C ivars.
753 if (const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR)) {
754 // Only comparisons are meaningful here!
755 if (!BinaryOperator::isComparisonOp(op))
756 return UnknownVal();
757
758 // First see if the right region is also a FieldRegion.
759 const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR);
760 if (!RightFR)
761 return UnknownVal();
762
763 // Next, see if the two FRs have the same super-region.
764 // FIXME: This doesn't handle casts yet, and simply stripping the casts
765 // doesn't help.
766 if (LeftFR->getSuperRegion() != RightFR->getSuperRegion())
767 return UnknownVal();
768
769 const FieldDecl *LeftFD = LeftFR->getDecl();
770 const FieldDecl *RightFD = RightFR->getDecl();
771 const RecordDecl *RD = LeftFD->getParent();
772
773 // Make sure the two FRs are from the same kind of record. Just in case!
774 // FIXME: This is probably where inheritance would be a problem.
775 if (RD != RightFD->getParent())
776 return UnknownVal();
777
778 // We know for sure that the two fields are not the same, since that
779 // would have given us the same SVal.
John McCall2de56d12010-08-25 11:45:40 +0000780 if (op == BO_EQ)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000781 return makeTruthVal(false, resultTy);
John McCall2de56d12010-08-25 11:45:40 +0000782 if (op == BO_NE)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000783 return makeTruthVal(true, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000784
785 // Iterate through the fields and see which one comes first.
786 // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field
787 // members and the units in which bit-fields reside have addresses that
788 // increase in the order in which they are declared."
John McCall2de56d12010-08-25 11:45:40 +0000789 bool leftFirst = (op == BO_LT || op == BO_LE);
Jordy Roseeac4a002010-06-28 08:26:15 +0000790 for (RecordDecl::field_iterator I = RD->field_begin(),
791 E = RD->field_end(); I!=E; ++I) {
792 if (*I == LeftFD)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000793 return makeTruthVal(leftFirst, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000794 if (*I == RightFD)
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000795 return makeTruthVal(!leftFirst, resultTy);
Jordy Roseeac4a002010-06-28 08:26:15 +0000796 }
797
798 assert(false && "Fields not found in parent record's definition");
799 }
800
801 // If we get here, we have no way of comparing the regions.
802 return UnknownVal();
803 }
Ted Kremeneke8391722009-06-26 00:25:05 +0000804 }
805}
806
Ted Kremenek9c149532010-12-01 21:57:22 +0000807SVal SimpleSValBuilder::evalBinOpLN(const GRState *state,
Ted Kremeneke8391722009-06-26 00:25:05 +0000808 BinaryOperator::Opcode op,
Mike Stump1eb44332009-09-09 15:08:12 +0000809 Loc lhs, NonLoc rhs, QualType resultTy) {
Ted Kremeneke8391722009-06-26 00:25:05 +0000810 // Special case: 'rhs' is an integer that has the same width as a pointer and
811 // we are using the integer location in a comparison. Normally this cannot be
812 // triggered, but transfer functions like those for OSCommpareAndSwapBarrier32
813 // can generate comparisons that trigger this code.
814 // FIXME: Are all locations guaranteed to have pointer width?
Jordy Roseeac4a002010-06-28 08:26:15 +0000815 if (BinaryOperator::isComparisonOp(op)) {
Ted Kremeneke8391722009-06-26 00:25:05 +0000816 if (nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs)) {
817 const llvm::APSInt *x = &rhsInt->getValue();
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000818 ASTContext &ctx = Context;
Ted Kremeneke8391722009-06-26 00:25:05 +0000819 if (ctx.getTypeSize(ctx.VoidPtrTy) == x->getBitWidth()) {
820 // Convert the signedness of the integer (if necessary).
821 if (x->isSigned())
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000822 x = &getBasicValueFactory().getValue(*x, true);
Ted Kremeneke8391722009-06-26 00:25:05 +0000823
Ted Kremenek9c149532010-12-01 21:57:22 +0000824 return evalBinOpLL(state, op, lhs, loc::ConcreteInt(*x), resultTy);
Ted Kremeneke8391722009-06-26 00:25:05 +0000825 }
826 }
827 }
Ted Kremenek56af4462010-09-03 01:07:06 +0000828
829 // We are dealing with pointer arithmetic.
Mike Stump1eb44332009-09-09 15:08:12 +0000830
Ted Kremenek56af4462010-09-03 01:07:06 +0000831 // Handle pointer arithmetic on constant values.
832 if (nonloc::ConcreteInt *rhsInt = dyn_cast<nonloc::ConcreteInt>(&rhs)) {
833 if (loc::ConcreteInt *lhsInt = dyn_cast<loc::ConcreteInt>(&lhs)) {
834 const llvm::APSInt &leftI = lhsInt->getValue();
835 assert(leftI.isUnsigned());
836 llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true);
837
838 // Convert the bitwidth of rightI. This should deal with overflow
839 // since we are dealing with concrete values.
Jay Foad9f71a8f2010-12-07 08:25:34 +0000840 rightI = rightI.extOrTrunc(leftI.getBitWidth());
Ted Kremenek56af4462010-09-03 01:07:06 +0000841
842 // Offset the increment by the pointer size.
Ted Kremenek56af4462010-09-03 01:07:06 +0000843 llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true);
844 rightI *= Multiplicand;
845
846 // Compute the adjusted pointer.
847 switch (op) {
848 case BO_Add:
849 rightI = leftI + rightI;
850 break;
851 case BO_Sub:
852 rightI = leftI - rightI;
853 break;
854 default:
855 llvm_unreachable("Invalid pointer arithmetic operation");
856 }
Ted Kremenekc8413fd2010-12-02 07:49:45 +0000857 return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));
Ted Kremenek56af4462010-09-03 01:07:06 +0000858 }
859 }
860
861
862 // Delegate remaining pointer arithmetic to the StoreManager.
Ted Kremenek9c149532010-12-01 21:57:22 +0000863 return state->getStateManager().getStoreManager().evalBinOp(op, lhs,
Ted Kremeneke8391722009-06-26 00:25:05 +0000864 rhs, resultTy);
865}
Jordy Rose32f26562010-07-04 00:00:41 +0000866
Ted Kremenek846eabd2010-12-01 21:28:31 +0000867const llvm::APSInt *SimpleSValBuilder::getKnownValue(const GRState *state,
Jordy Rose32f26562010-07-04 00:00:41 +0000868 SVal V) {
869 if (V.isUnknownOrUndef())
870 return NULL;
871
872 if (loc::ConcreteInt* X = dyn_cast<loc::ConcreteInt>(&V))
873 return &X->getValue();
874
875 if (nonloc::ConcreteInt* X = dyn_cast<nonloc::ConcreteInt>(&V))
876 return &X->getValue();
877
878 if (SymbolRef Sym = V.getAsSymbol())
879 return state->getSymVal(Sym);
880
881 // FIXME: Add support for SymExprs.
882 return NULL;
883}