Ted Kremenek | d70d0b0 | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 1 | //== SymbolManager.h - Management of Symbolic Values ------------*- 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 | // |
Gabor Greif | 843e934 | 2008-03-06 10:40:09 +0000 | [diff] [blame] | 10 | // This file defines SymbolManager, a class that manages symbolic values |
Ted Kremenek | d70d0b0 | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 11 | // created for use by GRExprEngine and related classes. |
| 12 | // |
| 13 | //===----------------------------------------------------------------------===// |
| 14 | |
| 15 | #include "clang/Analysis/PathSensitive/SymbolManager.h" |
Zhongxing Xu | 4193eca | 2008-12-20 06:32:12 +0000 | [diff] [blame] | 16 | #include "clang/Analysis/PathSensitive/MemRegion.h" |
Ted Kremenek | 562731e | 2008-12-05 02:45:20 +0000 | [diff] [blame] | 17 | #include "llvm/Support/raw_ostream.h" |
Ted Kremenek | d70d0b0 | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 18 | |
| 19 | using namespace clang; |
| 20 | |
Ted Kremenek | 8800ad4 | 2009-07-13 23:31:04 +0000 | [diff] [blame] | 21 | void SymExpr::dump() const { |
| 22 | dumpToStream(llvm::errs()); |
| 23 | } |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 24 | |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 25 | static void print(llvm::raw_ostream& os, BinaryOperator::Opcode Op) { |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 26 | switch (Op) { |
| 27 | default: |
| 28 | assert(false && "operator printing not implemented"); |
| 29 | break; |
| 30 | case BinaryOperator::Mul: os << '*' ; break; |
| 31 | case BinaryOperator::Div: os << '/' ; break; |
| 32 | case BinaryOperator::Rem: os << '%' ; break; |
| 33 | case BinaryOperator::Add: os << '+' ; break; |
| 34 | case BinaryOperator::Sub: os << '-' ; break; |
| 35 | case BinaryOperator::Shl: os << "<<" ; break; |
| 36 | case BinaryOperator::Shr: os << ">>" ; break; |
| 37 | case BinaryOperator::LT: os << "<" ; break; |
| 38 | case BinaryOperator::GT: os << '>' ; break; |
| 39 | case BinaryOperator::LE: os << "<=" ; break; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 40 | case BinaryOperator::GE: os << ">=" ; break; |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 41 | case BinaryOperator::EQ: os << "==" ; break; |
| 42 | case BinaryOperator::NE: os << "!=" ; break; |
| 43 | case BinaryOperator::And: os << '&' ; break; |
| 44 | case BinaryOperator::Xor: os << '^' ; break; |
| 45 | case BinaryOperator::Or: os << '|' ; break; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 46 | } |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 47 | } |
| 48 | |
Ted Kremenek | 8800ad4 | 2009-07-13 23:31:04 +0000 | [diff] [blame] | 49 | void SymIntExpr::dumpToStream(llvm::raw_ostream& os) const { |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 50 | os << '('; |
Ted Kremenek | 8800ad4 | 2009-07-13 23:31:04 +0000 | [diff] [blame] | 51 | getLHS()->dumpToStream(os); |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 52 | os << ") "; |
Ted Kremenek | 8800ad4 | 2009-07-13 23:31:04 +0000 | [diff] [blame] | 53 | print(os, getOpcode()); |
| 54 | os << ' ' << getRHS().getZExtValue(); |
| 55 | if (getRHS().isUnsigned()) os << 'U'; |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 56 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 57 | |
Ted Kremenek | 8800ad4 | 2009-07-13 23:31:04 +0000 | [diff] [blame] | 58 | void SymSymExpr::dumpToStream(llvm::raw_ostream& os) const { |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 59 | os << '('; |
Ted Kremenek | 8800ad4 | 2009-07-13 23:31:04 +0000 | [diff] [blame] | 60 | getLHS()->dumpToStream(os); |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 61 | os << ") "; |
| 62 | os << '('; |
Ted Kremenek | 8800ad4 | 2009-07-13 23:31:04 +0000 | [diff] [blame] | 63 | getRHS()->dumpToStream(os); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 64 | os << ')'; |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 65 | } |
| 66 | |
Ted Kremenek | 8800ad4 | 2009-07-13 23:31:04 +0000 | [diff] [blame] | 67 | void SymbolConjured::dumpToStream(llvm::raw_ostream& os) const { |
Ted Kremenek | 19e1f0b | 2009-08-01 06:17:29 +0000 | [diff] [blame] | 68 | os << "conj_$" << getSymbolID() << '{' << T.getAsString() << '}'; |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 69 | } |
| 70 | |
Ted Kremenek | fb91c70 | 2009-07-15 02:27:32 +0000 | [diff] [blame] | 71 | void SymbolDerived::dumpToStream(llvm::raw_ostream& os) const { |
| 72 | os << "derived_$" << getSymbolID() << '{' |
| 73 | << getParentSymbol() << ',' << getRegion() << '}'; |
| 74 | } |
| 75 | |
Ted Kremenek | 8800ad4 | 2009-07-13 23:31:04 +0000 | [diff] [blame] | 76 | void SymbolRegionValue::dumpToStream(llvm::raw_ostream& os) const { |
| 77 | os << "reg_$" << getSymbolID() << "<" << R << ">"; |
Ted Kremenek | 94c9698 | 2009-03-03 22:06:47 +0000 | [diff] [blame] | 78 | } |
| 79 | |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 80 | const SymbolRegionValue* |
Zhongxing Xu | 45257c3 | 2009-06-19 06:00:32 +0000 | [diff] [blame] | 81 | SymbolManager::getRegionValueSymbol(const MemRegion* R, QualType T) { |
Ted Kremenek | 00a3a5f | 2008-03-12 01:21:45 +0000 | [diff] [blame] | 82 | llvm::FoldingSetNodeID profile; |
Zhongxing Xu | 45257c3 | 2009-06-19 06:00:32 +0000 | [diff] [blame] | 83 | SymbolRegionValue::Profile(profile, R, T); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 84 | void* InsertPos; |
| 85 | SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); |
| 86 | if (!SD) { |
Zhongxing Xu | d9b6ad6 | 2009-05-09 04:08:27 +0000 | [diff] [blame] | 87 | SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>(); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 88 | new (SD) SymbolRegionValue(SymbolCounter, R, T); |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 89 | DataSet.InsertNode(SD, InsertPos); |
| 90 | ++SymbolCounter; |
| 91 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 92 | |
Zhongxing Xu | d9b6ad6 | 2009-05-09 04:08:27 +0000 | [diff] [blame] | 93 | return cast<SymbolRegionValue>(SD); |
Zhongxing Xu | eabf776 | 2008-11-19 11:03:17 +0000 | [diff] [blame] | 94 | } |
| 95 | |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 96 | const SymbolConjured* |
| 97 | SymbolManager::getConjuredSymbol(const Stmt* E, QualType T, unsigned Count, |
| 98 | const void* SymbolTag) { |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 99 | |
Ted Kremenek | 00a3a5f | 2008-03-12 01:21:45 +0000 | [diff] [blame] | 100 | llvm::FoldingSetNodeID profile; |
Ted Kremenek | a880b66 | 2009-03-04 22:53:46 +0000 | [diff] [blame] | 101 | SymbolConjured::Profile(profile, E, T, Count, SymbolTag); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 102 | void* InsertPos; |
| 103 | SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); |
| 104 | if (!SD) { |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 105 | SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>(); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 106 | new (SD) SymbolConjured(SymbolCounter, E, T, Count, SymbolTag); |
| 107 | DataSet.InsertNode(SD, InsertPos); |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 108 | ++SymbolCounter; |
| 109 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 110 | |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 111 | return cast<SymbolConjured>(SD); |
Ted Kremenek | 00a3a5f | 2008-03-12 01:21:45 +0000 | [diff] [blame] | 112 | } |
| 113 | |
Ted Kremenek | fb91c70 | 2009-07-15 02:27:32 +0000 | [diff] [blame] | 114 | const SymbolDerived* |
| 115 | SymbolManager::getDerivedSymbol(SymbolRef parentSymbol, |
| 116 | const TypedRegion *R) { |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 117 | |
Ted Kremenek | fb91c70 | 2009-07-15 02:27:32 +0000 | [diff] [blame] | 118 | llvm::FoldingSetNodeID profile; |
| 119 | SymbolDerived::Profile(profile, parentSymbol, R); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 120 | void* InsertPos; |
| 121 | SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos); |
| 122 | if (!SD) { |
Ted Kremenek | fb91c70 | 2009-07-15 02:27:32 +0000 | [diff] [blame] | 123 | SD = (SymExpr*) BPAlloc.Allocate<SymbolDerived>(); |
| 124 | new (SD) SymbolDerived(SymbolCounter, parentSymbol, R); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 125 | DataSet.InsertNode(SD, InsertPos); |
Ted Kremenek | fb91c70 | 2009-07-15 02:27:32 +0000 | [diff] [blame] | 126 | ++SymbolCounter; |
| 127 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 128 | |
Ted Kremenek | fb91c70 | 2009-07-15 02:27:32 +0000 | [diff] [blame] | 129 | return cast<SymbolDerived>(SD); |
| 130 | } |
| 131 | |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 132 | const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs, |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 133 | BinaryOperator::Opcode op, |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 134 | const llvm::APSInt& v, |
| 135 | QualType t) { |
Zhongxing Xu | a129eb9 | 2009-03-25 05:58:37 +0000 | [diff] [blame] | 136 | llvm::FoldingSetNodeID ID; |
| 137 | SymIntExpr::Profile(ID, lhs, op, v, t); |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 138 | void *InsertPos; |
| 139 | SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); |
Zhongxing Xu | a129eb9 | 2009-03-25 05:58:37 +0000 | [diff] [blame] | 140 | |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 141 | if (!data) { |
| 142 | data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>(); |
| 143 | new (data) SymIntExpr(lhs, op, v, t); |
| 144 | DataSet.InsertNode(data, InsertPos); |
| 145 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 146 | |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 147 | return cast<SymIntExpr>(data); |
Zhongxing Xu | a129eb9 | 2009-03-25 05:58:37 +0000 | [diff] [blame] | 148 | } |
| 149 | |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 150 | const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs, |
| 151 | BinaryOperator::Opcode op, |
| 152 | const SymExpr *rhs, |
| 153 | QualType t) { |
Zhongxing Xu | a129eb9 | 2009-03-25 05:58:37 +0000 | [diff] [blame] | 154 | llvm::FoldingSetNodeID ID; |
| 155 | SymSymExpr::Profile(ID, lhs, op, rhs, t); |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 156 | void *InsertPos; |
| 157 | SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos); |
Zhongxing Xu | a129eb9 | 2009-03-25 05:58:37 +0000 | [diff] [blame] | 158 | |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 159 | if (!data) { |
| 160 | data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>(); |
| 161 | new (data) SymSymExpr(lhs, op, rhs, t); |
| 162 | DataSet.InsertNode(data, InsertPos); |
| 163 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 164 | |
Ted Kremenek | e0e4ebf | 2009-03-26 03:35:11 +0000 | [diff] [blame] | 165 | return cast<SymSymExpr>(data); |
Zhongxing Xu | a129eb9 | 2009-03-25 05:58:37 +0000 | [diff] [blame] | 166 | } |
| 167 | |
Ted Kremenek | 9ab6b9c | 2009-01-22 18:23:34 +0000 | [diff] [blame] | 168 | QualType SymbolConjured::getType(ASTContext&) const { |
| 169 | return T; |
| 170 | } |
Ted Kremenek | d763eb9 | 2008-02-26 02:15:56 +0000 | [diff] [blame] | 171 | |
Ted Kremenek | fb91c70 | 2009-07-15 02:27:32 +0000 | [diff] [blame] | 172 | |
| 173 | QualType SymbolDerived::getType(ASTContext& Ctx) const { |
| 174 | return R->getValueType(Ctx); |
| 175 | } |
| 176 | |
Zhongxing Xu | d9b6ad6 | 2009-05-09 04:08:27 +0000 | [diff] [blame] | 177 | QualType SymbolRegionValue::getType(ASTContext& C) const { |
Zhongxing Xu | 45257c3 | 2009-06-19 06:00:32 +0000 | [diff] [blame] | 178 | if (!T.isNull()) |
| 179 | return T; |
| 180 | |
Ted Kremenek | 9ab6b9c | 2009-01-22 18:23:34 +0000 | [diff] [blame] | 181 | if (const TypedRegion* TR = dyn_cast<TypedRegion>(R)) |
Zhongxing Xu | a82d8aa | 2009-05-09 03:57:34 +0000 | [diff] [blame] | 182 | return TR->getValueType(C); |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 183 | |
Ted Kremenek | 9ab6b9c | 2009-01-22 18:23:34 +0000 | [diff] [blame] | 184 | return QualType(); |
Ted Kremenek | d70d0b0 | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 185 | } |
| 186 | |
Ted Kremenek | d70d0b0 | 2008-02-16 01:12:31 +0000 | [diff] [blame] | 187 | SymbolManager::~SymbolManager() {} |
Ted Kremenek | 241677a | 2009-01-21 22:26:05 +0000 | [diff] [blame] | 188 | |
Ted Kremenek | 693de5d | 2009-03-23 15:42:58 +0000 | [diff] [blame] | 189 | bool SymbolManager::canSymbolicate(QualType T) { |
Ted Kremenek | 4e6e0d7 | 2009-07-29 18:12:48 +0000 | [diff] [blame] | 190 | return Loc::IsLocType(T) || (T->isIntegerType() && T->isScalarType()); |
Ted Kremenek | 693de5d | 2009-03-23 15:42:58 +0000 | [diff] [blame] | 191 | } |
| 192 | |
Ted Kremenek | 241677a | 2009-01-21 22:26:05 +0000 | [diff] [blame] | 193 | void SymbolReaper::markLive(SymbolRef sym) { |
Ted Kremenek | a97d54c | 2009-09-02 06:03:18 +0000 | [diff] [blame] | 194 | TheLiving.insert(sym); |
| 195 | TheDead.erase(sym); |
Ted Kremenek | 241677a | 2009-01-21 22:26:05 +0000 | [diff] [blame] | 196 | } |
| 197 | |
| 198 | bool SymbolReaper::maybeDead(SymbolRef sym) { |
| 199 | if (isLive(sym)) |
| 200 | return false; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 201 | |
Ted Kremenek | a97d54c | 2009-09-02 06:03:18 +0000 | [diff] [blame] | 202 | TheDead.insert(sym); |
Ted Kremenek | 241677a | 2009-01-21 22:26:05 +0000 | [diff] [blame] | 203 | return true; |
| 204 | } |
| 205 | |
Ted Kremenek | 9ab6b9c | 2009-01-22 18:23:34 +0000 | [diff] [blame] | 206 | bool SymbolReaper::isLive(SymbolRef sym) { |
Ted Kremenek | a97d54c | 2009-09-02 06:03:18 +0000 | [diff] [blame] | 207 | if (TheLiving.count(sym)) |
Ted Kremenek | dcb6a26 | 2009-01-22 18:51:33 +0000 | [diff] [blame] | 208 | return true; |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 209 | |
Ted Kremenek | 19e1f0b | 2009-08-01 06:17:29 +0000 | [diff] [blame] | 210 | if (const SymbolDerived *derived = dyn_cast<SymbolDerived>(sym)) { |
| 211 | if (isLive(derived->getParentSymbol())) { |
| 212 | markLive(sym); |
| 213 | return true; |
| 214 | } |
| 215 | return false; |
| 216 | } |
Mike Stump | 1eb4433 | 2009-09-09 15:08:12 +0000 | [diff] [blame] | 217 | |
Ted Kremenek | dcb6a26 | 2009-01-22 18:51:33 +0000 | [diff] [blame] | 218 | // Interogate the symbol. It may derive from an input value to |
| 219 | // the analyzed function/method. |
Zhongxing Xu | d9b6ad6 | 2009-05-09 04:08:27 +0000 | [diff] [blame] | 220 | return isa<SymbolRegionValue>(sym); |
Ted Kremenek | 241677a | 2009-01-21 22:26:05 +0000 | [diff] [blame] | 221 | } |
Ted Kremenek | 5216ad7 | 2009-02-14 03:16:10 +0000 | [diff] [blame] | 222 | |
Ted Kremenek | edeb5b6 | 2009-12-04 20:32:20 +0000 | [diff] [blame] | 223 | bool SymbolReaper::isLive(const Stmt *Loc, const VarRegion *VR) const { |
| 224 | return Liveness.isLive(Loc, VR->getDecl()); |
| 225 | } |
| 226 | |
Ted Kremenek | 5216ad7 | 2009-02-14 03:16:10 +0000 | [diff] [blame] | 227 | SymbolVisitor::~SymbolVisitor() {} |