graphSorting.cpp File Reference

#include <set>
#include "graphSorting.hh"
#include <string>
#include <list>
#include <stack>
#include <map>
#include "tlib.hh"
Include dependency graph for graphSorting.cpp:
This graph shows which files directly or indirectly include this file:

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.

Function Documentation

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 }

Here is the caller graph for this function:

static void setLevel ( int  order,
const lset T1,
lset T2,
lgraph V 
) [static]

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

static void setOrder ( Loop l,
int  order,
lgraph V 
) [static]

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 }

Here is the caller graph for this function:

void sortGraph ( Loop root,
lgraph V 
)

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 }

Here is the call graph for this function:

Here is the caller graph for this function:

Generated on Thu Jul 15 15:47:05 2010 for FAUST compiler by  doxygen 1.6.3