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 // Get the type used for calculating wraparound. 258 BasicValueFactory &BVF = getBasicVals(); 259 APSIntType WraparoundType = BVF.getAPSIntType(LHS->getType()); 260 261 // We only handle simple comparisons of the form "$sym == constant" 262 // or "($sym+constant1) == constant2". 263 // The adjustment is "constant1" in the above expression. It's used to 264 // "slide" the solution range around for modular arithmetic. For example, 265 // x < 4 has the solution [0, 3]. x+2 < 4 has the solution [0-2, 3-2], which 266 // in modular arithmetic is [0, 1] U [UINT_MAX-1, UINT_MAX]. It's up to 267 // the subclasses of SimpleConstraintManager to handle the adjustment. 268 SymbolRef Sym = LHS; 269 llvm::APSInt Adjustment = WraparoundType.getZeroValue(); 270 computeAdjustment(Sym, Adjustment); 271 272 // Convert the right-hand side integer as necessary. 273 APSIntType ComparisonType = std::max(WraparoundType, APSIntType(Int)); 274 llvm::APSInt ConvertedInt = ComparisonType.convert(Int); 275 276 // Prefer unsigned comparisons. 277 if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() && 278 ComparisonType.isUnsigned() && !WraparoundType.isUnsigned()) 279 Adjustment.setIsSigned(false); 280 281 switch (Op) { 282 default: 283 llvm_unreachable("invalid operation not caught by assertion above"); 284 285 case BO_EQ: 286 return assumeSymEQ(State, Sym, ConvertedInt, Adjustment); 287 288 case BO_NE: 289 return assumeSymNE(State, Sym, ConvertedInt, Adjustment); 290 291 case BO_GT: 292 return assumeSymGT(State, Sym, ConvertedInt, Adjustment); 293 294 case BO_GE: 295 return assumeSymGE(State, Sym, ConvertedInt, Adjustment); 296 297 case BO_LT: 298 return assumeSymLT(State, Sym, ConvertedInt, Adjustment); 299 300 case BO_LE: 301 return assumeSymLE(State, Sym, ConvertedInt, Adjustment); 302 } // end switch 303 } 304 305 ProgramStateRef SimpleConstraintManager::assumeSymWithinInclusiveRange( 306 ProgramStateRef State, SymbolRef Sym, const llvm::APSInt &From, 307 const llvm::APSInt &To, bool InRange) { 308 // Get the type used for calculating wraparound. 309 BasicValueFactory &BVF = getBasicVals(); 310 APSIntType WraparoundType = BVF.getAPSIntType(Sym->getType()); 311 312 llvm::APSInt Adjustment = WraparoundType.getZeroValue(); 313 SymbolRef AdjustedSym = Sym; 314 computeAdjustment(AdjustedSym, Adjustment); 315 316 // Convert the right-hand side integer as necessary. 317 APSIntType ComparisonType = std::max(WraparoundType, APSIntType(From)); 318 llvm::APSInt ConvertedFrom = ComparisonType.convert(From); 319 llvm::APSInt ConvertedTo = ComparisonType.convert(To); 320 321 // Prefer unsigned comparisons. 322 if (ComparisonType.getBitWidth() == WraparoundType.getBitWidth() && 323 ComparisonType.isUnsigned() && !WraparoundType.isUnsigned()) 324 Adjustment.setIsSigned(false); 325 326 if (InRange) 327 return assumeSymbolWithinInclusiveRange(State, AdjustedSym, ConvertedFrom, 328 ConvertedTo, Adjustment); 329 return assumeSymbolOutOfInclusiveRange(State, AdjustedSym, ConvertedFrom, 330 ConvertedTo, Adjustment); 331 } 332 333 } // end of namespace ento 334 335 } // end of namespace clang 336