interpreter/preprocessor/faust-0.9.47mr3/compiler/parallelize/graphSorting.cpp

   1 #include <set>
   2 #include "graphSorting.hh"
   3
   4 /**
   5  * Set the order of a loop and place it to appropriate set
   6  */
   7 static void setOrder(Loop* l, int order, lgraph& V)
   8 {
   9     assert(l);
  10     V.resize(order+1);
  11     if (l->fOrder >= 0) { V[l->fOrder].erase(l); }
  12     l->fOrder = order; V[order].insert(l);
  13 }
  14
  15 /**
  16  * Set the order of T1's loops and collect there sons into T2
  17  */
  18 static void setLevel(int order, const lset& T1, lset& T2, lgraph& V)
  19 {
  20     for (lset::const_iterator p = T1.begin(); p!=T1.end(); p++) {
  21         setOrder(*p, order, V);
  22         T2.insert((*p)->fBackwardLoopDependencies.begin(), (*p)->fBackwardLoopDependencies.end());
  23     }
  24 }
  25
  26
  27 static void resetOrder(Loop* l)
  28 {
  29     l->fOrder = -1;
  30     for (lset::const_iterator p = l->fBackwardLoopDependencies.begin(); p!=l->fBackwardLoopDependencies.end(); p++) {
  31         resetOrder(*p);
  32     }
  33 }
  34 /**
  35  * Topological sort of an acyclic graph of loops. The loops
  36  * are collect in an lgraph : a vector of sets of loops
  37  */
  38 void sortGraph(Loop* root, lgraph& V)
  39 {
  40     lset            T1, T2;
  41     int             level;
  42
  43     assert(root);
  44     resetOrder(root);
  45     T1.insert(root); level=0; V.clear();
  46     do {
  47         setLevel(level, T1, T2, V);
  48         T1=T2; T2.clear(); level++;
  49     } while (T1.size()>0);
  50
  51     // Erase empty levels
  52     lgraph::iterator p = V.begin();
  53     while (p != V.end()) {
  54         if ((*p).size() == 1 && (*(*p).begin())->isEmpty()) {
  55             p = V.erase(p);
  56         } else {
  57             p++;
  58         }
  59     }
  60 }