PIPS
|
#include "local.h"
Go to the source code of this file.
Macros | |
#define | NEW_MARK 1 |
a set of macros to mark a vertex as 'not visited' or 'visited' and to check if a node has already been visited More... | |
#define | OLD_MARK 2 |
#define | MARK_OLD(v) |
#define | MARK_NEW(v) |
#define | MARKED_NEW_P(v) |
Functions | |
void | set_sccs_drivers (bool *ignore_this_vertex_fun, bool *ignore_this_successor_fun) |
void | reset_sccs_drivers () |
void | LowlinkCompute (graph g, set region, vertex v, int level, sccs Components) |
int | IsInStack (vertex v) |
this function checks if vertex v is in the stack More... | |
sccs | FindSccs (graph g, set region, int level) |
FindSccs is the interface function to compute the SCCs of a graph. More... | |
void | ComputeInDegree (graph g, set region, int l) |
list | TopSortSccs (graph __attribute__((unused)) g, set region, int l, sccs Components) |
list | FindAndTopSortSccs (graph g, set region, int l) |
void | PrintScc (scc s) |
void | PrintSccs (sccs ss) |
Variables | |
static int | Count |
a set of variables shared by the functions of this package. More... | |
static int | StackPointer |
static vertex * | Stack |
static bool(* | ignore_this_vertex_drv )(set, vertex)=0 |
static bool(* | ignore_this_successor_drv )(vertex, set, successor, int)=0 |
#define MARK_NEW | ( | v | ) |
#define MARK_OLD | ( | v | ) |
#define MARKED_NEW_P | ( | v | ) |
#define NEW_MARK 1 |
region | egion |
Definition at line 244 of file scc.c.
References FOREACH, graph_vertices, ignore_this_successor_drv, ignore_this_vertex_drv, region, scc_indegree, SUCCESSOR, successor_vertex, VERTEX, VERTEX_ENCLOSING_SCC, and vertex_successors.
Referenced by FindAndTopSortSccs().
region | egion |
Definition at line 317 of file scc.c.
References Components, ComputeInDegree(), FindSccs(), free(), gen_free_list(), ifdebug, pips_debug, prettyprint_dependence_graph(), region, sccs_sccs, statement_undefined, and TopSortSccs().
Referenced by CodeGenerate(), SimplifyGraph(), and SupressDependances().
FindSccs is the interface function to compute the SCCs of a graph.
It marks all nodes as 'not visited' and then apply the main function LowlinkCompute on all vertices.
A vertex is processed only if it belongs to region. Later, successors will be processed if they can be reached through arcs whose level is greater or equal to level.
g is a graph
region and level define a sub-graph of g
Bug FOREACH
region | egion |
level | evel |
Definition at line 206 of file scc.c.
References Components, Count, dg_vertex_label_sccflags, FOREACH, free(), gen_length(), graph_vertices, ifdebug, ignore_this_vertex_drv, level, LowlinkCompute(), make_sccflags(), make_sccs(), malloc(), MARKED_NEW_P, NEW_MARK, NIL, pips_debug, PrintSccs(), region, scc_undefined, sccflags_mark, sccflags_undefined, Stack, StackPointer, VERTEX, and vertex_vertex_label.
Referenced by FindAndTopSortSccs().
this function checks if vertex v is in the stack
Definition at line 183 of file scc.c.
References Stack, and StackPointer.
Referenced by LowlinkCompute().
region | egion |
level | evel |
Components | omponents |
Definition at line 115 of file scc.c.
References Components, CONS, Count, dg_vertex_label_sccflags, dg_vertex_label_statement, FOREACH, gen_nconc(), ignore_this_successor_drv, ignore_this_vertex_drv, IsInStack(), level, LowlinkCompute(), make_scc(), MARK_OLD, MARKED_NEW_P, MIN, NIL, ordering_to_statement(), pips_debug, region, SCC, scc_vertices, sccflags_dfnumber, sccflags_enclosing_scc, sccflags_lowlink, sccflags_mark, sccs_sccs, Stack, StackPointer, statement_number, SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_vertex_label.
Referenced by FindSccs(), and LowlinkCompute().
void PrintScc | ( | scc | s | ) |
Definition at line 346 of file scc.c.
References FOREACH, fprintf(), scc_indegree, scc_vertices, statement_number, VERTEX, and vertex_to_statement().
Referenced by ConnectedStatements(), and PrintSccs().
void PrintSccs | ( | sccs | ss | ) |
ss | s |
Definition at line 356 of file scc.c.
References CAR, ENDP, fprintf(), MAPL, PrintScc(), SCC, and sccs_sccs.
Referenced by FindSccs().
void reset_sccs_drivers | ( | void | ) |
Definition at line 98 of file scc.c.
References ignore_this_successor_drv, ignore_this_vertex_drv, and pips_assert.
Referenced by CodeGenerate(), SimplifyGraph(), and SupressDependances().
Definition at line 88 of file scc.c.
References ignore_this_successor_drv, ignore_this_vertex_drv, and pips_assert.
Definition at line 262 of file scc.c.
References CAR, CDR, Components, CONS, FOREACH, fprintf(), ifdebug, ignore_this_successor_drv, ignore_this_vertex_drv, INSERT_AT_END, NIL, pips_debug, region, SCC, scc_indegree, scc_vertices, sccs_sccs, statement_number, SUCCESSOR, successor_vertex, VERTEX, VERTEX_ENCLOSING_SCC, vertex_successors, and vertex_to_statement().
Referenced by FindAndTopSortSccs().
|
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 74 of file scc.c.
Referenced by FindSccs(), and LowlinkCompute().
|
static |
Definition at line 82 of file scc.c.
Referenced by ComputeInDegree(), LowlinkCompute(), reset_sccs_drivers(), set_sccs_drivers(), and TopSortSccs().
Definition at line 81 of file scc.c.
Referenced by ComputeInDegree(), FindSccs(), LowlinkCompute(), reset_sccs_drivers(), set_sccs_drivers(), and TopSortSccs().
|
static |
Definition at line 75 of file scc.c.
Referenced by FindSccs(), IsInStack(), and LowlinkCompute().
|
static |
Definition at line 74 of file scc.c.
Referenced by FindSccs(), IsInStack(), and LowlinkCompute().