graphSorting.cpp File Reference

#include <set>
#include "graphSorting.hh"

Include dependency graph for graphSorting.cpp:

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. More...
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. More...
static void	resetOrder (Loop *l)
void	sortGraph (Loop *root, lgraph &V)
	Topological sort of an acyclic graph of loops. More...

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().

{
    l->fOrder = -1;
    for (lset::const_iterator p = l->fBackwardLoopDependencies.begin(); p!=l->fBackwardLoopDependencies.end(); p++) {
        resetOrder(*p);
    }
}

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().

{
    for (lset::const_iterator p = T1.begin(); p!=T1.end(); p++) {
        setOrder(*p, order, V);
        T2.insert((*p)->fBackwardLoopDependencies.begin(), (*p)->fBackwardLoopDependencies.end());
    }
}

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().

{
    assert(l);
    V.resize(order+1);
    if (l->fOrder >= 0) { V[l->fOrder].erase(l); }
    l->fOrder = order; V[order].insert(l);
}

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().

{
    lset            T1, T2;
    int             level;
    
    assert(root);
    resetOrder(root);
    T1.insert(root); level=0; V.clear();
    do {
        setLevel(level, T1, T2, V); 
        T1=T2; T2.clear(); level++;
    } while (T1.size()>0);
    
    // Erase empty levels
    lgraph::iterator p = V.begin();
    while (p != V.end()) {
        if ((*p).size() == 1 && (*(*p).begin())->isEmpty()) {
            p = V.erase(p);
        } else {
            p++; 
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function: