#include <set>
#include "graphSorting.hh"
#include <string>
#include <list>
#include <stack>
#include <map>
#include "tlib.hh"
Go to the source code of this file.
Functions | |
static void | setOrder (Loop *l, int order, lgraph &V) |
Set the order of a loop and place it to appropriate set. | |
static void | setLevel (int order, const lset &T1, lset &T2, lgraph &V) |
Set the order of T1's loops and collect there sons into T2. | |
static void | resetOrder (Loop *l) |
void | sortGraph (Loop *root, lgraph &V) |
Topological sort of an acyclic graph of loops. |
static void resetOrder | ( | Loop * | l | ) | [static] |
Definition at line 27 of file graphSorting.cpp.
References Loop::fBackwardLoopDependencies, and Loop::fOrder.
Referenced by sortGraph().
00028 { 00029 l->fOrder = -1; 00030 for (lset::const_iterator p = l->fBackwardLoopDependencies.begin(); p!=l->fBackwardLoopDependencies.end(); p++) { 00031 resetOrder(*p); 00032 } 00033 }
Set the order of T1's loops and collect there sons into T2.
Definition at line 18 of file graphSorting.cpp.
References setOrder().
Referenced by sortGraph().
00019 { 00020 for (lset::const_iterator p = T1.begin(); p!=T1.end(); p++) { 00021 setOrder(*p, order, V); 00022 T2.insert((*p)->fBackwardLoopDependencies.begin(), (*p)->fBackwardLoopDependencies.end()); 00023 } 00024 }
Set the order of a loop and place it to appropriate set.
Definition at line 7 of file graphSorting.cpp.
References Loop::fOrder.
Referenced by setLevel().
00008 { 00009 assert(l); 00010 V.resize(order+1); 00011 if (l->fOrder >= 0) { V[l->fOrder].erase(l); } 00012 l->fOrder = order; V[order].insert(l); 00013 }
Topological sort of an acyclic graph of loops.
Topological sort of an acyclic graph of loops starting from its root.
The loops are collect in an lgraph : a vector of sets of loops
Definition at line 38 of file graphSorting.cpp.
References resetOrder(), and setLevel().
Referenced by Klass::buildTasksList(), Klass::printGraphDotFormat(), Klass::printLoopGraphInternal(), Klass::printLoopGraphOpenMP(), Klass::printLoopGraphScheduler(), and Klass::printLoopGraphVector().
00039 { 00040 lset T1, T2; 00041 int level; 00042 00043 assert(root); 00044 resetOrder(root); 00045 T1.insert(root); level=0; V.clear(); 00046 do { 00047 setLevel(level, T1, T2, V); 00048 T1=T2; T2.clear(); level++; 00049 } while (T1.size()>0); 00050 00051 // Erase empty levels 00052 lgraph::iterator p = V.begin(); 00053 while (p != V.end()) { 00054 if ((*p).size() == 1 && (*(*p).begin())->isEmpty()) { 00055 p = V.erase(p); 00056 } else { 00057 p++; 00058 } 00059 } 00060 }