GCC Middle and Back End API Reference
graphds.h File Reference
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  graph_edge
struct  vertex
struct  graph

Typedefs

typedef void(* graphds_edge_callback )(struct graph *, struct graph_edge *)

Functions

struct graphnew_graph (int)
void dump_graph (FILE *, struct graph *)
struct graph_edgeadd_edge (struct graph *, int, int)
void identify_vertices (struct graph *, int, int)
int graphds_dfs (struct graph *, int *, int, vec< int > *, bool, bitmap)
int graphds_scc (struct graph *, bitmap)
void graphds_domtree (struct graph *, int, int *, int *, int *)
void for_each_edge (struct graph *, graphds_edge_callback)
void free_graph (struct graph *g)

Typedef Documentation

typedef void(* graphds_edge_callback)(struct graph *, struct graph_edge *)

Function Documentation

struct graph_edge* add_edge ( struct graph ,
int  ,
int   
)
read
void dump_graph ( FILE *  ,
struct graph  
)
void for_each_edge ( struct graph ,
graphds_edge_callback   
)
void free_graph ( struct graph g)
int graphds_dfs ( struct graph g,
int *  qs,
int  nq,
vec< int > *  qt,
bool  forward,
bitmap  subgraph 
)

Runs dfs search over vertices of G, from NQ vertices in queue QS. The vertices in postorder are stored into QT. If FORWARD is false, backward dfs is run. If SUBGRAPH is not NULL, it specifies the subgraph of G to run DFS on. Returns the number of the components of the graph (number of the restarts of DFS).

References vertex::component, vertex::post, and graph::vertices.

void graphds_domtree ( struct graph g,
int  entry,
int *  parent,
int *  son,
int *  brother 
)

Determines the dominance tree of G (stored in the PARENT, SON and BROTHER arrays), where the entry node is ENTRY.

We use a slight modification of the standard iterative algorithm, as described in

K. D. Cooper, T. J. Harvey and K. Kennedy: A Simple, Fast Dominance Algorithm

sort vertices in reverse postorder foreach v dom(v) = everything dom(entry) = entry;

while (anything changes) foreach v dom(v) = {v} union (intersection of dom(p) over all predecessors of v)

The sets dom(v) are represented by the parent links in the current version of the dominance tree.

int graphds_scc ( struct graph ,
bitmap   
)
void identify_vertices ( struct graph ,
int  ,
int   
)
struct graph* new_graph ( int  )
read