blob: 5ddcfb6b99f0d3260f23d0533da7f0a16b9cfd1e [file] [log] [blame]
Ted Kremeneka90ccfe2008-01-31 19:34:24 +00001//== ValueState.h - Path-Sens. "State" for tracking valuues -----*- 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//
Ted Kremenekd70b62e2008-02-08 20:29:23 +000010// This files defines SymbolID, ExprBindKey, and ValueState.
Ted Kremeneka90ccfe2008-01-31 19:34:24 +000011//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_CLANG_ANALYSIS_VALUESTATE_H
15#define LLVM_CLANG_ANALYSIS_VALUESTATE_H
16
17// FIXME: Reduce the number of includes.
18
19#include "RValues.h"
20
Ted Kremenek4d4dd852008-02-13 17:41:41 +000021#include "clang/Analysis/PathSensitive/GRCoreEngine.h"
Ted Kremeneka90ccfe2008-01-31 19:34:24 +000022#include "clang/AST/Expr.h"
23#include "clang/AST/Decl.h"
24#include "clang/AST/ASTContext.h"
25#include "clang/Analysis/Analyses/LiveVariables.h"
26
27#include "llvm/Support/Casting.h"
28#include "llvm/Support/DataTypes.h"
29#include "llvm/ADT/APSInt.h"
30#include "llvm/ADT/FoldingSet.h"
31#include "llvm/ADT/ImmutableMap.h"
32#include "llvm/ADT/SmallVector.h"
33#include "llvm/ADT/SmallPtrSet.h"
34#include "llvm/Support/Allocator.h"
35#include "llvm/Support/Compiler.h"
36#include "llvm/Support/Streams.h"
37
38#include <functional>
39
Ted Kremeneke7d22112008-02-11 19:21:59 +000040namespace clang {
Ted Kremeneka90ccfe2008-01-31 19:34:24 +000041
42//===----------------------------------------------------------------------===//
43// ValueState - An ImmutableMap type Stmt*/Decl*/Symbols to RValues.
44//===----------------------------------------------------------------------===//
45
Ted Kremenek9153f732008-02-05 07:17:49 +000046namespace vstate {
Ted Kremenek174aea42008-02-05 18:51:06 +000047 typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy;
48
Ted Kremeneke7d22112008-02-11 19:21:59 +000049 typedef llvm::ImmutableMap<Expr*,RValue> ExprBindingsTy;
Ted Kremenek016f52f2008-02-08 21:10:02 +000050 typedef llvm::ImmutableMap<VarDecl*,RValue> VarBindingsTy;
Ted Kremenek862d5bb2008-02-06 00:54:14 +000051 typedef llvm::ImmutableMap<SymbolID,IntSetTy> ConstantNotEqTy;
52 typedef llvm::ImmutableMap<SymbolID,const llvm::APSInt*> ConstantEqTy;
Ted Kremenek9153f732008-02-05 07:17:49 +000053}
Ted Kremenek6f886bd2008-02-05 18:24:17 +000054
55/// ValueStateImpl - This class encapsulates the actual data values for
56/// for a "state" in our symbolic value tracking. It is intended to be
57/// used as a functional object; that is once it is created and made
58/// "persistent" in a FoldingSet its values will never change.
Ted Kremeneka40ba022008-02-06 02:50:36 +000059class ValueStateImpl : public llvm::FoldingSetNode {
60private:
61 void operator=(const ValueStateImpl& R) const;
62
63public:
Ted Kremeneke7d22112008-02-11 19:21:59 +000064 vstate::ExprBindingsTy SubExprBindings;
65 vstate::ExprBindingsTy BlockExprBindings;
Ted Kremenek53c641a2008-02-08 03:02:48 +000066 vstate::VarBindingsTy VarBindings;
Ted Kremenek174aea42008-02-05 18:51:06 +000067 vstate::ConstantNotEqTy ConstantNotEq;
Ted Kremenek862d5bb2008-02-06 00:54:14 +000068 vstate::ConstantEqTy ConstantEq;
Ted Kremenek9153f732008-02-05 07:17:49 +000069
Ted Kremenek174aea42008-02-05 18:51:06 +000070 /// This ctor is used when creating the first ValueStateImpl object.
Ted Kremenek016f52f2008-02-08 21:10:02 +000071 ValueStateImpl(vstate::ExprBindingsTy EB,
72 vstate::VarBindingsTy VB,
Ted Kremenek862d5bb2008-02-06 00:54:14 +000073 vstate::ConstantNotEqTy CNE,
74 vstate::ConstantEqTy CE)
Ted Kremeneke7d22112008-02-11 19:21:59 +000075 : SubExprBindings(EB),
76 BlockExprBindings(EB),
77 VarBindings(VB),
78 ConstantNotEq(CNE),
79 ConstantEq(CE) {}
Ted Kremenek9153f732008-02-05 07:17:49 +000080
Ted Kremenek174aea42008-02-05 18:51:06 +000081 /// Copy ctor - We must explicitly define this or else the "Next" ptr
82 /// in FoldingSetNode will also get copied.
Ted Kremenek9153f732008-02-05 07:17:49 +000083 ValueStateImpl(const ValueStateImpl& RHS)
Ted Kremenek6f886bd2008-02-05 18:24:17 +000084 : llvm::FoldingSetNode(),
Ted Kremeneke7d22112008-02-11 19:21:59 +000085 SubExprBindings(RHS.SubExprBindings),
86 BlockExprBindings(RHS.BlockExprBindings),
Ted Kremenek53c641a2008-02-08 03:02:48 +000087 VarBindings(RHS.VarBindings),
Ted Kremenek862d5bb2008-02-06 00:54:14 +000088 ConstantNotEq(RHS.ConstantNotEq),
89 ConstantEq(RHS.ConstantEq) {}
Ted Kremenek9153f732008-02-05 07:17:49 +000090
Ted Kremeneka40ba022008-02-06 02:50:36 +000091
92
Ted Kremenek174aea42008-02-05 18:51:06 +000093 /// Profile - Profile the contents of a ValueStateImpl object for use
94 /// in a FoldingSet.
Ted Kremenek9153f732008-02-05 07:17:49 +000095 static void Profile(llvm::FoldingSetNodeID& ID, const ValueStateImpl& V) {
Ted Kremeneke7d22112008-02-11 19:21:59 +000096 V.SubExprBindings.Profile(ID);
97 V.BlockExprBindings.Profile(ID);
Ted Kremenek53c641a2008-02-08 03:02:48 +000098 V.VarBindings.Profile(ID);
Ted Kremenek862d5bb2008-02-06 00:54:14 +000099 V.ConstantNotEq.Profile(ID);
100 V.ConstantEq.Profile(ID);
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000101 }
Ted Kremenek174aea42008-02-05 18:51:06 +0000102
103 /// Profile - Used to profile the contents of this object for inclusion
104 /// in a FoldingSet.
Ted Kremenek9153f732008-02-05 07:17:49 +0000105 void Profile(llvm::FoldingSetNodeID& ID) const {
106 Profile(ID, *this);
107 }
108
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000109};
110
Ted Kremenek6f886bd2008-02-05 18:24:17 +0000111/// ValueState - This class represents a "state" in our symbolic value
112/// tracking. It is really just a "smart pointer", wrapping a pointer
113/// to ValueStateImpl object. Making this class a smart pointer means that its
114/// size is always the size of a pointer, which allows easy conversion to
Ted Kremenek4d4dd852008-02-13 17:41:41 +0000115/// void* when being handled by GRCoreEngine. It also forces us to unique states;
Ted Kremenek6f886bd2008-02-05 18:24:17 +0000116/// consequently, a ValueStateImpl* with a specific address will always refer
117/// to the unique state with those values.
Ted Kremeneka40ba022008-02-06 02:50:36 +0000118class ValueState {
Ted Kremenek9153f732008-02-05 07:17:49 +0000119 ValueStateImpl* Data;
120public:
Ted Kremeneked900212008-02-05 18:17:58 +0000121 ValueState(ValueStateImpl* D) : Data(D) {}
Ted Kremeneka40ba022008-02-06 02:50:36 +0000122 ValueState() : Data(0) {}
Ted Kremeneked900212008-02-05 18:17:58 +0000123
Ted Kremenekcba2e432008-02-05 19:35:18 +0000124 // Accessors.
Ted Kremeneked900212008-02-05 18:17:58 +0000125 ValueStateImpl* getImpl() const { return Data; }
Ted Kremeneke7d22112008-02-11 19:21:59 +0000126 ValueStateImpl& operator*() { return *Data; }
127 ValueStateImpl* operator->() { return Data; }
Ted Kremenek174aea42008-02-05 18:51:06 +0000128
Ted Kremenekcba2e432008-02-05 19:35:18 +0000129 // Typedefs.
Ted Kremenek862d5bb2008-02-06 00:54:14 +0000130 typedef vstate::IntSetTy IntSetTy;
Ted Kremenek016f52f2008-02-08 21:10:02 +0000131 typedef vstate::ExprBindingsTy ExprBindingsTy;
132 typedef vstate::VarBindingsTy VarBindingsTy;
Ted Kremenekcba2e432008-02-05 19:35:18 +0000133 typedef vstate::ConstantNotEqTy ConstantNotEqTy;
Ted Kremenek862d5bb2008-02-06 00:54:14 +0000134 typedef vstate::ConstantEqTy ConstantEqTy;
135
Ted Kremenekcba2e432008-02-05 19:35:18 +0000136 typedef llvm::SmallVector<ValueState,5> BufferTy;
Ted Kremenek174aea42008-02-05 18:51:06 +0000137
Ted Kremenek862d5bb2008-02-06 00:54:14 +0000138 // Queries.
139
140 bool isNotEqual(SymbolID sym, const llvm::APSInt& V) const;
141 const llvm::APSInt* getSymVal(SymbolID sym) const;
142
Ted Kremenek174aea42008-02-05 18:51:06 +0000143 // Iterators.
144
Ted Kremeneke7d22112008-02-11 19:21:59 +0000145 typedef VarBindingsTy::iterator vb_iterator;
146 vb_iterator vb_begin() const { return Data->VarBindings.begin(); }
147 vb_iterator vb_end() const { return Data->VarBindings.end(); }
148
149 typedef ExprBindingsTy::iterator seb_iterator;
150 seb_iterator seb_begin() const { return Data->SubExprBindings.begin(); }
151 seb_iterator seb_end() const { return Data->SubExprBindings.end(); }
Ted Kremenek016f52f2008-02-08 21:10:02 +0000152
Ted Kremeneke7d22112008-02-11 19:21:59 +0000153 typedef ExprBindingsTy::iterator beb_iterator;
154 beb_iterator beb_begin() const { return Data->BlockExprBindings.begin(); }
155 beb_iterator beb_end() const { return Data->BlockExprBindings.end(); }
Ted Kremenek9153f732008-02-05 07:17:49 +0000156
Ted Kremeneked900212008-02-05 18:17:58 +0000157 // Profiling and equality testing.
158
Ted Kremenek9153f732008-02-05 07:17:49 +0000159 bool operator==(const ValueState& RHS) const {
160 return Data == RHS.Data;
161 }
162
163 static void Profile(llvm::FoldingSetNodeID& ID, const ValueState& V) {
164 ID.AddPointer(V.getImpl());
165 }
166
167 void Profile(llvm::FoldingSetNodeID& ID) const {
168 Profile(ID, *this);
169 }
Ted Kremeneke7d22112008-02-11 19:21:59 +0000170
171 void printDOT(std::ostream& Out) const;
172 void print(std::ostream& Out) const;
173 void print() const { print(*llvm::cerr); }
174
Ted Kremenek9153f732008-02-05 07:17:49 +0000175};
176
177template<> struct GRTrait<ValueState> {
178 static inline void* toPtr(ValueState St) {
179 return reinterpret_cast<void*>(St.getImpl());
180 }
181 static inline ValueState toState(void* P) {
182 return ValueState(static_cast<ValueStateImpl*>(P));
183 }
184};
185
Ted Kremeneke070a1d2008-02-04 21:59:01 +0000186
187class ValueStateManager {
188public:
189 typedef ValueState StateTy;
190
191private:
Ted Kremenek862d5bb2008-02-06 00:54:14 +0000192 ValueState::IntSetTy::Factory ISetFactory;
Ted Kremenek016f52f2008-02-08 21:10:02 +0000193 ValueState::ExprBindingsTy::Factory EXFactory;
194 ValueState::VarBindingsTy::Factory VBFactory;
Ted Kremenek174aea42008-02-05 18:51:06 +0000195 ValueState::ConstantNotEqTy::Factory CNEFactory;
Ted Kremenek862d5bb2008-02-06 00:54:14 +0000196 ValueState::ConstantEqTy::Factory CEFactory;
Ted Kremenek174aea42008-02-05 18:51:06 +0000197
198 /// StateSet - FoldingSet containing all the states created for analyzing
199 /// a particular function. This is used to unique states.
Ted Kremenek9153f732008-02-05 07:17:49 +0000200 llvm::FoldingSet<ValueStateImpl> StateSet;
Ted Kremeneke070a1d2008-02-04 21:59:01 +0000201
202 /// ValueMgr - Object that manages the data for all created RValues.
203 ValueManager ValMgr;
Ted Kremenek9153f732008-02-05 07:17:49 +0000204
Ted Kremeneke070a1d2008-02-04 21:59:01 +0000205 /// SymMgr - Object that manages the symbol information.
206 SymbolManager SymMgr;
Ted Kremenek9153f732008-02-05 07:17:49 +0000207
208 /// Alloc - A BumpPtrAllocator to allocate states.
209 llvm::BumpPtrAllocator& Alloc;
Ted Kremeneke7d22112008-02-11 19:21:59 +0000210
211private:
212
213 ValueState::ExprBindingsTy Remove(ValueState::ExprBindingsTy B, Expr* E) {
214 return EXFactory.Remove(B, E);
215 }
216
217 ValueState::VarBindingsTy Remove(ValueState::VarBindingsTy B, VarDecl* V) {
218 return VBFactory.Remove(B, V);
219 }
Ted Kremenek9153f732008-02-05 07:17:49 +0000220
Ted Kremeneke7d22112008-02-11 19:21:59 +0000221 inline ValueState::ExprBindingsTy Remove(const ValueStateImpl& V, Expr* E) {
222 return Remove(V.BlockExprBindings, E);
223 }
224
225 inline ValueState::VarBindingsTy Remove(const ValueStateImpl& V, VarDecl* D) {
226 return Remove(V.VarBindings, D);
227 }
228
229 ValueState BindVar(ValueState St, VarDecl* D, const RValue& V);
230 ValueState UnbindVar(ValueState St, VarDecl* D);
Ted Kremeneke070a1d2008-02-04 21:59:01 +0000231
232public:
Ted Kremenek9153f732008-02-05 07:17:49 +0000233 ValueStateManager(ASTContext& Ctx, llvm::BumpPtrAllocator& alloc)
Ted Kremenek8158a0e2008-02-11 23:12:59 +0000234 : ISetFactory(alloc),
235 EXFactory(alloc),
236 VBFactory(alloc),
237 CNEFactory(alloc),
238 CEFactory(alloc),
239 ValMgr(Ctx, alloc), Alloc(alloc) {}
Ted Kremeneke070a1d2008-02-04 21:59:01 +0000240
Ted Kremeneke7d22112008-02-11 19:21:59 +0000241 ValueState getInitialState();
Ted Kremeneke070a1d2008-02-04 21:59:01 +0000242
243 ValueManager& getValueManager() { return ValMgr; }
244 SymbolManager& getSymbolManager() { return SymMgr; }
245
Ted Kremeneke7d22112008-02-11 19:21:59 +0000246 ValueState RemoveDeadBindings(ValueState St, Stmt* Loc,
247 const LiveVariables& Liveness);
Ted Kremenekb87d9092008-02-08 19:17:19 +0000248
Ted Kremeneke7d22112008-02-11 19:21:59 +0000249 ValueState RemoveSubExprBindings(ValueState St) {
250 ValueStateImpl NewSt = *St;
251 NewSt.SubExprBindings = EXFactory.GetEmptyMap();
252 return getPersistentState(NewSt);
253 }
254
255
256 ValueState SetValue(ValueState St, Expr* S, bool isBlkExpr, const RValue& V);
257 ValueState SetValue(ValueState St, const LValue& LV, const RValue& V);
Ted Kremeneke070a1d2008-02-04 21:59:01 +0000258
Ted Kremeneke7d22112008-02-11 19:21:59 +0000259 RValue GetValue(ValueState St, Expr* S, bool* hasVal = NULL);
260 RValue GetValue(ValueState St, const LValue& LV, QualType* T = NULL);
261 LValue GetLValue(ValueState St, Expr* S);
Ted Kremenekb87d9092008-02-08 19:17:19 +0000262
Ted Kremeneke7d22112008-02-11 19:21:59 +0000263 ValueState getPersistentState(const ValueStateImpl& Impl);
Ted Kremenek016f52f2008-02-08 21:10:02 +0000264
Ted Kremeneke7d22112008-02-11 19:21:59 +0000265 ValueState AddEQ(ValueState St, SymbolID sym, const llvm::APSInt& V);
266 ValueState AddNE(ValueState St, SymbolID sym, const llvm::APSInt& V);
Ted Kremeneke070a1d2008-02-04 21:59:01 +0000267};
268
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000269} // end clang namespace
270
Ted Kremeneka90ccfe2008-01-31 19:34:24 +0000271#endif