#include "config.h"#include "system.h"#include "coretypes.h"#include "tm.h"#include "tree.h"#include "tm_p.h"#include "basic-block.h"#include "gimple-pretty-print.h"#include "gimple.h"#include "gimple-ssa.h"#include "cgraph.h"#include "tree-cfg.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-dfa.h"#include "tree-ssa.h"#include "cfgloop.h"#include "tree-pass.h"#include "ggc.h"#include "insn-config.h"#include "pointer-set.h"#include "hash-table.h"#include "tree-chrec.h"#include "tree-scalar-evolution.h"#include "params.h"#include "langhooks.h"#include "tree-affine.h"#include "target.h"#include "tree-inline.h"#include "tree-ssa-propagate.h"#include "expmed.h"#include "tree-ssa-address.h"#include "expr.h"#include "recog.h"
Data Structures | |
| struct | iv |
| struct | version_info |
| struct | comp_cost |
| struct | cost_pair |
| struct | iv_use |
| struct | iv_cand |
| struct | iv_inv_expr_ent |
| struct | iv_inv_expr_hasher |
| struct | ivopts_data |
| struct | iv_ca |
| struct | iv_ca_delta |
| struct | ifs_ivopts_data |
| struct | address_cost_data_s |
Macros | |
| #define | INFTY 10000000 |
| #define | AVG_LOOP_NITER(LOOP) 5 |
| #define | CONSIDER_ALL_CANDIDATES_BOUND ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND)) |
| #define | MAX_CONSIDERED_USES ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES)) |
| #define | ALWAYS_PRUNE_CAND_SET_BOUND ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND)) |
| #define | MAX_RATIO 128 |
Typedefs | |
| typedef struct iv_use * | iv_use_p |
| typedef struct iv_cand * | iv_cand_p |
| typedef struct address_cost_data_s * | address_cost_data |
Enumerations | |
| enum | use_type { USE_NONLINEAR_EXPR, USE_ADDRESS, USE_COMPARE } |
| enum | iv_position { IP_NORMAL, IP_END, IP_BEFORE_USE, IP_AFTER_USE, IP_ORIGINAL } |
Variables | |
| static const comp_cost | no_cost = {0, 0} |
| static const comp_cost | infinite_cost = {INFTY, INFTY} |
| static vec< tree > | decl_rtl_to_reset |
| static struct ivopts_data * | fd_ivopts_data |
Macro Definition Documentation
| #define ALWAYS_PRUNE_CAND_SET_BOUND ((unsigned) PARAM_VALUE (PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND)) |
If there are at most this number of ivs in the set, try removing unnecessary ivs from the set always.
Referenced by iv_ca_extend().
| #define AVG_LOOP_NITER | ( | LOOP | ) | 5 |
| #define CONSIDER_ALL_CANDIDATES_BOUND ((unsigned) PARAM_VALUE (PARAM_IV_CONSIDER_ALL_CANDIDATES_BOUND)) |
Bound on number of candidates below that all candidates are considered.
| #define INFTY 10000000 |
Induction variable optimizations. Copyright (C) 2003-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 pass tries to find the optimal set of induction variables for the loop. It optimizes just the basic linear induction variables (although adding support for other types should not be too hard). It includes the optimizations commonly known as strength reduction, induction variable coalescing and induction variable elimination. It does it in the following steps:
1) The interesting uses of induction variables are found. This includes
– uses of induction variables in non-linear expressions – addresses of arrays – comparisons of induction variables
2) Candidates for the induction variables are found. This includes
– old induction variables – the variables defined by expressions derived from the "interesting uses" above
3) The optimal (w.r. to a cost function) set of variables is chosen. The cost function assigns a cost to sets of induction variables and consists of three parts:
– The use costs. Each of the interesting uses chooses the best induction variable in the set and adds its cost to the sum. The cost reflects the time spent on modifying the induction variables value to be usable for the given purpose (adding base and offset for arrays, etc.). – The variable costs. Each of the variables has a cost assigned that reflects the costs associated with incrementing the value of the variable. The original variables are somewhat preferred. – The set cost. Depending on the size of the set, extra cost may be added to reflect register pressure.
All the costs are defined in a machine-specific way, using the target hooks and machine descriptions to determine them.
4) The trees are transformed to use the new variables, the dead code is removed.
All of this is done loop by loop. Doing it globally is theoretically possible, it might give a better performance and it might enable us to decide costs more precisely, but getting all the interactions right would be complicated. FIXME: Expressions are expanded to RTL in this pass to determine the cost of different addressing modes. This should be moved to a TBD interface between the GIMPLE and RTL worlds. The infinite cost.
| #define MAX_CONSIDERED_USES ((unsigned) PARAM_VALUE (PARAM_IV_MAX_CONSIDERED_USES)) |
If there are more iv occurrences, we just give up (it is quite unlikely that optimizing such a loop would help, and it would take ages).
Referenced by rewrite_use_compare().
| #define MAX_RATIO 128 |
Referenced by determine_common_wider_type().
Typedef Documentation
| typedef struct address_cost_data_s * address_cost_data |
Returns cost of address in shape symbol + var + OFFSET + RATIO * index. If SYMBOL_PRESENT is false, symbol is omitted. If VAR_PRESENT is false, variable is omitted. Compute the cost for a memory reference that accesses a memory location of mode MEM_MODE in address space AS.
MAY_AUTOINC is set to true if the autoincrement (increasing index by size of MEM_MODE / RATIO) is available. To make this determination, we look at the size of the increment to be made, which is given in CSTEP. CSTEP may be zero if the step is unknown. STMT_AFTER_INC is true iff the statement we're looking at is after the increment of the original biv.
TODO – there must be some better way. This all is quite crude.
Enumeration Type Documentation
| enum iv_position |
| enum use_type |
Function Documentation
|
static |
Returns true if EXP is a ssa name that occurs in an abnormal phi node.
|
static |
If possible, adds autoincrement candidates BASE + STEP * i based on use USE. Important field is set to IMPORTANT.
If we insert the increment in any position other than the standard ones, we must ensure that it is incremented once per iteration. It must not be in an inner nested loop, or one side of an if statement.
|
static |
Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and position to POS. If USE is not NULL, the candidate is set as related to it. The candidate computation is scheduled on all available positions.
|
staticread |
Adds a candidate BASE + STEP * i. Important field is set to IMPORTANT and position to POS. If USE is not NULL, the candidate is set as related to it. If both BASE and STEP are NULL, we add a pseudocandidate for the replacement of the final value of the iv by a direct computation.
For non-original variables, make sure their values are computed in a type that does not invoke undefined behavior on overflows (since in general, we cannot prove that these induction variables are non-wrapping).
|
static |
|
static |
Adds candidates based on the uses.
Just add the ivs based on the value of the iv used here.
|
static |
Adds candidates based on the value of the induction variable IV and USE.
The same, but with initial value zero. Make such variable important, since it is generic enough so that possibly many uses may be based on it.
Third, try removing the constant offset. Make sure to even add a candidate for &a[0] vs. (T *)&a.
References comp_cost::complexity, and comp_cost::cost.
|
static |
Adds candidates bases on the old induction variable IV.
The same, but with initial value zero.
Additionally record the possibility of leaving the original iv
untouched.
Referenced by allow_ip_end_pos_p().
|
static |
Adds candidates based on the old induction variables.
|
static |
Adds standard iv candidates.
The same for a double-integer type if it is still fast enough.
The same for a double-integer type if it is still fast enough.
|
static |
Performs a peephole optimization to reorder the iv update statement with a mem ref to enable instruction combining in later phases. The mem ref uses the iv value before the update, so the reordering transformation requires adjustment of the offset. CAND is the selected IV_CAND.
Example:
t = MEM_REF (base, iv1, 8, 16); // base, index, stride, offset iv2 = iv1 + 1;
if (t < val) (1) goto L; goto Head;
directly propagating t over to (1) will introduce overlapping live range thus increase register pressure. This peephole transform it into:
iv2 = iv1 + 1; t = MEM_REF (base, iv2, 8, 8); if (t < val) goto L; goto Head;
Only handle conditional statement for now.
References free_tree_niter_desc(), ivopts_data::niters, NULL, pointer_map_destroy(), and pointer_map_traverse().
|
static |
Adjust the cost COST for being in loop setup rather than loop body. If we're optimizing for space, the loop setup overhead is constant; if we're optimizing for speed, amortize it over the per-iteration cost.
|
staticread |
Allocates an induction variable with given initial value BASE and step STEP for loop LOOP.
References contains_abnormal_ssa_name_p(), determine_biv_step(), expand_simple_operations(), fold_convert, gsi_stmt(), loop_preheader_edge(), PHI_ARG_DEF_FROM_EDGE, PHI_RESULT, SSA_NAME_OCCURS_IN_ABNORMAL_PHI, and TREE_TYPE.
|
static |
Allocates the data structure mapping the (use, candidate) pairs to costs. If consider_all_candidates is true, we use a two-dimensional array, otherwise we allocate a simple list to every use.
Round up to the power of two, so that moduling by it is fast.
References cost_pair::cost, NEXT_INSN, SET_SRC, set_src_cost(), and single_set.
|
static |
Returns true if incrementing the induction variable at the end of the LOOP is allowed.
The purpose is to avoid splitting latch edge with a biv increment, thus creating a jump, possibly confusing other optimization passes and leaving less freedom to scheduler. So we allow IP_END_POS only if IP_NORMAL_POS is not available (so we do not have a better alternative), or if the latch edge is already nonempty.
References add_old_iv_candidates(), iv::biv_p, integer_zerop(), version_info::iv, iv::step, and ver_info().
|
static |
Return true if get_computation_cost indicates that autoincrement is a possibility for the pair of USE and CAND, false otherwise.
|
inlinestatic |
Returns the expected number of loop iterations for LOOP. The average trip count is computed from profile data if it exists.
Referenced by get_expr_id().
|
static |
Computes value of candidate CAND at position AT in iteration NITER, and stores it to VAL.
|
static |
Returns true if A is a cheaper cost pair than B.
In case the costs are the same, prefer the cheaper candidate.
Referenced by iv_ca_set_cp().
|
static |
Returns true if AFF1 and AFF2 are identical.
|
static |
Returns a negative number if COST1 < COST2, a positive number if COST1 > COST2, and 0 if COST1 = COST2.
Referenced by iv_ca_extend().
|
static |
Determines cost of the computation of EXPR.
Avoid using hard regs in ways which may be unsupported.
|
static |
If we can prove that TOP = cst * BOT for some constant cst, store cst to MUL and return true. Otherwise return false. The returned value is always sign-extended, regardless of the signedness of TOP and BOT.
| bool contains_abnormal_ssa_name_p | ( | ) |
Returns true if EXPR contains a ssa name that occurs in an abnormal phi node.
Fallthru.
Referenced by alloc_iv().
|
static |
Creates a new induction variable corresponding to CAND.
fall through
Mark that the iv is preserved.
Rewrite the increment so that it uses var_before directly.
|
static |
Creates new induction variables described in SET.
|
static |
Returns a memory object to that EXPR points. In case we are able to determine that it does not point to any such object, NULL is returned.
If this is a pointer casted to any type, we need to determine the base object for the pointer; so handle conversions before throwing away non-pointer expressions.
Pointer addition is done solely using POINTER_PLUS_EXPR.
References build_int_cst(), ivopts_data::current_loop, flow_bb_inside_loop_p(), gimple_bb(), INTEGRAL_TYPE_P, version_info::iv, name_info(), NULL, POINTER_TYPE_P, set_iv(), SSA_NAME_DEF_STMT, and TREE_TYPE.
Referenced by niter_for_single_dom_exit().
|
static |
Determines the step of a biv defined in PHI. Returns NULL if PHI does not define a simple affine biv with nonzero step.
Referenced by alloc_iv().
|
static |
If A is (TYPE) BA and B is (TYPE) BB, and the types of BA and BB have the same precision that is at least as wide as the precision of TYPE, stores BA to A and BB to B, and returns the type of BA. Otherwise, returns the type of A and B.
References bitmap_bit_p, bitmap_clear(), bitmap_set_bit, dump_file, dump_flags, gen_int_mode(), gen_raw_REG(), HOST_WIDE_INT, LAST_VIRTUAL_REGISTER, MAX_RATIO, memory_address_addr_space_p(), NULL_RTX, sbitmap_alloc(), targetm, and XEXP.
|
static |
Determines cost of the candidate CAND.
There are two costs associated with the candidate – its increment and its initialization. The second is almost negligible for any loop that rolls enough, so we take it just very little into account.
It will be exceptional that the iv register happens to be initialized with the proper value at no cost. In general, there will at least be a regcopy or a const set.
Prefer the original ivs unless we may gain something by replacing it. The reason is to make debugging simpler; so this is not relevant for artificial ivs created by other optimization passes.
Prefer not to insert statements into latch unless there are some already (so that we do not create unnecessary jumps).
|
static |
Determines costs of computation of the candidates.
Referenced by rewrite_use_compare().
|
static |
For each size of the induction variable set determine the penalty.
References iv_ca::n_invariant_uses.
Referenced by rewrite_use_compare().
|
static |
Determines cost of basing replacement of USE on CAND. Returns false if USE cannot be based on CAND.
References dump_file, ivopts_data::speed, target_avail_regs, target_clobbered_regs, target_reg_cost, and target_spill_cost.
|
static |
Determines cost of basing replacement of USE on CAND in an address.
If we generated the candidate solely for exploiting autoincrement opportunities, and it turns out it can't be used, set the cost to infinity to make sure we ignore it.
References comp, HOST_WIDE_INT, IP_ORIGINAL, ivopts_data::loop_single_exit_p, tree_niter_desc::niter, nowrap_type_p(), offset, and TREE_TYPE.
|
static |
Determines cost of basing replacement of USE on CAND in a condition.
Only consider real candidates.
Try iv elimination.
If we replace a loop condition 'i < n' with 'p < base + n',
depends_on_elim will have 'base' and 'n' set, which implies
that both 'base' and 'n' will be live during the loop. More likely,
'base + n' will be loop invariant, resulting in only one live value
during the loop. So in that case we clear depends_on_elim and set
elim_inv_expr_id instead. The bound is a loop invariant, so it will be only computed
once. Try expressing the original giv. If it is compared with an invariant, note that we cannot get rid of it.
When the condition is a comparison of the candidate IV against zero, prefer this IV. TODO: The constant that we're subtracting from the cost should be target-dependent. This information should be added to the target costs for each backend.
Count the cost of the original bound as well.
Choose the better approach, preferring the eliminated IV.
|
static |
Determines cost of basing replacement of USE on CAND in a generic expression.
The simple case first – if we need to express value of the preserved original biv, the cost is 0. This also prevents us from counting the cost of increment twice – once at this use and once in the cost of the candidate.
|
static |
Determines costs of basing the use of the iv on an iv candidate.
Remove the candidates for that the cost is infinite from the list of related candidates.
Referenced by rewrite_use_compare().
|
static |
Returns true if we can prove that BASE - OFFSET does not overflow. For now, we only detect the situation that BASE = SOMETHING + OFFSET, where the calculation is performed in non-wrapping type.
TODO: More generally, we could test for the situation that BASE = SOMETHING + OFFSET' and OFFSET is between OFFSET' and zero. This would require knowing the sign of OFFSET.
Also, we only look for the first addition in the computation of BASE. More complex analysis would be better, but introducing it just for this optimization seems like an overkill.
TODO: deeper inspection may be necessary to prove the equality.
|
static |
Estimates cost of expressing difference E1 - E2 as var + symbol + offset. The value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding part is missing. DEPENDS_ON is a set of the invariants the computation depends on.
Referenced by get_expr_id().
| void dump_cand | ( | ) |
Dumps information about induction variable candidate CAND to FILE.
References SSA_NAME_VERSION, and ver_info().
| void dump_iv | ( | ) |
Dumps information about the induction variable IV to FILE.
| void dump_use | ( | ) |
Dumps information about the USE to FILE.
References dump_bitmap().
| void dump_uses | ( | ) |
Dumps information about the uses to FILE.
|
static |
Walk the SSA form and check whether E == WHAT. Fairly simplistic, we check for an exact match.
Fallthru.
| bool expr_invariant_in_loop_p | ( | ) |
Returns true if expression EXPR is obviously invariant in LOOP, i.e. if all its operands are defined outside of the LOOP. LOOP should not be the function body.
Referenced by outermost_invariant_loop_for_expr().
|
static |
Given a condition in statement STMT, checks whether it is a compare of an induction variable and an invariant. If this is the case, CONTROL_VAR is set to location of the iv, BOUND to the location of the invariant, IV_VAR and IV_BOUND are set to the corresponding induction variable descriptions, and true is returned. If this is not the case, CONTROL_VAR and BOUND are set to the arguments of the condition and false is returned.
The objects returned when COND has constant operands.
Exactly one of the compared values must be an iv, and the other one must be an invariant.
Control variable may be on the other side.
|
static |
Finds basic ivs.
|
static |
Referenced by get_shiftadd_cost().
|
static |
Finds general ivs.
|
static |
Finds general ivs in basic block BB.
References gimple_bb(), SSA_NAME_DEF_STMT, TREE_CODE, and virtual_operand_p().
|
static |
Finds general ivs in statement STMT.
|
static |
Checks whether STMT defines a linear induction variable and stores its parameters to IV.
If STMT could throw, then do not consider STMT as defining a GIV. While this will suppress optimizations, we can not safely delete this GIV and associated statements, even if it appears it is not used.
|
static |
For each ssa name defined in LOOP determines whether it is an induction variable and if so, its initial value and step.
References gcc_assert, get_iv(), iv::have_use_for, iv_use::id, integer_zerop(), is_gimple_assign(), iv_use::iv, iv_use(), NULL, record_invariant(), record_use(), SSA_NAME_DEF_STMT, iv::step, TREE_CODE, iv_use::type, iv::use_id, and USE_NONLINEAR_EXPR.
Referenced by rewrite_use_compare().
|
static |
Finds uses of the induction variables that are interesting.
Referenced by rewrite_use_compare().
|
static |
Finds addresses in *OP_P inside STMT.
Do not play with volatile memory references. A bit too conservative, perhaps, but safe.
Ignore bitfields for now. Not really something terribly complicated to handle. TODO.
Check that the base expression is addressable. This needs
to be done after substituting bases of IVs into it. Moreover, on strict alignment platforms, check that it is
sufficiently aligned. Substituting bases of IVs into the base expression might
have caused folding opportunities.
|
static |
Checks whether the condition in STMT is interesting and if so, records it.
|
staticread |
Checks whether the use OP is interesting and if so, records it.
|
static |
Finds interesting uses of induction variables outside of loops on loop exit edge EXIT.
|
static |
Finds interesting uses of induction variables in the statement STMT.
If the statement defines an induction variable, the uses are not interesting by themselves.
TODO – we should also handle address uses of type
memory = call (whatever);
and
call (memory).
References dump_file, EXECUTE_IF_SET_IN_BITMAP, version_info::has_nonlin_use, version_info::inv_id, version_info::name, print_generic_expr(), TDF_SLIM, and ver_info().
|
static |
Finds and records invariants used in STMT.
|
static |
Finds the candidates for the induction variables.
Add commonly used ivs.
Add old induction variables.
Add induction variables derived from uses.
Record the important candidates.
References iv_ca::cand_cost, iv_ca::cand_use_cost, comp_cost::cost, cost_pair::cost, iv_ca::cost, ivopts_global_cost_for_size(), iv_ca::n_regs, and iv_ca::num_used_inv_expr.
Referenced by rewrite_use_compare().
|
staticread |
Determine the cost based on a strategy that starts with original IVs, and try again using a strategy that prefers candidates not based on any IVs.
Choose the one with the best cost.
|
staticread |
Attempts to find the optimal set of induction variables. We do simple greedy heuristic – we try to replace at most one candidate in the selected solution and remove the unused ivs while this improves the cost.
Get the initial solution.
Referenced by get_shiftadd_cost().
|
static |
Estimates cost of forcing expression EXPR into a variable.
Just an arbitrary value, FIXME.
Bound the cost by target_spill_cost. The parts of complicated computations often are either loop invariant or at least can be shared between several iv uses, so letting this grow without limits would not give reasonable results.
|
static |
Estimates cost of forcing EXPR into a variable. DEPENDS_ON is a set of the invariants the computation depends on.
|
static |
Frees data allocated by the optimization of a single loop.
Referenced by rewrite_use_address().
|
static |
Frees memory occupied by struct tree_niter_desc in *VALUE. Callback for pointer_map_traverse.
Referenced by adjust_iv_update_pos().
|
static |
Returns variant of TYPE that can be used as base for different uses. We return unsigned type with the same precision, which avoids problems with overflows.
|
static |
Compute the cost of various addressing modes.
??? We can run into trouble with some backends by presenting
it with symbols which haven't been properly passed through
targetm.encode_section_info. By setting the local bit, we
enhance the probability of things working. To avoid splitting addressing modes, pretend that no cse will
follow. On some targets, it is quite expensive to load symbol to a register,
which makes addresses that contain symbols look much more expensive.
However, the symbol will have to be loaded in any case before the
loop (and quite likely we have it in register already), so it does not
make much sense to penalize them too heavily. So make some final
tweaks for the SYMBOL_PRESENT modes:
If VAR_PRESENT is false, and the mode obtained by changing symbol to
var is cheaper, use this mode with small penalty.
If VAR_PRESENT is true, try whether the mode with
SYMBOL_PRESENT = false is cheaper even with cost of addition, and
if this is the case, use it.
References address_cost_data_s::costs, and dump_file.
|
static |
Determines the expression by that USE is expressed from induction variable CAND in LOOP. The computation is unshared.
References memory_address_addr_space_p().
|
static |
Determines the expression by that USE is expressed from induction variable CAND at statement AT in LOOP. The expression is stored in a decomposed form into AFF. Returns false if USE cannot be expressed using CAND.
We do not have a precision to express the values of use.
If the conversion is not noop, perform it. In case both UBASE and CBASE are shortened to UUTYPE from some common type, we achieve better folding by computing their difference in this wider type, and cast the result to UUTYPE. We do not need to worry about overflows, as all the arithmetics will in the end be performed in UUTYPE anyway.
use = ubase - ratio * cbase + ratio * var.
We need to shift the value if we are after the increment.
|
static |
Determines the expression by that USE is expressed from induction variable CAND at statement AT in LOOP. The computation is unshared.
Referenced by rewrite_use_nonlinear_expr().
|
static |
Determines the cost of the computation by that USE is expressed from induction variable CAND. If ADDRESS_P is true, we just need to create an address from it, otherwise we want to get it into register. A set of invariants we depend on is stored in DEPENDS_ON. If CAN_AUTOINC is nonnull, use it to record whether autoinc addressing is likely.
Referenced by may_eliminate_iv().
|
static |
Determines the cost of the computation by that USE is expressed from induction variable CAND. If ADDRESS_P is true, we just need to create an address from it, otherwise we want to get it into register. A set of invariants we depend on is stored in DEPENDS_ON. AT is the statement at that the value is computed. If CAN_AUTOINC is nonnull, use it to record whether autoinc addressing is likely.
Only consider real candidates.
We do not have a precision to express the values of use.
Do not try to express address of an object with computation based
on address of a different object. This may cause problems in rtl
level alias analysis (that does not expect this to be happening,
as this is illegal in C), and would be unlikely to be useful
anyway. TODO – add direct handling of this case.
CSTEPI is removed from the offset in case statement is after the increment. If the step is not constant, we use zero instead. This is a bit imprecise (there is the extra addition), but redundancy elimination is likely to transform the code so that it uses value of the variable before increment anyway, so it is not that much unrealistic.
use = ubase + ratio * (var - cbase). If either cbase is a constant or ratio == 1, it is better to handle this like ubase - ratio * cbase + ratio * var (also holds in the case ratio == -1, TODO.
Check to see if any adjustment is needed.
Clear depends on.
If we are after the increment, the value of the candidate is higher by one iteration.
Now the computation is in shape symbol + var1 + const + ratio * var2. (symbol/var1/const parts may be omitted). If we are looking for an address, find the cost of addressing this.
Otherwise estimate the costs for computing the expression.
Symbol + offset should be compile-time computable so consider that they are added once to the variable, if present.
Having offset does not affect runtime cost in case it is added to symbol, but it increases complexity.
Just get the expression, expand it and measure the cost.
References iv_use::stmt.
|
static |
Stores EXPR in DATA->inv_expr_tab, and assigns it an inv_expr_id.
References avg_loop_niter(), build_int_cst(), comp_cost::cost, ivopts_data::current_loop, difference_cost(), and int_cst_value().
|
staticread |
Finds an initial assignment of candidates to uses.
|
staticread |
Finds induction variable declaration for VAR.
References ivopts_data::current_loop, gimple_bb(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), loop::header, basic_block_def::loop_father, loop_latch_edge(), PHI_ARG_DEF_FROM_EDGE, PHI_RESULT, and SSA_NAME_DEF_STMT.
Referenced by find_induction_variables().
|
static |
Returns the pseudo expr id if expression UBASE - RATIO * CBASE requires a new compiler generated temporary. Returns -1 otherwise. ADDRESS_P is a flag indicating if the expression is for address computation.
Strips the constant part.
Strips the constant part.
Now do more complex comparison
|
static |
Calculate the SPEED or size cost of shiftadd EXPR in MODE. MULT is the the EXPR operand holding the shift. COST0 and COST1 are the costs for calculating the operands of EXPR. Returns true if successful, and returns the cost in COST.
References find_depends(), force_expr_to_var_cost(), NULL, ivopts_data::speed, and walk_tree.
|
staticread |
Gets cost of (USE, CANDIDATE) pair.
n_map_members is a power of two, so this computes modulo.
References stmt_after_increment().
Referenced by iv_ca_add_use(), and iv_ca_set_cp().
|
static |
Return the type of USE.
The base_type may be a void pointer. Create a pointer type based on the mem_ref instead.
References dump_file, GET_MODE_NAME, HOST_WIDE_INT_PRINT_DEC, address_cost_data_s::max_offset, and address_cost_data_s::min_offset.
Returns false if BASE or INDEX contains a ssa name that occurs in an abnormal phi node. Callback for for_each_index.
References ivopts_data::niters, NULL, and pointer_map_create().
|
static |
If base is a component ref, require that the offset of the reference be invariant.
If base is array, first check whether we will be able to move the reference out of the loop (in order to take its address in strength reduction). In order for this to work we need both lower bound and step to be loop invariants.
Moreover, for a range, the size needs to be invariant as well.
XXX We produce for a base of *D42 with iv->base being &x[0]
&x[0], which is not folded and does not trigger the
ARRAY_REF path below. We only handle addresses whose step is an integer constant.
The step for pointer arithmetics already is 1 byte.
The index might wrap.
References double_int_one.
Records use in index IDX. Callback for for_each_index. Ivopts data object is passed to it in DATA.
|
static |
Returns true if COST is infinite.
Referenced by may_eliminate_iv().
|
static |
Extend set IVS by expressing USE by some of the candidates in it if possible. All important candidates will be considered if IMPORTANT_CANDIDATES is true.
References cost_pair::cand, iv_ca::cands, ivopts_data::consider_all_candidates, EXECUTE_IF_SET_IN_BITMAP, get_use_iv_cost(), iv_cand::id, iv_ca_cand_for_use(), iv_ca_has_deps(), iv_cand(), iv_use(), n_iv_uses(), and NULL.
Referenced by iv_ca_delta_commit().
|
staticread |
Returns candidate by that USE is expressed in IVS.
Referenced by iv_ca_add_use(), iv_ca_delta_commit(), and iv_ca_set_cp().
|
static |
Returns true if CAND is used in IVS.
Referenced by iv_ca_extend().
|
static |
Get cost for assignment IVS.
This was a conditional expression but it triggered a bug in Sun C 5.5.
Referenced by iv_ca_delta_commit(), iv_ca_extend(), and iv_ca_set_cp().
|
staticread |
Creates change of expressing USE by NEW_CP instead of OLD_CP and chains it before NEXT_CHANGE.
Referenced by iv_ca_set_cp().
|
static |
Commit changes in DELTA to IVS. If FORWARD is false, the changes are reverted instead.
References iv_ca::bad_uses, iv_ca_add_use(), iv_ca_cand_for_use(), iv_ca_cost(), NULL, and iv_ca::upto.
Referenced by iv_ca_extend(), and iv_ca_set_cp().
|
static |
Free the list of changes DELTA.
Referenced by iv_ca_dump(), iv_ca_extend(), and iv_ca_new().
|
staticread |
Joins two lists of changes L1 and L2. Destructive – old lists are rewritten.
Referenced by iv_ca_extend().
|
staticread |
Reverse the list of changes DELTA, forming the inverse to it.
|
static |
Dumps IVS to FILE.
References iv_ca_delta_free().
|
static |
Try changing candidate in IVS to CAND for each use. Return cost of the new set, and store differences in DELTA. Number of induction variables in the new set is stored to N_IVS. MIN_NCAND is a flag. When it is true the function will try to find a solution with mimimal iv candidates.
References ALWAYS_PRUNE_CAND_SET_BOUND, compare_costs(), iv_ca_cand_used_p(), iv_ca_cost(), iv_ca_delta_commit(), iv_ca_delta_free(), iv_ca_delta_join(), iv_ca_prune(), iv_cand(), n_iv_cands(), and NULL.
|
static |
Free memory occupied by the set IVS.
|
static |
Returns true if all dependences of CP are among invariants in IVS.
Referenced by iv_ca_add_use(), and iv_ca_set_cp().
|
static |
Returns number of induction variable candidates in the set IVS.
References IP_ORIGINAL, and iv_cand().
Referenced by iv_ca_set_cp().
|
static |
Try narrowing set IVS by removing CAND. Return the cost of the new set and store the differences in DELTA.
|
staticread |
Allocates new iv candidates assignment.
References iv_ca_delta_free().
|
static |
Try optimizing the set of candidates IVS by removing candidates different from to EXCEPT_CAND from it. Return cost of the new set, and store differences in DELTA.
Recurse to possibly remove other unnecessary ivs.
Referenced by iv_ca_extend().
|
static |
Computes the cost field of IVS structure.
|
static |
Add invariants in set INVS to set IVS.
|
static |
Set cost pair for USE in set IVS to CP.
Do not count the pseudocandidates.
References cost_pair::cand, cheaper_cost_pair(), cost_pair::cost, get_use_iv_cost(), iv_ca_cand_for_use(), iv_ca_cost(), iv_ca_delta_add(), iv_ca_delta_commit(), iv_ca_has_deps(), iv_ca_n_cands(), iv_use(), NULL, and iv_ca::upto.
|
static |
Set USE not to be expressed by any candidate in IVS.
Do not count the pseudocandidates.
|
static |
Remove invariants in set INVS to set IVS.
References iv_ca_delta::next_change.
Ith candidate recorded in DATA.
Referenced by iv_ca_add_use(), iv_ca_extend(), and iv_ca_n_cands().
|
static |
Returns the comparison operator used when eliminating the iv USE.
|
static |
Tries to replace loop exit by one formulated in terms of a LT_EXPR comparison with CAND. NITER describes the number of iterations of the loops. If successful, the comparison in COMP_P is altered accordingly.
We aim to handle the following situation:
sometype *base, *p; int a, b, i;
i = a; p = p_0 = base + a;
do { bla (*p); p++; i++; } while (i < b);
Here, the number of iterations of the loop is (a + 1 > b) ? 0 : b - a - 1. We aim to optimize this to
p = p_0 = base + a; do { bla (*p); p++; } while (p < p_0 - a + b);
This preserves the correctness, since the pointer arithmetics does not overflow. More precisely:
1) if a + 1 <= b, then p_0 - a + b is the final value of p, hence there is no overflow in computing it or the values of p. 2) if a + 1 > b, then we need to verify that the expression p_0 - a does not overflow. To prove this, we use the fact that p_0 = base + a.
We need to know that the candidate induction variable does not overflow. While more complex analysis may be used to prove this, for now just check that the variable appears in the original program and that it is computed in a type that guarantees no overflows.
Make sure that the loop iterates till the loop bound is hit, as otherwise the calculation of the BOUND could overflow, making the comparison invalid.
We need to be able to decide whether candidate is increasing or decreasing in order to choose the right comparison operator.
Check that the number of iterations matches the expected pattern: a + 1 > b ? 0 : b - a - 1.
Handle a + 1 > b.
Handle b < a + 1.
Expected number of iterations is B - A - 1. Check that it matches the actual number, i.e., that B - A - NITER = 1.
Finally, check that CAND->IV->BASE - CAND->IV->STEP * A does not overflow.
Determine the new comparison operator.
|
static |
Returns period of induction variable iv.
Period of the iv is lcm (step, type_range)/step -1, i.e., N*type_range/step - 1. Since type range is power of two, N == (step >> num_of_ending_zeros_binary (step), so the final result is
(type_range >> num_of_ending_zeros_binary (step)) - 1
Ith use recorded in DATA.
Referenced by find_induction_variables(), iv_ca_add_use(), iv_ca_set_cp(), and rewrite_use_nonlinear_expr().
|
static |
Calculates cost for having SIZE induction variables.
We add size to the cost, so that we prefer eliminating ivs if possible.
References cost_pair::depends_on, and EXECUTE_IF_SET_IN_BITMAP.
Referenced by find_iv_candidates().
|
static |
Returns true if the loop body BODY includes any function calls.
Referenced by rewrite_use_compare().
|
static |
Marks basic ivs.
If the increment is in the subloop, ignore it.
| bool may_be_nonaddressable_p | ( | ) |
Return true if EXPR may be non-addressable.
TARGET_MEM_REFs are translated directly to valid MEMs on the
target, thus they are always addressable.
This kind of view-conversions may wrap non-addressable objects
and make them look addressable. After some processing the
non-addressability may be uncovered again, causing ADDR_EXPRs
of inappropriate objects to be built. ... fall through ...
|
static |
Returns true if memory reference REF with step STEP may be unaligned.
TARGET_MEM_REFs are translated directly to valid MEMs on the target, thus they are not misaligned.
The test below is basically copy of what expr.c:normal_inner_ref does to check whether the object must be loaded by parts when STRICT_ALIGNMENT is true.
|
static |
Check whether it is possible to express the condition in USE by comparison of candidate CAND. If so, store the value compared with to BOUND, and the comparison operator to COMP.
For now works only for exits that dominate the loop latch. TODO: extend to other conditions inside loop body.
Determine whether we can use the variable to test the exit condition. This is the case iff the period of the induction variable is greater than the number of iterations for which the exit condition is true.
If the number of iterations is constant, compare against it directly.
See cand_value_at.
If not, and if this is the only possible exit of the loop, see whether we can get a conservative estimate on the number of iterations of the entire loop and compare against that instead.
See if we can take advantage of inferred loop bound information.
The loop bound is already adjusted by adding 1.
It is unlikely that computing the number of iterations using division would be more profitable than keeping the original induction variable.
Sometimes, it is possible to handle the situation that the number of
iterations may be zero unless additional assumtions by using <
instead of != in the exit condition.
TODO: we could also calculate the value MAY_BE_ZERO ? 0 : NITER and
base the exit condition on it. However, that is often too
expensive.
References BITMAP_FREE, get_computation_cost(), infinite_cost_p(), NULL, iv_use::type, and USE_ADDRESS.
| bool multiplier_allowed_in_address_p | ( | HOST_WIDE_INT | ratio, |
| enum machine_mode | mode, | ||
| addr_space_t | as | ||
| ) |
Returns true if multiplying by RATIO is allowed in an address. Test the validity for a memory reference accessing memory of mode MODE in address space AS.
|
inlinestatic |
Number of candidates recorded in DATA.
References iv::base_object, print_generic_expr(), and TDF_SLIM.
Referenced by iv_ca_extend().
|
inlinestatic |
Number of uses recorded in DATA.
References iv::base, print_generic_expr(), iv::step, and TDF_SLIM.
Referenced by iv_ca_add_use(), and rewrite_use_nonlinear_expr().
|
staticread |
Returns the info for ssa name NAME.
Referenced by determine_base_object().
|
static |
Returns description of computation cost of expression whose runtime cost is RUNTIME and complexity corresponds to COMPLEXITY.
References targetm.
Referenced by do_SUBST_MODE(), and reload_combine_closest_single_use().
|
staticread |
Returns the structure describing number of iterations determined from EXIT of DATA->current_loop, or NULL if something goes wrong.
Try to determine number of iterations. We cannot safely work with ssa names that appear in phi nodes on abnormal edges, so that we do not create overlapping life ranges for them (PR 27283).
|
staticread |
Returns the structure describing number of iterations determined from single dominating exit of DATA->current_loop, or NULL if something goes wrong.
References iv::base, iv::base_object, iv::biv_p, determine_base_object(), gcc_assert, iv::have_use_for, NULL_TREE, iv::ssa_name, iv::step, and iv::use_id.
|
read |
Returns the outermost loop EXPR is obviously invariant in relative to the loop LOOP, i.e. if all its operands are defined outside of the returned loop. Returns NULL if EXPR is not even obviously invariant in LOOP.
References array_ref_element_size(), array_ref_low_bound(), expr_invariant_in_loop_p(), TREE_CODE, TREE_TYPE, and TYPE_SIZE.
|
static |
Calculates the cost of BOUND, if it is a PARM_DECL. A PARM_DECL must be copied, if is is used in the loop body and DATA->body_includes_call.
|
static |
Prepares decl_rtl for variables referred in *EXPR_P. Callback for walk_tree. DATA contains the actual fake register number.
Defer handling of anonymous SSA_NAMEs to the expander.
|
static |
Produce DECL_RTL for object obj so it looks like it is stored in memory.
Referenced by sub_costs().
|
static |
Estimates cost of expressing difference of addresses E1 - E2 as var + symbol + offset. The value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding part is missing. DEPENDS_ON is a set of the invariants the computation depends on.
|
static |
Record important candidates and add them to related_cands bitmaps if needed.
We will not need "related_cands" bitmaps in this case, so release them to decrease peak memory consumption.
Add important candidates to the related_cands bitmaps.
|
static |
Checks whether OP is a loop-level invariant and if so, records it. NONLINEAR_USE is true if the invariant is used in a way we do not handle specially.
Referenced by find_induction_variables().
|
staticread |
Records a use of type USE_TYPE at *USE_P in STMT whose value is IV.
To avoid showing ssa name in the dumps, if it was not reset by the caller.
References gimple_assign_rhs1_ptr(), gimple_assign_rhs2_ptr(), gimple_cond_lhs_ptr(), gimple_cond_rhs_ptr(), integer_zero_node, and iv::step.
Referenced by find_induction_variables().
|
static |
Removes the ivs that are not used after rewriting.
Figure out an order in which to release SSA DEFs so that we don't release something that we'd have to propagate into a debug stmt afterwards.
We just want to determine whether to do nothing
(count == 0), to substitute the computed
expression into a single use of the SSA DEF by
itself (count == 1), or to use a debug temp
because the SSA DEF is used multiple times or as
part of a larger expression (count > 1).
|
static |
Rewrites USE using candidate CAND.
|
static |
Rewrites USE (address that is an iv) using candidate CAND.
To avoid undefined overflow problems, all IV candidates use unsigned integer types. The drawback is that this makes it impossible for create_mem_ref to distinguish an IV that is based on a memory object from one that represents simply an offset.
To work around this problem, we pass a hint to create_mem_ref that indicates which variable (if any) in aff is an IV based on a memory object. Note that we only consider the candidate. If this is not based on an object, the base of the reference is in some subexpression of the use – but these will use pointer types, so they are recognized by the create_mem_ref heuristics anyway.
References BITMAP_FREE, decl_rtl_to_reset, and free_loop_data().
|
static |
Rewrites USE (the condition such that one of the arguments is an iv) using candidate CAND.
The induction variable elimination failed; just express the original giv.
References ivopts_data::body_includes_call, changed, ivopts_data::current_loop, edge_def::dest, determine_iv_costs(), determine_set_costs(), determine_use_iv_costs(), dump_file, dump_flags, find_induction_variables(), find_interesting_uses(), find_iv_candidates(), gcc_assert, get_loop_body(), basic_block_def::index, last_stmt(), loop_body_includes_call(), loop_only_exit_p(), ivopts_data::loop_single_exit_p, MAX_CONSIDERED_USES, ivopts_data::niters, NULL, loop::num, loop::num_nodes, optimize_loop_for_speed_p(), print_gimple_stmt(), renumber_gimple_stmt_uids_in_blocks(), single_dom_exit(), ivopts_data::speed, edge_def::src, and TDF_SLIM.
|
static |
Rewrites USE (definition of iv used in a nonlinear expression) using candidate CAND.
An important special case – if we are asked to express value of the original iv by itself, just exit; there is no need to introduce a new computation (that might also need casting the variable to unsigned and back).
Check whether we may leave the computation unchanged.
This is the case only if it does not rely on other
computations in the loop – otherwise, the computation
we rely upon may be removed in remove_unused_ivs,
thus leading to ICE. If we should keep the biv, do not replace it.
We can't allow re-allocating the stmt as it might be pointed
to still. As this isn't a plain copy we have to reset alignment
information.
References iv::base, bitmap_set_bit, BREAK_FROM_IMM_USE_STMT, count, ivopts_data::current_loop, DECL_ARTIFICIAL, DECL_MODE, FOR_EACH_IMM_USE_ON_STMT, FOR_EACH_IMM_USE_STMT, get_computation_at(), gimple_build_debug_bind, gimple_debug_bind_get_value(), gimple_debug_bind_p(), gsi_after_labels(), gsi_for_stmt(), gsi_insert_before(), GSI_SAME_STMT, version_info::iv, iv_use::iv, iv_use(), make_node, MAY_HAVE_DEBUG_STMTS, n_iv_uses(), NULL, operand_equal_p(), iv_use::selected, SET_USE, iv::ssa_name, SSA_NAME_DEF_STMT, SSA_NAME_VAR, SSA_NAME_VERSION, iv::step, TREE_CODE, TREE_TYPE, TYPE_MODE, and update_stmt().
|
static |
Rewrite the uses using the selected induction variables.
References dump_file, dump_flags, flow_loop_dump(), FOR_EACH_LOOP, LI_FROM_INNERMOST, NULL, tree_ssa_iv_optimize_finalize(), tree_ssa_iv_optimize_init(), and tree_ssa_iv_optimize_loop().
|
static |
Returns estimate on cost of computing SEQ.
|
static |
Examine IP_ORIGINAL candidates to see if they are incremented next to a use that allows autoincrement, and set their AINC_USE if possible.
|
static |
Sets STEP and BASE for induction variable IV.
Referenced by determine_base_object().
|
static |
Sets cost of (USE, CANDIDATE) pair to COST and record that it depends on invariants DEPENDS_ON and that the value used in expressing it is VALUE, and in case of iv elimination the comparison operator is COMP.
n_map_members is a power of two, so this computes modulo.
| edge single_dom_exit | ( | ) |
The single loop exit if it dominates the latch, NULL otherwise.
References gcc_unreachable, USE_ADDRESS, USE_COMPARE, and USE_NONLINEAR_EXPR.
Referenced by build_new_reduction(), create_loop_fn(), insn_to_prefetch_ratio_too_small_p(), loop_has_vector_phi_nodes(), and rewrite_use_compare().
|
static |
Estimates cost of expressing address ADDR as var + symbol + offset. The value of offset is added to OFFSET, SYMBOL_PRESENT and VAR_PRESENT are set to false if the corresponding part is missing. DEPENDS_ON is a set of the invariants the computation depends on.
References TREE_CODE, and TREE_OPERAND.
|
static |
Returns true if STMT if after the place where the original induction variable CAND is incremented. If TRUE_IF_EQUAL is set, we return true if the positions are identical.
|
static |
Returns true if STMT if after the place where the induction variable CAND is incremented in LOOP.
Referenced by get_use_iv_cost().
|
static |
Returns true if STMT is after the place where the IP_NORMAL ivs will be emitted in LOOP.
|
static |
Strips constant offsets from EXPR and stores them to OFFSET.
|
static |
Strips constant offsets from EXPR and stores them to OFFSET. If INSIDE_ADDR is true, assume we are inside an address. If TOP_COMPREF is true, assume we are at the top-level of the processed address.
Strip the component reference completely.
Strip the component reference completely.
??? Offset operand?
Default handling of expressions for that we want to recurse into the first operand.
Inside address, we might strip the top level component references, thus changing type of the expression. Handling of ADDR_EXPR will fix that.
|
static |
References ivopts_data::current_loop.
|
static |
Subtracts costs COST1 and COST2.
References DECL_P, DECL_RTL_SET_P, handled_component_p(), HAS_RTL_P, produce_memory_decl_rtl(), and TREE_OPERAND.
| void tree_ssa_iv_optimize | ( | void | ) |
Main entry point. Optimizes induction variables in loops.
Optimize the loops starting with the innermost ones.
|
static |
Finalizes data structures used by the iv optimization pass. LOOPS is the loop tree.
Referenced by rewrite_uses().
|
static |
Initializes data structures used by the iv optimization pass, stored in DATA.
Referenced by rewrite_uses().
|
static |
Optimizes the LOOP. Returns true if anything changed.
For each ssa name determines whether it behaves as an induction variable in some loop.
Finds interesting uses (item 1).
Finds candidates for the induction variables (item 2).
Calculates the costs (item 3, part 1).
Find the optimal set of induction variables (item 3, part 2).
Create the new induction variables (item 4, part 1).
Rewrite the uses (item 4, part 2).
Remove the ivs that are unused after rewriting.
We have changed the structure of induction variables; it might happen that definitions in the scev database refer to some of them that were eliminated.
Referenced by rewrite_uses().
|
static |
Tries to extend the sets IVS in the best possible way in order to express the USE. If ORIGINALP is true, prefer candidates from the original set of IVs, otherwise favor important candidates not based on any memory object.
If ORIGINALP is true, try to find the original IV for the use. Otherwise first try important candidates not based on any memory object. Only if this fails, try the specific ones. Rationale – in loops with many variables the best choice often is to use just one generic biv. If we added here many ivs specific to the uses, the optimization algorithm later would be likely to get stuck in a local minimum, thus causing us to create too many ivs. The approach from few ivs to more seems more likely to be successful – starting from few ivs, replacing an expensive use by a specific iv should always be a win.
Already tried this.
|
static |
Tries to improve set of induction variables IVS.
Try extending the set of induction variables by one.
If we successfully added the candidate and the set is small enough,
try optimizing it by removing other candidates. Try removing the candidates from the set instead.
Nothing more we can do.
References dump_file, dump_flags, gimple_assign_lhs(), gimple_bb(), gsi_end_p(), gsi_last_nondebug_bb(), gsi_prev_nondebug(), gsi_stmt(), IP_NORMAL, print_gimple_stmt(), SSA_NAME_DEF_STMT, iv_use::stmt, and TREE_CODE.
|
static |
Returns variable containing the value of candidate CAND at statement AT.
|
staticread |
Returns the info for ssa version VER.
Referenced by allow_ip_end_pos_p(), dump_cand(), and find_interesting_uses_stmt().
Variable Documentation
The list of trees for that the decl_rtl field must be reset is stored here.
Referenced by rewrite_use_address().
|
static |
Records invariants in *EXPR_P. Callback for walk_tree. DATA contains the bitmap to that we should store it.
|
static |
