ROSE  0.9.9.109
nodeState.h
1 #ifndef NODE_STATE_H
2 #define NODE_STATE_H
3 
4 #include "DataflowCFG.h"
5 class NodeFact;
6 class NodeState;
7 
8 #include "lattice.h"
9 #include "analysis.h"
10 #include <map>
11 #include <vector>
12 #include <string>
13 #include <set>
14 
15 #ifdef THREADED
16 #include "tbb/concurrent_hash_map.h"
17 #include "tbb/atomic.h"
18 #endif
19 
20 
21 //template<class factType>
22 /************************************************
23  *** NodeFact ***
24  *** A fact associated with a CFG node by ***
25  *** some analysis thatis not evolved as part ***
26  *** of a dataflow analysis (i.e. it should ***
27  *** stay constant throughout the analysis). ***
28  ************************************************/
29 // A fact associated with a CFG node that is not part of a dataflow analysis. In other words,
30 // it is not a lattice and is not meant to evolve during the course of a dataflow analysis.
31 class NodeFact: public printable
32 {
33  public:
34 
35  // The string that represents this object.
36  // Every line of this string must be prefixed by indent.
37  // The last character of the returned string must not be '\n', even if it is a multi-line string.
38  //virtual string str(string indent="")=0;
39 
40  // returns a copy of this node fact
41  virtual NodeFact* copy() const=0;
42 
43 /* void* fact;
44 
45  public:
46  NodeFact(void* fact)
47  {
48  this->fact = fact;
49  }
50 
51  NodeFact(factType* fact)
52  {
53  this->fact = *fact;
54  }
55 
56  void* getFact()
57  {
58  return fact;
59  }*/
60 };
61 
62 
63 /**********************************************
64  *** NodeState ***
65  *** The state of all the Lattice elements ***
66  *** associated by dataflow analyses with a ***
67  *** given node. This state will evolve as ***
68  *** a result of the dataflow analysis. ***
69  **********************************************/
70 #ifdef THREADED
71 class NodeStateHashCompare
72 {
73  public:
74  NodeStateHashCompare() {}
75  NodeStateHashCompare(const NodeStateHashCompare & that) {}
76 
77  ~NodeStateHashCompare(){}
78 
79  static bool equal(const Analysis* & j, const Analysis* & k )
80  { return j==k; }
81 
82  static bool equal(const Analysis* const & j, const Analysis* const & k )
83  { return j==k; }
84 
85  static size_t hash( const Analysis* k ) { return (size_t) k; }
86 };
87 #endif
88 
89 class NodeState
90 {
91  #ifdef THREADED
92  typedef tbb::concurrent_hash_map <Analysis*, std::vector<Lattice*>, NodeStateHashCompare > LatticeMap;
93  //typedef tbb::concurrent_hash_map <Analysis*, map <int, NodeFact*>, NodeStateHashCompare > NodeFactMap;
94  typedef tbb::concurrent_hash_map <Analysis*, std::vector<NodeFact*>, NodeStateHashCompare > NodeFactMap;
95  typedef tbb::concurrent_hash_map <Analysis*, bool, NodeStateHashCompare > BoolMap;
96  #else
97  typedef std::map<Analysis*, std::vector<Lattice*> > LatticeMap;
98  //typedef std::map<Analysis*, std::map<int, NodeFact*> > NodeFactMap;
99  typedef std::map<Analysis*, std::vector<NodeFact*> > NodeFactMap;
100  typedef std::map<Analysis*, bool > BoolMap;
101  #endif
102 
103  // the dataflow information Above the node, for each analysis that
104  // may be interested in the current node
105  LatticeMap dfInfoAbove;
106 
107  // the Analysis information Below the node, for each analysis that
108  // may be interested in the current node
109  LatticeMap dfInfoBelow;
110 
111  // the facts that are true at this node, for each analysis that
112  // may be interested in the current node
113  NodeFactMap facts;
114 
115  // Contains all the Analyses that have initialized their state at this node. It is a map because
116  // TBB doesn't provide a concurrent set.
117  BoolMap initializedAnalyses;
118 
119  // the dataflow node that this NodeState object corresponds to
120  //DataflowNode parentNode;
121 
122  public:
123  /*NodeState(DataflowNode& parentNode) : parentNode(parentNode)
124  {}
125 
126  NodeState(CFGNode& parentNode) : parentNode(parentNode)
127  {}
128 
129  NodeState(CFGNode parentNode) : parentNode(parentNode)
130  {}*/
131 
132  NodeState()
133  {}
134 
135 /* void initialize(Analysis* analysis, int latticeName)
136  {
137  initDfMap(dfInfoAbove);
138  initDfMap(dfInfoBelow);
139  }
140 
141  private:
142  // initializes the given lattice owned by the given analysis in the given map
143  // dfMap may be either dfInfoAbove or dfInfoBelow
144  void initDfMap(std::map<Analysis*, std::vector<Lattice*> >& dfMap)
145  {
146  std::map<Analysis*, std::vector<Lattice*> >::iterator dfLattices;
147  // if this analysis has registered some Lattices at this node
148  if((dfLattices = dfMap.find(analysis)) != dfInfoAbove.end())
149  {
150  std::map<int, Lattice>::iterator it;
151  // if the given lattice name was registered by this analysis
152  if((it = (*dfLattices).find(latticeName) != (*dfLattices).end())
153  {
154  (*it)->initialize();
155  }
156  else
157  {
158  (*dfLattices)[latticeName] = new Lattice();
159  }
160  }
161  else
162  {
163  std::map<int, Lattice> newMap;
164  Lattice newLattice;
165  newMap[latticeName] = newLattice;
166  dfMap[analysis] = newMap;
167  }
168  }*/
169 
170  public:
171  // Records that this analysis has initializedAnalyses its state at this node
172  void initialized(Analysis* analysis);
173 
174  // Returns true if this analysis has initialized its state at this node and false otherwise
175  bool isInitialized(Analysis* analysis);
176 
177  // adds the given lattice, organizing it under the given analysis and lattice name
178  //void addLattice(const Analysis* analysis, int latticeName, Lattice* l);
179 
180 
181  // Set this node's lattices for this analysis (possibly above or below only, replacing previous mappings)
182  // These methods take ownership of the pointed-to lattices.
183  void setLattices(const Analysis* analysis, std::vector<Lattice*>& lattices);
184  void setLatticeAbove(const Analysis* analysis, std::vector<Lattice*>& lattices);
185  void setLatticeBelow(const Analysis* analysis, std::vector<Lattice*>& lattices);
186 
187  // returns the given lattice from above the node that is owned by the given analysis
188  Lattice* getLatticeAbove(const Analysis* analysis, int latticeName) const;
189  // returns the given lattice from below the node that is owned by the given analysis
190  Lattice* getLatticeBelow(const Analysis* analysis, int latticeName) const;
191 
193  // (read-only access)
194  static const std::vector<Lattice*>& getLatticeAbove(const Analysis* analysis, SgNode* n, unsigned int index ) ;
195 
196  // returns all the lattices from below the CFG node (corresponding to SgNode and an CFG index) that are owned by the given analysis
197  // (read-only access)
198  static const std::vector<Lattice*>& getLatticeBelow(const Analysis* analysis, SgNode* n, unsigned int index) ;
199 
200 
201  // returns the map containing all the lattices from above the node that are owned by the given analysis
202  // (read-only access)
203  const std::vector<Lattice*>& getLatticeAbove(const Analysis* analysis) const;
204  // returns the map containing all the lattices from below the node that are owned by the given analysis
205  // (read-only access)
206  const std::vector<Lattice*>& getLatticeBelow(const Analysis* analysis) const;
207 
208  // returns the map containing all the lattices from above the node that are owned by the given analysis
209  // (read/write access)
210  std::vector<Lattice*>& getLatticeAboveMod(const Analysis* analysis);
211  // returns the map containing all the lattices from below the node that are owned by the given analysis
212  // (read/write access)
213  std::vector<Lattice*>& getLatticeBelowMod(const Analysis* analysis);
214 
215  // deletes all lattices above this node associated with the given analysis
216  void deleteLatticeAbove(const Analysis* analysis);
217 
218  // deletes all lattices below this node associated with the given analysis
219  void deleteLatticeBelow(const Analysis* analysis);
220 
221  // returns true if the two lattices vectors are the same and false otherwise
222  static bool eqLattices(const std::vector<Lattice*>& latticesA,
223  const std::vector<Lattice*>& latticesB);
224 
225  // Creates a copy of all the dataflow state (Lattices and Facts) associated with
226  // analysis srcA and associates this copied state with analysis tgtA.
227  void cloneAnalysisState(const Analysis* srcA, const Analysis* tgtA);
228 
229  // Given a set of analyses, one of which is designated as a master, unions together the
230  // lattices associated with each of these analyses. The results are associated on each
231  // CFG node with the master analysis.
232  void unionLattices(std::set<Analysis*>& unionSet, const Analysis* master);
233 
234  //void removeLattice(const Analysis* analysis, int latticeName);
235 
236  private:
237  /*// adds the given lattice to the given dfInfo structure (dfInfoAbove or dfInfoBelow),
238  // organizing it under the given analysis and lattice name
239  void addLattice_ex(std::map<Analysis*, std::vector<Lattice*> >& dfMap,
240  const Analysis* analysis, int latticeName, Lattice* l);
241  */
242  // returns the given lattice, which owned by the given analysis
243  Lattice* getLattice_ex(const LatticeMap& dfMap,
244  const Analysis* analysis, int latticeName) const;
245 
246  /*// removes the given lattice, owned by the given analysis
247  // returns true if the given lattice was found and removed and false if it was not found
248  bool removeLattice_ex(LatticeMap& dfMap,
249  const Analysis* analysis, int latticeName);
250  */
251  public:
252  // associates the given analysis/fact name with the given NodeFact,
253  // deleting any previous association (the previous NodeFact is freed)
254  void addFact(const Analysis* analysis, int factName, NodeFact* f);
255 
256  // associates the given analysis with the given map of fact names to NodeFacts,
257  // deleting any previous association (the previous NodeFacts are freed). This call
258  // takes the actual provided facts and does not make a copy of them.
259  //void setFacts(const Analysis* analysis, const std::map<int, NodeFact*>& newFacts);
260  void setFacts(const Analysis* analysis, const std::vector<NodeFact*>& newFacts);
261 
262  // returns the given fact, which owned by the given analysis
263  NodeFact* getFact(const Analysis* analysis, int factName) const ;
264 
265  // returns the map of all the facts owned by the given analysis at this NodeState
266  // (read-only access)
267  //const std::map<int, NodeFact*>& getFacts(const Analysis* analysis) const;
268  const std::vector<NodeFact*>& getFacts(const Analysis* analysis) const;
269 
270  // returns the map of all the facts owned by the given analysis at this NodeState
271  // (read/write access)
272  //std::map<int, NodeFact*>& getFactsMod(const Analysis* analysis);
273  std::vector<NodeFact*>& getFactsMod(const Analysis* analysis);
274 
275  // removes the given fact, owned by the given analysis
276  // returns true if the given fact was found and removed and false if it was not found
277  //bool removeFact(const Analysis* analysis, int factName);
278 
279  // deletes all facts at this node associated with the given analysis
280  void deleteFacts(const Analysis* analysis);
281 
282  // delete all state at this node associated with the given analysis
283  void deleteState(const Analysis* analysis);
284 
285  // ====== STATIC ======
286  private:
287  static std::map<DataflowNode, std::vector<NodeState*> > nodeStateMap;
288  static bool nodeStateMapInit;
289 
290  public:
291  // returns the NodeState object associated with the given dataflow node.
292  // index is used when multiple NodeState objects are associated with a given node
293  // (ex: SgFunctionCallExp has 3 NodeStates: entry, function body, exit)
294  static NodeState* getNodeState(const DataflowNode& n, int index=0);
295 
296 
297  //returns the NodeState object associated with a given SgNode
298  //index is used when multiple Control flow nodes (and consequently multiple NodeStates) are associated with a given node
299  static NodeState* getNodeState(SgNode * n, int index=0);
300 
301  // returns a vector of NodeState objects associated with the given dataflow node.
302  static const std::vector<NodeState*> getNodeStates(const DataflowNode& n);
303 
304  // returns the number of NodeStates associated with the given DataflowNode
305  static int numNodeStates(DataflowNode& n);
306 
307  private:
308  // initializes the nodeStateMap
309  static void initNodeStateMap(bool (*filter) (CFGNode cfgn));
310 
311  public:
312  /*// copies the facts from that to this
313  void copyFacts(NodeState &that);
314 
315  // copies the dfInfoBelow lattices from that to this
316  void copyLatticesBelow(NodeState &that);
317 
318  // copies the dfInfoAbove lattices from the given map to this
319  void copyLatticesAbove(const LatticeMap& thatInfo);
320 
321  // copies the dfInfoBelow lattices from the given map to this
322  void copyLatticesBelow(const LatticeMap& thatInfo);
323 
324  protected:
325  // copies the dfInfoAbove or dfInfoBelow lattices from that to this
326  void copyLattices(const LatticeMap& dfInfo,
327  const LatticeMap& thatInfo);
328  */
329 
330  // copies from's above lattices for the given analysis to to's above lattices for the same analysis
331  static void copyLattices_aEQa(Analysis* analysis, NodeState& to, const NodeState& from);
332 
333  // copies from's above lattices for analysisA to to's above lattices for analysisB
334  static void copyLattices_aEQa(Analysis* analysisA, NodeState& to, Analysis* analysisB, const NodeState& from);
335 
336  // copies from's above lattices for the given analysis to to's below lattices for the same analysis
337  static void copyLattices_bEQa(Analysis* analysis, NodeState& to, const NodeState& from);
338 
339  // copies from's above lattices for analysisA to to's below lattices for analysisB
340  static void copyLattices_bEQa(Analysis* analysisA, NodeState& to, Analysis* analysisB, const NodeState& from);
341 
342  // copies from's below lattices for the given analysis to to's below lattices for the same analysis
343  static void copyLattices_bEQb(Analysis* analysis, NodeState& to, const NodeState& from);
344 
345  // copies from's below lattices for the given analysis to to's above lattices for the same analysis
346  static void copyLattices_aEQb(Analysis* analysis, NodeState& to, const NodeState& from);
347 
348  protected:
349  // makes dfInfoX a copy of dfInfoY
350  static void copyLattices(std::vector<Lattice*>& dfInfoX, const std::vector<Lattice*>& dfInfoY);
351 
352  /*public:
353  void operator=(NodeState& that);*/
354  public:
355  std::string str(Analysis* analysis, std::string indent="") const;
356 };
357 
358 #endif
A node in the control flow graph.
Definition: virtualCFG.h:67
This class represents the base class for all IR nodes within Sage III.
Definition: Cxx_Grammar.h:8322
Definition: lattice.h:9