Data Structures
struct	dref_d
struct	chain
struct	component
struct	epcc_data

Typedefs
typedef struct dref_d *	dref
typedef struct chain *	chain_p

Enumerations
enum	chain_type { CT_INVARIANT, CT_LOAD, CT_STORE_LOAD, CT_COMBINATION }
enum	ref_step_type { RS_INVARIANT, RS_NONZERO, RS_ANY }

Functions
void	dump_dref (FILE *, dref)
void	dump_dref ()
void	dump_chain (FILE *, chain_p)
void	dump_chain ()
void	dump_chains (FILE *, vec< chain_p >)
void	dump_chains ()
void	dump_component (FILE , struct component )
void	dump_component ()
void	dump_components (FILE , struct component )
void	dump_components ()
static void	release_chain ()
static void	release_chains ()
static void	release_component ()
static void	release_components ()
static unsigned	component_of ()
static void	merge_comps ()
static bool	suitable_reference_p ()
static void	aff_combination_dr_offset ()
static bool	determine_offset (struct data_reference a, struct data_reference b, double_int *off)
static basic_block	last_always_executed_block ()
static struct component *	split_data_refs_to_components (struct loop *loop, vec< data_reference_p > datarefs, vec< ddr_p > depends)
static bool	suitable_component_p ()
static struct component *	filter_suitable_components ()
static int	order_drefs ()
static dref	get_chain_root ()
static void	add_ref_to_chain ()
static chain_p	make_invariant_chain ()
static chain_p	make_rooted_chain ()
static bool	nontrivial_chain_p ()
static tree	name_for_ref ()
static bool	valid_initializer_p (struct data_reference ref, unsigned distance, struct data_reference root)
static gimple	find_looparound_phi ()
static void	insert_looparound_copy ()
static void	add_looparound_copies ()
static void	determine_roots_comp (struct loop loop, struct component comp, vec< chain_p > *chains)
static void	determine_roots (struct loop loop, struct component comps, vec< chain_p > *chains)
static void	replace_ref_with ()
static tree	ref_at_iteration ()
static tree	get_init_expr ()
static tree	predcom_tmp_var ()
static void	initialize_root_vars ()
static void	initialize_root ()
static void	initialize_root_vars_lm (struct loop loop, dref root, bool written, vec< tree > vars, vec< tree > inits, bitmap tmp_vars)
static void	execute_load_motion ()
static gimple	single_nonlooparound_use ()
static void	remove_stmt ()
static void	execute_pred_commoning_chain (struct loop *loop, chain_p chain, bitmap tmp_vars)
static unsigned	determine_unroll_factor ()
static void	execute_pred_commoning (struct loop *loop, vec< chain_p > chains, bitmap tmp_vars)
static void	replace_phis_by_defined_names ()
static void	replace_names_by_phis ()
static void	execute_pred_commoning_cbck ()
static void	base_names_in_chain_on ()
static void	eliminate_temp_copies ()
static bool	chain_can_be_combined_p ()
static gimple	find_use_stmt ()
static bool	may_reassociate_p ()
static gimple	find_associative_operation_root ()
static gimple	find_common_use_stmt ()
static bool	combinable_refs_p (dref r1, dref r2, enum tree_code code, bool swap, tree *rslt_type)
static void	remove_name_from_operation ()
static gimple	reassociate_to_the_same_stmt ()
static gimple	stmt_combining_refs ()
static chain_p	combine_chains ()
static void	try_combine_chains ()
static bool	prepare_initializers_chain ()
static void	prepare_initializers ()
static bool	tree_predictive_commoning_loop ()
unsigned	tree_predictive_commoning ()
static unsigned	run_tree_predictive_commoning ()
static bool	gate_tree_predictive_commoning ()
gimple_opt_pass *	make_pass_predcom ()

Variables
static bitmap	looparound_phis
static struct pointer_map_t *	name_expansions

Typedef Documentation

typedef struct chain * chain_p

   Chains of data references.

typedef struct dref_d * dref

   Data references (or phi nodes that carry data reference values across
   loop iterations).

Enumeration Type Documentation

enum chain_type

   Type of the chain of the references.

Enumerator:

CT_INVARIANT	The addresses of the references in the chain are constant.
CT_LOAD	There are only loads in the chain.
CT_STORE_LOAD	Root of the chain is store, the rest are loads.
CT_COMBINATION	A combination of two chains.

enum ref_step_type

   Describes the knowledge about the step of the memory references in
   the component.

Enumerator:

RS_INVARIANT	The step is zero.
RS_NONZERO	The step is nonzero.
RS_ANY	The step may or may not be nonzero.

Function Documentation

static void add_looparound_copies ( )

static

   For references in CHAIN that are copied around the LOOP (created previously
   by PRE, or by user), add the results of such copies to the chain.  This
   enables us to remove the copies by unrolling, and may need less registers
   (also, it may allow us to combine chains together).

static void add_ref_to_chain ( )

static

   Adds REF to the chain CHAIN.

static void aff_combination_dr_offset ( )

static

   Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET.

static void base_names_in_chain_on ( )

static

   Base NAME and all the names in the chain of phi nodes that use it
   on variable VAR.  The phi nodes are recognized by being in the copies of
   the header of the LOOP.

static bool chain_can_be_combined_p ( )

static

   Returns true if CHAIN is suitable to be combined.

static bool combinable_refs_p	(	dref	r1,
		dref	r2,
		enum tree_code *	code,
		bool *	swap,
		tree *	rslt_type
	)

static

   Checks whether R1 and R2 are combined together using CODE, with the result
   in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
   if it is true.  If CODE is ERROR_MARK, set these values instead.

static chain_p combine_chains ( )

static

   Tries to combine chains CH1 and CH2 together.  If this succeeds, the
   description of the new chain is returned, otherwise we return NULL.

static unsigned component_of ( )

static

   Finds a root of tree given by FATHERS containing A, and performs path
   shortening.

References DR_REF, DR_STEP, integer_nonzerop(), integer_zerop(), is_gimple_reg_type(), RS_ANY, RS_INVARIANT, RS_NONZERO, and tree_could_throw_p().

Referenced by release_component().

static bool determine_offset	(	struct data_reference *	a,
		struct data_reference *	b,
		double_int *	off
	)

static

   Determines number of iterations of the innermost enclosing loop before B
   refers to exactly the same location as A and stores it to OFF.  If A and
   B do not have the same step, they never meet, or anything else fails,
   returns false, otherwise returns true.  Both A and B are assumed to
   satisfy suitable_reference_p.

     Check that both the references access the location in the same type.

     Check whether the base address and the step of both references is the
     same.

         If the references have loop invariant address, check that they access
         exactly the same location.

     Compare the offsets of the addresses, and check whether the difference
     is a multiple of step.

References data_reference::aux, comp, DR_REF, last_always_executed_block(), and suitable_reference_p().

static void determine_roots	(	struct loop *	loop,
		struct component *	comps,
		vec< chain_p > *	chains
	)

static

   Find roots of the values and determine distances in components COMPS, and
   separates the references to CHAINS.  LOOP is the current loop.

static void determine_roots_comp	(	struct loop *	loop,
		struct component *	comp,
		vec< chain_p > *	chains
	)

static

   Find roots of the values and determine distances in the component COMP.
   The references are redistributed into CHAINS.  LOOP is the current
   loop.

     Invariants are handled specially.

static unsigned determine_unroll_factor ( )

static

   Determines the unroll factor necessary to remove as many temporary variable
   copies as possible.  CHAINS is the list of chains that will be
   optimized.

         The best unroll factor for this chain is equal to the number of
         temporary variables that we create for it.

References flow_bb_inside_loop_p(), and replace_ssa_name_symbol().

void dump_chain	(	FILE *	,
		chain_p
	)

   Dumps CHAIN to FILE.

void dump_chain ( )

void dump_chains	(	FILE *	,
		vec< chain_p >
	)

   Dumps CHAINS to FILE.

void dump_chains ( )

References free(), chain::refs, and chain::vars.

void dump_component	(	FILE *	,
		struct component *
	)

   Dumps COMP to FILE.

void dump_component ( )

void dump_components	(	FILE *	,
		struct component *
	)

   Dumps COMPS to FILE.

void dump_components ( )

References free().

void dump_dref	(	FILE *	,
		dref
	)

   Dumps data reference REF to FILE.

void dump_dref ( )

References CT_COMBINATION, CT_INVARIANT, CT_LOAD, and CT_STORE_LOAD.

static void eliminate_temp_copies ( )

static

   Given an unrolled LOOP after predictive commoning, remove the
   register copies arising from phi nodes by changing the base
   variables of SSA names.  TMP_VARS is the set of the temporary variables
   for those we want to perform this.

         Base all the ssa names in the ud and du chain of NAME on VAR.

                In case we could not unroll the loop enough to eliminate
                all copies, we may reach the loop header before the defining
                statement (in that case, some register copies will be present
                in loop latch in the final code, corresponding to the newly
                created looparound phi nodes).

References find_use_stmt(), gimple_assign_lhs(), and gimple_assign_rhs_code().

static void execute_load_motion ( )

static

   Execute load motion for references in chain CHAIN.  Uids of the newly
   created temporary variables are marked in TMP_VARS.

     If there are no reads in the loop, there is nothing to do.

static void execute_pred_commoning	(	struct loop *	loop,
		vec< chain_p >	chains,
		bitmap	tmp_vars
	)

static

   Perform the predictive commoning optimization for CHAINS.
   Uids of the newly created temporary variables are marked in TMP_VARS.

static void execute_pred_commoning_cbck ( )

static

     Restore phi nodes that were replaced by ssa names before
     tree_transform_and_unroll_loop (see detailed description in
     tree_predictive_commoning_loop).

static void execute_pred_commoning_chain	(	struct loop *	loop,
		chain_p	chain,
		bitmap	tmp_vars
	)

static

   Perform the predictive commoning optimization for a chain CHAIN.
   Uids of the newly created temporary variables are marked in TMP_VARS.

         For combined chains, just remove the statements that are used to
         compute the values of the expression (except for the root one).

         For non-combined chains, set up the variables that hold its value,
         and replace the uses of the original references by these
         variables.

References dref_d::name_defined_by_phi, chain::refs, and dref_d::stmt.

static struct component* filter_suitable_components ( )

staticread

   Check the conditions on references inside each of components COMPS,
   and remove the unsuitable components from the list.  The new list
   of components is returned.  The conditions are described in 2) at
   the beginning of this file.  LOOP is the current loop.

static gimple find_associative_operation_root ( )

static

   If the operation used in STMT is associative and commutative, go through the
   tree of the same operations and returns its root.  Distance to the root
   is stored in DISTANCE.

static gimple find_common_use_stmt ( )

static

   Returns the common statement in that NAME1 and NAME2 have a use.  If there
   is no such statement, returns NULL_TREE.  In case the operation used on
   NAME1 and NAME2 is associative and commutative, returns the root of the
   tree formed by this operation instead of the statement that uses NAME1 or
   NAME2.

Referenced by find_use_stmt().

static gimple find_looparound_phi ( )

static

   Finds looparound phi node of LOOP that copies the value of REF, and if its
   initial value is correct (equal to initial value of REF shifted by one
   iteration), returns the phi node.  Otherwise, NULL_TREE is returned.  ROOT
   is the root of the current chain.

     Analyze the behavior of INIT_REF with respect to LOOP (innermost
     loop enclosing PHI).

References chain::has_max_use_after, and chain::length.

static gimple find_use_stmt ( )

static

   Returns the modify statement that uses NAME.  Skips over assignment
   statements, NAME is replaced with the actual name used in the returned
   statement.

     Skip over assignments.

References commutative_tree_code(), find_common_use_stmt(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs_code(), and name_for_ref().

Referenced by eliminate_temp_copies().

static bool gate_tree_predictive_commoning ( )

static

static dref get_chain_root ( )

inlinestatic

   Returns root of the CHAIN.

References chain::all_always_accessed, dref_d::always_accessed, CT_LOAD, CT_STORE_LOAD, DR_IS_READ, dref_d::ref, chain::refs, and chain::type.

static tree get_init_expr ( )

static

   Get the initialization expression for the INDEX-th temporary variable
   of CHAIN.

static void initialize_root ( )

static

   Create the variables and initialization statement for root of chain
   CHAIN.  Uids of the newly created temporary variables are marked
   in TMP_VARS.

References make_ssa_name().

Referenced by single_nonlooparound_use().

static void initialize_root_vars ( )

static

   Creates the variables for CHAIN, as well as phi nodes for them and
   initialization on entry to LOOP.  Uids of the newly created
   temporary variables are marked in TMP_VARS.

     If N == 0, then all the references are within the single iteration.  And
     since this is an nonempty chain, reuse_first cannot be true.

static void initialize_root_vars_lm	(	struct loop *	loop,
		dref	root,
		bool	written,
		vec< tree > *	vars,
		vec< tree >	inits,
		bitmap	tmp_vars
	)

static

   Initializes a variable for load motion for ROOT and prepares phi nodes and
   initialization on entry to LOOP if necessary.  The ssa name for the variable
   is stored in VARS.  If WRITTEN is true, also a phi node to copy its value
   around the loop is created.  Uid of the newly created temporary variable
   is marked in TMP_VARS.  INITS is the list containing the (single)
   initializer.

     Find the initializer for the variable, and check that it cannot
     trap.

References bitmap_bit_p(), and is_gimple_debug().

static void insert_looparound_copy ( )

static

   Adds a reference for the looparound copy of REF in PHI to CHAIN.

static basic_block last_always_executed_block ( )

static

   Returns the last basic block in LOOP for that we are sure that
   it is executed whenever the loop is entered.

Referenced by determine_offset().

static chain_p make_invariant_chain ( )

static

   Returns the chain for invariant component COMP.

References DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_STEP, integer_zerop(), and operand_equal_p().

gimple_opt_pass* make_pass_predcom ( )

static chain_p make_rooted_chain ( )

static

   Make a new chain rooted at REF.

static bool may_reassociate_p ( )

static

   Returns true if we may perform reassociation for operation CODE in TYPE.

References gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_set_rhs_from_tree(), gsi_for_stmt(), is_gimple_assign(), and si.

static void merge_comps ( )

static

   Join operation for DFU.  FATHERS gives the tree, SIZES are sizes of the
   components, A and B are components to merge.

References aff_combination_add(), aff_combination_const(), DR_INIT, DR_OFFSET, tree_to_aff_combination_expand(), and tree_to_double_int().

static tree name_for_ref ( )

static

   Returns the ssa name that contains the value of REF, or NULL_TREE if there
   is no such name.

Referenced by find_use_stmt().

static bool nontrivial_chain_p ( )

static

   Returns true if CHAIN is not trivial.

static int order_drefs ( )

static

   Compares two drefs A and B by their offset and position.  Callback for
   qsort.

References chain::all_always_accessed, dref_d::always_accessed, and chain::refs.

static tree predcom_tmp_var ( )

static

   Returns a new temporary variable used for the I-th variable carrying
   value of REF.  The variable's uid is marked in TMP_VARS.

     We never access the components of the temporary variable in predictive
     commoning.

References DR_REF, loop_latch_edge(), loop_preheader_edge(), component::next, and dref_d::ref.

static void prepare_initializers ( )

static

   Prepare initializers for CHAINS in LOOP, and free chains that cannot
   be used because the initializers might trap.

static bool prepare_initializers_chain ( )

static

   Prepare initializers for CHAIN in LOOP.  Returns false if this is
   impossible because one of these initializers may trap, true otherwise.

     Find the initializers for the variables, and check that they cannot
     trap.

     If we have replaced some looparound phi nodes, use their initializers
     instead of creating our own.

static gimple reassociate_to_the_same_stmt ( )

static

   Reassociates the expression in that NAME1 and NAME2 are used so that they
   are combined in a single statement, and returns this statement.

     Find the root of the nearest expression in that both NAME1 and NAME2
     are used.

     Remove NAME1 and NAME2 from the statements in that they are used
     currently.

     Insert the new statement combining NAME1 and NAME2 before S1, and
     combine it with the rhs of S1.

     Rhs of S1 may now be either a binary expression with operation
     CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
     so that name1 or name2 was removed from it).

static tree ref_at_iteration ( )

static

   Returns the reference to the address of REF in the ITER-th iteration of
   LOOP, or NULL if we fail to determine it (ITER may be negative).  We
   try to preserve the original shape of the reference (not rewrite it
   as an indirect ref to the address), to make tree_could_trap_p in
   prepare_initializers_chain return false more often.

         Check that the offset is loop invariant.

         Check that the lower bound and the step are loop invariant.

static void release_chain ( )

static

   Frees a chain CHAIN.

References component::next, and release_component().

static void release_chains ( )

static

   Frees CHAINS.

static void release_component ( )

static

   Frees a component COMP.

References component_of().

Referenced by release_chain(), and suitable_component_p().

static void release_components ( )

static

   Frees list of components COMPS.

static void remove_name_from_operation ( )

static

   Remove OP from the operation on rhs of STMT, and replace STMT with
   an assignment of the remaining operand.

     We should not have reallocated STMT.

References dref_d::distance, chain::length, chain::refs, and swap().

static void remove_stmt ( )

static

   Remove statement STMT, as well as the chain of assignments in that it is
   used.

static void replace_names_by_phis ( )

static

   For each reference in CHAINS, if name_defined_by_phi is not
   NULL, use it to set the stmt field.

References chain::combined, CT_COMBINATION, CT_LOAD, and chain::type.

static void replace_phis_by_defined_names ( )

static

   For each reference in CHAINS, if its defining statement is
   phi node, record the ssa name that is defined by it.

static void replace_ref_with ( )

static

   Replace the reference in statement STMT with temporary variable
   NEW_TREE.  If SET is true, NEW_TREE is instead initialized to the value of
   the reference in the statement.  IN_LHS is true if the reference
   is in the lhs of STMT, false if it is in rhs.

         Turn the phi node into GIMPLE_ASSIGN.

     Since the reference is of gimple_reg type, it should only
     appear as lhs or rhs of modify statement.

     If we do not need to initialize NEW_TREE, just replace the use of OLD.

         We have statement

         OLD = VAL

         If OLD is a memory reference, then VAL is gimple_val, and we transform
         this to

         OLD = VAL
         NEW = VAL

         Otherwise, we are replacing a combination chain,
         VAL is the expression that performs the combination, and OLD is an
         SSA name.  In this case, we transform the assignment to

         OLD = VAL
         NEW = OLD

         VAL = OLD

         is transformed to

         VAL = OLD
         NEW = VAL

Referenced by single_nonlooparound_use().

static unsigned run_tree_predictive_commoning ( )

static

   Predictive commoning Pass.

static gimple single_nonlooparound_use ( )

static

   Returns the single statement in that NAME is used, excepting
   the looparound phi nodes contained in one of the chains.  If there is no
   such statement, or more statements, NULL is returned.

             Ignore uses in looparound phi nodes.  Uses in other phi nodes
             could not be processed anyway, so just fail for them.

References dref_d::distance, initialize_root(), chain::length, chain::refs, replace_ref_with(), dref_d::stmt, and chain::vars.

static struct component* split_data_refs_to_components	(	struct loop *	loop,
		vec< data_reference_p >	datarefs,
		vec< ddr_p >	depends
	)

staticread

   Splits dependence graph on DATAREFS described by DEPENDS to components.

             A fake reference for call or asm_expr that may clobber memory;
             just fail.

     A component reserved for the "bad" data references.

         If both A and B are reads, we may ignore unsuitable dependences.

static gimple stmt_combining_refs ( )

static

   Returns the statement that combines references R1 and R2.  In case R1
   and R2 are not used in the same statement, but they are used with an
   associative and commutative operation in the same expression, reassociate
   the expression so that they are used in the same statement.

static bool suitable_component_p ( )

static

   Returns true if the component COMP satisfies the conditions
   described in 2) at the beginning of this file.  LOOP is the current
   loop.

     If there is a write inside the component, we must know whether the
     step is nonzero or not -- we would not otherwise be able to recognize
     whether the value accessed by reads comes from the OFFSET-th iteration
     or the previous one.

References comp, free(), component::next, component::refs, and release_component().

static bool suitable_reference_p ( )

static

   Returns true if A is a reference that is suitable for predictive commoning
   in the innermost loop that contains it.  REF_STEP is set according to the
   step of the reference A.

Referenced by determine_offset().

unsigned tree_predictive_commoning ( )

   Runs predictive commoning.

static bool tree_predictive_commoning_loop ( )

static

   Performs predictive commoning for LOOP.  Returns true if LOOP was
   unrolled.

     Find the data references and split them into components according to their
     dependence relations.

     Find the suitable components and split them into chains.

     Try to combine the chains that are always worked with together.

     Determine the unroll factor, and if the loop should be unrolled, ensure
     that its number of iterations is divisible by the factor.

     Execute the predictive commoning transformations, and possibly unroll the
     loop.

         Cfg manipulations performed in tree_transform_and_unroll_loop before
         execute_pred_commoning_cbck is called may cause phi nodes to be
         reallocated, which is a problem since CHAINS may point to these
         statements.  To fix this, we store the ssa names defined by the
         phi nodes here instead of the phi nodes themselves, and restore
         the phi nodes in execute_pred_commoning_cbck.  A bit hacky.

static void try_combine_chains ( )

static

   Try to combine the CHAINS.

References dump_file, dump_flags, free_data_refs(), and free_dependence_relations().

static bool valid_initializer_p	(	struct data_reference *	ref,
		unsigned	distance,
		struct data_reference *	root
	)

static

   Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
   iterations of the innermost enclosing loop).

     Both REF and ROOT must be accessing the same object.

     The initializer is defined outside of loop, hence its address must be
     invariant inside the loop.

     If the address of the reference is invariant, initializer must access
     exactly the same location.

     Verify that this index of REF is equal to the root's index at
     -DISTANCE-th iteration.

Variable Documentation

bitmap looparound_phis

static

   Bitmap of ssa names defined by looparound phi nodes covered by chains.

struct pointer_map_t* name_expansions

static

   Cache used by tree_to_aff_combination_expand.

Data Structures

Typedefs

Enumerations

Functions

Variables

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation