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

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.

static void add_backarc_to_ddg ( )

static

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

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

static void add_backarc_to_scc	(	ddg_scc_ptr	,
		ddg_edge_ptr
	)

static

static void add_backarc_to_scc ( )

static

   Add backarc to an SCC.

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.

     Create inter-loop true dependences and anti dependences.

         ??? Do not handle uses with DF_REF_IN_NOTE notes.

             Add true deps from last_def to it's uses in the next
             iteration.  Any such upwards exposed use appears before
             the last_def def.

             Add anti deps from last_def's uses in the current iteration
             to the first def in the next iteration.  We do not add ANTI
             dep when there is an intra-loop TRUE dep in the opposite
             direction, but use regmoves to fix such disregarded ANTI
             deps when broken.  If the first_def reaches the USE then
             there is such a dep.

            Always create the edge if the use node is a branch in
            order to prevent the creation of reg-moves.  
            If the address that is being auto-inc or auto-dec in LAST_DEF
            is used in USE_INSN then do not remove the edge to make sure
            reg-moves will not be created for that address.

     Create an inter-loop output dependence between LAST_DEF (which is the
     last def in its block, being downwards exposed) and the first def in
     its block.  Avoid creating a self output dependence.  Avoid creating
     an output dependence if there is a dependence path between the two
     defs starting with a true dependence to a use which can be in the
     next iteration; followed by an anti dependence of that use to the
     first def (i.e. if there is a use between the two defs.)

static void add_edge_to_ddg	(	ddg_ptr	g,
		ddg_edge_ptr
	)

static

static void add_edge_to_ddg ( )

static

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

     Should have allocated the sbitmaps.

static void add_inter_loop_mem_dep ( )

static

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

       Do not create edge if memory references have disjoint alias sets.

References ddg::bb, get_ebb_head_tail(), init_deps(), init_deps_global(), ddg_node::insn, ddg::nodes, ddg::num_nodes, and sched_analyze().

static void add_intra_loop_mem_dep ( )

static

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

       Do not create edge if memory references have disjoint alias sets
       or 'to' and 'from' are the same instruction.

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

static void add_scc_to_ddg	(	ddg_all_sccs_ptr	,
		ddg_scc_ptr
	)

static

Referenced by compare_sccs().

static void add_scc_to_ddg ( )

static

   Add the given SCC to the DDG.

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.

static void build_inter_loop_deps ( )

static

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

     Find inter-loop register output, true and anti deps.

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.

     Hold the dependency analysis state during dependency calculations.

     Build the dependence information, using the sched_analyze function.

     Do the intra-block data dependence analysis for the given block.

     Build intra-loop data dependencies using the scheduler dependency
     analysis.

             Don't add dependencies on debug insns to non-debug insns
             to avoid codegen differences between -g and -g0.

         If this insn modifies memory, add an edge to all insns that access
         memory.

                     Don't bother calculating inter-loop dep if an intra-loop dep
                     already exists.

                     If -fmodulo-sched-allow-regmoves
                     is set certain anti-dep edges are not created.
                     It might be that these anti-dep edges are on the
                     path from one memory instruction to another such that
                     removing these edges could cause a violation of the
                     memory dependencies.  Thus we add intra edges between
                     every two memory instructions in this case.

     Free the INSN_LISTs.

     Free dependencies.

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.

         Verify that every node in sccs is in exactly one strongly
         connected component.

static int compare_sccs ( )

static

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

References add_scc_to_ddg(), and create_scc().

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.

     Count the number of insns in the BB.

     There is nothing to do for this BB.

     Allocate the nodes array, and initialize the nodes.

     We must have found a branch in DDG.

     Build the data dependency graph.

References bitmap_clear(), ddg::closing_branch, ddg_node::cuid, ddg_node::first_note, ddg_node::insn, ddg::nodes, ddg_node::predecessors, sbitmap_alloc(), and ddg_node::successors.

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.

         If the backarc already belongs to an SCC, continue.

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.

     Note: REG_DEP_ANTI applies to MEM ANTI_DEP as well!!

     We currently choose not to create certain anti-deps edges and
     compensate for that by generating reg-moves based on the life-range
     analysis.  The anti-deps that will be deleted are the ones which
     have true-deps edges in the opposite direction (in other words
     the kernel has only one def of the relevant register).
     If the address that is being auto-inc or auto-dec in DEST_NODE
     is used in SRC_NODE then do not remove the edge to make sure
     reg-moves will not be created for this address.  
     TODO: support the removal of all anti-deps edges, i.e. including those
     whose register has multiple defs in the loop.

         TODO: Handle registers that REG_P is not true for them, i.e.
         subregs and special registers.

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.

Referenced by add_intra_loop_mem_dep(), and walk_mems_1().

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.

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.

     Mark the backarcs that belong to this SCC.

Referenced by compare_sccs().

static bool def_has_ccmode_p ( )

static

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

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 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 find_predecessors(), and verify_partial_schedule().

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.

     We want those that are not in ops.

References ddg_edge::aux, ddg::backarcs, bitmap_clear(), bitmap_set_bit(), ddg_edge::count, ddg_node::cuid, ddg_edge::dest, find_nodes_on_paths(), IN_SCC, and ddg_edge::src.

Referenced by calculate_order_params().

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.

     We want those that are not in ops.

Referenced by calculate_order_params().

void free_ddg ( )

   Free all the memory allocated for the DDG.

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

void free_ddg_all_sccs ( )

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

References bitmap_set_bit().

static void free_scc ( )

static

   Cleans the memory allocation of a given SCC.

References bitmap_ior(), and ddg::nodes.

ddg_node_ptr get_node_of_insn ( )

   Given the instruction INSN return the node that represents it.

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

static int insns_may_alias_p ( )

static

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

     For each pair of MEMs in INSN1 and INSN2 check their independence.

Referenced by walk_mems_1().

int longest_simple_path ( )

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

     Data will hold the distance of the longest path found so far from
     src to each node.  Initialize to -1 = less than minimum.

static void mark_mem_store ( )

static

References note_stores().

static int mark_mem_use ( )

static

   Auxiliary function for mem_read_insn_p.

static void mark_mem_use_1 ( )

static

   Auxiliary function for mem_read_insn_p.

References note_uses().

static bool mem_access_insn_p ( )

static

   Returns nonzero if INSN reads to or writes from memory.

References reg_referenced_p().

static bool mem_read_insn_p ( )

static

   Returns nonzero if INSN reads from memory.

Referenced by add_intra_loop_mem_dep(), and walk_mems_1().

static bool mem_write_insn_p ( )

static

   Returns nonzero if INSN writes to memory.

Referenced by walk_mems_1().

static void order_sccs ( )

static

   Order the backarcs in descending recMII order using compare_sccs.

void print_ddg ( )

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

void print_ddg_edge ( )

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

Referenced by free_ddg().

void print_sccs ( )

   Dump the sccs in SCCS.

static bool rtx_mem_access_p ( )

static

   Returns nonzero if X has access to memory.

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.

             fprintf (stderr, "Backarc not on simple cycle in SCC.\n");

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

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.

DEBUG_FUNCTION void vcg_print_ddg ( )

   Print the given DDG in VCG format.

             Give the backarcs a different color.

static int walk_mems_1 ( )

static

         Visit all MEMs in *PAT and check independence.

           Indicate that dependence was determined and stop traversal.

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

static int walk_mems_2 ( )

static

References for_each_rtx(), and 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