blob: 275f30a2963e0ea3bbf13b02b4026e5d8090edcd [file] [log] [blame]
Ted Kremenekd70d0b02008-02-16 01:12:31 +00001//== 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 Greif843e9342008-03-06 10:40:09 +000010// This file defines SymbolManager, a class that manages symbolic values
Ted Kremenekd70d0b02008-02-16 01:12:31 +000011// created for use by GRExprEngine and related classes.
12//
13//===----------------------------------------------------------------------===//
14
15#include "clang/Analysis/PathSensitive/SymbolManager.h"
Zhongxing Xu4193eca2008-12-20 06:32:12 +000016#include "clang/Analysis/PathSensitive/MemRegion.h"
Ted Kremenek562731e2008-12-05 02:45:20 +000017#include "llvm/Support/raw_ostream.h"
Ted Kremenekd70d0b02008-02-16 01:12:31 +000018
19using namespace clang;
20
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +000021static void print(llvm::raw_ostream& os, const SymExpr *SE);
22
23static void print(llvm::raw_ostream& os, BinaryOperator::Opcode Op) {
24 switch (Op) {
25 default:
26 assert(false && "operator printing not implemented");
27 break;
28 case BinaryOperator::Mul: os << '*' ; break;
29 case BinaryOperator::Div: os << '/' ; break;
30 case BinaryOperator::Rem: os << '%' ; break;
31 case BinaryOperator::Add: os << '+' ; break;
32 case BinaryOperator::Sub: os << '-' ; break;
33 case BinaryOperator::Shl: os << "<<" ; break;
34 case BinaryOperator::Shr: os << ">>" ; break;
35 case BinaryOperator::LT: os << "<" ; break;
36 case BinaryOperator::GT: os << '>' ; break;
37 case BinaryOperator::LE: os << "<=" ; break;
38 case BinaryOperator::GE: os << ">=" ; break;
39 case BinaryOperator::EQ: os << "==" ; break;
40 case BinaryOperator::NE: os << "!=" ; break;
41 case BinaryOperator::And: os << '&' ; break;
42 case BinaryOperator::Xor: os << '^' ; break;
43 case BinaryOperator::Or: os << '|' ; break;
44 }
45}
46
47static void print(llvm::raw_ostream& os, const SymIntExpr *SE) {
48 os << '(';
49 print(os, SE->getLHS());
50 os << ") ";
51 print(os, SE->getOpcode());
52 os << ' ' << SE->getRHS().getZExtValue();
53 if (SE->getRHS().isUnsigned()) os << 'U';
54}
Ted Kremenek94c96982009-03-03 22:06:47 +000055
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +000056static void print(llvm::raw_ostream& os, const SymSymExpr *SE) {
57 os << '(';
58 print(os, SE->getLHS());
59 os << ") ";
60 os << '(';
61 print(os, SE->getRHS());
62 os << ')';
63}
64
65static void print(llvm::raw_ostream& os, const SymExpr *SE) {
66 switch (SE->getKind()) {
67 case SymExpr::BEGIN_SYMBOLS:
Zhongxing Xud9b6ad62009-05-09 04:08:27 +000068 case SymExpr::RegionValueKind:
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +000069 case SymExpr::ConjuredKind:
70 case SymExpr::END_SYMBOLS:
71 os << '$' << cast<SymbolData>(SE)->getSymbolID();
72 return;
73 case SymExpr::SymIntKind:
74 print(os, cast<SymIntExpr>(SE));
75 return;
76 case SymExpr::SymSymKind:
77 print(os, cast<SymSymExpr>(SE));
78 return;
79 }
80}
81
82
83llvm::raw_ostream& llvm::operator<<(llvm::raw_ostream& os, const SymExpr *SE) {
84 print(os, SE);
Ted Kremenek94c96982009-03-03 22:06:47 +000085 return os;
86}
87
Zhongxing Xud9b6ad62009-05-09 04:08:27 +000088const SymbolRegionValue*
Zhongxing Xu45257c32009-06-19 06:00:32 +000089SymbolManager::getRegionValueSymbol(const MemRegion* R, QualType T) {
Ted Kremenek00a3a5f2008-03-12 01:21:45 +000090 llvm::FoldingSetNodeID profile;
Zhongxing Xu45257c32009-06-19 06:00:32 +000091 SymbolRegionValue::Profile(profile, R, T);
Ted Kremenek9ab6b9c2009-01-22 18:23:34 +000092 void* InsertPos;
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +000093 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
94 if (!SD) {
Zhongxing Xud9b6ad62009-05-09 04:08:27 +000095 SD = (SymExpr*) BPAlloc.Allocate<SymbolRegionValue>();
Zhongxing Xu45257c32009-06-19 06:00:32 +000096 new (SD) SymbolRegionValue(SymbolCounter, R, T);
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +000097 DataSet.InsertNode(SD, InsertPos);
98 ++SymbolCounter;
99 }
Ted Kremenek00a3a5f2008-03-12 01:21:45 +0000100
Zhongxing Xud9b6ad62009-05-09 04:08:27 +0000101 return cast<SymbolRegionValue>(SD);
Zhongxing Xueabf7762008-11-19 11:03:17 +0000102}
103
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000104const SymbolConjured*
105SymbolManager::getConjuredSymbol(const Stmt* E, QualType T, unsigned Count,
106 const void* SymbolTag) {
Ted Kremenek00a3a5f2008-03-12 01:21:45 +0000107
108 llvm::FoldingSetNodeID profile;
Ted Kremeneka880b662009-03-04 22:53:46 +0000109 SymbolConjured::Profile(profile, E, T, Count, SymbolTag);
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000110 void* InsertPos;
111 SymExpr *SD = DataSet.FindNodeOrInsertPos(profile, InsertPos);
112 if (!SD) {
113 SD = (SymExpr*) BPAlloc.Allocate<SymbolConjured>();
114 new (SD) SymbolConjured(SymbolCounter, E, T, Count, SymbolTag);
115 DataSet.InsertNode(SD, InsertPos);
116 ++SymbolCounter;
117 }
Ted Kremenek00a3a5f2008-03-12 01:21:45 +0000118
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000119 return cast<SymbolConjured>(SD);
Ted Kremenek00a3a5f2008-03-12 01:21:45 +0000120}
121
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000122const SymIntExpr *SymbolManager::getSymIntExpr(const SymExpr *lhs,
123 BinaryOperator::Opcode op,
124 const llvm::APSInt& v,
125 QualType t) {
Zhongxing Xua129eb92009-03-25 05:58:37 +0000126 llvm::FoldingSetNodeID ID;
127 SymIntExpr::Profile(ID, lhs, op, v, t);
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000128 void *InsertPos;
129 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
Zhongxing Xua129eb92009-03-25 05:58:37 +0000130
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000131 if (!data) {
132 data = (SymIntExpr*) BPAlloc.Allocate<SymIntExpr>();
133 new (data) SymIntExpr(lhs, op, v, t);
134 DataSet.InsertNode(data, InsertPos);
135 }
136
137 return cast<SymIntExpr>(data);
Zhongxing Xua129eb92009-03-25 05:58:37 +0000138}
139
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000140const SymSymExpr *SymbolManager::getSymSymExpr(const SymExpr *lhs,
141 BinaryOperator::Opcode op,
142 const SymExpr *rhs,
143 QualType t) {
Zhongxing Xua129eb92009-03-25 05:58:37 +0000144 llvm::FoldingSetNodeID ID;
145 SymSymExpr::Profile(ID, lhs, op, rhs, t);
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000146 void *InsertPos;
147 SymExpr *data = DataSet.FindNodeOrInsertPos(ID, InsertPos);
Zhongxing Xua129eb92009-03-25 05:58:37 +0000148
Ted Kremeneke0e4ebf2009-03-26 03:35:11 +0000149 if (!data) {
150 data = (SymSymExpr*) BPAlloc.Allocate<SymSymExpr>();
151 new (data) SymSymExpr(lhs, op, rhs, t);
152 DataSet.InsertNode(data, InsertPos);
153 }
154
155 return cast<SymSymExpr>(data);
Zhongxing Xua129eb92009-03-25 05:58:37 +0000156}
157
Ted Kremenek9ab6b9c2009-01-22 18:23:34 +0000158QualType SymbolConjured::getType(ASTContext&) const {
159 return T;
160}
Ted Kremenekd763eb92008-02-26 02:15:56 +0000161
Zhongxing Xud9b6ad62009-05-09 04:08:27 +0000162QualType SymbolRegionValue::getType(ASTContext& C) const {
Zhongxing Xu45257c32009-06-19 06:00:32 +0000163 if (!T.isNull())
164 return T;
165
Ted Kremenek9ab6b9c2009-01-22 18:23:34 +0000166 if (const TypedRegion* TR = dyn_cast<TypedRegion>(R))
Zhongxing Xua82d8aa2009-05-09 03:57:34 +0000167 return TR->getValueType(C);
Ted Kremenek9ab6b9c2009-01-22 18:23:34 +0000168
169 return QualType();
Ted Kremenekd70d0b02008-02-16 01:12:31 +0000170}
171
Ted Kremenekd70d0b02008-02-16 01:12:31 +0000172SymbolManager::~SymbolManager() {}
Ted Kremenek241677a2009-01-21 22:26:05 +0000173
Ted Kremenek693de5d2009-03-23 15:42:58 +0000174bool SymbolManager::canSymbolicate(QualType T) {
175 return Loc::IsLocType(T) || T->isIntegerType();
176}
177
Ted Kremenek241677a2009-01-21 22:26:05 +0000178void SymbolReaper::markLive(SymbolRef sym) {
179 TheLiving = F.Add(TheLiving, sym);
180 TheDead = F.Remove(TheDead, sym);
181}
182
183bool SymbolReaper::maybeDead(SymbolRef sym) {
184 if (isLive(sym))
185 return false;
186
187 TheDead = F.Add(TheDead, sym);
188 return true;
189}
190
Ted Kremenek9ab6b9c2009-01-22 18:23:34 +0000191bool SymbolReaper::isLive(SymbolRef sym) {
Ted Kremenekdcb6a262009-01-22 18:51:33 +0000192 if (TheLiving.contains(sym))
193 return true;
194
195 // Interogate the symbol. It may derive from an input value to
196 // the analyzed function/method.
Zhongxing Xud9b6ad62009-05-09 04:08:27 +0000197 return isa<SymbolRegionValue>(sym);
Ted Kremenek241677a2009-01-21 22:26:05 +0000198}
Ted Kremenek5216ad72009-02-14 03:16:10 +0000199
200SymbolVisitor::~SymbolVisitor() {}