GCC Middle and Back End API Reference

Data Structures  
struct  slsr_cand_d 
struct  cand_chain_d 
struct  incr_info_d 
struct  cand_chain_hasher 
class  find_candidates_dom_walker 
Typedefs  
typedef unsigned  cand_idx 
typedef struct slsr_cand_d  slsr_cand 
typedef struct slsr_cand_d *  slsr_cand_t 
typedef struct slsr_cand_d *  const_slsr_cand_t 
typedef struct cand_chain_d  cand_chain 
typedef struct cand_chain_d *  cand_chain_t 
typedef struct cand_chain_d *  const_cand_chain_t 
typedef struct incr_info_d  incr_info 
typedef struct incr_info_d *  incr_info_t 
Enumerations  
enum  cand_kind { CAND_MULT, CAND_ADD, CAND_REF, CAND_PHI } 
enum  cost_consts { COST_NEUTRAL = 0, COST_INFINITE = 1000 } 
enum  stride_status { UNKNOWN_STRIDE = 0, KNOWN_STRIDE = 1 } 
enum  phi_adjust_status { NOT_PHI_ADJUST = 0, PHI_ADJUST = 1 } 
enum  count_phis_status { DONT_COUNT_PHIS = 0, COUNT_PHIS = 1 } 
Variables  
static vec< slsr_cand_t >  cand_vec 
static struct pointer_map_t *  stmt_cand_map 
static struct obstack  cand_obstack 
static struct obstack  chain_obstack 
static incr_info_t  incr_vec 
static unsigned  incr_vec_len 
const int  MAX_INCR_VEC_LEN = 16 
static bool  address_arithmetic_p 
static hash_table < cand_chain_hasher >  base_cand_map 
typedef struct cand_chain_d cand_chain 
typedef struct cand_chain_d * cand_chain_t 
typedef unsigned cand_idx 
@verbatim
Straightline strength reduction. Copyright (C) 20122013 Free Software Foundation, Inc. Contributed by Bill Schmidt, IBM wschm idt@ linux .ibm .com
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/.
There are many algorithms for performing strength reduction on loops. This is not one of them. IVOPTS handles strength reduction of induction variables just fine. This pass is intended to pick up the crumbs it leaves behind, by considering opportunities for strength reduction along dominator paths. Strength reduction addresses explicit multiplies, and certain multiplies implicit in addressing expressions. It would also be possible to apply strength reduction to divisions and modulos, but such opportunities are relatively uncommon. Strength reduction is also currently restricted to integer operations. If desired, it could be extended to floatingpoint operations under control of something like funsafemathoptimizations.
Information about a strength reduction candidate. Each statement in the candidate table represents an expression of one of the following forms (the special case of CAND_REF will be described later): (CAND_MULT) S1: X = (B + i) * S (CAND_ADD) S1: X = B + (i * S) Here X and B are SSA names, i is an integer constant, and S is either an SSA name or a constant. We call B the "base," i the "index", and S the "stride." Any statement S0 that dominates S1 and is of the form: (CAND_MULT) S0: Y = (B + i') * S (CAND_ADD) S0: Y = B + (i' * S) is called a "basis" for S1. In both cases, S1 may be replaced by S1': X = Y + (i  i') * S, where (i  i') * S is folded to the extent possible. All gimple statements are visited in dominator order, and each statement that may contribute to one of the forms of S1 above is given at least one entry in the candidate table. Such statements include addition, pointer addition, subtraction, multiplication, negation, copies, and nontrivial type casts. If a statement may represent more than one expression of the forms of S1 above, multiple "interpretations" are stored in the table and chained together. Examples: * An add of two SSA names may treat either operand as the base. * A multiply of two SSA names, likewise. * A copy or cast may be thought of as either a CAND_MULT with i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0. Candidate records are allocated from an obstack. They are addressed both from a hash table keyed on S1, and from a vector of candidate pointers arranged in predominator order. Opportunity note  Currently we don't recognize: S0: Y = (S * i')  B S1: X = (S * i)  B as a strength reduction opportunity, even though this S1 would also be replaceable by the S1' above. This can be added if it comes up in practice. Strength reduction in addressing  There is another kind of candidate known as CAND_REF. A CAND_REF describes a statement containing a memory reference having complex addressing that might benefit from strength reduction. Specifically, we are interested in references for which get_inner_reference returns a base address, offset, and bitpos as follows: base: MEM_REF (T1, C1) offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3) bitpos: C4 * BITS_PER_UNIT Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are arbitrary integer constants. Note that C2 may be zero, in which case the offset will be MULT_EXPR (T2, C3). When this pattern is recognized, the original memory reference can be replaced with: MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)), C1 + (C2 * C3) + C4) which distributes the multiply to allow constant folding. When two or more addressing expressions can be represented by MEM_REFs of this form, differing only in the constants C1, C2, and C4, making this substitution produces more efficient addressing during the RTL phases. When there are not at least two expressions with the same values of T1, T2, and C3, there is nothing to be gained by the replacement. Strength reduction of CAND_REFs uses the same infrastructure as that used by CAND_MULTs and CAND_ADDs. We record T1 in the base (B) field, MULT_EXPR (T2, C3) in the stride (S) field, and C1 + (C2 * C3) + C4 in the index (i) field. A basis for a CAND_REF is thus another CAND_REF with the same B and S values. When at least two CAND_REFs are chained together using the basis relation, each of them is replaced as above, resulting in improved code generation for addressing. Conditional candidates ====================== Conditional candidates are best illustrated with an example. Consider the code sequence: (1) x_0 = ...; (2) a_0 = x_0 * 5; MULT (B: x_0; i: 0; S: 5) if (...) (3) x_1 = x_0 + 1; ADD (B: x_0, i: 1; S: 1) (4) x_2 = PHI <x_0, x_1>; PHI (B: x_0, i: 0, S: 1) (5) x_3 = x_2 + 1; ADD (B: x_2, i: 1, S: 1) (6) a_1 = x_3 * 5; MULT (B: x_2, i: 1; S: 5) Here strength reduction is complicated by the uncertain value of x_2. A legitimate transformation is: (1) x_0 = ...; (2) a_0 = x_0 * 5; if (...) { (3) [x_1 = x_0 + 1;] (3a) t_1 = a_0 + 5; } (4) [x_2 = PHI <x_0, x_1>;] (4a) t_2 = PHI <a_0, t_1>; (5) [x_3 = x_2 + 1;] (6r) a_1 = t_2 + 5; where the bracketed instructions may go dead. To recognize this opportunity, we have to observe that statement (6) has a "hidden basis" (2). The hidden basis is unlike a normal basis in that the statement and the hidden basis have different base SSA names (x_2 and x_0, respectively). The relationship is established when a statement's base name (x_2) is defined by a phi statement (4), each argument of which (x_0, x_1) has an identical "derived base name." If the argument is defined by a candidate (as x_1 is by (3)) that is a CAND_ADD having a stride of 1, the derived base name of the argument is the base name of the candidate (x_0). Otherwise, the argument itself is its derived base name (as is the case with argument x_0). The hidden basis for statement (6) is the nearest dominating candidate whose base name is the derived base name (x_0) of the feeding phi (4), and whose stride is identical to that of the statement. We can then create the new "phi basis" (4a) and feeding adds along incoming arcs (3a), allowing the final replacement of (6) by the strengthreduced (6r). To facilitate this, a new kind of candidate (CAND_PHI) is introduced. A CAND_PHI is not a candidate for replacement, but is maintained in the candidate table to ease discovery of hidden bases. Any phi statement whose arguments share a common derived base name is entered into the table with the derived base name, an (arbitrary) index of zero, and a stride of 1. A statement with a hidden basis can then be detected by simply looking up its feeding phi definition in the candidate table, extracting the derived base name, and searching for a basis in the usual manner after substituting the derived base name. Note that the transformation is only valid when the original phi and the statements that define the phi's arguments are all at the same position in the loop hierarchy.
Index into the candidate vector, offset by 1. VECs are zerobased, while cand_idx's are onebased, with zero indicating null.
typedef struct cand_chain_d* const_cand_chain_t 
typedef struct slsr_cand_d* const_slsr_cand_t 
typedef struct incr_info_d incr_info 
typedef struct incr_info_d * incr_info_t 
typedef struct slsr_cand_d slsr_cand 
typedef struct slsr_cand_d * slsr_cand_t 
enum cand_kind 
enum cost_consts 
enum count_phis_status 
enum phi_adjust_status 
enum stride_status 

static 
Add an entry to the statementtocandidate mapping.
Referenced by create_add_imm_cand().

static 
Return TRUE iff all required increments for candidates feeding PHI are profitable to replace on behalf of candidate C.
Referenced by ncd_of_cand_and_phis(), and replace_rhs_if_not_dup().

static 
Allocate storage for a new candidate and initialize its fields. Attempt to find a basis for the candidate.
References add_cost(), convert_cost(), gimple_assign_rhs2(), host_integerp(), mul_cost(), mult_by_coeff_cost(), and neg_cost().

static 
Analyze costs of related candidates in the candidate vector, and make beneficial replacements.
Each candidate that has a null basis and a nonnull dependent is the root of a tree of related statements. Analyze each tree to determine a subset of those statements that can be replaced with maximum benefit.
If this is a chain of CAND_REFs, unconditionally replace each of them with a strengthreduced data reference.
If the common stride of all related candidates is a known constant, each candidate without a phidependence can be profitably replaced. Each replaces a multiply by a single add, with the possibility that a feeding add also goes dead. A candidate with a phidependence is replaced only if the compensation code it requires is offset by the strength reduction savings.
When the stride is an SSA name, it may still be profitable to replace some or all of the dependent candidates, depending on whether the introduced increments can be reused, or are less expensive to calculate than the replaced statements.
Determine whether we'll be generating pointer arithmetic when replacing candidates.
If all candidates have already been replaced under other interpretations, nothing remains to be done.
Construct an array of increments for this candidate chain.
Determine which increments are profitable to replace.
Insert initializers of the form T_0 = stride * increment for use in profitable replacements.
Perform the replacements.

static 
Use targetspecific costs to determine and record which increments in the current candidate tree are profitable to replace, assuming MODE and SPEED. FIRST_DEP is the first dependent of the root of the candidate tree. One slight limitation here is that we don't account for the possible introduction of casts in some cases. See replace_one_candidate for the cases where these are introduced. This should probably be cleaned up sometime.
If somehow this increment is bigger than a HWI, we won't be optimizing candidates that use it. And if the increment has a count of zero, nothing will be done with it.
Increments of 0, 1, and 1 are always profitable to replace, because they always replace a multiply or add with an add or copy, and may cause one or more existing instructions to go dead. Exception: 1 can't be assumed to be profitable for pointer addition.
FORNOW: If we need to add an initializer, give up if a cast from the candidate's type to its stride's type can lose precision. This could eventually be handled better by expressly retaining the result of a cast to a wider type in the stride. Example: short int _1; _2 = (int) _1; _3 = _2 * 10; _4 = x + _3; ADD: x + (10 * _1) : int _5 = _2 * 15; _6 = x + _3; ADD: x + (15 * _1) : int Right now replacing _6 would cause insertion of an initializer of the form "short int T = _1 * 5;" followed by a cast to int, which could overflow incorrectly. Had we recorded _2 or (int)_1 as the stride, this wouldn't happen. However, doing this breaks other opportunities, so this will require some care.
If we need to add an initializer, make sure we don't introduce a multiply by a pointer type, which can happen in certain cast scenarios. FIXME: When cleaning up these cast issues, we can afford to introduce the multiply provided we cast out to an unsigned int of appropriate size.
For any other increment, if this is a multiply candidate, we must introduce a temporary T and initialize it with T_0 = stride * increment. When optimizing for speed, walk the candidate tree to calculate the best cost reduction along any path; if it offsets the fixed cost of inserting the initializer, replacing the increment is profitable. When optimizing for size, instead calculate the total cost reduction from replacing all candidates with this increment.
If this is an add candidate, the initializer may already exist, so only calculate the cost of the initializer if it doesn't. We are replacing one add with another here, so the known replacement savings is zero. We will account for removal of dead instructions in lowest_cost_path or total_savings.
References address_arithmetic_p, base_cand_from_table(), slsr_cand_d::base_expr, slsr_cand_d::basis, slsr_cand_d::cand_stmt, gimple_phi_arg_def(), gimple_phi_num_args(), gimple_phi_result(), slsr_cand_d::index, lookup_cand(), ncd_for_two_cands(), ncd_with_phi(), and operand_equal_p().

static 
Given PBASE which is a pointer to tree, look up the defining statement for it and check whether the candidate is in the form of: X = B + (1 * S), S is integer constant X = B + (i * S), S is integer one If so, set PBASE to the candidate's base_expr and return double int (i * S). Otherwise, just return double int zero.
Strip off widening conversion(s) to handle cases where e.g. 'B' is widened from an 'int' in order to calculate a 64bit address.
X = B + (1 * S), S is integer constant.
X = B + (i * S), S is integer one.
References double_int_to_tree(), double_int::from_uhwi(), double_int::is_zero(), mem_ref_offset(), offset, tree_to_double_int(), type(), double_int::udiv(), and double_int::umod().

static 
Forward function declarations.
Referenced by analyze_increments(), create_mul_ssa_cand(), lookup_cand(), and ncd_of_cand_and_phis().

static 
Look up the defining statement for BASE_IN and return a pointer to its candidate in the candidate table, if any; otherwise NULL. Only CAND_ADD and CAND_MULT candidates are returned.

inlinestatic 
Calculate the increment required for candidate C relative to its basis. If we aren't going to generate pointer arithmetic for this candidate, return the absolute value of that increment instead.
Referenced by record_phi_increments().

inlinestatic 
Return TRUE iff candidate C has already been replaced under another interpretation.
References incr_info_d::incr, and incr_vec_len.
Referenced by record_phi_increments().

static 
Calculate the increment required for candidate C relative to its basis.
If the candidate doesn't have a basis, just return its own index. This is useful in record_increments to help us find an existing initializer. Also, if the candidate's basis is hidden by a phi, then its own index will be the increment from the newly introduced phi basis.
Referenced by dump_incr_vec().

static 
Count the number of candidates in the tree rooted at C that have not already been replaced under other interpretations.

static 
Create a candidate entry for a statement GS, where GS adds SSA name BASE_IN to constant INDEX_IN. Propagate any known information about BASE_IN into the new candidate. Return the new candidate.
Y = (B + i') * S, S constant, c = kS for some integer k X = Y + c ============================ X = (B + (i'+ k)) * S OR Y = B + (i' * S), S constant, c = kS for some integer k X = Y + c ============================ X = (B + (i'+ k)) * S
No interpretations had anything useful to propagate, so produce X = Y + (c * 1).
References add_cand_for_stmt(), create_add_ssa_cand(), and slsr_cand_d::next_interp.

static 
Create a new statement along edge E to add BASIS_NAME to the product of INCREMENT and the stride of candidate C. Create and return a new SSA name from *VAR to be used as the LHS of the new statement. KNOWN_STRIDE is true iff C's stride is a constant.
If the add candidate along this incoming edge has the same index as C's hidden basis, the hidden basis represents this edge correctly.

static 
Create a candidate entry for a statement GS, where GS adds two SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known information about the two SSA names into the new candidate. Return the new candidate.
The most useful transformation is a multiplyimmediate feeding an add or subtract. Look for that first.
Z = (B + 0) * S, S constant X = Y +/ Z =========================== X = Y + ((+/1 * S) * B)
Y = B + (i' * S), i' * S = 0 X = Y +/ Z ============================ X = B + (+/1 * Z)
Z = (B + 0) * S, S constant X = Y  Z =========================== Value: X = Y + ((1 * S) * B)
No interpretations had anything useful to propagate, so produce X = Y + (1 * Z).
Referenced by create_add_imm_cand().

static 
Create a candidate entry for a statement GS, where GS multiplies SSA name BASE_IN by constant STRIDE_IN. Propagate any known information about BASE_IN into the new candidate. Return the new candidate.
Look at all interpretations of the base candidate, if necessary, to find information to propagate into this candidate.
Y = (B + i') * S, S constant X = Y * c ============================ X = (B + i') * (S * c)
Y = B + (i' * 1) X = Y * c =========================== X = (B + i') * c
Y = B + (1 * S), S constant X = Y * c =========================== X = (B + S) * c
No interpretations had anything useful to propagate, so produce X = (Y + 0) * c.

static 
Create a candidate entry for a statement GS, where GS multiplies two SSA names BASE_IN and STRIDE_IN. Propagate any known information about the two SSA names into the new candidate. Return the new candidate.
Look at all interpretations of the base candidate, if necessary, to find information to propagate into this candidate.
Y = (B + i') * 1 X = Y * Z ================ X = (B + i') * Z
Y = B + (i' * S), S constant X = Y * Z ============================ X = B + ((i' * S) * Z)
No interpretations had anything useful to propagate, so produce X = (Y + 0) * Z.
References base_cand_from_table(), slsr_cand_d::base_expr, CAND_ADD, CAND_MULT, CAND_PHI, slsr_cand_d::cand_stmt, slsr_cand_d::cand_type, slsr_cand_d::dead_savings, double_int_to_tree(), has_single_use(), slsr_cand_d::index, integer_onep(), double_int::is_one(), slsr_cand_d::kind, lookup_cand(), slsr_cand_d::next_interp, stmt_cost(), slsr_cand_d::stride, and tree_to_double_int().

static 
Given a candidate C with BASIS_NAME being the LHS of C's basis which is hidden by the phi node FROM_PHI, create a new phi node in the same block as FROM_PHI. The new phi is suitable for use as a basis by C, with its phi arguments representing conditional adjustments to the hidden basis along conditional incoming paths. Those adjustments are made by creating add statements (and sometimes recursively creating phis) along those incoming paths. LOC is the location to attach to the introduced statements. KNOWN_STRIDE is true iff C's stride is a constant.
Process each argument of the existing phi that represents conditionallyexecuted add candidates.
If the phi argument is the base name of the CAND_PHI, then this incoming arc should use the hidden basis.
If there is another phi along this incoming edge, we must process it in the same fashion to ensure that all basis adjustments are made along its incoming edges.
Because of recursion, we need to save the arguments in a vector so we can create the PHI statement all at once. Otherwise the storage for the halfcreated PHI can be reclaimed.
Create the new phi basis.
Referenced by replace_rhs_if_not_dup().

static 
Dump the candidate chains.

static 
Dump the candidate vector for debug.

static 
Dump a candidate for debug.

static 
Dump the increment vector for debug.
References address_arithmetic_p, cand_increment(), and double_int::is_negative().

static 
Create the obstack where candidates will reside.
Allocate the candidate vector.
Allocate the mapping from statements to candidate indices.
Create the obstack where candidate chains will reside.
Allocate the mapping from base expressions to candidate chains.
Initialize the loop optimizer. We need to detect flow across back edges, and this gives us dominator information as well.
Walk the CFG in predominator order looking for strength reduction candidates.
Analyze costs and make appropriate replacements.
Referenced by replace_profitable_candidates().

static 
Helper routine for find_basis_for_candidate. May be called twice: once for the candidate's base expr, and optionally again for the candidate's phi definition.
References slsr_cand_d::base_expr, slsr_cand_d::basis, slsr_cand_d::cand_num, slsr_cand_d::cand_stmt, CDI_DOMINATORS, slsr_cand_d::dead_savings, slsr_cand_d::def_phi, slsr_cand_d::dependent, dominated_by_p(), gimple_bb(), gimple_phi_result(), has_single_use(), lookup_cand(), and slsr_cand_d::sibling.

static 
Use the base expr from candidate C to look for possible candidates that can serve as a basis for C. Each potential basis must also appear in a block that dominates the candidate statement and have the same stride and type. If more than one possible basis exists, the one with highest index in the vector is chosen; this will be the most immediately dominating basis.
If a candidate doesn't have a basis using its base expression, it may have a basis hidden by one or more intervening phis.
A hidden basis must dominate the phidefinition of the candidate's base name.
If we found a hidden basis, estimate additional deadcode savings if the phi and its feeding statements can be removed.

static 
Look in the candidate table for a CAND_PHI that defines BASE and return it if found; otherwise return NULL.

static 
Referenced by replace_profitable_candidates().

inlinestatic 
Return the index in the increment vector of the given INCREMENT, or 1 if not found. The latter can occur if more than MAX_INCR_VEC_LEN increments have been found.
Referenced by ncd_of_cand_and_phis().

static 
For each profitable increment in the increment vector not equal to 0 or 1 (or 1, for nonpointer arithmetic), find the nearest common dominator of all statements in the candidate chain rooted at C that require that increment, and insert an initializer T_0 = stride * increment at that location. Record T_0 with the increment record.
We may have already identified an existing initializer that will suffice.
Find the block that most closely dominates all candidates with this increment. If there is at least one candidate in that block, the earliest one will be returned in WHERE.
Create a new SSA name to hold the initializer's value.
Create the initializer and insert it in the latest possible dominating position.

static 
Referenced by replace_ref().

static 
Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of type TO_TYPE, and insert it in front of the statement represented by candidate C. Use *NEW_VAR to create the new SSA name. Return the new SSA name.

static 
Return TRUE if GS is a statement that defines an SSA name from a conversion and is legal for us to combine with an add and multiply in the candidate table. For example, suppose we have: A = B + i; C = (type) A; D = C * S; Without the typecast, we would create a CAND_MULT for D with base B, index i, and stride S. We want to record this candidate only if it is equivalent to apply the type cast following the multiply: A = B + i; E = A * S; D = (type) E; We will record the type with the candidate for D. This allows us to use a similar previous candidate as a basis. If we have earlier seen A' = B + i'; C' = (type) A'; D' = C' * S; we can replace D with D = D' + (i  i') * S; But if moving the typecast would change semantics, we mustn't do this. This is legitimate for casts from a nonwrapping integral type to any integral type of the same or larger size. It is not legitimate to convert a wrapping type to a nonwrapping type, or to a wrapping type of a different size. I.e., with a wrapping type, we must assume that the addition B + i could wrap, in which case performing the multiply before or after one of the "illegal" type casts will have different semantics.

static 
Help function for legal_cast_p, operating on two trees. Checks whether it's allowable to cast from RHS to LHS. See legal_cast_p for more details.

static 
Produce a pointer to the IDX'th candidate in the candidate vector.
References base_cand_from_table().
Referenced by analyze_increments(), create_mul_ssa_cand(), find_basis_for_base_expr(), record_phi_increments(), and replace_rhs_if_not_dup().

static 
Add COST_IN to the lowest cost of any dependent path starting at candidate C or any of its siblings, counting only candidates along such paths with increment INCR. Assume that replacing a candidate reduces cost by REPL_SAVINGS. Also account for savings from any statements that would go dead. If COUNT_PHIS is true, include costs of introducing feeding statements for conditional candidates.
Referenced by record_phi_increments().
gimple_opt_pass* make_pass_strength_reduction  (  ) 

static 
Return the nearest common dominator of BB1 and BB2. If the blocks are identical, return the earlier of C1 and C2 in *WHERE. Otherwise, if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2, return C2 in *WHERE; and if the NCD matches neither, return NULL in *WHERE. Note: It is possible for one of C1 and C2 to be NULL.
If both candidates are in the same block, the earlier candidate wins.
Otherwise, if one of them produced a candidate in the dominator, that one wins.
If neither matches the dominator, neither wins.
References slsr_cand_d::cand_stmt, double_int_to_tree(), dump_file, dump_flags, gimple_assign_rhs_code(), incr_info_d::incr, incr_vec_len, incr_info_d::initializer, double_int::is_minus_one(), double_int::is_one(), double_int::is_zero(), make_temp_ssa_name(), nearest_common_dominator_for_cands(), print_gimple_stmt(), profitable_increment_p(), and slsr_cand_d::stride.
Referenced by analyze_increments().

static 
Consider the candidate C together with any candidates that feed C's phi dependence (if any). Find and return the nearest common dominator of those candidates requiring the given increment INCR. If the returned block contains one or more of the candidates, return the earliest candidate in the block in *WHERE.
References address_arithmetic_p, all_phi_incrs_profitable(), base_cand_from_table(), slsr_cand_d::base_expr, dump_file, dump_flags, gimple_phi_arg_def(), incr_vec_index(), slsr_cand_d::index, double_int::is_negative(), and operand_equal_p().

static 
Consider all candidates that feed PHI. Find the nearest common dominator of those candidates requiring the given increment INCR. Further find and return the nearest common dominator of this result with block NCD. If the returned block contains one or more of the candidates, return the earliest candidate in the block in *WHERE.
Referenced by analyze_increments().

static 
Consider all candidates in the tree rooted at C for which INCR represents the required increment of C relative to its basis. Find and return the basic block that most nearly dominates all such candidates. If the returned block contains one or more of the candidates, return the earliest candidate in the block in *WHERE.
First find the NCD of all siblings and dependents.
If the candidate's increment doesn't match the one we're interested in (and nor do any increments for feeding defs of a phidependence), then the result depends only on siblings and dependents.
Otherwise, compare this candidate with the result from all siblings and dependents.
Referenced by ncd_for_two_cands().

static 
Return TRUE if the candidates in the tree rooted at C should be optimized for speed, else FALSE. We estimate this based on the block containing the most dominant candidate in the tree that has not yet been replaced.
References mult_by_coeff_cost().

static 
Compute the expected costs of inserting basis adjustments for candidate C with phidefinition PHI. The cost of inserting one adjustment is given by ONE_ADD_COST. If PHI has arguments which are themselves phi results, recursively calculate costs for those phis as well.
If we work our way back to a phi that isn't dominated by the hidden basis, this isn't a candidate for replacement. Indicate this by returning an unreasonably high cost. It's not easy to detect these situations when determining the basis, so we defer the decision until now.

static 
Return TRUE if candidate C is dependent upon a PHI.
A candidate is not necessarily dependent upon a PHI just because it has a phi definition for its base name. It may have a basis that relies upon the same phi definition, in which case the PHI is irrelevant to this candidate.
References slsr_cand_d::cand_stmt, dump_file, and dump_flags.
Referenced by record_phi_increments(), and replace_rhs_if_not_dup().

static 
Add up and return the costs of introducing add statements that require the increment INCR on behalf of candidate C and phi statement PHI. Accumulate into *SAVINGS the potential savings from removing existing statements that feed PHI and have no other uses.
Referenced by record_phi_increments().

inlinestatic 
Return TRUE if the increment indexed by INDEX is profitable to replace.
References slsr_cand_d::cand_stmt, gsi_for_stmt(), and operand_equal_p().
Referenced by ncd_for_two_cands().

static 
Increase the count of INCREMENT by one in the increment vector. INCREMENT is associated with candidate C. If INCREMENT is to be conditionally executed as part of a conditional candidate replacement, IS_PHI_ADJUST is true, otherwise false. If an initializer T_0 = stride * I is provided by a candidate that dominates all candidates with the same increment, also record T_0 for subsequent use.
Treat increments that differ only in sign as identical so as to share initializers, unless we are generating pointer arithmetic.
If we previously recorded an initializer that doesn't dominate this candidate, it's not going to be useful to us after all.
The first time we see an increment, create the entry for it. If this is the root candidate which doesn't have a basis, set the count to zero. We're only processing it so it can possibly provide an initializer for other candidates.
Optimistically record the first occurrence of this increment as providing an initializer (if it does); we will revise this opinion later if it doesn't dominate all other occurrences. Exception: increments of 1, 0, 1 never need initializers; and phi adjustments don't ever provide initializers.

static 
Determine how many times each unique increment occurs in the set of candidates rooted at C's parent, recording the data in the increment vector. For each unique increment I, if an initializer T_0 = stride * I is provided by a candidate that dominates all candidates with the same increment, also record T_0 for subsequent use.
A candidate with a basis hidden by a phi will have one increment for its relationship to the index represented by the phi, and potentially additional increments along each incoming edge. For the root of the dependency tree (which has no basis), process just the initial index in case it has an initializer that can be used by subsequent candidates.

static 
Given phi statement PHI that hides a candidate from its BASIS, find the increments along each incoming arc (recursively handling additional phis that may be present) and record them. These increments are the difference in index between the indexadjusting statements and the index of the basis.
References cand_abs_increment(), cand_already_replaced(), slsr_cand_d::cand_stmt, slsr_cand_d::dead_savings, slsr_cand_d::def_phi, slsr_cand_d::dependent, gimple_phi_result(), has_single_use(), lookup_cand(), lowest_cost_path(), phi_dependent_cand_p(), phi_incr_cost(), and slsr_cand_d::sibling.

static 
Record a mapping from the base expression of C to C itself, indicating that C may potentially serve as a basis using that base expression.

static 
Given a candidate C whose basis is hidden by at least one intervening phi, introduce a matching number of new phis to represent its basis adjusted by conditional increments along possible incoming paths. Then replace C as though it were an unconditional candidate, using the new basis.
Look up the LHS SSA name from C's basis. This will be the RHS1 of the adds we will introduce to create new phi arguments.
Create a new phi statement which will represent C's true basis after the transformation is complete.
Replace C with an add of the new basis phi and a constant.
References address_arithmetic_p, slsr_cand_d::cand_stmt, CDI_DOMINATORS, incr_info_d::count, dominated_by_p(), incr_vec_len, incr_info_d::init_bb, incr_info_d::initializer, and double_int::is_negative().

static 
Common logic used by replace_unconditional_candidate and replace_conditional_candidate.
It is highly unlikely, but possible, that the resulting bump doesn't fit in a HWI. Abandon the replacement in this case. This does not affect siblings or dependents of C. Restriction to signed HWI is conservative for unsigned types but allows for safe negation without twisted logic.
It is not useful to replace casts, copies, or adds of an SSA name and a constant.
If the basis name and the candidate's LHS have incompatible types, introduce a cast.

static 
Strengthreduce the statement represented by candidate C by replacing it with an equivalent addition or subtraction. I is the index into the increment vector identifying C's increment. NEW_VAR is used to create a new SSA name if a cast needs to be introduced. BASIS_NAME is the rhs1 to use in creating the add/subtract.
If the increment has an initializer T_0, replace the candidate statement with an add of the basis name and the initializer.
Otherwise, the increment is one of 1, 0, and 1. Replace with a subtract of the stride from the basis name, a copy from the basis name, or an add of the stride to the basis name, respectively. It may be necessary to introduce a cast (or reuse an existing cast).
Referenced by replace_rhs_if_not_dup().

static 
For each candidate in the tree rooted at C, replace it with an increment if such has been shown to be profitable.
Only process profitable increments. Nothing useful can be done to a cast or copy.
Look up the LHS SSA name from C's basis. This will be the RHS1 of the adds we will introduce to create new phi arguments.
Create a new phi statement that will represent C's true basis after the transformation is complete.
Replace C with an add of the new basis phi and the increment.
References opt_pass::execute(), execute_strength_reduction(), opt_pass::gate(), gate_strength_reduction(), and gimple_opt_pass::gimple_opt_pass().

static 
Replace *EXPR in candidate C with an equivalent strengthreduced data reference.
Ensure the memory reference carries the minimum alignment requirement for the data type. See PR58041.
Gimplify the base addressing expression for the new MEM_REF tree.
References slsr_cand_d::cand_stmt, double_int_to_tree(), dump_file, dump_flags, double_int::fits_shwi(), gimple_assign_lhs(), gimple_assign_rhs_code(), HOST_WIDE_INT_MIN, introduce_cast_before_cand(), double_int::is_negative(), double_int::to_shwi(), and useless_type_conversion_p().

static 
Replace CAND_REF candidate C, each sibling of candidate C, and each dependent of candidate C with an equivalent strengthreduced data reference.

static 
Replace the RHS of the statement represented by candidate C with NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't leave C unchanged or just interchange its operands. The original operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2. If the replacement was made and we are doing a details dump, return the revised statement, else NULL.
References all_phi_incrs_profitable(), slsr_cand_d::basis, slsr_cand_d::cand_stmt, create_phi_basis(), slsr_cand_d::def_phi, gimple_assign_lhs(), gimple_location(), lookup_cand(), phi_dependent_cand_p(), replace_one_candidate(), and UNKNOWN_STRIDE.

static 
For candidate C, each sibling of candidate C, and each dependent of candidate C, determine whether the candidate is dependent upon a phi that hides its basis. If not, replace the candidate unconditionally. Otherwise, determine whether the cost of introducing compensation code for the candidate is offset by the gains from strength reduction. If so, replace the candidate and introduce the compensation code.
A candidate dependent upon a phi will replace a multiply by a constant with an add, and will insert at most one add for each phi argument. Add these costs with the potential deadcode savings to determine profitability.
References incr_vec_len, incr_info_d::init_bb, and incr_info_d::initializer.

static 
Replace candidate C with an add or subtract. Note that we only operate on CAND_MULTs with known strides, so we will never generate a POINTER_PLUS_EXPR. Each candidate X = (B + i) * S is replaced by X = Y + ((i  i') * S), as described in the module commentary. The folded value ((i  i') * S) is referred to here as the "bump."

static 
Look for the following pattern: *PBASE: MEM_REF (T1, C1) *POFFSET: MULT_EXPR (T2, C3) [C2 is zero] or MULT_EXPR (PLUS_EXPR (T2, C2), C3) or MULT_EXPR (MINUS_EXPR (T2, C2), C3) *PINDEX: C4 * BITS_PER_UNIT If not present, leave the input values unchanged and return FALSE. Otherwise, modify the input values as follows and return TRUE: *PBASE: T1 *POFFSET: MULT_EXPR (T2, C3) *PINDEX: C1 + (C2 * C3) + C4 When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it will be further restructured to: *PBASE: T1 *POFFSET: MULT_EXPR (T2', C3) *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3)

static 
Given GS which is an add or subtract of scalar integers or pointers, make at least one appropriate entry in the candidate table.
First record an interpretation assuming RHS1 is the base expression and RHS2 is the stride. But it doesn't make sense for the stride to be a pointer, so don't record a candidate in that case.
Add the first interpretation to the statementcandidate mapping.
If the two RHS operands are identical, or this is a subtract, we're done.
Otherwise, record another interpretation assuming RHS2 is the base expression and RHS1 is the stride, again provided that the stride is not a pointer.
Record an interpretation for the addimmediate.
Add the interpretation to the statementcandidate mapping.

static 
Given GS which is a cast to a scalar integer type, determine whether the cast is legal for strength reduction. If so, make at least one appropriate entry in the candidate table.
Propagate all data from the base candidate except the type, which comes from the cast, and the base candidate's cast, which is no longer applicable.
If nothing is known about the RHS, create fresh CAND_ADD and CAND_MULT interpretations: X = Y + (0 * 1) X = (Y + 0) * 1 The first of these is somewhat arbitrary, but the choice of 1 for the stride simplifies the logic for propagating casts into their uses.
Add the first (or only) interpretation to the statementcandidate mapping.

static 
Given GS which is a copy of a scalar integer type, make at least one appropriate entry in the candidate table. This interface is included for completeness, but is unnecessary if this pass immediately follows a pass that performs copy propagation, such as DOM.
Propagate all data from the base candidate.
If nothing is known about the RHS, create fresh CAND_ADD and CAND_MULT interpretations: X = Y + (0 * 1) X = (Y + 0) * 1 The first of these is somewhat arbitrary, but the choice of 1 for the stride simplifies the logic for propagating casts into their uses.
Add the first (or only) interpretation to the statementcandidate mapping.

static 
Given GS which is a multiply of scalar integers, make an appropriate entry in the candidate table. If this is a multiply of two SSA names, create two CAND_MULT interpretations and attempt to find a basis for each of them. Otherwise, create a single CAND_MULT and attempt to find a basis.
If this is a multiply of an SSA name with itself, it is highly unlikely that we will get a strength reduction opportunity, so don't record it as a candidate. This simplifies the logic for finding a basis, so if this is removed that must be considered.
Record an interpretation of this statement in the candidate table assuming RHS1 is the base expression and RHS2 is the stride.
Add the first interpretation to the statementcandidate mapping.
Record another interpretation of this statement assuming RHS1 is the stride and RHS2 is the base expression.
Record an interpretation for the multiplyimmediate.
Add the interpretation to the statementcandidate mapping.

static 
Given GS which is a negate of a scalar integer, make an appropriate entry in the candidate table. A negate is equivalent to a multiply by 1.
Record a CAND_MULT interpretation for the multiply by 1.
Add the interpretation to the statementcandidate mapping.

static 
Given PHI which contains a phi statement, determine whether it satisfies all the requirements of a phi candidate. If so, create a candidate. Note that a CAND_PHI never has a basis itself, but is used to help find a basis for subsequent candidates.
A CAND_PHI requires each of its arguments to have the same derived base name. (See the module header commentary for a definition of derived base names.) Furthermore, all feeding definitions must be in the same position in the loop hierarchy as PHI.
Gather potential dead code savings if the phi statement can be removed later on.
Create the candidate. "alloc_cand_and_find_basis" is named misleadingly for this case, as no basis will be sought for a CAND_PHI.
Add the candidate to the statementcandidate mapping.

static 
Given GS which contains a data reference, create a CAND_REF entry in the candidate table and attempt to find a basis.
Add the candidate to the statementcandidate mapping.
int ssa_base_cand_dump_callback  (  ) 
Callback used to dump the candidate chains hash table.

static 
Determine the target cost of statement GS when compiling according to SPEED.
Note that we don't assign costs to copies that in most cases will go away.
References CAND_REF, slsr_cand_d::kind, and pointer_map_contains().
Referenced by create_mul_ssa_cand(), default_builtin_support_vector_misalignment(), and destroy_bb_vec_info().

static 
Compute the total savings that would accrue from all replacements in the candidate tree rooted at C, counting only candidates with increment INCR. Assume that replacing a candidate reduces cost by REPL_SAVINGS. Also account for savings from statements that would go dead.

static 
Return the first candidate in the tree rooted at C that has not already been replaced, favoring siblings over dependents.

static 
For a chain of candidates with unknown stride, indicates whether or not we must generate pointer arithmetic when replacing statements.
Referenced by analyze_increments(), dump_incr_vec(), ncd_of_cand_and_phis(), and replace_conditional_candidate().

static 
Hash table embodying a mapping from base exprs to chains of candidates.

static 
Obstack for candidates.

static 
Candidates are maintained in a vector. If candidate X dominates candidate Y, then X appears before Y in the vector; but the converse does not necessarily hold.

static 
Obstack for candidate chains.

static 
An array INCR_VEC of incr_infos is used during analysis of related candidates having an SSA name for a stride. INCR_VEC_LEN describes its current length. MAX_INCR_VEC_LEN is used to avoid costly pathological cases.

static 
const int MAX_INCR_VEC_LEN = 16 

static 
Pointer map embodying a mapping from statements to candidates.