#include "config.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "tree.h"#include "tm_p.h"#include "cfgloop.h"#include "gimple.h"#include "gimple-ssa.h"#include "tree-phinodes.h"#include "ssa-iterators.h"#include "tree-ssanames.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 "ggc.h"#include "tree-data-ref.h"#include "tree-scalar-evolution.h"#include "tree-chrec.h"#include "params.h"#include "gimple-pretty-print.h"#include "tree-pass.h"#include "tree-affine.h"#include "tree-inline.h"
Data Structures | |
| struct | dref_d |
| struct | chain |
| struct | component |
| struct | epcc_data |
Macros | |
| #define | MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8) |
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 } |
Variables | |
| static bitmap | looparound_phis |
| static struct pointer_map_t * | name_expansions |
Macro Definition Documentation
| #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8) |
Predictive commoning. Copyright (C) 2005-2013 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; }
TODO – stores killing other stores can be taken into account, e.g., for (i = 0; i < n; i++) { a[i] = 1; a[i+2] = 2; }
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;
The interesting part is that this would generalize store motion; still, since sm is performed elsewhere, it does not seem that important.
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.
Typedef Documentation
Data references (or phi nodes that carry data reference values across loop iterations).
Enumeration Type Documentation
| enum chain_type |
| enum ref_step_type |
Function Documentation
|
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 |
Adds REF to the chain CHAIN.
|
static |
Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET.
|
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 |
Returns true if CHAIN is suitable to be combined.
|
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 |
Tries to combine chains CH1 and CH2 together. If this succeeds, the description of the new chain is returned, otherwise we return NULL.
|
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, tree_could_throw_p(), TREE_THIS_VOLATILE, and TREE_TYPE.
Referenced by release_component().
|
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, FOR_EACH_VEC_ELT, last_always_executed_block(), NULL, and suitable_reference_p().
|
static |
Find roots of the values and determine distances in components COMPS, and separates the references to CHAINS. LOOP is the current loop.
|
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 |
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 BREAK_FROM_IMM_USE_STMT, flow_bb_inside_loop_p(), FOR_EACH_IMM_USE_STMT, NULL, PHI_RESULT, and replace_ssa_name_symbol().
| void dump_chain | ( | FILE * | , |
| chain_p | |||
| ) |
Dumps CHAIN to FILE.
| void dump_chain | ( | ) |
| void dump_chains | ( | ) |
References FOR_EACH_VEC_ELT, NULL, 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 | ( | ) |
| void dump_dref | ( | FILE * | , |
| dref | |||
| ) |
Dumps data reference REF to FILE.
| void dump_dref | ( | ) |
References CT_COMBINATION, CT_INVARIANT, CT_LOAD, CT_STORE_LOAD, and gcc_unreachable.
|
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(), gcc_assert, gimple_assign_lhs(), gimple_assign_rhs_code(), and TREE_CODE.
|
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 |
Perform the predictive commoning optimization for CHAINS. Uids of the newly created temporary variables are marked in TMP_VARS.
|
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 |
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 FOR_EACH_VEC_ELT, gcc_assert, dref_d::name_defined_by_phi, NULL, NULL_TREE, chain::refs, SSA_NAME_DEF_STMT, and dref_d::stmt.
|
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 |
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 |
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 |
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 |
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(), gcc_assert, gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs_code(), name_for_ref(), NULL_TREE, and TREE_TYPE.
Referenced by eliminate_temp_copies().
|
static |
|
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 |
Get the initialization expression for the INDEX-th temporary variable of CHAIN.
|
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(), NULL, and SSA_NAME_VAR.
Referenced by single_nonlooparound_use().
|
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 |
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, FOR_EACH_IMM_USE_FAST, is_gimple_debug(), NULL, PHI_RESULT, SSA_NAME_VERSION, and USE_STMT.
|
static |
Adds a reference for the looparound copy of REF in PHI to CHAIN.
|
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 |
Returns the chain for invariant component COMP.
References DR_BASE_ADDRESS, DR_INIT, DR_OFFSET, DR_STEP, gcc_assert, integer_zerop(), and operand_equal_p().
| gimple_opt_pass* make_pass_predcom | ( | ) |
|
static |
Make a new chain rooted at REF.
|
static |
Returns true if we may perform reassociation for operation CODE in TYPE.
References gcc_assert, gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_set_rhs_from_tree(), gsi_for_stmt(), is_gimple_assign(), and si.
|
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(), tree_to_double_int(), and TREE_TYPE.
|
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 |
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 |
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 |
Prepare initializers for CHAINS in LOOP, and free chains that cannot be used because the initializers might trap.
|
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 |
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 |
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 |
Frees a chain CHAIN.
References component::next, and release_component().
|
static |
Frees CHAINS.
|
static |
Frees a component COMP.
References component_of().
Referenced by release_chain(), and suitable_component_p().
|
static |
Frees list of components COMPS.
|
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, NULL, NULL_TREE, chain::refs, and swap().
|
static |
Remove statement STMT, as well as the chain of assignments in that it is used.
|
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 |
For each reference in CHAINS, if its defining statement is phi node, record the ssa name that is defined by it.
|
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 |
Predictive commoning Pass.
|
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.
|
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 |
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 |
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, FOR_EACH_VEC_ELT, component::next, component::refs, and release_component().
|
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 |
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 |
Try to combine the CHAINS.
References dump_file, dump_flags, free_data_refs(), and free_dependence_relations().
|
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
|
static |
Bitmap of ssa names defined by looparound phi nodes covered by chains.
|
static |
Cache used by tree_to_aff_combination_expand.
