ROSE  0.9.9.109
partitionedAnalysis.h
1 #ifndef PARTITIONED_ANALYSIS_H
2 #define PARTITIONED_ANALYSIS_H
3 
4 #include <sage3.h>
5 
6 #include "genericDataflowCommon.h"
7 #include "variables.h"
8 #include "cfgUtils.h"
9 #include "analysisCommon.h"
10 #include "functionState.h"
11 #include "latticeFull.h"
12 #include "analysis.h"
13 #include "dataflow.h"
14 #include "VirtualCFGIterator.h"
15 #include "LogicalCond.h"
16 #include "printAnalysisStates.h"
17 
18 #include <list>
19 #include <sstream>
20 #include <iostream>
21 #include <fstream>
22 #include <string>
23 #include <vector>
24 
25 //class partition
26 //{
27 // // The analysis that is this partition.
28 // IntraPartitionDataflow* analysis;
29 //
30 // // The current execution state of the analysis.
31 // IntraPartitionDataflowCheckpoint* chkpt;
32 //}
33 
36 
37 // Set of partition dataflow analyses that were split in a given call to split.
38 // The original analysis that was split is explicitly identified as the "master" of the split.
39 class partSplit
40 {
41  public:
42  std::set<IntraPartitionDataflow*> splitSet;
43  IntraPartitionDataflow* master;
44 
46  {
47  this->master = master;
48  splitSet.insert(master);
49  }
50 
51  void addChild(IntraPartitionDataflow* child)
52  {
53  splitSet.insert(child);
54  }
55 
56  std::string str(std::string indent="")
57  {
58  std::ostringstream oss;
59 
60  oss << indent << "[partSplit:\n";
61  oss << indent << " splitSet = <";
62  for(std::set<IntraPartitionDataflow*>::iterator it=splitSet.begin(); it!=splitSet.end(); )
63  {
64  oss << (*it);
65  it++;
66  if(it!=splitSet.end()) oss << ", ";
67  }
68  oss << ">\n";
69  oss << indent << " master = "<< master << "]\n";
70 
71  return oss.str();
72  }
73 };
74 
76 {
77  // the partitions that are currently executing
78  std::set<IntraPartitionDataflow*> activeParts;
79  // the set of partitions that are currently blocked and need to be explicitly
80  // unblocked before they may resume execution
81  //std::set<IntraPartitionDataflow*> blockedParts;
82  // the set of partitions that have called join and are simply waiting to be joined
83  // to the master partitions that they split from
84  std::set<IntraPartitionDataflow*> joinParts;
85 
86  // Maps partitions to their respective splits. A given partition may be split
87  // multiple times in a hierarchical fashion (split-join). The first split
88  // in the list corresponds to the outer-most split and the last split
89  // is the inner-most split. Thus, if a given partition performs a join,
90  // the jointed split is the last/inner-most split in parts2splits.
91  std::map<IntraPartitionDataflow*, std::list<partSplit*> > parts2splits;
92 
93  // Maps analysis partitions to their respective current execution states
94  // (these are only upto-date for analyses that are currently stopped)
95  std::map<IntraPartitionDataflow*, IntraPartitionDataflowCheckpoint*> parts2chkpts;
96 
97  // Sample interprocedural analysis object that we'll use as a factory to create more such objects
98  IntraPartitionDataflow* intraFactory;
99 
100  public:
101  // Creates a PartitionedAnalysis, starting the analysis with the given
102  // master analysis partition and creating an initial split that only contains the master.
104 
105  // Create the initial partition state for analyzing some function
106  void initMaster();
107 
108  // Returns a reference to the master dataflow analysis. At the end of the partitioned analysis,
109  // it is this object that owns all the dataflow state generated by the overall analysis.
110  IntraPartitionDataflow* getMasterDFAnalysis();
111 
112  // Activates the given partition, returning true if it was previously inactive and false otherwise.
113  bool activatePart(IntraPartitionDataflow* part);
114 
115  // Splits the given dataflow analysis partition into several partitions, one for each given checkpoint
116  // The partition origA will be assigned the last checkpoint in partitionChkpts.
117  // If newSplit==true, this split operation creates a new split within origA's current split and place
118  // the newly-generated partitions into this split.
119  // If newSplit==false, the newly-generated partitions will be added to origA's current split.
120  // If newPartActive==true, the newly-generated partitions will be made initially active. If not,
121  // they will start out in joined status.
122  // Returns the set of newly-created partitions.
123  std::set<IntraPartitionDataflow*> split(IntraPartitionDataflow* origA, std::vector<IntraPartitionDataflowCheckpoint*> partitionChkpts,
124  const Function& func, NodeState* fState, bool newSplit, bool newPartActive);
125 
126  // Joins all the analysis partitions in a given split into a single partition, unioning
127  // their respective dataflow information
129  const Function& func, NodeState* fState);
130 
131  // Called by the base PartitionedAnalysis class when all partitions in a given split have decided
132  // to join to decide whether they should be joined or all released. It may also do some
133  // processing of their state prior to the release or join.
134  // Returns the set of partitions that will remain in joined status after this join. If all partitions in the split
135  // set are on this list, they are all joined(all but one will be deleted). Any remaining partitions will be released.
136  virtual std::set<IntraPartitionDataflow*> preJoin(partSplit* s, const Function& func, NodeState* fState,
137  const std::map<IntraPartitionDataflow*,
138  IntraPartitionDataflowCheckpoint*>& parts2chkpts)=0;
139 
140  // Called by the base PartitionedAnalysis class when all partitions in a given split have
141  // finished their respective executions.
142  virtual void postFinish(partSplit* s,
143  const std::map<IntraPartitionDataflow*, IntraPartitionDataflowCheckpoint*>& parts2chkpts)=0;
144 
145  // runs the intra-procedural analysis on the given function, returns true if
146  // the function's NodeState gets modified as a result and false otherwise
147  // state - the function's NodeState
148  bool runAnalysis(const Function& func, NodeState* state);
149 };
150 
151 // Given a source analysis, splits the dataflow states of all the CFG nodes in
152 // a given function so that the target analysis gets copies of the source analysis'
153 // state.
155 {
156  Analysis* srcAnalysis;
157  Analysis* tgtAnalysis;
158 
159  public:
160  partitionDFAnalysisState(Analysis* srcAnalysis, Analysis* tgtAnalysis)
161  {
162  this->srcAnalysis = srcAnalysis;
163  this->tgtAnalysis = tgtAnalysis;
164  }
165 
166  void visit(const Function& func, const DataflowNode& n, NodeState& state)
167  {
168  state.cloneAnalysisState(srcAnalysis, tgtAnalysis);
169  }
170 };
171 
172 // Given a set of analyses, one of which is designated as a master, unions together the
173 // dataflow states associated on each CFG node with each of these analyses.
174 // The results are associated on each CFG node with the master analysis.
176 {
177  std::set<Analysis*> unionSet;
178  Analysis* master;
179 
180  public:
182  std::set<Analysis*>& unionSet, Analysis* master)
183  {
184  for(std::set<Analysis*>::iterator it = unionSet.begin(); it!=unionSet.end(); it++)
185  { this->unionSet.insert(*it); }
186  //this->unionSet = unionSet;
187  this->master = master;
188  }
189 
190  void visit(const Function& func, const DataflowNode& n, NodeState& state);
191 };
192 
193 // Deletes all the state associated with the given analyses
195 {
196  std::set<IntraPartitionDataflow*> tgtA;
197 
198  public:
199  deleteDFAnalysisState(std::set<IntraPartitionDataflow*>& tgtA)
200  {
201  this->tgtA = tgtA;
202  }
203 
204  void visit(const Function& func, const DataflowNode& n, NodeState& state)
205  {
206  for(std::set<IntraPartitionDataflow*>::iterator it = tgtA.begin(); it!=tgtA.end(); it++)
207  state.deleteState((Analysis*)*it);
208  }
209 };
210 
211 
213 {
214  protected:
215  PartitionedAnalysis* parent;
216 
217  public:
218  // The logic expression that describes the invariant that holds for this partition
219  /*LogicalCond*/printable* partitionCond;
220 
222  {
223  parent = that.parent;
224  partitionCond = that.partitionCond;
225  }
226 
228  {
229  this->parent = parent;
230  partitionCond = NULL;
231  }
232 
234  {
235  delete partitionCond;
236  }
237 
238 /* IntraPartitionDataflow()
239  {
240  parent = NULL;
241  }
242 
243  void setParent(PartitionedAnalysis* parent)
244  {
245  this->parent = parent;
246  }*/
247 
248  PartitionedAnalysis* getParent() const
249  {
250  return parent;
251  }
252 
253  // A dummy analysis that is associated with facts connected with the
254  // IntraPartitionDataflow-specific logic rather than the logic of a class that
255  // derives from IntraPartitionDataflow.
256  // Analysis* dummy;
257 
258  // Creates a new instance of the derived object that is a copy of the original instance.
259  // This instance will be used to instantiate a new partition of the analysis.
260  virtual IntraPartitionDataflow* copy()=0;
261 
262  virtual bool runAnalysis(const Function& func, NodeState* fState, bool& splitPart,
263  bool &joinPart, IntraPartitionDataflowCheckpoint*& outChkpt)=0;
264 
265  // Resumes the execution of runAnalysis from the given checkpoint
266  // splitPart - set by the call to indicate that it exited because it was split
267  // joinPart - set by the call to indicate that it exited because it wishes to join the partitions that it split from
268  // outChkpt - set by the call to be the checkpoint that representing the state of this analysis at the time of the exit
269  // set to NULL in the case of a normal exit or a split exit
270  virtual bool runAnalysisResume(const Function& func, NodeState* fState,
271  IntraPartitionDataflowCheckpoint* chkpt, bool& splitPart,
272  bool &joinPart, IntraPartitionDataflowCheckpoint*& outChkpt)=0;
273 
274  // Called when a partition is created to allow a specific analysis to initialize
275  // its dataflow information from the partition condition
276  virtual void initDFfromPartCond(const Function& func, const DataflowNode& n, NodeState& state,
277  const std::vector<Lattice*>& dfInfo, const std::vector<NodeFact*>& facts,
278  /*LogicalCond*/printable* partitionCond) {}
279 };
280 
282 {
283  public:
284  // A checkpoint of the dataflow state associated with the given state of the dataflow analysis
285  dataflow::checkpoint dfChkpt;
286  // Set of nodes that this analysis has blocked progress on until the next join point
287  std::set<DataflowNode> joinNodes;
288  // The DataflowNode that that analysis was processing when the checkpoint was taken
289  DataflowNode* curNode;
290  // The logical condition that is an invariant of all the states of the dataflow analysis
291  /*LogicalCond*/printable* partitionCond;
292  // Given that the current node in the dataflow analysis has one or more successors, the index of
293  // the given node's successor
294  int partitionIndex;
295 
296  // the arguments to runAnalysis() used as part of the dataflow pass
297  const Function& func;
298  NodeState* fState;
299 
301  dfChkpt(that.dfChkpt), func(that.func)
302  {
303  this->joinNodes = that.joinNodes;
304  if(that.curNode)
305  this->curNode = new DataflowNode(*(that.curNode));
306  else
307  this->curNode = NULL;
308 
309  this->partitionCond = that.partitionCond;
310  this->partitionIndex = that.partitionIndex;
311  this->fState = that.fState;
312  }
313 
314  IntraPartitionDataflowCheckpoint(dataflow::checkpoint& dfChkpt, const std::set<DataflowNode>& joinNodes,
315  const DataflowNode* curNode,
316  /*LogicalCond*/printable* partitionCond, int partitionIndex,
317  const Function& func, NodeState* fState) :
318  dfChkpt(dfChkpt), func(func)
319  {
320  this->joinNodes = joinNodes;
321  if(curNode)
322  this->curNode = new DataflowNode(*curNode);
323  else
324  this->curNode = NULL;
325 
326  this->partitionCond = partitionCond;
327  this->partitionIndex = partitionIndex;
328  this->fState = fState;
329  }
330 
332  {
333  //delete partitionCond;
334  if(curNode)
335  delete curNode;
336  }
337 
338  std::string str(std::string indent="")
339  {
340  std::ostringstream outs;
341  outs << indent << "[IntraPartitionDataflowCheckpoint : \n"; //fflush(stdout);
342  outs << indent << " dfChkpt = \n"<<dfChkpt.str(indent+" ")<<"\n";
343  if(curNode)
344  outs << indent << " curNode = <"<<curNode->getNode()->class_name()<<" | "<<curNode->getNode()->unparseToString()<<" | "<< curNode->getIndex() << ">\n";
345  else
346  outs << indent << " curNode = NULL\n";
347 
348  if(joinNodes.size()==0)
349  outs << indent << " joinNodes = None\n";
350  else
351  {
352  outs << indent << " joinNodes = \n";
353  for(std::set<DataflowNode>::iterator it=joinNodes.begin(); it!=joinNodes.end(); it++)
354  { outs << indent << " <"<<(*it).getNode()->class_name()<<" | "<<(*it).getNode()->unparseToString()<<">\n"; }
355  }
356  if(partitionCond)
357  outs << indent << " partitionCond = \n"<<partitionCond->str(indent+" ")<<"\n";
358 
359  if(partitionIndex>=0)
360  outs << indent << " partitionIndex = descendant "<<partitionIndex<<"]";
361  else
362  outs << indent << " partitionIndex = all descendants ("<<partitionIndex<<")]";
363  return outs.str();
364  }
365 };
366 
368 {
369  protected:
370  //std::vector<<Lattice*> initState;
371 
372  //std::map <DataflowNode, Lattice*> nodeState;
373  //std::map<DataflowNode, std::list<Lattice*> > nodeState;
374 
375  public:
377  { }
378 
381  {
382  //this->initState = that.initState;
383  }
384 
385  /*IntraPartitionFWDataflow(): IntraPartitionDataflow()
386  { }*/
387 
388  // the transfer function that is applied to every node
389  // n - the dataflow node that is being processed
390  // state - the NodeState object that describes the state of the node, as established by earlier
391  // analysis passes
392  // dfInfo - the Lattices that this transfer function operates on. The function takes these lattices
393  // as input and overwrites them with the result of the transfer.
394  // splitAnalysis - set by callee to
395  // - noSplit if the analysis does not want a split
396  // - splitNew if the analysis wants to perform a split and place the newly-generated partitions into
397  // a fresh split set that is nested inside this partition's current split
398  // - splitParent if the analysis wants to perform a split and place the newly-generated partitions
399  // into this partition's current split (i.e. on the same split level as the current partition)
400  typedef enum {noSplit, splitNew, splitParent} splitType;
401  // splitConditions - if splitAnalysis==splitNew or ==splitParent, the analysis sets this vector to the conditions for all the
402  // descendant CFG nodes in the split
403  /* // joinAnalysis - set to true if the analysis wants to perform a join */
404  // joinNode - set to true if progress along the given dataflow node needs to be blocked until the next join point.
405  // If all paths of dataflow progress are blocked in this analysis, this is the same as the analysis
406  // requesting to be joined.
407  // Returns true if any of the input lattices changed as a result of the transfer function and
408  // false otherwise.
409  virtual bool transfer(const Function& func, const DataflowNode& n, NodeState& state, const std::vector<Lattice*>& dfInfo,
410  splitType& splitAnalysis, std::vector</*LogicalCond*/printable*>& splitConditions, /*bool& joinAnalysis, */bool& joinNode)=0;
411 
412  // Runs the intra-procedural analysis on the given function. Returns true if
413  // the function's NodeState gets modified as a result and false otherwise.
414  // state - the function's NodeState
415  bool runAnalysis(const Function& func, NodeState* fState, bool analyzeDueToCallers, std::set<Function> calleesUpdated);
416 
417  // Runs the intra-procedural analysis on the given function.
418  // Returns true if the function's NodeState gets modified as a result and false otherwise.
419  // state - the function's NodeState
420  bool runAnalysis(const Function& func, NodeState* fState,
421  bool& splitPart, bool &joinPart, IntraPartitionDataflowCheckpoint*& outChkpt);
422 
423  // Resumes the execution of runAnalysis from the given checkpoint
424  bool runAnalysisResume(const Function& func, NodeState* fState,
425  IntraPartitionDataflowCheckpoint* chkpt, bool& splitPart,
426  bool &joinPart, IntraPartitionDataflowCheckpoint*& outChkpt);
427 
428  typedef enum {retFalse, cont, normal} partitionTranferRet;
429 
430  partitionTranferRet partitionTranfer(
431  const Function& func, NodeState* fState, const DataflowNode& n, NodeState* state, VirtualCFG::dataflow& dfIt,
432  const std::vector<Lattice*>& dfInfoBelow, bool& splitPart, std::set<DataflowNode>& joinNodes,
434 
435  // propagates the forward dataflow info from the current node's NodeState (curNodeState) to the next node's
436  // NodeState (nextNodeState)
437  bool propagateFWStateToNextNode(
438  const std::vector<Lattice*>& curNodeState, DataflowNode curDFNode, int nodeIndex,
439  const std::vector<Lattice*>& nextNodeState, DataflowNode nextDFNode);
440 };
441 
442 #endif
virtual std::string unparseToString(SgUnparse_Info *info) const
This function unparses the AST node (excluding comments and unnecessary white space) ...
virtual std::string class_name() const
returns a string representing the class name