osprey/ir_tools/ir_graph.h File Reference

Go to the source code of this file.

Data Types

type vertex

type edge

type graph

type dfn

type v_iter

Defines

#define INVALID_EINDEX   -1

#define INVALID_VINDEX   -1

#define VERTEX_user(vertex)   ((vertex)->user)

#define VERTEX_from(vertex)   ((vertex)->from)

#define VERTEX_to(vertex)   ((vertex)->to)

#define VERTEX_fcnt(vertex)   ((vertex)->fcnt)

#define VERTEX_tcnt(vertex)   ((vertex)->tcnt)

#define VERTEX_level(vertex)   ((vertex)->level)

#define FALSE   0

#define TRUE   1

#define EDGE_user(edge)   ((edge)->user)

#define EDGE_from(edge)   ((edge)->from)

#define EDGE_to(edge)   ((edge)->to)

#define EDGE_nfrom(edge)   ((edge)->nfrom)

#define EDGE_nto(edge)   ((edge)->nto)

#define EDGE_etype(edge)   ((edge)->etype)

#define EDGE_RECURSIVE   1

#define Set_EDGE_recursive(edge)   (EDGE_etype(edge) |= EDGE_RECURSIVE)

#define EDGE_recursive(edge)   (EDGE_etype(edge) & EDGE_RECURSIVE)

#define GRAPH_vcnt(g)   ((g)->vcnt)

#define GRAPH_vmax(g)   ((g)->vmax)

#define GRAPH_vfree(g)   ((g)->vfree)

#define GRAPH_ecnt(g)   ((g)->ecnt)

#define GRAPH_emax(g)   ((g)->emax)

#define GRAPH_efree(g)   ((g)->efree)

#define GRAPH_root(g)   ((g)->root)

#define GRAPH_m(g)   ((g)->m)

#define GRAPH_v(g)   ((g)->v)

#define GRAPH_v_i(g, index)   ((g)->v[index])

#define GRAPH_e(g)   ((g)->e)

#define GRAPH_e_i(g, index)   ((g)->e[index])

#define FOR_EACH_VERTEX(g, v)

#define DFN_v_list(d)   ((d)->v_list)

#define DFN_v_list_i(d, i)   ((d)->v_list[i])

#define DFN_first(d)   ((d)->first)

#define DFN_end(d)   ((d)->end)

#define V_ITER_g(vi)   ((vi)->g)

#define V_ITER_c_v(vi)   ((vi)->c_v)

#define V_ITER_from_e(vi)   ((vi)->from_e)

#define V_ITER_to_e(vi)   ((vi)->to_e)

#define V_ITER_fcnt(vi)   ((vi)->fcnt)

#define V_ITER_nfrom(vi)   ((vi)->nfrom)

#define V_ITER_tcnt(vi)   ((vi)->tcnt)

#define V_ITER_nto(vi)   ((vi)->nto)

#define V_ITER_c_e(vi)   ((vi)->c_e)

#define V_ITER_m(vi)   ((vi)->m)

#define MEM_POOL_Alloc(m, s)   calloc(m, s)

#define MEM_POOL_Realloc(m, ob, os, ns)   realloc(m, ns)

#define MEM_POOL_FREE(m, s)

Typedefs

typedef int EINDEX

typedef int VINDEX

typedef struct vertex VERTEX

typedef int ETYPEX

typedef int BOOL

typedef char MEM_POOL

typedef struct edge EDGE

typedef struct graph GRAPH

typedef struct dfn DFN

typedef struct v_iter V_ITER

Functions/Subroutines

void Print_DFN (DFN *)

DFN * Depth_First_Ordering (GRAPH *, MEM_POOL *)

void Free_DFN (DFN *, MEM_POOL *)

GRAPH * build_graph_u (VINDEX, EINDEX, MEM_POOL *)

GRAPH * build_graph (MEM_POOL *)

VINDEX add_vertex (GRAPH *, void *)

EINDEX add_edge (GRAPH *, VINDEX, VINDEX, void *)

BOOL is_vertex (GRAPH *, VINDEX)

BOOL is_edge (GRAPH *, EINDEX)

void delete_edge (GRAPH *, EINDEX)

void * delete_vertex (GRAPH *, VINDEX)

void * get_vertex (GRAPH *, VINDEX)

void * get_edge (GRAPH *, VINDEX, VINDEX)

void * get_edge_u (GRAPH *, EINDEX)

void set_edge_u (GRAPH *, EINDEX, void *)

int num_preds (GRAPH *, VINDEX)

int num_succs (GRAPH *, VINDEX)

int edge_count (GRAPH *, VINDEX from, VINDEX to)

VINDEX next_vertex (GRAPH *g, VINDEX vertex)

V_ITER * create_vertex_iter (GRAPH *, VINDEX, MEM_POOL *)

VINDEX first_v_preds (V_ITER *)

VINDEX next_v_preds (V_ITER *)

VINDEX first_v_succs (V_ITER *)

VINDEX next_v_succs (V_ITER *)

void set_vertex_level (GRAPH *, VINDEX r, int level)

int get_vertex_level (GRAPH *, VINDEX r)

Define Documentation

#define DFN_end ( d ) ((d)->end)

Definition at line 231 of file ir_graph.h.

#define DFN_first ( d ) ((d)->first)

Definition at line 230 of file ir_graph.h.

#define DFN_v_list ( d ) ((d)->v_list)

Definition at line 228 of file ir_graph.h.

#define DFN_v_list_i	(	d,
		i		)	((d)->v_list[i])

Definition at line 229 of file ir_graph.h.

#define EDGE_etype ( edge ) ((edge)->etype)

Definition at line 152 of file ir_graph.h.

#define EDGE_from ( edge ) ((edge)->from)

Definition at line 148 of file ir_graph.h.

#define EDGE_nfrom ( edge ) ((edge)->nfrom)

Definition at line 150 of file ir_graph.h.

#define EDGE_nto ( edge ) ((edge)->nto)

Definition at line 151 of file ir_graph.h.

#define EDGE_recursive ( edge ) (EDGE_etype(edge) & EDGE_RECURSIVE)

Definition at line 157 of file ir_graph.h.

#define EDGE_RECURSIVE 1

Definition at line 155 of file ir_graph.h.

#define EDGE_to ( edge ) ((edge)->to)

Definition at line 149 of file ir_graph.h.

#define EDGE_user ( edge ) ((edge)->user)

Definition at line 147 of file ir_graph.h.

#define FALSE 0

Definition at line 132 of file ir_graph.h.

#define FOR_EACH_VERTEX	(	g,
		v		)

Value:

for ( v = 0; v < GRAPH_vmax(g); v++ ) \
    if ( VERTEX_fcnt (&GRAPH_v_i(g,v)) != INVALID_VINDEX )

Definition at line 204 of file ir_graph.h.

#define GRAPH_e ( g ) ((g)->e)

Definition at line 200 of file ir_graph.h.

#define GRAPH_e_i	(	g,
		index		)	((g)->e[index])

Definition at line 201 of file ir_graph.h.

#define GRAPH_ecnt ( g ) ((g)->ecnt)

Definition at line 193 of file ir_graph.h.

#define GRAPH_efree ( g ) ((g)->efree)

Definition at line 195 of file ir_graph.h.

#define GRAPH_emax ( g ) ((g)->emax)

Definition at line 194 of file ir_graph.h.

#define GRAPH_m ( g ) ((g)->m)

Definition at line 197 of file ir_graph.h.

#define GRAPH_root ( g ) ((g)->root)

Definition at line 196 of file ir_graph.h.

#define GRAPH_v ( g ) ((g)->v)

Definition at line 198 of file ir_graph.h.

#define GRAPH_v_i	(	g,
		index		)	((g)->v[index])

Definition at line 199 of file ir_graph.h.

#define GRAPH_vcnt ( g ) ((g)->vcnt)

Definition at line 190 of file ir_graph.h.

#define GRAPH_vfree ( g ) ((g)->vfree)

Definition at line 192 of file ir_graph.h.

#define GRAPH_vmax ( g ) ((g)->vmax)

Definition at line 191 of file ir_graph.h.

#define INVALID_EINDEX -1

Definition at line 84 of file ir_graph.h.

Referenced by add_vertex(), delete_vertex(), Depth_First_Ordering(), edge_count(), first_v_preds(), first_v_succs(), get_edge(), and grow_edge().

#define INVALID_VINDEX -1

Definition at line 85 of file ir_graph.h.

Referenced by build_call_graph(), build_graph(), build_graph_u(), delete_edge(), Depth_First_Ordering(), first_v_preds(), first_v_succs(), grow_vertex(), is_edge(), is_vertex(), next_v_preds(), next_v_succs(), next_vertex(), Print_Pred(), and Search().

#define MEM_POOL_Alloc	(	m,
		s		)	calloc(m, s)

Definition at line 276 of file ir_graph.h.

#define MEM_POOL_FREE	(	m,
		s		)

Definition at line 278 of file ir_graph.h.

Referenced by Cleanup_Archive_Handle(), DFBASE::Connect_graph(), Copy_Non_MP_Tree_Rec(), mempool_allocator< bb * >::deallocate(), Delete_DEPV_ARRAY(), Depth_First_Ordering(), DEPV_Free(), FBV::FBV_free(), first_v_preds(), first_v_succs(), DYN_ARRAY< T >::Free_array(), Free_DFN(), IPA_LNO_Write_Summary(), IPA_WN_MAP_Delete(), MEM_POOL_Realloc_P(), next_v_preds(), next_v_succs(), operator delete(), SEGMENTED_ARRAY< T, block_size >::Pop_Map(), RELATED_SEGMENTED_ARRAY< T, block_size >::Pop_Map(), process_whirl(), TN_CORRESPOND_Free(), VHO_Lower_Switch(), VHO_Switch_Generate_Compgoto(), WN_FreeStack(), WN_MAP_TAB_Delete(), AUX_IPA_EDGE< EDGE >::~AUX_IPA_EDGE(), AUX_IPA_NODE< NODE >::~AUX_IPA_NODE(), DF_PRINT::~DF_PRINT(), IPAA_DF_SOLVER::~IPAA_DF_SOLVER(), RELATED_SEGMENTED_ARRAY< T, block_size >::~RELATED_SEGMENTED_ARRAY(), and SEGMENTED_ARRAY< VN_EXPR, VN_BUFFER_CHUNKSIZE >::~SEGMENTED_ARRAY().

#define MEM_POOL_Realloc	(	m,
		ob,
		os,
		ns	)	realloc(m, ns)

Definition at line 277 of file ir_graph.h.

#define Set_EDGE_recursive ( edge ) (EDGE_etype(edge) |= EDGE_RECURSIVE)

Definition at line 156 of file ir_graph.h.

#define TRUE 1

Definition at line 133 of file ir_graph.h.

#define V_ITER_c_e ( vi ) ((vi)->c_e)

Definition at line 273 of file ir_graph.h.

Referenced by first_v_preds(), first_v_succs(), next_v_preds(), next_v_succs(), Print_Pred(), and Search().

#define V_ITER_c_v ( vi ) ((vi)->c_v)

Definition at line 266 of file ir_graph.h.

Referenced by create_vertex_iter().

#define V_ITER_fcnt ( vi ) ((vi)->fcnt)

Definition at line 269 of file ir_graph.h.

Referenced by create_vertex_iter().

#define V_ITER_from_e ( vi ) ((vi)->from_e)

Definition at line 267 of file ir_graph.h.

Referenced by create_vertex_iter(), and first_v_succs().

#define V_ITER_g ( vi ) ((vi)->g)

Definition at line 265 of file ir_graph.h.

Referenced by create_vertex_iter(), first_v_preds(), first_v_succs(), next_v_preds(), and next_v_succs().

#define V_ITER_m ( vi ) ((vi)->m)

Definition at line 274 of file ir_graph.h.

Referenced by create_vertex_iter(), first_v_preds(), first_v_succs(), next_v_preds(), and next_v_succs().

#define V_ITER_nfrom ( vi ) ((vi)->nfrom)

Definition at line 270 of file ir_graph.h.

Referenced by create_vertex_iter(), first_v_succs(), and next_v_succs().

#define V_ITER_nto ( vi ) ((vi)->nto)

Definition at line 272 of file ir_graph.h.

Referenced by create_vertex_iter(), first_v_preds(), and next_v_preds().

#define V_ITER_tcnt ( vi ) ((vi)->tcnt)

Definition at line 271 of file ir_graph.h.

Referenced by create_vertex_iter().

#define V_ITER_to_e ( vi ) ((vi)->to_e)

Definition at line 268 of file ir_graph.h.

Referenced by create_vertex_iter(), and first_v_preds().

#define VERTEX_fcnt ( vertex ) ((vertex)->fcnt)

Definition at line 112 of file ir_graph.h.

Referenced by add_edge(), add_vertex(), build_graph_u(), create_vertex_iter(), delete_edge(), delete_vertex(), grow_vertex(), is_vertex(), and num_succs().

#define VERTEX_from ( vertex ) ((vertex)->from)

Definition at line 110 of file ir_graph.h.

Referenced by add_edge(), add_vertex(), build_graph_u(), create_vertex_iter(), delete_edge(), delete_vertex(), edge_count(), get_edge(), and grow_vertex().

#define VERTEX_level ( vertex ) ((vertex)->level)

Definition at line 114 of file ir_graph.h.

Referenced by add_vertex(), get_vertex_level(), and set_vertex_level().

#define VERTEX_tcnt ( vertex ) ((vertex)->tcnt)

Definition at line 113 of file ir_graph.h.

Referenced by add_edge(), add_vertex(), create_vertex_iter(), delete_edge(), and num_preds().

#define VERTEX_to ( vertex ) ((vertex)->to)

Definition at line 111 of file ir_graph.h.

Referenced by add_edge(), add_vertex(), create_vertex_iter(), delete_edge(), and delete_vertex().

#define VERTEX_user ( vertex ) ((vertex)->user)

Definition at line 109 of file ir_graph.h.

Referenced by add_vertex(), delete_vertex(), and get_vertex().

Typedef Documentation

typedef int BOOL

Definition at line 130 of file ir_graph.h.

typedef struct dfn DFN

typedef struct edge EDGE

typedef int EINDEX

Definition at line 82 of file ir_graph.h.

typedef int ETYPEX

Definition at line 129 of file ir_graph.h.

typedef struct graph GRAPH

typedef char MEM_POOL

Definition at line 135 of file ir_graph.h.

typedef struct v_iter V_ITER

typedef struct vertex VERTEX

typedef int VINDEX

Definition at line 83 of file ir_graph.h.

Function Documentation

EINDEX add_edge	(	GRAPH *	,
		VINDEX	,
		VINDEX	,
		void *
	)

Definition at line 245 of file ir_graph_util.c.

VINDEX add_vertex	(	GRAPH *	,
		void *
	)

Definition at line 207 of file ir_graph_util.c.

Referenced by build_call_graph().

GRAPH* build_graph ( MEM_POOL * )

Definition at line 123 of file ir_graph_util.c.

GRAPH* build_graph_u	(	VINDEX	,
		EINDEX	,
		MEM_POOL *
	)

Definition at line 57 of file ir_graph_util.c.

Referenced by build_call_graph().

V_ITER* create_vertex_iter	(	GRAPH *	,
		VINDEX	,
		MEM_POOL *
	)

Definition at line 542 of file ir_graph_util.c.

Referenced by Print_Pred(), and Search().

void delete_edge	(	GRAPH *	,
		EINDEX
	)

Definition at line 328 of file ir_graph_util.c.

Referenced by delete_vertex().

void* delete_vertex	(	GRAPH *	,
		VINDEX
	)

Definition at line 402 of file ir_graph_util.c.

DFN* Depth_First_Ordering	(	GRAPH *	,
		MEM_POOL *
	)

Definition at line 514 of file ip_graph.cxx.

int edge_count	(	GRAPH *	,
		VINDEX	from,
		VINDEX	to
	)

Definition at line 502 of file ir_graph_util.c.

Referenced by Depth_First_Ordering(), and try_forward_edges().

VINDEX first_v_preds ( V_ITER * )

Definition at line 565 of file ir_graph_util.c.

Referenced by Print_Pred().

VINDEX first_v_succs ( V_ITER * )

Definition at line 622 of file ir_graph_util.c.

Referenced by Search().

void Free_DFN	(	DFN *	,
		MEM_POOL *
	)

Definition at line 598 of file ip_graph.cxx.

void* get_edge	(	GRAPH *	,
		VINDEX	,
		VINDEX
	)

Definition at line 480 of file ir_graph_util.c.

void* get_edge_u	(	GRAPH *	,
		EINDEX
	)

Definition at line 524 of file ir_graph_util.c.

Referenced by Print_Pred(), and Search().

void* get_vertex	(	GRAPH *	,
		VINDEX
	)

Definition at line 450 of file ir_graph_util.c.

int get_vertex_level	(	GRAPH *	,
		VINDEX	r
	)

Definition at line 674 of file ir_graph_util.c.

Referenced by Print_DFN().

BOOL is_edge	(	GRAPH *	,
		EINDEX
	)

Definition at line 441 of file ir_graph_util.c.

Referenced by delete_edge(), and get_edge_u().

BOOL is_vertex	(	GRAPH *	,
		VINDEX
	)

Definition at line 303 of file ir_graph_util.c.

Referenced by add_edge(), delete_vertex(), edge_count(), get_edge(), get_vertex(), next_vertex(), num_preds(), and num_succs().

VINDEX next_v_preds ( V_ITER * )

Definition at line 593 of file ir_graph_util.c.

Referenced by Print_Pred().

VINDEX next_v_succs ( V_ITER * )

Definition at line 647 of file ir_graph_util.c.

Referenced by Search().

VINDEX next_vertex	(	GRAPH *	g,
		VINDEX	vertex
	)

Definition at line 312 of file ir_graph_util.c.

Referenced by accumulate_line_counts().

int num_preds	(	GRAPH *	,
		VINDEX
	)

Definition at line 460 of file ir_graph_util.c.

int num_succs	(	GRAPH *	,
		VINDEX
	)

Definition at line 470 of file ir_graph_util.c.

Referenced by GCM_Fill_Branch_Delay_Slots().

void Print_DFN ( DFN * )

void set_edge_u	(	GRAPH *	,
		EINDEX	,
		void *
	)

Definition at line 534 of file ir_graph_util.c.

Referenced by build_call_graph().

void set_vertex_level	(	GRAPH *	,
		VINDEX	r,
		int	level
	)

Definition at line 683 of file ir_graph_util.c.

Referenced by Search().


Data Types
type	vertex
type	edge
type	graph
type	dfn
type	v_iter
Defines
#define	INVALID_EINDEX -1
#define	INVALID_VINDEX -1
#define	VERTEX_user(vertex) ((vertex)->user)
#define	VERTEX_from(vertex) ((vertex)->from)
#define	VERTEX_to(vertex) ((vertex)->to)
#define	VERTEX_fcnt(vertex) ((vertex)->fcnt)
#define	VERTEX_tcnt(vertex) ((vertex)->tcnt)
#define	VERTEX_level(vertex) ((vertex)->level)
#define	FALSE 0
#define	TRUE 1
#define	EDGE_user(edge) ((edge)->user)
#define	EDGE_from(edge) ((edge)->from)
#define	EDGE_to(edge) ((edge)->to)
#define	EDGE_nfrom(edge) ((edge)->nfrom)
#define	EDGE_nto(edge) ((edge)->nto)
#define	EDGE_etype(edge) ((edge)->etype)
#define	EDGE_RECURSIVE 1
#define	Set_EDGE_recursive(edge) (EDGE_etype(edge) \|= EDGE_RECURSIVE)
#define	EDGE_recursive(edge) (EDGE_etype(edge) & EDGE_RECURSIVE)
#define	GRAPH_vcnt(g) ((g)->vcnt)
#define	GRAPH_vmax(g) ((g)->vmax)
#define	GRAPH_vfree(g) ((g)->vfree)
#define	GRAPH_ecnt(g) ((g)->ecnt)
#define	GRAPH_emax(g) ((g)->emax)
#define	GRAPH_efree(g) ((g)->efree)
#define	GRAPH_root(g) ((g)->root)
#define	GRAPH_m(g) ((g)->m)
#define	GRAPH_v(g) ((g)->v)
#define	GRAPH_v_i(g, index) ((g)->v[index])
#define	GRAPH_e(g) ((g)->e)
#define	GRAPH_e_i(g, index) ((g)->e[index])
#define	FOR_EACH_VERTEX(g, v)
#define	DFN_v_list(d) ((d)->v_list)
#define	DFN_v_list_i(d, i) ((d)->v_list[i])
#define	DFN_first(d) ((d)->first)
#define	DFN_end(d) ((d)->end)
#define	V_ITER_g(vi) ((vi)->g)
#define	V_ITER_c_v(vi) ((vi)->c_v)
#define	V_ITER_from_e(vi) ((vi)->from_e)
#define	V_ITER_to_e(vi) ((vi)->to_e)
#define	V_ITER_fcnt(vi) ((vi)->fcnt)
#define	V_ITER_nfrom(vi) ((vi)->nfrom)
#define	V_ITER_tcnt(vi) ((vi)->tcnt)
#define	V_ITER_nto(vi) ((vi)->nto)
#define	V_ITER_c_e(vi) ((vi)->c_e)
#define	V_ITER_m(vi) ((vi)->m)
#define	MEM_POOL_Alloc(m, s) calloc(m, s)
#define	MEM_POOL_Realloc(m, ob, os, ns) realloc(m, ns)
#define	MEM_POOL_FREE(m, s)
Typedefs
typedef int	EINDEX
typedef int	VINDEX
typedef struct vertex	VERTEX
typedef int	ETYPEX
typedef int	BOOL
typedef char	MEM_POOL
typedef struct edge	EDGE
typedef struct graph	GRAPH
typedef struct dfn	DFN
typedef struct v_iter	V_ITER
Functions/Subroutines
void	Print_DFN (DFN *)
DFN *	Depth_First_Ordering (GRAPH , MEM_POOL )
void	Free_DFN (DFN , MEM_POOL )
GRAPH *	build_graph_u (VINDEX, EINDEX, MEM_POOL *)
GRAPH *	build_graph (MEM_POOL *)
VINDEX	add_vertex (GRAPH , void )
EINDEX	add_edge (GRAPH , VINDEX, VINDEX, void )
BOOL	is_vertex (GRAPH *, VINDEX)
BOOL	is_edge (GRAPH *, EINDEX)
void	delete_edge (GRAPH *, EINDEX)
void *	delete_vertex (GRAPH *, VINDEX)
void *	get_vertex (GRAPH *, VINDEX)
void *	get_edge (GRAPH *, VINDEX, VINDEX)
void *	get_edge_u (GRAPH *, EINDEX)
void	set_edge_u (GRAPH , EINDEX, void )
int	num_preds (GRAPH *, VINDEX)
int	num_succs (GRAPH *, VINDEX)
int	edge_count (GRAPH *, VINDEX from, VINDEX to)
VINDEX	next_vertex (GRAPH *g, VINDEX vertex)
V_ITER *	create_vertex_iter (GRAPH , VINDEX, MEM_POOL )
VINDEX	first_v_preds (V_ITER *)
VINDEX	next_v_preds (V_ITER *)
VINDEX	first_v_succs (V_ITER *)
VINDEX	next_v_succs (V_ITER *)
void	set_vertex_level (GRAPH *, VINDEX r, int level)
int	get_vertex_level (GRAPH *, VINDEX r)