Enumerations
enum	edge_flag { NOT_IN_SCC = 0, IN_SCC }

Functions
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_dep_from_intra_loop_link (ddg_ptr, ddg_node_ptr, ddg_node_ptr, dep_t)
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 ()
static void	mark_mem_use_1 ()
static bool	mem_read_insn_p ()
static void	mark_mem_store ()
static bool	mem_write_insn_p ()
static bool	rtx_mem_access_p ()
static bool	mem_access_insn_p ()
bool	autoinc_var_is_used_p ()
static bool	def_has_ccmode_p ()
static void	add_cross_iteration_register_deps ()
static void	build_inter_loop_deps ()
static int	walk_mems_2 ()
static int	walk_mems_1 ()
static int	insns_may_alias_p ()
static void	add_intra_loop_mem_dep ()
static void	add_inter_loop_mem_dep ()
static void	build_intra_loop_deps ()
ddg_ptr	create_ddg ()
void	free_ddg ()
void	print_ddg_edge ()
void	print_ddg ()
DEBUG_FUNCTION void	vcg_print_ddg ()
void	print_sccs ()
static void	add_edge_to_ddg ()
static void	set_recurrence_length ()
static ddg_scc_ptr	create_scc ()
static void	free_scc ()
static void	add_backarc_to_ddg ()
static void	add_backarc_to_scc ()
static void	add_scc_to_ddg ()
ddg_node_ptr	get_node_of_insn ()
void	find_successors ()
void	find_predecessors ()
static int	compare_sccs ()
static void	order_sccs ()
static void	check_sccs ()
ddg_all_sccs_ptr	create_ddg_all_sccs ()
void	free_ddg_all_sccs ()
int	find_nodes_on_paths ()
static int	update_dist_to_successors ()
int	longest_simple_path ()

Variables
static bool	mem_ref_p

Enumeration Type Documentation

enum edge_flag

@verbatim DDG - Data Dependence Graph implementation.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/.

A flag indicating that a ddg edge belongs to an SCC or not.

Enumerator:

NOT_IN_SCC
IN_SCC

Function Documentation

static void add_backarc_to_ddg	(	ddg_ptr	,
		ddg_edge_ptr
	)

static

Forward declarations.

Referenced by create_ddg_dep_no_link().

static void add_backarc_to_ddg ( )

static

Add a given edge known to be a backarc to the given DDG.

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

static void add_backarc_to_scc	(	ddg_scc_ptr	,
		ddg_edge_ptr
	)

static

Referenced by create_scc().

static void add_backarc_to_scc ( )

static

Add backarc to an SCC.

References ddg_scc::backarcs, and ddg_scc::num_backarcs.

static void add_cross_iteration_register_deps ( )

static

Given a downwards exposed register def LAST_DEF (which is the last
   definition of that register in the bb), add inter-loop true dependences
   to all its uses in the next iteration, an output dependence to the
   first def of the same register (possibly itself) in the next iteration
   and anti-dependences from its uses in the current iteration to the
   first definition in the next iteration.

References ANTI_DEP, autoinc_var_is_used_p(), ddg::bb, bitmap_bit_p(), create_ddg_dep_no_link(), ddg_node::cuid, def_has_ccmode_p(), df_bb_regno_first_def_find(), df_rd_bb_info::gen, get_node_of_insn(), ddg_node::insn, df_link::next, OUTPUT_DEP, df_link::ref, REG_DEP, and TRUE_DEP.

Referenced by build_inter_loop_deps().

static void add_edge_to_ddg	(	ddg_ptr	g,
		ddg_edge_ptr
	)

static

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

static void add_edge_to_ddg ( )

static

Add the given edge to the in/out linked lists of the DDG nodes.

References bitmap_set_bit(), ddg_node::cuid, ddg_edge::dest, ddg_node::in, ddg_edge::next_in, ddg_edge::next_out, ddg_node::out, ddg_node::predecessors, ddg_edge::src, and ddg_node::successors.

static void add_inter_loop_mem_dep ( )

static

Given two nodes, analyze their RTL insns and add inter-loop mem deps
   to ddg G.

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

Referenced by build_intra_loop_deps().

static void add_intra_loop_mem_dep ( )

static

Given two nodes, analyze their RTL insns and add intra-loop mem deps
   to ddg G.

References ANTI_DEP, create_ddg_dep_no_link(), ddg_node::cuid, ddg_node::insn, insns_may_alias_p(), 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	,
		ddg_scc_ptr
	)

static

Referenced by create_ddg_all_sccs().

static void add_scc_to_ddg ( )

static

Add the given SCC to the DDG.

References ddg_all_sccs::num_sccs, and ddg_all_sccs::sccs.

bool autoinc_var_is_used_p ( )

Return true if DEF_INSN contains address being auto-inc or auto-dec
   which is used in USE_INSN.  Otherwise return false.  The result is
   being used to decide whether to remove the edge between def_insn and
   use_insn when -fmodulo-sched-allow-regmoves is set.  This function
   doesn't need to consider the specific address register; no reg_moves
   will be allowed for any life range defined by def_insn and used
   by use_insn, if use_insn uses an address register auto-inc'ed by
   def_insn.

References reg_referenced_p().

Referenced by add_cross_iteration_register_deps(), create_ddg_dep_from_intra_loop_link(), and schedule_reg_moves().

static void build_inter_loop_deps ( )

static

Build inter-loop dependencies, by looking at DF analysis backwards.

References add_cross_iteration_register_deps(), ddg::bb, and df_rd_bb_info::gen.

static void build_intra_loop_deps ( )

static

Perform intra-block Data Dependency analysis and connect the nodes in
   the DDG.  We assume the loop has a single basic block.

References add_inter_loop_mem_dep(), add_intra_loop_mem_dep(), ddg::bb, bitmap_bit_p(), create_ddg_dep_from_intra_loop_link(), finish_deps_global(), free_deps(), get_ebb_head_tail(), get_node_of_insn(), init_deps(), init_deps_global(), ddg_node::insn, mem_access_insn_p(), ddg::nodes, ddg::num_nodes, ddg_node::predecessors, sched_analyze(), sched_free_deps(), and ddg_node::successors.

static void check_sccs ( )

static

Check that every node in SCCS belongs to exactly one strongly connected
   component and that no element of SCCS is empty.

References bitmap_clear(), bitmap_empty_p(), bitmap_intersect_p(), bitmap_ior(), ddg_scc::nodes, ddg_all_sccs::num_sccs, sbitmap_alloc(), sbitmap_free(), and ddg_all_sccs::sccs.

Referenced by create_ddg_all_sccs().

static int compare_sccs ( )

static

Compare function to be passed to qsort to order the backarcs in descending
   recMII order.

Referenced by order_sccs().

ddg_ptr create_ddg ( )

Given a basic block, create its DDG and return a pointer to a variable
   of ddg type that represents it.
   Initialize the ddg structure fields to the appropriate values.

References ddg::bb, ddg::closing_branch_deps, g, mem_read_insn_p(), mem_write_insn_p(), ddg::num_debug, ddg::num_loads, and ddg::num_stores.

Referenced by sms_schedule().

ddg_all_sccs_ptr create_ddg_all_sccs ( )

Perform the Strongly Connected Components decomposing algorithm on the
   DDG and return DDG_ALL_SCCS structure that contains them.

References add_scc_to_ddg(), ddg_edge::aux, ddg::backarcs, bitmap_clear(), bitmap_set_bit(), check_sccs(), ddg_edge::count, create_scc(), ddg_node::cuid, ddg_all_sccs::ddg, ddg_edge::dest, find_nodes_on_paths(), g, IN_SCC, ddg::num_backarcs, ddg::num_nodes, ddg_all_sccs::num_sccs, order_sccs(), sbitmap_alloc(), sbitmap_free(), ddg_all_sccs::sccs, and ddg_edge::src.

Referenced by sms_order_nodes().

static void create_ddg_dep_from_intra_loop_link	(	ddg_ptr	g,
		ddg_node_ptr	src_node,
		ddg_node_ptr	dest_node,
		dep_t	link
	)

static

Computes the dependence parameters (latency, distance etc.), creates
   a ddg_edge and adds it to the given DDG.

References add_edge_to_ddg(), ANTI_DEP, autoinc_var_is_used_p(), ddg::bb, bitmap_bit_p(), create_ddg_edge(), ddg_node::cuid, def_has_ccmode_p(), dep_cost(), df_bb_regno_first_def_find(), df_rd_bb_info::gen, ddg_node::insn, mem_access_insn_p(), MEM_DEP, OUTPUT_DEP, REG_DEP, and TRUE_DEP.

Referenced by build_intra_loop_deps().

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

The same as the above function, but it doesn't require a link parameter.

References add_backarc_to_ddg(), add_edge_to_ddg(), ANTI_DEP, create_ddg_edge(), dep_cost(), init_dep(), ddg_node::insn, OUTPUT_DEP, and TRUE_DEP.

Referenced by add_cross_iteration_register_deps(), add_inter_loop_mem_dep(), and add_intra_loop_mem_dep().

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

Create an edge and initialize it with given values.

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, ddg_edge::src, and ddg_edge::type.

Referenced by create_ddg_dep_from_intra_loop_link(), and create_ddg_dep_no_link().

static ddg_scc_ptr create_scc ( )

static

Create a new SCC given the set of its nodes.  Compute its recurrence_length
   and mark edges that belong to this scc as IN_SCC.

References add_backarc_to_scc(), ddg_edge::aux, ddg_scc::backarcs, bitmap_bit_p(), bitmap_copy(), ddg_edge::count, ddg_node::cuid, ddg_edge::dest, ddg_edge::distance, IN_SCC, ddg_edge::next_out, ddg::nodes, ddg_scc::nodes, ddg_scc::num_backarcs, ddg::num_nodes, ddg_node::out, sbitmap_alloc(), and set_recurrence_length().

Referenced by create_ddg_all_sccs().

static bool def_has_ccmode_p ( )

static

Return true if one of the definitions in INSN has MODE_CC.  Otherwise
   return false.

Referenced by add_cross_iteration_register_deps(), and create_ddg_dep_from_intra_loop_link().

int find_nodes_on_paths ( )

Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
   nodes - find all nodes that lie on paths from FROM to TO (not excluding
   nodes from FROM and TO).  Return nonzero if nodes exist.

References bitmap_and(), bitmap_bit_p(), bitmap_clear(), bitmap_copy(), bitmap_set_bit(), ddg_node::cuid, ddg_edge::dest, ddg_node::in, ddg_edge::next_in, ddg_edge::next_out, ddg::nodes, ddg::num_nodes, ddg_node::out, sbitmap_alloc(), sbitmap_free(), and ddg_edge::src.

Referenced by create_ddg_all_sccs(), and order_nodes_of_sccs().

void find_predecessors ( )

Given a set OPS of nodes in the DDG, find the set of their predecessors
   which are not in OPS, and set their bits in PREDS.  Bits corresponding to
   OPS are cleared from PREDS.  Leaves the other bits in PREDS unchanged.

References bitmap_and_compl(), bitmap_ior(), and ddg::nodes.

Referenced by order_nodes_in_scc().

void find_successors ( )

Given a set OPS of nodes in the DDG, find the set of their successors
   which are not in OPS, and set their bits in SUCC.  Bits corresponding to
   OPS are cleared from SUCC.  Leaves the other bits in SUCC unchanged.

References bitmap_and_compl(), bitmap_ior(), and ddg::nodes.

Referenced by order_nodes_in_scc().

void free_ddg ( )

Free all the memory allocated for the DDG.

References ddg::backarcs, free(), ddg_edge::next_out, ddg::nodes, ddg::num_backarcs, ddg::num_nodes, ddg_node::out, ddg_node::predecessors, sbitmap_free(), and ddg_node::successors.

Referenced by sms_schedule().

void free_ddg_all_sccs ( )

Frees the memory allocated for all SCCs of the DDG, but keeps the DDG.

References free(), free_scc(), ddg_all_sccs::num_sccs, and ddg_all_sccs::sccs.

Referenced by sms_order_nodes().

static void free_scc ( )

static

Cleans the memory allocation of a given SCC.

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 ( )

Given the instruction INSN return the node that represents it.

References ddg_node::insn, ddg::nodes, and ddg::num_nodes.

Referenced by add_cross_iteration_register_deps(), and build_intra_loop_deps().

static int insns_may_alias_p ( )

static

Return 1 if two specified instructions have mem expr with conflict alias sets

References for_each_rtx(), and walk_mems_1().

Referenced by add_inter_loop_mem_dep(), and add_intra_loop_mem_dep().

int longest_simple_path ( )

Find the length of a longest path from SRC to DEST in G,
   going only through NODES, and disregarding backarcs.

References ddg_node::aux, bitmap_clear(), bitmap_copy(), bitmap_set_bit(), ddg_node::count, ddg::nodes, ddg::num_nodes, sbitmap_alloc(), sbitmap_free(), and update_dist_to_successors().

Referenced by set_recurrence_length().

static void mark_mem_store ( )

static

Referenced by mem_write_insn_p().

static int mark_mem_use ( )

static

Auxiliary function for mem_read_insn_p.

Referenced by mark_mem_use_1().

static void mark_mem_use_1 ( )

static

Auxiliary function for mem_read_insn_p.

References for_each_rtx(), and mark_mem_use().

Referenced by mem_read_insn_p().

static bool mem_access_insn_p ( )

static

Returns nonzero if INSN reads to or writes from memory.

References rtx_mem_access_p().

Referenced by build_intra_loop_deps(), and create_ddg_dep_from_intra_loop_link().

static bool mem_read_insn_p ( )

static

Returns nonzero if INSN reads from memory.

References mark_mem_use_1(), and note_uses().

Referenced by add_inter_loop_mem_dep(), add_intra_loop_mem_dep(), and create_ddg().

static bool mem_write_insn_p ( )

static

Returns nonzero if INSN writes to memory.

References mark_mem_store(), and note_stores().

Referenced by add_inter_loop_mem_dep(), add_intra_loop_mem_dep(), and create_ddg().

static void order_sccs ( )

static

Order the backarcs in descending recMII order using compare_sccs.

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

Referenced by create_ddg_all_sccs().

void print_ddg ( )

Print the DDG nodes with there in/out edges to the dump file.

References ddg_node::cuid, ddg_node::in, ddg_node::insn, ddg_edge::next_in, ddg_edge::next_out, ddg::nodes, ddg::num_nodes, ddg_node::out, print_ddg_edge(), and print_rtl_single().

Referenced by sms_schedule().

void print_ddg_edge ( )

References ANTI_DEP, ddg_edge::dest, ddg_edge::distance, ddg_node::insn, ddg_edge::latency, OUTPUT_DEP, ddg_edge::src, and ddg_edge::type.

Referenced by get_sched_window(), and print_ddg().

void print_sccs ( )

Dump the sccs in SCCS.

References ddg_node::insn, ddg::nodes, ddg_scc::nodes, ddg_all_sccs::num_sccs, print_rtl_single(), and ddg_all_sccs::sccs.

Referenced by sms_order_nodes().

static bool rtx_mem_access_p ( )

static

Returns nonzero if X has access to memory.

Referenced by mem_access_insn_p().

static void set_recurrence_length ( )

static

Algorithm for computing the recurrence_length of an scc.  We assume at
   for now that cycles in the data dependence graph contain a single backarc.
   This simplifies the algorithm, and can be generalized later.

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

Referenced by create_scc().

static int update_dist_to_successors ( )

static

Updates the counts of U_NODE's successors (that belong to NODES) to be
   at-least as large as the count of U_NODE plus the latency between them.
   Sets a bit in TMP for each successor whose count was changed (increased).
   Returns nonzero if any count was changed.

References ddg_node::aux, bitmap_bit_p(), bitmap_set_bit(), ddg_node::count, ddg_node::cuid, ddg_edge::dest, ddg_edge::distance, ddg_edge::latency, ddg_edge::next_out, and ddg_node::out.

Referenced by longest_simple_path().

DEBUG_FUNCTION void vcg_print_ddg ( )

Print the given DDG in VCG format.

References ddg_node::cuid, ddg_edge::dest, ddg_edge::distance, ddg_node::insn, ddg_edge::latency, ddg_edge::next_out, ddg::nodes, ddg::num_nodes, ddg_node::out, and print_rtl_single().

static int walk_mems_1 ( )

static

References for_each_rtx(), and walk_mems_2().

Referenced by insns_may_alias_p().

static int walk_mems_2 ( )

static

References may_alias_p().

Referenced by walk_mems_1().

Variable Documentation

bool mem_ref_p

static

Auxiliary variable for mem_read_insn_p/mem_write_insn_p.

Enumerations

Functions

Variables

Enumeration Type Documentation

Function Documentation

Variable Documentation