GCC Middle and Back End API Reference
tree-predcom.c File Reference

Data Structures

struct  dref_d
struct  chain
struct  component
struct  epcc_data


typedef struct dref_ddref
typedef struct chainchain_p


enum  ref_step_type { RS_INVARIANT, RS_NONZERO, RS_ANY }


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 componentsplit_data_refs_to_components (struct loop *loop, vec< data_reference_p > datarefs, vec< ddr_p > depends)
static bool suitable_component_p ()
static struct componentfilter_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_passmake_pass_predcom ()


static bitmap looparound_phis
static struct pointer_map_tname_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.  
     The addresses of the references in the chain are constant.  
     There are only loads in the chain.  
     Root of the chain is store, the rest are loads.  
     A combination of two chains.  
   Describes the knowledge about the step of the memory references in
   the component.  
     The step is zero.  
     The step is nonzero.  
     The step may or may not be nonzero.  

Function Documentation

static void add_looparound_copies ( )
   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 ( )
   Adds REF to the chain CHAIN.  
static void aff_combination_dr_offset ( )
   Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET.  
static void base_names_in_chain_on ( )
   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 ( )
   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 
   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 ( )
   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 ( )
   Finds a root of tree given by FATHERS containing A, and performs path

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 
   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
         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 
   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 
   Find roots of the values and determine distances in the component COMP.
   The references are redistributed into CHAINS.  LOOP is the current
     Invariants are handled specially.  
static unsigned determine_unroll_factor ( )
   Determines the unroll factor necessary to remove as many temporary variable
   copies as possible.  CHAINS is the list of chains that will be
         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 *  ,
   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 *  ,
   Dumps data reference REF to FILE.  
void dump_dref ( )
static void eliminate_temp_copies ( )
   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 ( )
   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 
   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 ( )
     Restore phi nodes that were replaced by ssa names before
     tree_transform_and_unroll_loop (see detailed description in
static void execute_pred_commoning_chain ( struct loop loop,
chain_p  chain,
bitmap  tmp_vars 
   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

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

static struct component* filter_suitable_components ( )
   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 ( )
   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 ( )
   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

Referenced by find_use_stmt().

static gimple find_looparound_phi ( )
   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 ( )
   Returns the modify statement that uses NAME.  Skips over assignment
   statements, NAME is replaced with the actual name used in the returned
     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 dref get_chain_root ( )
static tree get_init_expr ( )
   Get the initialization expression for the INDEX-th temporary variable
   of CHAIN.  
static void initialize_root ( )
   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 ( )
   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 
   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)
     Find the initializer for the variable, and check that it cannot

References bitmap_bit_p(), and is_gimple_debug().

static void insert_looparound_copy ( )
   Adds a reference for the looparound copy of REF in PHI to CHAIN.  
static basic_block last_always_executed_block ( )
   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 ( )
   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 ( )
   Make a new chain rooted at REF.  
static bool may_reassociate_p ( )
   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 ( )
   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 ( )
   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 ( )
   Returns true if CHAIN is not trivial.  
static int order_drefs ( )
   Compares two drefs A and B by their offset and position.  Callback for

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

static tree predcom_tmp_var ( )
   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

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

static void prepare_initializers ( )
   Prepare initializers for CHAINS in LOOP, and free chains that cannot
   be used because the initializers might trap.  
static bool prepare_initializers_chain ( )
   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
     If we have replaced some looparound phi nodes, use their initializers
     instead of creating our own.  
static gimple reassociate_to_the_same_stmt ( )
   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
     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 ( )
   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 ( )
   Frees a chain CHAIN.  

References component::next, and release_component().

static void release_chains ( )
   Frees CHAINS.  
static void release_component ( )
   Frees a component COMP.  

References component_of().

Referenced by release_chain(), and suitable_component_p().

static void release_components ( )
   Frees list of components COMPS.  
static void remove_name_from_operation ( )
   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 ( )
   Remove statement STMT, as well as the chain of assignments in that it is
static void replace_names_by_phis ( )
   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 ( )
   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 ( )
   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 ( )
   Predictive commoning Pass.  
static gimple single_nonlooparound_use ( )
   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 
   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 ( )
   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 ( )
   Returns true if the component COMP satisfies the conditions
   described in 2) at the beginning of this file.  LOOP is the current
     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 ( )
   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 ( )
   Performs predictive commoning for LOOP.  Returns true if LOOP was
     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
         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 ( )
   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 
   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
   Bitmap of ssa names defined by looparound phi nodes covered by chains.  
struct pointer_map_t* name_expansions
   Cache used by tree_to_aff_combination_expand.