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