ROSE  0.9.6a
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
graphProcessing.h
Go to the documentation of this file.
1 /*
2 
3 FINISH TEMPFLATPATH CODE
4 
5 */
6 
7 
8 
9 
10 #define LP 1
11 #define PERFDEBUG 0
12 //#define FULLDEBUG 1
13 #ifdef _OPENMP
14 #include <omp.h>
15 #endif
16 #include <boost/regex.hpp>
17 #include <iostream>
18 #include <fstream>
19 #include <string>
20 #include <assert.h>
21 #include <staticCFG.h>
22 
54 #include <boost/graph/adjacency_list.hpp>
55 #include <boost/bind.hpp>
56 #include <boost/foreach.hpp>
57 #include <boost/tuple/tuple.hpp>
58 #include <boost/graph/graphviz.hpp>
59 #include <boost/graph/dominator_tree.hpp>
60 #include <boost/graph/reverse_graph.hpp>
61 #include <boost/graph/transpose_graph.hpp>
62 #include <boost/algorithm/string.hpp>
63 
64 
65 
66 #include <vector>
67 #include <algorithm>
68 #include <utility>
69 #include <iostream>
70 #include <sys/time.h>
71 #include <sys/resource.h>
72 #include <sys/time.h>
73 
74 
75 
76 
77 
78 
79 template <class CFG>
80 class SgGraphTraversal
81 {
82 public:
83 
84  typedef typename boost::graph_traits<CFG>::vertex_descriptor Vertex;
85  typedef typename boost::graph_traits<CFG>:: edge_descriptor Edge;
86 
87  void constructPathAnalyzer(CFG* g, bool unbounded=false, Vertex end=0, Vertex begin=0, bool ns = true);
88  virtual void analyzePath(std::vector<Vertex>& pth) = 0;
89  std::vector<int> getInEdges(int& node, CFG*& g);
90  std::vector<int> getOutEdges(int& node, CFG*& g);
91  int getTarget(int& n, CFG*& g);
92  int getSource(int& n, CFG*& g);
93  std::map<Vertex, int> vertintmap;
94  std::map<Edge, int> edgeintmap;
95  std::map<int, Vertex> intvertmap;
96  std::map<int, Edge> intedgemap;
97  SgGraphTraversal();
98  virtual ~SgGraphTraversal();
99  SgGraphTraversal( SgGraphTraversal &);
100  SgGraphTraversal &operator=( SgGraphTraversal &);
101  int pathnum;
102 
103 
104  void firstPrepGraph(CFG*& g);
105 
106 private:
107 
108  int normals;
109  int abnormals;
110  bool needssafety;
111  int recursed;
112  int checkedfound;
113  // typedef typename boost::graph_traits<CFG>::vertex_descriptor Vertex;
114  // typedef typename boost::graph_traits<CFG>:: edge_descriptor Edge;
115  // std::vector<int> getInEdges(int& node, CFG*& g);
116  // std::vector<int> getOutEdges(int& node, CFG*& g);
117  void prepareGraph(CFG*& g);
118  void findClosuresAndMarkersAndEnumerate(CFG*& g);
119  // void constructPathAnalyzer(CFG* g, bool unbounded=false, Vertex end=0, Vertex begin=0, bool ns = true);
120  // virtual void analyzePath(std::vector<Vertex>& pth) = 0;
121  // void firstPrepGraph(CFG*& g);
122  int stoppedpaths;
123  std::set<std::vector<int> > traversePath(int begin, int end, CFG*& g, bool loop=false);
124  std::set<std::vector<int> > uTraversePath(int begin, int end, CFG*& g, bool loop, std::map<int, std::vector<std::vector<int> > >& localLoops);
125  std::vector<std::vector<int> > bfsTraversePath(int begin, int end, CFG*& g, bool loop=false);
126  std::vector<int> unzipPath(std::vector<int>& path, CFG*& g, int start, int end);
127  std::vector<int> zipPath(std::vector<int>& path, CFG*& g, int start, int end);
128  std::vector<int> zipPath2(std::vector<int>& path, CFG*& g);
129  void printCFGNode(int& cf, std::ofstream& o);
130  void printCFGNodeGeneric(int& cf, std::string prop, std::ofstream& o);
131  void printCFGEdge(int& cf, CFG*& cfg, std::ofstream& o);
132  void printHotness(CFG*& g);
133  void printPathDot(CFG*& g);
134  void computeOrder(CFG*& g, const int& begin);
135  void computeSubGraphs(const int& begin, const int &end, CFG*& g, int depthDifferential);
136  //int getTarget(int& n, CFG*& g);
137  //int getSource(int& n, CFG*& g);
138  std::vector<int> sources;
139  std::vector<int> sinks;
140  std::vector<int> recursiveLoops;
141  std::vector<int> recurses;
142  std::map<int, int> ptsNum;
143  bool borrowed;
144  std::set<int> badloop;
145  std::map<int, std::vector<std::vector<int> > > totalLoops;
146 // int pathnum;
147  std::map<int, std::string> nodeStrings;
148  int sourcenum;
149  unsigned long long evaledpaths;
150  int badpaths;
151  int workingthreadnum;
152  bool workingthread;
153  std::map<int, std::set<std::vector<int> > > loopStore;
154  std::vector<std::vector<int> > pathStore;
155  std::map<int, std::vector<int> > subpathglobal;
156  std::map<std::vector<int>, int> subpathglobalinv;
157  int nextsubpath;
158  std::vector<int> orderOfNodes;
159 // std::map<Vertex, int> vertintmap;
160 // std::map<Edge, int> edgeintmap;
161 // std::map<int, Vertex> intvertmap;
162 // std::map<int, Edge> intedgemap;
163  std::vector<std::map<Vertex, Vertex> > SubGraphGraphMap;
164  std::vector<std::map<Vertex, Vertex> > GraphSubGraphMap;
165  std::vector<CFG*> subGraphVector;
166  void getVertexPath(std::vector<int> path, CFG*& g, std::vector<Vertex>& vertexPath );
167  void storeCompact(std::vector<int> path);
168  int nextNode;
169  int nextEdge;
170  std::vector<int> markers;
171  std::vector<int> closures;
172  std::map<int, int> markerIndex;
173  std::map<int, std::vector<int> > pathsAtMarkers;
174  typedef typename boost::graph_traits<CFG>::vertex_iterator vertex_iterator;
175  typedef typename boost::graph_traits<CFG>::out_edge_iterator out_edge_iterator;
176  typedef typename boost::graph_traits<CFG>::in_edge_iterator in_edge_iterator;
177  typedef typename boost::graph_traits<CFG>::edge_iterator edge_iterator;
178  bool bound;
179 // SgGraphTraversal();
180 // virtual ~SgGraphTraversal();
181 // SgGraphTraversal( SgGraphTraversal &);
182 // SgGraphTraversal &operator=( SgGraphTraversal &);
183 
184 
185 };
186 
187 
188 template<class CFG>
189 SgGraphTraversal<CFG>::
190 SgGraphTraversal()
191 {
192 }
193 
194 
195 
196 template<class CFG>
197 SgGraphTraversal<CFG> &
198 SgGraphTraversal<CFG>::
199 operator=( SgGraphTraversal &other)
200 {
201  return *this;
202 }
203 
204 #ifndef SWIG
205 
206 template<class CFG>
207 SgGraphTraversal<CFG>::
208 ~SgGraphTraversal()
209 {
210 }
211 
212 #endif
213 
221 template<class CFG>
222 inline int
223 SgGraphTraversal<CFG>::
224 getSource(int& edge, CFG*& g)
225 {
226  Edge e = intedgemap[edge];
227  Vertex v = boost::source(e, *g);
228  return(vertintmap[v]);
229 }
230 
240 template<class CFG>
241 inline int
242 SgGraphTraversal<CFG>::
243 getTarget(int& edge, CFG*& g)
244 {
245  Edge e = intedgemap[edge];
246  Vertex v = boost::target(e, *g);
247  return(vertintmap[v]);
248 }
249 
258 template<class CFG>
259 std::vector<int>
260 SgGraphTraversal<CFG>::
261 getInEdges(int& node, CFG*& g)
262 {
263  Vertex getIns = intvertmap[node];
264  std::vector<int> inedges;
265  in_edge_iterator i, j;
266  for (boost::tie(i, j) = boost::in_edges(getIns, *g); i != j; ++i)
267  {
268  inedges.push_back(edgeintmap[*i]);
269  }
270  return inedges;
271 }
272 
283 template<class CFG>
284 std::vector<int>
285 SgGraphTraversal<CFG>::
286 getOutEdges(int &node, CFG*& g)
287 {
288  Vertex getOuts = intvertmap[node];
289  std::vector<int> outedges;
290  out_edge_iterator i, j;
291  for (boost::tie(i, j) = boost::out_edges(getOuts, *g); i != j; ++i)
292  {
293  outedges.push_back(edgeintmap[*i]);
294  }
295  return outedges;
296 }
297 
307 template<class CFG>
308 inline
309 std::vector<int>
310 SgGraphTraversal<CFG>::
311 zipPath2(std::vector<int>& pth, CFG*& g) {
312  std::vector<int> npth;
313  npth.push_back(pth[0]);
314  for (int i = 1; i < pth.size()-1; i++) {
315  if (find(closures.begin(), closures.end(), pth[i]) != closures.end()) {
316  npth.push_back(pth[i]);
317  }
318  }
319  npth.push_back(pth.back());
320  return npth;
321 }
322 
334 template<class CFG>
335 std::vector<int>
336 SgGraphTraversal<CFG>::
337 zipPath(std::vector<int>& pth, CFG*& g, int start, int end) {
338  std::vector<int> subpath;
339  std::vector<int> movepath;
340  movepath.push_back(pth.front());
341  movepath.push_back(pth.back());
342  for (unsigned int qw = 0; qw < pth.size()-1; qw++) {
343  if (find(markers.begin(), markers.end(), pth[qw]) != markers.end()) {
344  std::vector<int> oeds = getOutEdges(pth[qw], g);
345  for (unsigned int i = 0; i < oeds.size(); i++) {
346  if (getTarget(oeds[i], g) == pth[qw+1]) {
347  movepath.push_back(oeds[i]);
348  }
349  }
350  }
351  }
352  return movepath;
353  }
354 
355 
356 
357 
358 
359 
370 template<class CFG>
371 std::vector<int>
372 SgGraphTraversal<CFG>::
373 unzipPath(std::vector<int>& pzipped, CFG*& g, int start, int end) {
374  ROSE_ASSERT(pzipped[0] == start && (pzipped[1] == end || end == -1));
375  std::vector<int> zipped;
376  for (unsigned int i = 2; i < pzipped.size(); i++) {
377  zipped.push_back(pzipped[i]);
378  }
379  std::vector<int> unzipped;
380  unzipped.push_back(start);
381  std::vector<int> oeds = getOutEdges(start, g);
382  if (oeds.size() == 0) {
383  return unzipped;
384  }
385  for (unsigned int i = 0; i < zipped.size(); i++) {
386  oeds = getOutEdges(unzipped.back(), g);
387  while (oeds.size() == 1) {
388  if (getTarget(oeds[0], g) == end && unzipped.size() != 1) {
389  unzipped.push_back(end);
390  return unzipped;
391  }
392  unzipped.push_back(getTarget(oeds[0], g));
393  oeds = getOutEdges(unzipped.back(), g);
394  }
395  if (oeds.size() == 0) {
396  return unzipped;
397  }
398  if (oeds.size() > 1 && (unzipped.back() != end || (unzipped.size() == 1 && unzipped.back() == end))) {
399  ROSE_ASSERT(getSource(zipped[i], g) == unzipped.back());
400  unzipped.push_back(getTarget(zipped[i], g));
401  }
402 
403  }
404  std::vector<int> oeds2 = getOutEdges(unzipped.back(), g);
405  if (unzipped.back() != end && oeds2.size() != 0) {
406  while (oeds2.size() == 1 && unzipped.back() != end) {
407  unzipped.push_back(getTarget(oeds2[0], g));
408  oeds2 = getOutEdges(unzipped.back(), g);
409  }
410  }
411  return unzipped;
412 }
413 
414 /*
415 Example Time
416 
417  Example:
418  timeval tim;
419  gettimeofday(&tim, NULL);
420  double t1=tim.tv_sec+(tim.tv_usec/1000000.0);
421  do_something_long();
422  gettimeofday(&tim, NULL);
423  double t2=tim.tv_sec+(tim.tv_usec/1000000.0);
424  printf("%.6lf seconds elapsed\n", t2-t1);
425 
426 */
427 
439 template<class CFG>
440 std::vector<std::vector<int> >
441 SgGraphTraversal<CFG>::
442 bfsTraversePath(int begin, int end, CFG*& g, bool loop) {
443 //perfdebug allows for examining the speed of traversal
444  #ifdef PERFDEBUG
445  //timeval tim;
446  //gettimeofday(&tim, NULL);
447  //double tim1 = tim.tv_sec+(tim.tv_usec/1000000.0);
448  #endif
449  bool recursedloop = loop;
450  std::map<int, std::vector<std::vector<int> > > PtP;
451  std::set<int> nodes;
452  std::vector<std::vector<int> > pathContainer;
453  //std::vector<std::vector<int> > oldPaths;
454  std::vector<int> completedLoops;
455  std::vector<std::vector<int> > npc;
456  std::vector<int> bgpath;
457  bgpath.push_back(begin);
458  pathContainer.push_back(bgpath);
459  std::vector<std::vector<int> > newPathContainer;
460  std::vector<std::vector<int> > paths;
461  std::vector<int> localLoops;
462  std::map<int, std::vector<std::vector<int> > > globalLoopPaths;
463  //std::cout << "at the while" << std::endl;
464 //To keep
465  while (pathContainer.size() != 0 /*|| oldPaths.size() != 0*/) {
466 /*
467  unsigned int mpc = 50000;
468  if (pathContainer.size() == 0) {
469  unsigned int mxl = 0;
470  if (oldPaths.size() > mpc) {
471  mxl = mpc/2;
472  }
473  else {
474  mxl = oldPaths.size();
475  }
476  for (unsigned int k = 0; k < mxl; k++) {
477  pathContainer.push_back(oldPaths.back());
478  oldPaths.pop_back();
479  }
480  }
481  if (pathContainer.size() > mpc) {
482  unsigned int j = 0;
483  while (j < mpc) {
484  npc.push_back(pathContainer.back());
485  pathContainer.pop_back();
486  j++;
487  }
488  oldPaths.insert(oldPaths.end(), pathContainer.begin(), pathContainer.end());
489  pathContainer = npc;
490  npc.clear();
491  }
492 */
493 
494 //iterating through the currently discovered subpaths to build them up
495  for (unsigned int i = 0; i < pathContainer.size(); i++) {
496  std::vector<int> npth = pathContainer[i];
497  std::vector<int> oeds = getOutEdges(npth.back(), g);
498  std::vector<int> ieds = getInEdges(npth.back(), g);
499 
500  npth = pathContainer[i];
501  oeds = getOutEdges(npth.back(), g);
502 
503  if ((!recursedloop && ((bound && npth.back() == end && npth.size() != 1) || (!bound && oeds.size() == 0))) || (recursedloop && npth.back() == end && npth.size() != 1)) {
504  std::vector<int> newpth;
505  newpth = (pathContainer[i]);
506  std::vector<int> movepath = newpth;//zipPath(newpth, g);
507  if (recursedloop && newpth.back() == end && newpth.size() != 1) {
508  paths.push_back(movepath);
509  }
510  else if (!recursedloop) {
511  if (bound && newpth.size() != 1 && newpth.back() == end) {
512  paths.push_back(movepath);
513  }
514  else if (!bound) {
515  paths.push_back(movepath);
516  }
517  }
518 
519  }
520  else {
521 std::vector<int> oeds = getOutEdges(pathContainer[i].back(), g);
522 
523  for (unsigned int j = 0; j < oeds.size(); j++) {
524 
525 
526 int tg = getTarget(oeds[j], g);
527 
528 
529  std::vector<int> newpath = (pathContainer[i]);
530  //we split up paths into pieces so that they don't take up a lot of memory, basically this is when we run into a path
531  //more than once, so we attach all paths that go to that path to that particular node via PtP
532  if (nodes.find(tg) != nodes.end() && find(newpath.begin(), newpath.end(), tg) == newpath.end() && tg != end) {
533  if (PtP.find(tg) == PtP.end()) {
534  std::vector<int> nv;
535  nv.push_back(tg);
536  newPathContainer.push_back(nv);
537  PtP[tg].push_back(/*zipPath(*(*/newpath);//, g, newpath.front(), newpath.back()));
538  }
539  else {
540  PtP[tg].push_back(/*zipPath(*/newpath);//, g, newpath.front(), newpath.back()));
541  }
542  }
543  else if (find(newpath.begin(), newpath.end(), getTarget(oeds[j], g)) == newpath.end() || getTarget(oeds[j], g) == end) {
544  newpath.push_back(tg);
545  std::vector<int> ieds = getInEdges(tg, g);
546  if (ieds.size() > 1) {//find(closures.begin(), closures.end(), tg) != closures.end()) {
547  nodes.insert(tg);
548  }
549  newPathContainer.push_back(newpath);
550  }
551  else if (tg == end && recursedloop) {
552  newpath.push_back(tg);
553  newPathContainer.push_back(newpath);
554  }
555  else {//if (find(newpath.begin(), newpath.end(), tg) != newpath.end() && tg != end) {
556  std::vector<int> ieds = getInEdges(tg, g);
557  if (ieds.size() > 1/*find(closures.begin(), closures.end(), tg) != closures.end()*/ && find(completedLoops.begin(), completedLoops.end(), tg) == completedLoops.end() /*&& find(localLoops.begin(), localLoops.end(), tg) == localLoops.end()*/ && find(recurses.begin(), recurses.end(), tg) == recurses.end()) {
558  localLoops.push_back(tg);
559  nodes.insert(tg);
560  }
561  // else if (find(recurses.begin(), recurses.end(), tg) != recurses.end()) {
562  // }
563  }
564  //else {
565  // std::cout << "problem" << std::endl;
566  // ROSE_ASSERT(false);
567  // }
568  }
569  }
570  }
571  pathContainer = newPathContainer;
572  newPathContainer.clear();
573  }
574  // std::cout << "done while" << std::endl;
575  pathContainer.clear();
576  std::vector<std::vector<int> > finnpts;
577  std::vector<std::vector<int> > npts;
578  while (true) {
579  if (paths.size() > 1000000) {
580  std::cout << "too many paths, consider a subgraph" << std::endl;
581  ROSE_ASSERT(false);
582  }
583  //#pragma omp parallel for schedule(guided)
584  for (unsigned int qq = 0; qq < paths.size(); qq++) {
585  std::vector<int> pq = paths[qq];
586  std::vector<int> qp;
587  int ppf = paths[qq].front();
588  if (PtP.find(ppf) != PtP.end()) {
589  for (unsigned int kk = 0; kk < PtP[ppf].size(); kk++) {
590  std::vector<int> newpath = /*unzipPath(*/PtP[ppf][kk];//, g, PtP[ppf][kk][0], PtP[ppf][kk][1]);
591  bool good = true;
592  if (newpath.back() == newpath.front() && newpath.front() != begin && newpath.size() > 1) {
593  good = false;
594  }
595  else {
596 
597  // if (find(pq.begin(), pq.end(), newpath.front()) != pq.end() && newpath.front() != begin) {
598  // good = false;
599  // }
600 
601 
602  // else {
603  for (unsigned int kk1 = 0; kk1 < newpath.size(); kk1++) {
604 
605  /*
606  if (newpath.front() == newpath.back()) {
607  good = false;
608  break;
609  }
610  else */if (find(pq.begin(), pq.end(), newpath[kk1]) != pq.end() && newpath[kk1] != begin) {
611  good = false;
612  break;
613 
614  }
615  }
616  //}
617  }
618  if (good) {
619  newpath.insert(newpath.end(), pq.begin(), pq.end());
620  #pragma omp critical
621  {
622  npts.push_back(newpath);
623  }
624  }
625  }
626  }
627  else {
628  std::vector<int> ppq = pq;// zipPath(pq, g, pq.front(), pq.back());
629  #pragma omp critical
630  {
631  finnpts.push_back(ppq);
632  }
633  }
634  }
635  if (npts.size() == 0) {
636  break;
637  }
638  else {
639  paths = npts;
640  npts.clear();
641  }
642  }
643  paths = finnpts;
644  finnpts.clear();
645  for (unsigned int k = 0; k < localLoops.size(); k++) {
646  int lk = localLoops[k];
647  std::vector<std::vector<int> > loopp;
648  if (loopStore.find(localLoops[k]) != loopStore.end()) {
649  loopp.insert(loopp.end(), loopStore[localLoops[k]].begin(), loopStore[localLoops[k]].end());
650  }
651  else {
652  std::map<int, std::vector<std::vector<int> > > localLoopPaths;
653  completedLoops.push_back(lk);
654  recurses.push_back(lk);
655  loopp = bfsTraversePath(lk, lk, g, true);
656  recurses.pop_back();
657  }
658  for (unsigned int ik = 0; ik < loopp.size(); ik++) {
659 
660  if (find(globalLoopPaths[lk].begin(), globalLoopPaths[lk].end(), loopp[ik]) == globalLoopPaths[lk].end()) {
661  globalLoopPaths[localLoops[k]].push_back(loopp[ik]);
662  }
663  }
664 
665 
666 
667  }
668  borrowed = true;
669  std::vector<std::vector<int> > lps2;
670  unsigned int maxpaths = 1000;
671  unsigned int pathdivisor = 1;//paths.size()/maxpaths;///paths.size();
672 
673  //if (pathdivisor < 1) {
674  pathdivisor = 1;
675  maxpaths = paths.size();
676  // }
677 /*
678  for (unsigned int j = 0; j < pathdivisor+1; j++) {
679  std::vector<std::vector<int> > npaths;
680  std::vector<int> dummyvec;
681  unsigned int mxpths;
682  if (j < pathdivisor) {
683  mxpths = maxpaths;
684  }
685  else {
686  mxpths = paths.size() % pathdivisor;
687  }
688  for (unsigned int k = 0; k < mxpths; k++) {
689  npaths.push_back(paths.back());//unzipPath(paths.back(), g, begin, end));
690  paths.pop_back();
691  }
692 */
693  pathStore = paths;
694  paths.clear();
695  if (!recursedloop) {
696  uTraversePath(begin, end, g, false, globalLoopPaths);
697  }
698  else {
699  recursed++;
700 
701  std::set<std::vector<int> > lps = uTraversePath(begin, end, g, true, globalLoopPaths);
702  recursed--;
703  for (std::set<std::vector<int> >::iterator ij = lps.begin(); ij != lps.end(); ij++) {
704  std::vector<int> ijk = (*ij);
705 
706  lps2.push_back(*ij);
707  }
708  }
709  //}
710  #ifdef PERFDEBUG
711  // timeval tim;
712  //std::cout << "begin: " << begin << " end: " << end << std::endl;
713  //gettimeofday(&tim, NULL);
714  //double tim2 = tim.tv_sec+(tim.tv_usec/1000000);
715  //double timeRet = tim2 - tim1;
716  //std::cout << "bfs time elapsed: " << timeRet << std::endl;
717  #endif
718  return lps2;
719 
720 }
721 
722 
734 template<class CFG>
735 std::set<std::vector<int> >
736 SgGraphTraversal<CFG>::
737 uTraversePath(int begin, int end, CFG*& g, bool loop, std::map<int, std::vector<std::vector<int> > >& globalLoopPaths) {
738  //std::cout << "uTraverse" << std::endl;
739  //int doubledpaths = 0;
740  int newmil = 1;
741  //#ifdef LP
742  //if (loop && loopStore.find(begin) != loopStore.end()) {
743  // return loopStore[begin];
744  //}
745  //#endif
746  #ifdef PERFDEBUG
747  //timeval tim;
748  //gettimeofday(&tim, NULL);
749  //double t1 = tim.tv_sec+(tim.tv_usec/1000000);
750  #endif
751  std::set<std::vector<int> > newpaths;
752  std::set<std::vector<int> > npaths;
753  pathnum = 0;
754  std::vector<int> path;
755  std::vector<std::vector<int> > paths;
756  int truepaths = 0;
757  std::vector<std::vector<int> > checkpaths;
758  std::vector<std::vector<int> > npathchecker;
759  std::map<int, int> currents;
760  //int nnumpaths = 0;
761  std::set<std::vector<int> > loopPaths;
762  //bool threadsafe = true;
763  bool done = false;
764  std::set<std::vector<int> > fts;
765  //double ttfors = 0;
766  //double tperms = 0;
767  while (true) {
768  //std::cout << "paths.size() " << paths.size() << std::endl;
769  if (paths.size() > 1000000) {
770  std::cout << "nearly 1 million paths with no loops, stopping" << std::endl;
771  return loopPaths;
772  std::cout << "ended early" << std::endl;
773  }
774  if (done || borrowed) {
775 
776  if (borrowed) {
777  paths = pathStore;
778  pathStore.clear();
779  }
780  //std::cout << "paths.size(): " << paths.size() << std::endl;
781  if (paths.size() != 0) {
782  }
783  else {
784  return loopPaths;
785  }
786 
787  // #pragma omp parallel
788  // {
789  #pragma omp parallel for schedule(guided)
790  for (unsigned int qqq = 0; qqq < paths.size(); qqq++) {
791  // std::cout << "pathcheck" << std::endl;
792  //int pathevals = 0;
793  //std::vector<int> zpt = zipPath2(paths[qqq], g);
794  //std::set<std::vector<int> > boxpaths;
795  std::set<std::vector<int> > movepaths;
796  std::vector<int> path;// = paths[qqq];
797  path = paths[qqq];//unzipPath(paths[qqq], g, begin, end);
798  truepaths++;
799  int permnums = 1;
800  std::vector<int> perms;
801  std::vector<unsigned int> qs;
802  std::map<int, std::vector<std::vector<int> > > localLoops;
803  std::vector<int> takenLoops;
804  takenLoops.push_back(path[0]);
805  bool taken = false;
806  //timeval timfor;
807  int lost = 0;
808  //gettimeofday(&timfor, NULL);
809  //double t1for = timfor.tv_sec + (timfor.tv_usec/1000000);
810  for (unsigned int q = 1; q < path.size()-1; q++) {
811  //if (find(closures.begin(), closures.end(), path[q]) != closures.end()) {
812  if (globalLoopPaths.find(path[q]) != globalLoopPaths.end() /*&& find(lloops.begin(), lloops.end(), path[q]) != lloops.end()*/ && globalLoopPaths[path[q]].size() != 0 /*&& path[q] != begin && path[q] != end*/) {
813  for (unsigned int qp1 = 0; qp1 < globalLoopPaths[path[q]].size(); qp1++) {
814 
815  std::vector<int> gp = globalLoopPaths[path[q]][qp1]; //unzipPath(globalLoopPaths[path[q]][qp1],g,path[q],path[q]);
816  // std::vector<int> zgp = zipPath2(globalLoopPaths[zpt[q]][qp1], g);
817  for (unsigned int qp2 = 0; qp2 < takenLoops.size(); qp2++) {
818  if (find(gp.begin(),gp.end(), takenLoops[qp2]) != gp.end()) {
819  taken = true;
820  }
821  }
822 
823  if (!taken) {
824  localLoops[path[q]].push_back(gp);
825  }
826  else {
827  lost++;
828  taken = false;
829  }
830  }
831  if (localLoops[path[q]].size() != 0) {
832  takenLoops.push_back(path[q]);
833  permnums *= (localLoops[path[q]].size()+1);
834  perms.push_back(permnums);
835  qs.push_back(path[q]);
836  }
837  }
838  }
839 
840  //}
841  //if (loop) {
842  //std::cout << "lostloop: " << lost << std::endl;
843  //}
844  //else {
845  //std::cout << "lostpath: " << lost << std::endl;
846  //}
847  //std::cout << "endpathcheck" << std::endl;
848  //std::cout << "rest" << std::endl;
849  //std::cout << "permnums: " << permnums << std::endl;
850  //gettimeofday(&timfor, NULL);
851  //double t2for = timfor.tv_sec + (timfor.tv_usec/1000000);
852  //double ttfor = t2for - t1for;
853  //#pragma omp atomic
854  //ttfors += ttfor;
855 
856  //std::set<std::vector<int> > movepaths2;
857  std::set<std::vector<int> > movepathscheck;
858  //timeval timperms;
859  //gettimeofday(&timperms, NULL);
860  // double t1perm = timperms.tv_sec + (timperms.tv_usec/1000000);
861  std::vector<int> nvec;
862  std::vector<std::vector<int> > boxpaths(permnums, nvec);
863  //#pragma omp parallel for schedule(guided)
864  for (int i = 1; i <= permnums; i++) {
865  //bool goodthread = false;
866  std::vector<int> loopsTaken;
867  //bool stop = false;
868  unsigned int j = 0;
869  std::vector<int> npath;
870  while (true) {
871  if (j == perms.size() || perms[j] > i) {
872  break;
873  }
874  else {
875  j++;
876  }
877  }
878  int pn = i;
879  std::vector<int> pL;
880  for (unsigned int j1 = 0; j1 <= j; j1++) {
881  pL.push_back(-1);
882  }
883  for (unsigned int k = j; k > 0; k--) {
884  int l = 1;
885  while (perms[k-1]*l < pn) {
886  l++;
887  }
888  pL[k] = l-2;
889  pn -= (perms[k-1]*(l-1));
890  }
891  pL[0] = pn-2;
892 
893  unsigned int q2 = 0;
894  for (unsigned int q1 = 0; q1 < path.size(); q1++) {
895  if (q2 < qs.size()) {
896  if (qs.size() != 0 && (unsigned)path[q1] == qs[q2] && (size_t)q2 != pL.size()) {
897  if (pL[q2] == -1) {
898  npath.push_back(path[q1]);
899  }
900  else {
901  // if (!stop) {
902  npath.insert(npath.end(), localLoops[path[q1]][pL[q2]].begin(),
903  localLoops[path[q1]][pL[q2]].end());
904  // }
905  }
906  q2++;
907  }
908  else {
909  npath.push_back(path[q1]);
910  }
911  }
912  else {
913  npath.push_back(path[q1]);
914  }
915  }
916  #ifdef FULLDEBUG
917  std::cout << "path: " << std::endl;
918  for (int qe = 0; qe < npath.size(); qe++) {
919  std::cout << ", " << npath[qe];
920  }
921  std::cout << std::endl;
922  std::cout << "permnum: " << i << std::endl;
923  #endif
924  // bool addit = false;
925  //if (!stop) {
926  // if (loop && npath.front() == npath.back()) {
927  // addit = true;
928  // }
929  // else if (!loop && bound && npath.front() == begin && npath.back() == end && npath.size() != 1) {
930  // addit = true;
931  // }
932  // else if (!loop && !bound) {
933  // addit = true;
934  // }
935  // if (!addit) {
936  // std::cout << "bad path" << std::endl;
937  // }
938  //bool extra = false;
939  //if (addit && !loop) {
940  //if (movepathscheck.find(npath) == movepathscheck.end()) {
941  //int mpc = movepathscheck.size();
942  //std::set<std::vector<int> > movepathspre = movepathscheck;
943  // movepaths2.insert(npath);
944  //movepathscheck.insert(npath);
945  //ROSE_ASSERT(movepathscheck.size() == mpc || movepathspre.find(npath) == movepathspre.end());
946  //if (movepathscheck.size() == mpc) {
947  // extra = true;
948  // }
949 
950  //}
951  //else {
952  //#pragma omp atomic
953  // doubledpaths++;
954  // }
955  //}
956 
957  //if (!workingthread || threadsafe) {
958  //if ((newpaths.size() > 1 || i == permnums || threadsafe)) {
959  // }
960  // }
961 
962  // }
963  //if (!extra)
964  // {
965  //if (movepaths2.size() > 0) //|| i == permnums || threadsafe)
966  // #pragma omp critical
967  // {
968  boxpaths[i-1] = npath;
969  // }
970  // }
971  //std::cout << "endrest" << std::endl;
972  }
973 
974  evaledpaths += boxpaths.size();
975  if (evaledpaths > newmil*100000ull) {
976  //std::cout << "evaledpaths: " << evaledpaths << std::endl;
977  newmil++;
978  }
979  // #pragma omp critical
980  // {
981  if (!loop) {
982  for (std::vector<std::vector<int> >::iterator box = boxpaths.begin(); box != boxpaths.end(); box++) {
983  std::vector<Vertex> verts;
984  getVertexPath((*box), g, verts);
985  #pragma omp critical
986  {
987  analyzePath(verts);
988  }
989  }
990  }
991  else {
992  #pragma omp critical
993  {
994  loopPaths.insert(boxpaths.begin(), boxpaths.end());;
995  }
996  }
997  }
998  }
999  //}
1000 
1001 /*
1002  #pragma omp atomic
1003  evaledpaths++;
1004  //pathevals++;
1005  if (evaledpaths % 10000 == 0 && evaledpaths != 0) {
1006  std::cout << "evaled paths: " << evaledpaths << std::endl;
1007  }
1008  if (!loop) {
1009  std::vector<Vertex> verts;
1010  getVertexPath(npath, g, verts);
1011  #pragma omp critical
1012  {
1013  #ifdef FULLDEBUG
1014  for (unsigned int aa = 0; aa < npath.size(); aa++) {
1015  if (ptsNum.find(npath[aa]) != ptsNum.end()) {
1016  ptsNum[npath[aa]] += 1;
1017  }
1018  else {
1019  ptsNum[npath[aa]] = 1;
1020  }
1021  }
1022  #endif
1023  analyzePath(verts);
1024  }
1025  }
1026  else if (loop)
1027  {
1028  //std::vector<int> zpth = zipPath(npath, g, npath.front(), npath.back());
1029  #pragma omp critical
1030  {
1031  loopPaths.insert(npath);//zipPath(npath, g, npath.front(), npath.back()));
1032  }
1033  }
1034  else {
1035  }
1036 
1037  }
1038 */
1039 
1040  // movepaths2.clear();
1041 
1042  // std::cout << "permnums: " << permnums << std::endl;
1043  // std::cout << "evaledpaths final: " << pathevals << std::endl;
1044  //gettimeofday(&timperms, NULL);
1045  //double t2perm = timperms.tv_sec+(timperms.tv_usec/1000000);
1046  //#pragma omp atomic
1047  //tperms += t2perm - t1perm;
1048  // }
1049  //}
1050  //}
1051  //}
1052 
1053 
1054 
1055 
1056 
1057 
1058  #ifdef PERFDEBUG
1059  //gettimeofday(&tim, NULL);
1060  // double t2 = tim.tv_sec+(tim.tv_usec/1000000.0);
1061  // double tperm = t2 - t1perm
1062  //double tX = t2 - t1;
1063  //std::cout << "begin: " << begin << " end: " << end << std::endl;
1064  // std::cout << "uTraverse time: " << tX << std::endl;
1065  // std::cout << "tperms: " << tperms << std::endl;
1066  // std::cout << "ttfors: " << ttfors << std::endl;
1067  // std::cout << "doubledpaths: " << doubledpaths << std::endl;
1068  #endif
1069  #ifdef LP
1070  if (loop) {
1071  #ifdef PERFDEBUG
1072  // std::cout << "loopPaths: " << loopPaths.size() << std::endl;
1073  #endif
1074  loopStore[begin] = loopPaths;
1075  }
1076  #endif
1077  return loopPaths;
1078 
1079  }
1080  }
1081 
1082 
1083 
1084 
1085 
1086 
1087 
1088 
1100 template<class CFG>
1101 void
1102 SgGraphTraversal<CFG>::
1103 constructPathAnalyzer(CFG* g, bool unbounded, Vertex begin, Vertex end, bool ns) {
1104  abnormals = 0;
1105  normals = 0;
1106  if (ns) {
1107  needssafety = true;
1108  }
1109  else {
1110  needssafety = false;
1111  }
1112  checkedfound = 0;
1113  recursed = 0;
1114  nextsubpath = 0;
1115  borrowed = true;
1116  stoppedpaths = 0;
1117  evaledpaths = 0;
1118  badpaths = 0;
1119  sourcenum = 0;
1120  prepareGraph(g);
1121  workingthread = false;
1122  workingthreadnum = -1;
1123  //std::cout << "markers: " << markers.size() << std::endl;
1124  //std::cout << "closures: " << closures.size() << std::endl;
1125  //std::cout << "sources: " << sources.size() << std::endl;
1126  //std::cout << "sinks" << sinks.size() << std::endl;
1127 // printHotness(g);
1128  bool subgraph = false;
1129  if (!subgraph) {
1130  if (!unbounded) {
1131  bound = true;
1132  recursiveLoops.clear();
1133  recurses.clear();
1134  std::vector<std::vector<int> > spaths = bfsTraversePath(vertintmap[begin], vertintmap[end], g);
1135  // std::cout << "spaths: " << spaths.size() << std::endl;
1136  }
1137  else {
1138  std::set<int> usedsources;
1139  bound = false;
1140  std::vector<int> localLps;
1141  for (unsigned int j = 0; j < sources.size(); j++) {
1142  sourcenum = sources[j];
1143  recursiveLoops.clear();
1144  recurses.clear();
1145  std::vector<std::vector<int> > spaths = bfsTraversePath(sources[j], -1, g);
1146 
1147 
1148  }
1149  }
1150  }
1151  //std::cout << "checkedfound: " << checkedfound << std::endl;
1152  printHotness(g);
1153 }
1154 
1165 template<class CFG>
1166 void
1167 SgGraphTraversal<CFG>::
1168 computeSubGraphs(const int& begin, const int &end, CFG*& g, int depthDifferential) {
1169  int minDepth = 0;
1170  int maxDepth = minDepth + depthDifferential;
1171  int currSubGraph = 0;
1172  CFG* subGraph;
1173  std::set<int> foundNodes;
1174  while (true) {
1175  Vertex begin = boost::add_vertex(*subGraphVector[currSubGraph]);
1176  GraphSubGraphMap[currSubGraph][intvertmap[orderOfNodes[minDepth]]] = intvertmap[begin];
1177  SubGraphGraphMap[currSubGraph][intvertmap[begin]] = intvertmap[orderOfNodes[minDepth]];
1178  for (int i = minDepth; i <= maxDepth; i++) {
1179  Vertex v = GraphSubGraphMap[currSubGraph][intvertmap[orderOfNodes[i]]];
1180  std::vector<int> outEdges = getOutEdges(orderOfNodes[i], g);
1181  for (unsigned int j = 0; j < outEdges.size(); j++) {
1182  Vertex u;
1183  if (foundNodes.find(getTarget(outEdges[j], g)) == foundNodes.end()) {
1184  u = GraphSubGraphMap[currSubGraph][intvertmap[getTarget(outEdges[j], g)]];
1185  }
1186  else {
1187  u = boost::add_vertex(*subGraphVector[currSubGraph]);
1188  foundNodes.insert(getTarget(outEdges[j], g));
1189  SubGraphGraphMap[currSubGraph][u] = intvertmap[getTarget(outEdges[j], g)];
1190  GraphSubGraphMap[currSubGraph][intvertmap[getTarget(outEdges[j], g)]] = u;
1191 
1192  }
1193  Edge edge;
1194  bool ok;
1195  boost::tie(edge, ok) = boost::add_edge(v,u,*subGraphVector[currSubGraph]);
1196  }
1197  }
1198  minDepth = maxDepth;
1199  if ((unsigned int) minDepth == orderOfNodes.size()-1) {
1200  break;
1201  }
1202  maxDepth += depthDifferential;
1203  if ((unsigned int) maxDepth > orderOfNodes.size()-1)
1204  {
1205  maxDepth = orderOfNodes.size()-1;
1206  }
1207  CFG* newSubGraph;
1208  subGraphVector.push_back(newSubGraph);
1209  currSubGraph++;
1210  }
1211  return;
1212 }
1213 
1214 
1215 /*
1216 These should NOT be used by the user. They are simply for writing interesting information on the DOT graphs of the CFG
1217 */
1218 
1219 
1220 
1221  template<class CFG>
1222  void
1223  SgGraphTraversal<CFG>::
1224  printCFGNodeGeneric(int &cf, std::string prop, std::ofstream& o) {
1225  std::string nodeColor = "black";
1226  o << cf << " [label=\"" << " num:" << cf << " prop: " << prop << "\", color=\"" << nodeColor << "\", style=\"" << "solid" << "\"];\n";
1227  }
1228 
1229  template<class CFG>
1230  void
1231  SgGraphTraversal<CFG>::
1232  printCFGNode(int& cf, std::ofstream& o)
1233  {
1234  #ifdef FULLDEBUG
1235  int pts = ptsNum[cf];
1236  std::string nodeColor = "black";
1237  o << cf << " [label=\"" << " pts: " << pts << "\", color=\"" << nodeColor << "\", style=\"" << "solid" << "\"];\n";
1238  #endif
1239  #ifndef FULLDEBUG
1240  std::string nodeColor = "black";
1241  o << cf << " [label=\"" << " num:" << cf << "\", color=\"" << nodeColor << "\", style=\"" << "solid" << "\"];\n";
1242  #endif
1243 
1244  }
1245 
1246  template<class CFG>
1247  void
1248  SgGraphTraversal<CFG>::
1249  printCFGEdge(int& cf, CFG*& cfg, std::ofstream& o)
1250  {
1251  int src = getSource(cf, cfg);
1252  int tar = getTarget(cf, cfg);
1253  o << src << " -> " << tar << " [label=\"" << src << " " << tar << "\", style=\"" << "solid" << "\"];\n";
1254  }
1255 
1256  template<class CFG>
1257  void
1258  SgGraphTraversal<CFG>::
1259  printHotness(CFG*& g)
1260  {
1261  const CFG* gc = g;
1262  int currhot = 0;
1263  std::ofstream mf;
1264  std::stringstream filenam;
1265  filenam << "hotness" << currhot << ".dot";
1266  currhot++;
1267  std::string fn = filenam.str();
1268  mf.open(fn.c_str());
1269 
1270  mf << "digraph defaultName { \n";
1271  vertex_iterator v, vend;
1272  edge_iterator e, eend;
1273  for (tie(v, vend) = vertices(*gc); v != vend; ++v)
1274  {
1275  printCFGNode(vertintmap[*v], mf);
1276  }
1277  for (tie(e, eend) = edges(*gc); e != eend; ++e)
1278  {
1279  printCFGEdge(edgeintmap[*e], g, mf);
1280  }
1281  mf.close();
1282  }
1283  template<class CFG>
1284  void
1285  SgGraphTraversal<CFG>::
1286  printPathDot(CFG*& g)
1287  {
1288  const CFG* gc = g;
1289  std::ofstream mf;
1290  std::stringstream filenam;
1291  filenam << "pathnums.dot";
1292  std::string fn = filenam.str();
1293  mf.open(fn.c_str());
1294 
1295  mf << "digraph defaultName { \n";
1296  vertex_iterator v, vend;
1297  edge_iterator e, eend;
1298  for (tie(v, vend) = vertices(*gc); v != vend; ++v)
1299  {
1300  if (nodeStrings.find(vertintmap[*v]) != nodeStrings.end()) {
1301  int nn = vertintmap[*v];
1302  printCFGNodeGeneric(vertintmap[*v], nodeStrings[nn], mf);
1303  }
1304  else {
1305  printCFGNodeGeneric(vertintmap[*v], "noprop", mf);
1306  }
1307  }
1308  for (tie(e, eend) = edges(*gc); e != eend; ++e)
1309  {
1310  printCFGEdge(edgeintmap[*e], g, mf);
1311  }
1312 
1313  mf.close();
1314  }
1315 
1316 
1317 
1327 template<class CFG>
1328 void
1329 SgGraphTraversal<CFG>::
1330 prepareGraph(CFG*& g) {
1331  nextNode = 1;
1332  nextEdge = 1;
1333  findClosuresAndMarkersAndEnumerate(g);
1334 }
1335 
1336 
1348 template<class CFG>
1349 void
1350 SgGraphTraversal<CFG>::
1351 firstPrepGraph(CFG*& g) {
1352  nextNode = 1;
1353  nextEdge = 1;
1354  findClosuresAndMarkersAndEnumerate(g);
1355 }
1356 
1368 template<class CFG>
1369 void
1370 SgGraphTraversal<CFG>::
1371 findClosuresAndMarkersAndEnumerate(CFG*& g)
1372 {
1373  edge_iterator e, eend;
1374  for (tie(e, eend) = edges(*g); e != eend; ++e) {
1375  intedgemap[nextEdge] = *e;
1376  edgeintmap[*e] = nextEdge;
1377  nextEdge++;
1378  }
1379  vertex_iterator v1, vend1;
1380  for (tie(v1, vend1) = vertices(*g); v1 != vend1; ++v1)
1381  {
1382  vertintmap[*v1] = nextNode;
1383  intvertmap[nextNode] = *v1;
1384  nextNode++;
1385  }
1386  vertex_iterator v, vend;
1387  for (tie(v, vend) = vertices(*g); v != vend; ++v) {
1388  std::vector<int> outs = getOutEdges(vertintmap[*v], g);
1389  std::vector<int> ins = getInEdges(vertintmap[*v], g);
1390  if (outs.size() > 1)
1391  {
1392  markers.push_back(vertintmap[*v]);
1393 
1394  markerIndex[vertintmap[*v]] = markers.size()-1;
1395  for (unsigned int i = 0; i < outs.size(); i++) {
1396  pathsAtMarkers[vertintmap[*v]].push_back(getTarget(outs[i], g));
1397  }
1398  }
1399  if (ins.size() > 1)
1400  {
1401  closures.push_back(vertintmap[*v]);
1402  }
1403  if (outs.size() == 0) {
1404  sinks.push_back(vertintmap[*v]);
1405  }
1406  if (ins.size() == 0) {
1407  sources.push_back(vertintmap[*v]);
1408  }
1409  }
1410  return;
1411 }
1412 
1413 
1414 
1421 template<class CFG>
1422 void
1423 SgGraphTraversal<CFG>::
1424 computeOrder(CFG*& g, const int& begin) {
1425  std::vector<int> currentNodes;
1426  std::vector<int> newCurrentNodes;
1427  currentNodes.push_back(begin);
1428  std::map<int, int> reverseCurrents;
1429  orderOfNodes.push_back(begin);
1430  std::set<int> heldBackNodes;
1431  while (currentNodes.size() != 0) {
1432  for (unsigned int j = 0; j < currentNodes.size(); j++) {
1433 
1434  std::vector<int> inEdges = getInEdges(currentNodes[j], g);
1435  if (inEdges.size() > 1) {
1436  if (reverseCurrents.find(currentNodes[j]) == reverseCurrents.end()) {
1437  reverseCurrents[currentNodes[j]] = 0;
1438  }
1439  if ((unsigned int) reverseCurrents[currentNodes[j]] == inEdges.size() - 1) {
1440  heldBackNodes.erase(currentNodes[j]);
1441  reverseCurrents[currentNodes[j]]++;
1442  std::vector<int> outEdges = getOutEdges(currentNodes[j], g);
1443  for (unsigned int k = 0; k < outEdges.size(); k++) {
1444  newCurrentNodes.push_back(getTarget(outEdges[k], g));
1445  orderOfNodes.push_back(getTarget(outEdges[k], g));
1446  }
1447  }
1448  else if (reverseCurrents[currentNodes[j]] < reverseCurrents.size()) {
1449  reverseCurrents[currentNodes[j]]++;
1450  if (heldBackNodes.find(currentNodes[j]) == heldBackNodes.end()) {
1451  heldBackNodes.insert(currentNodes[j]);
1452  }
1453  }
1454  }
1455  else {
1456  std::vector<int> outEdges = getOutEdges(currentNodes[j], g);
1457  for (unsigned int k = 0; k < outEdges.size(); k++) {
1458  newCurrentNodes.push_back(getTarget(outEdges[k], g));
1459  orderOfNodes.push_back(getTarget(outEdges[k], g));
1460 
1461  }
1462  }
1463  }
1464  if (newCurrentNodes.size() == 0 && heldBackNodes.size() != 0) {
1465  for (std::set<int>::iterator q = heldBackNodes.begin(); q != heldBackNodes.end(); q++) {
1466  int qint = *q;
1467  std::vector<int> heldBackOutEdges = getOutEdges(qint, g);
1468  for (unsigned int p = 0; p < heldBackOutEdges.size(); p++) {
1469  newCurrentNodes.push_back(getTarget(heldBackOutEdges[p], g));
1470  }
1471  }
1472  heldBackNodes.clear();
1473  }
1474  currentNodes = newCurrentNodes;
1475  newCurrentNodes.clear();
1476  }
1477  return;
1478 }
1479 
1489 template<class CFG>
1490 void
1491 SgGraphTraversal<CFG>::
1492 getVertexPath(std::vector<int> path, CFG*& g, std::vector<Vertex>& vertexPath) {
1493  for (unsigned int i = 0; i < path.size(); i++) {
1494  vertexPath.push_back(intvertmap[path[i]]);
1495  }
1496 
1497 
1498 
1499 }
1500 
1507 template<class CFG>
1508 void
1509 SgGraphTraversal<CFG>::
1510 storeCompact(std::vector<int> compactPath) {
1511 return;
1512 }
1513 
1514 
1515 
1516 
1517