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 "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
  16 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.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) && op != BO_Cmp) {
  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     if (Loc::isLocType(SSE->getLHS()->getType()) &&
  56         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
  69   // If we get here, there's nothing else we can do but treat the symbol as
  70   // opaque.
  71   return assumeSymUnsupported(State, Sym, Assumption);
  72 }
  73
  74 ProgramStateRef RangedConstraintManager::assumeSymInclusiveRange(
  75     ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From,
  76     const llvm::APSInt &To, bool InRange) {
  77   // Get the type used for calculating wraparound.
  78   BasicValueFactory &BVF = getBasicVals();
  79   APSIntType WraparoundType = BVF.getAPSIntType(Sym->getType());
  80
  81   llvm::APSInt Adjustment = WraparoundType.getZeroValue();
  82   SymbolRef AdjustedSym = Sym;
  83   computeAdjustment(AdjustedSym, Adjustment);
  84
  85   // Convert the right-hand side integer as necessary.
  86   APSIntType ComparisonType = std::max(WraparoundType, APSIntType(From));
  87   llvm::APSInt ConvertedFrom = ComparisonType.convert(From);
  88   llvm::APSInt ConvertedTo = ComparisonType.convert(To);
  89
  90   // Prefer unsigned comparisons.
  91   if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() &&
  92       ComparisonType.isUnsigned() && !WraparoundType.isUnsigned())
  93     Adjustment.setIsSigned(false);
  94
  95   if (InRange)
  96     return assumeSymWithinInclusiveRange(State, AdjustedSym, ConvertedFrom,
  97                                          ConvertedTo, Adjustment);
  98   return assumeSymOutsideInclusiveRange(State, AdjustedSym, ConvertedFrom,
  99                                         ConvertedTo, Adjustment);
 100 }
 101
 102 ProgramStateRef
 103 RangedConstraintManager::assumeSymUnsupported(ProgramStateRef State,
 104                                               SymbolRef Sym, bool Assumption) {
 105   BasicValueFactory &BVF = getBasicVals();
 106   QualType T = Sym->getType();
 107
 108   // Non-integer types are not supported.
 109   if (!T->isIntegralOrEnumerationType())
 110     return State;
 111
 112   // Reverse the operation and add directly to state.
 113   const llvm::APSInt &Zero = BVF.getValue(0, T);
 114   if (Assumption)
 115     return assumeSymNE(State, Sym, Zero, Zero);
 116   else
 117     return assumeSymEQ(State, Sym, Zero, Zero);
 118 }
 119
 120 ProgramStateRef RangedConstraintManager::assumeSymRel(ProgramStateRef State,
 121                                                       SymbolRef Sym,
 122                                                       BinaryOperator::Opcode Op,
 123                                                       const llvm::APSInt &Int) {
 124   assert(BinaryOperator::isComparisonOp(Op) &&
 125          "Non-comparison ops should be rewritten as comparisons to zero.");
 126
 127   // Simplification: translate an assume of a constraint of the form
 128   // "(exp comparison_op expr) != 0" to true into an assume of
 129   // "exp comparison_op expr" to true. (And similarly, an assume of the form
 130   // "(exp comparison_op expr) == 0" to true into an assume of
 131   // "exp comparison_op expr" to false.)
 132   if (Int == 0 && (Op == BO_EQ || Op == BO_NE)) {
 133     if (const BinarySymExpr *SE = dyn_cast<BinarySymExpr>(Sym))
 134       if (BinaryOperator::isComparisonOp(SE->getOpcode()))
 135         return assumeSym(State, Sym, (Op == BO_NE ? true : false));
 136   }
 137
 138   // Get the type used for calculating wraparound.
 139   BasicValueFactory &BVF = getBasicVals();
 140   APSIntType WraparoundType = BVF.getAPSIntType(Sym->getType());
 141
 142   // We only handle simple comparisons of the form "$sym == constant"
 143   // or "($sym+constant1) == constant2".
 144   // The adjustment is "constant1" in the above expression. It's used to
 145   // "slide" the solution range around for modular arithmetic. For example,
 146   // x < 4 has the solution [0, 3]. x+2 < 4 has the solution [0-2, 3-2], which
 147   // in modular arithmetic is [0, 1] U [UINT_MAX-1, UINT_MAX]. It's up to
 148   // the subclasses of SimpleConstraintManager to handle the adjustment.
 149   llvm::APSInt Adjustment = WraparoundType.getZeroValue();
 150   computeAdjustment(Sym, Adjustment);
 151
 152   // Convert the right-hand side integer as necessary.
 153   APSIntType ComparisonType = std::max(WraparoundType, APSIntType(Int));
 154   llvm::APSInt ConvertedInt = ComparisonType.convert(Int);
 155
 156   // Prefer unsigned comparisons.
 157   if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() &&
 158       ComparisonType.isUnsigned() && !WraparoundType.isUnsigned())
 159     Adjustment.setIsSigned(false);
 160
 161   switch (Op) {
 162   default:
 163     llvm_unreachable("invalid operation not caught by assertion above");
 164
 165   case BO_EQ:
 166     return assumeSymEQ(State, Sym, ConvertedInt, Adjustment);
 167
 168   case BO_NE:
 169     return assumeSymNE(State, Sym, ConvertedInt, Adjustment);
 170
 171   case BO_GT:
 172     return assumeSymGT(State, Sym, ConvertedInt, Adjustment);
 173
 174   case BO_GE:
 175     return assumeSymGE(State, Sym, ConvertedInt, Adjustment);
 176
 177   case BO_LT:
 178     return assumeSymLT(State, Sym, ConvertedInt, Adjustment);
 179
 180   case BO_LE:
 181     return assumeSymLE(State, Sym, ConvertedInt, Adjustment);
 182   } // end switch
 183 }
 184
 185 void RangedConstraintManager::computeAdjustment(SymbolRef &Sym,
 186                                                 llvm::APSInt &Adjustment) {
 187   // Is it a "($sym+constant1)" expression?
 188   if (const SymIntExpr *SE = dyn_cast<SymIntExpr>(Sym)) {
 189     BinaryOperator::Opcode Op = SE->getOpcode();
 190     if (Op == BO_Add || Op == BO_Sub) {
 191       Sym = SE->getLHS();
 192       Adjustment = APSIntType(Adjustment).convert(SE->getRHS());
 193
 194       // Don't forget to negate the adjustment if it's being subtracted.
 195       // This should happen /after/ promotion, in case the value being
 196       // subtracted is, say, CHAR_MIN, and the promoted type is 'int'.
 197       if (Op == BO_Sub)
 198         Adjustment = -Adjustment;
 199     }
 200   }
 201 }
 202
 203 void *ProgramStateTrait<ConstraintRange>::GDMIndex() {
 204   static int Index;
 205   return &Index;
 206 }
 207
 208 } // end of namespace ento
 209
 210 } // end of namespace clang