---

nci/suif/suif2b/extratypes/sgraph_algs/sgraph_algs.cpp File Reference

#include "common/suif_copyright.h"
#include "sgraph/sgraph.h"
#include "sgraph_algs.h"
#include "sgraph/sgraph_iter.h"
#include "bit_vector/bit_vector.h"
#include "suifkernel/suifkernel_messages.h"
#include "suifkernel/suif_env.h"

Functions
BitVector*	build_reachable (const SGraph *the_sgraph, SGraphNode node, bool do_forward)
BitVector*	build_reachable (const SGraph *the_sgraph, SGraphNodeList *entries, bool do_forward)
SGraphNodeList*	build_reverse_postorder_list (const SGraph *the_sgraph, SGraphNode node, bool do_forward)
SGraphNodeList*	build_reverse_postorder_list (const SGraph *the_sgraph, const SGraphNodeList *entries, bool do_forward)
void	build_dominators (SGraphBit *domination, const SGraph *reachable, SGraphNodeList *rev_postord_list, SGraphNode start, bool do_forward)
void	build_immediate_dominators (SGraph *immed_doms, const SGraph *reachable, const SGraph *domination, SGraphNodeList *rev_postord_list, SGraphNode root, bool do_forward)
void	build_dominance_frontiers (SGraphBit *df_graph, const SGraph *the_sgraph, const SGraph *immediate_dominators, SGraphNode x, bool do_forward)
void	build_iterated_dominance_frontiers (SGraph *idf_graph, const SGraph *the_sgraph, const SGraph *dominators)
suif_vector<int>*	build_scc (const SGraph *the_sgraph)
unsigned	build_nodeid_to_sccid (const SGraph *the_sgraph, suif_vector<int>* nodeid_sccid)
	Build a nodeid -> sccid map. More...
unsigned	build_scc_graph (const SGraph* the_sgraph, suif_vector<int>* nodeid_sccid, SGraph* scc_graph)
	Build a SCC graph, where each node is a sccid. More...
unsigned	build_scc_subgraph (const SGraph* the_sgraph, suif_vector<int>* nodeid_sccid, int sccid, SGraph* scc_subgraph)
	Build a SCC subgraph, where all nodes belong to the same SCC component. More...
void	export_dot (const SGraph *the_sgraph, ion *out)
	Export non-named dot, unlike the following two functions.
void	export_named_dot (const SGraph *the_sgraph, ion *out, suif_vector<String>* name_map)
void	print_named (const SGraph *the_sgraph, ion *out, suif_vector<String> *name_map)
void	build_reverse_graph (SGraph *reverse, const SGraph *the_graph)
void	init_sgraph_algs (SuifEnv *s)

---

Function Documentation

void build_dominance_frontiers ( SGraphBit * df_graph, const SGraph * the_sgraph, const SGraph * immediate_dominators, SGraphNode x, bool do_forward)

void build_dominators ( SGraphBit * domination, const SGraph * reachable, SGraphNodeList * rev_postord_list, SGraphNode start, bool do_forward)

void build_immediate_dominators ( SGraph * immed_doms, const SGraph * reachable, const SGraph * domination, SGraphNodeList * rev_postord_list, SGraphNode root, bool do_forward)

void build_iterated_dominance_frontiers ( SGraph * idf_graph, const SGraph * the_sgraph, const SGraph * dominators)

unsigned build_nodeid_to_sccid ( const SGraph * the_sgraph, suif_vector<int>* nodeid_sccid)

Build a nodeid -> sccid map.

Each sccid identifies a Strongly-Connected-Component.

Parameters:

the_sgraph	IN the original SGraph.
nodeid_sccid	OUT the mapping from nodeid to sccid.

Returns:

number of scc components found.

BitVector * build_reachable ( const SGraph * the_sgraph, SGraphNodeList * entries, bool do_forward)

BitVector * build_reachable ( const SGraph * the_sgraph, SGraphNode node, bool do_forward)

void build_reverse_graph ( SGraph * reverse, const SGraph * the_graph)

SGraphNodeList * build_reverse_postorder_list ( const SGraph * the_sgraph, const SGraphNodeList * entries, bool do_forward)

SGraphNodeList * build_reverse_postorder_list ( const SGraph * the_sgraph, SGraphNode node, bool do_forward)

suif_vector<int>* build_scc<int> ( const SGraph * the_sgraph)

unsigned build_scc_graph ( const SGraph * the_sgraph, suif_vector<int>* nodeid_sccid, SGraph * scc_graph)

Build a SCC graph, where each node is a sccid.

Parameters:

the_sgraph	IN the original SGraph.
nodedi_sccid	IN the nodeid to sccid map, output of build_nodeid_to_sccid().
scc_graph	OUT the graph of sccid.

Returns:

number of nodes (sccid) added to scc_graph.

This function will add nodes and edges to scc_graph. Each node added represents a new scc component.

unsigned build_scc_subgraph ( const SGraph * the_sgraph, suif_vector<int>* nodeid_sccid, int sccid, SGraph * scc_subgraph)

Build a SCC subgraph, where all nodes belong to the same SCC component.

Parameters:

the_sgraph	IN the original SGraph.
nodeis_sccid	IN the nodeid to sccid map, output of build_nodeid_to_sccid().
sccid	IN identifies a scc component.
scc_subgraph	OUT containing all nodes of the scc component.

Returns:

number of nodes added to scc_subgraph.

void export_dot ( const SGraph * the_sgraph, ion * out)

Export non-named dot, unlike the following two functions.

void export_named_dot ( const SGraph * the_sgraph, ion * out, suif_vector<String>* name_map)

void init_sgraph_algs ( SuifEnv * s)

void print_named ( const SGraph * the_sgraph, ion * out, suif_vector<String>* name_map)

---