• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // SimpleSValBuilder.cpp - A basic SValBuilder -----------------------*- 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 SimpleSValBuilder, a basic implementation of SValBuilder.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
15 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
16 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
17 
18 using namespace clang;
19 using namespace ento;
20 
21 namespace {
22 class SimpleSValBuilder : public SValBuilder {
23 protected:
24   SVal dispatchCast(SVal val, QualType castTy) override;
25   SVal evalCastFromNonLoc(NonLoc val, QualType castTy) override;
26   SVal evalCastFromLoc(Loc val, QualType castTy) override;
27 
28 public:
SimpleSValBuilder(llvm::BumpPtrAllocator & alloc,ASTContext & context,ProgramStateManager & stateMgr)29   SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
30                     ProgramStateManager &stateMgr)
31                     : SValBuilder(alloc, context, stateMgr) {}
~SimpleSValBuilder()32   ~SimpleSValBuilder() override {}
33 
34   SVal evalMinus(NonLoc val) override;
35   SVal evalComplement(NonLoc val) override;
36   SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
37                    NonLoc lhs, NonLoc rhs, QualType resultTy) override;
38   SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
39                    Loc lhs, Loc rhs, QualType resultTy) override;
40   SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
41                    Loc lhs, NonLoc rhs, QualType resultTy) override;
42 
43   /// getKnownValue - evaluates a given SVal. If the SVal has only one possible
44   ///  (integer) value, that value is returned. Otherwise, returns NULL.
45   const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V) override;
46 
47   SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op,
48                      const llvm::APSInt &RHS, QualType resultTy);
49 };
50 } // end anonymous namespace
51 
createSimpleSValBuilder(llvm::BumpPtrAllocator & alloc,ASTContext & context,ProgramStateManager & stateMgr)52 SValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
53                                            ASTContext &context,
54                                            ProgramStateManager &stateMgr) {
55   return new SimpleSValBuilder(alloc, context, stateMgr);
56 }
57 
58 //===----------------------------------------------------------------------===//
59 // Transfer function for Casts.
60 //===----------------------------------------------------------------------===//
61 
dispatchCast(SVal Val,QualType CastTy)62 SVal SimpleSValBuilder::dispatchCast(SVal Val, QualType CastTy) {
63   assert(Val.getAs<Loc>() || Val.getAs<NonLoc>());
64   return Val.getAs<Loc>() ? evalCastFromLoc(Val.castAs<Loc>(), CastTy)
65                            : evalCastFromNonLoc(Val.castAs<NonLoc>(), CastTy);
66 }
67 
evalCastFromNonLoc(NonLoc val,QualType castTy)68 SVal SimpleSValBuilder::evalCastFromNonLoc(NonLoc val, QualType castTy) {
69 
70   bool isLocType = Loc::isLocType(castTy);
71 
72   if (Optional<nonloc::LocAsInteger> LI = val.getAs<nonloc::LocAsInteger>()) {
73     if (isLocType)
74       return LI->getLoc();
75 
76     // FIXME: Correctly support promotions/truncations.
77     unsigned castSize = Context.getTypeSize(castTy);
78     if (castSize == LI->getNumBits())
79       return val;
80     return makeLocAsInteger(LI->getLoc(), castSize);
81   }
82 
83   if (const SymExpr *se = val.getAsSymbolicExpression()) {
84     QualType T = Context.getCanonicalType(se->getType());
85     // If types are the same or both are integers, ignore the cast.
86     // FIXME: Remove this hack when we support symbolic truncation/extension.
87     // HACK: If both castTy and T are integers, ignore the cast.  This is
88     // not a permanent solution.  Eventually we want to precisely handle
89     // extension/truncation of symbolic integers.  This prevents us from losing
90     // precision when we assign 'x = y' and 'y' is symbolic and x and y are
91     // different integer types.
92    if (haveSameType(T, castTy))
93       return val;
94 
95     if (!isLocType)
96       return makeNonLoc(se, T, castTy);
97     return UnknownVal();
98   }
99 
100   // If value is a non-integer constant, produce unknown.
101   if (!val.getAs<nonloc::ConcreteInt>())
102     return UnknownVal();
103 
104   // Handle casts to a boolean type.
105   if (castTy->isBooleanType()) {
106     bool b = val.castAs<nonloc::ConcreteInt>().getValue().getBoolValue();
107     return makeTruthVal(b, castTy);
108   }
109 
110   // Only handle casts from integers to integers - if val is an integer constant
111   // being cast to a non-integer type, produce unknown.
112   if (!isLocType && !castTy->isIntegralOrEnumerationType())
113     return UnknownVal();
114 
115   llvm::APSInt i = val.castAs<nonloc::ConcreteInt>().getValue();
116   BasicVals.getAPSIntType(castTy).apply(i);
117 
118   if (isLocType)
119     return makeIntLocVal(i);
120   else
121     return makeIntVal(i);
122 }
123 
evalCastFromLoc(Loc val,QualType castTy)124 SVal SimpleSValBuilder::evalCastFromLoc(Loc val, QualType castTy) {
125 
126   // Casts from pointers -> pointers, just return the lval.
127   //
128   // Casts from pointers -> references, just return the lval.  These
129   //   can be introduced by the frontend for corner cases, e.g
130   //   casting from va_list* to __builtin_va_list&.
131   //
132   if (Loc::isLocType(castTy) || castTy->isReferenceType())
133     return val;
134 
135   // FIXME: Handle transparent unions where a value can be "transparently"
136   //  lifted into a union type.
137   if (castTy->isUnionType())
138     return UnknownVal();
139 
140   // Casting a Loc to a bool will almost always be true,
141   // unless this is a weak function or a symbolic region.
142   if (castTy->isBooleanType()) {
143     switch (val.getSubKind()) {
144       case loc::MemRegionValKind: {
145         const MemRegion *R = val.castAs<loc::MemRegionVal>().getRegion();
146         if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R))
147           if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl()))
148             if (FD->isWeak())
149               // FIXME: Currently we are using an extent symbol here,
150               // because there are no generic region address metadata
151               // symbols to use, only content metadata.
152               return nonloc::SymbolVal(SymMgr.getExtentSymbol(FTR));
153 
154         if (const SymbolicRegion *SymR = R->getSymbolicBase())
155           return nonloc::SymbolVal(SymR->getSymbol());
156 
157         // FALL-THROUGH
158       }
159 
160       case loc::GotoLabelKind:
161         // Labels and non-symbolic memory regions are always true.
162         return makeTruthVal(true, castTy);
163     }
164   }
165 
166   if (castTy->isIntegralOrEnumerationType()) {
167     unsigned BitWidth = Context.getTypeSize(castTy);
168 
169     if (!val.getAs<loc::ConcreteInt>())
170       return makeLocAsInteger(val, BitWidth);
171 
172     llvm::APSInt i = val.castAs<loc::ConcreteInt>().getValue();
173     BasicVals.getAPSIntType(castTy).apply(i);
174     return makeIntVal(i);
175   }
176 
177   // All other cases: return 'UnknownVal'.  This includes casting pointers
178   // to floats, which is probably badness it itself, but this is a good
179   // intermediate solution until we do something better.
180   return UnknownVal();
181 }
182 
183 //===----------------------------------------------------------------------===//
184 // Transfer function for unary operators.
185 //===----------------------------------------------------------------------===//
186 
evalMinus(NonLoc val)187 SVal SimpleSValBuilder::evalMinus(NonLoc val) {
188   switch (val.getSubKind()) {
189   case nonloc::ConcreteIntKind:
190     return val.castAs<nonloc::ConcreteInt>().evalMinus(*this);
191   default:
192     return UnknownVal();
193   }
194 }
195 
evalComplement(NonLoc X)196 SVal SimpleSValBuilder::evalComplement(NonLoc X) {
197   switch (X.getSubKind()) {
198   case nonloc::ConcreteIntKind:
199     return X.castAs<nonloc::ConcreteInt>().evalComplement(*this);
200   default:
201     return UnknownVal();
202   }
203 }
204 
205 //===----------------------------------------------------------------------===//
206 // Transfer function for binary operators.
207 //===----------------------------------------------------------------------===//
208 
MakeSymIntVal(const SymExpr * LHS,BinaryOperator::Opcode op,const llvm::APSInt & RHS,QualType resultTy)209 SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS,
210                                     BinaryOperator::Opcode op,
211                                     const llvm::APSInt &RHS,
212                                     QualType resultTy) {
213   bool isIdempotent = false;
214 
215   // Check for a few special cases with known reductions first.
216   switch (op) {
217   default:
218     // We can't reduce this case; just treat it normally.
219     break;
220   case BO_Mul:
221     // a*0 and a*1
222     if (RHS == 0)
223       return makeIntVal(0, resultTy);
224     else if (RHS == 1)
225       isIdempotent = true;
226     break;
227   case BO_Div:
228     // a/0 and a/1
229     if (RHS == 0)
230       // This is also handled elsewhere.
231       return UndefinedVal();
232     else if (RHS == 1)
233       isIdempotent = true;
234     break;
235   case BO_Rem:
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       return makeIntVal(0, resultTy);
242     break;
243   case BO_Add:
244   case BO_Sub:
245   case BO_Shl:
246   case BO_Shr:
247   case BO_Xor:
248     // a+0, a-0, a<<0, a>>0, a^0
249     if (RHS == 0)
250       isIdempotent = true;
251     break;
252   case BO_And:
253     // a&0 and a&(~0)
254     if (RHS == 0)
255       return makeIntVal(0, resultTy);
256     else if (RHS.isAllOnesValue())
257       isIdempotent = true;
258     break;
259   case BO_Or:
260     // a|0 and a|(~0)
261     if (RHS == 0)
262       isIdempotent = true;
263     else if (RHS.isAllOnesValue()) {
264       const llvm::APSInt &Result = BasicVals.Convert(resultTy, RHS);
265       return nonloc::ConcreteInt(Result);
266     }
267     break;
268   }
269 
270   // Idempotent ops (like a*1) can still change the type of an expression.
271   // Wrap the LHS up in a NonLoc again and let evalCastFromNonLoc do the
272   // dirty work.
273   if (isIdempotent)
274       return evalCastFromNonLoc(nonloc::SymbolVal(LHS), resultTy);
275 
276   // If we reach this point, the expression cannot be simplified.
277   // Make a SymbolVal for the entire expression, after converting the RHS.
278   const llvm::APSInt *ConvertedRHS = &RHS;
279   if (BinaryOperator::isComparisonOp(op)) {
280     // We're looking for a type big enough to compare the symbolic value
281     // with the given constant.
282     // FIXME: This is an approximation of Sema::UsualArithmeticConversions.
283     ASTContext &Ctx = getContext();
284     QualType SymbolType = LHS->getType();
285     uint64_t ValWidth = RHS.getBitWidth();
286     uint64_t TypeWidth = Ctx.getTypeSize(SymbolType);
287 
288     if (ValWidth < TypeWidth) {
289       // If the value is too small, extend it.
290       ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
291     } else if (ValWidth == TypeWidth) {
292       // If the value is signed but the symbol is unsigned, do the comparison
293       // in unsigned space. [C99 6.3.1.8]
294       // (For the opposite case, the value is already unsigned.)
295       if (RHS.isSigned() && !SymbolType->isSignedIntegerOrEnumerationType())
296         ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
297     }
298   } else
299     ConvertedRHS = &BasicVals.Convert(resultTy, RHS);
300 
301   return makeNonLoc(LHS, op, *ConvertedRHS, resultTy);
302 }
303 
evalBinOpNN(ProgramStateRef state,BinaryOperator::Opcode op,NonLoc lhs,NonLoc rhs,QualType resultTy)304 SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
305                                   BinaryOperator::Opcode op,
306                                   NonLoc lhs, NonLoc rhs,
307                                   QualType resultTy)  {
308   NonLoc InputLHS = lhs;
309   NonLoc InputRHS = rhs;
310 
311   // Handle trivial case where left-side and right-side are the same.
312   if (lhs == rhs)
313     switch (op) {
314       default:
315         break;
316       case BO_EQ:
317       case BO_LE:
318       case BO_GE:
319         return makeTruthVal(true, resultTy);
320       case BO_LT:
321       case BO_GT:
322       case BO_NE:
323         return makeTruthVal(false, resultTy);
324       case BO_Xor:
325       case BO_Sub:
326         if (resultTy->isIntegralOrEnumerationType())
327           return makeIntVal(0, resultTy);
328         return evalCastFromNonLoc(makeIntVal(0, /*Unsigned=*/false), resultTy);
329       case BO_Or:
330       case BO_And:
331         return evalCastFromNonLoc(lhs, resultTy);
332     }
333 
334   while (1) {
335     switch (lhs.getSubKind()) {
336     default:
337       return makeSymExprValNN(state, op, lhs, rhs, resultTy);
338     case nonloc::LocAsIntegerKind: {
339       Loc lhsL = lhs.castAs<nonloc::LocAsInteger>().getLoc();
340       switch (rhs.getSubKind()) {
341         case nonloc::LocAsIntegerKind:
342           return evalBinOpLL(state, op, lhsL,
343                              rhs.castAs<nonloc::LocAsInteger>().getLoc(),
344                              resultTy);
345         case nonloc::ConcreteIntKind: {
346           // Transform the integer into a location and compare.
347           llvm::APSInt i = rhs.castAs<nonloc::ConcreteInt>().getValue();
348           BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i);
349           return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy);
350         }
351         default:
352           switch (op) {
353             case BO_EQ:
354               return makeTruthVal(false, resultTy);
355             case BO_NE:
356               return makeTruthVal(true, resultTy);
357             default:
358               // This case also handles pointer arithmetic.
359               return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
360           }
361       }
362     }
363     case nonloc::ConcreteIntKind: {
364       llvm::APSInt LHSValue = lhs.castAs<nonloc::ConcreteInt>().getValue();
365 
366       // If we're dealing with two known constants, just perform the operation.
367       if (const llvm::APSInt *KnownRHSValue = getKnownValue(state, rhs)) {
368         llvm::APSInt RHSValue = *KnownRHSValue;
369         if (BinaryOperator::isComparisonOp(op)) {
370           // We're looking for a type big enough to compare the two values.
371           // FIXME: This is not correct. char + short will result in a promotion
372           // to int. Unfortunately we have lost types by this point.
373           APSIntType CompareType = std::max(APSIntType(LHSValue),
374                                             APSIntType(RHSValue));
375           CompareType.apply(LHSValue);
376           CompareType.apply(RHSValue);
377         } else if (!BinaryOperator::isShiftOp(op)) {
378           APSIntType IntType = BasicVals.getAPSIntType(resultTy);
379           IntType.apply(LHSValue);
380           IntType.apply(RHSValue);
381         }
382 
383         const llvm::APSInt *Result =
384           BasicVals.evalAPSInt(op, LHSValue, RHSValue);
385         if (!Result)
386           return UndefinedVal();
387 
388         return nonloc::ConcreteInt(*Result);
389       }
390 
391       // Swap the left and right sides and flip the operator if doing so
392       // allows us to better reason about the expression (this is a form
393       // of expression canonicalization).
394       // While we're at it, catch some special cases for non-commutative ops.
395       switch (op) {
396       case BO_LT:
397       case BO_GT:
398       case BO_LE:
399       case BO_GE:
400         op = BinaryOperator::reverseComparisonOp(op);
401         // FALL-THROUGH
402       case BO_EQ:
403       case BO_NE:
404       case BO_Add:
405       case BO_Mul:
406       case BO_And:
407       case BO_Xor:
408       case BO_Or:
409         std::swap(lhs, rhs);
410         continue;
411       case BO_Shr:
412         // (~0)>>a
413         if (LHSValue.isAllOnesValue() && LHSValue.isSigned())
414           return evalCastFromNonLoc(lhs, resultTy);
415         // FALL-THROUGH
416       case BO_Shl:
417         // 0<<a and 0>>a
418         if (LHSValue == 0)
419           return evalCastFromNonLoc(lhs, resultTy);
420         return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
421       default:
422         return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
423       }
424     }
425     case nonloc::SymbolValKind: {
426       // We only handle LHS as simple symbols or SymIntExprs.
427       SymbolRef Sym = lhs.castAs<nonloc::SymbolVal>().getSymbol();
428 
429       // LHS is a symbolic expression.
430       if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(Sym)) {
431 
432         // Is this a logical not? (!x is represented as x == 0.)
433         if (op == BO_EQ && rhs.isZeroConstant()) {
434           // We know how to negate certain expressions. Simplify them here.
435 
436           BinaryOperator::Opcode opc = symIntExpr->getOpcode();
437           switch (opc) {
438           default:
439             // We don't know how to negate this operation.
440             // Just handle it as if it were a normal comparison to 0.
441             break;
442           case BO_LAnd:
443           case BO_LOr:
444             llvm_unreachable("Logical operators handled by branching logic.");
445           case BO_Assign:
446           case BO_MulAssign:
447           case BO_DivAssign:
448           case BO_RemAssign:
449           case BO_AddAssign:
450           case BO_SubAssign:
451           case BO_ShlAssign:
452           case BO_ShrAssign:
453           case BO_AndAssign:
454           case BO_XorAssign:
455           case BO_OrAssign:
456           case BO_Comma:
457             llvm_unreachable("'=' and ',' operators handled by ExprEngine.");
458           case BO_PtrMemD:
459           case BO_PtrMemI:
460             llvm_unreachable("Pointer arithmetic not handled here.");
461           case BO_LT:
462           case BO_GT:
463           case BO_LE:
464           case BO_GE:
465           case BO_EQ:
466           case BO_NE:
467             assert(resultTy->isBooleanType() ||
468                    resultTy == getConditionType());
469             assert(symIntExpr->getType()->isBooleanType() ||
470                    getContext().hasSameUnqualifiedType(symIntExpr->getType(),
471                                                        getConditionType()));
472             // Negate the comparison and make a value.
473             opc = BinaryOperator::negateComparisonOp(opc);
474             return makeNonLoc(symIntExpr->getLHS(), opc,
475                 symIntExpr->getRHS(), resultTy);
476           }
477         }
478 
479         // For now, only handle expressions whose RHS is a constant.
480         if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) {
481           // If both the LHS and the current expression are additive,
482           // fold their constants and try again.
483           if (BinaryOperator::isAdditiveOp(op)) {
484             BinaryOperator::Opcode lop = symIntExpr->getOpcode();
485             if (BinaryOperator::isAdditiveOp(lop)) {
486               // Convert the two constants to a common type, then combine them.
487 
488               // resultTy may not be the best type to convert to, but it's
489               // probably the best choice in expressions with mixed type
490               // (such as x+1U+2LL). The rules for implicit conversions should
491               // choose a reasonable type to preserve the expression, and will
492               // at least match how the value is going to be used.
493               APSIntType IntType = BasicVals.getAPSIntType(resultTy);
494               const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS());
495               const llvm::APSInt &second = IntType.convert(*RHSValue);
496 
497               const llvm::APSInt *newRHS;
498               if (lop == op)
499                 newRHS = BasicVals.evalAPSInt(BO_Add, first, second);
500               else
501                 newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);
502 
503               assert(newRHS && "Invalid operation despite common type!");
504               rhs = nonloc::ConcreteInt(*newRHS);
505               lhs = nonloc::SymbolVal(symIntExpr->getLHS());
506               op = lop;
507               continue;
508             }
509           }
510 
511           // Otherwise, make a SymIntExpr out of the expression.
512           return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy);
513         }
514       }
515 
516       // Does the symbolic expression simplify to a constant?
517       // If so, "fold" the constant by setting 'lhs' to a ConcreteInt
518       // and try again.
519       ConstraintManager &CMgr = state->getConstraintManager();
520       if (const llvm::APSInt *Constant = CMgr.getSymVal(state, Sym)) {
521         lhs = nonloc::ConcreteInt(*Constant);
522         continue;
523       }
524 
525       // Is the RHS a constant?
526       if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs))
527         return MakeSymIntVal(Sym, op, *RHSValue, resultTy);
528 
529       // Give up -- this is not a symbolic expression we can handle.
530       return makeSymExprValNN(state, op, InputLHS, InputRHS, resultTy);
531     }
532     }
533   }
534 }
535 
evalBinOpFieldRegionFieldRegion(const FieldRegion * LeftFR,const FieldRegion * RightFR,BinaryOperator::Opcode op,QualType resultTy,SimpleSValBuilder & SVB)536 static SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR,
537                                             const FieldRegion *RightFR,
538                                             BinaryOperator::Opcode op,
539                                             QualType resultTy,
540                                             SimpleSValBuilder &SVB) {
541   // Only comparisons are meaningful here!
542   if (!BinaryOperator::isComparisonOp(op))
543     return UnknownVal();
544 
545   // Next, see if the two FRs have the same super-region.
546   // FIXME: This doesn't handle casts yet, and simply stripping the casts
547   // doesn't help.
548   if (LeftFR->getSuperRegion() != RightFR->getSuperRegion())
549     return UnknownVal();
550 
551   const FieldDecl *LeftFD = LeftFR->getDecl();
552   const FieldDecl *RightFD = RightFR->getDecl();
553   const RecordDecl *RD = LeftFD->getParent();
554 
555   // Make sure the two FRs are from the same kind of record. Just in case!
556   // FIXME: This is probably where inheritance would be a problem.
557   if (RD != RightFD->getParent())
558     return UnknownVal();
559 
560   // We know for sure that the two fields are not the same, since that
561   // would have given us the same SVal.
562   if (op == BO_EQ)
563     return SVB.makeTruthVal(false, resultTy);
564   if (op == BO_NE)
565     return SVB.makeTruthVal(true, resultTy);
566 
567   // Iterate through the fields and see which one comes first.
568   // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field
569   // members and the units in which bit-fields reside have addresses that
570   // increase in the order in which they are declared."
571   bool leftFirst = (op == BO_LT || op == BO_LE);
572   for (const auto *I : RD->fields()) {
573     if (I == LeftFD)
574       return SVB.makeTruthVal(leftFirst, resultTy);
575     if (I == RightFD)
576       return SVB.makeTruthVal(!leftFirst, resultTy);
577   }
578 
579   llvm_unreachable("Fields not found in parent record's definition");
580 }
581 
582 // FIXME: all this logic will change if/when we have MemRegion::getLocation().
evalBinOpLL(ProgramStateRef state,BinaryOperator::Opcode op,Loc lhs,Loc rhs,QualType resultTy)583 SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
584                                   BinaryOperator::Opcode op,
585                                   Loc lhs, Loc rhs,
586                                   QualType resultTy) {
587   // Only comparisons and subtractions are valid operations on two pointers.
588   // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
589   // However, if a pointer is casted to an integer, evalBinOpNN may end up
590   // calling this function with another operation (PR7527). We don't attempt to
591   // model this for now, but it could be useful, particularly when the
592   // "location" is actually an integer value that's been passed through a void*.
593   if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub))
594     return UnknownVal();
595 
596   // Special cases for when both sides are identical.
597   if (lhs == rhs) {
598     switch (op) {
599     default:
600       llvm_unreachable("Unimplemented operation for two identical values");
601     case BO_Sub:
602       return makeZeroVal(resultTy);
603     case BO_EQ:
604     case BO_LE:
605     case BO_GE:
606       return makeTruthVal(true, resultTy);
607     case BO_NE:
608     case BO_LT:
609     case BO_GT:
610       return makeTruthVal(false, resultTy);
611     }
612   }
613 
614   switch (lhs.getSubKind()) {
615   default:
616     llvm_unreachable("Ordering not implemented for this Loc.");
617 
618   case loc::GotoLabelKind:
619     // The only thing we know about labels is that they're non-null.
620     if (rhs.isZeroConstant()) {
621       switch (op) {
622       default:
623         break;
624       case BO_Sub:
625         return evalCastFromLoc(lhs, resultTy);
626       case BO_EQ:
627       case BO_LE:
628       case BO_LT:
629         return makeTruthVal(false, resultTy);
630       case BO_NE:
631       case BO_GT:
632       case BO_GE:
633         return makeTruthVal(true, resultTy);
634       }
635     }
636     // There may be two labels for the same location, and a function region may
637     // have the same address as a label at the start of the function (depending
638     // on the ABI).
639     // FIXME: we can probably do a comparison against other MemRegions, though.
640     // FIXME: is there a way to tell if two labels refer to the same location?
641     return UnknownVal();
642 
643   case loc::ConcreteIntKind: {
644     // If one of the operands is a symbol and the other is a constant,
645     // build an expression for use by the constraint manager.
646     if (SymbolRef rSym = rhs.getAsLocSymbol()) {
647       // We can only build expressions with symbols on the left,
648       // so we need a reversible operator.
649       if (!BinaryOperator::isComparisonOp(op))
650         return UnknownVal();
651 
652       const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue();
653       op = BinaryOperator::reverseComparisonOp(op);
654       return makeNonLoc(rSym, op, lVal, resultTy);
655     }
656 
657     // If both operands are constants, just perform the operation.
658     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
659       SVal ResultVal =
660           lhs.castAs<loc::ConcreteInt>().evalBinOp(BasicVals, op, *rInt);
661       if (Optional<NonLoc> Result = ResultVal.getAs<NonLoc>())
662         return evalCastFromNonLoc(*Result, resultTy);
663 
664       assert(!ResultVal.getAs<Loc>() && "Loc-Loc ops should not produce Locs");
665       return UnknownVal();
666     }
667 
668     // Special case comparisons against NULL.
669     // This must come after the test if the RHS is a symbol, which is used to
670     // build constraints. The address of any non-symbolic region is guaranteed
671     // to be non-NULL, as is any label.
672     assert(rhs.getAs<loc::MemRegionVal>() || rhs.getAs<loc::GotoLabel>());
673     if (lhs.isZeroConstant()) {
674       switch (op) {
675       default:
676         break;
677       case BO_EQ:
678       case BO_GT:
679       case BO_GE:
680         return makeTruthVal(false, resultTy);
681       case BO_NE:
682       case BO_LT:
683       case BO_LE:
684         return makeTruthVal(true, resultTy);
685       }
686     }
687 
688     // Comparing an arbitrary integer to a region or label address is
689     // completely unknowable.
690     return UnknownVal();
691   }
692   case loc::MemRegionValKind: {
693     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
694       // If one of the operands is a symbol and the other is a constant,
695       // build an expression for use by the constraint manager.
696       if (SymbolRef lSym = lhs.getAsLocSymbol(true))
697         return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);
698 
699       // Special case comparisons to NULL.
700       // This must come after the test if the LHS is a symbol, which is used to
701       // build constraints. The address of any non-symbolic region is guaranteed
702       // to be non-NULL.
703       if (rInt->isZeroConstant()) {
704         if (op == BO_Sub)
705           return evalCastFromLoc(lhs, resultTy);
706 
707         if (BinaryOperator::isComparisonOp(op)) {
708           QualType boolType = getContext().BoolTy;
709           NonLoc l = evalCastFromLoc(lhs, boolType).castAs<NonLoc>();
710           NonLoc r = makeTruthVal(false, boolType).castAs<NonLoc>();
711           return evalBinOpNN(state, op, l, r, resultTy);
712         }
713       }
714 
715       // Comparing a region to an arbitrary integer is completely unknowable.
716       return UnknownVal();
717     }
718 
719     // Get both values as regions, if possible.
720     const MemRegion *LeftMR = lhs.getAsRegion();
721     assert(LeftMR && "MemRegionValKind SVal doesn't have a region!");
722 
723     const MemRegion *RightMR = rhs.getAsRegion();
724     if (!RightMR)
725       // The RHS is probably a label, which in theory could address a region.
726       // FIXME: we can probably make a more useful statement about non-code
727       // regions, though.
728       return UnknownVal();
729 
730     const MemRegion *LeftBase = LeftMR->getBaseRegion();
731     const MemRegion *RightBase = RightMR->getBaseRegion();
732     const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace();
733     const MemSpaceRegion *RightMS = RightBase->getMemorySpace();
734     const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion();
735 
736     // If the two regions are from different known memory spaces they cannot be
737     // equal. Also, assume that no symbolic region (whose memory space is
738     // unknown) is on the stack.
739     if (LeftMS != RightMS &&
740         ((LeftMS != UnknownMS && RightMS != UnknownMS) ||
741          (isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) {
742       switch (op) {
743       default:
744         return UnknownVal();
745       case BO_EQ:
746         return makeTruthVal(false, resultTy);
747       case BO_NE:
748         return makeTruthVal(true, resultTy);
749       }
750     }
751 
752     // If both values wrap regions, see if they're from different base regions.
753     // Note, heap base symbolic regions are assumed to not alias with
754     // each other; for example, we assume that malloc returns different address
755     // on each invocation.
756     if (LeftBase != RightBase &&
757         ((!isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) ||
758          (isa<HeapSpaceRegion>(LeftMS) || isa<HeapSpaceRegion>(RightMS))) ){
759       switch (op) {
760       default:
761         return UnknownVal();
762       case BO_EQ:
763         return makeTruthVal(false, resultTy);
764       case BO_NE:
765         return makeTruthVal(true, resultTy);
766       }
767     }
768 
769     // Handle special cases for when both regions are element regions.
770     const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR);
771     const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR);
772     if (RightER && LeftER) {
773       // Next, see if the two ERs have the same super-region and matching types.
774       // FIXME: This should do something useful even if the types don't match,
775       // though if both indexes are constant the RegionRawOffset path will
776       // give the correct answer.
777       if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
778           LeftER->getElementType() == RightER->getElementType()) {
779         // Get the left index and cast it to the correct type.
780         // If the index is unknown or undefined, bail out here.
781         SVal LeftIndexVal = LeftER->getIndex();
782         Optional<NonLoc> LeftIndex = LeftIndexVal.getAs<NonLoc>();
783         if (!LeftIndex)
784           return UnknownVal();
785         LeftIndexVal = evalCastFromNonLoc(*LeftIndex, ArrayIndexTy);
786         LeftIndex = LeftIndexVal.getAs<NonLoc>();
787         if (!LeftIndex)
788           return UnknownVal();
789 
790         // Do the same for the right index.
791         SVal RightIndexVal = RightER->getIndex();
792         Optional<NonLoc> RightIndex = RightIndexVal.getAs<NonLoc>();
793         if (!RightIndex)
794           return UnknownVal();
795         RightIndexVal = evalCastFromNonLoc(*RightIndex, ArrayIndexTy);
796         RightIndex = RightIndexVal.getAs<NonLoc>();
797         if (!RightIndex)
798           return UnknownVal();
799 
800         // Actually perform the operation.
801         // evalBinOpNN expects the two indexes to already be the right type.
802         return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);
803       }
804     }
805 
806     // Special handling of the FieldRegions, even with symbolic offsets.
807     const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR);
808     const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR);
809     if (RightFR && LeftFR) {
810       SVal R = evalBinOpFieldRegionFieldRegion(LeftFR, RightFR, op, resultTy,
811                                                *this);
812       if (!R.isUnknown())
813         return R;
814     }
815 
816     // Compare the regions using the raw offsets.
817     RegionOffset LeftOffset = LeftMR->getAsOffset();
818     RegionOffset RightOffset = RightMR->getAsOffset();
819 
820     if (LeftOffset.getRegion() != nullptr &&
821         LeftOffset.getRegion() == RightOffset.getRegion() &&
822         !LeftOffset.hasSymbolicOffset() && !RightOffset.hasSymbolicOffset()) {
823       int64_t left = LeftOffset.getOffset();
824       int64_t right = RightOffset.getOffset();
825 
826       switch (op) {
827         default:
828           return UnknownVal();
829         case BO_LT:
830           return makeTruthVal(left < right, resultTy);
831         case BO_GT:
832           return makeTruthVal(left > right, resultTy);
833         case BO_LE:
834           return makeTruthVal(left <= right, resultTy);
835         case BO_GE:
836           return makeTruthVal(left >= right, resultTy);
837         case BO_EQ:
838           return makeTruthVal(left == right, resultTy);
839         case BO_NE:
840           return makeTruthVal(left != right, resultTy);
841       }
842     }
843 
844     // At this point we're not going to get a good answer, but we can try
845     // conjuring an expression instead.
846     SymbolRef LHSSym = lhs.getAsLocSymbol();
847     SymbolRef RHSSym = rhs.getAsLocSymbol();
848     if (LHSSym && RHSSym)
849       return makeNonLoc(LHSSym, op, RHSSym, resultTy);
850 
851     // If we get here, we have no way of comparing the regions.
852     return UnknownVal();
853   }
854   }
855 }
856 
evalBinOpLN(ProgramStateRef state,BinaryOperator::Opcode op,Loc lhs,NonLoc rhs,QualType resultTy)857 SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,
858                                   BinaryOperator::Opcode op,
859                                   Loc lhs, NonLoc rhs, QualType resultTy) {
860   assert(!BinaryOperator::isComparisonOp(op) &&
861          "arguments to comparison ops must be of the same type");
862 
863   // Special case: rhs is a zero constant.
864   if (rhs.isZeroConstant())
865     return lhs;
866 
867   // We are dealing with pointer arithmetic.
868 
869   // Handle pointer arithmetic on constant values.
870   if (Optional<nonloc::ConcreteInt> rhsInt = rhs.getAs<nonloc::ConcreteInt>()) {
871     if (Optional<loc::ConcreteInt> lhsInt = lhs.getAs<loc::ConcreteInt>()) {
872       const llvm::APSInt &leftI = lhsInt->getValue();
873       assert(leftI.isUnsigned());
874       llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true);
875 
876       // Convert the bitwidth of rightI.  This should deal with overflow
877       // since we are dealing with concrete values.
878       rightI = rightI.extOrTrunc(leftI.getBitWidth());
879 
880       // Offset the increment by the pointer size.
881       llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true);
882       rightI *= Multiplicand;
883 
884       // Compute the adjusted pointer.
885       switch (op) {
886         case BO_Add:
887           rightI = leftI + rightI;
888           break;
889         case BO_Sub:
890           rightI = leftI - rightI;
891           break;
892         default:
893           llvm_unreachable("Invalid pointer arithmetic operation");
894       }
895       return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));
896     }
897   }
898 
899   // Handle cases where 'lhs' is a region.
900   if (const MemRegion *region = lhs.getAsRegion()) {
901     rhs = convertToArrayIndex(rhs).castAs<NonLoc>();
902     SVal index = UnknownVal();
903     const MemRegion *superR = nullptr;
904     QualType elementType;
905 
906     if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(region)) {
907       assert(op == BO_Add || op == BO_Sub);
908       index = evalBinOpNN(state, op, elemReg->getIndex(), rhs,
909                           getArrayIndexType());
910       superR = elemReg->getSuperRegion();
911       elementType = elemReg->getElementType();
912     }
913     else if (isa<SubRegion>(region)) {
914       assert(op == BO_Add || op == BO_Sub);
915       index = (op == BO_Add) ? rhs : evalMinus(rhs);
916       superR = region;
917       if (resultTy->isAnyPointerType())
918         elementType = resultTy->getPointeeType();
919     }
920 
921     if (Optional<NonLoc> indexV = index.getAs<NonLoc>()) {
922       return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV,
923                                                        superR, getContext()));
924     }
925   }
926   return UnknownVal();
927 }
928 
getKnownValue(ProgramStateRef state,SVal V)929 const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,
930                                                    SVal V) {
931   if (V.isUnknownOrUndef())
932     return nullptr;
933 
934   if (Optional<loc::ConcreteInt> X = V.getAs<loc::ConcreteInt>())
935     return &X->getValue();
936 
937   if (Optional<nonloc::ConcreteInt> X = V.getAs<nonloc::ConcreteInt>())
938     return &X->getValue();
939 
940   if (SymbolRef Sym = V.getAsSymbol())
941     return state->getConstraintManager().getSymVal(state, Sym);
942 
943   // FIXME: Add support for SymExprs.
944   return nullptr;
945 }
946