osprey-gcc/gcc/ddg.c File Reference

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "toplev.h"
#include "rtl.h"
#include "tm_p.h"
#include "hard-reg-set.h"
#include "regs.h"
#include "function.h"
#include "flags.h"
#include "insn-config.h"
#include "insn-attr.h"
#include "except.h"
#include "recog.h"
#include "sched-int.h"
#include "target.h"
#include "cfglayout.h"
#include "cfgloop.h"
#include "sbitmap.h"
#include "expr.h"
#include "bitmap.h"
#include "df.h"
#include "ddg.h"

Include dependency graph for ddg.c:

Go to the source code of this file.

Enumerations

enum edge_flag { NOT_IN_SCC = 0, IN_SCC, NOT_IN_SCC = 0, IN_SCC }

Functions/Subroutines

static void add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr)

static void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr)

static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr)

static void create_ddg_dependence (ddg_ptr, ddg_node_ptr, ddg_node_ptr, rtx)

static void create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr, dep_type, dep_data_type, int)

static ddg_edge_ptr create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type, dep_data_type, int, int)

static void add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr)

static int mark_mem_use (rtx *x, void *data ATTRIBUTE_UNUSED)

static void mark_mem_use_1 (rtx *x, void *data)

static bool mem_read_insn_p (rtx insn)

static void mark_mem_store (rtx loc, rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)

static bool mem_write_insn_p (rtx insn)

static bool rtx_mem_access_p (rtx x)

static bool mem_access_insn_p (rtx insn)

static void add_deps_for_def (ddg_ptr g, struct df *df, struct ref *rd)

static void add_deps_for_use (ddg_ptr g, struct df *df, struct ref *use)

static void build_inter_loop_deps (ddg_ptr g, struct df *df)

static void add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)

static void build_intra_loop_deps (ddg_ptr g)

ddg_ptr create_ddg (basic_block bb, struct df *df, int closing_branch_deps)

void free_ddg (ddg_ptr g)

void print_ddg_edge (FILE *dump_file, ddg_edge_ptr e)

void print_ddg (FILE *dump_file, ddg_ptr g)

void vcg_print_ddg (FILE *dump_file, ddg_ptr g)

static void set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)

static ddg_scc_ptr create_scc (ddg_ptr g, sbitmap nodes)

static void free_scc (ddg_scc_ptr scc)

ddg_node_ptr get_node_of_insn (ddg_ptr g, rtx insn)

void find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)

void find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)

static int compare_sccs (const void *s1, const void *s2)

static void order_sccs (ddg_all_sccs_ptr g)

ddg_all_sccs_ptr create_ddg_all_sccs (ddg_ptr g)

void free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)

int find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)

static int update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)

int longest_simple_path (struct ddg *g, int src, int dest, sbitmap nodes)

Variables

static bool mem_ref_p

Enumeration Type Documentation

enum edge_flag

Enumerator:

NOT_IN_SCC
IN_SCC
NOT_IN_SCC
IN_SCC

Definition at line 50 of file ddg.c.

Function Documentation

static void add_backarc_to_ddg	(	ddg_ptr	g,
		ddg_edge_ptr	e
	)			`[static]`

Definition at line 738 of file ddg.c.

References add_edge_to_ddg(), ddg::backarcs, ddg::num_backarcs, size, and xrealloc().

Referenced by create_ddg_dep_no_link(), and create_ddg_dependence().

static void add_backarc_to_scc	(	ddg_scc_ptr	scc,
		ddg_edge_ptr	e
	)			`[static]`

Definition at line 749 of file ddg.c.

References ddg_scc::backarcs, ddg_scc::num_backarcs, size, and xrealloc().

Referenced by create_scc().

static void add_deps_for_def	(	ddg_ptr	g,
		struct df *	df,
		struct ref *	rd
	)			`[static]`

Definition at line 225 of file ddg.c.

References ddg::bb, bitmap_bit_p(), create_ddg_dep_no_link(), ddg_node::cuid, DF_BB_INFO, df_bb_regno_first_def_find(), DF_REF_CHAIN, DF_REF_INSN, DF_REF_REGNO, df_reg_used(), gcc_assert, get_node_of_insn(), i, ref::id, ref::insn, ddg_node::insn, df_link::next, ddg::nodes, NULL, OUTPUT_DEP, df_link::ref, ref::reg, REG_DEP, bb_info::ru_gen, and TRUE_DEP.

Referenced by build_inter_loop_deps().

static void add_deps_for_use	(	ddg_ptr	g,
		struct df *	df,
		struct ref *	use
	)			`[static]`

Definition at line 281 of file ddg.c.

References ANTI_DEP, ddg::bb, bitmap_bit_p(), create_ddg_dep_no_link(), ddg_node::cuid, DF_BB_INFO, df_bb_regno_first_def_find(), df_find_def(), DF_REF_REGNO, gcc_assert, get_node_of_insn(), i, ref::id, ref::insn, ddg_node::insn, ddg::nodes, bb_info::rd_gen, ref::reg, and REG_DEP.

Referenced by build_inter_loop_deps().

static void add_edge_to_ddg	(	ddg_ptr g	ATTRIBUTE_UNUSED,
		ddg_edge_ptr	e
	)			`[static]`

Definition at line 642 of file ddg.c.

References ddg_node::cuid, ddg_edge::dest, dest, gcc_assert, ddg_node::in, ddg_edge::next_in, ddg_edge::next_out, ddg_node::out, ddg_node::predecessors, SET_BIT, src, ddg_edge::src, and ddg_node::successors.

Referenced by add_backarc_to_ddg(), create_ddg_dep_no_link(), and create_ddg_dependence().

static void add_inter_loop_mem_dep	(	ddg_ptr	g,
		ddg_node_ptr	from,
		ddg_node_ptr	to
	)			`[static]`

Definition at line 345 of file ddg.c.

References ANTI_DEP, create_ddg_dep_no_link(), ddg_node::cuid, ddg_node::insn, MEM_DEP, mem_read_insn_p(), mem_write_insn_p(), OUTPUT_DEP, and TRUE_DEP.

Referenced by build_intra_loop_deps().

static void add_scc_to_ddg	(	ddg_all_sccs_ptr	g,
		ddg_scc_ptr	scc
	)			`[static]`

Definition at line 759 of file ddg.c.

References ddg_all_sccs::num_sccs, ddg_all_sccs::sccs, size, and xrealloc().

Referenced by create_ddg_all_sccs().

static void build_inter_loop_deps	(	ddg_ptr	g,
		struct df *	df
	)			`[static]`

Definition at line 313 of file ddg.c.

References add_deps_for_def(), add_deps_for_use(), ddg::bb, BLOCK_FOR_INSN, df::defs, DF_BB_INFO, EXECUTE_IF_SET_IN_BITMAP, ref::insn, rd, bb_info::rd_gen, bb_info::ru_kill, and df::uses.

Referenced by create_ddg().

static void build_intra_loop_deps ( ddg_ptr g ) [static]

Definition at line 370 of file ddg.c.

References add_forward_dependence(), add_inter_loop_mem_dep(), ddg::bb, create_ddg_dependence(), finish_deps_global(), free_deps(), get_block_head_tail(), get_node_of_insn(), i, basic_block_def::index, init_deps(), init_deps_global(), ddg_node::insn, INSN_DEPEND, INSN_P, LOG_LINKS, mem_access_insn_p(), ddg::nodes, ddg::num_nodes, REG_NOTE_KIND, sched_analyze(), ddg_node::successors, tail, TEST_BIT, and XEXP.

Referenced by create_ddg().

static int compare_sccs	(	const void *	s1,
		const void *	s2
	)			`[static]`

Definition at line 819 of file ddg.c.

Referenced by order_sccs().

ddg_ptr create_ddg	(	basic_block	bb,
		struct df *	df,
		int	closing_branch_deps
	)

Definition at line 435 of file ddg.c.

ddg_all_sccs_ptr create_ddg_all_sccs ( ddg_ptr g )

Definition at line 838 of file ddg.c.

static void create_ddg_dep_no_link	(	ddg_ptr	g,
		ddg_node_ptr	from,
		ddg_node_ptr	to,
		dep_type	d_t,
		dep_data_type	d_dt,
		int	distance
	)			`[static]`

Definition at line 198 of file ddg.c.

References add_backarc_to_ddg(), add_edge_to_ddg(), alloc_INSN_LIST(), ANTI_DEP, create_ddg_edge(), free_INSN_LIST_node(), ddg_node::insn, insn_cost(), NULL_RTX, OUTPUT_DEP, PUT_REG_NOTE_KIND, REG_DEP_ANTI, and REG_DEP_OUTPUT.

Referenced by add_deps_for_def(), add_deps_for_use(), and add_inter_loop_mem_dep().

static void create_ddg_dependence	(	ddg_ptr	g,
		ddg_node_ptr	src_node,
		ddg_node_ptr	dest_node,
		rtx	link
	)			`[static]`

Definition at line 150 of file ddg.c.

References add_backarc_to_ddg(), add_edge_to_ddg(), ANTI_DEP, create_ddg_edge(), ddg_node::cuid, free(), gcc_assert, ddg_node::insn, insn_cost(), mem_access_insn_p(), MEM_DEP, OUTPUT_DEP, REG_DEP, REG_DEP_ANTI, REG_DEP_OUTPUT, REG_NOTE_KIND, and TRUE_DEP.

Referenced by build_intra_loop_deps().

static ddg_edge_ptr create_ddg_edge	(	ddg_node_ptr	src,
		ddg_node_ptr	dest,
		dep_type	t,
		dep_data_type	dt,
		int	l,
		int	d
	)			`[static]`

Definition at line 624 of file ddg.c.

References ddg_edge::aux, ddg_edge::data_type, ddg_edge::dest, ddg_edge::distance, ddg_edge::info, ddg_edge::latency, ddg_edge::next_in, ddg_edge::next_out, NULL, ddg_edge::src, ddg_edge::type, and xmalloc().

Referenced by create_ddg_dep_no_link(), and create_ddg_dependence().

static ddg_scc_ptr create_scc	(	ddg_ptr	g,
		sbitmap	nodes
	)			`[static]`

Definition at line 692 of file ddg.c.

References add_backarc_to_scc(), ddg_edge::aux, ddg_scc::backarcs, ddg_edge::count, ddg_node::cuid, ddg_edge::dest, ddg_edge::distance, EXECUTE_IF_SET_IN_SBITMAP, if(), IN_SCC, n, ddg_edge::next_out, ddg::nodes, ddg_scc::nodes, NULL, ddg_scc::num_backarcs, ddg::num_nodes, ddg_node::out, sbitmap_alloc(), sbitmap_copy(), scc, TEST_BIT, and xmalloc().

Referenced by create_ddg_all_sccs().

int find_nodes_on_paths	(	sbitmap	result,
		ddg_ptr	g,
		sbitmap	from,
		sbitmap	to
	)

Definition at line 901 of file ddg.c.

Referenced by create_ddg_all_sccs().

void find_predecessors	(	sbitmap	preds,
		ddg_ptr	g,
		sbitmap	ops
	)

Definition at line 801 of file ddg.c.

void find_successors	(	sbitmap	succ,
		ddg_ptr	g,
		sbitmap	ops
	)

Definition at line 783 of file ddg.c.

void free_ddg ( ddg_ptr g )

Definition at line 518 of file ddg.c.

void free_ddg_all_sccs ( ddg_all_sccs_ptr all_sccs )

Definition at line 883 of file ddg.c.

static void free_scc ( ddg_scc_ptr scc ) [static]

Definition at line 724 of file ddg.c.

References ddg_scc::backarcs, free(), ddg_scc::nodes, ddg_scc::num_backarcs, and sbitmap_free.

Referenced by free_ddg_all_sccs().

ddg_node_ptr get_node_of_insn	(	ddg_ptr	g,
		rtx	insn
	)

Definition at line 769 of file ddg.c.

Referenced by add_deps_for_def(), add_deps_for_use(), and build_intra_loop_deps().

int longest_simple_path	(	struct ddg *	g,
		int	src,
		int	dest,
		sbitmap	nodes
	)

Definition at line 1009 of file ddg.c.

References ddg_node::aux, change, ddg_node::count, EXECUTE_IF_SET_IN_SBITMAP, i, ddg::nodes, ddg::num_nodes, result, sbitmap_alloc(), sbitmap_copy(), sbitmap_free, sbitmap_zero(), SET_BIT, tmp, and update_dist_to_successors().

Referenced by set_recurrence_length().

static void mark_mem_store	(	rtx	loc,
		rtx setter	ATTRIBUTE_UNUSED,
		void *data	ATTRIBUTE_UNUSED
	)			`[static]`

Definition at line 92 of file ddg.c.

References MEM_P, and mem_ref_p.

Referenced by mem_write_insn_p().

static int mark_mem_use	(	rtx *	x,
		void *data	ATTRIBUTE_UNUSED
	)			`[static]`

Definition at line 68 of file ddg.c.

References MEM_P, and mem_ref_p.

Referenced by mark_mem_use_1().

static void mark_mem_use_1	(	rtx *	x,
		void *	data
	)			`[static]`

Definition at line 77 of file ddg.c.

References for_each_rtx(), and mark_mem_use().

Referenced by mem_read_insn_p().

static bool mem_access_insn_p ( rtx insn ) [static]

Definition at line 142 of file ddg.c.

References PATTERN, and rtx_mem_access_p().

Referenced by build_intra_loop_deps(), and create_ddg_dependence().

static bool mem_read_insn_p ( rtx insn ) [static]

Definition at line 84 of file ddg.c.

References mark_mem_use_1(), mem_ref_p, note_uses(), NULL, and PATTERN.

Referenced by add_inter_loop_mem_dep(), and create_ddg().

static bool mem_write_insn_p ( rtx insn ) [static]

Definition at line 100 of file ddg.c.

References mark_mem_store(), mem_ref_p, note_stores(), NULL, and PATTERN.

Referenced by add_inter_loop_mem_dep(), and create_ddg().

static void order_sccs ( ddg_all_sccs_ptr g ) [static]

Definition at line 829 of file ddg.c.

References compare_sccs(), ddg_all_sccs::num_sccs, qsort(), and ddg_all_sccs::sccs.

Referenced by create_ddg_all_sccs().

void print_ddg	(	FILE *	dump_file,
		ddg_ptr	g
	)

Definition at line 567 of file ddg.c.

void print_ddg_edge	(	FILE *	dump_file,
		ddg_edge_ptr	e
	)

Definition at line 546 of file ddg.c.

Referenced by print_ddg().

static bool rtx_mem_access_p ( rtx x ) [static]

Definition at line 109 of file ddg.c.

References GET_CODE, GET_RTX_FORMAT, GET_RTX_LENGTH, i, MEM_P, XEXP, XVECEXP, and XVECLEN.

Referenced by mem_access_insn_p(), and rtx_mem_access_p().

static void set_recurrence_length	(	ddg_scc_ptr	scc,
		ddg_ptr	g
	)			`[static]`

Definition at line 664 of file ddg.c.

References ddg_scc::backarcs, ddg_node::cuid, ddg_edge::dest, dest, ddg_edge::distance, ddg_edge::latency, length, longest_simple_path(), MAX, ddg_scc::nodes, ddg_scc::num_backarcs, ddg_scc::recurrence_length, result, src, and ddg_edge::src.

Referenced by create_scc().

static int update_dist_to_successors	(	ddg_node_ptr	u_node,
		sbitmap	nodes,
		sbitmap	tmp
	)			`[static]`

Definition at line 983 of file ddg.c.

References ddg_node::aux, ddg_node::count, ddg_node::cuid, ddg_edge::dest, ddg_edge::distance, ddg_edge::latency, ddg_edge::next_out, ddg_node::out, result, SET_BIT, and TEST_BIT.

Referenced by longest_simple_path().

void vcg_print_ddg	(	FILE *	dump_file,
		ddg_ptr	g
	)

Definition at line 590 of file ddg.c.

Variable Documentation

bool mem_ref_p [static]

Definition at line 64 of file ddg.c.

Referenced by mark_mem_store(), mark_mem_use(), mem_read_insn_p(), and mem_write_insn_p().


Enumerations
enum	edge_flag { NOT_IN_SCC = 0, IN_SCC, NOT_IN_SCC = 0, IN_SCC }
Functions/Subroutines
static void	add_backarc_to_ddg (ddg_ptr, ddg_edge_ptr)
static void	add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr)
static void	add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_ptr)
static void	create_ddg_dependence (ddg_ptr, ddg_node_ptr, ddg_node_ptr, rtx)
static void	create_ddg_dep_no_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr, dep_type, dep_data_type, int)
static ddg_edge_ptr	create_ddg_edge (ddg_node_ptr, ddg_node_ptr, dep_type, dep_data_type, int, int)
static void	add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr)
static int	mark_mem_use (rtx x, void data ATTRIBUTE_UNUSED)
static void	mark_mem_use_1 (rtx x, void data)
static bool	mem_read_insn_p (rtx insn)
static void	mark_mem_store (rtx loc, rtx setter ATTRIBUTE_UNUSED, void *data ATTRIBUTE_UNUSED)
static bool	mem_write_insn_p (rtx insn)
static bool	rtx_mem_access_p (rtx x)
static bool	mem_access_insn_p (rtx insn)
static void	add_deps_for_def (ddg_ptr g, struct df df, struct ref rd)
static void	add_deps_for_use (ddg_ptr g, struct df df, struct ref use)
static void	build_inter_loop_deps (ddg_ptr g, struct df *df)
static void	add_inter_loop_mem_dep (ddg_ptr g, ddg_node_ptr from, ddg_node_ptr to)
static void	build_intra_loop_deps (ddg_ptr g)
ddg_ptr	create_ddg (basic_block bb, struct df *df, int closing_branch_deps)
void	free_ddg (ddg_ptr g)
void	print_ddg_edge (FILE *dump_file, ddg_edge_ptr e)
void	print_ddg (FILE *dump_file, ddg_ptr g)
void	vcg_print_ddg (FILE *dump_file, ddg_ptr g)
static void	set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
static ddg_scc_ptr	create_scc (ddg_ptr g, sbitmap nodes)
static void	free_scc (ddg_scc_ptr scc)
ddg_node_ptr	get_node_of_insn (ddg_ptr g, rtx insn)
void	find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
void	find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
static int	compare_sccs (const void s1, const void s2)
static void	order_sccs (ddg_all_sccs_ptr g)
ddg_all_sccs_ptr	create_ddg_all_sccs (ddg_ptr g)
void	free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
int	find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
static int	update_dist_to_successors (ddg_node_ptr u_node, sbitmap nodes, sbitmap tmp)
int	longest_simple_path (struct ddg *g, int src, int dest, sbitmap nodes)
Variables
static bool	mem_ref_p