Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 1 | // ValueManager.h - Low-level value management for Value Tracking -*- 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 files defines ValueManager, a class that manages the lifetime of APSInt |
| 11 | // objects and symbolic constraints used by GRExprEngine and related classes. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "clang/Analysis/PathSensitive/ValueManager.h" |
| 16 | |
| 17 | using namespace clang; |
| 18 | |
| 19 | ValueManager::~ValueManager() { |
| 20 | // Note that the dstor for the contents of APSIntSet will never be called, |
| 21 | // so we iterate over the set and invoke the dstor for each APSInt. This |
| 22 | // frees an aux. memory allocated to represent very large constants. |
| 23 | for (APSIntSetTy::iterator I=APSIntSet.begin(), E=APSIntSet.end(); I!=E; ++I) |
| 24 | I->getValue().~APSInt(); |
| 25 | } |
| 26 | |
| 27 | const llvm::APSInt& ValueManager::getValue(const llvm::APSInt& X) { |
| 28 | llvm::FoldingSetNodeID ID; |
| 29 | void* InsertPos; |
| 30 | typedef llvm::FoldingSetNodeWrapper<llvm::APSInt> FoldNodeTy; |
| 31 | |
| 32 | X.Profile(ID); |
| 33 | FoldNodeTy* P = APSIntSet.FindNodeOrInsertPos(ID, InsertPos); |
| 34 | |
| 35 | if (!P) { |
| 36 | P = (FoldNodeTy*) BPAlloc.Allocate<FoldNodeTy>(); |
| 37 | new (P) FoldNodeTy(X); |
| 38 | APSIntSet.InsertNode(P, InsertPos); |
| 39 | } |
| 40 | |
| 41 | return *P; |
| 42 | } |
| 43 | |
| 44 | const llvm::APSInt& ValueManager::getValue(uint64_t X, unsigned BitWidth, |
| 45 | bool isUnsigned) { |
| 46 | llvm::APSInt V(BitWidth, isUnsigned); |
| 47 | V = X; |
| 48 | return getValue(V); |
| 49 | } |
| 50 | |
Chris Lattner | 8cd0e93 | 2008-03-05 18:54:05 +0000 | [diff] [blame^] | 51 | const llvm::APSInt& ValueManager::getValue(uint64_t X, QualType T) { |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 52 | |
Chris Lattner | 8cd0e93 | 2008-03-05 18:54:05 +0000 | [diff] [blame^] | 53 | unsigned bits = Ctx.getTypeSize(T); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 54 | llvm::APSInt V(bits, T->isUnsignedIntegerType()); |
| 55 | V = X; |
| 56 | return getValue(V); |
| 57 | } |
| 58 | |
| 59 | const SymIntConstraint& |
| 60 | ValueManager::getConstraint(SymbolID sym, BinaryOperator::Opcode Op, |
| 61 | const llvm::APSInt& V) { |
| 62 | |
| 63 | llvm::FoldingSetNodeID ID; |
| 64 | SymIntConstraint::Profile(ID, sym, Op, V); |
| 65 | void* InsertPos; |
| 66 | |
| 67 | SymIntConstraint* C = SymIntCSet.FindNodeOrInsertPos(ID, InsertPos); |
| 68 | |
| 69 | if (!C) { |
| 70 | C = (SymIntConstraint*) BPAlloc.Allocate<SymIntConstraint>(); |
| 71 | new (C) SymIntConstraint(sym, Op, V); |
| 72 | SymIntCSet.InsertNode(C, InsertPos); |
| 73 | } |
| 74 | |
| 75 | return *C; |
| 76 | } |
| 77 | |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 78 | const llvm::APSInt* |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 79 | ValueManager::EvaluateAPSInt(BinaryOperator::Opcode Op, |
| 80 | const llvm::APSInt& V1, const llvm::APSInt& V2) { |
| 81 | |
| 82 | switch (Op) { |
| 83 | default: |
| 84 | assert (false && "Invalid Opcode."); |
| 85 | |
| 86 | case BinaryOperator::Mul: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 87 | return &getValue( V1 * V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 88 | |
| 89 | case BinaryOperator::Div: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 90 | return &getValue( V1 / V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 91 | |
| 92 | case BinaryOperator::Rem: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 93 | return &getValue( V1 % V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 94 | |
| 95 | case BinaryOperator::Add: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 96 | return &getValue( V1 + V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 97 | |
| 98 | case BinaryOperator::Sub: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 99 | return &getValue( V1 - V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 100 | |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 101 | case BinaryOperator::Shl: { |
| 102 | |
| 103 | // FIXME: This logic should probably go higher up, where we can |
| 104 | // test these conditions symbolically. |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 105 | |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 106 | // FIXME: Expand these checks to include all undefined behavior. |
| 107 | |
| 108 | if (V2.isSigned() && V2.isNegative()) |
| 109 | return NULL; |
| 110 | |
| 111 | uint64_t Amt = V2.getZExtValue(); |
| 112 | |
| 113 | if (Amt > V1.getBitWidth()) |
| 114 | return NULL; |
| 115 | |
| 116 | return &getValue( V1.operator<<( (unsigned) Amt )); |
| 117 | } |
| 118 | |
| 119 | case BinaryOperator::Shr: { |
| 120 | |
| 121 | // FIXME: This logic should probably go higher up, where we can |
| 122 | // test these conditions symbolically. |
| 123 | |
| 124 | // FIXME: Expand these checks to include all undefined behavior. |
| 125 | |
| 126 | if (V2.isSigned() && V2.isNegative()) |
| 127 | return NULL; |
| 128 | |
| 129 | uint64_t Amt = V2.getZExtValue(); |
| 130 | |
| 131 | if (Amt > V1.getBitWidth()) |
| 132 | return NULL; |
| 133 | |
| 134 | return &getValue( V1.operator>>( (unsigned) Amt )); |
| 135 | } |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 136 | |
| 137 | case BinaryOperator::LT: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 138 | return &getTruthValue( V1 < V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 139 | |
| 140 | case BinaryOperator::GT: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 141 | return &getTruthValue( V1 > V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 142 | |
| 143 | case BinaryOperator::LE: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 144 | return &getTruthValue( V1 <= V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 145 | |
| 146 | case BinaryOperator::GE: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 147 | return &getTruthValue( V1 >= V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 148 | |
| 149 | case BinaryOperator::EQ: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 150 | return &getTruthValue( V1 == V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 151 | |
| 152 | case BinaryOperator::NE: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 153 | return &getTruthValue( V1 != V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 154 | |
| 155 | // Note: LAnd, LOr, Comma are handled specially by higher-level logic. |
| 156 | |
| 157 | case BinaryOperator::And: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 158 | return &getValue( V1 & V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 159 | |
| 160 | case BinaryOperator::Or: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 161 | return &getValue( V1 | V2 ); |
Ted Kremenek | 7c79a79 | 2008-02-19 20:53:37 +0000 | [diff] [blame] | 162 | |
| 163 | case BinaryOperator::Xor: |
Ted Kremenek | c2d0720 | 2008-02-28 20:32:03 +0000 | [diff] [blame] | 164 | return &getValue( V1 ^ V2 ); |
Ted Kremenek | 94e915e | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 165 | } |
| 166 | } |