1 #include <set>
2 #include "graphSorting.hh"
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 }
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 }
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;
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);
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 }