PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include "genC.h"
#include "boolean.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
#include "polyedre.h"
#include "union.h"
#include "matrix.h"
#include "ri.h"
#include "graph.h"
#include "dg.h"
#include "misc.h"
#include "ri-util.h"
#include "properties.h"
#include "constants.h"
#include "rice.h"
#include "ricedg.h"
#include "complexity_ri.h"
#include "database.h"
#include "parser_private.h"
#include "property.h"
#include "reduction.h"
#include "tiling.h"
#include "text.h"
#include "text-util.h"
#include "pipsdbm.h"
#include "paf_ri.h"
#include "paf-util.h"
#include "resources.h"
#include "scheduling.h"
Go to the source code of this file.
Macros | |
#define | MY_MIN(a, b) ((a)>(b)?(b):(a)) |
=================================================================== More... | |
#define | NEW_MARK 1 |
#define | OLD_MARK 2 |
#define | DFG_MARK_OLD(v) |
#define | DFG_MARK_NEW(v) |
#define | DFG_MARKED_NEW_P(v) |
#define | DFG_VERTEX_ENCLOSING_SCC(v) |
Typedefs | |
typedef dfg_arc_label | arc_label |
lint More... | |
typedef dfg_vertex_label | vertex_label |
Functions | |
int | dfg_is_in_stack (vertex v) |
================================================================= More... | |
void | dfg_low_link_compute (graph g, vertex v) |
================================================================= More... | |
sccs | dfg_find_sccs (graph g) |
================================================================= More... | |
void | fprint_sccs (FILE *fp, sccs obj) |
=========================================================================== More... | |
vertex | dfg_in_vertex_list (list l, vertex v) |
================================================================= More... | |
graph | dfg_reverse_graph (graph g) |
====================================================================== More... | |
Variables | |
char | vcid_scheduling_sccdfg [] = "$Id: sccdfg.c 23065 2016-03-02 09:05:50Z coelho $" |
static int | Count |
A set of variables shared by the functions of this package. More... | |
static int | StackPointer |
static vertex * | Stack |
static sccs | Components |
#define DFG_MARK_NEW | ( | v | ) |
#define DFG_MARK_OLD | ( | v | ) |
#define DFG_MARKED_NEW_P | ( | v | ) |
#define DFG_VERTEX_ENCLOSING_SCC | ( | v | ) |
#define MY_MIN | ( | a, | |
b | |||
) | ((a)>(b)?(b):(a)) |
===================================================================
This collection of functions implements Tarjan's algorithm to find the strongly connected components of a directed graph.
this algorithm is presented in: Types de Donnees et Algorithmes Recherche, Tri, Algorithmes sur les Graphes Marie-Claude Gaudel, Michele Soria, Christine Froidevaux Collection Didactique
A set of macros to mark a vertex as 'not visited' or 'visited' and to check if a node has already been visited.
typedef dfg_arc_label arc_label |
typedef dfg_vertex_label vertex_label |
=================================================================
dfg_find_sccs is the interface function to compute the SCCs of a graph. It marks all nodes as 'not visited' and then apply the main function dfg_low_link_compute() on all vertices.
AC 93/10/19
Definition at line 223 of file sccdfg.c.
References CAR, CDR, Components, Count, dfg_low_link_compute(), DFG_MARKED_NEW_P, dfg_vertex_label_sccflags, free(), gen_length(), graph_vertices, make_sccflags(), make_sccs(), malloc(), MAPL, NIL, scc_undefined, Stack, StackPointer, VERTEX, and vertex_vertex_label.
Referenced by scheduling().
=================================================================
The following functions are used to build the reverse graph of a
================================================================= vertex dfg_in_vertex_list((list) l, (vertex) v): Input : A list l of vertices. A vertex v of a dataflow graph. Returns vertex_undefined if v is not in list l. Returns v' that has the same statement_ordering than v.
AC 93/10/19
Definition at line 308 of file sccdfg.c.
References CAR, dfg_vertex_label_statement, ENDP, POP, VERTEX, vertex_undefined, and vertex_vertex_label.
Referenced by dfg_reverse_graph().
=================================================================
int dfg_is_in_stack(v) : this function checks if vertex v is in the stack.
AC 93/10/18
Definition at line 135 of file sccdfg.c.
References Stack, and StackPointer.
Referenced by dfg_low_link_compute().
=================================================================
dfg_low_link_compute() is the main function. Its behavior is explained in the book mentionned ealier.
AC 93/10/18
Definition at line 154 of file sccdfg.c.
References CAR, Components, CONS, Count, dfg_is_in_stack(), DFG_MARK_OLD, DFG_MARKED_NEW_P, dfg_vertex_label_sccflags, gen_nconc(), make_scc(), MAPL, MY_MIN, NIL, SCC, scc_vertices, sccflags_dfnumber, sccflags_enclosing_scc, sccflags_lowlink, sccs_sccs, Stack, StackPointer, SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_vertex_label.
Referenced by dfg_find_sccs().
======================================================================
graph dfg_reverse_graph((graph) g): This function is used to reverse Pips's graph in order to have all possible sources directly (Feautrier's dependance graph).
AC 93/10/19
Definition at line 339 of file sccdfg.c.
References ADD_ELEMENT_TO_LIST, CAR, copy_dfg_vertex_label(), dfg_in_vertex_list(), graph_undefined, graph_vertices, make_graph(), make_successor(), make_vertex(), MAPL, NIL, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, vertex_undefined, and vertex_vertex_label.
Referenced by scheduling().
void fprint_sccs | ( | FILE * | fp, |
sccs | obj | ||
) |
===========================================================================
void fprint_sccs(FILE *fp, sccs obj): prints in the file "fp" the list of strongly connected components "obj".
AC 93/10/20
Definition at line 258 of file sccdfg.c.
References CAR, CDR, DATAFLOW, dfg_arc_label_dataflows, fprint_dataflow(), fprintf(), NIL, SCC, scc_vertices, sccs_sccs, sink_stmt, source_stmt, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_int_stmt(), and vertex_successors.
Referenced by scheduling().
|
static |
Definition at line 126 of file sccdfg.c.
Referenced by dfg_find_sccs(), dfg_low_link_compute(), FindAndTopSortSccs(), FindSccs(), LowlinkCompute(), and TopSortSccs().
|
static |
A set of variables shared by the functions of this package.
The
stack contains the current SCC, i.e. the SCC currently being
built. Components is the result, i.e. a set of scc.
Definition at line 124 of file sccdfg.c.
Referenced by dfg_find_sccs(), and dfg_low_link_compute().
|
static |
Definition at line 125 of file sccdfg.c.
Referenced by dfg_find_sccs(), dfg_is_in_stack(), and dfg_low_link_compute().
|
static |
Definition at line 124 of file sccdfg.c.
Referenced by dfg_find_sccs(), dfg_is_in_stack(), and dfg_low_link_compute().