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