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

   1 //== RangedConstraintManager.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 RangedConstraintManager, a class that provides a
  11 //  range-based constraint manager interface.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "RangedConstraintManager.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  17
  18 namespace clang {
  19
  20 namespace ento {
  21
  22 RangedConstraintManager::~RangedConstraintManager() {}
  23
  24 ProgramStateRef RangedConstraintManager::assumeSym(ProgramStateRef State,
  25                                                    SymbolRef Sym,
  26                                                    bool Assumption) {
  27   // Handle SymbolData.
  28   if (isa<SymbolData>(Sym)) {
  29     return assumeSymUnsupported(State, Sym, Assumption);
  30
  31     // Handle symbolic expression.
  32   } else if (const SymIntExpr *SIE = dyn_cast<SymIntExpr>(Sym)) {
  33     // We can only simplify expressions whose RHS is an integer.
  34
  35     BinaryOperator::Opcode op = SIE->getOpcode();
  36     if (BinaryOperator::isComparisonOp(op)) {
  37       if (!Assumption)
  38         op = BinaryOperator::negateComparisonOp(op);
  39
  40       return assumeSymRel(State, SIE->getLHS(), op, SIE->getRHS());
  41     }
  42
  43   } else if (const SymSymExpr *SSE = dyn_cast<SymSymExpr>(Sym)) {
  44     // Translate "a != b" to "(b - a) != 0".
  45     // We invert the order of the operands as a heuristic for how loop
  46     // conditions are usually written ("begin != end") as compared to length
  47     // calculations ("end - begin"). The more correct thing to do would be to
  48     // canonicalize "a - b" and "b - a", which would allow us to treat
  49     // "a != b" and "b != a" the same.
  50     SymbolManager &SymMgr = getSymbolManager();
  51     BinaryOperator::Opcode Op = SSE->getOpcode();
  52     assert(BinaryOperator::isComparisonOp(Op));
  53
  54     // For now, we only support comparing pointers.
  55     assert(Loc::isLocType(SSE->getLHS()->getType()));
  56     assert(Loc::isLocType(SSE->getRHS()->getType()));
  57     QualType DiffTy = SymMgr.getContext().getPointerDiffType();
  58     SymbolRef Subtraction =
  59         SymMgr.getSymSymExpr(SSE->getRHS(), BO_Sub, SSE->getLHS(), DiffTy);
  60
  61     const llvm::APSInt &Zero = getBasicVals().getValue(0, DiffTy);
  62     Op = BinaryOperator::reverseComparisonOp(Op);
  63     if (!Assumption)
  64       Op = BinaryOperator::negateComparisonOp(Op);
  65     return assumeSymRel(State, Subtraction, Op, Zero);
  66   }
  67
  68   // If we get here, there's nothing else we can do but treat the symbol as
  69   // opaque.
  70   return assumeSymUnsupported(State, Sym, Assumption);
  71 }
  72
  73 ProgramStateRef RangedConstraintManager::assumeSymInclusiveRange(
  74     ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
  75     const llvm::APSInt &To, bool InRange) {
  76   // Get the type used for calculating wraparound.
  77   BasicValueFactory &BVF = getBasicVals();
  78   APSIntType WraparoundType = BVF.getAPSIntType(Sym->getType());
  79
  80   llvm::APSInt Adjustment = WraparoundType.getZeroValue();
  81   SymbolRef AdjustedSym = Sym;
  82   computeAdjustment(AdjustedSym, Adjustment);
  83
  84   // Convert the right-hand side integer as necessary.
  85   APSIntType ComparisonType = std::max(WraparoundType, APSIntType(From));
  86   llvm::APSInt ConvertedFrom = ComparisonType.convert(From);
  87   llvm::APSInt ConvertedTo = ComparisonType.convert(To);
  88
  89   // Prefer unsigned comparisons.
  90   if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() &&
  91       ComparisonType.isUnsigned() && !WraparoundType.isUnsigned())
  92     Adjustment.setIsSigned(false);
  93
  94   if (InRange)
  95     return assumeSymWithinInclusiveRange(State, AdjustedSym, ConvertedFrom,
  96                                          ConvertedTo, Adjustment);
  97   return assumeSymOutsideInclusiveRange(State, AdjustedSym, ConvertedFrom,
  98                                         ConvertedTo, Adjustment);
  99 }
 100
 101 ProgramStateRef
 102 RangedConstraintManager::assumeSymUnsupported(ProgramStateRef State,
 103                                               SymbolRef Sym, bool Assumption) {
 104   BasicValueFactory &BVF = getBasicVals();
 105   QualType T = Sym->getType();
 106
 107   // Non-integer types are not supported.
 108   if (!T->isIntegralOrEnumerationType())
 109     return State;
 110
 111   // Reverse the operation and add directly to state.
 112   const llvm::APSInt &Zero = BVF.getValue(0, T);
 113   if (Assumption)
 114     return assumeSymNE(State, Sym, Zero, Zero);
 115   else
 116     return assumeSymEQ(State, Sym, Zero, Zero);
 117 }
 118
 119 ProgramStateRef RangedConstraintManager::assumeSymRel(ProgramStateRef State,
 120                                                       SymbolRef Sym,
 121                                                       BinaryOperator::Opcode Op,
 122                                                       const llvm::APSInt &Int) {
 123   assert(BinaryOperator::isComparisonOp(Op) &&
 124          "Non-comparison ops should be rewritten as comparisons to zero.");
 125
 126   // Simplification: translate an assume of a constraint of the form
 127   // "(exp comparison_op expr) != 0" to true into an assume of
 128   // "exp comparison_op expr" to true. (And similarly, an assume of the form
 129   // "(exp comparison_op expr) == 0" to true into an assume of
 130   // "exp comparison_op expr" to false.)
 131   if (Int == 0 && (Op == BO_EQ || Op == BO_NE)) {
 132     if (const BinarySymExpr *SE = dyn_cast<BinarySymExpr>(Sym))
 133       if (BinaryOperator::isComparisonOp(SE->getOpcode()))
 134         return assumeSym(State, Sym, (Op == BO_NE ? true : false));
 135   }
 136
 137   // Get the type used for calculating wraparound.
 138   BasicValueFactory &BVF = getBasicVals();
 139   APSIntType WraparoundType = BVF.getAPSIntType(Sym->getType());
 140
 141   // We only handle simple comparisons of the form "$sym == constant"
 142   // or "($sym+constant1) == constant2".
 143   // The adjustment is "constant1" in the above expression. It's used to
 144   // "slide" the solution range around for modular arithmetic. For example,
 145   // x < 4 has the solution [0, 3]. x+2 < 4 has the solution [0-2, 3-2], which
 146   // in modular arithmetic is [0, 1] U [UINT_MAX-1, UINT_MAX]. It's up to
 147   // the subclasses of SimpleConstraintManager to handle the adjustment.
 148   llvm::APSInt Adjustment = WraparoundType.getZeroValue();
 149   computeAdjustment(Sym, Adjustment);
 150
 151   // Convert the right-hand side integer as necessary.
 152   APSIntType ComparisonType = std::max(WraparoundType, APSIntType(Int));
 153   llvm::APSInt ConvertedInt = ComparisonType.convert(Int);
 154
 155   // Prefer unsigned comparisons.
 156   if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() &&
 157       ComparisonType.isUnsigned() && !WraparoundType.isUnsigned())
 158     Adjustment.setIsSigned(false);
 159
 160   switch (Op) {
 161   default:
 162     llvm_unreachable("invalid operation not caught by assertion above");
 163
 164   case BO_EQ:
 165     return assumeSymEQ(State, Sym, ConvertedInt, Adjustment);
 166
 167   case BO_NE:
 168     return assumeSymNE(State, Sym, ConvertedInt, Adjustment);
 169
 170   case BO_GT:
 171     return assumeSymGT(State, Sym, ConvertedInt, Adjustment);
 172
 173   case BO_GE:
 174     return assumeSymGE(State, Sym, ConvertedInt, Adjustment);
 175
 176   case BO_LT:
 177     return assumeSymLT(State, Sym, ConvertedInt, Adjustment);
 178
 179   case BO_LE:
 180     return assumeSymLE(State, Sym, ConvertedInt, Adjustment);
 181   } // end switch
 182 }
 183
 184 void RangedConstraintManager::computeAdjustment(SymbolRef &Sym,
 185                                                 llvm::APSInt &Adjustment) {
 186   // Is it a "($sym+constant1)" expression?
 187   if (const SymIntExpr *SE = dyn_cast<SymIntExpr>(Sym)) {
 188     BinaryOperator::Opcode Op = SE->getOpcode();
 189     if (Op == BO_Add || Op == BO_Sub) {
 190       Sym = SE->getLHS();
 191       Adjustment = APSIntType(Adjustment).convert(SE->getRHS());
 192
 193       // Don't forget to negate the adjustment if it's being subtracted.
 194       // This should happen /after/ promotion, in case the value being
 195       // subtracted is, say, CHAR_MIN, and the promoted type is 'int'.
 196       if (Op == BO_Sub)
 197         Adjustment = -Adjustment;
 198     }
 199   }
 200 }
 201
 202 } // end of namespace ento
 203
 204 } // end of namespace clang