1 //== SimpleConstraintManager.cpp --------------------------------*- C++ -*--==//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines SimpleConstraintManager, a class that holds code shared
11 // between BasicConstraintManager and RangeConstraintManager.
13 //===----------------------------------------------------------------------===//
15 #include "SimpleConstraintManager.h"
16 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
23 SimpleConstraintManager::~SimpleConstraintManager() {}
25 bool SimpleConstraintManager::canReasonAbout(SVal X) const {
26 nonloc::SymbolVal *SymVal = dyn_cast<nonloc::SymbolVal>(&X);
27 if (SymVal && SymVal->isExpression()) {
28 const SymExpr *SE = SymVal->getSymbol();
30 if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
31 switch (SIE->getOpcode()) {
32 // We don't reason yet about bitwise-constraints on symbolic values.
37 // We don't reason yet about these arithmetic constraints on
57 ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef state,
60 if (isa<NonLoc>(Cond))
61 return assume(state, cast<NonLoc>(Cond), Assumption);
63 return assume(state, cast<Loc>(Cond), Assumption);
66 ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef state, Loc cond,
68 state = assumeAux(state, cond, assumption);
69 return SU.processAssume(state, cond, assumption);
72 ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef state,
73 Loc Cond, bool Assumption) {
75 BasicValueFactory &BasicVals = state->getBasicVals();
77 switch (Cond.getSubKind()) {
79 assert (false && "'Assume' not implemented for this Loc.");
82 case loc::MemRegionKind: {
83 // FIXME: Should this go into the storemanager?
85 const MemRegion *R = cast<loc::MemRegionVal>(Cond).getRegion();
86 const SubRegion *SubR = dyn_cast<SubRegion>(R);
89 // FIXME: now we only find the first symbolic region.
90 if (const SymbolicRegion *SymR = dyn_cast<SymbolicRegion>(SubR)) {
91 const llvm::APSInt &zero = BasicVals.getZeroWithPtrWidth();
93 return assumeSymNE(state, SymR->getSymbol(), zero, zero);
95 return assumeSymEQ(state, SymR->getSymbol(), zero, zero);
97 SubR = dyn_cast<SubRegion>(SubR->getSuperRegion());
103 case loc::GotoLabelKind:
104 return Assumption ? state : NULL;
106 case loc::ConcreteIntKind: {
107 bool b = cast<loc::ConcreteInt>(Cond).getValue() != 0;
108 bool isFeasible = b ? Assumption : !Assumption;
109 return isFeasible ? state : NULL;
114 ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef state,
117 state = assumeAux(state, cond, assumption);
118 return SU.processAssume(state, cond, assumption);
121 static BinaryOperator::Opcode NegateComparison(BinaryOperator::Opcode op) {
122 // FIXME: This should probably be part of BinaryOperator, since this isn't
123 // the only place it's used. (This code was copied from SimpleSValBuilder.cpp.)
126 llvm_unreachable("Invalid opcode.");
127 case BO_LT: return BO_GE;
128 case BO_GT: return BO_LE;
129 case BO_LE: return BO_GT;
130 case BO_GE: return BO_LT;
131 case BO_EQ: return BO_NE;
132 case BO_NE: return BO_EQ;
137 ProgramStateRef SimpleConstraintManager::assumeAuxForSymbol(
138 ProgramStateRef State,
141 QualType T = State->getSymbolManager().getType(Sym);
142 const llvm::APSInt &zero = State->getBasicVals().getValue(0, T);
144 return assumeSymNE(State, Sym, zero, zero);
146 return assumeSymEQ(State, Sym, zero, zero);
149 ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef state,
153 // We cannot reason about SymSymExprs, and can only reason about some
155 if (!canReasonAbout(Cond)) {
156 // Just add the constraint to the expression without trying to simplify.
157 SymbolRef sym = Cond.getAsSymExpr();
158 return assumeAuxForSymbol(state, sym, Assumption);
161 BasicValueFactory &BasicVals = state->getBasicVals();
162 SymbolManager &SymMgr = state->getSymbolManager();
164 switch (Cond.getSubKind()) {
166 llvm_unreachable("'Assume' not implemented for this NonLoc");
168 case nonloc::SymbolValKind: {
169 nonloc::SymbolVal& SV = cast<nonloc::SymbolVal>(Cond);
170 SymbolRef sym = SV.getSymbol();
173 // Handle SymbolData.
174 if (!SV.isExpression()) {
175 return assumeAuxForSymbol(state, sym, Assumption);
177 // Handle symbolic expression.
179 // We can only simplify expressions whose RHS is an integer.
180 const SymIntExpr *SE = dyn_cast<SymIntExpr>(sym);
182 return assumeAuxForSymbol(state, sym, Assumption);
184 BinaryOperator::Opcode op = SE->getOpcode();
185 // Implicitly compare non-comparison expressions to 0.
186 if (!BinaryOperator::isComparisonOp(op)) {
187 QualType T = SymMgr.getType(SE);
188 const llvm::APSInt &zero = BasicVals.getValue(0, T);
189 op = (Assumption ? BO_NE : BO_EQ);
190 return assumeSymRel(state, SE, op, zero);
192 // From here on out, op is the real comparison we'll be testing.
194 op = NegateComparison(op);
196 return assumeSymRel(state, SE->getLHS(), op, SE->getRHS());
200 case nonloc::ConcreteIntKind: {
201 bool b = cast<nonloc::ConcreteInt>(Cond).getValue() != 0;
202 bool isFeasible = b ? Assumption : !Assumption;
203 return isFeasible ? state : NULL;
206 case nonloc::LocAsIntegerKind:
207 return assumeAux(state, cast<nonloc::LocAsInteger>(Cond).getLoc(),
212 static llvm::APSInt computeAdjustment(const SymExpr *LHS,
214 llvm::APSInt DefaultAdjustment;
215 DefaultAdjustment = 0;
217 // First check if the LHS is a simple symbol reference.
218 if (isa<SymbolData>(LHS))
219 return DefaultAdjustment;
221 // Next, see if it's a "($sym+constant1)" expression.
222 const SymIntExpr *SE = dyn_cast<SymIntExpr>(LHS);
224 // We cannot simplify "($sym1+$sym2)".
226 return DefaultAdjustment;
228 // Get the constant out of the expression "($sym+constant1)" or
229 // "<expr>+constant1".
231 switch (SE->getOpcode()) {
235 return -SE->getRHS();
237 // We cannot simplify non-additive operators.
238 return DefaultAdjustment;
242 ProgramStateRef SimpleConstraintManager::assumeSymRel(ProgramStateRef state,
244 BinaryOperator::Opcode op,
245 const llvm::APSInt& Int) {
246 assert(BinaryOperator::isComparisonOp(op) &&
247 "Non-comparison ops should be rewritten as comparisons to zero.");
249 // We only handle simple comparisons of the form "$sym == constant"
250 // or "($sym+constant1) == constant2".
251 // The adjustment is "constant1" in the above expression. It's used to
252 // "slide" the solution range around for modular arithmetic. For example,
253 // x < 4 has the solution [0, 3]. x+2 < 4 has the solution [0-2, 3-2], which
254 // in modular arithmetic is [0, 1] U [UINT_MAX-1, UINT_MAX]. It's up to
255 // the subclasses of SimpleConstraintManager to handle the adjustment.
257 llvm::APSInt Adjustment = computeAdjustment(LHS, Sym);
259 // FIXME: This next section is a hack. It silently converts the integers to
260 // be of the same type as the symbol, which is not always correct. Really the
261 // comparisons should be performed using the Int's type, then mapped back to
262 // the symbol's range of values.
263 ProgramStateManager &StateMgr = state->getStateManager();
264 ASTContext &Ctx = StateMgr.getContext();
266 QualType T = Sym->getType(Ctx);
267 assert(T->isIntegerType() || Loc::isLocType(T));
268 unsigned bitwidth = Ctx.getTypeSize(T);
270 = T->isUnsignedIntegerOrEnumerationType() || Loc::isLocType(T);
272 // Convert the adjustment.
273 Adjustment.setIsUnsigned(isSymUnsigned);
274 Adjustment = Adjustment.extOrTrunc(bitwidth);
276 // Convert the right-hand side integer.
277 llvm::APSInt ConvertedInt(Int, isSymUnsigned);
278 ConvertedInt = ConvertedInt.extOrTrunc(bitwidth);
282 // No logic yet for other operators. assume the constraint is feasible.
286 return assumeSymEQ(state, Sym, ConvertedInt, Adjustment);
289 return assumeSymNE(state, Sym, ConvertedInt, Adjustment);
292 return assumeSymGT(state, Sym, ConvertedInt, Adjustment);
295 return assumeSymGE(state, Sym, ConvertedInt, Adjustment);
298 return assumeSymLT(state, Sym, ConvertedInt, Adjustment);
301 return assumeSymLE(state, Sym, ConvertedInt, Adjustment);
305 } // end of namespace ento
307 } // end of namespace clang