Ted Kremenek | 8ad1987 | 2008-03-07 20:13:31 +0000 | [diff] [blame] | 1 | //=== BasicValueFactory.cpp - Basic values for Path Sens analysis --*- C++ -*-// |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 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 | // |
Ted Kremenek | 8ad1987 | 2008-03-07 20:13:31 +0000 | [diff] [blame] | 10 | // This file defines BasicValueFactory, a class that manages the lifetime |
| 11 | // of APSInt objects and symbolic constraints used by GRExprEngine |
| 12 | // and related classes. |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 13 | // |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
Ted Kremenek | 8ad1987 | 2008-03-07 20:13:31 +0000 | [diff] [blame] | 16 | #include "clang/Analysis/PathSensitive/BasicValueFactory.h" |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 17 | #include "clang/Analysis/PathSensitive/RValues.h" |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 18 | |
| 19 | using namespace clang; |
| 20 | |
Ted Kremenek | 465f25a | 2008-04-29 22:17:41 +0000 | [diff] [blame] | 21 | typedef std::pair<RVal, uintptr_t> RValData; |
Ted Kremenek | c4385b4 | 2008-04-29 23:24:44 +0000 | [diff] [blame] | 22 | typedef std::pair<RVal, RVal> RValPair; |
| 23 | |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 24 | |
| 25 | namespace llvm { |
Ted Kremenek | 465f25a | 2008-04-29 22:17:41 +0000 | [diff] [blame] | 26 | template<> struct FoldingSetTrait<RValData> { |
| 27 | static inline void Profile(const RValData& X, llvm::FoldingSetNodeID& ID) { |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 28 | X.first.Profile(ID); |
Ted Kremenek | 465f25a | 2008-04-29 22:17:41 +0000 | [diff] [blame] | 29 | ID.AddPointer( (void*) X.second); |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 30 | } |
| 31 | }; |
Ted Kremenek | c4385b4 | 2008-04-29 23:24:44 +0000 | [diff] [blame] | 32 | |
| 33 | template<> struct FoldingSetTrait<RValPair> { |
| 34 | static inline void Profile(const RValPair& X, llvm::FoldingSetNodeID& ID) { |
| 35 | X.first.Profile(ID); |
| 36 | X.second.Profile(ID); |
| 37 | } |
| 38 | }; |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 39 | } |
| 40 | |
Ted Kremenek | 465f25a | 2008-04-29 22:17:41 +0000 | [diff] [blame] | 41 | typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<RValData> > |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 42 | PersistentRValsTy; |
| 43 | |
Ted Kremenek | c4385b4 | 2008-04-29 23:24:44 +0000 | [diff] [blame] | 44 | typedef llvm::FoldingSet<llvm::FoldingSetNodeWrapper<RValPair> > |
| 45 | PersistentRValPairsTy; |
| 46 | |
Ted Kremenek | 8ad1987 | 2008-03-07 20:13:31 +0000 | [diff] [blame] | 47 | BasicValueFactory::~BasicValueFactory() { |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 48 | // Note that the dstor for the contents of APSIntSet will never be called, |
| 49 | // so we iterate over the set and invoke the dstor for each APSInt. This |
| 50 | // frees an aux. memory allocated to represent very large constants. |
| 51 | for (APSIntSetTy::iterator I=APSIntSet.begin(), E=APSIntSet.end(); I!=E; ++I) |
| 52 | I->getValue().~APSInt(); |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 53 | |
| 54 | delete (PersistentRValsTy*) PersistentRVals; |
Ted Kremenek | c4385b4 | 2008-04-29 23:24:44 +0000 | [diff] [blame] | 55 | delete (PersistentRValPairsTy*) PersistentRValPairs; |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 56 | } |
| 57 | |
Ted Kremenek | 8ad1987 | 2008-03-07 20:13:31 +0000 | [diff] [blame] | 58 | const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) { |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 59 | llvm::FoldingSetNodeID ID; |
| 60 | void* InsertPos; |
| 61 | typedef llvm::FoldingSetNodeWrapper<llvm::APSInt> FoldNodeTy; |
| 62 | |
| 63 | X.Profile(ID); |
| 64 | FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos); |
| 65 | |
| 66 | if (!P) { |
| 67 | P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); |
| 68 | new (P) FoldNodeTy(X); |
| 69 | APSIntSet.InsertNode(P, InsertPos); |
| 70 | } |
| 71 | |
| 72 | return *P; |
| 73 | } |
| 74 | |
Ted Kremenek | 8ad1987 | 2008-03-07 20:13:31 +0000 | [diff] [blame] | 75 | const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth, |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 76 | bool isUnsigned) { |
| 77 | llvm::APSInt V(BitWidth, isUnsigned); |
| 78 | V = X; |
| 79 | return getValue(V); |
| 80 | } |
| 81 | |
Ted Kremenek | 8ad1987 | 2008-03-07 20:13:31 +0000 | [diff] [blame] | 82 | const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, QualType T) { |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 83 | |
Chris Lattner | 8cd0e93 | 2008-03-05 18:54:05 +0000 | [diff] [blame] | 84 | unsigned bits = Ctx.getTypeSize(T); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 85 | llvm::APSInt V(bits, T->isUnsignedIntegerType()); |
| 86 | V = X; |
| 87 | return getValue(V); |
| 88 | } |
| 89 | |
| 90 | const SymIntConstraint& |
Ted Kremenek | 8ad1987 | 2008-03-07 20:13:31 +0000 | [diff] [blame] | 91 | BasicValueFactory::getConstraint(SymbolID sym, BinaryOperator::Opcode Op, |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 92 | const llvm::APSInt& V) { |
| 93 | |
| 94 | llvm::FoldingSetNodeID ID; |
| 95 | SymIntConstraint::Profile(ID, sym, Op, V); |
| 96 | void* InsertPos; |
| 97 | |
| 98 | SymIntConstraint* C = SymIntCSet.FindNodeOrInsertPos(ID, InsertPos); |
| 99 | |
| 100 | if (!C) { |
| 101 | C = (SymIntConstraint*) BPAlloc.Allocate<SymIntConstraint>(); |
| 102 | new (C) SymIntConstraint(sym, Op, V); |
| 103 | SymIntCSet.InsertNode(C, InsertPos); |
| 104 | } |
| 105 | |
| 106 | return *C; |
| 107 | } |
| 108 | |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 109 | const llvm::APSInt* |
Ted Kremenek | 8ad1987 | 2008-03-07 20:13:31 +0000 | [diff] [blame] | 110 | BasicValueFactory::EvaluateAPSInt(BinaryOperator::Opcode Op, |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 111 | const llvm::APSInt& V1, const llvm::APSInt& V2) { |
| 112 | |
| 113 | switch (Op) { |
| 114 | default: |
| 115 | assert (false && "Invalid Opcode."); |
| 116 | |
| 117 | case BinaryOperator::Mul: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 118 | return &getValue( V1 * V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 119 | |
| 120 | case BinaryOperator::Div: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 121 | return &getValue( V1 / V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 122 | |
| 123 | case BinaryOperator::Rem: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 124 | return &getValue( V1 % V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 125 | |
| 126 | case BinaryOperator::Add: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 127 | return &getValue( V1 + V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 128 | |
| 129 | case BinaryOperator::Sub: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 130 | return &getValue( V1 - V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 131 | |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 132 | case BinaryOperator::Shl: { |
| 133 | |
| 134 | // FIXME: This logic should probably go higher up, where we can |
| 135 | // test these conditions symbolically. |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 136 | |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 137 | // FIXME: Expand these checks to include all undefined behavior. |
| 138 | |
| 139 | if (V2.isSigned() && V2.isNegative()) |
| 140 | return NULL; |
| 141 | |
| 142 | uint64_t Amt = V2.getZExtValue(); |
| 143 | |
| 144 | if (Amt > V1.getBitWidth()) |
| 145 | return NULL; |
| 146 | |
| 147 | return &getValue( V1.operator<<( (unsigned) Amt )); |
| 148 | } |
| 149 | |
| 150 | case BinaryOperator::Shr: { |
| 151 | |
| 152 | // FIXME: This logic should probably go higher up, where we can |
| 153 | // test these conditions symbolically. |
| 154 | |
| 155 | // FIXME: Expand these checks to include all undefined behavior. |
| 156 | |
| 157 | if (V2.isSigned() && V2.isNegative()) |
| 158 | return NULL; |
| 159 | |
| 160 | uint64_t Amt = V2.getZExtValue(); |
| 161 | |
| 162 | if (Amt > V1.getBitWidth()) |
| 163 | return NULL; |
| 164 | |
| 165 | return &getValue( V1.operator>>( (unsigned) Amt )); |
| 166 | } |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 167 | |
| 168 | case BinaryOperator::LT: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 169 | return &getTruthValue( V1 < V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 170 | |
| 171 | case BinaryOperator::GT: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 172 | return &getTruthValue( V1 > V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 173 | |
| 174 | case BinaryOperator::LE: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 175 | return &getTruthValue( V1 <= V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 176 | |
| 177 | case BinaryOperator::GE: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 178 | return &getTruthValue( V1 >= V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 179 | |
| 180 | case BinaryOperator::EQ: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 181 | return &getTruthValue( V1 == V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 182 | |
| 183 | case BinaryOperator::NE: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 184 | return &getTruthValue( V1 != V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 185 | |
| 186 | // Note: LAnd, LOr, Comma are handled specially by higher-level logic. |
| 187 | |
| 188 | case BinaryOperator::And: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 189 | return &getValue( V1 & V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 190 | |
| 191 | case BinaryOperator::Or: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 192 | return &getValue( V1 | V2 ); |
Ted Kremenek | 7c79a79 | 2008-02-19 20:53:37 +0000 | [diff] [blame] | 193 | |
| 194 | case BinaryOperator::Xor: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 195 | return &getValue( V1 ^ V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 196 | } |
| 197 | } |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 198 | |
| 199 | |
Ted Kremenek | 465f25a | 2008-04-29 22:17:41 +0000 | [diff] [blame] | 200 | const std::pair<RVal, uintptr_t>& |
| 201 | BasicValueFactory::getPersistentRValWithData(const RVal& V, uintptr_t Data) { |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 202 | |
| 203 | // Lazily create the folding set. |
| 204 | if (!PersistentRVals) PersistentRVals = new PersistentRValsTy(); |
| 205 | |
| 206 | llvm::FoldingSetNodeID ID; |
| 207 | void* InsertPos; |
| 208 | V.Profile(ID); |
Ted Kremenek | 465f25a | 2008-04-29 22:17:41 +0000 | [diff] [blame] | 209 | ID.AddPointer((void*) Data); |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 210 | |
| 211 | PersistentRValsTy& Map = *((PersistentRValsTy*) PersistentRVals); |
| 212 | |
Ted Kremenek | 465f25a | 2008-04-29 22:17:41 +0000 | [diff] [blame] | 213 | typedef llvm::FoldingSetNodeWrapper<RValData> FoldNodeTy; |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 214 | FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); |
| 215 | |
| 216 | if (!P) { |
| 217 | P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); |
Ted Kremenek | 465f25a | 2008-04-29 22:17:41 +0000 | [diff] [blame] | 218 | new (P) FoldNodeTy(std::make_pair(V, Data)); |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 219 | Map.InsertNode(P, InsertPos); |
| 220 | } |
| 221 | |
Ted Kremenek | 465f25a | 2008-04-29 22:17:41 +0000 | [diff] [blame] | 222 | return P->getValue(); |
Ted Kremenek | fe1a0b1 | 2008-04-22 21:10:18 +0000 | [diff] [blame] | 223 | } |
Ted Kremenek | c4385b4 | 2008-04-29 23:24:44 +0000 | [diff] [blame] | 224 | |
| 225 | const std::pair<RVal, RVal>& |
| 226 | BasicValueFactory::getPersistentRValPair(const RVal& V1, const RVal& V2) { |
| 227 | |
| 228 | // Lazily create the folding set. |
| 229 | if (!PersistentRValPairs) PersistentRValPairs = new PersistentRValPairsTy(); |
| 230 | |
| 231 | llvm::FoldingSetNodeID ID; |
| 232 | void* InsertPos; |
| 233 | V1.Profile(ID); |
| 234 | V2.Profile(ID); |
| 235 | |
| 236 | PersistentRValPairsTy& Map = *((PersistentRValPairsTy*) PersistentRValPairs); |
| 237 | |
| 238 | typedef llvm::FoldingSetNodeWrapper<RValPair> FoldNodeTy; |
| 239 | FoldNodeTy* P = Map.FindNodeOrInsertPos(ID, InsertPos); |
| 240 | |
| 241 | if (!P) { |
| 242 | P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); |
| 243 | new (P) FoldNodeTy(std::make_pair(V1, V2)); |
| 244 | Map.InsertNode(P, InsertPos); |
| 245 | } |
| 246 | |
| 247 | return P->getValue(); |
| 248 | } |
| 249 | |