contrib/llvm/tools/clang/lib/StaticAnalyzer/Core/SimpleConstraintManager.cpp

   1 //== SimpleConstraintManager.cpp --------------------------------*- 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 SimpleConstraintManager, a class that holds code shared
  11 //  between BasicConstraintManager and RangeConstraintManager.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "SimpleConstraintManager.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
  17 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
  18 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  19
  20 namespace clang {
  21
  22 namespace ento {
  23
  24 SimpleConstraintManager::~SimpleConstraintManager() {}
  25
  26 bool SimpleConstraintManager::canReasonAbout(SVal X) const {
  27   Optional<nonloc::SymbolVal> SymVal = X.getAs<nonloc::SymbolVal>();
  28   if (SymVal && SymVal->isExpression()) {
  29     const SymExpr *SE = SymVal->getSymbol();
  30
  31     if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(SE)) {
  32       switch (SIE->getOpcode()) {
  33       // We don't reason yet about bitwise-constraints on symbolic values.
  34       case BO_And:
  35       case BO_Or:
  36       case BO_Xor:
  37         return false;
  38       // We don't reason yet about these arithmetic constraints on
  39       // symbolic values.
  40       case BO_Mul:
  41       case BO_Div:
  42       case BO_Rem:
  43       case BO_Shl:
  44       case BO_Shr:
  45         return false;
  46       // All other cases.
  47       default:
  48         return true;
  49       }
  50     }
  51
  52     if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(SE)) {
  53       if (BinaryOperator::isComparisonOp(SSE->getOpcode())) {
  54         // We handle Loc <> Loc comparisons, but not (yet) NonLoc <> NonLoc.
  55         if (Loc::isLocType(SSE->getLHS()->getType())) {
  56           assert(Loc::isLocType(SSE->getRHS()->getType()));
  57           return true;
  58         }
  59       }
  60     }
  61
  62     return false;
  63   }
  64
  65   return true;
  66 }
  67
  68 ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef State,
  69                                                 DefinedSVal Cond,
  70                                                 bool Assumption) {
  71   // If we have a Loc value, cast it to a bool NonLoc first.
  72   if (Optional<Loc> LV = Cond.getAs<Loc>()) {
  73     SValBuilder &SVB = State->getStateManager().getSValBuilder();
  74     QualType T;
  75     const MemRegion *MR = LV->getAsRegion();
  76     if (const TypedRegion *TR = dyn_cast_or_null<TypedRegion>(MR))
  77       T = TR->getLocationType();
  78     else
  79       T = SVB.getContext().VoidPtrTy;
  80
  81     Cond = SVB.evalCast(*LV, SVB.getContext().BoolTy, T).castAs<DefinedSVal>();
  82   }
  83
  84   return assume(State, Cond.castAs<NonLoc>(), Assumption);
  85 }
  86
  87 ProgramStateRef SimpleConstraintManager::assume(ProgramStateRef State,
  88                                                 NonLoc Cond, bool Assumption) {
  89   State = assumeAux(State, Cond, Assumption);
  90   if (NotifyAssumeClients && SU)
  91     return SU->processAssume(State, Cond, Assumption);
  92   return State;
  93 }
  94
  95 ProgramStateRef
  96 SimpleConstraintManager::assumeAuxForSymbol(ProgramStateRef State,
  97                                             SymbolRef Sym, bool Assumption) {
  98   BasicValueFactory &BVF = getBasicVals();
  99   QualType T = Sym->getType();
 100
 101   // None of the constraint solvers currently support non-integer types.
 102   if (!T->isIntegralOrEnumerationType())
 103     return State;
 104
 105   const llvm::APSInt &zero = BVF.getValue(0, T);
 106   if (Assumption)
 107     return assumeSymNE(State, Sym, zero, zero);
 108   else
 109     return assumeSymEQ(State, Sym, zero, zero);
 110 }
 111
 112 ProgramStateRef SimpleConstraintManager::assumeAux(ProgramStateRef State,
 113                                                    NonLoc Cond,
 114                                                    bool Assumption) {
 115
 116   // We cannot reason about SymSymExprs, and can only reason about some
 117   // SymIntExprs.
 118   if (!canReasonAbout(Cond)) {
 119     // Just add the constraint to the expression without trying to simplify.
 120     SymbolRef Sym = Cond.getAsSymExpr();
 121     return assumeAuxForSymbol(State, Sym, Assumption);
 122   }
 123
 124   switch (Cond.getSubKind()) {
 125   default:
 126     llvm_unreachable("'Assume' not implemented for this NonLoc");
 127
 128   case nonloc::SymbolValKind: {
 129     nonloc::SymbolVal SV = Cond.castAs<nonloc::SymbolVal>();
 130     SymbolRef Sym = SV.getSymbol();
 131     assert(Sym);
 132
 133     // Handle SymbolData.
 134     if (!SV.isExpression()) {
 135       return assumeAuxForSymbol(State, Sym, Assumption);
 136
 137       // Handle symbolic expression.
 138     } else if (const SymIntExpr *SE = dyn_cast<SymIntExpr>(Sym)) {
 139       // We can only simplify expressions whose RHS is an integer.
 140
 141       BinaryOperator::Opcode Op = SE->getOpcode();
 142       if (BinaryOperator::isComparisonOp(Op)) {
 143         if (!Assumption)
 144           Op = BinaryOperator::negateComparisonOp(Op);
 145
 146         return assumeSymRel(State, SE->getLHS(), Op, SE->getRHS());
 147       }
 148
 149     } else if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
 150       // Translate "a != b" to "(b - a) != 0".
 151       // We invert the order of the operands as a heuristic for how loop
 152       // conditions are usually written ("begin != end") as compared to length
 153       // calculations ("end - begin"). The more correct thing to do would be to
 154       // canonicalize "a - b" and "b - a", which would allow us to treat
 155       // "a != b" and "b != a" the same.
 156       SymbolManager &SymMgr = getSymbolManager();
 157       BinaryOperator::Opcode Op = SSE->getOpcode();
 158       assert(BinaryOperator::isComparisonOp(Op));
 159
 160       // For now, we only support comparing pointers.
 161       assert(Loc::isLocType(SSE->getLHS()->getType()));
 162       assert(Loc::isLocType(SSE->getRHS()->getType()));
 163       QualType DiffTy = SymMgr.getContext().getPointerDiffType();
 164       SymbolRef Subtraction =
 165           SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), DiffTy);
 166
 167       const llvm::APSInt &Zero = getBasicVals().getValue(0, DiffTy);
 168       Op = BinaryOperator::reverseComparisonOp(Op);
 169       if (!Assumption)
 170         Op = BinaryOperator::negateComparisonOp(Op);
 171       return assumeSymRel(State, Subtraction, Op, Zero);
 172     }
 173
 174     // If we get here, there's nothing else we can do but treat the symbol as
 175     // opaque.
 176     return assumeAuxForSymbol(State, Sym, Assumption);
 177   }
 178
 179   case nonloc::ConcreteIntKind: {
 180     bool b = Cond.castAs<nonloc::ConcreteInt>().getValue() != 0;
 181     bool isFeasible = b ? Assumption : !Assumption;
 182     return isFeasible ? State : nullptr;
 183   }
 184
 185   case nonloc::PointerToMemberKind: {
 186     bool IsNull = !Cond.castAs<nonloc::PointerToMember>().isNullMemberPointer();
 187     bool IsFeasible = IsNull ? Assumption : !Assumption;
 188     return IsFeasible ? State : nullptr;
 189   }
 190
 191   case nonloc::LocAsIntegerKind:
 192     return assume(State, Cond.castAs<nonloc::LocAsInteger>().getLoc(),
 193                   Assumption);
 194   } // end switch
 195 }
 196
 197 ProgramStateRef SimpleConstraintManager::assumeInclusiveRange(
 198     ProgramStateRef State, NonLoc Value, const llvm::APSInt &From,
 199     const llvm::APSInt &To, bool InRange) {
 200
 201   assert(From.isUnsigned() == To.isUnsigned() &&
 202          From.getBitWidth() == To.getBitWidth() &&
 203          "Values should have same types!");
 204
 205   if (!canReasonAbout(Value)) {
 206     // Just add the constraint to the expression without trying to simplify.
 207     SymbolRef Sym = Value.getAsSymExpr();
 208     assert(Sym);
 209     return assumeSymWithinInclusiveRange(State, Sym, From, To, InRange);
 210   }
 211
 212   switch (Value.getSubKind()) {
 213   default:
 214     llvm_unreachable("'assumeInclusiveRange' is not implemented"
 215                      "for this NonLoc");
 216
 217   case nonloc::LocAsIntegerKind:
 218   case nonloc::SymbolValKind: {
 219     if (SymbolRef Sym = Value.getAsSymbol())
 220       return assumeSymWithinInclusiveRange(State, Sym, From, To, InRange);
 221     return State;
 222   } // end switch
 223
 224   case nonloc::ConcreteIntKind: {
 225     const llvm::APSInt &IntVal = Value.castAs<nonloc::ConcreteInt>().getValue();
 226     bool IsInRange = IntVal >= From && IntVal <= To;
 227     bool isFeasible = (IsInRange == InRange);
 228     return isFeasible ? State : nullptr;
 229   }
 230   } // end switch
 231 }
 232
 233 static void computeAdjustment(SymbolRef &Sym, llvm::APSInt &Adjustment) {
 234   // Is it a "($sym+constant1)" expression?
 235   if (const SymIntExpr *SE = dyn_cast<SymIntExpr>(Sym)) {
 236     BinaryOperator::Opcode Op = SE->getOpcode();
 237     if (Op == BO_Add || Op == BO_Sub) {
 238       Sym = SE->getLHS();
 239       Adjustment = APSIntType(Adjustment).convert(SE->getRHS());
 240
 241       // Don't forget to negate the adjustment if it's being subtracted.
 242       // This should happen /after/ promotion, in case the value being
 243       // subtracted is, say, CHAR_MIN, and the promoted type is 'int'.
 244       if (Op == BO_Sub)
 245         Adjustment = -Adjustment;
 246     }
 247   }
 248 }
 249
 250 ProgramStateRef SimpleConstraintManager::assumeSymRel(ProgramStateRef State,
 251                                                       const SymExpr *LHS,
 252                                                       BinaryOperator::Opcode Op,
 253                                                       const llvm::APSInt &Int) {
 254   assert(BinaryOperator::isComparisonOp(Op) &&
 255          "Non-comparison ops should be rewritten as comparisons to zero.");
 256
 257   SymbolRef Sym = LHS;
 258
 259   // Simplification: translate an assume of a constraint of the form
 260   // "(exp comparison_op expr) != 0" to true into an assume of
 261   // "exp comparison_op expr" to true. (And similarly, an assume of the form
 262   // "(exp comparison_op expr) == 0" to true into an assume of
 263   // "exp comparison_op expr" to false.)
 264   if (Int == 0 && (Op == BO_EQ || Op == BO_NE)) {
 265     if (const BinarySymExpr *SE = dyn_cast<BinarySymExpr>(Sym))
 266       if (BinaryOperator::isComparisonOp(SE->getOpcode()))
 267         return assume(State, nonloc::SymbolVal(Sym), (Op == BO_NE ? true : false));
 268   }
 269
 270   // Get the type used for calculating wraparound.
 271   BasicValueFactory &BVF = getBasicVals();
 272   APSIntType WraparoundType = BVF.getAPSIntType(LHS->getType());
 273
 274   // We only handle simple comparisons of the form "$sym == constant"
 275   // or "($sym+constant1) == constant2".
 276   // The adjustment is "constant1" in the above expression. It's used to
 277   // "slide" the solution range around for modular arithmetic. For example,
 278   // x < 4 has the solution [0, 3]. x+2 < 4 has the solution [0-2, 3-2], which
 279   // in modular arithmetic is [0, 1] U [UINT_MAX-1, UINT_MAX]. It's up to
 280   // the subclasses of SimpleConstraintManager to handle the adjustment.
 281   llvm::APSInt Adjustment = WraparoundType.getZeroValue();
 282   computeAdjustment(Sym, Adjustment);
 283
 284   // Convert the right-hand side integer as necessary.
 285   APSIntType ComparisonType = std::max(WraparoundType, APSIntType(Int));
 286   llvm::APSInt ConvertedInt = ComparisonType.convert(Int);
 287
 288   // Prefer unsigned comparisons.
 289   if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() &&
 290       ComparisonType.isUnsigned() && !WraparoundType.isUnsigned())
 291     Adjustment.setIsSigned(false);
 292
 293   switch (Op) {
 294   default:
 295     llvm_unreachable("invalid operation not caught by assertion above");
 296
 297   case BO_EQ:
 298     return assumeSymEQ(State, Sym, ConvertedInt, Adjustment);
 299
 300   case BO_NE:
 301     return assumeSymNE(State, Sym, ConvertedInt, Adjustment);
 302
 303   case BO_GT:
 304     return assumeSymGT(State, Sym, ConvertedInt, Adjustment);
 305
 306   case BO_GE:
 307     return assumeSymGE(State, Sym, ConvertedInt, Adjustment);
 308
 309   case BO_LT:
 310     return assumeSymLT(State, Sym, ConvertedInt, Adjustment);
 311
 312   case BO_LE:
 313     return assumeSymLE(State, Sym, ConvertedInt, Adjustment);
 314   } // end switch
 315 }
 316
 317 ProgramStateRef SimpleConstraintManager::assumeSymWithinInclusiveRange(
 318     ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
 319     const llvm::APSInt &To, bool InRange) {
 320   // Get the type used for calculating wraparound.
 321   BasicValueFactory &BVF = getBasicVals();
 322   APSIntType WraparoundType = BVF.getAPSIntType(Sym->getType());
 323
 324   llvm::APSInt Adjustment = WraparoundType.getZeroValue();
 325   SymbolRef AdjustedSym = Sym;
 326   computeAdjustment(AdjustedSym, Adjustment);
 327
 328   // Convert the right-hand side integer as necessary.
 329   APSIntType ComparisonType = std::max(WraparoundType, APSIntType(From));
 330   llvm::APSInt ConvertedFrom = ComparisonType.convert(From);
 331   llvm::APSInt ConvertedTo = ComparisonType.convert(To);
 332
 333   // Prefer unsigned comparisons.
 334   if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() &&
 335       ComparisonType.isUnsigned() && !WraparoundType.isUnsigned())
 336     Adjustment.setIsSigned(false);
 337
 338   if (InRange)
 339     return assumeSymbolWithinInclusiveRange(State, AdjustedSym, ConvertedFrom,
 340                                             ConvertedTo, Adjustment);
 341   return assumeSymbolOutOfInclusiveRange(State, AdjustedSym, ConvertedFrom,
 342                                          ConvertedTo, Adjustment);
 343 }
 344
 345 } // end of namespace ento
 346
 347 } // end of namespace clang