#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"
Data Structures | |
| class | dref_d |
| struct | chain |
| struct | component |
| class | pcom_worker |
| struct | epcc_data |
Macros | |
| #define | MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8) |
Typedefs | |
| typedef class dref_d * | dref |
| typedef struct chain * | chain_p |
Enumerations | |
| enum | chain_type { CT_INVARIANT , CT_LOAD , CT_STORE_LOAD , CT_STORE_STORE , CT_COMBINATION } |
| enum | ref_step_type { RS_INVARIANT , RS_NONZERO , RS_ANY } |
Macro Definition Documentation
◆ MAX_DISTANCE
| #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 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/>.
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
reuse),
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 references.
Referenced by pcom_worker::determine_roots_comp().
Typedef Documentation
◆ chain_p
◆ dref
Data references (or phi nodes that carry data reference values across loop iterations).
Enumeration Type Documentation
◆ chain_type
◆ ref_step_type
Function Documentation
◆ add_ref_to_chain()
Adds REF to the chain CHAIN.
References chain::all_always_accessed, CT_STORE_STORE, DR_IS_WRITE, wi::fits_uhwi_p(), gcc_assert, get_chain_root(), ggc_alloc(), chain::has_max_use_after, chain::length, wi::les_p(), chain::refs, and chain::type.
Referenced by pcom_worker::determine_roots_comp().
◆ 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.
References flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_STMT, ggc_alloc(), gimple_bb(), NULL, PHI_RESULT, and replace_ssa_name_symbol().
Referenced by eliminate_temp_copies().
◆ chain_can_be_combined_p()
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()
Finds a root of tree given by FATHERS containing A, and performs path shortening.
References a, and ggc_alloc().
Referenced by merge_comps(), and pcom_worker::split_data_refs_to_components().
◆ 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 optimized.
References a, chain::combined, CT_INVARIANT, CT_STORE_STORE, FOR_EACH_VEC_ELT, gcd(), ggc_alloc(), chain::has_max_use_after, i, chain::length, chain::refs, and chain::type.
Referenced by pcom_worker::tree_predictive_commoning_loop().
◆ dump_chain()
Dumps CHAIN to FILE.
References a, chain::ch1, chain::ch2, chain::combined, CT_COMBINATION, CT_INVARIANT, CT_LOAD, CT_STORE_LOAD, CT_STORE_STORE, dump_dref(), FOR_EACH_VEC_ELT, gcc_unreachable, ggc_alloc(), chain::has_max_use_after, i, chain::inits, chain::length, chain::op, op_symbol_code(), print_generic_expr(), chain::refs, chain::rslt_type, TDF_SLIM, chain::type, and chain::vars.
Referenced by dump_chains().
◆ dump_chains()
Dumps CHAINS to FILE.
References dump_chain(), FOR_EACH_VEC_ELT, and i.
Referenced by pcom_worker::tree_predictive_commoning_loop().
◆ dump_component()
Dumps COMP to FILE.
References a, comp, dump_dref(), FOR_EACH_VEC_ELT, ggc_alloc(), i, and RS_INVARIANT.
Referenced by dump_components().
◆ dump_components()
Dumps COMPS to FILE.
References comp, dump_component(), and ggc_alloc().
Referenced by pcom_worker::tree_predictive_commoning_loop().
◆ dump_dref()
Dumps data reference REF to FILE.
References DR_IS_READ, DR_REF, ggc_alloc(), print_decs(), print_generic_expr(), print_gimple_stmt(), and TDF_SLIM.
Referenced by dump_chain(), and dump_component().
◆ 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.
References base_names_in_chain_on(), bitmap_bit_p, DECL_UID, gcc_assert, ggc_alloc(), 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()
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(), ggc_alloc(), 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()
References pcom_worker::execute_pred_commoning(), ggc_alloc(), replace_names_by_phis(), and epcc_data::worker.
Referenced by pcom_worker::tree_predictive_commoning_loop().
◆ finalize_eliminated_stores()
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()
Given CHAIN, returns the last write ref at DISTANCE, or NULL if it doesn't exist.
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()
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, ggc_alloc(), i, NULL, chain::refs, and refs.
Referenced by pcom_worker::execute_pred_commoning_chain().
◆ get_chain_root()
Returns root of the CHAIN.
References chain::refs.
Referenced by pcom_worker::add_looparound_copies(), add_ref_to_chain(), execute_load_motion(), pcom_worker::execute_pred_commoning_chain(), initialize_root_vars(), initialize_root_vars_store_elim_2(), pcom_worker::prepare_finalizers_chain(), pcom_worker::prepare_initializers_chain(), prepare_initializers_chain_store_elim(), and pcom_worker::try_combine_chains().
◆ get_init_expr()
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()
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.
References add_phi_arg(), create_phi_node(), CT_COMBINATION, DR_REF, FOR_EACH_VEC_ELT, force_gimple_operand(), gcc_assert, get_chain_root(), get_init_expr(), ggc_alloc(), gimple_assign_lhs(), gsi_insert_seq_on_edge_immediate(), chain::has_max_use_after, loop::header, i, chain::length, loop_latch_edge(), loop_preheader_edge(), make_ssa_name(), component::next, NULL_TREE, predcom_tmp_var(), chain::type, UNKNOWN_LOCATION, and chain::vars.
Referenced by pcom_worker::execute_pred_commoning_chain().
◆ initialize_root_vars_lm()
|
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.
References add_phi_arg(), create_phi_node(), DR_REF, FOR_EACH_VEC_ELT, force_gimple_operand(), ggc_alloc(), 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()
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 |
Creates root variables for store elimination CHAIN in which stores for elimination store loop variant values. In this case, we may need to load root variables before LOOP and propagate it with PHI nodes. Uids of the newly created root variables are marked in TMP_VARS.
References a, add_phi_arg(), cfun, copy_ssa_name(), create_phi_node(), DR_REF, FOR_EACH_VEC_ELT, force_gimple_operand(), get_chain_last_write_at(), get_chain_root(), get_init_expr(), get_or_create_ssa_default_def(), ggc_alloc(), gimple_assign_rhs1(), gimple_assign_set_rhs1(), gimple_build_assign(), gsi_for_stmt(), gsi_insert_after(), gsi_insert_seq_on_edge_immediate(), GSI_NEW_STMT, loop::header, i, last, chain::length, loop_latch_edge(), loop_preheader_edge(), make_ssa_name(), component::next, NULL_TREE, predcom_tmp_var(), chain::refs, SSA_NAME_VAR, TREE_CLOBBER_P, UNKNOWN_LOCATION, and chain::vars.
Referenced by pcom_worker::execute_pred_commoning_chain().
◆ insert_init_seqs()
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()
Adds a reference for the looparound copy of REF in PHI to CHAIN.
References FOR_EACH_VEC_ELT, ggc_alloc(), 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()
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(), ggc_alloc(), 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 |
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(), ggc_alloc(), i, last, loop::latch, and nearest_common_dominator().
Referenced by pcom_worker::split_data_refs_to_components().
◆ make_invariant_chain()
Returns the chain for invariant component COMP.
References chain::all_always_accessed, comp, chain::finis, FOR_EACH_VEC_ELT, ggc_alloc(), 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 | ) |
References ggc_alloc().
◆ make_rooted_chain()
|
static |
Make a new chain of type TYPE rooted at REF.
References chain::all_always_accessed, chain::finis, ggc_alloc(), chain::inits, chain::refs, and vNULL.
Referenced by pcom_worker::determine_roots_comp().
◆ may_reassociate_p()
Returns true if we may perform reassociation for operation CODE in TYPE.
References associative_tree_code(), commutative_tree_code(), FLOAT_TYPE_P, and ggc_alloc().
Referenced by pcom_worker::find_associative_operation_root().
◆ 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 a, b, component_of(), and ggc_alloc().
Referenced by pcom_worker::split_data_refs_to_components().
◆ name_for_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()
Returns true if CHAIN is not trivial.
References NULL, and chain::refs.
Referenced by pcom_worker::determine_roots_comp().
◆ order_drefs()
Compares two drefs A and B by their offset and position. Callback for qsort.
References a, b, wi::cmps(), and ggc_alloc().
Referenced by pcom_worker::determine_roots_comp().
◆ order_drefs_by_pos()
Compares two drefs A and B by their position. Callback for qsort.
References a, b, and ggc_alloc().
Referenced by pcom_worker::try_combine_chains().
◆ pcom_stmt_dominates_stmt_p()
Returns true if statement S1 dominates statement S2.
References CDI_DOMINATORS, dominated_by_p(), ggc_alloc(), gimple_bb(), and gimple_uid().
Referenced by pcom_worker::try_combine_chains().
◆ 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.
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()
Prepare initializers for store elimination CHAIN in LOOP. Returns false if this is impossible because one of these initializers may trap, true otherwise.
References chain::all_always_accessed, CT_STORE_STORE, get_chain_root(), ggc_alloc(), 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()
|
static |
Returns a memory reference to DR in the (NITERS + ITER)-th iteration of the loop it was analyzed in. Append init stmts to STMTS.
References bitsize_zero_node, build2(), build3(), build_aligned_type(), build_zero_cst(), component_ref_field_offset(), DECL_BIT_FIELD, DECL_FIELD_BIT_OFFSET, DECL_SIZE, DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_REF, DR_STEP, fold_build_pointer_plus, fold_convert, force_gimple_operand_1(), get_object_alignment(), ggc_alloc(), integer_zerop(), is_gimple_mem_ref_addr(), NULL_TREE, offset, reference_alias_ptr_type(), size_binop, ssize_int, ssizetype, TREE_CODE, tree_fits_uhwi_p(), TREE_OPERAND, tree_to_uhwi(), TREE_TYPE, and unshare_expr().
Referenced by pcom_worker::prepare_finalizers_chain(), pcom_worker::prepare_initializers_chain(), and prepare_initializers_chain_store_elim().
◆ release_components()
Frees list of components COMPS.
References ggc_alloc(), and component::next.
Referenced by pcom_worker::tree_predictive_commoning_loop().
◆ remove_name_from_operation()
Remove OP from the operation on rhs of STMT, and replace STMT with an assignment of the remaining operand.
References gcc_assert, ggc_alloc(), 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()
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, ggc_alloc(), i, NULL, NULL_TREE, chain::refs, and SSA_NAME_DEF_STMT.
Referenced by execute_pred_commoning_cbck().
◆ 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.
References a, FOR_EACH_VEC_ELT, ggc_alloc(), i, NULL, PHI_RESULT, and chain::refs.
Referenced by pcom_worker::tree_predictive_commoning_loop().
◆ 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.
References cfun, gcc_assert, get_or_create_ssa_default_def(), ggc_alloc(), 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()
Predictive commoning Pass.
References ggc_alloc(), number_of_loops(), and tree_predictive_commoning().
◆ 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.
References a, DR_REF, DR_STEP, ggc_alloc(), 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()
Runs predictive commoning.
References cfun, changed, free_original_copy_tables(), ggc_alloc(), initialize_original_copy_tables(), LI_ONLY_INNERMOST, NULL, optimize_loop_for_speed_p(), rewrite_into_loop_closed_ssa(), scev_reset(), TODO_cleanup_cfg, TODO_update_ssa, and TODO_update_ssa_only_virtuals.
Referenced by run_tree_predictive_commoning().
◆ update_pos_for_combined_chains()
Recursively update position information of all offspring chains to ROOT chain's position information.
References chain::ch1, chain::ch2, CT_COMBINATION, ggc_alloc(), chain::refs, chain::type, and update_pos_for_combined_chains().
Referenced by pcom_worker::try_combine_chains(), and update_pos_for_combined_chains().
