ROSE  0.9.9.109
graphProcessingSgIncGraph.h
1 /*
2 
3 FINISH TEMPFLATPATH CODE
4 
5 */
6 
7 
8 
9 
10 // Original Author (SgGraphTraversal mechanisms): Michael Hoffman
11 //$id$
12 #include<omp.h>
13 #include <boost/regex.hpp>
14 #include <iostream>
15 #include <fstream>
16 #include <string>
17 
71 #include "staticCFG.h"
72 #include <vector>
73 #include <algorithm>
74 #include <utility>
75 #include <iostream>
76 #include <sys/time.h>
77 #include <sys/resource.h>
78 //#include "graphBot.h"
79 
80 //This is necessary for technical reasons with regards to the graphnodeinheritedmap
81 
82 
83 
84 struct Bot {
85  std::vector<std::vector<SgGraphNode*> > path;
86  std::vector<std::set<SgGraphNode*> > pthloops;
87  std::vector<SgGraphNode*> currpth;
88  std::vector<std::pair<SgGraphNode*, int> > nodelst;
89  bool on;
90  bool remove;
91 };
92 
93 double timeDifference(const struct timeval& end, const struct timeval& begin)
94 {
95  return (end.tv_sec + end.tv_usec / 1.0e6) - (begin.tv_sec + begin.tv_usec / 1.0e6);
96 }
97 
98 static inline timeval getCPUTime() {
99  rusage ru;
100  getrusage(RUSAGE_SELF, &ru);
101  return ru.ru_utime;
102 }
103 
104 
106  bool operator()(const SgGraphNode* a, const SgGraphNode* b) const
107  {
108  return a==b;
109  }
110 };
111 
112 
113 /* The SgGraphTraversal class is utilized specifically for StaticCFG traversals,
114 though the input must be in terms of a SgIncidenceDirectedGraph*/
115 template <class InheritedAttributeType, class SynthesizedAttributeType>
116 class SgGraphTraversal
117 {
118  public:
119  std::set<std::map<int, std::set<int> > > subpathmap;
120  int loopNum;
121  int nullNum;
122  std::set<SgDirectedGraphEdge*> nullEdgesOrdered;
123  std::map<SgGraphNode*, int> loopNumMap;
124  std::map<SgGraphNode*, int> pathValMap;
125  int nullloops;
126  std::vector<std::vector<SgGraphNode*> > looppaths;
127  std::vector<std::vector<SgGraphNode*> > iLoops;
128  std::vector<SgGraphNode*> ifstatements;
129  virtual ~SgGraphTraversal();
130  SgGraphTraversal();
131  // Copy operations
132  int nullEdgesPaths;
133  int turns;
135  const SgGraphTraversal &operator=(const SgGraphTraversal &);
136  //This is not used, but will be important if SynthesizedAttributes become useful
137  typedef StackFrameVector<SynthesizedAttributeType> SynthesizedAttributesList;
138  //one of the most important structures in the algorithm, this attaches SgGraphNode*s to InheritedAttributeTypes so that
139  //looking up the values is possible.
140  //int numnodes;
141  //std::map<SgGraphNode*, InheritedAttributeType> seen;
142  int numnodes;
143  //InheritedAttributeType pthgraphinherit;
144  //StaticCFG::CFG* SgCFG;
145  SgGraphNode* nullnode;
146  std::map<SgGraphNode*, int> primenode;
147  bool done;
148  //std::set<SgGraphNode*> startnodes;
149  std::set<SgGraphNode*> lstN;
150  std::map<SgGraphNode*, std::vector<std::set<int> > > lstordmap;
151  std::set<SgGraphNode*> solvedLoops;
152  std::map<SgGraphNode*, std::vector<SgGraphNode*> > checkednodes;
153  std::map<SgGraphNode*, std::set<SgGraphNode*> > downed;
154 
155  //std::map<SgGraphNode*, int> nodeinedgordmap;
156  //a value for nodes that have no value, set in the traverse function
157  InheritedAttributeType nullInherit;
158  //the user invoked function, runs the algorithm
159  InheritedAttributeType traverse(SgGraphNode* basenode, SgIncidenceDirectedGraph* g,
160  InheritedAttributeType inheritedValue, InheritedAttributeType nullInherit,
161  SgGraphNode* endnode, bool insep = false, bool pcHk = false);
162  std::set<SgGraphNode*> loopSet;
163 
164  protected:
165  //User defined functions to do whatever is needed in evaluation
166  //All the user gets access to is the node in question
167  //and the values of the parent nodes (this should be all that is necessary)
168  virtual InheritedAttributeType evaluateInheritedAttribute(SgGraphNode* n,
169  std::vector<InheritedAttributeType> inheritedValues) = 0;
170  //Not used, but may be useful if SynthesizedAttributes become workable in this context
171  virtual SynthesizedAttributeType evaluateSynthesizedAttribute(SgGraphNode* n,
172  InheritedAttributeType in,
173  SynthesizedAttributesList l) = 0;
174 
175 #if !USE_ROSE
176  // DQ (11/3/2011): EDG compilains about this (but GNU allowed it, I think that EDG might be correct,
177  // namely that the value of a reference must be an lvalue (not NULL). But since we are only trying
178  // to compile ROSE with ROSE (using the new EDG 4.3 front-end as a tests) we can just skip this case for now.
179  virtual void pathAnalyze(std::vector<SgGraphNode*>& pth, bool loop=false, std::set<std::vector<SgGraphNode*> >& incloops=NULL) = 0;
180 #else
181  virtual void pathAnalyze(std::vector<SgGraphNode*>& pth, bool loop, std::set<std::vector<SgGraphNode*> >& incloops) = 0;
182 #endif
183 
184  //also not used, but important for possible later use of SynthesizedAttributes
185  SynthesizedAttributeType defaultSynthesizedAttribute(InheritedAttributeType);
186  private:
187  double distime;
188  //std::set<std::pair<std::pair<SgGraphNode*, SgGraphNode*>, std::pair<SgGraphNode*, SgGraphNode*> > > flpset;
189  //std::set<std::pair<std::pair<SgGraphNode*, SgGraphNode*>, std::pair<SgGraphNode*, SgGraphNode*> > > goodset;
190  std::set<SgGraphNode*> ploops;
191  std::map<SgGraphNode*, std::set<std::vector<SgGraphNode*> > > lpbegins;
192  std::map<SgGraphNode*, int> frksLeft;
193  int currm;
194  int dpMax;
195  int repEval;
196  bool pathCheck;
197  int pathsSize;
198  //this constructs the graph tree for computation of inheritedValues
199 
200 
201  std::map<SgGraphNode*, InheritedAttributeType> known;
202  std::vector<InheritedAttributeType> connectNodes;
203  std::map<SgGraphNode*, bool> solved;
204  std::set<SgGraphNode*> solvedset;
205  //these two are not used, but will be important if SynthesizedAttributes are made reasonable in this context
206  SynthesizedAttributesList *synthesizedAttributes;
207  SynthesizedAttributeType traversalResult();
208  //finally we have two functions necessary for parallel processing if that is chosen to be used by the user
209 
210 
211 
212 
213  std::map<SgGraphNode*, int> nodeInEdgesNum;
214  int currprime;
215  std::vector<SgGraphNode*> endnodefakes;
216  std::map<SgGraphNode*, std::vector<std::vector<SgGraphNode*> > > pathsAtMk;
217  std::set<SgGraphNode*> mkloops;
218  std::map<SgGraphNode*, std::set<std::vector<SgGraphNode*> > > mkloopmap;
219  std::map<SgGraphNode*, std::set<std::vector<SgGraphNode*> > > subPathsAtMk;
220  std::vector<SgGraphNode*> mkglobal;
221  std::vector<SgGraphNode*> clglobal;
222  bool inseparable;
223  void solvePaths(SgIncidenceDirectedGraph* g, SgGraphNode* n, SgGraphNode* endnode);
224  std::vector<std::set<SgGraphNode*> > closuresVec;
225  void evaluatePaths(SgIncidenceDirectedGraph* g, SgGraphNode* realstartnode, SgGraphNode* endnode);
226  void evaluatePathsPar(SgIncidenceDirectedGraph* g, SgGraphNode* realstartnode, SgGraphNode* endnode);
227  bool disjoint(std::vector<SgGraphNode*>& path, std::vector<SgGraphNode*>& vec2) const;
228  std::set<std::vector<SgGraphNode*> > flatpaths;
229 // void evalNode(SgIncidenceDirectedGraph* g, SgGraphNode* n);
230  bool canSolve(SgIncidenceDirectedGraph* g, SgGraphNode* n);
231  std::map<SgGraphNode*, InheritedAttributeType> inhVals;
232  std::set<SgDirectedGraphEdge*> seenEdges;
233  std::set<SgDirectedGraphEdge*> nullEdges;
234  std::set<SgGraphNode*> clsT;
235  void computeOrder(SgIncidenceDirectedGraph* g, SgGraphNode* n, SgGraphNode* endnode);
236  void computeInheritedOrdered(SgIncidenceDirectedGraph* g, SgGraphNode* n);
237  std::pair<bool, SgGraphNode*> getNextPar(SgIncidenceDirectedGraph* g, SgGraphNode* n);
238  std::pair<bool, SgGraphNode*> getNextChild(SgIncidenceDirectedGraph* g, SgGraphNode* n);
239  bool computable(SgIncidenceDirectedGraph* g, SgGraphNode* n);
240  void evalNodeOrdered(SgIncidenceDirectedGraph* g, SgGraphNode* n);
241  std::map<SgGraphNode*, int> oVals;
242  bool canEval(SgIncidenceDirectedGraph* g, SgGraphNode* n);
243  void setPathVal(SgIncidenceDirectedGraph*g, SgGraphNode* n);
244  void printNodePlusEdgesForAnalysis(SgIncidenceDirectedGraph* g, SgGraphNode* n, int loopNum, int pathVal, std::ofstream& ss);
245  void printNodePlusEdgesForAnalysisPath(SgIncidenceDirectedGraph* g, std::vector<SgGraphNode*> n, int loopNum, int pathVal, std::ofstream& ss);
246  void printNodeForAnalysis(SgGraphNode* n, int loopNum, int pathNum, std::ofstream& ss);
247  std::set<SgGraphNode*> completedNodesPath;
248  std::set<std::pair<SgGraphNode*, SgGraphNode*> > completedEdgesPath;
249  void printEdgeForAnalysis(SgDirectedGraphEdge* e, bool isNullEdge, std::ofstream& ss);
250  void printEdgeForAnalysisPath(SgGraphNode* g1, SgGraphNode* g2, std::ofstream& ss);
251  std::map<int, SgGraphNode*> iVals;
252 
253  std::set<SgDirectedGraphEdge*> nullEdgesOrderedOut;
254  std::set<SgDirectedGraphEdge*> completedEdgesOut;
255  std::set<SgDirectedGraphEdge*> completedEdges;
256  std::set<SgGraphNode*> compPar;
257  std::set<SgGraphNode*> compChild;
258  std::set<SgGraphNode*> computedNodes;
259  SgGraphNode* st;
260  SgGraphNode* en;
261  double fllp;
262  int loopnum;
263  //std::set<SgGraphNode*> solved;
264  //InheritedAttributeType findAndReverse(SgGraphNode* n, SgIncidenceDirectedGraph* g);
265  //evaluateAllInheritedAttribute(std::vector<InheritedAttributeType> endNodeInhVec, SgGraphNode* endnode, std::vector<SgGraphNode*> nodes, std::vector<InheritedAttributeType> inh);
266 //std::vector<InheritedAttributeType> getZeroInhs(std::vector<std::vector<std::vector<SgGraphNode*> > > qAnsSetSet, std::vector<InheritedAttributeType> endnodeInhVec, SgGraphNode* node);
267 
268 };
269 
270 
271 
272 /*
273 template <class InheritedAttributeType, class SynthesizedAttributeType>
274 void
275 GraphBot<InheritedAttributeType, SynthesizedAttributeType>::
276 travelDown(SgIncidenceDirectedGraph* g) {
277  std::set<SgDirectedGraphEdge*> oedgs = g->computeEdgeSetOut(iAmHere);
278  bool taken = false;
279  if (oedgs.size() > 1) {
280  std::set<SgDirectedGraphEdge*> edgeTrav = clEdgeTrav[iAmHere];
281  ROSE_ASSERT(clEdgeTrav.find(iAmHere) != clEdgeTrav.end());
282  for (std::set<SgDirectedGraphEdge*>::iterator i = oedgs.begin(); i != oedgs.end(); i++) {
283  if (edgTrav.find(*i) == edgTrav.end() || !taken) {
284  taken = true;
285  iAmHere = (*i)->get_to();
286  lastEdge = *i;
287  }
288  }
289  }
290  else {
291  iAmHere = (*(oedgs.begin())->get_to();
292  }
293 }
294 */
295 
296 
297 
298 
299 
300 
301 /*
302 ***************************
303 Various Admin Functions
304 ***************************
305 */
306 template<class InheritedAttributeType, class SynthesizedAttributeType>
309  : synthesizedAttributes(new SynthesizedAttributesList())
310 {
311 }
312 
313 #ifndef SWIG
314 
315 template<class InheritedAttributeType, class SynthesizedAttributeType>
318 {
319  ROSE_ASSERT(synthesizedAttributes != NULL);
320  delete synthesizedAttributes;
321  synthesizedAttributes = NULL;
322 }
323 
324 #endif
325 
326 
327 template<class InheritedAttributeType, class SynthesizedAttributeType>
330 operator=(const SgGraphTraversal &other)
331 {
332 
333  ROSE_ASSERT(synthesizedAttributes != NULL);
334  delete synthesizedAttributes;
335  synthesizedAttributes = other.synthesizedAttributes->deepCopy();
336 
337  return *this;
338 }
339 
357 template<class InheritedAttributeType, class SynthesizedAttributeType>
358 InheritedAttributeType
360 traverse(SgGraphNode* n, SgIncidenceDirectedGraph* g, InheritedAttributeType inheritedValue, InheritedAttributeType nullI, SgGraphNode* endnode, bool insep, bool pCh) {
361  //numnodes = 0;
362  //primes.clear();
363  looppaths.clear();
364  iLoops.clear();
365  completedEdgesPath.clear();
366  pathValMap.clear();
367  loopNumMap.clear();
368  nullloops = 0;
369  nullEdgesPaths = 0;
370  fllp = 0.0;
371  mkglobal.clear();
372  clglobal.clear();
373 
374  lpbegins.clear();
375  //currents.clear();
376  inhVals.clear();
377  iVals.clear();
378  oVals.clear();
379  //reservedEdges.clear();
380  completedEdges.clear();
381  completedEdgesOut.clear();
382  //completedNodes.clear();
383  computedNodes.clear();
384  nullEdgesOrdered.clear();
385  nullEdgesOrderedOut.clear();
386  loopSet.clear();
387  pathsAtMk.clear();
388 
389  st = n;
390  en = endnode;
391  distime = 0.0;
392  int currm = 1;
393  int turns = 0;
394  pathsSize = 0;
395  done = false;
396  numnodes = 1;
397  std::cout << "starting traversal" << std::endl;
398  pathCheck = pCh;
399  currprime = 1;
400  inseparable = insep;
401  synthesizedAttributes->resetStack();
402  ROSE_ASSERT(synthesizedAttributes->debugSize() == 0);
403  //SgCFG = cfg;
404  inhVals[n] = inheritedValue;
405  //GraphBot<InheritedAttributeType, SynthesizedAttributeType>::inhVals[n] = inheritedValue;
406  //primes = generatePrimesSieve();
407 
408 
409 // graphnodeinheritedordmap[ncpy] = inheritedValue;
410 // nodenodeordmap[ncpy] = n;
411 // std::vector<SgGraphNode*> lst;
412 // lst.push_back(n);
413 // lstordmap[ncpy] = lst;
414 
415  nullInherit = nullI;
416 InheritedAttributeType inh;
417  struct timeval t1, t2, t3, t4, t5, t6, t7, t8;
418  //else {
419  loopnum = 0;
420  //InheritedAttributeType inh;
421  t1 = getCPUTime();
422 
423  //this function essentially sets up for the evaluate later, it makes putting together the paths much easier
424  solvePaths(g, n, endnode);
425 
426  t2 = getCPUTime();
427 
428 //making sure that endnode hasn't already been evaluated before the traversal starts, unlikely but just in case
429  ROSE_ASSERT(inhVals.find(endnode) == inhVals.end());
430 
431  std::cout << "solvePaths done" << std::endl;
432  double diff = timeDifference(t2, t1);
433  t5 = getCPUTime();
434  //InheritedAttributeType pthgraphinherit = botTraverse(g, n, endnode);
435  oVals[n] = 0;
436  iVals[0] = n;
437  pathValMap[n] = 1;
438 //inserting n as a computed node
439  computedNodes.insert(n);
440 //computes the order in which the nodes must be evaluated, makes computeInheritedOrdered much faster
441  computeOrder(g, n, endnode);
442  std::cout << "order computed" << std::endl;
443 //computes the nodal inheritance values
444  computeInheritedOrdered(g, n);
445  std::cout << "inheritance computed" << std::endl;
446  ROSE_ASSERT(oVals.find(endnode) != oVals.end());
447  ROSE_ASSERT(inhVals.find(endnode) != inhVals.end());
448 //value at the endnode
449  InheritedAttributeType pthgraphinherit = inhVals[endnode];
450  //= evaluateGraph(g, n, endnode, inheritedValue);
451  t6 = getCPUTime();
452  std::cout << "evaluateGraph done" << std::endl;
453  double diff3 = timeDifference(t6, t5);
454  t3 = getCPUTime();
455 //actually evaluates every path with a user defined pathAnalyze function
456  //for (int i = 0; i < 10; i++) {
457  evaluatePaths(g, n, endnode);
458  //}
459  t4 = getCPUTime();
460 
461  t7 = getCPUTime();
462  //evaluatePathsPar(g, n, endnode);
463  t8 = getCPUTime();
464 
465  std::cout << "evaluatePaths done " << std::endl;
466  double diff2 = timeDifference(t4, t3);
467  double diff2Par = timeDifference(t8, t7);
468  std::cout << "pathsolve took: " << diff << std::endl;
469  std::cout << "patheval took: " << diff2 << std::endl;
470  std::cout << "parpatheval took: " << diff2Par << std::endl;
471  std::cout << "grapheval took: " << diff3 << std::endl;
472  std::cout << "entire pathsolve took: " << diff+diff2+diff3+diff2Par << std::endl;
473  std::cout << "potential loops: " << nullEdgesOrdered.size() << std::endl;
474  std::cout << "nullNum: " << nullNum << std::endl;
475  //std::cout << "goodsets: " << goodset.size() << std::endl;
476  //std::cout << "flpsets: " << flpset.size() << std::endl;
477  std::cout << "mkloops: " << mkloops.size() << std::endl;
478  std::cout << "distime: " << distime << std::endl;
479  std::cout << "fllp: " << fllp << std::endl;
480  return pthgraphinherit;
481  //}
482  //std::cout << "number of endnodefakes: " << endnodefakes.size() << std::endl;
483  //std::cout << "should be number of nodes: " << currprime << std::endl;
484  //if (pathanalysis == true) {
485  // analyzepaths(endnode, g);
486  //}
487  //return inh;
488  //Currently this is not very useful, but it does nothing if traversalResult is not set.
489 }
490 
491 /* WARNING:
492  This is not a general is_disjoint. It skips the
493 first element of the second set because in the way I assemble
494 paths the last element of the path and the first element of addend
495 must be the same. Hence I simply skip the first node
496 */
497 bool is_disjoint(std::set<SgGraphNode*> set1, std::set<SgGraphNode*> set2) {
498 
499  if (set1.empty() || set2.empty()) {
500  return true;
501  }
502  std::set<SgGraphNode*>::iterator it1 = set1.begin();
503  std::set<SgGraphNode*>::iterator it2 = set2.begin();
504  std::set<SgGraphNode*>::iterator it1End = set1.end();
505  std::set<SgGraphNode*>::iterator it2End = set2.end();
506 
507  if (*it1 > *set2.rbegin() || *it2 > *set1.rbegin()) {
508  return true;
509  }
510 
511  while (it1 != it1End && it2 != it2End) {
512  if (*it1 == *it2) {
513  return false;
514  }
515  if (*it1 < *it2) {
516  it1++;
517  }
518  else {
519  it2++;
520  }
521  }
522  return true;
523 }
524 
525 
526 
527 //Checks for disjoint, necessary in computing the paths
528 template<class InheritedAttributeType, class SynthesizedAttributeType>
529 bool
531 disjoint(std::vector<SgGraphNode*>& pthloops, std::vector<SgGraphNode*>& vec2) const {
532 /*
533  time_t t1, t2;
534  time(&t1);
535  int a = 0;
536  std::set<SgGraphNode*> s1;
537  std::set<SgGraphNode*> s2;
538  std::vector<SgGraphNode*> mkloopvec;
539  bool goodsetbool;
540  bool pbool = true;
541  //std::cout << "calculating disjoint" << std::endl;
542  ROSE_ASSERT((path.back()).back() == vec2.front());
543 
544  //copy(vec2.begin(), vec2.end(), inserter(s2, s2.end()));
545 /*
546  for (int i = 0; i < vec2.size(); i++) {
547  if (ploops.find(vec2[i]) != ploops.end()) {
548  pbool = false;
549  }
550  }
551  if (pbool) {
552  return true;
553  }
554  if (
555 */ //for (int q = 0; q < pthloops->size(); q++) {
556  for (int i = 0; i < pthloops.size(); i++) {
557  if (find(vec2.begin(), vec2.end(), pthloops[i]) != vec2.end()) {
558  return false;
559  }
560  }
561  return true;
562 }
563 /*
564  if (pbool) {
565  time(&t2);
566  double diff = difftime(t2, t1);
567  distime += diff;
568  return true;
569  }
570  for (unsigned int k = 0; k < path.size(); k++) {
571  s1.clear();
572 */
573 /*
574  pbool = true;
575  for (int p = 0; p < path[k].size(); p++) {
576  if (ploops.find(path[k][p]) != ploops.end()) {
577  pbool = false;
578  }
579  }
580 // copy(path[k].begin(), path[k].end(), inserter(s1, s1.end()));
581  if (!pbool) {
582 */
583 /*
584  std::pair<std::pair<SgGraphNode*, SgGraphNode*>, std::pair<SgGraphNode*, SgGraphNode*> > flp;
585  flp.second.first = vec2[0];
586  flp.second.first = vec2[1];
587 
588  flp.first.first = path[k][0];
589  flp.first.second = path[k][1];
590  if (vec2.front() == vec2.back()) {
591  time(&t2);
592  double diff = difftime(t2, t1);
593  distime += diff;
594 
595  return false;
596  }
597  if (flpset.find(flp) != flpset.end()) {
598  //std::cout << "already seen" << std::endl;
599  time(&t2);
600  double diff = difftime(t2, t1);
601  distime += diff;
602 
603  return false;
604  }
605 */
606 /*
607  else if (goodset.find(flp) != goodset.end()) {
608  goodsetbool = true;
609  }
610 */
611 /*
612  if (is_disjoint(s1,s2)) {
613  //goodset.insert(flp);
614  continue;
615  }
616  else {
617  return false;
618  }
619 */
620 /*
621  else {
622  std::vector<SgGraphNode*> vec1 = path[k];
623 
624  //for (unsigned int i = 0; i < vec1.size(); i++) {
625  for (unsigned int j = 0; j < mkloopvec.size(); j++) {
626  std::vector<SgGraphNode*>::iterator q = find(vec1.begin(), vec1.end(), mkloopvec[j]);
627  if (q != vec1.end()) {
628  if (*q != vec1[vec1.size() - 1] || j != 0) {
629 
630  flpset.insert(flp);
631  // std::cout << "not disjoint" << std::endl;
632  time(&t2);
633  double diff = difftime(t2, t1);
634  distime += diff;
635 
636  return false;
637  }
638  }
639  }
640  //}
641  //goodset.insert(flp);
642  }
643  }
644  //}
645 */
646 
647 
648 /*
649  for (unsigned int p = 0; p < vec2.size(); p++) {
650  for (unsigned int q = 0; q < vec2.size(); q++) {
651  if (p != q) {
652  if (vec2[p] == vec2[q]) {
653  return false;
654  }
655  }
656  }
657  }
658 */
659 /*
660  time(&t2);
661  double diff = difftime(t2, t1);
662  distime += diff;
663 
664  return true;
665 }
666 */
667 //checks for solvability of a node in nodal analysis
668 
669 template<class InheritedAttributeType, class SynthesizedAttributeType>
670 bool
673  bool loop = false;
674  if (inhVals.find(n) != inhVals.end()) {
675  return true;
676  }
677  std::set<SgDirectedGraphEdge*> oed = g->computeEdgeSetIn(n);
678  if (oed.size() == 0) {
679  return false;
680  }
681  for (std::set<SgDirectedGraphEdge*>::iterator i = oed.begin(); i != oed.end(); i++) {
682  if (inhVals.find((*i)->get_from()) == inhVals.end() && nullEdges.find(*i) == nullEdges.end()) {
683  return false;
684  }
685  }
686  return true;
687 }
688 
689 //this function evaluates values of paths via the user-defined pathAnalyze function
690 
691 template<class InheritedAttributeType, class SynthesizedAttributeType>
692 void
695 std::vector<std::vector<SgGraphNode*> > path;
696 std::vector<SgGraphNode*> spath;
697 SgGraphNode* n = realstartnode;
698 int successes = 0;
699 int failures = 0;
700 int j = 0;
701 std::vector<SgGraphNode*> currpthorg;
702 int currint = 0;
703 std::map<SgGraphNode*, int> intPath;
704 intPath[n] = currint;
705 currint++;
706 std::map<SgGraphNode*, int> currents;
707 SgGraphNode* currnode;
708 bool step = false;
709 bool midstep = false;
710 
711 //note: pathsAtMk is referring to subpaths connected to that marker, a marker is a split in the graph (usually an if statement)
712 
713 std::vector<std::vector<SgGraphNode*> > pth = pathsAtMk[realstartnode];
714 std::vector<std::vector<SgGraphNode*> > cpth = pathsAtMk[realstartnode];
715  path.clear();
716  int disjoints = 0;
717  int disjointtrues = 0;
718  currpthorg = pth[0];
719  intPath[pth[0].front()] = currint;
720  std::set<SgGraphNode*> pthloopstmp;
721  SgGraphNode* fakenode;
722  pthloopstmp.insert(fakenode);
723  std::vector<std::set<SgGraphNode*> > pthloops;
724  pthloops.push_back(pthloopstmp);
725  pthloopstmp.clear();
726  currint++;
727 
728  int stepnum = 0;
729  std::vector<SgGraphNode*> rs;
730  rs.push_back(realstartnode);
731  path.push_back(rs);
732  currents.clear();
733 
734  step = false;
735  std::vector<SgGraphNode*> sub;
736 
737 
738  std::set<std::vector<SgGraphNode*> > nullIncLoops;
739  std::vector<struct Bot*> todobotlst;
740  std::vector<struct Bot*> botlst;
741  struct Bot* rootBot = new Bot;
742  rootBot->remove = false;
743 
744  rootBot->path = path;
745  rootBot->currpth = currpthorg;
746  rootBot->pthloops = pthloops;
747  rootBot->on = true;
748  botlst.push_back(rootBot);
749  int tip = 1;
750  int ti = 1;
751  std::vector<std::pair<std::vector<SgGraphNode*>, std::vector<std::set<SgGraphNode*> > > > collectedPaths;
752  int maxlst = 0;
753  while (true) {
754  if (todobotlst.size()+botlst.size() > maxlst) {
755  maxlst = todobotlst.size()+botlst.size();
756  std::cout << "maxlst: " << maxlst << std::endl;
757  std::cout << "todobotlst.size(): " << todobotlst.size() << std::endl;
758  std::cout << "botlst.size(): " << botlst.size() << std::endl;
759  }
760  int MAXBOTS = 10000;
761  int MINPATHS = 1000;
762  int LOCALMAXBOTS = 10;
763  int LOCALMAXNODES = 0;
764  std::vector<struct Bot*> lstnullbot;
765  std::vector<std::vector<struct Bot*> > newbotlsts (MAXBOTS, lstnullbot);
766  //std::vector<struct Bot*> newbotlsts (MAXBOTS, lstnullbot);
767  //tip = ti;
768  //ti = 0;
769  ROSE_ASSERT(botlst.size() >= 0);
770  if (botlst.size() == 0) {
771  if (todobotlst.size() != 0) {
772  while (todobotlst.size() > 0 && botlst.size() < MAXBOTS) {
773  todobotlst.back()->on = true;
774  botlst.push_back(todobotlst.back());
775  todobotlst.pop_back();
776  }
777  }
778  else {
779  if (collectedPaths.size() > 0) {
780  for (int i = 0; i < collectedPaths.size(); i++) {
781  std::set<std::vector<SgGraphNode*> > incloops;
782  std::vector<std::set<SgGraphNode*> > pthloops = collectedPaths[i].second;
783  for (int q = 0; q < pthloops.size(); q++) {
784  for (std::set<SgGraphNode*>::iterator p = pthloops[q].begin(); p != pthloops[q].end(); p++) {
785  for (std::set<std::vector<SgGraphNode*> >::iterator o = mkloopmap[*p].begin(); o != mkloopmap[*p].end(); o++) {
786  incloops.insert(*o);
787  }
788  }
789  }
790 
791 
792  pathAnalyze(collectedPaths[i].first, false, incloops);
793  }
794  collectedPaths.clear();
795  }
796  break;
797  }
798  }
799  if (botlst.size() > 0) {
800  std::pair<std::vector<SgGraphNode*>, std::vector<std::set<SgGraphNode*> > > nullpr;
801  std::vector<std::pair<std::vector<SgGraphNode*>, std::vector<std::set<SgGraphNode*> > > > newpathslst (MAXBOTS, nullpr);
802  #pragma omp parallel for
803  for (int i = 0; i < botlst.size(); i++) {
804  //std::map<SgGraphNode*, std::set<std::vector<SgGraphNode*> > > mkloopmaptmp = mkloopmap;
805  std::vector<struct Bot*> localbotlst;
806  std::pair<std::vector<SgGraphNode*>, std::vector<std::set<SgGraphNode*> > > localnewpath;
807  struct Bot* currBot = botlst[i];
808  if (currBot->on) {
809  std::vector<SgGraphNode*> currpth = currBot->currpth;
810  std::vector<std::vector<SgGraphNode*> > path = currBot->path;
811  std::vector<std::set<SgGraphNode*> > pthloops = currBot->pthloops;
812 
813  if (currpth.back() == endnode) {
814  path.push_back(currpth);
815  std::vector<SgGraphNode*> flatpath;
816  std::set<std::vector<SgGraphNode*> > incloops;
817  struct timeval q1, q2;
818  ROSE_ASSERT(path.size() == pthloops.size() + 1);
819  q1 = getCPUTime();
820  for (unsigned int q = 0; q < pthloops.size(); q++) {
821  for (unsigned int r = 0; r < path[q].size(); r++) {
822  flatpath.push_back(path[q][r]);
823  }
824 
825 /*
826 #pragma omp critical
827 {
828  for (std::set<SgGraphNode*>::iterator p = pthloops[q].begin(); p != pthloops[q].end(); p++) {
829  for (std::set<std::vector<SgGraphNode*> >::iterator o = mkloopmap[*p].begin(); o != mkloopmap[*p].end(); o++) {
830  incloops.insert(*o);
831  }
832  }
833 }
834 */
835 
836  }
837 
838  for (unsigned int pt2 = 0; pt2 < path[path.size()-1].size(); pt2++) {
839  flatpath.push_back(path[path.size()-1][pt2]);
840  }
841  q2 = getCPUTime();
842  fllp += timeDifference(q2,q1);
843  flatpath.push_back(endnode);
844 //user defined function, run on the final path, gives the user loops that are included via "incloops" a set of vectors that contain the individual loops
845 /*
846  #pragma omp critical (analyze)
847 {
848  pathAnalyze(flatpath, false, incloops);
849 }
850 */
851  std::pair<std::vector<SgGraphNode*> , std::vector<std::set<SgGraphNode*> > > newcol;
852  newcol.first = flatpath;
853  newcol.second = pthloops;
854  localnewpath = newcol;
855  incloops.clear();
856 
857  int pts = pathsSize++;
858  pathsSize += 1;
859 
860  flatpath.clear();
861  path.pop_back();
862  int rounds = 0;
863  bool starter = false;
864 
865 // This gets a bit complicated so here is an overview:
866 // This is running down the graph and finding the endnode. Once it finds the endnode it goes back up to the last unevaluated subpath. It does this quickly with an integer that counts how many times that node has been used for a path. If this ends up being the number of outnodes, we don't need that node anymore, so we clear it to zero, then continue up the graph. We HAVE to reset because every time a new pathway is chosen above that node, it needs to have the ability to traverse that node.
867 /*
868  if (currBot->nodelst.size() != 0) {
869  while (path.back().back() != currBot->nodelst.back().first) {
870  ROSE_ASSERT(path.size() != 0);
871  path.pop_back();
872  pthloops.pop_back();
873 
874  }
875  currBot->path = path;
876  currBot->pthloops = pthloops;
877  currBot->currpth = pathsAtMk[(path.back()).back()][currBot->nodelst.back().second];
878  currBot->nodelst.pop_back();
879  localbotlst.push_back(currBot);
880  }
881  else {
882 */
883  currBot->remove = true;
884  localbotlst.push_back(currBot);
885  //}
886  }
887  else {
888 
889 //this checks first to see if we have any loops in our path. If not it continues down, if there is it goes back to the last nonloop node
890  bool disj = true;
891  struct timeval tdisb, tdise;
892  //tdisb = getCPUTime();
893  for (int x = 0; x < pthloops.size(); x++) {
894  for (std::set<SgGraphNode*>::iterator j = pthloops[x].begin(); j != pthloops[x].end(); j++) {
895  if (find(currpth.begin(), currpth.end(), *j) != currpth.end()) {
896  disj = false;
897  }
898  }
899  }
900  //tdise = getCPUTime();
901  //distime += timeDifference(tdise, tdisb);
902  if (disj) {
903 
904  disjointtrues++;
905  //std::cout << "disjoints: " << disjointtrues << std::endl;
906  midstep = false;
907 std::set<SgGraphNode*> pthloopstmp;
908  pthloopstmp.clear();
909  for (int i = 0; i < currpth.size(); i++) {
910  //currflat.push_back(currpth[i]);
911  if (mkloops.find(currpth[i]) != mkloops.end()) {
912  pthloopstmp.insert(currpth[i]);
913  }
914  }
915  pthloops.push_back(pthloopstmp);
916  path.push_back(currpth);
917  pthloopstmp.clear();
918 
919  //std::set<std::vector<SgGraphNode*> > lpth;
920  std::vector<SgGraphNode*> oldcurrpth = currpth;
921  currpth.clear();
922  SgGraphNode* frontnode = (path.back()).front();
923  SgGraphNode* backnode = (path.back()).back();
924 
925  ROSE_ASSERT(pathsAtMk.find(backnode) != pathsAtMk.end() || backnode == endnode);
926  ROSE_ASSERT(pathsAtMk.find(frontnode) != pathsAtMk.end());
927  std::vector<std::vector<SgGraphNode*> > tmppths = pathsAtMk[backnode];
928  currBot->currpth = tmppths[0];
929  currBot->path = path;
930  currBot->pthloops = pthloops;
931  //newbotlst.push_back(currBot);
932  for (int tp = 1; tp < tmppths.size(); tp++) {
933  //if (localbotlst.size() < LOCALMAXBOTS) {
934 /*
935  if (currBot->nodelst.size() < LOCALMAXNODES) {
936  std::pair<SgGraphNode*, int> cur;
937  cur.second = tp;
938  cur.first = path.back().back();
939  currBot->nodelst.push_back(cur);
940  }
941  else {
942 */
943  struct Bot* newBot = new Bot;
944  newBot->remove = false;
945  newBot->currpth = tmppths[tp];
946  newBot->path = path;
947  newBot->pthloops = pthloops;
948  localbotlst.push_back(newBot);
949  //ti++;
950  // }
951  }
952  localbotlst.push_back(currBot);
953  //ti++;
954  }
955  else {
956 /*
957  if (currBot->nodelst.size() != 0) {
958  while (path.back().back() != currBot->nodelst.back().first) {
959  ROSE_ASSERT(path.size() != 0);
960  path.pop_back();
961  pthloops.pop_back();
962 
963  }
964  currBot->path = path;
965  currBot->pthloops = pthloops;
966  currBot->currpth = pathsAtMk[(path.back()).back()][currBot->nodelst.back().second];
967  currBot->nodelst.pop_back();
968  localbotlst.push_back(currBot);
969  //ti++;
970  }
971 
972  else {
973 */
974  currBot->remove = true;
975  localbotlst.push_back(currBot);
976  //delete currBot;
977  // }
978 
979  }
980  }
981  newpathslst[i] = localnewpath;
982  newbotlsts[i] = localbotlst;
983  }
984 }
985  botlst.clear();
986  int num = 0;
987 
988  for (int i = 0; i < newbotlsts.size(); i++) {
989  if (newpathslst[i].first.size() > 0) {
990  collectedPaths.push_back(newpathslst[i]);
991  }
992  for (int j = 0; j < newbotlsts[i].size(); j++) {
993  if (newbotlsts[i][j]->remove == true) {
994  delete newbotlsts[i][j];
995  }
996  else if (num < MAXBOTS) {
997  newbotlsts[i][j]->on = true;
998  botlst.push_back(newbotlsts[i][j]);
999  num++;
1000  }
1001  else {
1002  newbotlsts[i][j]->on = false;
1003  todobotlst.push_back(newbotlsts[i][j]);
1004  }
1005  }
1006 }
1007 
1008 if (collectedPaths.size() > MINPATHS) {
1009 
1010  for (int i = 0; i < collectedPaths.size(); i++) {
1011  std::vector<std::set<SgGraphNode*> > pthloops;
1012  std::set<std::vector<SgGraphNode*> > incloops;
1013  pthloops = collectedPaths[i].second;
1014  for (int q = 0; q < pthloops.size(); q++) {
1015  for (std::set<SgGraphNode*>::iterator p = pthloops[q].begin(); p != pthloops[q].end(); p++) {
1016  for (std::set<std::vector<SgGraphNode*> >::iterator o = mkloopmap[*p].begin(); o != mkloopmap[*p].end(); o++) {
1017  incloops.insert(*o);
1018  }
1019  }
1020  }
1021 
1022  pathAnalyze(collectedPaths[i].first, false, incloops);
1023  }
1024  collectedPaths.clear();
1025 }
1026 }
1027  else {
1028  if (collectedPaths.size() > 0) {
1029  for (int i = 0; i < collectedPaths.size(); i++) {
1030  std::set<std::vector<SgGraphNode*> > incloops;
1031  pthloops = collectedPaths[i].second;
1032  for (int q = 0; q < pthloops.size(); q++) {
1033  for (std::set<SgGraphNode*>::iterator p = pthloops[q].begin(); p != pthloops[q].end(); p++) {
1034  for (std::set<std::vector<SgGraphNode*> >::iterator o = mkloopmap[*p].begin(); o != mkloopmap[*p].end(); o++) {
1035  incloops.insert(*o);
1036  }
1037  }
1038  }
1039 
1040  pathAnalyze(collectedPaths[i].first, false, incloops);
1041  }
1042  }
1043  collectedPaths.clear();
1044  break;
1045  }
1046 }
1047 
1048 std::cout << "successes: " << successes << std::endl;
1049 std::cout << "failures: " << failures << std::endl;
1050 std::cout << "maxlst: " << maxlst << std::endl;
1051 return;
1052 }
1053 
1054 
1055 
1056 template<class InheritedAttributeType, class SynthesizedAttributeType>
1057 void
1059 evaluatePaths(SgIncidenceDirectedGraph* g, SgGraphNode* realstartnode, SgGraphNode* endnode) {
1060 //std::set<SgGraphNode*> seen;
1061 //for (std::map<SgGraphNode*, std::vector<std::vector<SgGraphNode*> > >::iterator i = pathsAtMk.begin(); i != pathsAtMk.end(); i++) {
1062 /*
1063  std::vector<std::vector<SgGraphNode*> > tocheck = (*i).second;
1064  for (int j = 0; j < tocheck.size(); j++) {
1065  for (int k = 0; k < tocheck[j].size(); k++) {
1066  if (seen.find(tocheck[j][k]) != seen.end()) {
1067  ploops.insert(tocheck[j][k]);
1068  }
1069  else {
1070  seen.insert(tocheck[j][k]);
1071  }
1072  }
1073  }
1074 }
1075 */
1076 std::vector<std::vector<SgGraphNode*> > path;
1077 std::vector<SgGraphNode*> spath;
1078 SgGraphNode* n = realstartnode;
1079 int successes = 0;
1080 int failures = 0;
1081 int j = 0;
1082 std::vector<SgGraphNode*> currpth;
1083 int currint = 0;
1084 std::map<SgGraphNode*, int> intPath;
1085 intPath[n] = currint;
1086 currint++;
1087 std::map<SgGraphNode*, int> currents;
1088 SgGraphNode* currnode;
1089 bool step = false;
1090 bool midstep = false;
1091 
1092 //note: pathsAtMk is referring to subpaths connected to that marker, a marker is a split in the graph (usually an if statement)
1093 
1094 std::vector<std::vector<SgGraphNode*> > pth = pathsAtMk[realstartnode];
1095 std::vector<std::vector<SgGraphNode*> > cpth = pathsAtMk[realstartnode];
1096  path.clear();
1097  int disjoints = 0;
1098  int disjointtrues = 0;
1099  currpth = pth[0];
1100  intPath[pth[0].front()] = currint;
1101  std::set<SgGraphNode*> pthloopstmp;
1102  SgGraphNode* fakenode;
1103  pthloopstmp.insert(fakenode);
1104  std::vector<std::set<SgGraphNode*> > pthloops;
1105  pthloops.push_back(pthloopstmp);
1106  pthloopstmp.clear();
1107  currint++;
1108 
1109  int stepnum = 0;
1110  std::vector<SgGraphNode*> rs;
1111  rs.push_back(realstartnode);
1112  path.push_back(rs);
1113  //currflat.push_back(realstartnode);
1114  currents.clear();
1115 
1116  step = false;
1117  //std::vector<SgGraphNode*> currflat;
1118  std::vector<SgGraphNode*> sub;
1119 
1120 /*
1121  std::ofstream mz;
1122  mz.open("pathanalysis.dot");
1123  mz << "digraph defaultName { \n";
1124 */
1125  std::set<std::vector<SgGraphNode*> > nullIncLoops;
1126 
1127 /*
1128  for (unsigned int p = 0; p < looppaths.size(); p++) {
1129  std::vector<SgGraphNode*> lp = looppaths[p];
1130 
1131  for (unsigned int i = 0; i < lp.size()-1; i++) {
1132  for (unsigned int l = i+1; l < lp.size(); l++) {
1133  if (lp[i] == lp[l] && lp[i] != realstartnode && lp[i] != endnode) {
1134  std::vector<SgGraphNode*> interiorloop;
1135  interiorloop.clear();
1136  for (unsigned int j = i; j < l+1; j++) {
1137  interiorloop.push_back(lp[j]);
1138  }
1139  if (interiorloop.size() > 2) {
1140  }
1141  if (interiorloop.size() > 2 && interiorloop.back() != endnode) {
1142  if (find(iLoops.begin(), iLoops.end(), interiorloop) == iLoops.end()) {
1143  if (find(looppaths.begin(), looppaths.end(), interiorloop) == looppaths.end()) {
1144  iLoops.push_back(interiorloop);
1145  loopnum++;
1146  for (unsigned int k = 0; k < interiorloop.size(); k++) {
1147  loopNumMap[interiorloop[k]] = loopnum;
1148  }
1149  lpbegins[interiorloop.front()].insert(interiorloop);
1150  pathAnalyze(interiorloop, true, nullIncLoops);
1151 
1152  }
1153  }
1154  }
1155  }
1156  }
1157  }
1158  if (lp.size() > 2) {
1159  lpbegins[lp.front()].insert(lp);
1160  pathAnalyze(lp, true, nullIncLoops);
1161  //for (unsigned int i = 1; i < lp.size(); i++) {
1162  // printNodePlusEdgesForAnalysisPath(g, lp, p, p, mz);
1163  //}
1164  }
1165  }
1166 */
1167  while (step == false) {
1168  stepnum++;
1169 
1170  if (currpth.back() == endnode) {
1171  path.push_back(currpth);
1172  //for (int i = 0; i < currpth.size(); i++) {
1173  // currflat.push_back(currpth[i]);
1174  //}
1175  std::vector<SgGraphNode*> flatpath;
1176  //std::vector<SgGraphNode*> sub;
1177  std::set<std::vector<SgGraphNode*> > incloops;
1178  struct timeval q1, q2;
1179  //std::cout << "path.size(): " << path.size() << std::endl;
1180  //std::cout << "pthloops.size(): " << pthloops.size() << std::endl;
1181  ROSE_ASSERT(path.size() == pthloops.size() + 1);
1182  q1 = getCPUTime();
1183  for (unsigned int q = 0; q < pthloops.size(); q++) {
1184  //sub = path[q];
1185  //sub.pop_back();
1186  for (unsigned int r = 0; r < path[q].size(); r++) {
1187  flatpath.push_back(path[q][r]);
1188  }
1189  for (std::set<SgGraphNode*>::iterator p = pthloops[q].begin(); p != pthloops[q].end(); p++) {
1190  for (std::set<std::vector<SgGraphNode*> >::iterator o = mkloopmap[*p].begin(); o != mkloopmap[*p].end(); o++) {
1191  incloops.insert(*o);
1192  }
1193  }
1194  }
1195  for (unsigned int pt2 = 0; pt2 < path[path.size()-1].size(); pt2++) {
1196  flatpath.push_back(path[path.size()-1][pt2]);
1197  }
1198 
1199  q2 = getCPUTime();
1200  fllp += timeDifference(q2,q1);
1201  flatpath.push_back(endnode);
1202 /*
1203  for (unsigned int ps = 0; ps < flatpath.size(); ps++) {
1204  if (lpbegins.find(flatpath[ps]) != lpbegins.end()) {
1205  for (std::set<std::vector<SgGraphNode*> >::iterator sv = lpbegins[flatpath[ps]].begin(); sv != lpbegins[flatpath[ps]].end(); sv++) {
1206  incloops.insert(*sv);
1207  }
1208  }
1209  }
1210 */
1211 //user defined function, run on the final path, gives the user loops that are included via "incloops" a set of vectors that contain the individual loops
1212  pathAnalyze(flatpath, false, incloops);
1213  incloops.clear();
1214  //printNodePlusEdgesForAnalysisPath(g, flatpath, -1, -1, mz);
1215 
1216  int pts = pathsSize++;
1217  pathsSize += 1;
1218 
1219  flatpath.clear();
1220  path.pop_back();
1221  int rounds = 0;
1222  bool starter = false;
1223 
1224 // This gets a bit complicated so here is an overview:
1225 // This is running down the graph and finding the endnode. Once it finds the endnode it goes back up to the last unevaluated subpath. It does this quickly with an integer that counts how many times that node has been used for a path. If this ends up being the number of outnodes, we don't need that node anymore, so we clear it to zero, then continue up the graph. We HAVE to reset because every time a new pathway is chosen above that node, it needs to have the ability to traverse that node.
1226 
1227 
1228  while (true) {
1229  rounds++;
1230  ROSE_ASSERT(pathsAtMk.find((path.back()).back()) != pathsAtMk.end());
1231  if ((path.back()).front() == realstartnode) {
1232  starter = true;
1233  }
1234  if (currents[(path.back()).back()] < (pathsAtMk[(path.back()).back()].size()) /*|| (path.back()).front() == realstartnode*/) {
1235  std::vector<std::vector<SgGraphNode*> > cpths = pathsAtMk[(path.back()).back()];
1236  currpth = cpths[currents[(path.back()).back()]];
1237  currents[(path.back()).back()]++;
1238  break;
1239  }
1240  else {
1241  currents[(path.back()).back()] = 0;
1242  path.pop_back();
1243  pthloops.pop_back();
1244  }
1245  if (starter == true) {
1246  step = true;
1247  break;
1248  }
1249 
1250  }
1251  }
1252  else {
1253 
1254 //this checks first to see if we have any loops in our path. If not it continues down, if there is it goes back to the last nonloop node
1255  bool disj = true;
1256  struct timeval tdisb, tdise;
1257  tdisb = getCPUTime();
1258  for (int i = 0; i < pthloops.size(); i++) {
1259  for (std::set<SgGraphNode*>::iterator j = pthloops[i].begin(); j != pthloops[i].end(); j++) {
1260  if (find(currpth.begin(), currpth.end(), *j) != currpth.end()) {
1261  disj = false;
1262  }
1263  }
1264  }
1265 /*
1266  #pragma omp parallel for num_threads(4) private(i,j)
1267  for (i = 0; i < pthloops.size(); i++) {
1268  if (disj) {
1269  for (std::set<SgGraphNode*>::iterator j = pthloops[i].begin(); j != pthloops[i].end(); j++) {
1270  if (find(currpth.begin(), currpth.end(), *j) != currpth.end()) {
1271  disj = false;
1272  //j = pthloops[i].size();
1273  }
1274  }
1275  }
1276 
1277  }
1278 */
1279  tdise = getCPUTime();
1280  distime += timeDifference(tdise, tdisb);
1281  if (disj) {
1282 
1283  disjointtrues++;
1284  //std::cout << "disjoints: " << disjointtrues << std::endl;
1285  midstep = false;
1286  std::set<SgGraphNode*> pthloopstmp;
1287  pthloopstmp.clear();
1288  for (int i = 0; i < currpth.size(); i++) {
1289  //currflat.push_back(currpth[i]);
1290  if (mkloops.find(currpth[i]) != mkloops.end()) {
1291  pthloopstmp.insert(currpth[i]);
1292  }
1293  }
1294  pthloops.push_back(pthloopstmp);
1295  path.push_back(currpth);
1296  pthloopstmp.clear();
1297 
1298  //std::set<std::vector<SgGraphNode*> > lpth;
1299  std::vector<SgGraphNode*> oldcurrpth = currpth;
1300  currpth.clear();
1301  if (currents.find((path.back()).back()) == currents.end()) {
1302  currents[(path.back()).back()] = 0;
1303  }
1304  SgGraphNode* frontnode = (path.back()).front();
1305  SgGraphNode* backnode = (path.back()).back();
1306 
1307  ROSE_ASSERT(pathsAtMk.find(backnode) != pathsAtMk.end() || backnode == endnode);
1308  ROSE_ASSERT(pathsAtMk.find(frontnode) != pathsAtMk.end());
1309  if (currents.find(backnode) == currents.end()) {
1310  currents[backnode] = 0;
1311  }
1312  else {
1313  ROSE_ASSERT(currents[backnode] == 0);
1314  }
1315  std::vector<std::vector<SgGraphNode*> > tmppths = pathsAtMk[backnode];
1316 
1317  currpth = tmppths[currents[backnode]];
1318  ROSE_ASSERT(currpth != oldcurrpth);
1319  currents[backnode]++;
1320  }
1321  else {
1322  disjoints++;
1323  //std::cout << "disjoint false: " << s << std::endl;
1324 
1325  while (true) {
1326  if (currents[(path.back()).back()] < pathsAtMk[(path.back()).back()].size() || path.back().back() == realstartnode) {
1327  break;
1328  }
1329  currents[(path.back()).back()] = 0;
1330  path.pop_back();
1331  pthloops.pop_back();
1332  }
1333  if ((path.back()).back() != realstartnode) {
1334  currpth = (pathsAtMk[(path.back()).back()])[currents[(path.back()).back()]];
1335  currents[(path.back()).back()]++;
1336  }
1337  else {
1338  step = true;
1339  }
1340  }
1341  }
1342  }
1343 std::cout << "successes: " << successes << std::endl;
1344 std::cout << "failures: " << failures << std::endl;
1345 
1346 return;
1347 }
1348 
1349 
1350 //these are debugging functions, used to visually ascertain where the paths are going to check to make sure everything is evaluated
1351 
1352 
1353 /* DEBUGGING */
1354 
1355 template<class InheritedAttributeType, class SynthesizedAttributeType>
1356 void
1358 printNodePlusEdgesForAnalysis(SgIncidenceDirectedGraph* g, SgGraphNode* n, int loopNum, int pathVal, std::ofstream& ss) {
1359  printNodeForAnalysis(n, loopNum, pathVal, ss);
1360  std::set<SgDirectedGraphEdge*> outEdges = g->computeEdgeSetOut(n);
1361  for (std::set<SgDirectedGraphEdge*>::iterator i = outEdges.begin(); i != outEdges.end(); i++) {
1362  if (nullEdgesOrdered.find(*i) == nullEdgesOrdered.end()) {
1363  printEdgeForAnalysis(*i, false, ss);
1364  }
1365  else {
1366  printEdgeForAnalysis(*i, true, ss);
1367  }
1368  }
1369 }
1370 
1371 template<class InheritedAttributeType, class SynthesizedAttributeType>
1372 void
1374 printNodePlusEdgesForAnalysisPath(SgIncidenceDirectedGraph* g, std::vector<SgGraphNode*> n, int loopNum, int pathVal, std::ofstream& ss) {
1375  for (unsigned int i = 0; i < n.size()-1; i++) {
1376  if (completedNodesPath.find(n[i]) == completedNodesPath.end()) {
1377  printNodeForAnalysis(n[i], loopNum, pathVal, ss);
1378  completedNodesPath.insert(n[i]);
1379  }
1380  std::pair<SgGraphNode*, SgGraphNode*> prnod;
1381  prnod.first = n[i+1];
1382  prnod.second = n[i];
1383  if (completedEdgesPath.find(prnod) == completedEdgesPath.end()) {
1384  printEdgeForAnalysisPath(n[i+1], n[i], ss);
1385  completedEdgesPath.insert(prnod);
1386  }
1387  }
1388  if (completedNodesPath.find(n[n.size() - 1]) == completedNodesPath.end()) {
1389  printNodeForAnalysis(n[n.size()-1], loopNum, pathVal, ss);
1390  completedNodesPath.insert(n[n.size() - 1]);
1391  }
1392 
1393 }
1394 
1395 
1396 template<class InheritedAttributeType, class SynthesizedAttributeType>
1397 void
1399 printNodeForAnalysis(SgGraphNode* n, int loopNum, int pathNum, std::ofstream &ss) {
1400  int id = n->get_index();
1401  std::string nodeColor = "black";
1402  if (loopNum != 0) {
1403  ss << id << " [label=\"" << "LoopNumS" << loopNum << "\", color=\"" << "green" << "\", style=\"" << "solid" << "\"];\n";
1404  }
1405  else {
1406  ss << id << " [label=\"" << "pathNumS" << pathNum << "\", color=\"" << "black" << "\", style=\"" << "dotted" << "\"];\n";
1407  }
1408 
1409 }
1410 template<class InheritedAttributeType, class SynthesizedAttributeType>
1411 void
1413 printEdgeForAnalysis(SgDirectedGraphEdge* e, bool isNullEdge, std::ofstream &ss) {
1414  if (isNullEdge) {
1415  ss << e->get_from()->get_index() << " -> " << e->get_to()->get_index() << " [label=\"" << "NullEdge" << "\", style=\"" << "dotted" << "\"];\n";
1416  }
1417  else {
1418  ss << e->get_from()->get_index() << " -> " << e->get_to()->get_index() << " [label=\"" << "\", style=\"" << "solid" << "\"];\n";
1419  }
1420 }
1421 template<class InheritedAttributeType, class SynthesizedAttributeType>
1422 void
1424 printEdgeForAnalysisPath(SgGraphNode* g1, SgGraphNode* g2, std::ofstream &ss) {
1425  ss << g2->get_index() << " -> " << g1->get_index() << " [label=\"" << "Edge" << "\", style=\"" << "solid" << "\"];\n";
1426 }
1427 
1428 /* END DEBUGGING */
1429 
1430 //This function sets up the graph so that the evaluatePath function can easily traverse the paths
1431 
1432 template<class InheritedAttributeType, class SynthesizedAttributeType>
1433 void
1436  bool done = false;
1437  bool edges = true;
1438  bool tookone = false;
1439  std::vector<SgGraphNode*> mkpath;
1440  std::vector<SgGraphNode*> marks;
1441  marks.push_back(n);
1442  mkglobal.push_back(n);
1443  SgGraphNode* currn = n;
1444  SgGraphNode* took;
1445  std::set<SgDirectedGraphEdge*> taken;
1446  std::vector<SgGraphNode*> toTake;
1447  std::vector<SgGraphNode*> path;
1448  path.push_back(n);
1449  mkpath.push_back(n);
1450  int itr = 0;
1451  int bifurcations = 0;
1452  std::map<SgGraphNode*, bool> completed;
1453  while (done == false) {
1454  ROSE_ASSERT(currn != NULL);
1455 //check to see if we've hit the endnode or if we're done, if not continue, if so push the subpath into the "pathsAtMk" repository
1456  if (currn == endnode || completed.find(currn) != completed.end()) {
1457  if (pathsAtMk.find(marks.back()) == pathsAtMk.end()) {
1458  std::vector<std::vector<SgGraphNode*> > emptypath;
1459  pathsAtMk[marks.back()] = emptypath;
1460  }
1461  edges = false;
1462  pathsAtMk[marks.back()].push_back(mkpath);
1463  //for (int mk = 0; mk < mkpath.size(); mk++) {
1464  // std::set<SgDirectedGraphEdge*> iedg = g->computeEdgeSetIn(mkpath[mk]);
1465  //if (iedg.size() > 1) {
1466  // ploops.insert(mkpath[mk]);
1467  // }
1468  //}
1469  ROSE_ASSERT(mkpath.front() == marks.back());
1470  if (marks.size() == 0) {
1471  return;
1472  }
1473  mkpath.clear();
1474  bool y = true;
1475  bool haventtaken = false;
1476  bool p = true;
1477  int place;
1478  bool found = false;
1479  while (found == false) {
1480  if (marks.size() == 0) {
1481  return;
1482  }
1483  SgDirectedGraphEdge* tooked;
1484  SgGraphNode* mark1 = marks.back();
1485  std::set<SgDirectedGraphEdge*> oedg = g->computeEdgeSetOut(mark1);
1486  ROSE_ASSERT(oedg.size() > 1 || mark1 == n);
1487  for (std::set<SgDirectedGraphEdge*>::iterator j = oedg.begin(); j != oedg.end(); j++) {
1488  if (taken.find(*j) == taken.end() && haventtaken == false) {
1489  tooked = *j;
1490  haventtaken = true;
1491  }
1492  }
1493  if (haventtaken == true) {
1494  if (marks.back() == n) {
1495  path.clear();
1496  }
1497  path.push_back(marks.back());
1498  if ( mkpath.empty() || (mkpath.back() != marks.back()) ) {
1499  ROSE_ASSERT(!marks.empty());
1500  mkpath.push_back(marks.back());
1501  }
1502  taken.insert(tooked);
1503  took = tooked->get_to();
1504  found = true;
1505  }
1506  else {
1507  completed[marks.back()] = true;
1508  bifurcations++;
1509  marks.pop_back();
1510  }
1511  }
1512  if (marks.size() == 0) {
1513  return;
1514  }
1515  haventtaken = false;
1516  found = false;
1517 
1518  }
1519 //if we haven't reached the endnode or completed, continue down the graph
1520  else {
1521  std::set<SgDirectedGraphEdge*> oedg = g->computeEdgeSetOut(currn);
1522  std::set<SgDirectedGraphEdge*> iedg = g->computeEdgeSetIn(currn);
1523  if (oedg.size() > 1) {
1524  if (mkpath.back() != currn) {
1525  mkpath.push_back(currn);
1526  }
1527  pathsAtMk[marks.back()].push_back(mkpath);
1528  mkpath.clear();
1529  mkpath.push_back(currn);
1530  marks.push_back(currn);
1531  if (find(mkglobal.begin(), mkglobal.end(), currn) == mkglobal.end()) {
1532  mkglobal.push_back(currn);
1533  }
1534  for (std::set<SgDirectedGraphEdge*>::iterator i = oedg.begin(); i != oedg.end(); i++) {
1535  if (taken.find(*i) == taken.end() && tookone == false) {
1536  taken.insert(*i);
1537  tookone = true;
1538  took = (*i)->get_to();
1539  }
1540  else if (taken.find(*i) == taken.end() && tookone == true) {
1541  //toTake.push_back((*i)->get_to());
1542  }
1543  }
1544  tookone = false;
1545  }
1546  else {
1547  took = (*(oedg.begin()))->get_to();
1548  }
1549  }
1550  itr++;
1551 
1552  if (find(path.begin(), path.end(), took) == path.end()) {
1553  mkpath.push_back(took);
1554  path.push_back(took);
1555  currn = took;
1556  }
1557  else {
1558  mkloops.insert(took);
1559  std::vector<SgGraphNode*> lptemp;
1560  lptemp.clear();
1561  lptemp.push_back(took);
1562  while (path.back() != took) {
1563 
1564  path.pop_back();
1565 
1566  lptemp.push_back(path.back());
1567 
1568  }
1569  (mkloopmap[took]).insert(lptemp);
1570 /*
1571  if (lptemp.size() > 1) {
1572  if (find(looppaths.begin(), looppaths.end(), lptemp) == looppaths.end() && find(lptemp.begin(), lptemp.end(), st) == lptemp.end() && find(lptemp.begin(), lptemp.end(), endnode) == lptemp.end()) {
1573  looppaths.push_back(lptemp);
1574  loopnum++;
1575  for (unsigned int i = 0; i < lptemp.size(); i++) {
1576  loopNumMap[lptemp[i]] = loopnum;
1577  }
1578  }
1579  }
1580 */
1581  path.push_back(took);
1582  currn = path.back();
1583  mkpath.push_back(took);
1584  }
1585 
1586 
1587 }
1588  return;
1589 }
1590 
1591 //not currently useful
1592 template <class InheritedAttributeType, class SynthesizedAttributeType>
1593 SynthesizedAttributeType
1595 defaultSynthesizedAttribute(InheritedAttributeType inh)
1596 {
1597  SynthesizedAttributeType s = SynthesizedAttributeType();
1598  return s;
1599 }
1600 
1601 
1602 //computes the order in which to evaluate the nodes in nodal analysis so that you don't evaluate a node before you evaluate its parents
1603 
1604 template <class InheritedAttributeType, class SynthesizedAttributeType>
1605 void
1608  std::map<SgGraphNode*, int> incomputables;
1609  std::set<SgGraphNode*> lpposs;
1610  //std::set<SgGraphNode*> lps;
1611  SgGraphNode* currn;
1612  currn = n;
1613  int orders = 0;
1614  while (true) {
1615  if (orders % 10000 == 0) {
1616  std::cout << "orders: " << orders << std::endl;
1617  }
1618  orders++;
1619  if (currn == endnode) {
1620  }
1621  if (computable(g, currn) || currn == n) {
1622  int mp;
1623  if (oVals.find(currn) == oVals.end()) {
1624  oVals[currn] = currm++;
1625  iVals[currm++] = currn;
1626  currm += 1;
1627  }
1628  if (currn == endnode) {
1629 
1630  break;
1631  }
1632  std::pair<bool, SgGraphNode*> pbs = getNextChild(g, currn);
1633  computedNodes.insert(currn);
1634  ROSE_ASSERT(pbs.first == true);
1635  currn = pbs.second;
1636  }
1637  else {
1638  std::pair<bool, SgGraphNode*> pbp = getNextPar(g, currn);
1639  ROSE_ASSERT(pbp.first == true);
1640  currn = pbp.second;
1641 
1642  }
1643 
1644  }
1645  std::cout << "required orders" << orders << std::endl;
1646  std::cout << "incomputables.size() " << incomputables.size() << std::endl;
1647 }
1648 
1649 //simple fucntion to check the computability under nodal analysis
1650 template <class InheritedAttributeType, class SynthesizedAttributeType>
1651 bool
1654  if (computedNodes.find(n) != computedNodes.end()) {
1655  return true;
1656  }
1657  std::set<SgDirectedGraphEdge*> ed = g->computeEdgeSetIn(n);
1658  bool comp = true;
1659  for (std::set<SgDirectedGraphEdge*>::iterator i = ed.begin(); i != ed.end(); i++) {
1660  if (oVals.find((*i)->get_from()) == oVals.end() && nullEdgesOrdered.find(*i) == nullEdgesOrdered.end()) {
1661  comp = false;
1662  }
1663  }
1664  return comp;
1665 }
1666 
1667 
1668 //computes the inherited attribute values in nodal analysis
1669 
1670 template <class InheritedAttributeType, class SynthesizedAttributeType>
1671 void
1674  int runs = 0;
1675 // std::ofstream mf;
1676 // mf.open("analysis.dot");
1677 // mf << "digraph defaultName { \n";
1678  for (std::map<int, SgGraphNode*>::iterator i = iVals.begin(); i != iVals.end(); i++) {
1679  runs++;
1680  ROSE_ASSERT(canEval(g, (*i).second));
1681  setPathVal(g, n);
1682  //printNodePlusEdgesForAnalysis(g, (*i).second, loopNumMap[(*i).second], pathValMap[(*i).second], mf);
1683  evalNodeOrdered(g, (*i).second);
1684  }
1685 }
1686 
1687 //checks to see if evaluation is possible under nodal analysis
1688 template <class InheritedAttributeType, class SynthesizedAttributeType>
1689 bool
1692  bool evaled = true;
1693  if (inhVals.find(n) == inhVals.end()) {
1694  std::set<SgDirectedGraphEdge*> ins = g->computeEdgeSetIn(n);
1695  for (std::set<SgDirectedGraphEdge*>::iterator i = ins.begin(); i != ins.end(); i++) {
1696  if (inhVals.find((*i)->get_from()) == inhVals.end() && nullEdgesOrdered.find(*i) == nullEdgesOrdered.end()) {
1697  evaled = false;
1698  }
1699  }
1700  }
1701  return evaled;
1702 }
1703 
1704 
1705 //actually does the evaluation
1706 template <class InheritedAttributeType, class SynthesizedAttributeType>
1707 void
1710  if (inhVals.find(n) != inhVals.end()) {
1711  return;
1712  }
1713  std::set<SgDirectedGraphEdge*> par = g->computeEdgeSetIn(n);
1714  std::vector<InheritedAttributeType> inh;
1715  for (std::set<SgDirectedGraphEdge*>::iterator i = par.begin(); i != par.end(); i++) {
1716  if (inhVals.find((*i)->get_from()) != inhVals.end()) {
1717  inh.push_back(inhVals[(*i)->get_from()]);
1718  }
1719  }
1720 
1721  if (n != st || inh.size() > 0) {
1722  InheritedAttributeType inhX;
1723  inhX = evaluateInheritedAttribute(n, inh);
1724  inhVals[n] = inhX;
1725  }
1726  //std::cout << "num of inhVals: " << inh.size() << std::endl;
1727 
1728 }
1729 
1730 
1731 //debugging function, currently not useful for the end user
1732 template <class InheritedAttributeType, class SynthesizedAttributeType>
1733 void
1736  if (pathValMap.find(currn) != pathValMap.end()) {
1737  return;
1738  }
1739  std::set<SgDirectedGraphEdge*> ined = g->computeEdgeSetIn(currn);
1740  int tmppathcount = 0;
1741  for (std::set<SgDirectedGraphEdge*>::iterator i = ined.begin(); i != ined.end(); i++) {
1742  ROSE_ASSERT(pathValMap.find((*i)->get_from()) != pathValMap.end() /*|| nullEdgesOrdered.find(*i) != nullEdgesOrdered.end()*/);
1743  //if (nullEdgesOrdered.find(*i) != nullEdgesOrdered.end()) {
1744  // pathValMap[(*i)->get_from()] = 0;
1745  // }
1746  int pv = pathValMap[(*i)->get_from()];
1747  if (pv != 0) {
1748  tmppathcount += pv;
1749  }
1750  }
1751  pathValMap[currn] = tmppathcount;
1752  return;
1753  }
1754 
1755 //computes the next child to be analyzed in nodal analysis
1756 template <class InheritedAttributeType, class SynthesizedAttributeType>
1757 std::pair<bool, SgGraphNode*>
1760  bool nullPoss = false;
1761  //std::cout << "nextChild" << std::endl;
1762  std::set<SgDirectedGraphEdge*> outs = g->computeEdgeSetOut(n);
1763  //std::cout << "outs.size(): " << outs.size() << std::endl;
1764  //std::cout << "outs: " << outs.size() << std::endl;
1765  SgGraphNode* nextNode;
1766  SgGraphNode* nullNode;
1767  bool completed = false;
1768  bool completeNull = false;
1769 
1770  for (std::set<SgDirectedGraphEdge*>::iterator i = outs.begin(); i != outs.end(); i++) {
1771 
1772  if (outs.size() == 1) {
1773  nextNode = (*i)->get_to();
1774  if (nullEdgesOrdered.find(*i) != nullEdgesOrdered.end()) {
1775  nullNum++;
1776  }
1777  //completedEdges.insert(*i);
1778  completed = true;
1779  }
1780  else if (completed == false && computedNodes.find((*i)->get_to()) == computedNodes.end()) {
1781  completed = true;
1782  nextNode = (*i)->get_to();
1783  if (nullEdgesOrdered.find(*i) != nullEdgesOrdered.end()) {
1784  nullNum++;
1785  }
1786  completedEdgesOut.insert(*i);
1787  }
1788 
1789 
1790  }
1791  std::pair<bool, SgGraphNode*> pr;
1792  ROSE_ASSERT (completed == true || completeNull == true);
1793  if (completed == true) {
1794  pr.first = completed;
1795  pr.second = nextNode;
1796  return pr;
1797  }
1798  else {
1799  pr.first = true;
1800  pr.second = nullNode;
1801  return pr;
1802  }
1803 
1804 }
1805 
1806 //computes the next parent to be analyzed in nodal analysis
1807 template <class InheritedAttributeType, class SynthesizedAttributeType>
1808 std::pair<bool, SgGraphNode*>
1811  std::set<SgDirectedGraphEdge*> ins = g->computeEdgeSetIn(n);
1812  SgGraphNode* nextPar;
1813  SgDirectedGraphEdge* nullEdgeO;
1814  bool completed = false;
1815  bool completeNull = false;
1816  for (std::set<SgDirectedGraphEdge*>::iterator i = ins.begin(); i != ins.end(); i++) {
1817 
1818  if (ins.size() == 1 /*&& completedEdges.find(*i) == completedEdges.end()*/) {
1819  completed = true;
1820  completedEdges.insert(*i);
1821  nextPar = (*i)->get_from();
1822  }
1823 
1824  else if (completedEdges.find(*i) == completedEdges.end() && completed == false) {
1825  completed = true;
1826  nextPar = (*i)->get_from();
1827  completedEdges.insert(*i);
1828  }
1829 
1830  else if (completedEdges.find(*i) != completedEdges.end() && computedNodes.find((*i)->get_from()) == computedNodes.end() && completed == false /*&& nullEdgesOrdered.find(*i) == nullEdgesOrdered.end()*/) {
1831  completeNull = true;
1832  std::pair<SgGraphNode*, SgGraphNode*> lpp;
1833  nextPar = n;
1834  nullEdgesOrdered.insert(*i);
1835  nullEdgesPaths++;
1836 
1837  }
1838  }
1839  ROSE_ASSERT(completed == true || completeNull == true);
1840  std::pair<bool, SgGraphNode*> pr;
1841  pr.first = completed;
1842  pr.second = nextPar;
1843 
1844  if (completeNull == true && completed == false) {
1845  pr.first = completeNull;
1846  pr.second = nextPar;
1847  }
1848 
1849  return pr;
1850 }
1851 
1852 
1853 
1854 
1855 
1856 
1857 
1858 
1859 
1860 
1861 
1862 
1863 
1864 
1865 
InheritedAttributeType traverse(SgGraphNode *basenode, SgIncidenceDirectedGraph *g, InheritedAttributeType inheritedValue, InheritedAttributeType nullInherit, SgGraphNode *endnode, bool insep=false, bool pcHk=false)
This is the function that is used by the user directly to start the algorithm.