aboutsummaryrefslogtreecommitdiff
path: root/Analysis/ValueState.h
blob: 5458ab86e59ca4ee09fae30af9329a642b98ed6f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
//== ValueState.h - Path-Sens. "State" for tracking valuues -----*- C++ -*--==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This files defines SymbolID, ExprBindKey, and ValueState.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CLANG_ANALYSIS_VALUESTATE_H
#define LLVM_CLANG_ANALYSIS_VALUESTATE_H

// FIXME: Reduce the number of includes.

#include "clang/Analysis/PathSensitive/RValues.h"
#include "clang/Analysis/PathSensitive/GRCoreEngine.h"
#include "clang/AST/Expr.h"
#include "clang/AST/Decl.h"
#include "clang/AST/ASTContext.h"
#include "clang/Analysis/Analyses/LiveVariables.h"

#include "llvm/Support/Casting.h"
#include "llvm/Support/DataTypes.h"
#include "llvm/ADT/APSInt.h"
#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/ImmutableMap.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/Support/Allocator.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Streams.h"

#include <functional>

namespace clang {

//===----------------------------------------------------------------------===//
// ValueState - An ImmutableMap type Stmt*/Decl*/Symbols to RVals.
//===----------------------------------------------------------------------===//

namespace vstate {
  typedef llvm::ImmutableSet<llvm::APSInt*> IntSetTy;
  
  typedef llvm::ImmutableMap<Expr*,RVal>                   ExprBindingsTy;
  typedef llvm::ImmutableMap<VarDecl*,RVal>                VarBindingsTy;  
  typedef llvm::ImmutableMap<SymbolID,IntSetTy>            ConstNotEqTy;
  typedef llvm::ImmutableMap<SymbolID,const llvm::APSInt*> ConstEqTy;
}

/// ValueStateImpl - This class encapsulates the actual data values for
///  for a "state" in our symbolic value tracking.  It is intended to be
///  used as a functional object; that is once it is created and made
///  "persistent" in a FoldingSet its values will never change.
class ValueStateImpl : public llvm::FoldingSetNode {
private:
  void operator=(const ValueStateImpl& R) const;

public:
  vstate::ExprBindingsTy   SubExprBindings;
  vstate::ExprBindingsTy   BlockExprBindings;  
  vstate::VarBindingsTy    VarBindings;
  vstate::ConstNotEqTy     ConstNotEq;
  vstate::ConstEqTy        ConstEq;
  
  /// This ctor is used when creating the first ValueStateImpl object.
  ValueStateImpl(vstate::ExprBindingsTy  EB,  vstate::VarBindingsTy VB,
                 vstate::ConstNotEqTy CNE, vstate::ConstEqTy  CE)
    : SubExprBindings(EB), 
      BlockExprBindings(EB),
      VarBindings(VB),
      ConstNotEq(CNE),
      ConstEq(CE) {}
  
  /// Copy ctor - We must explicitly define this or else the "Next" ptr
  ///  in FoldingSetNode will also get copied.
  ValueStateImpl(const ValueStateImpl& RHS)
    : llvm::FoldingSetNode(),
      SubExprBindings(RHS.SubExprBindings),
      BlockExprBindings(RHS.BlockExprBindings),
      VarBindings(RHS.VarBindings),
      ConstNotEq(RHS.ConstNotEq),
      ConstEq(RHS.ConstEq) {} 
  
  /// Profile - Profile the contents of a ValueStateImpl object for use
  ///  in a FoldingSet.
  static void Profile(llvm::FoldingSetNodeID& ID, const ValueStateImpl& V) {
    V.SubExprBindings.Profile(ID);
    V.BlockExprBindings.Profile(ID);
    V.VarBindings.Profile(ID);
    V.ConstNotEq.Profile(ID);
    V.ConstEq.Profile(ID);
  }

  /// Profile - Used to profile the contents of this object for inclusion
  ///  in a FoldingSet.
  void Profile(llvm::FoldingSetNodeID& ID) const {
    Profile(ID, *this);
  }
  
};
  
/// ValueState - This class represents a "state" in our symbolic value
///  tracking. It is really just a "smart pointer", wrapping a pointer
///  to ValueStateImpl object.  Making this class a smart pointer means that its
///  size is always the size of a pointer, which allows easy conversion to
///  void* when being handled by GRCoreEngine.  It also forces us to unique states;
///  consequently, a ValueStateImpl* with a specific address will always refer
///  to the unique state with those values.
class ValueState {
  ValueStateImpl* Data;
public:
  ValueState(ValueStateImpl* D) : Data(D) {}
  ValueState() : Data(0) {}
  
  // Accessors.  
  ValueStateImpl* getImpl() const { return Data; }
  ValueStateImpl& operator*() { return *Data; }
  ValueStateImpl* operator->() { return Data; }

  // Typedefs.
  typedef vstate::IntSetTy                 IntSetTy;
  typedef vstate::ExprBindingsTy           ExprBindingsTy;
  typedef vstate::VarBindingsTy            VarBindingsTy;
  typedef vstate::ConstNotEqTy          ConstNotEqTy;
  typedef vstate::ConstEqTy             ConstEqTy;

  typedef llvm::SmallVector<ValueState,5>  BufferTy;

  // Queries.
  
  bool isNotEqual(SymbolID sym, const llvm::APSInt& V) const;
  const llvm::APSInt* getSymVal(SymbolID sym) const;
  
  // Iterators.

  typedef VarBindingsTy::iterator vb_iterator;
  vb_iterator vb_begin() const { return Data->VarBindings.begin(); }
  vb_iterator vb_end() const { return Data->VarBindings.end(); }
    
  typedef ExprBindingsTy::iterator seb_iterator;
  seb_iterator seb_begin() const { return Data->SubExprBindings.begin(); }
  seb_iterator seb_end() const { return Data->SubExprBindings.end(); }
  
  typedef ExprBindingsTy::iterator beb_iterator;
  beb_iterator beb_begin() const { return Data->BlockExprBindings.begin(); }
  beb_iterator beb_end() const { return Data->BlockExprBindings.end(); }
  
  typedef ConstNotEqTy::iterator cne_iterator;
  cne_iterator cne_begin() const { return Data->ConstNotEq.begin(); }
  cne_iterator cne_end() const { return Data->ConstNotEq.end(); }
  
  typedef ConstEqTy::iterator ce_iterator;
  ce_iterator ce_begin() const { return Data->ConstEq.begin(); }
  ce_iterator ce_end() const { return Data->ConstEq.end(); }
  
  // Profiling and equality testing.
  
  bool operator==(const ValueState& RHS) const {
    return Data == RHS.Data;
  }
  
  static void Profile(llvm::FoldingSetNodeID& ID, const ValueState& V) {
    ID.AddPointer(V.getImpl());
  }
  
  void Profile(llvm::FoldingSetNodeID& ID) const {
    Profile(ID, *this);
  }
  
  void printDOT(std::ostream& Out) const;
  void print(std::ostream& Out) const;
  void printStdErr() const { print(*llvm::cerr); }
  
};  
  
template<> struct GRTrait<ValueState> {
  static inline void* toPtr(ValueState St) {
    return reinterpret_cast<void*>(St.getImpl());
  }  
  static inline ValueState toState(void* P) {    
    return ValueState(static_cast<ValueStateImpl*>(P));
  }
};    
  
class ValueStateManager {
public:
  typedef ValueState StateTy;

private:
  ValueState::IntSetTy::Factory        ISetFactory;
  ValueState::ExprBindingsTy::Factory  EXFactory;
  ValueState::VarBindingsTy::Factory   VBFactory;
  ValueState::ConstNotEqTy::Factory    CNEFactory;
  ValueState::ConstEqTy::Factory       CEFactory;
  
  /// StateSet - FoldingSet containing all the states created for analyzing
  ///  a particular function.  This is used to unique states.
  llvm::FoldingSet<ValueStateImpl> StateSet;

  /// ValueMgr - Object that manages the data for all created RVals.
  ValueManager ValMgr;

  /// SymMgr - Object that manages the symbol information.
  SymbolManager SymMgr;

  /// Alloc - A BumpPtrAllocator to allocate states.
  llvm::BumpPtrAllocator& Alloc;
  
private:
  
  ValueState::ExprBindingsTy Remove(ValueState::ExprBindingsTy B, Expr* E) {
    return EXFactory.Remove(B, E);
  }    
    
  ValueState::VarBindingsTy  Remove(ValueState::VarBindingsTy B, VarDecl* V) {
    return VBFactory.Remove(B, V);
  }

  inline ValueState::ExprBindingsTy Remove(const ValueStateImpl& V, Expr* E) {
    return Remove(V.BlockExprBindings, E);
  }
  
  inline ValueState::VarBindingsTy Remove(const ValueStateImpl& V, VarDecl* D) {
    return Remove(V.VarBindings, D);
  }
                  
  ValueState BindVar(ValueState St, VarDecl* D, RVal V);
  ValueState UnbindVar(ValueState St, VarDecl* D);  
  
public:  
  ValueStateManager(ASTContext& Ctx, llvm::BumpPtrAllocator& alloc) 
    : ISetFactory(alloc), 
      EXFactory(alloc),
      VBFactory(alloc),
      CNEFactory(alloc),
      CEFactory(alloc),
      ValMgr(Ctx, alloc),
      Alloc(alloc) {}
  
  ValueState getInitialState();
        
  ValueManager& getValueManager() { return ValMgr; }
  SymbolManager& getSymbolManager() { return SymMgr; }
  
  ValueState RemoveDeadBindings(ValueState St, Stmt* Loc, 
                                const LiveVariables& Liveness);
  
  ValueState RemoveSubExprBindings(ValueState St) {
    ValueStateImpl NewSt = *St;
    NewSt.SubExprBindings = EXFactory.GetEmptyMap();
    return getPersistentState(NewSt);    
  }
  
  ValueState SetRVal(ValueState St, Expr* E, RVal V,
                     bool isBlkExpr, bool Invalidate);
  
  ValueState SetRVal(ValueState St, LVal LV, RVal V);

  RVal GetRVal(ValueState St,<