GCC Middle and Back End API Reference
tree-predcom.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "predict.h"
#include "tree-pass.h"
#include "ssa.h"
#include "gimple-pretty-print.h"
#include "alias.h"
#include "fold-const.h"
#include "cfgloop.h"
#include "tree-eh.h"
#include "gimplify.h"
#include "gimple-iterator.h"
#include "gimplify-me.h"
#include "tree-ssa-loop-ivopts.h"
#include "tree-ssa-loop-manip.h"
#include "tree-ssa-loop-niter.h"
#include "tree-ssa-loop.h"
#include "tree-into-ssa.h"
#include "tree-dfa.h"
#include "tree-ssa.h"
#include "tree-data-ref.h"
#include "tree-scalar-evolution.h"
#include "tree-affine.h"
#include "builtins.h"
#include "opts.h"
Include dependency graph for tree-predcom.cc:

Data Structures

class  dref_d
struct  chain
struct  component
class  pcom_worker
struct  epcc_data


#define MAX_DISTANCE   (target_avail_regs < 16 ? 4 : 8)


typedef class dref_ddref
typedef struct chainchain_p


enum  chain_type {
enum  ref_step_type { RS_INVARIANT , RS_NONZERO , RS_ANY }


void dump_dref (FILE *, dref)
void dump_chain (FILE *, chain_p)
void dump_chains (FILE *file, const vec< chain_p > &chains)
void dump_component (FILE *, struct component *)
void dump_components (FILE *, struct component *)
static void release_components (struct component *comps)
static unsigned component_of (vec< unsigned > &fathers, unsigned a)
static void merge_comps (vec< unsigned > &fathers, vec< unsigned > &sizes, unsigned a, unsigned b)
static bool suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)
static basic_block last_always_executed_block (class loop *loop)
static int order_drefs (const void *a, const void *b)
static int order_drefs_by_pos (const void *a, const void *b)
static dref get_chain_root (chain_p chain)
static dref get_chain_last_write_at (chain_p chain, unsigned distance)
static dref get_chain_last_write_before_load (chain_p chain, unsigned load_idx)
static void add_ref_to_chain (chain_p chain, dref ref)
static chain_p make_invariant_chain (struct component *comp)
static chain_p make_rooted_chain (dref ref, enum chain_type type)
static bool nontrivial_chain_p (chain_p chain)
static tree name_for_ref (dref ref)
static void insert_looparound_copy (chain_p chain, dref ref, gphi *phi)
static void replace_ref_with (gimple *stmt, tree new_tree, bool set, bool in_lhs)
static tree ref_at_iteration (data_reference_p dr, int iter, gimple_seq *stmts, tree niters=NULL_TREE)
static tree get_init_expr (chain_p chain, unsigned index)
static tree predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
static void initialize_root_vars (class loop *loop, chain_p chain, bitmap tmp_vars)
static bool is_inv_store_elimination_chain (class loop *loop, chain_p chain)
static void initialize_root_vars_store_elim_1 (chain_p chain)
static void initialize_root_vars_store_elim_2 (class loop *loop, chain_p chain, bitmap tmp_vars)
static void finalize_eliminated_stores (class loop *loop, chain_p chain)
static void initialize_root_vars_lm (class loop *loop, dref root, bool written, vec< tree > *vars, const vec< tree > &inits, bitmap tmp_vars)
static void execute_load_motion (class loop *loop, chain_p chain, bitmap tmp_vars)
static unsigned determine_unroll_factor (const vec< chain_p > &chains)
static void replace_phis_by_defined_names (vec< chain_p > &chains)
static void replace_names_by_phis (vec< chain_p > chains)
static void execute_pred_commoning_cbck (class loop *loop, void *data)
static void base_names_in_chain_on (class loop *loop, tree name, tree var)
static void eliminate_temp_copies (class loop *loop, bitmap tmp_vars)
static bool chain_can_be_combined_p (chain_p chain)
static bool may_reassociate_p (tree type, enum tree_code code)
static void remove_name_from_operation (gimple *stmt, tree op)
static void update_pos_for_combined_chains (chain_p root)
static bool pcom_stmt_dominates_stmt_p (gimple *s1, gimple *s2)
static bool prepare_initializers_chain_store_elim (class loop *loop, chain_p chain)
static void insert_init_seqs (class loop *loop, vec< chain_p > &chains)
unsigned tree_predictive_commoning (bool allow_unroll_p)
static unsigned run_tree_predictive_commoning (struct function *fun, bool allow_unroll_p)
gimple_opt_passmake_pass_predcom (gcc::context *ctxt)

Macro Definition Documentation


#define MAX_DISTANCE   (target_avail_regs < 16 ? 4 : 8)
Predictive commoning.
   Copyright (C) 2005-2024 Free Software Foundation, Inc.

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
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
This file implements the predictive commoning optimization.  Predictive
commoning can be viewed as CSE around a loop, and with some improvements,
as generalized strength reduction-- i.e., reusing values computed in
earlier iterations of a loop in the later ones.  So far, the pass only
handles the most useful case, that is, reusing values of memory references.
If you think this is all just a special case of PRE, you are sort of right;
however, concentrating on loops is simpler, and makes it possible to
incorporate data dependence analysis to detect the opportunities, perform
loop unrolling to avoid copies together with renaming immediately,
and if needed, we could also take register pressure into account.

Let us demonstrate what is done on an example:

for (i = 0; i < 100; i++)
    a[i+2] = a[i] + a[i+1];
    b[10] = b[10] + i;
    c[i] = c[99 - i];
    d[i] = d[i + 1];

1) We find data references in the loop, and split them to mutually
   independent groups (i.e., we find components of a data dependence
   graph).  We ignore read-read dependences whose distance is not constant.
   (TODO -- we could also ignore antidependences).  In this example, we
   find the following groups:

   a[i]{read}, a[i+1]{read}, a[i+2]{write}
   b[10]{read}, b[10]{write}
   c[99 - i]{read}, c[i]{write}
   d[i + 1]{read}, d[i]{write}

2) Inside each of the group, we verify several conditions:
   a) all the references must differ in indices only, and the indices
      must all have the same step
   b) the references must dominate loop latch (and thus, they must be
      ordered by dominance relation).
   c) the distance of the indices must be a small multiple of the step
   We are then able to compute the difference of the references (# of
   iterations before they point to the same place as the first of them).
   Also, in case there are writes in the loop, we split the groups into
   chains whose head is the write whose values are used by the reads in
   the same chain.  The chains are then processed independently,
   making the further transformations simpler.  Also, the shorter chains
   need the same number of registers, but may require lower unrolling
   factor in order to get rid of the copies on the loop latch.

   In our example, we get the following chains (the chain for c is invalid).

   a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2}
   b[10]{read,+0}, b[10]{write,+0}
   d[i + 1]{read,+0}, d[i]{write,+1}

3) For each read, we determine the read or write whose value it reuses,
   together with the distance of this reuse.  I.e. we take the last
   reference before it with distance 0, or the last of the references
   with the smallest positive distance to the read.  Then, we remove
   the references that are not used in any of these chains, discard the
   empty groups, and propagate all the links so that they point to the
   single root reference of the chain (adjusting their distance
   appropriately).  Some extra care needs to be taken for references with
   step 0.  In our example (the numbers indicate the distance of the

   a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*)
   b[10] --> (*) 1, b[10] (*)

4) The chains are combined together if possible.  If the corresponding
   elements of two chains are always combined together with the same
   operator, we remember just the result of this combination, instead
   of remembering the values separately.  We may need to perform
   reassociation to enable combining, for example

   e[i] + f[i+1] + e[i+1] + f[i]

   can be reassociated as

   (e[i] + f[i]) + (e[i+1] + f[i+1])

   and we can combine the chains for e and f into one chain.

5) For each root reference (end of the chain) R, let N be maximum distance
   of a reference reusing its value.  Variables R0 up to RN are created,
   together with phi nodes that transfer values from R1 .. RN to
   R0 .. R(N-1).
   Initial values are loaded to R0..R(N-1) (in case not all references
   must necessarily be accessed and they may trap, we may fail here;
   TODO sometimes, the loads could be guarded by a check for the number
   of iterations).  Values loaded/stored in roots are also copied to
   RN.  Other reads are replaced with the appropriate variable Ri.
   Everything is put to SSA form.

   As a small improvement, if R0 is dead after the root (i.e., all uses of
   the value with the maximum distance dominate the root), we can avoid
   creating RN and use R0 instead of it.

   In our example, we get (only the parts concerning a and b are shown):
   for (i = 0; i < 100; i++)
       f = phi (a[0], s);
       s = phi (a[1], f);
       x = phi (b[10], x);

       f = f + s;
       a[i+2] = f;
       x = x + i;
       b[10] = x;

6) Factor F for unrolling is determined as the smallest common multiple of
   (N + 1) for each root reference (N for references for that we avoided
   creating RN).  If F and the loop is small enough, loop is unrolled F
   times.  The stores to RN (R0) in the copies of the loop body are
   periodically replaced with R0, R1, ... (R1, R2, ...), so that they can
   be coalesced and the copies can be eliminated.

   TODO -- copy propagation and other optimizations may change the live
   ranges of the temporary registers and prevent them from being coalesced;
   this may increase the register pressure.

   In our case, F = 2 and the (main loop of the) result is

   for (i = 0; i < ...; i += 2)
       f = phi (a[0], f);
       s = phi (a[1], s);
       x = phi (b[10], x);

       f = f + s;
       a[i+2] = f;
       x = x + i;
       b[10] = x;

       s = s + f;
       a[i+3] = s;
       x = x + i;
       b[10] = x;

Apart from predictive commoning on Load-Load and Store-Load chains, we
also support Store-Store chains -- stores killed by other store can be
eliminated.  Given below example:

  for (i = 0; i < n; i++)
      a[i] = 1;
      a[i+2] = 2;

It can be replaced with:

  t0 = a[0];
  t1 = a[1];
  for (i = 0; i < n; i++)
      a[i] = 1;
      t2 = 2;
      t0 = t1;
      t1 = t2;
  a[n] = t0;
  a[n+1] = t1;

If the loop runs more than 1 iterations, it can be further simplified into:

  for (i = 0; i < n; i++)
      a[i] = 1;
  a[n] = 2;
  a[n+1] = 2;

The interesting part is this can be viewed either as general store motion
or general dead store elimination in either intra/inter-iterations way.

With trivial effort, we also support load inside Store-Store chains if the
load is dominated by a store statement in the same iteration of loop.  You
can see this as a restricted Store-Mixed-Load-Store chain.

TODO: For now, we don't support store-store chains in multi-exit loops.  We
force to not unroll in case of store-store chain even if other chains might
ask for unroll.

Predictive commoning can be generalized for arbitrary computations (not
just memory loads), and also nontrivial transfer functions (e.g., replacing
i * i with ii_last + 2 * i + 1), to generalize strength reduction.   
The maximum number of iterations between the considered memory

Referenced by pcom_worker::determine_roots_comp().

Typedef Documentation

◆ chain_p

typedef struct chain * chain_p
Chains of data references.   

◆ dref

typedef class dref_d * dref
Data references (or phi nodes that carry data reference values across
loop iterations).   

Enumeration Type Documentation

◆ chain_type

enum chain_type
Type of the chain of the references.   

◆ ref_step_type

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

Function Documentation

◆ add_ref_to_chain()

◆ base_names_in_chain_on()

static void base_names_in_chain_on ( class loop * loop,
tree name,
tree var )
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.   

References flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_STMT, gimple_bb(), NULL, PHI_RESULT, and replace_ssa_name_symbol().

Referenced by eliminate_temp_copies().

◆ chain_can_be_combined_p()

static bool chain_can_be_combined_p ( chain_p chain)
Returns true if CHAIN is suitable to be combined.   

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

Referenced by pcom_worker::try_combine_chains().

◆ component_of()

static unsigned component_of ( vec< unsigned > & fathers,
unsigned a )
Finds a root of tree given by FATHERS containing A, and performs path

References a.

Referenced by merge_comps(), and pcom_worker::split_data_refs_to_components().

◆ determine_unroll_factor()

static unsigned determine_unroll_factor ( const vec< chain_p > & chains)
Determines the unroll factor necessary to remove as many temporary variable
copies as possible.  CHAINS is the list of chains that will be

References a, chain::combined, CT_INVARIANT, CT_STORE_STORE, FOR_EACH_VEC_ELT, gcd(), chain::has_max_use_after, i, chain::length, chain::refs, and chain::type.

Referenced by pcom_worker::tree_predictive_commoning_loop().

◆ dump_chain()

◆ dump_chains()

void dump_chains ( FILE * file,
const vec< chain_p > & chains )
Dumps CHAINS to FILE.   

References dump_chain(), FOR_EACH_VEC_ELT, and i.

Referenced by pcom_worker::tree_predictive_commoning_loop().

◆ dump_component()

void dump_component ( FILE * file,
struct component * comp )
Dumps COMP to FILE.   

References a, comp, dump_dref(), FOR_EACH_VEC_ELT, i, and RS_INVARIANT.

Referenced by dump_components().

◆ dump_components()

void dump_components ( FILE * file,
struct component * comps )
Dumps COMPS to FILE.   

References comp, and dump_component().

Referenced by pcom_worker::tree_predictive_commoning_loop().

◆ dump_dref()

void dump_dref ( FILE * file,
dref ref )
Dumps data reference REF to FILE.   

References DR_IS_READ, DR_REF, print_decs(), print_generic_expr(), print_gimple_stmt(), and TDF_SLIM.

Referenced by dump_chain(), and dump_component().

◆ eliminate_temp_copies()

static void eliminate_temp_copies ( class loop * loop,
bitmap tmp_vars )
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.   

References base_names_in_chain_on(), bitmap_bit_p, DECL_UID, gcc_assert, gimple_bb(), gsi_end_p(), gsi_next(), gsi_start_phis(), loop::header, loop_latch_edge(), gphi_iterator::phi(), PHI_ARG_DEF, PHI_ARG_DEF_FROM_EDGE, PHI_RESULT, single_pred_p(), SSA_NAME_DEF_STMT, SSA_NAME_VAR, epcc_data::tmp_vars, and TREE_CODE.

Referenced by pcom_worker::tree_predictive_commoning_loop().

◆ execute_load_motion()

static void execute_load_motion ( class loop * loop,
chain_p chain,
bitmap tmp_vars )
Execute load motion for references in chain CHAIN.  Uids of the newly
created temporary variables are marked in TMP_VARS.   

References a, chain::combined, CT_INVARIANT, DR_IS_READ, DR_IS_WRITE, FOR_EACH_VEC_ELT, gcc_assert, get_chain_root(), i, initialize_root_vars_lm(), chain::inits, make_ssa_name(), chain::refs, replace_ref_with(), SSA_NAME_VAR, and chain::type.

Referenced by pcom_worker::execute_pred_commoning().

◆ execute_pred_commoning_cbck()

static void execute_pred_commoning_cbck ( class loop * loop,
void * data )

◆ finalize_eliminated_stores()

static void finalize_eliminated_stores ( class loop * loop,
chain_p chain )
Generates stores for CHAIN's eliminated stores in LOOP's last
(CHAIN->length - 1) iterations.   

References chain::fini_seq, chain::finis, gimple_build_assign(), gimple_seq_add_stmt_without_update(), gsi_insert_seq_on_edge_immediate(), i, chain::length, NULL, single_exit(), and chain::vars.

Referenced by pcom_worker::execute_pred_commoning_chain().

◆ get_chain_last_write_at()

static dref get_chain_last_write_at ( chain_p chain,
unsigned distance )
Given CHAIN, returns the last write ref at DISTANCE, or NULL if it doesn't

References DR_IS_WRITE, i, NULL, and chain::refs.

Referenced by initialize_root_vars_store_elim_1(), initialize_root_vars_store_elim_2(), and is_inv_store_elimination_chain().

◆ get_chain_last_write_before_load()

static dref get_chain_last_write_before_load ( chain_p chain,
unsigned load_idx )
Given CHAIN, returns the last write ref with the same distance before load
at index LOAD_IDX, or NULL if it doesn't exist.   

References DR_IS_WRITE, gcc_assert, i, NULL, chain::refs, and refs.

Referenced by pcom_worker::execute_pred_commoning_chain().

◆ get_chain_root()

◆ get_init_expr()

static tree get_init_expr ( chain_p chain,
unsigned index )
Get the initialization expression for the INDEX-th temporary variable
of CHAIN.   

References chain::ch1, chain::ch2, CT_COMBINATION, fold_build2, get_init_expr(), chain::inits, chain::op, chain::rslt_type, and chain::type.

Referenced by get_init_expr(), initialize_root_vars(), and initialize_root_vars_store_elim_2().

◆ initialize_root_vars()

static void initialize_root_vars ( class loop * loop,
chain_p chain,
bitmap tmp_vars )

◆ initialize_root_vars_lm()

static void initialize_root_vars_lm ( class loop * loop,
dref root,
bool written,
vec< tree > * vars,
const 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)

References add_phi_arg(), create_phi_node(), DR_REF, FOR_EACH_VEC_ELT, force_gimple_operand(), gimple_build_assign(), gsi_insert_on_edge_immediate(), gsi_insert_seq_on_edge_immediate(), loop::header, i, loop_latch_edge(), loop_preheader_edge(), make_ssa_name(), component::next, NULL_TREE, predcom_tmp_var(), and UNKNOWN_LOCATION.

Referenced by execute_load_motion().

◆ initialize_root_vars_store_elim_1()

static void initialize_root_vars_store_elim_1 ( chain_p chain)
Creates root variables for store elimination CHAIN in which stores for
elimination only store loop invariant values.  In this case, we neither
need to load root variables before loop nor propagate it with PHI nodes.   

References a, get_chain_last_write_at(), gimple_assign_rhs1(), i, chain::length, NULL, NULL_TREE, and chain::vars.

Referenced by pcom_worker::execute_pred_commoning_chain().

◆ initialize_root_vars_store_elim_2()

static void initialize_root_vars_store_elim_2 ( class loop * loop,
chain_p chain,
bitmap tmp_vars )

◆ insert_init_seqs()

static void insert_init_seqs ( class loop * loop,
vec< chain_p > & chains )
Insert all initializing gimple stmts into LOOP's entry edge.   

References gsi_insert_seq_on_edge_immediate(), i, loop_preheader_edge(), and NULL.

Referenced by pcom_worker::tree_predictive_commoning_loop().

◆ insert_looparound_copy()

static void insert_looparound_copy ( chain_p chain,
dref ref,
gphi * phi )
Adds a reference for the looparound copy of REF in PHI to CHAIN.   

References FOR_EACH_VEC_ELT, chain::has_max_use_after, i, chain::length, data_reference::ref, and chain::refs.

Referenced by pcom_worker::add_looparound_copies().

◆ is_inv_store_elimination_chain()

static bool is_inv_store_elimination_chain ( class loop * loop,
chain_p chain )
For inter-iteration store elimination CHAIN in LOOP, returns true if
all stores to be eliminated store loop invariant values into memory.
In this case, we can use these invariant values directly after LOOP.   

References a, CONSTANT_CLASS_P, CT_STORE_STORE, flow_bb_inside_loop_p(), gcc_assert, get_chain_last_write_at(), gimple_assign_rhs1(), gimple_assign_single_p(), gimple_bb(), gimple_nop_p(), chain::has_max_use_after, i, chain::length, wi::leu_p(), NULL, number_of_latch_executions(), SSA_NAME_DEF_STMT, wi::to_wide(), TREE_CLOBBER_P, TREE_CODE, and chain::type.

Referenced by prepare_initializers_chain_store_elim().

◆ last_always_executed_block()

static basic_block last_always_executed_block ( class loop * loop)
Returns the last basic block in LOOP for that we are sure that
it is executed whenever the loop is entered.   

References CDI_DOMINATORS, FOR_EACH_VEC_ELT, get_loop_exit_edges(), i, last, loop::latch, and nearest_common_dominator().

Referenced by pcom_worker::split_data_refs_to_components().

◆ make_invariant_chain()

static chain_p make_invariant_chain ( struct component * comp)
Returns the chain for invariant component COMP.   

References chain::all_always_accessed, comp, chain::finis, FOR_EACH_VEC_ELT, i, chain::inits, chain::refs, and vNULL.

Referenced by pcom_worker::determine_roots_comp().

◆ make_pass_predcom()

gimple_opt_pass * make_pass_predcom ( gcc::context * ctxt)

◆ make_rooted_chain()

static chain_p make_rooted_chain ( dref ref,
enum chain_type type )
Make a new chain of type TYPE rooted at REF.   

References chain::all_always_accessed, chain::finis, chain::inits, chain::refs, and vNULL.

Referenced by pcom_worker::determine_roots_comp().

◆ may_reassociate_p()

static bool may_reassociate_p ( tree type,
enum tree_code code )
Returns true if we may perform reassociation for operation CODE in TYPE.   

References associative_tree_code(), commutative_tree_code(), and FLOAT_TYPE_P.

Referenced by pcom_worker::find_associative_operation_root().

◆ merge_comps()

static void merge_comps ( vec< unsigned > & fathers,
vec< unsigned > & sizes,
unsigned a,
unsigned b )
Join operation for DFU.  FATHERS gives the tree, SIZES are sizes of the
components, A and B are components to merge.   

References a, b, and component_of().

Referenced by pcom_worker::split_data_refs_to_components().

◆ name_for_ref()

static tree name_for_ref ( dref ref)
Returns the ssa name that contains the value of REF, or NULL_TREE if there
is no such name.   

References DR_IS_READ, gimple_assign_lhs(), gimple_assign_rhs1(), is_gimple_assign(), NULL_TREE, PHI_RESULT, and TREE_CODE.

Referenced by pcom_worker::combinable_refs_p(), and pcom_worker::stmt_combining_refs().

◆ nontrivial_chain_p()

static bool nontrivial_chain_p ( chain_p chain)
Returns true if CHAIN is not trivial.   

References NULL, and chain::refs.

Referenced by pcom_worker::determine_roots_comp().

◆ order_drefs()

static int order_drefs ( const void * a,
const void * b )
Compares two drefs A and B by their offset and position.  Callback for

References a, b, and wi::cmps().

Referenced by pcom_worker::determine_roots_comp().

◆ order_drefs_by_pos()

static int order_drefs_by_pos ( const void * a,
const void * b )
Compares two drefs A and B by their position.  Callback for qsort.   

References a, and b.

Referenced by pcom_worker::try_combine_chains().

◆ pcom_stmt_dominates_stmt_p()

static bool pcom_stmt_dominates_stmt_p ( gimple * s1,
gimple * s2 )
Returns true if statement S1 dominates statement S2.   

References CDI_DOMINATORS, dominated_by_p(), gimple_bb(), and gimple_uid().

Referenced by pcom_worker::try_combine_chains().

◆ predcom_tmp_var()

static tree predcom_tmp_var ( tree ref,
unsigned i,
bitmap tmp_vars )
Returns a new temporary variable used for the I-th variable carrying
value of REF.  The variable's uid is marked in TMP_VARS.   

References bitmap_set_bit, create_tmp_reg(), DECL_UID, get_lsm_tmp_name(), i, and TREE_TYPE.

Referenced by initialize_root_vars(), initialize_root_vars_lm(), and initialize_root_vars_store_elim_2().

◆ prepare_initializers_chain_store_elim()

static bool prepare_initializers_chain_store_elim ( class loop * loop,
chain_p chain )
Prepare initializers for store elimination CHAIN in LOOP.  Returns false
if this is impossible because one of these initializers may trap, true

References chain::all_always_accessed, CT_STORE_STORE, get_chain_root(), gimple_seq_add_seq_without_update(), i, chain::init_seq, chain::inits, chain::inv_store_elimination, is_inv_store_elimination_chain(), chain::length, NULL, data_reference::ref, ref_at_iteration(), chain::refs, and chain::type.

Referenced by pcom_worker::prepare_initializers_chain().

◆ ref_at_iteration()

◆ release_components()

static void release_components ( struct component * comps)
Frees list of components COMPS.   

References component::next.

Referenced by pcom_worker::tree_predictive_commoning_loop().

◆ remove_name_from_operation()

static void remove_name_from_operation ( gimple * stmt,
tree op )
Remove OP from the operation on rhs of STMT, and replace STMT with
an assignment of the remaining operand.   

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

Referenced by pcom_worker::reassociate_to_the_same_stmt().

◆ replace_names_by_phis()

static void replace_names_by_phis ( vec< chain_p > chains)
For each reference in CHAINS, if name_defined_by_phi is not
NULL, use it to set the stmt field.   

References a, FOR_EACH_VEC_ELT, gcc_assert, i, NULL, NULL_TREE, chain::refs, and SSA_NAME_DEF_STMT.

Referenced by execute_pred_commoning_cbck().

◆ replace_phis_by_defined_names()

static void replace_phis_by_defined_names ( vec< chain_p > & chains)
For each reference in CHAINS, if its defining statement is
phi node, record the ssa name that is defined by it.   

References a, FOR_EACH_VEC_ELT, i, NULL, PHI_RESULT, and chain::refs.

Referenced by pcom_worker::tree_predictive_commoning_loop().

◆ replace_ref_with()

static void replace_ref_with ( gimple * stmt,
tree new_tree,
bool set,
bool in_lhs )
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.   

References cfun, gcc_assert, get_or_create_ssa_default_def(), gimple_assign_copy_p(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_set_rhs_from_tree(), gimple_assign_single_p(), gimple_bb(), gimple_build_assign(), gsi_after_labels(), gsi_for_stmt(), gsi_insert_after(), gsi_insert_before(), GSI_NEW_STMT, gsi_stmt(), is_gimple_assign(), PHI_RESULT, remove_phi_node(), SSA_NAME_VAR, TREE_CLOBBER_P, TREE_CODE, unshare_expr(), and update_stmt().

Referenced by execute_load_motion(), and pcom_worker::execute_pred_commoning_chain().

◆ run_tree_predictive_commoning()

static unsigned run_tree_predictive_commoning ( struct function * fun,
bool allow_unroll_p )
Predictive commoning Pass.   

References number_of_loops(), and tree_predictive_commoning().

◆ suitable_reference_p()

static bool suitable_reference_p ( struct data_reference * a,
enum ref_step_type * ref_step )
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.   

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

Referenced by pcom_worker::split_data_refs_to_components(), and pcom_worker::suitable_component_p().

◆ tree_predictive_commoning()

◆ update_pos_for_combined_chains()

static void update_pos_for_combined_chains ( chain_p root)
Recursively update position information of all offspring chains to ROOT
chain's position information.   

References chain::ch1, chain::ch2, CT_COMBINATION, chain::refs, chain::type, and update_pos_for_combined_chains().

Referenced by pcom_worker::try_combine_chains(), and update_pos_for_combined_chains().