"Fossies" - the Fresh Open Source Software Archive

Member "cfe-9.0.0.src/lib/StaticAnalyzer/Core/SimpleSValBuilder.cpp" (16 Jul 2019, 51488 Bytes) of package /linux/misc/cfe-9.0.0.src.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "SimpleSValBuilder.cpp": 8.0.1_vs_9.0.0.

    1 // SimpleSValBuilder.cpp - A basic SValBuilder -----------------------*- C++ -*-
    2 //
    3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
    4 // See https://llvm.org/LICENSE.txt for license information.
    5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
    6 //
    7 //===----------------------------------------------------------------------===//
    8 //
    9 //  This file defines SimpleSValBuilder, a basic implementation of SValBuilder.
   10 //
   11 //===----------------------------------------------------------------------===//
   12 
   13 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
   14 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
   15 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
   16 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
   17 #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
   18 #include "clang/StaticAnalyzer/Core/PathSensitive/SValVisitor.h"
   19 
   20 using namespace clang;
   21 using namespace ento;
   22 
   23 namespace {
   24 class SimpleSValBuilder : public SValBuilder {
   25 protected:
   26   SVal dispatchCast(SVal val, QualType castTy) override;
   27   SVal evalCastFromNonLoc(NonLoc val, QualType castTy) override;
   28   SVal evalCastFromLoc(Loc val, QualType castTy) override;
   29 
   30 public:
   31   SimpleSValBuilder(llvm::BumpPtrAllocator &alloc, ASTContext &context,
   32                     ProgramStateManager &stateMgr)
   33                     : SValBuilder(alloc, context, stateMgr) {}
   34   ~SimpleSValBuilder() override {}
   35 
   36   SVal evalMinus(NonLoc val) override;
   37   SVal evalComplement(NonLoc val) override;
   38   SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op,
   39                    NonLoc lhs, NonLoc rhs, QualType resultTy) override;
   40   SVal evalBinOpLL(ProgramStateRef state, BinaryOperator::Opcode op,
   41                    Loc lhs, Loc rhs, QualType resultTy) override;
   42   SVal evalBinOpLN(ProgramStateRef state, BinaryOperator::Opcode op,
   43                    Loc lhs, NonLoc rhs, QualType resultTy) override;
   44 
   45   /// getKnownValue - evaluates a given SVal. If the SVal has only one possible
   46   ///  (integer) value, that value is returned. Otherwise, returns NULL.
   47   const llvm::APSInt *getKnownValue(ProgramStateRef state, SVal V) override;
   48 
   49   /// Recursively descends into symbolic expressions and replaces symbols
   50   /// with their known values (in the sense of the getKnownValue() method).
   51   SVal simplifySVal(ProgramStateRef State, SVal V) override;
   52 
   53   SVal MakeSymIntVal(const SymExpr *LHS, BinaryOperator::Opcode op,
   54                      const llvm::APSInt &RHS, QualType resultTy);
   55 };
   56 } // end anonymous namespace
   57 
   58 SValBuilder *ento::createSimpleSValBuilder(llvm::BumpPtrAllocator &alloc,
   59                                            ASTContext &context,
   60                                            ProgramStateManager &stateMgr) {
   61   return new SimpleSValBuilder(alloc, context, stateMgr);
   62 }
   63 
   64 //===----------------------------------------------------------------------===//
   65 // Transfer function for Casts.
   66 //===----------------------------------------------------------------------===//
   67 
   68 SVal SimpleSValBuilder::dispatchCast(SVal Val, QualType CastTy) {
   69   assert(Val.getAs<Loc>() || Val.getAs<NonLoc>());
   70   return Val.getAs<Loc>() ? evalCastFromLoc(Val.castAs<Loc>(), CastTy)
   71                            : evalCastFromNonLoc(Val.castAs<NonLoc>(), CastTy);
   72 }
   73 
   74 SVal SimpleSValBuilder::evalCastFromNonLoc(NonLoc val, QualType castTy) {
   75   bool isLocType = Loc::isLocType(castTy);
   76   if (val.getAs<nonloc::PointerToMember>())
   77     return val;
   78 
   79   if (Optional<nonloc::LocAsInteger> LI = val.getAs<nonloc::LocAsInteger>()) {
   80     if (isLocType)
   81       return LI->getLoc();
   82     // FIXME: Correctly support promotions/truncations.
   83     unsigned castSize = Context.getIntWidth(castTy);
   84     if (castSize == LI->getNumBits())
   85       return val;
   86     return makeLocAsInteger(LI->getLoc(), castSize);
   87   }
   88 
   89   if (const SymExpr *se = val.getAsSymbolicExpression()) {
   90     QualType T = Context.getCanonicalType(se->getType());
   91     // If types are the same or both are integers, ignore the cast.
   92     // FIXME: Remove this hack when we support symbolic truncation/extension.
   93     // HACK: If both castTy and T are integers, ignore the cast.  This is
   94     // not a permanent solution.  Eventually we want to precisely handle
   95     // extension/truncation of symbolic integers.  This prevents us from losing
   96     // precision when we assign 'x = y' and 'y' is symbolic and x and y are
   97     // different integer types.
   98    if (haveSameType(T, castTy))
   99       return val;
  100 
  101     if (!isLocType)
  102       return makeNonLoc(se, T, castTy);
  103     return UnknownVal();
  104   }
  105 
  106   // If value is a non-integer constant, produce unknown.
  107   if (!val.getAs<nonloc::ConcreteInt>())
  108     return UnknownVal();
  109 
  110   // Handle casts to a boolean type.
  111   if (castTy->isBooleanType()) {
  112     bool b = val.castAs<nonloc::ConcreteInt>().getValue().getBoolValue();
  113     return makeTruthVal(b, castTy);
  114   }
  115 
  116   // Only handle casts from integers to integers - if val is an integer constant
  117   // being cast to a non-integer type, produce unknown.
  118   if (!isLocType && !castTy->isIntegralOrEnumerationType())
  119     return UnknownVal();
  120 
  121   llvm::APSInt i = val.castAs<nonloc::ConcreteInt>().getValue();
  122   BasicVals.getAPSIntType(castTy).apply(i);
  123 
  124   if (isLocType)
  125     return makeIntLocVal(i);
  126   else
  127     return makeIntVal(i);
  128 }
  129 
  130 SVal SimpleSValBuilder::evalCastFromLoc(Loc val, QualType castTy) {
  131 
  132   // Casts from pointers -> pointers, just return the lval.
  133   //
  134   // Casts from pointers -> references, just return the lval.  These
  135   //   can be introduced by the frontend for corner cases, e.g
  136   //   casting from va_list* to __builtin_va_list&.
  137   //
  138   if (Loc::isLocType(castTy) || castTy->isReferenceType())
  139     return val;
  140 
  141   // FIXME: Handle transparent unions where a value can be "transparently"
  142   //  lifted into a union type.
  143   if (castTy->isUnionType())
  144     return UnknownVal();
  145 
  146   // Casting a Loc to a bool will almost always be true,
  147   // unless this is a weak function or a symbolic region.
  148   if (castTy->isBooleanType()) {
  149     switch (val.getSubKind()) {
  150       case loc::MemRegionValKind: {
  151         const MemRegion *R = val.castAs<loc::MemRegionVal>().getRegion();
  152         if (const FunctionCodeRegion *FTR = dyn_cast<FunctionCodeRegion>(R))
  153           if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(FTR->getDecl()))
  154             if (FD->isWeak())
  155               // FIXME: Currently we are using an extent symbol here,
  156               // because there are no generic region address metadata
  157               // symbols to use, only content metadata.
  158               return nonloc::SymbolVal(SymMgr.getExtentSymbol(FTR));
  159 
  160         if (const SymbolicRegion *SymR = R->getSymbolicBase())
  161           return makeNonLoc(SymR->getSymbol(), BO_NE,
  162                             BasicVals.getZeroWithPtrWidth(), castTy);
  163 
  164         // FALL-THROUGH
  165         LLVM_FALLTHROUGH;
  166       }
  167 
  168       case loc::GotoLabelKind:
  169         // Labels and non-symbolic memory regions are always true.
  170         return makeTruthVal(true, castTy);
  171     }
  172   }
  173 
  174   if (castTy->isIntegralOrEnumerationType()) {
  175     unsigned BitWidth = Context.getIntWidth(castTy);
  176 
  177     if (!val.getAs<loc::ConcreteInt>())
  178       return makeLocAsInteger(val, BitWidth);
  179 
  180     llvm::APSInt i = val.castAs<loc::ConcreteInt>().getValue();
  181     BasicVals.getAPSIntType(castTy).apply(i);
  182     return makeIntVal(i);
  183   }
  184 
  185   // All other cases: return 'UnknownVal'.  This includes casting pointers
  186   // to floats, which is probably badness it itself, but this is a good
  187   // intermediate solution until we do something better.
  188   return UnknownVal();
  189 }
  190 
  191 //===----------------------------------------------------------------------===//
  192 // Transfer function for unary operators.
  193 //===----------------------------------------------------------------------===//
  194 
  195 SVal SimpleSValBuilder::evalMinus(NonLoc val) {
  196   switch (val.getSubKind()) {
  197   case nonloc::ConcreteIntKind:
  198     return val.castAs<nonloc::ConcreteInt>().evalMinus(*this);
  199   default:
  200     return UnknownVal();
  201   }
  202 }
  203 
  204 SVal SimpleSValBuilder::evalComplement(NonLoc X) {
  205   switch (X.getSubKind()) {
  206   case nonloc::ConcreteIntKind:
  207     return X.castAs<nonloc::ConcreteInt>().evalComplement(*this);
  208   default:
  209     return UnknownVal();
  210   }
  211 }
  212 
  213 //===----------------------------------------------------------------------===//
  214 // Transfer function for binary operators.
  215 //===----------------------------------------------------------------------===//
  216 
  217 SVal SimpleSValBuilder::MakeSymIntVal(const SymExpr *LHS,
  218                                     BinaryOperator::Opcode op,
  219                                     const llvm::APSInt &RHS,
  220                                     QualType resultTy) {
  221   bool isIdempotent = false;
  222 
  223   // Check for a few special cases with known reductions first.
  224   switch (op) {
  225   default:
  226     // We can't reduce this case; just treat it normally.
  227     break;
  228   case BO_Mul:
  229     // a*0 and a*1
  230     if (RHS == 0)
  231       return makeIntVal(0, resultTy);
  232     else if (RHS == 1)
  233       isIdempotent = true;
  234     break;
  235   case BO_Div:
  236     // a/0 and a/1
  237     if (RHS == 0)
  238       // This is also handled elsewhere.
  239       return UndefinedVal();
  240     else if (RHS == 1)
  241       isIdempotent = true;
  242     break;
  243   case BO_Rem:
  244     // a%0 and a%1
  245     if (RHS == 0)
  246       // This is also handled elsewhere.
  247       return UndefinedVal();
  248     else if (RHS == 1)
  249       return makeIntVal(0, resultTy);
  250     break;
  251   case BO_Add:
  252   case BO_Sub:
  253   case BO_Shl:
  254   case BO_Shr:
  255   case BO_Xor:
  256     // a+0, a-0, a<<0, a>>0, a^0
  257     if (RHS == 0)
  258       isIdempotent = true;
  259     break;
  260   case BO_And:
  261     // a&0 and a&(~0)
  262     if (RHS == 0)
  263       return makeIntVal(0, resultTy);
  264     else if (RHS.isAllOnesValue())
  265       isIdempotent = true;
  266     break;
  267   case BO_Or:
  268     // a|0 and a|(~0)
  269     if (RHS == 0)
  270       isIdempotent = true;
  271     else if (RHS.isAllOnesValue()) {
  272       const llvm::APSInt &Result = BasicVals.Convert(resultTy, RHS);
  273       return nonloc::ConcreteInt(Result);
  274     }
  275     break;
  276   }
  277 
  278   // Idempotent ops (like a*1) can still change the type of an expression.
  279   // Wrap the LHS up in a NonLoc again and let evalCastFromNonLoc do the
  280   // dirty work.
  281   if (isIdempotent)
  282       return evalCastFromNonLoc(nonloc::SymbolVal(LHS), resultTy);
  283 
  284   // If we reach this point, the expression cannot be simplified.
  285   // Make a SymbolVal for the entire expression, after converting the RHS.
  286   const llvm::APSInt *ConvertedRHS = &RHS;
  287   if (BinaryOperator::isComparisonOp(op)) {
  288     // We're looking for a type big enough to compare the symbolic value
  289     // with the given constant.
  290     // FIXME: This is an approximation of Sema::UsualArithmeticConversions.
  291     ASTContext &Ctx = getContext();
  292     QualType SymbolType = LHS->getType();
  293     uint64_t ValWidth = RHS.getBitWidth();
  294     uint64_t TypeWidth = Ctx.getTypeSize(SymbolType);
  295 
  296     if (ValWidth < TypeWidth) {
  297       // If the value is too small, extend it.
  298       ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
  299     } else if (ValWidth == TypeWidth) {
  300       // If the value is signed but the symbol is unsigned, do the comparison
  301       // in unsigned space. [C99 6.3.1.8]
  302       // (For the opposite case, the value is already unsigned.)
  303       if (RHS.isSigned() && !SymbolType->isSignedIntegerOrEnumerationType())
  304         ConvertedRHS = &BasicVals.Convert(SymbolType, RHS);
  305     }
  306   } else
  307     ConvertedRHS = &BasicVals.Convert(resultTy, RHS);
  308 
  309   return makeNonLoc(LHS, op, *ConvertedRHS, resultTy);
  310 }
  311 
  312 // See if Sym is known to be a relation Rel with Bound.
  313 static bool isInRelation(BinaryOperator::Opcode Rel, SymbolRef Sym,
  314                          llvm::APSInt Bound, ProgramStateRef State) {
  315   SValBuilder &SVB = State->getStateManager().getSValBuilder();
  316   SVal Result =
  317       SVB.evalBinOpNN(State, Rel, nonloc::SymbolVal(Sym),
  318                       nonloc::ConcreteInt(Bound), SVB.getConditionType());
  319   if (auto DV = Result.getAs<DefinedSVal>()) {
  320     return !State->assume(*DV, false);
  321   }
  322   return false;
  323 }
  324 
  325 // See if Sym is known to be within [min/4, max/4], where min and max
  326 // are the bounds of the symbol's integral type. With such symbols,
  327 // some manipulations can be performed without the risk of overflow.
  328 // assume() doesn't cause infinite recursion because we should be dealing
  329 // with simpler symbols on every recursive call.
  330 static bool isWithinConstantOverflowBounds(SymbolRef Sym,
  331                                            ProgramStateRef State) {
  332   SValBuilder &SVB = State->getStateManager().getSValBuilder();
  333   BasicValueFactory &BV = SVB.getBasicValueFactory();
  334 
  335   QualType T = Sym->getType();
  336   assert(T->isSignedIntegerOrEnumerationType() &&
  337          "This only works with signed integers!");
  338   APSIntType AT = BV.getAPSIntType(T);
  339 
  340   llvm::APSInt Max = AT.getMaxValue() / AT.getValue(4), Min = -Max;
  341   return isInRelation(BO_LE, Sym, Max, State) &&
  342          isInRelation(BO_GE, Sym, Min, State);
  343 }
  344 
  345 // Same for the concrete integers: see if I is within [min/4, max/4].
  346 static bool isWithinConstantOverflowBounds(llvm::APSInt I) {
  347   APSIntType AT(I);
  348   assert(!AT.isUnsigned() &&
  349          "This only works with signed integers!");
  350 
  351   llvm::APSInt Max = AT.getMaxValue() / AT.getValue(4), Min = -Max;
  352   return (I <= Max) && (I >= -Max);
  353 }
  354 
  355 static std::pair<SymbolRef, llvm::APSInt>
  356 decomposeSymbol(SymbolRef Sym, BasicValueFactory &BV) {
  357   if (const auto *SymInt = dyn_cast<SymIntExpr>(Sym))
  358     if (BinaryOperator::isAdditiveOp(SymInt->getOpcode()))
  359       return std::make_pair(SymInt->getLHS(),
  360                             (SymInt->getOpcode() == BO_Add) ?
  361                             (SymInt->getRHS()) :
  362                             (-SymInt->getRHS()));
  363 
  364   // Fail to decompose: "reduce" the problem to the "$x + 0" case.
  365   return std::make_pair(Sym, BV.getValue(0, Sym->getType()));
  366 }
  367 
  368 // Simplify "(LSym + LInt) Op (RSym + RInt)" assuming all values are of the
  369 // same signed integral type and no overflows occur (which should be checked
  370 // by the caller).
  371 static NonLoc doRearrangeUnchecked(ProgramStateRef State,
  372                                    BinaryOperator::Opcode Op,
  373                                    SymbolRef LSym, llvm::APSInt LInt,
  374                                    SymbolRef RSym, llvm::APSInt RInt) {
  375   SValBuilder &SVB = State->getStateManager().getSValBuilder();
  376   BasicValueFactory &BV = SVB.getBasicValueFactory();
  377   SymbolManager &SymMgr = SVB.getSymbolManager();
  378 
  379   QualType SymTy = LSym->getType();
  380   assert(SymTy == RSym->getType() &&
  381          "Symbols are not of the same type!");
  382   assert(APSIntType(LInt) == BV.getAPSIntType(SymTy) &&
  383          "Integers are not of the same type as symbols!");
  384   assert(APSIntType(RInt) == BV.getAPSIntType(SymTy) &&
  385          "Integers are not of the same type as symbols!");
  386 
  387   QualType ResultTy;
  388   if (BinaryOperator::isComparisonOp(Op))
  389     ResultTy = SVB.getConditionType();
  390   else if (BinaryOperator::isAdditiveOp(Op))
  391     ResultTy = SymTy;
  392   else
  393     llvm_unreachable("Operation not suitable for unchecked rearrangement!");
  394 
  395   // FIXME: Can we use assume() without getting into an infinite recursion?
  396   if (LSym == RSym)
  397     return SVB.evalBinOpNN(State, Op, nonloc::ConcreteInt(LInt),
  398                            nonloc::ConcreteInt(RInt), ResultTy)
  399         .castAs<NonLoc>();
  400 
  401   SymbolRef ResultSym = nullptr;
  402   BinaryOperator::Opcode ResultOp;
  403   llvm::APSInt ResultInt;
  404   if (BinaryOperator::isComparisonOp(Op)) {
  405     // Prefer comparing to a non-negative number.
  406     // FIXME: Maybe it'd be better to have consistency in
  407     // "$x - $y" vs. "$y - $x" because those are solver's keys.
  408     if (LInt > RInt) {
  409       ResultSym = SymMgr.getSymSymExpr(RSym, BO_Sub, LSym, SymTy);
  410       ResultOp = BinaryOperator::reverseComparisonOp(Op);
  411       ResultInt = LInt - RInt; // Opposite order!
  412     } else {
  413       ResultSym = SymMgr.getSymSymExpr(LSym, BO_Sub, RSym, SymTy);
  414       ResultOp = Op;
  415       ResultInt = RInt - LInt; // Opposite order!
  416     }
  417   } else {
  418     ResultSym = SymMgr.getSymSymExpr(LSym, Op, RSym, SymTy);
  419     ResultInt = (Op == BO_Add) ? (LInt + RInt) : (LInt - RInt);
  420     ResultOp = BO_Add;
  421     // Bring back the cosmetic difference.
  422     if (ResultInt < 0) {
  423       ResultInt = -ResultInt;
  424       ResultOp = BO_Sub;
  425     } else if (ResultInt == 0) {
  426       // Shortcut: Simplify "$x + 0" to "$x".
  427       return nonloc::SymbolVal(ResultSym);
  428     }
  429   }
  430   const llvm::APSInt &PersistentResultInt = BV.getValue(ResultInt);
  431   return nonloc::SymbolVal(
  432       SymMgr.getSymIntExpr(ResultSym, ResultOp, PersistentResultInt, ResultTy));
  433 }
  434 
  435 // Rearrange if symbol type matches the result type and if the operator is a
  436 // comparison operator, both symbol and constant must be within constant
  437 // overflow bounds.
  438 static bool shouldRearrange(ProgramStateRef State, BinaryOperator::Opcode Op,
  439                             SymbolRef Sym, llvm::APSInt Int, QualType Ty) {
  440   return Sym->getType() == Ty &&
  441     (!BinaryOperator::isComparisonOp(Op) ||
  442      (isWithinConstantOverflowBounds(Sym, State) &&
  443       isWithinConstantOverflowBounds(Int)));
  444 }
  445 
  446 static Optional<NonLoc> tryRearrange(ProgramStateRef State,
  447                                      BinaryOperator::Opcode Op, NonLoc Lhs,
  448                                      NonLoc Rhs, QualType ResultTy) {
  449   ProgramStateManager &StateMgr = State->getStateManager();
  450   SValBuilder &SVB = StateMgr.getSValBuilder();
  451 
  452   // We expect everything to be of the same type - this type.
  453   QualType SingleTy;
  454 
  455   auto &Opts =
  456     StateMgr.getOwningEngine().getAnalysisManager().getAnalyzerOptions();
  457 
  458   // FIXME: After putting complexity threshold to the symbols we can always
  459   //        rearrange additive operations but rearrange comparisons only if
  460   //        option is set.
  461   if(!Opts.ShouldAggressivelySimplifyBinaryOperation)
  462     return None;
  463 
  464   SymbolRef LSym = Lhs.getAsSymbol();
  465   if (!LSym)
  466     return None;
  467 
  468   if (BinaryOperator::isComparisonOp(Op)) {
  469     SingleTy = LSym->getType();
  470     if (ResultTy != SVB.getConditionType())
  471       return None;
  472     // Initialize SingleTy later with a symbol's type.
  473   } else if (BinaryOperator::isAdditiveOp(Op)) {
  474     SingleTy = ResultTy;
  475     if (LSym->getType() != SingleTy)
  476       return None;
  477   } else {
  478     // Don't rearrange other operations.
  479     return None;
  480   }
  481 
  482   assert(!SingleTy.isNull() && "We should have figured out the type by now!");
  483 
  484   // Rearrange signed symbolic expressions only
  485   if (!SingleTy->isSignedIntegerOrEnumerationType())
  486     return None;
  487 
  488   SymbolRef RSym = Rhs.getAsSymbol();
  489   if (!RSym || RSym->getType() != SingleTy)
  490     return None;
  491 
  492   BasicValueFactory &BV = State->getBasicVals();
  493   llvm::APSInt LInt, RInt;
  494   std::tie(LSym, LInt) = decomposeSymbol(LSym, BV);
  495   std::tie(RSym, RInt) = decomposeSymbol(RSym, BV);
  496   if (!shouldRearrange(State, Op, LSym, LInt, SingleTy) ||
  497       !shouldRearrange(State, Op, RSym, RInt, SingleTy))
  498     return None;
  499 
  500   // We know that no overflows can occur anymore.
  501   return doRearrangeUnchecked(State, Op, LSym, LInt, RSym, RInt);
  502 }
  503 
  504 SVal SimpleSValBuilder::evalBinOpNN(ProgramStateRef state,
  505                                   BinaryOperator::Opcode op,
  506                                   NonLoc lhs, NonLoc rhs,
  507                                   QualType resultTy)  {
  508   NonLoc InputLHS = lhs;
  509   NonLoc InputRHS = rhs;
  510 
  511   // Handle trivial case where left-side and right-side are the same.
  512   if (lhs == rhs)
  513     switch (op) {
  514       default:
  515         break;
  516       case BO_EQ:
  517       case BO_LE:
  518       case BO_GE:
  519         return makeTruthVal(true, resultTy);
  520       case BO_LT:
  521       case BO_GT:
  522       case BO_NE:
  523         return makeTruthVal(false, resultTy);
  524       case BO_Xor:
  525       case BO_Sub:
  526         if (resultTy->isIntegralOrEnumerationType())
  527           return makeIntVal(0, resultTy);
  528         return evalCastFromNonLoc(makeIntVal(0, /*isUnsigned=*/false), resultTy);
  529       case BO_Or:
  530       case BO_And:
  531         return evalCastFromNonLoc(lhs, resultTy);
  532     }
  533 
  534   while (1) {
  535     switch (lhs.getSubKind()) {
  536     default:
  537       return makeSymExprValNN(op, lhs, rhs, resultTy);
  538     case nonloc::PointerToMemberKind: {
  539       assert(rhs.getSubKind() == nonloc::PointerToMemberKind &&
  540              "Both SVals should have pointer-to-member-type");
  541       auto LPTM = lhs.castAs<nonloc::PointerToMember>(),
  542            RPTM = rhs.castAs<nonloc::PointerToMember>();
  543       auto LPTMD = LPTM.getPTMData(), RPTMD = RPTM.getPTMData();
  544       switch (op) {
  545         case BO_EQ:
  546           return makeTruthVal(LPTMD == RPTMD, resultTy);
  547         case BO_NE:
  548           return makeTruthVal(LPTMD != RPTMD, resultTy);
  549         default:
  550           return UnknownVal();
  551       }
  552     }
  553     case nonloc::LocAsIntegerKind: {
  554       Loc lhsL = lhs.castAs<nonloc::LocAsInteger>().getLoc();
  555       switch (rhs.getSubKind()) {
  556         case nonloc::LocAsIntegerKind:
  557           // FIXME: at the moment the implementation
  558           // of modeling "pointers as integers" is not complete.
  559           if (!BinaryOperator::isComparisonOp(op))
  560             return UnknownVal();
  561           return evalBinOpLL(state, op, lhsL,
  562                              rhs.castAs<nonloc::LocAsInteger>().getLoc(),
  563                              resultTy);
  564         case nonloc::ConcreteIntKind: {
  565           // FIXME: at the moment the implementation
  566           // of modeling "pointers as integers" is not complete.
  567           if (!BinaryOperator::isComparisonOp(op))
  568             return UnknownVal();
  569           // Transform the integer into a location and compare.
  570           // FIXME: This only makes sense for comparisons. If we want to, say,
  571           // add 1 to a LocAsInteger, we'd better unpack the Loc and add to it,
  572           // then pack it back into a LocAsInteger.
  573           llvm::APSInt i = rhs.castAs<nonloc::ConcreteInt>().getValue();
  574           // If the region has a symbolic base, pay attention to the type; it
  575           // might be coming from a non-default address space. For non-symbolic
  576           // regions it doesn't matter that much because such comparisons would
  577           // most likely evaluate to concrete false anyway. FIXME: We might
  578           // still need to handle the non-comparison case.
  579           if (SymbolRef lSym = lhs.getAsLocSymbol(true))
  580             BasicVals.getAPSIntType(lSym->getType()).apply(i);
  581           else
  582             BasicVals.getAPSIntType(Context.VoidPtrTy).apply(i);
  583           return evalBinOpLL(state, op, lhsL, makeLoc(i), resultTy);
  584         }
  585         default:
  586           switch (op) {
  587             case BO_EQ:
  588               return makeTruthVal(false, resultTy);
  589             case BO_NE:
  590               return makeTruthVal(true, resultTy);
  591             default:
  592               // This case also handles pointer arithmetic.
  593               return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
  594           }
  595       }
  596     }
  597     case nonloc::ConcreteIntKind: {
  598       llvm::APSInt LHSValue = lhs.castAs<nonloc::ConcreteInt>().getValue();
  599 
  600       // If we're dealing with two known constants, just perform the operation.
  601       if (const llvm::APSInt *KnownRHSValue = getKnownValue(state, rhs)) {
  602         llvm::APSInt RHSValue = *KnownRHSValue;
  603         if (BinaryOperator::isComparisonOp(op)) {
  604           // We're looking for a type big enough to compare the two values.
  605           // FIXME: This is not correct. char + short will result in a promotion
  606           // to int. Unfortunately we have lost types by this point.
  607           APSIntType CompareType = std::max(APSIntType(LHSValue),
  608                                             APSIntType(RHSValue));
  609           CompareType.apply(LHSValue);
  610           CompareType.apply(RHSValue);
  611         } else if (!BinaryOperator::isShiftOp(op)) {
  612           APSIntType IntType = BasicVals.getAPSIntType(resultTy);
  613           IntType.apply(LHSValue);
  614           IntType.apply(RHSValue);
  615         }
  616 
  617         const llvm::APSInt *Result =
  618           BasicVals.evalAPSInt(op, LHSValue, RHSValue);
  619         if (!Result)
  620           return UndefinedVal();
  621 
  622         return nonloc::ConcreteInt(*Result);
  623       }
  624 
  625       // Swap the left and right sides and flip the operator if doing so
  626       // allows us to better reason about the expression (this is a form
  627       // of expression canonicalization).
  628       // While we're at it, catch some special cases for non-commutative ops.
  629       switch (op) {
  630       case BO_LT:
  631       case BO_GT:
  632       case BO_LE:
  633       case BO_GE:
  634         op = BinaryOperator::reverseComparisonOp(op);
  635         LLVM_FALLTHROUGH;
  636       case BO_EQ:
  637       case BO_NE:
  638       case BO_Add:
  639       case BO_Mul:
  640       case BO_And:
  641       case BO_Xor:
  642       case BO_Or:
  643         std::swap(lhs, rhs);
  644         continue;
  645       case BO_Shr:
  646         // (~0)>>a
  647         if (LHSValue.isAllOnesValue() && LHSValue.isSigned())
  648           return evalCastFromNonLoc(lhs, resultTy);
  649         LLVM_FALLTHROUGH;
  650       case BO_Shl:
  651         // 0<<a and 0>>a
  652         if (LHSValue == 0)
  653           return evalCastFromNonLoc(lhs, resultTy);
  654         return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
  655       default:
  656         return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
  657       }
  658     }
  659     case nonloc::SymbolValKind: {
  660       // We only handle LHS as simple symbols or SymIntExprs.
  661       SymbolRef Sym = lhs.castAs<nonloc::SymbolVal>().getSymbol();
  662 
  663       // LHS is a symbolic expression.
  664       if (const SymIntExpr *symIntExpr = dyn_cast<SymIntExpr>(Sym)) {
  665 
  666         // Is this a logical not? (!x is represented as x == 0.)
  667         if (op == BO_EQ && rhs.isZeroConstant()) {
  668           // We know how to negate certain expressions. Simplify them here.
  669 
  670           BinaryOperator::Opcode opc = symIntExpr->getOpcode();
  671           switch (opc) {
  672           default:
  673             // We don't know how to negate this operation.
  674             // Just handle it as if it were a normal comparison to 0.
  675             break;
  676           case BO_LAnd:
  677           case BO_LOr:
  678             llvm_unreachable("Logical operators handled by branching logic.");
  679           case BO_Assign:
  680           case BO_MulAssign:
  681           case BO_DivAssign:
  682           case BO_RemAssign:
  683           case BO_AddAssign:
  684           case BO_SubAssign:
  685           case BO_ShlAssign:
  686           case BO_ShrAssign:
  687           case BO_AndAssign:
  688           case BO_XorAssign:
  689           case BO_OrAssign:
  690           case BO_Comma:
  691             llvm_unreachable("'=' and ',' operators handled by ExprEngine.");
  692           case BO_PtrMemD:
  693           case BO_PtrMemI:
  694             llvm_unreachable("Pointer arithmetic not handled here.");
  695           case BO_LT:
  696           case BO_GT:
  697           case BO_LE:
  698           case BO_GE:
  699           case BO_EQ:
  700           case BO_NE:
  701             assert(resultTy->isBooleanType() ||
  702                    resultTy == getConditionType());
  703             assert(symIntExpr->getType()->isBooleanType() ||
  704                    getContext().hasSameUnqualifiedType(symIntExpr->getType(),
  705                                                        getConditionType()));
  706             // Negate the comparison and make a value.
  707             opc = BinaryOperator::negateComparisonOp(opc);
  708             return makeNonLoc(symIntExpr->getLHS(), opc,
  709                 symIntExpr->getRHS(), resultTy);
  710           }
  711         }
  712 
  713         // For now, only handle expressions whose RHS is a constant.
  714         if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs)) {
  715           // If both the LHS and the current expression are additive,
  716           // fold their constants and try again.
  717           if (BinaryOperator::isAdditiveOp(op)) {
  718             BinaryOperator::Opcode lop = symIntExpr->getOpcode();
  719             if (BinaryOperator::isAdditiveOp(lop)) {
  720               // Convert the two constants to a common type, then combine them.
  721 
  722               // resultTy may not be the best type to convert to, but it's
  723               // probably the best choice in expressions with mixed type
  724               // (such as x+1U+2LL). The rules for implicit conversions should
  725               // choose a reasonable type to preserve the expression, and will
  726               // at least match how the value is going to be used.
  727               APSIntType IntType = BasicVals.getAPSIntType(resultTy);
  728               const llvm::APSInt &first = IntType.convert(symIntExpr->getRHS());
  729               const llvm::APSInt &second = IntType.convert(*RHSValue);
  730 
  731               const llvm::APSInt *newRHS;
  732               if (lop == op)
  733                 newRHS = BasicVals.evalAPSInt(BO_Add, first, second);
  734               else
  735                 newRHS = BasicVals.evalAPSInt(BO_Sub, first, second);
  736 
  737               assert(newRHS && "Invalid operation despite common type!");
  738               rhs = nonloc::ConcreteInt(*newRHS);
  739               lhs = nonloc::SymbolVal(symIntExpr->getLHS());
  740               op = lop;
  741               continue;
  742             }
  743           }
  744 
  745           // Otherwise, make a SymIntExpr out of the expression.
  746           return MakeSymIntVal(symIntExpr, op, *RHSValue, resultTy);
  747         }
  748       }
  749 
  750       // Does the symbolic expression simplify to a constant?
  751       // If so, "fold" the constant by setting 'lhs' to a ConcreteInt
  752       // and try again.
  753       SVal simplifiedLhs = simplifySVal(state, lhs);
  754       if (simplifiedLhs != lhs)
  755         if (auto simplifiedLhsAsNonLoc = simplifiedLhs.getAs<NonLoc>()) {
  756           lhs = *simplifiedLhsAsNonLoc;
  757           continue;
  758         }
  759 
  760       // Is the RHS a constant?
  761       if (const llvm::APSInt *RHSValue = getKnownValue(state, rhs))
  762         return MakeSymIntVal(Sym, op, *RHSValue, resultTy);
  763 
  764       if (Optional<NonLoc> V = tryRearrange(state, op, lhs, rhs, resultTy))
  765         return *V;
  766 
  767       // Give up -- this is not a symbolic expression we can handle.
  768       return makeSymExprValNN(op, InputLHS, InputRHS, resultTy);
  769     }
  770     }
  771   }
  772 }
  773 
  774 static SVal evalBinOpFieldRegionFieldRegion(const FieldRegion *LeftFR,
  775                                             const FieldRegion *RightFR,
  776                                             BinaryOperator::Opcode op,
  777                                             QualType resultTy,
  778                                             SimpleSValBuilder &SVB) {
  779   // Only comparisons are meaningful here!
  780   if (!BinaryOperator::isComparisonOp(op))
  781     return UnknownVal();
  782 
  783   // Next, see if the two FRs have the same super-region.
  784   // FIXME: This doesn't handle casts yet, and simply stripping the casts
  785   // doesn't help.
  786   if (LeftFR->getSuperRegion() != RightFR->getSuperRegion())
  787     return UnknownVal();
  788 
  789   const FieldDecl *LeftFD = LeftFR->getDecl();
  790   const FieldDecl *RightFD = RightFR->getDecl();
  791   const RecordDecl *RD = LeftFD->getParent();
  792 
  793   // Make sure the two FRs are from the same kind of record. Just in case!
  794   // FIXME: This is probably where inheritance would be a problem.
  795   if (RD != RightFD->getParent())
  796     return UnknownVal();
  797 
  798   // We know for sure that the two fields are not the same, since that
  799   // would have given us the same SVal.
  800   if (op == BO_EQ)
  801     return SVB.makeTruthVal(false, resultTy);
  802   if (op == BO_NE)
  803     return SVB.makeTruthVal(true, resultTy);
  804 
  805   // Iterate through the fields and see which one comes first.
  806   // [C99 6.7.2.1.13] "Within a structure object, the non-bit-field
  807   // members and the units in which bit-fields reside have addresses that
  808   // increase in the order in which they are declared."
  809   bool leftFirst = (op == BO_LT || op == BO_LE);
  810   for (const auto *I : RD->fields()) {
  811     if (I == LeftFD)
  812       return SVB.makeTruthVal(leftFirst, resultTy);
  813     if (I == RightFD)
  814       return SVB.makeTruthVal(!leftFirst, resultTy);
  815   }
  816 
  817   llvm_unreachable("Fields not found in parent record's definition");
  818 }
  819 
  820 // FIXME: all this logic will change if/when we have MemRegion::getLocation().
  821 SVal SimpleSValBuilder::evalBinOpLL(ProgramStateRef state,
  822                                   BinaryOperator::Opcode op,
  823                                   Loc lhs, Loc rhs,
  824                                   QualType resultTy) {
  825   // Only comparisons and subtractions are valid operations on two pointers.
  826   // See [C99 6.5.5 through 6.5.14] or [C++0x 5.6 through 5.15].
  827   // However, if a pointer is casted to an integer, evalBinOpNN may end up
  828   // calling this function with another operation (PR7527). We don't attempt to
  829   // model this for now, but it could be useful, particularly when the
  830   // "location" is actually an integer value that's been passed through a void*.
  831   if (!(BinaryOperator::isComparisonOp(op) || op == BO_Sub))
  832     return UnknownVal();
  833 
  834   // Special cases for when both sides are identical.
  835   if (lhs == rhs) {
  836     switch (op) {
  837     default:
  838       llvm_unreachable("Unimplemented operation for two identical values");
  839     case BO_Sub:
  840       return makeZeroVal(resultTy);
  841     case BO_EQ:
  842     case BO_LE:
  843     case BO_GE:
  844       return makeTruthVal(true, resultTy);
  845     case BO_NE:
  846     case BO_LT:
  847     case BO_GT:
  848       return makeTruthVal(false, resultTy);
  849     }
  850   }
  851 
  852   switch (lhs.getSubKind()) {
  853   default:
  854     llvm_unreachable("Ordering not implemented for this Loc.");
  855 
  856   case loc::GotoLabelKind:
  857     // The only thing we know about labels is that they're non-null.
  858     if (rhs.isZeroConstant()) {
  859       switch (op) {
  860       default:
  861         break;
  862       case BO_Sub:
  863         return evalCastFromLoc(lhs, resultTy);
  864       case BO_EQ:
  865       case BO_LE:
  866       case BO_LT:
  867         return makeTruthVal(false, resultTy);
  868       case BO_NE:
  869       case BO_GT:
  870       case BO_GE:
  871         return makeTruthVal(true, resultTy);
  872       }
  873     }
  874     // There may be two labels for the same location, and a function region may
  875     // have the same address as a label at the start of the function (depending
  876     // on the ABI).
  877     // FIXME: we can probably do a comparison against other MemRegions, though.
  878     // FIXME: is there a way to tell if two labels refer to the same location?
  879     return UnknownVal();
  880 
  881   case loc::ConcreteIntKind: {
  882     // If one of the operands is a symbol and the other is a constant,
  883     // build an expression for use by the constraint manager.
  884     if (SymbolRef rSym = rhs.getAsLocSymbol()) {
  885       // We can only build expressions with symbols on the left,
  886       // so we need a reversible operator.
  887       if (!BinaryOperator::isComparisonOp(op) || op == BO_Cmp)
  888         return UnknownVal();
  889 
  890       const llvm::APSInt &lVal = lhs.castAs<loc::ConcreteInt>().getValue();
  891       op = BinaryOperator::reverseComparisonOp(op);
  892       return makeNonLoc(rSym, op, lVal, resultTy);
  893     }
  894 
  895     // If both operands are constants, just perform the operation.
  896     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
  897       SVal ResultVal =
  898           lhs.castAs<loc::ConcreteInt>().evalBinOp(BasicVals, op, *rInt);
  899       if (Optional<NonLoc> Result = ResultVal.getAs<NonLoc>())
  900         return evalCastFromNonLoc(*Result, resultTy);
  901 
  902       assert(!ResultVal.getAs<Loc>() && "Loc-Loc ops should not produce Locs");
  903       return UnknownVal();
  904     }
  905 
  906     // Special case comparisons against NULL.
  907     // This must come after the test if the RHS is a symbol, which is used to
  908     // build constraints. The address of any non-symbolic region is guaranteed
  909     // to be non-NULL, as is any label.
  910     assert(rhs.getAs<loc::MemRegionVal>() || rhs.getAs<loc::GotoLabel>());
  911     if (lhs.isZeroConstant()) {
  912       switch (op) {
  913       default:
  914         break;
  915       case BO_EQ:
  916       case BO_GT:
  917       case BO_GE:
  918         return makeTruthVal(false, resultTy);
  919       case BO_NE:
  920       case BO_LT:
  921       case BO_LE:
  922         return makeTruthVal(true, resultTy);
  923       }
  924     }
  925 
  926     // Comparing an arbitrary integer to a region or label address is
  927     // completely unknowable.
  928     return UnknownVal();
  929   }
  930   case loc::MemRegionValKind: {
  931     if (Optional<loc::ConcreteInt> rInt = rhs.getAs<loc::ConcreteInt>()) {
  932       // If one of the operands is a symbol and the other is a constant,
  933       // build an expression for use by the constraint manager.
  934       if (SymbolRef lSym = lhs.getAsLocSymbol(true)) {
  935         if (BinaryOperator::isComparisonOp(op))
  936           return MakeSymIntVal(lSym, op, rInt->getValue(), resultTy);
  937         return UnknownVal();
  938       }
  939       // Special case comparisons to NULL.
  940       // This must come after the test if the LHS is a symbol, which is used to
  941       // build constraints. The address of any non-symbolic region is guaranteed
  942       // to be non-NULL.
  943       if (rInt->isZeroConstant()) {
  944         if (op == BO_Sub)
  945           return evalCastFromLoc(lhs, resultTy);
  946 
  947         if (BinaryOperator::isComparisonOp(op)) {
  948           QualType boolType = getContext().BoolTy;
  949           NonLoc l = evalCastFromLoc(lhs, boolType).castAs<NonLoc>();
  950           NonLoc r = makeTruthVal(false, boolType).castAs<NonLoc>();
  951           return evalBinOpNN(state, op, l, r, resultTy);
  952         }
  953       }
  954 
  955       // Comparing a region to an arbitrary integer is completely unknowable.
  956       return UnknownVal();
  957     }
  958 
  959     // Get both values as regions, if possible.
  960     const MemRegion *LeftMR = lhs.getAsRegion();
  961     assert(LeftMR && "MemRegionValKind SVal doesn't have a region!");
  962 
  963     const MemRegion *RightMR = rhs.getAsRegion();
  964     if (!RightMR)
  965       // The RHS is probably a label, which in theory could address a region.
  966       // FIXME: we can probably make a more useful statement about non-code
  967       // regions, though.
  968       return UnknownVal();
  969 
  970     const MemRegion *LeftBase = LeftMR->getBaseRegion();
  971     const MemRegion *RightBase = RightMR->getBaseRegion();
  972     const MemSpaceRegion *LeftMS = LeftBase->getMemorySpace();
  973     const MemSpaceRegion *RightMS = RightBase->getMemorySpace();
  974     const MemSpaceRegion *UnknownMS = MemMgr.getUnknownRegion();
  975 
  976     // If the two regions are from different known memory spaces they cannot be
  977     // equal. Also, assume that no symbolic region (whose memory space is
  978     // unknown) is on the stack.
  979     if (LeftMS != RightMS &&
  980         ((LeftMS != UnknownMS && RightMS != UnknownMS) ||
  981          (isa<StackSpaceRegion>(LeftMS) || isa<StackSpaceRegion>(RightMS)))) {
  982       switch (op) {
  983       default:
  984         return UnknownVal();
  985       case BO_EQ:
  986         return makeTruthVal(false, resultTy);
  987       case BO_NE:
  988         return makeTruthVal(true, resultTy);
  989       }
  990     }
  991 
  992     // If both values wrap regions, see if they're from different base regions.
  993     // Note, heap base symbolic regions are assumed to not alias with
  994     // each other; for example, we assume that malloc returns different address
  995     // on each invocation.
  996     // FIXME: ObjC object pointers always reside on the heap, but currently
  997     // we treat their memory space as unknown, because symbolic pointers
  998     // to ObjC objects may alias. There should be a way to construct
  999     // possibly-aliasing heap-based regions. For instance, MacOSXApiChecker
 1000     // guesses memory space for ObjC object pointers manually instead of
 1001     // relying on us.
 1002     if (LeftBase != RightBase &&
 1003         ((!isa<SymbolicRegion>(LeftBase) && !isa<SymbolicRegion>(RightBase)) ||
 1004          (isa<HeapSpaceRegion>(LeftMS) || isa<HeapSpaceRegion>(RightMS))) ){
 1005       switch (op) {
 1006       default:
 1007         return UnknownVal();
 1008       case BO_EQ:
 1009         return makeTruthVal(false, resultTy);
 1010       case BO_NE:
 1011         return makeTruthVal(true, resultTy);
 1012       }
 1013     }
 1014 
 1015     // Handle special cases for when both regions are element regions.
 1016     const ElementRegion *RightER = dyn_cast<ElementRegion>(RightMR);
 1017     const ElementRegion *LeftER = dyn_cast<ElementRegion>(LeftMR);
 1018     if (RightER && LeftER) {
 1019       // Next, see if the two ERs have the same super-region and matching types.
 1020       // FIXME: This should do something useful even if the types don't match,
 1021       // though if both indexes are constant the RegionRawOffset path will
 1022       // give the correct answer.
 1023       if (LeftER->getSuperRegion() == RightER->getSuperRegion() &&
 1024           LeftER->getElementType() == RightER->getElementType()) {
 1025         // Get the left index and cast it to the correct type.
 1026         // If the index is unknown or undefined, bail out here.
 1027         SVal LeftIndexVal = LeftER->getIndex();
 1028         Optional<NonLoc> LeftIndex = LeftIndexVal.getAs<NonLoc>();
 1029         if (!LeftIndex)
 1030           return UnknownVal();
 1031         LeftIndexVal = evalCastFromNonLoc(*LeftIndex, ArrayIndexTy);
 1032         LeftIndex = LeftIndexVal.getAs<NonLoc>();
 1033         if (!LeftIndex)
 1034           return UnknownVal();
 1035 
 1036         // Do the same for the right index.
 1037         SVal RightIndexVal = RightER->getIndex();
 1038         Optional<NonLoc> RightIndex = RightIndexVal.getAs<NonLoc>();
 1039         if (!RightIndex)
 1040           return UnknownVal();
 1041         RightIndexVal = evalCastFromNonLoc(*RightIndex, ArrayIndexTy);
 1042         RightIndex = RightIndexVal.getAs<NonLoc>();
 1043         if (!RightIndex)
 1044           return UnknownVal();
 1045 
 1046         // Actually perform the operation.
 1047         // evalBinOpNN expects the two indexes to already be the right type.
 1048         return evalBinOpNN(state, op, *LeftIndex, *RightIndex, resultTy);
 1049       }
 1050     }
 1051 
 1052     // Special handling of the FieldRegions, even with symbolic offsets.
 1053     const FieldRegion *RightFR = dyn_cast<FieldRegion>(RightMR);
 1054     const FieldRegion *LeftFR = dyn_cast<FieldRegion>(LeftMR);
 1055     if (RightFR && LeftFR) {
 1056       SVal R = evalBinOpFieldRegionFieldRegion(LeftFR, RightFR, op, resultTy,
 1057                                                *this);
 1058       if (!R.isUnknown())
 1059         return R;
 1060     }
 1061 
 1062     // Compare the regions using the raw offsets.
 1063     RegionOffset LeftOffset = LeftMR->getAsOffset();
 1064     RegionOffset RightOffset = RightMR->getAsOffset();
 1065 
 1066     if (LeftOffset.getRegion() != nullptr &&
 1067         LeftOffset.getRegion() == RightOffset.getRegion() &&
 1068         !LeftOffset.hasSymbolicOffset() && !RightOffset.hasSymbolicOffset()) {
 1069       int64_t left = LeftOffset.getOffset();
 1070       int64_t right = RightOffset.getOffset();
 1071 
 1072       switch (op) {
 1073         default:
 1074           return UnknownVal();
 1075         case BO_LT:
 1076           return makeTruthVal(left < right, resultTy);
 1077         case BO_GT:
 1078           return makeTruthVal(left > right, resultTy);
 1079         case BO_LE:
 1080           return makeTruthVal(left <= right, resultTy);
 1081         case BO_GE:
 1082           return makeTruthVal(left >= right, resultTy);
 1083         case BO_EQ:
 1084           return makeTruthVal(left == right, resultTy);
 1085         case BO_NE:
 1086           return makeTruthVal(left != right, resultTy);
 1087       }
 1088     }
 1089 
 1090     // At this point we're not going to get a good answer, but we can try
 1091     // conjuring an expression instead.
 1092     SymbolRef LHSSym = lhs.getAsLocSymbol();
 1093     SymbolRef RHSSym = rhs.getAsLocSymbol();
 1094     if (LHSSym && RHSSym)
 1095       return makeNonLoc(LHSSym, op, RHSSym, resultTy);
 1096 
 1097     // If we get here, we have no way of comparing the regions.
 1098     return UnknownVal();
 1099   }
 1100   }
 1101 }
 1102 
 1103 SVal SimpleSValBuilder::evalBinOpLN(ProgramStateRef state,
 1104                                   BinaryOperator::Opcode op,
 1105                                   Loc lhs, NonLoc rhs, QualType resultTy) {
 1106   if (op >= BO_PtrMemD && op <= BO_PtrMemI) {
 1107     if (auto PTMSV = rhs.getAs<nonloc::PointerToMember>()) {
 1108       if (PTMSV->isNullMemberPointer())
 1109         return UndefinedVal();
 1110       if (const FieldDecl *FD = PTMSV->getDeclAs<FieldDecl>()) {
 1111         SVal Result = lhs;
 1112 
 1113         for (const auto &I : *PTMSV)
 1114           Result = StateMgr.getStoreManager().evalDerivedToBase(
 1115               Result, I->getType(),I->isVirtual());
 1116         return state->getLValue(FD, Result);
 1117       }
 1118     }
 1119 
 1120     return rhs;
 1121   }
 1122 
 1123   assert(!BinaryOperator::isComparisonOp(op) &&
 1124          "arguments to comparison ops must be of the same type");
 1125 
 1126   // Special case: rhs is a zero constant.
 1127   if (rhs.isZeroConstant())
 1128     return lhs;
 1129 
 1130   // Perserve the null pointer so that it can be found by the DerefChecker.
 1131   if (lhs.isZeroConstant())
 1132     return lhs;
 1133 
 1134   // We are dealing with pointer arithmetic.
 1135 
 1136   // Handle pointer arithmetic on constant values.
 1137   if (Optional<nonloc::ConcreteInt> rhsInt = rhs.getAs<nonloc::ConcreteInt>()) {
 1138     if (Optional<loc::ConcreteInt> lhsInt = lhs.getAs<loc::ConcreteInt>()) {
 1139       const llvm::APSInt &leftI = lhsInt->getValue();
 1140       assert(leftI.isUnsigned());
 1141       llvm::APSInt rightI(rhsInt->getValue(), /* isUnsigned */ true);
 1142 
 1143       // Convert the bitwidth of rightI.  This should deal with overflow
 1144       // since we are dealing with concrete values.
 1145       rightI = rightI.extOrTrunc(leftI.getBitWidth());
 1146 
 1147       // Offset the increment by the pointer size.
 1148       llvm::APSInt Multiplicand(rightI.getBitWidth(), /* isUnsigned */ true);
 1149       QualType pointeeType = resultTy->getPointeeType();
 1150       Multiplicand = getContext().getTypeSizeInChars(pointeeType).getQuantity();
 1151       rightI *= Multiplicand;
 1152 
 1153       // Compute the adjusted pointer.
 1154       switch (op) {
 1155         case BO_Add:
 1156           rightI = leftI + rightI;
 1157           break;
 1158         case BO_Sub:
 1159           rightI = leftI - rightI;
 1160           break;
 1161         default:
 1162           llvm_unreachable("Invalid pointer arithmetic operation");
 1163       }
 1164       return loc::ConcreteInt(getBasicValueFactory().getValue(rightI));
 1165     }
 1166   }
 1167 
 1168   // Handle cases where 'lhs' is a region.
 1169   if (const MemRegion *region = lhs.getAsRegion()) {
 1170     rhs = convertToArrayIndex(rhs).castAs<NonLoc>();
 1171     SVal index = UnknownVal();
 1172     const SubRegion *superR = nullptr;
 1173     // We need to know the type of the pointer in order to add an integer to it.
 1174     // Depending on the type, different amount of bytes is added.
 1175     QualType elementType;
 1176 
 1177     if (const ElementRegion *elemReg = dyn_cast<ElementRegion>(region)) {
 1178       assert(op == BO_Add || op == BO_Sub);
 1179       index = evalBinOpNN(state, op, elemReg->getIndex(), rhs,
 1180                           getArrayIndexType());
 1181       superR = cast<SubRegion>(elemReg->getSuperRegion());
 1182       elementType = elemReg->getElementType();
 1183     }
 1184     else if (isa<SubRegion>(region)) {
 1185       assert(op == BO_Add || op == BO_Sub);
 1186       index = (op == BO_Add) ? rhs : evalMinus(rhs);
 1187       superR = cast<SubRegion>(region);
 1188       // TODO: Is this actually reliable? Maybe improving our MemRegion
 1189       // hierarchy to provide typed regions for all non-void pointers would be
 1190       // better. For instance, we cannot extend this towards LocAsInteger
 1191       // operations, where result type of the expression is integer.
 1192       if (resultTy->isAnyPointerType())
 1193         elementType = resultTy->getPointeeType();
 1194     }
 1195 
 1196     // Represent arithmetic on void pointers as arithmetic on char pointers.
 1197     // It is fine when a TypedValueRegion of char value type represents
 1198     // a void pointer. Note that arithmetic on void pointers is a GCC extension.
 1199     if (elementType->isVoidType())
 1200       elementType = getContext().CharTy;
 1201 
 1202     if (Optional<NonLoc> indexV = index.getAs<NonLoc>()) {
 1203       return loc::MemRegionVal(MemMgr.getElementRegion(elementType, *indexV,
 1204                                                        superR, getContext()));
 1205     }
 1206   }
 1207   return UnknownVal();
 1208 }
 1209 
 1210 const llvm::APSInt *SimpleSValBuilder::getKnownValue(ProgramStateRef state,
 1211                                                    SVal V) {
 1212   V = simplifySVal(state, V);
 1213   if (V.isUnknownOrUndef())
 1214     return nullptr;
 1215 
 1216   if (Optional<loc::ConcreteInt> X = V.getAs<loc::ConcreteInt>())
 1217     return &X->getValue();
 1218 
 1219   if (Optional<nonloc::ConcreteInt> X = V.getAs<nonloc::ConcreteInt>())
 1220     return &X->getValue();
 1221 
 1222   if (SymbolRef Sym = V.getAsSymbol())
 1223     return state->getConstraintManager().getSymVal(state, Sym);
 1224 
 1225   // FIXME: Add support for SymExprs.
 1226   return nullptr;
 1227 }
 1228 
 1229 SVal SimpleSValBuilder::simplifySVal(ProgramStateRef State, SVal V) {
 1230   // For now, this function tries to constant-fold symbols inside a
 1231   // nonloc::SymbolVal, and does nothing else. More simplifications should
 1232   // be possible, such as constant-folding an index in an ElementRegion.
 1233 
 1234   class Simplifier : public FullSValVisitor<Simplifier, SVal> {
 1235     ProgramStateRef State;
 1236     SValBuilder &SVB;
 1237 
 1238     // Cache results for the lifetime of the Simplifier. Results change every
 1239     // time new constraints are added to the program state, which is the whole
 1240     // point of simplifying, and for that very reason it's pointless to maintain
 1241     // the same cache for the duration of the whole analysis.
 1242     llvm::DenseMap<SymbolRef, SVal> Cached;
 1243 
 1244     static bool isUnchanged(SymbolRef Sym, SVal Val) {
 1245       return Sym == Val.getAsSymbol();
 1246     }
 1247 
 1248     SVal cache(SymbolRef Sym, SVal V) {
 1249       Cached[Sym] = V;
 1250       return V;
 1251     }
 1252 
 1253     SVal skip(SymbolRef Sym) {
 1254       return cache(Sym, SVB.makeSymbolVal(Sym));
 1255     }
 1256 
 1257   public:
 1258     Simplifier(ProgramStateRef State)
 1259         : State(State), SVB(State->getStateManager().getSValBuilder()) {}
 1260 
 1261     SVal VisitSymbolData(const SymbolData *S) {
 1262       // No cache here.
 1263       if (const llvm::APSInt *I =
 1264               SVB.getKnownValue(State, SVB.makeSymbolVal(S)))
 1265         return Loc::isLocType(S->getType()) ? (SVal)SVB.makeIntLocVal(*I)
 1266                                             : (SVal)SVB.makeIntVal(*I);
 1267       return SVB.makeSymbolVal(S);
 1268     }
 1269 
 1270     // TODO: Support SymbolCast. Support IntSymExpr when/if we actually
 1271     // start producing them.
 1272 
 1273     SVal VisitSymIntExpr(const SymIntExpr *S) {
 1274       auto I = Cached.find(S);
 1275       if (I != Cached.end())
 1276         return I->second;
 1277 
 1278       SVal LHS = Visit(S->getLHS());
 1279       if (isUnchanged(S->getLHS(), LHS))
 1280         return skip(S);
 1281 
 1282       SVal RHS;
 1283       // By looking at the APSInt in the right-hand side of S, we cannot
 1284       // figure out if it should be treated as a Loc or as a NonLoc.
 1285       // So make our guess by recalling that we cannot multiply pointers
 1286       // or compare a pointer to an integer.
 1287       if (Loc::isLocType(S->getLHS()->getType()) &&
 1288           BinaryOperator::isComparisonOp(S->getOpcode())) {
 1289         // The usual conversion of $sym to &SymRegion{$sym}, as they have
 1290         // the same meaning for Loc-type symbols, but the latter form
 1291         // is preferred in SVal computations for being Loc itself.
 1292         if (SymbolRef Sym = LHS.getAsSymbol()) {
 1293           assert(Loc::isLocType(Sym->getType()));
 1294           LHS = SVB.makeLoc(Sym);
 1295         }
 1296         RHS = SVB.makeIntLocVal(S->getRHS());
 1297       } else {
 1298         RHS = SVB.makeIntVal(S->getRHS());
 1299       }
 1300 
 1301       return cache(
 1302           S, SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType()));
 1303     }
 1304 
 1305     SVal VisitSymSymExpr(const SymSymExpr *S) {
 1306       auto I = Cached.find(S);
 1307       if (I != Cached.end())
 1308         return I->second;
 1309 
 1310       // For now don't try to simplify mixed Loc/NonLoc expressions
 1311       // because they often appear from LocAsInteger operations
 1312       // and we don't know how to combine a LocAsInteger
 1313       // with a concrete value.
 1314       if (Loc::isLocType(S->getLHS()->getType()) !=
 1315           Loc::isLocType(S->getRHS()->getType()))
 1316         return skip(S);
 1317 
 1318       SVal LHS = Visit(S->getLHS());
 1319       SVal RHS = Visit(S->getRHS());
 1320       if (isUnchanged(S->getLHS(), LHS) && isUnchanged(S->getRHS(), RHS))
 1321         return skip(S);
 1322 
 1323       return cache(
 1324           S, SVB.evalBinOp(State, S->getOpcode(), LHS, RHS, S->getType()));
 1325     }
 1326 
 1327     SVal VisitSymExpr(SymbolRef S) { return nonloc::SymbolVal(S); }
 1328 
 1329     SVal VisitMemRegion(const MemRegion *R) { return loc::MemRegionVal(R); }
 1330 
 1331     SVal VisitNonLocSymbolVal(nonloc::SymbolVal V) {
 1332       // Simplification is much more costly than computing complexity.
 1333       // For high complexity, it may be not worth it.
 1334       return Visit(V.getSymbol());
 1335     }
 1336 
 1337     SVal VisitSVal(SVal V) { return V; }
 1338   };
 1339 
 1340   // A crude way of preventing this function from calling itself from evalBinOp.
 1341   static bool isReentering = false;
 1342   if (isReentering)
 1343     return V;
 1344 
 1345   isReentering = true;
 1346   SVal SimplifiedV = Simplifier(State).Visit(V);
 1347   isReentering = false;
 1348 
 1349   return SimplifiedV;
 1350 }