| /* Straight-line strength reduction. |
| Copyright (C) 2012-2018 Free Software Foundation, Inc. |
| Contributed by Bill Schmidt, IBM <wschmidt@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 floating-point operations under |
| control of something like -funsafe-math-optimizations. */ |
| |
| #include "config.h" |
| #include "system.h" |
| #include "coretypes.h" |
| #include "backend.h" |
| #include "rtl.h" |
| #include "tree.h" |
| #include "gimple.h" |
| #include "cfghooks.h" |
| #include "tree-pass.h" |
| #include "ssa.h" |
| #include "expmed.h" |
| #include "gimple-pretty-print.h" |
| #include "fold-const.h" |
| #include "gimple-iterator.h" |
| #include "gimplify-me.h" |
| #include "stor-layout.h" |
| #include "cfgloop.h" |
| #include "tree-cfg.h" |
| #include "domwalk.h" |
| #include "params.h" |
| #include "tree-ssa-address.h" |
| #include "tree-affine.h" |
| #include "tree-eh.h" |
| #include "builtins.h" |
| |
| /* 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 strength-reduced (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 zero-based, |
| while cand_idx's are one-based, with zero indicating null. */ |
| typedef unsigned cand_idx; |
| |
| /* The kind of candidate. */ |
| enum cand_kind |
| { |
| CAND_MULT, |
| CAND_ADD, |
| CAND_REF, |
| CAND_PHI |
| }; |
| |
| struct slsr_cand_d |
| { |
| /* The candidate statement S1. */ |
| gimple *cand_stmt; |
| |
| /* The base expression B: often an SSA name, but not always. */ |
| tree base_expr; |
| |
| /* The stride S. */ |
| tree stride; |
| |
| /* The index constant i. */ |
| widest_int index; |
| |
| /* The type of the candidate. This is normally the type of base_expr, |
| but casts may have occurred when combining feeding instructions. |
| A candidate can only be a basis for candidates of the same final type. |
| (For CAND_REFs, this is the type to be used for operand 1 of the |
| replacement MEM_REF.) */ |
| tree cand_type; |
| |
| /* The type to be used to interpret the stride field when the stride |
| is not a constant. Normally the same as the type of the recorded |
| stride, but when the stride has been cast we need to maintain that |
| knowledge in order to make legal substitutions without losing |
| precision. When the stride is a constant, this will be sizetype. */ |
| tree stride_type; |
| |
| /* The kind of candidate (CAND_MULT, etc.). */ |
| enum cand_kind kind; |
| |
| /* Index of this candidate in the candidate vector. */ |
| cand_idx cand_num; |
| |
| /* Index of the next candidate record for the same statement. |
| A statement may be useful in more than one way (e.g., due to |
| commutativity). So we can have multiple "interpretations" |
| of a statement. */ |
| cand_idx next_interp; |
| |
| /* Index of the first candidate record in a chain for the same |
| statement. */ |
| cand_idx first_interp; |
| |
| /* Index of the basis statement S0, if any, in the candidate vector. */ |
| cand_idx basis; |
| |
| /* First candidate for which this candidate is a basis, if one exists. */ |
| cand_idx dependent; |
| |
| /* Next candidate having the same basis as this one. */ |
| cand_idx sibling; |
| |
| /* If this is a conditional candidate, the CAND_PHI candidate |
| that defines the base SSA name B. */ |
| cand_idx def_phi; |
| |
| /* Savings that can be expected from eliminating dead code if this |
| candidate is replaced. */ |
| int dead_savings; |
| |
| /* For PHI candidates, use a visited flag to keep from processing the |
| same PHI twice from multiple paths. */ |
| int visited; |
| |
| /* We sometimes have to cache a phi basis with a phi candidate to |
| avoid processing it twice. Valid only if visited==1. */ |
| tree cached_basis; |
| }; |
| |
| typedef struct slsr_cand_d slsr_cand, *slsr_cand_t; |
| typedef const struct slsr_cand_d *const_slsr_cand_t; |
| |
| /* Pointers to candidates are chained together as part of a mapping |
| from base expressions to the candidates that use them. */ |
| |
| struct cand_chain_d |
| { |
| /* Base expression for the chain of candidates: often, but not |
| always, an SSA name. */ |
| tree base_expr; |
| |
| /* Pointer to a candidate. */ |
| slsr_cand_t cand; |
| |
| /* Chain pointer. */ |
| struct cand_chain_d *next; |
| |
| }; |
| |
| typedef struct cand_chain_d cand_chain, *cand_chain_t; |
| typedef const struct cand_chain_d *const_cand_chain_t; |
| |
| /* Information about a unique "increment" associated with candidates |
| having an SSA name for a stride. An increment is the difference |
| between the index of the candidate and the index of its basis, |
| i.e., (i - i') as discussed in the module commentary. |
| |
| When we are not going to generate address arithmetic we treat |
| increments that differ only in sign as the same, allowing sharing |
| of the cost of initializers. The absolute value of the increment |
| is stored in the incr_info. */ |
| |
| struct incr_info_d |
| { |
| /* The increment that relates a candidate to its basis. */ |
| widest_int incr; |
| |
| /* How many times the increment occurs in the candidate tree. */ |
| unsigned count; |
| |
| /* Cost of replacing candidates using this increment. Negative and |
| zero costs indicate replacement should be performed. */ |
| int cost; |
| |
| /* If this increment is profitable but is not -1, 0, or 1, it requires |
| an initializer T_0 = stride * incr to be found or introduced in the |
| nearest common dominator of all candidates. This field holds T_0 |
| for subsequent use. */ |
| tree initializer; |
| |
| /* If the initializer was found to already exist, this is the block |
| where it was found. */ |
| basic_block init_bb; |
| }; |
| |
| typedef struct incr_info_d incr_info, *incr_info_t; |
| |
| /* 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 vec<slsr_cand_t> cand_vec; |
| |
| 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 |
| }; |
| |
| /* Constrain how many PHI nodes we will visit for a conditional |
| candidate (depth and breadth). */ |
| const int MAX_SPREAD = 16; |
| |
| /* Pointer map embodying a mapping from statements to candidates. */ |
| static hash_map<gimple *, slsr_cand_t> *stmt_cand_map; |
| |
| /* Obstack for candidates. */ |
| static struct obstack cand_obstack; |
| |
| /* Obstack for candidate chains. */ |
| static struct obstack chain_obstack; |
| |
| /* 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 incr_info_t incr_vec; |
| static unsigned incr_vec_len; |
| const int MAX_INCR_VEC_LEN = 16; |
| |
| /* For a chain of candidates with unknown stride, indicates whether or not |
| we must generate pointer arithmetic when replacing statements. */ |
| static bool address_arithmetic_p; |
| |
| /* Forward function declarations. */ |
| static slsr_cand_t base_cand_from_table (tree); |
| static tree introduce_cast_before_cand (slsr_cand_t, tree, tree); |
| static bool legal_cast_p_1 (tree, tree); |
| |
| /* Produce a pointer to the IDX'th candidate in the candidate vector. */ |
| |
| static slsr_cand_t |
| lookup_cand (cand_idx idx) |
| { |
| return cand_vec[idx - 1]; |
| } |
| |
| /* Helper for hashing a candidate chain header. */ |
| |
| struct cand_chain_hasher : nofree_ptr_hash <cand_chain> |
| { |
| static inline hashval_t hash (const cand_chain *); |
| static inline bool equal (const cand_chain *, const cand_chain *); |
| }; |
| |
| inline hashval_t |
| cand_chain_hasher::hash (const cand_chain *p) |
| { |
| tree base_expr = p->base_expr; |
| return iterative_hash_expr (base_expr, 0); |
| } |
| |
| inline bool |
| cand_chain_hasher::equal (const cand_chain *chain1, const cand_chain *chain2) |
| { |
| return operand_equal_p (chain1->base_expr, chain2->base_expr, 0); |
| } |
| |
| /* Hash table embodying a mapping from base exprs to chains of candidates. */ |
| static hash_table<cand_chain_hasher> *base_cand_map; |
| |
| /* Pointer map used by tree_to_aff_combination_expand. */ |
| static hash_map<tree, name_expansion *> *name_expansions; |
| /* Pointer map embodying a mapping from bases to alternative bases. */ |
| static hash_map<tree, tree> *alt_base_map; |
| |
| /* Given BASE, use the tree affine combiniation facilities to |
| find the underlying tree expression for BASE, with any |
| immediate offset excluded. |
| |
| N.B. we should eliminate this backtracking with better forward |
| analysis in a future release. */ |
| |
| static tree |
| get_alternative_base (tree base) |
| { |
| tree *result = alt_base_map->get (base); |
| |
| if (result == NULL) |
| { |
| tree expr; |
| aff_tree aff; |
| |
| tree_to_aff_combination_expand (base, TREE_TYPE (base), |
| &aff, &name_expansions); |
| aff.offset = 0; |
| expr = aff_combination_to_tree (&aff); |
| |
| gcc_assert (!alt_base_map->put (base, base == expr ? NULL : expr)); |
| |
| return expr == base ? NULL : expr; |
| } |
| |
| return *result; |
| } |
| |
| /* Look in the candidate table for a CAND_PHI that defines BASE and |
| return it if found; otherwise return NULL. */ |
| |
| static cand_idx |
| find_phi_def (tree base) |
| { |
| slsr_cand_t c; |
| |
| if (TREE_CODE (base) != SSA_NAME) |
| return 0; |
| |
| c = base_cand_from_table (base); |
| |
| if (!c || c->kind != CAND_PHI |
| || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (c->cand_stmt))) |
| return 0; |
| |
| return c->cand_num; |
| } |
| |
| /* Determine whether all uses of NAME are directly or indirectly |
| used by STMT. That is, we want to know whether if STMT goes |
| dead, the definition of NAME also goes dead. */ |
| static bool |
| uses_consumed_by_stmt (tree name, gimple *stmt, unsigned recurse = 0) |
| { |
| gimple *use_stmt; |
| imm_use_iterator iter; |
| bool retval = true; |
| |
| FOR_EACH_IMM_USE_STMT (use_stmt, iter, name) |
| { |
| if (use_stmt == stmt || is_gimple_debug (use_stmt)) |
| continue; |
| |
| if (!is_gimple_assign (use_stmt) |
| || !gimple_get_lhs (use_stmt) |
| || !is_gimple_reg (gimple_get_lhs (use_stmt)) |
| || recurse >= 10 |
| || !uses_consumed_by_stmt (gimple_get_lhs (use_stmt), stmt, |
| recurse + 1)) |
| { |
| retval = false; |
| BREAK_FROM_IMM_USE_STMT (iter); |
| } |
| } |
| |
| return retval; |
| } |
| |
| /* Helper routine for find_basis_for_candidate. May be called twice: |
| once for the candidate's base expr, and optionally again either for |
| the candidate's phi definition or for a CAND_REF's alternative base |
| expression. */ |
| |
| static slsr_cand_t |
| find_basis_for_base_expr (slsr_cand_t c, tree base_expr) |
| { |
| cand_chain mapping_key; |
| cand_chain_t chain; |
| slsr_cand_t basis = NULL; |
| |
| // Limit potential of N^2 behavior for long candidate chains. |
| int iters = 0; |
| int max_iters = PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN); |
| |
| mapping_key.base_expr = base_expr; |
| chain = base_cand_map->find (&mapping_key); |
| |
| for (; chain && iters < max_iters; chain = chain->next, ++iters) |
| { |
| slsr_cand_t one_basis = chain->cand; |
| |
| if (one_basis->kind != c->kind |
| || one_basis->cand_stmt == c->cand_stmt |
| || !operand_equal_p (one_basis->stride, c->stride, 0) |
| || !types_compatible_p (one_basis->cand_type, c->cand_type) |
| || !types_compatible_p (one_basis->stride_type, c->stride_type) |
| || !dominated_by_p (CDI_DOMINATORS, |
| gimple_bb (c->cand_stmt), |
| gimple_bb (one_basis->cand_stmt))) |
| continue; |
| |
| tree lhs = gimple_assign_lhs (one_basis->cand_stmt); |
| if (lhs && TREE_CODE (lhs) == SSA_NAME |
| && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) |
| continue; |
| |
| if (!basis || basis->cand_num < one_basis->cand_num) |
| basis = one_basis; |
| } |
| |
| return basis; |
| } |
| |
| /* 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. */ |
| |
| static int |
| find_basis_for_candidate (slsr_cand_t c) |
| { |
| slsr_cand_t basis = find_basis_for_base_expr (c, c->base_expr); |
| |
| /* If a candidate doesn't have a basis using its base expression, |
| it may have a basis hidden by one or more intervening phis. */ |
| if (!basis && c->def_phi) |
| { |
| basic_block basis_bb, phi_bb; |
| slsr_cand_t phi_cand = lookup_cand (c->def_phi); |
| basis = find_basis_for_base_expr (c, phi_cand->base_expr); |
| |
| if (basis) |
| { |
| /* A hidden basis must dominate the phi-definition of the |
| candidate's base name. */ |
| phi_bb = gimple_bb (phi_cand->cand_stmt); |
| basis_bb = gimple_bb (basis->cand_stmt); |
| |
| if (phi_bb == basis_bb |
| || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb)) |
| { |
| basis = NULL; |
| c->basis = 0; |
| } |
| |
| /* If we found a hidden basis, estimate additional dead-code |
| savings if the phi and its feeding statements can be removed. */ |
| tree feeding_var = gimple_phi_result (phi_cand->cand_stmt); |
| if (basis && uses_consumed_by_stmt (feeding_var, c->cand_stmt)) |
| c->dead_savings += phi_cand->dead_savings; |
| } |
| } |
| |
| if (flag_expensive_optimizations && !basis && c->kind == CAND_REF) |
| { |
| tree alt_base_expr = get_alternative_base (c->base_expr); |
| if (alt_base_expr) |
| basis = find_basis_for_base_expr (c, alt_base_expr); |
| } |
| |
| if (basis) |
| { |
| c->sibling = basis->dependent; |
| basis->dependent = c->cand_num; |
| return basis->cand_num; |
| } |
| |
| return 0; |
| } |
| |
| /* Record a mapping from BASE to C, indicating that C may potentially serve |
| as a basis using that base expression. BASE may be the same as |
| C->BASE_EXPR; alternatively BASE can be a different tree that share the |
| underlining expression of C->BASE_EXPR. */ |
| |
| static void |
| record_potential_basis (slsr_cand_t c, tree base) |
| { |
| cand_chain_t node; |
| cand_chain **slot; |
| |
| gcc_assert (base); |
| |
| node = (cand_chain_t) obstack_alloc (&chain_obstack, sizeof (cand_chain)); |
| node->base_expr = base; |
| node->cand = c; |
| node->next = NULL; |
| slot = base_cand_map->find_slot (node, INSERT); |
| |
| if (*slot) |
| { |
| cand_chain_t head = (cand_chain_t) (*slot); |
| node->next = head->next; |
| head->next = node; |
| } |
| else |
| *slot = node; |
| } |
| |
| /* Allocate storage for a new candidate and initialize its fields. |
| Attempt to find a basis for the candidate. |
| |
| For CAND_REF, an alternative base may also be recorded and used |
| to find a basis. This helps cases where the expression hidden |
| behind BASE (which is usually an SSA_NAME) has immediate offset, |
| e.g. |
| |
| a2[i][j] = 1; |
| a2[i + 20][j] = 2; */ |
| |
| static slsr_cand_t |
| alloc_cand_and_find_basis (enum cand_kind kind, gimple *gs, tree base, |
| const widest_int &index, tree stride, tree ctype, |
| tree stype, unsigned savings) |
| { |
| slsr_cand_t c = (slsr_cand_t) obstack_alloc (&cand_obstack, |
| sizeof (slsr_cand)); |
| c->cand_stmt = gs; |
| c->base_expr = base; |
| c->stride = stride; |
| c->index = index; |
| c->cand_type = ctype; |
| c->stride_type = stype; |
| c->kind = kind; |
| c->cand_num = cand_vec.length () + 1; |
| c->next_interp = 0; |
| c->first_interp = c->cand_num; |
| c->dependent = 0; |
| c->sibling = 0; |
| c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0; |
| c->dead_savings = savings; |
| c->visited = 0; |
| c->cached_basis = NULL_TREE; |
| |
| cand_vec.safe_push (c); |
| |
| if (kind == CAND_PHI) |
| c->basis = 0; |
| else |
| c->basis = find_basis_for_candidate (c); |
| |
| record_potential_basis (c, base); |
| if (flag_expensive_optimizations && kind == CAND_REF) |
| { |
| tree alt_base = get_alternative_base (base); |
| if (alt_base) |
| record_potential_basis (c, alt_base); |
| } |
| |
| return c; |
| } |
| |
| /* Determine the target cost of statement GS when compiling according |
| to SPEED. */ |
| |
| static int |
| stmt_cost (gimple *gs, bool speed) |
| { |
| tree lhs, rhs1, rhs2; |
| machine_mode lhs_mode; |
| |
| gcc_assert (is_gimple_assign (gs)); |
| lhs = gimple_assign_lhs (gs); |
| rhs1 = gimple_assign_rhs1 (gs); |
| lhs_mode = TYPE_MODE (TREE_TYPE (lhs)); |
| |
| switch (gimple_assign_rhs_code (gs)) |
| { |
| case MULT_EXPR: |
| rhs2 = gimple_assign_rhs2 (gs); |
| |
| if (tree_fits_shwi_p (rhs2)) |
| return mult_by_coeff_cost (tree_to_shwi (rhs2), lhs_mode, speed); |
| |
| gcc_assert (TREE_CODE (rhs1) != INTEGER_CST); |
| return mul_cost (speed, lhs_mode); |
| |
| case PLUS_EXPR: |
| case POINTER_PLUS_EXPR: |
| case MINUS_EXPR: |
| return add_cost (speed, lhs_mode); |
| |
| case NEGATE_EXPR: |
| return neg_cost (speed, lhs_mode); |
| |
| CASE_CONVERT: |
| return convert_cost (lhs_mode, TYPE_MODE (TREE_TYPE (rhs1)), speed); |
| |
| /* Note that we don't assign costs to copies that in most cases |
| will go away. */ |
| case SSA_NAME: |
| return 0; |
| |
| default: |
| ; |
| } |
| |
| gcc_unreachable (); |
| return 0; |
| } |
| |
| /* 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. */ |
| |
| static slsr_cand_t |
| base_cand_from_table (tree base_in) |
| { |
| slsr_cand_t *result; |
| |
| gimple *def = SSA_NAME_DEF_STMT (base_in); |
| if (!def) |
| return (slsr_cand_t) NULL; |
| |
| result = stmt_cand_map->get (def); |
| |
| if (result && (*result)->kind != CAND_REF) |
| return *result; |
| |
| return (slsr_cand_t) NULL; |
| } |
| |
| /* Add an entry to the statement-to-candidate mapping. */ |
| |
| static void |
| add_cand_for_stmt (gimple *gs, slsr_cand_t c) |
| { |
| gcc_assert (!stmt_cand_map->put (gs, c)); |
| } |
| |
| /* 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. */ |
| |
| static void |
| slsr_process_phi (gphi *phi, bool speed) |
| { |
| unsigned i; |
| tree arg0_base = NULL_TREE, base_type; |
| slsr_cand_t c; |
| struct loop *cand_loop = gimple_bb (phi)->loop_father; |
| unsigned savings = 0; |
| |
| /* 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. */ |
| |
| for (i = 0; i < gimple_phi_num_args (phi); i++) |
| { |
| slsr_cand_t arg_cand; |
| tree arg = gimple_phi_arg_def (phi, i); |
| tree derived_base_name = NULL_TREE; |
| gimple *arg_stmt = NULL; |
| basic_block arg_bb = NULL; |
| |
| if (TREE_CODE (arg) != SSA_NAME) |
| return; |
| |
| arg_cand = base_cand_from_table (arg); |
| |
| if (arg_cand) |
| { |
| while (arg_cand->kind != CAND_ADD && arg_cand->kind != CAND_PHI) |
| { |
| if (!arg_cand->next_interp) |
| return; |
| |
| arg_cand = lookup_cand (arg_cand->next_interp); |
| } |
| |
| if (!integer_onep (arg_cand->stride)) |
| return; |
| |
| derived_base_name = arg_cand->base_expr; |
| arg_stmt = arg_cand->cand_stmt; |
| arg_bb = gimple_bb (arg_stmt); |
| |
| /* Gather potential dead code savings if the phi statement |
| can be removed later on. */ |
| if (uses_consumed_by_stmt (arg, phi)) |
| { |
| if (gimple_code (arg_stmt) == GIMPLE_PHI) |
| savings += arg_cand->dead_savings; |
| else |
| savings += stmt_cost (arg_stmt, speed); |
| } |
| } |
| else if (SSA_NAME_IS_DEFAULT_DEF (arg)) |
| { |
| derived_base_name = arg; |
| arg_bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); |
| } |
| |
| if (!arg_bb || arg_bb->loop_father != cand_loop) |
| return; |
| |
| if (i == 0) |
| arg0_base = derived_base_name; |
| else if (!operand_equal_p (derived_base_name, arg0_base, 0)) |
| return; |
| } |
| |
| /* Create the candidate. "alloc_cand_and_find_basis" is named |
| misleadingly for this case, as no basis will be sought for a |
| CAND_PHI. */ |
| base_type = TREE_TYPE (arg0_base); |
| |
| c = alloc_cand_and_find_basis (CAND_PHI, phi, arg0_base, |
| 0, integer_one_node, base_type, |
| sizetype, savings); |
| |
| /* Add the candidate to the statement-candidate mapping. */ |
| add_cand_for_stmt (phi, c); |
| } |
| |
| /* 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. */ |
| |
| static widest_int |
| backtrace_base_for_ref (tree *pbase) |
| { |
| tree base_in = *pbase; |
| slsr_cand_t base_cand; |
| |
| STRIP_NOPS (base_in); |
| |
| /* Strip off widening conversion(s) to handle cases where |
| e.g. 'B' is widened from an 'int' in order to calculate |
| a 64-bit address. */ |
| if (CONVERT_EXPR_P (base_in) |
| && legal_cast_p_1 (TREE_TYPE (base_in), |
| TREE_TYPE (TREE_OPERAND (base_in, 0)))) |
| base_in = get_unwidened (base_in, NULL_TREE); |
| |
| if (TREE_CODE (base_in) != SSA_NAME) |
| return 0; |
| |
| base_cand = base_cand_from_table (base_in); |
| |
| while (base_cand && base_cand->kind != CAND_PHI) |
| { |
| if (base_cand->kind == CAND_ADD |
| && base_cand->index == 1 |
| && TREE_CODE (base_cand->stride) == INTEGER_CST) |
| { |
| /* X = B + (1 * S), S is integer constant. */ |
| *pbase = base_cand->base_expr; |
| return wi::to_widest (base_cand->stride); |
| } |
| else if (base_cand->kind == CAND_ADD |
| && TREE_CODE (base_cand->stride) == INTEGER_CST |
| && integer_onep (base_cand->stride)) |
| { |
| /* X = B + (i * S), S is integer one. */ |
| *pbase = base_cand->base_expr; |
| return base_cand->index; |
| } |
| |
| if (base_cand->next_interp) |
| base_cand = lookup_cand (base_cand->next_interp); |
| else |
| base_cand = NULL; |
| } |
| |
| return 0; |
| } |
| |
| /* 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 bool |
| restructure_reference (tree *pbase, tree *poffset, widest_int *pindex, |
| tree *ptype) |
| { |
| tree base = *pbase, offset = *poffset; |
| widest_int index = *pindex; |
| tree mult_op0, t1, t2, type; |
| widest_int c1, c2, c3, c4, c5; |
| offset_int mem_offset; |
| |
| if (!base |
| || !offset |
| || TREE_CODE (base) != MEM_REF |
| || !mem_ref_offset (base).is_constant (&mem_offset) |
| || TREE_CODE (offset) != MULT_EXPR |
| || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST |
| || wi::umod_floor (index, BITS_PER_UNIT) != 0) |
| return false; |
| |
| t1 = TREE_OPERAND (base, 0); |
| c1 = widest_int::from (mem_offset, SIGNED); |
| type = TREE_TYPE (TREE_OPERAND (base, 1)); |
| |
| mult_op0 = TREE_OPERAND (offset, 0); |
| c3 = wi::to_widest (TREE_OPERAND (offset, 1)); |
| |
| if (TREE_CODE (mult_op0) == PLUS_EXPR) |
| |
| if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST) |
| { |
| t2 = TREE_OPERAND (mult_op0, 0); |
| c2 = wi::to_widest (TREE_OPERAND (mult_op0, 1)); |
| } |
| else |
| return false; |
| |
| else if (TREE_CODE (mult_op0) == MINUS_EXPR) |
| |
| if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST) |
| { |
| t2 = TREE_OPERAND (mult_op0, 0); |
| c2 = -wi::to_widest (TREE_OPERAND (mult_op0, 1)); |
| } |
| else |
| return false; |
| |
| else |
| { |
| t2 = mult_op0; |
| c2 = 0; |
| } |
| |
| c4 = index >> LOG2_BITS_PER_UNIT; |
| c5 = backtrace_base_for_ref (&t2); |
| |
| *pbase = t1; |
| *poffset = fold_build2 (MULT_EXPR, sizetype, fold_convert (sizetype, t2), |
| wide_int_to_tree (sizetype, c3)); |
| *pindex = c1 + c2 * c3 + c4 + c5 * c3; |
| *ptype = type; |
| |
| return true; |
| } |
| |
| /* Given GS which contains a data reference, create a CAND_REF entry in |
| the candidate table and attempt to find a basis. */ |
| |
| static void |
| slsr_process_ref (gimple *gs) |
| { |
| tree ref_expr, base, offset, type; |
| poly_int64 bitsize, bitpos; |
| machine_mode mode; |
| int unsignedp, reversep, volatilep; |
| slsr_cand_t c; |
| |
| if (gimple_vdef (gs)) |
| ref_expr = gimple_assign_lhs (gs); |
| else |
| ref_expr = gimple_assign_rhs1 (gs); |
| |
| if (!handled_component_p (ref_expr) |
| || TREE_CODE (ref_expr) == BIT_FIELD_REF |
| || (TREE_CODE (ref_expr) == COMPONENT_REF |
| && DECL_BIT_FIELD (TREE_OPERAND (ref_expr, 1)))) |
| return; |
| |
| base = get_inner_reference (ref_expr, &bitsize, &bitpos, &offset, &mode, |
| &unsignedp, &reversep, &volatilep); |
| HOST_WIDE_INT cbitpos; |
| if (reversep || !bitpos.is_constant (&cbitpos)) |
| return; |
| widest_int index = cbitpos; |
| |
| if (!restructure_reference (&base, &offset, &index, &type)) |
| return; |
| |
| c = alloc_cand_and_find_basis (CAND_REF, gs, base, index, offset, |
| type, sizetype, 0); |
| |
| /* Add the candidate to the statement-candidate mapping. */ |
| add_cand_for_stmt (gs, c); |
| } |
| |
| /* 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. */ |
| |
| static slsr_cand_t |
| create_mul_ssa_cand (gimple *gs, tree base_in, tree stride_in, bool speed) |
| { |
| tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE; |
| tree stype = NULL_TREE; |
| widest_int index; |
| unsigned savings = 0; |
| slsr_cand_t c; |
| slsr_cand_t base_cand = base_cand_from_table (base_in); |
| |
| /* Look at all interpretations of the base candidate, if necessary, |
| to find information to propagate into this candidate. */ |
| while (base_cand && !base && base_cand->kind != CAND_PHI) |
| { |
| |
| if (base_cand->kind == CAND_MULT && integer_onep (base_cand->stride)) |
| { |
| /* Y = (B + i') * 1 |
| X = Y * Z |
| ================ |
| X = (B + i') * Z */ |
| base = base_cand->base_expr; |
| index = base_cand->index; |
| stride = stride_in; |
| ctype = base_cand->cand_type; |
| stype = TREE_TYPE (stride_in); |
| if (has_single_use (base_in)) |
| savings = (base_cand->dead_savings |
| + stmt_cost (base_cand->cand_stmt, speed)); |
| } |
| else if (base_cand->kind == CAND_ADD |
| && TREE_CODE (base_cand->stride) == INTEGER_CST) |
| { |
| /* Y = B + (i' * S), S constant |
| X = Y * Z |
| ============================ |
| X = B + ((i' * S) * Z) */ |
| base = base_cand->base_expr; |
| index = base_cand->index * wi::to_widest (base_cand->stride); |
| stride = stride_in; |
| ctype = base_cand->cand_type; |
| stype = TREE_TYPE (stride_in); |
| if (has_single_use (base_in)) |
| savings = (base_cand->dead_savings |
| + stmt_cost (base_cand->cand_stmt, speed)); |
| } |
| |
| if (base_cand->next_interp) |
| base_cand = lookup_cand (base_cand->next_interp); |
| else |
| base_cand = NULL; |
| } |
| |
| if (!base) |
| { |
| /* No interpretations had anything useful to propagate, so |
| produce X = (Y + 0) * Z. */ |
| base = base_in; |
| index = 0; |
| stride = stride_in; |
| ctype = TREE_TYPE (base_in); |
| stype = TREE_TYPE (stride_in); |
| } |
| |
| c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride, |
| ctype, stype, savings); |
| return c; |
| } |
| |
| /* 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. */ |
| |
| static slsr_cand_t |
| create_mul_imm_cand (gimple *gs, tree base_in, tree stride_in, bool speed) |
| { |
| tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE; |
| widest_int index, temp; |
| unsigned savings = 0; |
| slsr_cand_t c; |
| slsr_cand_t base_cand = base_cand_from_table (base_in); |
| |
| /* Look at all interpretations of the base candidate, if necessary, |
| to find information to propagate into this candidate. */ |
| while (base_cand && !base && base_cand->kind != CAND_PHI) |
| { |
| if (base_cand->kind == CAND_MULT |
| && TREE_CODE (base_cand->stride) == INTEGER_CST) |
| { |
| /* Y = (B + i') * S, S constant |
| X = Y * c |
| ============================ |
| X = (B + i') * (S * c) */ |
| temp = wi::to_widest (base_cand->stride) * wi::to_widest (stride_in); |
| if (wi::fits_to_tree_p (temp, TREE_TYPE (stride_in))) |
| { |
| base = base_cand->base_expr; |
| index = base_cand->index; |
| stride = wide_int_to_tree (TREE_TYPE (stride_in), temp); |
| ctype = base_cand->cand_type; |
| if (has_single_use (base_in)) |
| savings = (base_cand->dead_savings |
| + stmt_cost (base_cand->cand_stmt, speed)); |
| } |
| } |
| else if (base_cand->kind == CAND_ADD && integer_onep (base_cand->stride)) |
| { |
| /* Y = B + (i' * 1) |
| X = Y * c |
| =========================== |
| X = (B + i') * c */ |
| base = base_cand->base_expr; |
| index = base_cand->index; |
| stride = stride_in; |
| ctype = base_cand->cand_type; |
| if (has_single_use (base_in)) |
| savings = (base_cand->dead_savings |
| + stmt_cost (base_cand->cand_stmt, speed)); |
| } |
| else if (base_cand->kind == CAND_ADD |
| && base_cand->index == 1 |
| && TREE_CODE (base_cand->stride) == INTEGER_CST) |
| { |
| /* Y = B + (1 * S), S constant |
| X = Y * c |
| =========================== |
| X = (B + S) * c */ |
| base = base_cand->base_expr; |
| index = wi::to_widest (base_cand->stride); |
| stride = stride_in; |
| ctype = base_cand->cand_type; |
| if (has_single_use (base_in)) |
| savings = (base_cand->dead_savings |
| + stmt_cost (base_cand->cand_stmt, speed)); |
| } |
| |
| if (base_cand->next_interp) |
| base_cand = lookup_cand (base_cand->next_interp); |
| else |
| base_cand = NULL; |
| } |
| |
| if (!base) |
| { |
| /* No interpretations had anything useful to propagate, so |
| produce X = (Y + 0) * c. */ |
| base = base_in; |
| index = 0; |
| stride = stride_in; |
| ctype = TREE_TYPE (base_in); |
| } |
| |
| c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride, |
| ctype, sizetype, savings); |
| return c; |
| } |
| |
| /* 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. */ |
| |
| static void |
| slsr_process_mul (gimple *gs, tree rhs1, tree rhs2, bool speed) |
| { |
| slsr_cand_t c, c2; |
| |
| /* 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. */ |
| if (rhs1 == rhs2) |
| return; |
| |
| if (TREE_CODE (rhs2) == SSA_NAME) |
| { |
| /* Record an interpretation of this statement in the candidate table |
| assuming RHS1 is the base expression and RHS2 is the stride. */ |
| c = create_mul_ssa_cand (gs, rhs1, rhs2, speed); |
| |
| /* Add the first interpretation to the statement-candidate mapping. */ |
| add_cand_for_stmt (gs, c); |
| |
| /* Record another interpretation of this statement assuming RHS1 |
| is the stride and RHS2 is the base expression. */ |
| c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed); |
| c->next_interp = c2->cand_num; |
| c2->first_interp = c->cand_num; |
| } |
| else if (TREE_CODE (rhs2) == INTEGER_CST) |
| { |
| /* Record an interpretation for the multiply-immediate. */ |
| c = create_mul_imm_cand (gs, rhs1, rhs2, speed); |
| |
| /* Add the interpretation to the statement-candidate mapping. */ |
| add_cand_for_stmt (gs, c); |
| } |
| } |
| |
| /* 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. */ |
| |
| static slsr_cand_t |
| create_add_ssa_cand (gimple *gs, tree base_in, tree addend_in, |
| bool subtract_p, bool speed) |
| { |
| tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE; |
| tree stype = NULL_TREE; |
| widest_int index; |
| unsigned savings = 0; |
| slsr_cand_t c; |
| slsr_cand_t base_cand = base_cand_from_table (base_in); |
| slsr_cand_t addend_cand = base_cand_from_table (addend_in); |
| |
| /* The most useful transformation is a multiply-immediate feeding |
| an add or subtract. Look for that first. */ |
| while (addend_cand && !base && addend_cand->kind != CAND_PHI) |
| { |
| if (addend_cand->kind == CAND_MULT |
| && addend_cand->index == 0 |
| && TREE_CODE (addend_cand->stride) == INTEGER_CST) |
| { |
| /* Z = (B + 0) * S, S constant |
| X = Y +/- Z |
| =========================== |
| X = Y + ((+/-1 * S) * B) */ |
| base = base_in; |
| index = wi::to_widest (addend_cand->stride); |
| if (subtract_p) |
| index = -index; |
| stride = addend_cand->base_expr; |
| ctype = TREE_TYPE (base_in); |
| stype = addend_cand->cand_type; |
| if (has_single_use (addend_in)) |
| savings = (addend_cand->dead_savings |
| + stmt_cost (addend_cand->cand_stmt, speed)); |
| } |
| |
| if (addend_cand->next_interp) |
| addend_cand = lookup_cand (addend_cand->next_interp); |
| else |
| addend_cand = NULL; |
| } |
| |
| while (base_cand && !base && base_cand->kind != CAND_PHI) |
| { |
| if (base_cand->kind == CAND_ADD |
| && (base_cand->index == 0 |
| || operand_equal_p (base_cand->stride, |
| integer_zero_node, 0))) |
| { |
| /* Y = B + (i' * S), i' * S = 0 |
| X = Y +/- Z |
| ============================ |
| X = B + (+/-1 * Z) */ |
| base = base_cand->base_expr; |
| index = subtract_p ? -1 : 1; |
| stride = addend_in; |
| ctype = base_cand->cand_type; |
| stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype |
| : TREE_TYPE (addend_in)); |
| if (has_single_use (base_in)) |
| savings = (base_cand->dead_savings |
| + stmt_cost (base_cand->cand_stmt, speed)); |
| } |
| else if (subtract_p) |
| { |
| slsr_cand_t subtrahend_cand = base_cand_from_table (addend_in); |
| |
| while (subtrahend_cand && !base && subtrahend_cand->kind != CAND_PHI) |
| { |
| if (subtrahend_cand->kind == CAND_MULT |
| && subtrahend_cand->index == 0 |
| && TREE_CODE (subtrahend_cand->stride) == INTEGER_CST) |
| { |
| /* Z = (B + 0) * S, S constant |
| X = Y - Z |
| =========================== |
| Value: X = Y + ((-1 * S) * B) */ |
| base = base_in; |
| index = wi::to_widest (subtrahend_cand->stride); |
| index = -index; |
| stride = subtrahend_cand->base_expr; |
| ctype = TREE_TYPE (base_in); |
| stype = subtrahend_cand->cand_type; |
| if (has_single_use (addend_in)) |
| savings = (subtrahend_cand->dead_savings |
| + stmt_cost (subtrahend_cand->cand_stmt, speed)); |
| } |
| |
| if (subtrahend_cand->next_interp) |
| subtrahend_cand = lookup_cand (subtrahend_cand->next_interp); |
| else |
| subtrahend_cand = NULL; |
| } |
| } |
| |
| if (base_cand->next_interp) |
| base_cand = lookup_cand (base_cand->next_interp); |
| else |
| base_cand = NULL; |
| } |
| |
| if (!base) |
| { |
| /* No interpretations had anything useful to propagate, so |
| produce X = Y + (1 * Z). */ |
| base = base_in; |
| index = subtract_p ? -1 : 1; |
| stride = addend_in; |
| ctype = TREE_TYPE (base_in); |
| stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype |
| : TREE_TYPE (addend_in)); |
| } |
| |
| c = alloc_cand_and_find_basis (CAND_ADD, gs, base, index, stride, |
| ctype, stype, savings); |
| return c; |
| } |
| |
| /* 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. */ |
| |
| static slsr_cand_t |
| create_add_imm_cand (gimple *gs, tree base_in, const widest_int &index_in, |
| bool speed) |
| { |
| enum cand_kind kind = CAND_ADD; |
| tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE; |
| tree stype = NULL_TREE; |
| widest_int index, multiple; |
| unsigned savings = 0; |
| slsr_cand_t c; |
| slsr_cand_t base_cand = base_cand_from_table (base_in); |
| |
| while (base_cand && !base && base_cand->kind != CAND_PHI) |
| { |
| signop sign = TYPE_SIGN (TREE_TYPE (base_cand->stride)); |
| |
| if (TREE_CODE (base_cand->stride) == INTEGER_CST |
| && wi::multiple_of_p (index_in, wi::to_widest (base_cand->stride), |
| sign, &multiple)) |
| { |
| /* 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 */ |
| kind = base_cand->kind; |
| base = base_cand->base_expr; |
| index = base_cand->index + multiple; |
| stride = base_cand->stride; |
| ctype = base_cand->cand_type; |
| stype = base_cand->stride_type; |
| if (has_single_use (base_in)) |
| savings = (base_cand->dead_savings |
| + stmt_cost (base_cand->cand_stmt, speed)); |
| } |
| |
| if (base_cand->next_interp) |
| base_cand = lookup_cand (base_cand->next_interp); |
| else |
| base_cand = NULL; |
| } |
| |
| if (!base) |
| { |
| /* No interpretations had anything useful to propagate, so |
| produce X = Y + (c * 1). */ |
| kind = CAND_ADD; |
| base = base_in; |
| index = index_in; |
| stride = integer_one_node; |
| ctype = TREE_TYPE (base_in); |
| stype = sizetype; |
| } |
| |
| c = alloc_cand_and_find_basis (kind, gs, base, index, stride, |
| ctype, stype, savings); |
| return c; |
| } |
| |
| /* Given GS which is an add or subtract of scalar integers or pointers, |
| make at least one appropriate entry in the candidate table. */ |
| |
| static void |
| slsr_process_add (gimple *gs, tree rhs1, tree rhs2, bool speed) |
| { |
| bool subtract_p = gimple_assign_rhs_code (gs) == MINUS_EXPR; |
| slsr_cand_t c = NULL, c2; |
| |
| if (TREE_CODE (rhs2) == SSA_NAME) |
| { |
| /* 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. */ |
| if (!POINTER_TYPE_P (TREE_TYPE (rhs2))) |
| { |
| c = create_add_ssa_cand (gs, rhs1, rhs2, subtract_p, speed); |
| |
| /* Add the first interpretation to the statement-candidate |
| mapping. */ |
| add_cand_for_stmt (gs, c); |
| } |
| |
| /* If the two RHS operands are identical, or this is a subtract, |
| we're done. */ |
| if (operand_equal_p (rhs1, rhs2, 0) || subtract_p) |
| return; |
| |
| /* Otherwise, record another interpretation assuming RHS2 is the |
| base expression and RHS1 is the stride, again provided that the |
| stride is not a pointer. */ |
| if (!POINTER_TYPE_P (TREE_TYPE (rhs1))) |
| { |
| c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed); |
| if (c) |
| { |
| c->next_interp = c2->cand_num; |
| c2->first_interp = c->cand_num; |
| } |
| else |
| add_cand_for_stmt (gs, c2); |
| } |
| } |
| else if (TREE_CODE (rhs2) == INTEGER_CST) |
| { |
| /* Record an interpretation for the add-immediate. */ |
| widest_int index = wi::to_widest (rhs2); |
| if (subtract_p) |
| index = -index; |
| |
| c = create_add_imm_cand (gs, rhs1, index, speed); |
| |
| /* Add the interpretation to the statement-candidate mapping. */ |
| add_cand_for_stmt (gs, c); |
| } |
| } |
| |
| /* 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. */ |
| |
| static void |
| slsr_process_neg (gimple *gs, tree rhs1, bool speed) |
| { |
| /* Record a CAND_MULT interpretation for the multiply by -1. */ |
| slsr_cand_t c = create_mul_imm_cand (gs, rhs1, integer_minus_one_node, speed); |
| |
| /* Add the interpretation to the statement-candidate mapping. */ |
| add_cand_for_stmt (gs, c); |
| } |
| |
| /* 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 bool |
| legal_cast_p_1 (tree lhs_type, tree rhs_type) |
| { |
| unsigned lhs_size, rhs_size; |
| bool lhs_wraps, rhs_wraps; |
| |
| lhs_size = TYPE_PRECISION (lhs_type); |
| rhs_size = TYPE_PRECISION (rhs_type); |
| lhs_wraps = ANY_INTEGRAL_TYPE_P (lhs_type) && TYPE_OVERFLOW_WRAPS (lhs_type); |
| rhs_wraps = ANY_INTEGRAL_TYPE_P (rhs_type) && TYPE_OVERFLOW_WRAPS (rhs_type); |
| |
| if (lhs_size < rhs_size |
| || (rhs_wraps && !lhs_wraps) |
| || (rhs_wraps && lhs_wraps && rhs_size != lhs_size)) |
| return false; |
| |
| return true; |
| } |
| |
| /* 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 type-cast, 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 type-cast would change semantics, we mustn't do this. |
| |
| This is legitimate for casts from a non-wrapping integral type to |
| any integral type of the same or larger size. It is not legitimate |
| to convert a wrapping type to a non-wrapping 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 bool |
| legal_cast_p (gimple *gs, tree rhs) |
| { |
| if (!is_gimple_assign (gs) |
| || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs))) |
| return false; |
| |
| return legal_cast_p_1 (TREE_TYPE (gimple_assign_lhs (gs)), TREE_TYPE (rhs)); |
| } |
| |
| /* 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. */ |
| |
| static void |
| slsr_process_cast (gimple *gs, tree rhs1, bool speed) |
| { |
| tree lhs, ctype; |
| slsr_cand_t base_cand, c = NULL, c2; |
| unsigned savings = 0; |
| |
| if (!legal_cast_p (gs, rhs1)) |
| return; |
| |
| lhs = gimple_assign_lhs (gs); |
| base_cand = base_cand_from_table (rhs1); |
| ctype = TREE_TYPE (lhs); |
| |
| if (base_cand && base_cand->kind != CAND_PHI) |
| { |
| slsr_cand_t first_cand = NULL; |
| |
| while (base_cand) |
| { |
| /* 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 (has_single_use (rhs1)) |
| savings = (base_cand->dead_savings |
| + stmt_cost (base_cand->cand_stmt, speed)); |
| |
| c = alloc_cand_and_find_basis (base_cand->kind, gs, |
| base_cand->base_expr, |
| base_cand->index, base_cand->stride, |
| ctype, base_cand->stride_type, |
| savings); |
| if (!first_cand) |
| first_cand = c; |
| |
| if (first_cand != c) |
| c->first_interp = first_cand->cand_num; |
| |
| if (base_cand->next_interp) |
| base_cand = lookup_cand (base_cand->next_interp); |
| else |
| base_cand = NULL; |
| } |
| } |
| else |
| { |
| /* 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. */ |
| c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0, |
| integer_one_node, ctype, sizetype, 0); |
| c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0, |
| integer_one_node, ctype, sizetype, 0); |
| c->next_interp = c2->cand_num; |
| c2->first_interp = c->cand_num; |
| } |
| |
| /* Add the first (or only) interpretation to the statement-candidate |
| mapping. */ |
| add_cand_for_stmt (gs, c); |
| } |
| |
| /* 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. */ |
| |
| static void |
| slsr_process_copy (gimple *gs, tree rhs1, bool speed) |
| { |
| slsr_cand_t base_cand, c = NULL, c2; |
| unsigned savings = 0; |
| |
| base_cand = base_cand_from_table (rhs1); |
| |
| if (base_cand && base_cand->kind != CAND_PHI) |
| { |
| slsr_cand_t first_cand = NULL; |
| |
| while (base_cand) |
| { |
| /* Propagate all data from the base candidate. */ |
| if (has_single_use (rhs1)) |
| savings = (base_cand->dead_savings |
| + stmt_cost (base_cand->cand_stmt, speed)); |
| |
| c = alloc_cand_and_find_basis (base_cand->kind, gs, |
| base_cand->base_expr, |
| base_cand->index, base_cand->stride, |
| base_cand->cand_type, |
| base_cand->stride_type, savings); |
| if (!first_cand) |
| first_cand = c; |
| |
| if (first_cand != c) |
| c->first_interp = first_cand->cand_num; |
| |
| if (base_cand->next_interp) |
| base_cand = lookup_cand (base_cand->next_interp); |
| else |
| base_cand = NULL; |
| } |
| } |
| else |
| { |
| /* 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. */ |
| c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0, |
| integer_one_node, TREE_TYPE (rhs1), |
| sizetype, 0); |
| c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0, |
| integer_one_node, TREE_TYPE (rhs1), |
| sizetype, 0); |
| c->next_interp = c2->cand_num; |
| c2->first_interp = c->cand_num; |
| } |
| |
| /* Add the first (or only) interpretation to the statement-candidate |
| mapping. */ |
| add_cand_for_stmt (gs, c); |
| } |
| |
| class find_candidates_dom_walker : public dom_walker |
| { |
| public: |
| find_candidates_dom_walker (cdi_direction direction) |
| : dom_walker (direction) {} |
| virtual edge before_dom_children (basic_block); |
| }; |
| |
| /* Find strength-reduction candidates in block BB. */ |
| |
| edge |
| find_candidates_dom_walker::before_dom_children (basic_block bb) |
| { |
| bool speed = optimize_bb_for_speed_p (bb); |
| |
| for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); |
| gsi_next (&gsi)) |
| slsr_process_phi (gsi.phi (), speed); |
| |
| for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); |
| gsi_next (&gsi)) |
| { |
| gimple *gs = gsi_stmt (gsi); |
| |
| if (stmt_could_throw_p (gs)) |
| continue; |
| |
| if (gimple_vuse (gs) && gimple_assign_single_p (gs)) |
| slsr_process_ref (gs); |
| |
| else if (is_gimple_assign (gs) |
| && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs))) |
| || POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs))))) |
| { |
| tree rhs1 = NULL_TREE, rhs2 = NULL_TREE; |
| |
| switch (gimple_assign_rhs_code (gs)) |
| { |
| case MULT_EXPR: |
| case PLUS_EXPR: |
| rhs1 = gimple_assign_rhs1 (gs); |
| rhs2 = gimple_assign_rhs2 (gs); |
| /* Should never happen, but currently some buggy situations |
| in earlier phases put constants in rhs1. */ |
| if (TREE_CODE (rhs1) != SSA_NAME) |
| continue; |
| break; |
| |
| /* Possible future opportunity: rhs1 of a ptr+ can be |
| an ADDR_EXPR. */ |
| case POINTER_PLUS_EXPR: |
| case MINUS_EXPR: |
| rhs2 = gimple_assign_rhs2 (gs); |
| gcc_fallthrough (); |
| |
| CASE_CONVERT: |
| case SSA_NAME: |
| case NEGATE_EXPR: |
| rhs1 = gimple_assign_rhs1 (gs); |
| if (TREE_CODE (rhs1) != SSA_NAME) |
| continue; |
| break; |
| |
| default: |
| ; |
| } |
| |
| switch (gimple_assign_rhs_code (gs)) |
| { |
| case MULT_EXPR: |
| slsr_process_mul (gs, rhs1, rhs2, speed); |
| break; |
| |
| case PLUS_EXPR: |
| case POINTER_PLUS_EXPR: |
| case MINUS_EXPR: |
| slsr_process_add (gs, rhs1, rhs2, speed); |
| break; |
| |
| case NEGATE_EXPR: |
| slsr_process_neg (gs, rhs1, speed); |
| break; |
| |
| CASE_CONVERT: |
| slsr_process_cast (gs, rhs1, speed); |
| break; |
| |
| case SSA_NAME: |
| slsr_process_copy (gs, rhs1, speed); |
| break; |
| |
| default: |
| ; |
| } |
| } |
| } |
| return NULL; |
| } |
| |
| /* Dump a candidate for debug. */ |
| |
| static void |
| dump_candidate (slsr_cand_t c) |
| { |
| fprintf (dump_file, "%3d [%d] ", c->cand_num, |
| gimple_bb (c->cand_stmt)->index); |
| print_gimple_stmt (dump_file, c->cand_stmt, 0); |
| switch (c->kind) |
| { |
| case CAND_MULT: |
| fputs (" MULT : (", dump_file); |
| print_generic_expr (dump_file, c->base_expr); |
| fputs (" + ", dump_file); |
| print_decs (c->index, dump_file); |
| fputs (") * ", dump_file); |
| if (TREE_CODE (c->stride) != INTEGER_CST |
| && c->stride_type != TREE_TYPE (c->stride)) |
| { |
| fputs ("(", dump_file); |
| print_generic_expr (dump_file, c->stride_type); |
| fputs (")", dump_file); |
| } |
| print_generic_expr (dump_file, c->stride); |
| fputs (" : ", dump_file); |
| break; |
| case CAND_ADD: |
| fputs (" ADD : ", dump_file); |
| print_generic_expr (dump_file, c->base_expr); |
| fputs (" + (", dump_file); |
| print_decs (c->index, dump_file); |
| fputs (" * ", dump_file); |
| if (TREE_CODE (c->stride) != INTEGER_CST |
| && c->stride_type != TREE_TYPE (c->stride)) |
| { |
| fputs ("(", dump_file); |
| print_generic_expr (dump_file, c->stride_type); |
| fputs (")", dump_file); |
| } |
| print_generic_expr (dump_file, c->stride); |
| fputs (") : ", dump_file); |
| break; |
| case CAND_REF: |
| fputs (" REF : ", dump_file); |
| print_generic_expr (dump_file, c->base_expr); |
| fputs (" + (", dump_file); |
| print_generic_expr (dump_file, c->stride); |
| fputs (") + ", dump_file); |
| print_decs (c->index, dump_file); |
| fputs (" : ", dump_file); |
| break; |
| case CAND_PHI: |
| fputs (" PHI : ", dump_file); |
| print_generic_expr (dump_file, c->base_expr); |
| fputs (" + (unknown * ", dump_file); |
| print_generic_expr (dump_file, c->stride); |
| fputs (") : ", dump_file); |
| break; |
| default: |
| gcc_unreachable (); |
| } |
| print_generic_expr (dump_file, c->cand_type); |
| fprintf (dump_file, "\n basis: %d dependent: %d sibling: %d\n", |
| c->basis, c->dependent, c->sibling); |
| fprintf (dump_file, |
| " next-interp: %d first-interp: %d dead-savings: %d\n", |
| c->next_interp, c->first_interp, c->dead_savings); |
| if (c->def_phi) |
| fprintf (dump_file, " phi: %d\n", c->def_phi); |
| fputs ("\n", dump_file); |
| } |
| |
| /* Dump the candidate vector for debug. */ |
| |
| static void |
| dump_cand_vec (void) |
| { |
| unsigned i; |
| slsr_cand_t c; |
| |
| fprintf (dump_file, "\nStrength reduction candidate vector:\n\n"); |
| |
| FOR_EACH_VEC_ELT (cand_vec, i, c) |
| dump_candidate (c); |
| } |
| |
| /* Callback used to dump the candidate chains hash table. */ |
| |
| int |
| ssa_base_cand_dump_callback (cand_chain **slot, void *ignored ATTRIBUTE_UNUSED) |
| { |
| const_cand_chain_t chain = *slot; |
| cand_chain_t p; |
| |
| print_generic_expr (dump_file, chain->base_expr); |
| fprintf (dump_file, " -> %d", chain->cand->cand_num); |
| |
| for (p = chain->next; p; p = p->next) |
| fprintf (dump_file, " -> %d", p->cand->cand_num); |
| |
| fputs ("\n", dump_file); |
| return 1; |
| } |
| |
| /* Dump the candidate chains. */ |
| |
| static void |
| dump_cand_chains (void) |
| { |
| fprintf (dump_file, "\nStrength reduction candidate chains:\n\n"); |
| base_cand_map->traverse_noresize <void *, ssa_base_cand_dump_callback> |
| (NULL); |
| fputs ("\n", dump_file); |
| } |
| |
| /* Dump the increment vector for debug. */ |
| |
| static void |
| dump_incr_vec (void) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| unsigned i; |
| |
| fprintf (dump_file, "\nIncrement vector:\n\n"); |
| |
| for (i = 0; i < incr_vec_len; i++) |
| { |
| fprintf (dump_file, "%3d increment: ", i); |
| print_decs (incr_vec[i].incr, dump_file); |
| fprintf (dump_file, "\n count: %d", incr_vec[i].count); |
| fprintf (dump_file, "\n cost: %d", incr_vec[i].cost); |
| fputs ("\n initializer: ", dump_file); |
| print_generic_expr (dump_file, incr_vec[i].initializer); |
| fputs ("\n\n", dump_file); |
| } |
| } |
| } |
| |
| /* Replace *EXPR in candidate C with an equivalent strength-reduced |
| data reference. */ |
| |
| static void |
| replace_ref (tree *expr, slsr_cand_t c) |
| { |
| tree add_expr, mem_ref, acc_type = TREE_TYPE (*expr); |
| unsigned HOST_WIDE_INT misalign; |
| unsigned align; |
| |
| /* Ensure the memory reference carries the minimum alignment |
| requirement for the data type. See PR58041. */ |
| get_object_alignment_1 (*expr, &align, &misalign); |
| if (misalign != 0) |
| align = least_bit_hwi (misalign); |
| if (align < TYPE_ALIGN (acc_type)) |
| acc_type = build_aligned_type (acc_type, align); |
| |
| add_expr = fold_build2 (POINTER_PLUS_EXPR, c->cand_type, |
| c->base_expr, c->stride); |
| mem_ref = fold_build2 (MEM_REF, acc_type, add_expr, |
| wide_int_to_tree (c->cand_type, c->index)); |
| |
| /* Gimplify the base addressing expression for the new MEM_REF tree. */ |
| gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); |
| TREE_OPERAND (mem_ref, 0) |
| = force_gimple_operand_gsi (&gsi, TREE_OPERAND (mem_ref, 0), |
| /*simple_p=*/true, NULL, |
| /*before=*/true, GSI_SAME_STMT); |
| copy_ref_info (mem_ref, *expr); |
| *expr = mem_ref; |
| update_stmt (c->cand_stmt); |
| } |
| |
| /* Replace CAND_REF candidate C, each sibling of candidate C, and each |
| dependent of candidate C with an equivalent strength-reduced data |
| reference. */ |
| |
| static void |
| replace_refs (slsr_cand_t c) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fputs ("Replacing reference: ", dump_file); |
| print_gimple_stmt (dump_file, c->cand_stmt, 0); |
| } |
| |
| if (gimple_vdef (c->cand_stmt)) |
| { |
| tree *lhs = gimple_assign_lhs_ptr (c->cand_stmt); |
| replace_ref (lhs, c); |
| } |
| else |
| { |
| tree *rhs = gimple_assign_rhs1_ptr (c->cand_stmt); |
| replace_ref (rhs, c); |
| } |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fputs ("With: ", dump_file); |
| print_gimple_stmt (dump_file, c->cand_stmt, 0); |
| fputs ("\n", dump_file); |
| } |
| |
| if (c->sibling) |
| replace_refs (lookup_cand (c->sibling)); |
| |
| if (c->dependent) |
| replace_refs (lookup_cand (c->dependent)); |
| } |
| |
| /* Return TRUE if candidate C is dependent upon a PHI. */ |
| |
| static bool |
| phi_dependent_cand_p (slsr_cand_t c) |
| { |
| /* 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. */ |
| return (c->def_phi |
| && c->basis |
| && lookup_cand (c->basis)->def_phi != c->def_phi); |
| } |
| |
| /* Calculate the increment required for candidate C relative to |
| its basis. */ |
| |
| static widest_int |
| cand_increment (slsr_cand_t c) |
| { |
| slsr_cand_t 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. */ |
| if (!c->basis || phi_dependent_cand_p (c)) |
| return c->index; |
| |
| basis = lookup_cand (c->basis); |
| gcc_assert (operand_equal_p (c->base_expr, basis->base_expr, 0)); |
| return c->index - basis->index; |
| } |
| |
| /* 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. */ |
| |
| static inline widest_int |
| cand_abs_increment (slsr_cand_t c) |
| { |
| widest_int increment = cand_increment (c); |
| |
| if (!address_arithmetic_p && wi::neg_p (increment)) |
| increment = -increment; |
| |
| return increment; |
| } |
| |
| /* Return TRUE iff candidate C has already been replaced under |
| another interpretation. */ |
| |
| static inline bool |
| cand_already_replaced (slsr_cand_t c) |
| { |
| return (gimple_bb (c->cand_stmt) == 0); |
| } |
| |
| /* Common logic used by replace_unconditional_candidate and |
| replace_conditional_candidate. */ |
| |
| static void |
| replace_mult_candidate (slsr_cand_t c, tree basis_name, widest_int bump) |
| { |
| tree target_type = TREE_TYPE (gimple_assign_lhs (c->cand_stmt)); |
| enum tree_code cand_code = gimple_assign_rhs_code (c->cand_stmt); |
| |
| /* It is not useful to replace casts, copies, negates, or adds of |
| an SSA name and a constant. */ |
| if (cand_code == SSA_NAME |
| || CONVERT_EXPR_CODE_P (cand_code) |
| || cand_code == PLUS_EXPR |
| || cand_code == POINTER_PLUS_EXPR |
| || cand_code == MINUS_EXPR |
| || cand_code == NEGATE_EXPR) |
| return; |
| |
| enum tree_code code = PLUS_EXPR; |
| tree bump_tree; |
| gimple *stmt_to_print = NULL; |
| |
| if (wi::neg_p (bump)) |
| { |
| code = MINUS_EXPR; |
| bump = -bump; |
| } |
| |
| /* It is possible that the resulting bump doesn't fit in target_type. |
| Abandon the replacement in this case. This does not affect |
| siblings or dependents of C. */ |
| if (bump != wi::ext (bump, TYPE_PRECISION (target_type), |
| TYPE_SIGN (target_type))) |
| return; |
| |
| bump_tree = wide_int_to_tree (target_type, bump); |
| |
| /* If the basis name and the candidate's LHS have incompatible types, |
| introduce a cast. */ |
| if (!useless_type_conversion_p (target_type, TREE_TYPE (basis_name))) |
| basis_name = introduce_cast_before_cand (c, target_type, basis_name); |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fputs ("Replacing: ", dump_file); |
| print_gimple_stmt (dump_file, c->cand_stmt, 0); |
| } |
| |
| if (bump == 0) |
| { |
| tree lhs = gimple_assign_lhs (c->cand_stmt); |
| gassign *copy_stmt = gimple_build_assign (lhs, basis_name); |
| gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); |
| slsr_cand_t cc = lookup_cand (c->first_interp); |
| gimple_set_location (copy_stmt, gimple_location (c->cand_stmt)); |
| gsi_replace (&gsi, copy_stmt, false); |
| while (cc) |
| { |
| cc->cand_stmt = copy_stmt; |
| cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL; |
| } |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| stmt_to_print = copy_stmt; |
| } |
| else |
| { |
| tree rhs1, rhs2; |
| if (cand_code != NEGATE_EXPR) { |
| rhs1 = gimple_assign_rhs1 (c->cand_stmt); |
| rhs2 = gimple_assign_rhs2 (c->cand_stmt); |
| } |
| if (cand_code != NEGATE_EXPR |
| && ((operand_equal_p (rhs1, basis_name, 0) |
| && operand_equal_p (rhs2, bump_tree, 0)) |
| || (operand_equal_p (rhs1, bump_tree, 0) |
| && operand_equal_p (rhs2, basis_name, 0)))) |
| { |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fputs ("(duplicate, not actually replacing)", dump_file); |
| stmt_to_print = c->cand_stmt; |
| } |
| } |
| else |
| { |
| gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); |
| slsr_cand_t cc = lookup_cand (c->first_interp); |
| gimple_assign_set_rhs_with_ops (&gsi, code, basis_name, bump_tree); |
| update_stmt (gsi_stmt (gsi)); |
| while (cc) |
| { |
| cc->cand_stmt = gsi_stmt (gsi); |
| cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL; |
| } |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| stmt_to_print = gsi_stmt (gsi); |
| } |
| } |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fputs ("With: ", dump_file); |
| print_gimple_stmt (dump_file, stmt_to_print, 0); |
| fputs ("\n", dump_file); |
| } |
| } |
| |
| /* 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 void |
| replace_unconditional_candidate (slsr_cand_t c) |
| { |
| slsr_cand_t basis; |
| |
| if (cand_already_replaced (c)) |
| return; |
| |
| basis = lookup_cand (c->basis); |
| widest_int bump = cand_increment (c) * wi::to_widest (c->stride); |
| |
| replace_mult_candidate (c, gimple_assign_lhs (basis->cand_stmt), bump); |
| } |
| |
| /* 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. */ |
| |
| static inline int |
| incr_vec_index (const widest_int &increment) |
| { |
| unsigned i; |
| |
| for (i = 0; i < incr_vec_len && increment != incr_vec[i].incr; i++) |
| ; |
| |
| if (i < incr_vec_len) |
| return i; |
| else |
| return -1; |
| } |
| |
| /* 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. */ |
| |
| static tree |
| create_add_on_incoming_edge (slsr_cand_t c, tree basis_name, |
| widest_int increment, edge e, location_t loc, |
| bool known_stride) |
| { |
| tree lhs, basis_type; |
| gassign *new_stmt, *cast_stmt = NULL; |
| |
| /* If the add candidate along this incoming edge has the same |
| index as C's hidden basis, the hidden basis represents this |
| edge correctly. */ |
| if (increment == 0) |
| return basis_name; |
| |
| basis_type = TREE_TYPE (basis_name); |
| lhs = make_temp_ssa_name (basis_type, NULL, "slsr"); |
| |
| /* Occasionally people convert integers to pointers without a |
| cast, leading us into trouble if we aren't careful. */ |
| enum tree_code plus_code |
| = POINTER_TYPE_P (basis_type) ? POINTER_PLUS_EXPR : PLUS_EXPR; |
| |
| if (known_stride) |
| { |
| tree bump_tree; |
| enum tree_code code = plus_code; |
| widest_int bump = increment * wi::to_widest (c->stride); |
| if (wi::neg_p (bump) && !POINTER_TYPE_P (basis_type)) |
| { |
| code = MINUS_EXPR; |
| bump = -bump; |
| } |
| |
| tree stride_type = POINTER_TYPE_P (basis_type) ? sizetype : basis_type; |
| bump_tree = wide_int_to_tree (stride_type, bump); |
| new_stmt = gimple_build_assign (lhs, code, basis_name, bump_tree); |
| } |
| else |
| { |
| int i; |
| bool negate_incr = !POINTER_TYPE_P (basis_type) && wi::neg_p (increment); |
| i = incr_vec_index (negate_incr ? -increment : increment); |
| gcc_assert (i >= 0); |
| |
| if (incr_vec[i].initializer) |
| { |
| enum tree_code code = negate_incr ? MINUS_EXPR : plus_code; |
| new_stmt = gimple_build_assign (lhs, code, basis_name, |
| incr_vec[i].initializer); |
| } |
| else { |
| tree stride; |
| |
| if (!types_compatible_p (TREE_TYPE (c->stride), c->stride_type)) |
| { |
| tree cast_stride = make_temp_ssa_name (c->stride_type, NULL, |
| "slsr"); |
| cast_stmt = gimple_build_assign (cast_stride, NOP_EXPR, |
| c->stride); |
| stride = cast_stride; |
| } |
| else |
| stride = c->stride; |
| |
| if (increment == 1) |
| new_stmt = gimple_build_assign (lhs, plus_code, basis_name, stride); |
| else if (increment == -1) |
| new_stmt = gimple_build_assign (lhs, MINUS_EXPR, basis_name, stride); |
| else |
| gcc_unreachable (); |
| } |
| } |
| |
| if (cast_stmt) |
| { |
| gimple_set_location (cast_stmt, loc); |
| gsi_insert_on_edge (e, cast_stmt); |
| } |
| |
| gimple_set_location (new_stmt, loc); |
| gsi_insert_on_edge (e, new_stmt); |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| if (cast_stmt) |
| { |
| fprintf (dump_file, "Inserting cast on edge %d->%d: ", |
| e->src->index, e->dest->index); |
| print_gimple_stmt (dump_file, cast_stmt, 0); |
| } |
| fprintf (dump_file, "Inserting on edge %d->%d: ", e->src->index, |
| e->dest->index); |
| print_gimple_stmt (dump_file, new_stmt, 0); |
| } |
| |
| return lhs; |
| } |
| |
| /* Clear the visited field for a tree of PHI candidates. */ |
| |
| static void |
| clear_visited (gphi *phi) |
| { |
| unsigned i; |
| slsr_cand_t phi_cand = *stmt_cand_map->get (phi); |
| |
| if (phi_cand->visited) |
| { |
| phi_cand->visited = 0; |
| |
| for (i = 0; i < gimple_phi_num_args (phi); i++) |
| { |
| tree arg = gimple_phi_arg_def (phi, i); |
| gimple *arg_def = SSA_NAME_DEF_STMT (arg); |
| if (gimple_code (arg_def) == GIMPLE_PHI) |
| clear_visited (as_a <gphi *> (arg_def)); |
| } |
| } |
| } |
| |
| /* Recursive helper function for create_phi_basis. */ |
| |
| static tree |
| create_phi_basis_1 (slsr_cand_t c, gimple *from_phi, tree basis_name, |
| location_t loc, bool known_stride) |
| { |
| int i; |
| tree name, phi_arg; |
| gphi *phi; |
| slsr_cand_t basis = lookup_cand (c->basis); |
| int nargs = gimple_phi_num_args (from_phi); |
| basic_block phi_bb = gimple_bb (from_phi); |
| slsr_cand_t phi_cand = *stmt_cand_map->get (from_phi); |
| auto_vec<tree> phi_args (nargs); |
| |
| if (phi_cand->visited) |
| return phi_cand->cached_basis; |
| phi_cand->visited = 1; |
| |
| /* Process each argument of the existing phi that represents |
| conditionally-executed add candidates. */ |
| for (i = 0; i < nargs; i++) |
| { |
| edge e = (*phi_bb->preds)[i]; |
| tree arg = gimple_phi_arg_def (from_phi, i); |
| tree feeding_def; |
| |
| /* If the phi argument is the base name of the CAND_PHI, then |
| this incoming arc should use the hidden basis. */ |
| if (operand_equal_p (arg, phi_cand->base_expr, 0)) |
| if (basis->index == 0) |
| feeding_def = gimple_assign_lhs (basis->cand_stmt); |
| else |
| { |
| widest_int incr = -basis->index; |
| feeding_def = create_add_on_incoming_edge (c, basis_name, incr, |
| e, loc, known_stride); |
| } |
| else |
| { |
| gimple *arg_def = SSA_NAME_DEF_STMT (arg); |
| |
| /* 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. */ |
| if (gimple_code (arg_def) == GIMPLE_PHI) |
| feeding_def = create_phi_basis_1 (c, arg_def, basis_name, |
| loc, known_stride); |
| else |
| { |
| slsr_cand_t arg_cand = base_cand_from_table (arg); |
| widest_int diff = arg_cand->index - basis->index; |
| feeding_def = create_add_on_incoming_edge (c, basis_name, diff, |
| e, loc, known_stride); |
| } |
| } |
| |
| /* 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 half-created PHI can be reclaimed. */ |
| phi_args.safe_push (feeding_def); |
| } |
| |
| /* Create the new phi basis. */ |
| name = make_temp_ssa_name (TREE_TYPE (basis_name), NULL, "slsr"); |
| phi = create_phi_node (name, phi_bb); |
| SSA_NAME_DEF_STMT (name) = phi; |
| |
| FOR_EACH_VEC_ELT (phi_args, i, phi_arg) |
| { |
| edge e = (*phi_bb->preds)[i]; |
| add_phi_arg (phi, phi_arg, e, loc); |
| } |
| |
| update_stmt (phi); |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fputs ("Introducing new phi basis: ", dump_file); |
| print_gimple_stmt (dump_file, phi, 0); |
| } |
| |
| phi_cand->cached_basis = name; |
| return name; |
| } |
| |
| /* 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. */ |
| |
| static tree |
| create_phi_basis (slsr_cand_t c, gimple *from_phi, tree basis_name, |
| location_t loc, bool known_stride) |
| { |
| tree retval = create_phi_basis_1 (c, from_phi, basis_name, loc, |
| known_stride); |
| gcc_assert (retval); |
| clear_visited (as_a <gphi *> (from_phi)); |
| return retval; |
| } |
| |
| /* 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. */ |
| |
| static void |
| replace_conditional_candidate (slsr_cand_t c) |
| { |
| tree basis_name, name; |
| slsr_cand_t basis; |
| location_t loc; |
| |
| /* 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. */ |
| basis = lookup_cand (c->basis); |
| basis_name = gimple_assign_lhs (basis->cand_stmt); |
| |
| /* Create a new phi statement which will represent C's true basis |
| after the transformation is complete. */ |
| loc = gimple_location (c->cand_stmt); |
| name = create_phi_basis (c, lookup_cand (c->def_phi)->cand_stmt, |
| basis_name, loc, KNOWN_STRIDE); |
| |
| /* Replace C with an add of the new basis phi and a constant. */ |
| widest_int bump = c->index * wi::to_widest (c->stride); |
| |
| replace_mult_candidate (c, name, bump); |
| } |
| |
| /* Recursive helper function for phi_add_costs. SPREAD is a measure of |
| how many PHI nodes we have visited at this point in the tree walk. */ |
| |
| static int |
| phi_add_costs_1 (gimple *phi, slsr_cand_t c, int one_add_cost, int *spread) |
| { |
| unsigned i; |
| int cost = 0; |
| slsr_cand_t phi_cand = *stmt_cand_map->get (phi); |
| |
| if (phi_cand->visited) |
| return 0; |
| |
| phi_cand->visited = 1; |
| (*spread)++; |
| |
| /* 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. */ |
| basic_block phi_bb = gimple_bb (phi); |
| slsr_cand_t basis = lookup_cand (c->basis); |
| basic_block basis_bb = gimple_bb (basis->cand_stmt); |
| |
| if (phi_bb == basis_bb || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb)) |
| return COST_INFINITE; |
| |
| for (i = 0; i < gimple_phi_num_args (phi); i++) |
| { |
| tree arg = gimple_phi_arg_def (phi, i); |
| |
| if (arg != phi_cand->base_expr) |
| { |
| gimple *arg_def = SSA_NAME_DEF_STMT (arg); |
| |
| if (gimple_code (arg_def) == GIMPLE_PHI) |
| { |
| cost += phi_add_costs_1 (arg_def, c, one_add_cost, spread); |
| |
| if (cost >= COST_INFINITE || *spread > MAX_SPREAD) |
| return COST_INFINITE; |
| } |
| else |
| { |
| slsr_cand_t arg_cand = base_cand_from_table (arg); |
| |
| if (arg_cand->index != c->index) |
| cost += one_add_cost; |
| } |
| } |
| } |
| |
| return cost; |
| } |
| |
| /* Compute the expected costs of inserting basis adjustments for |
| candidate C with phi-definition 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. */ |
| |
| static int |
| phi_add_costs (gimple *phi, slsr_cand_t c, int one_add_cost) |
| { |
| int spread = 0; |
| int retval = phi_add_costs_1 (phi, c, one_add_cost, &spread); |
| clear_visited (as_a <gphi *> (phi)); |
| return retval; |
| } |
| /* 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. */ |
| |
| static void |
| replace_uncond_cands_and_profitable_phis (slsr_cand_t c) |
| { |
| if (phi_dependent_cand_p (c)) |
| { |
| /* A multiply candidate with a stride of 1 is just an artifice |
| of a copy or cast; there is no value in replacing it. */ |
| if (c->kind == CAND_MULT && wi::to_widest (c->stride) != 1) |
| { |
| /* 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 dead-code |
| savings to determine profitability. */ |
| bool speed = optimize_bb_for_speed_p (gimple_bb (c->cand_stmt)); |
| int mult_savings = stmt_cost (c->cand_stmt, speed); |
| gimple *phi = lookup_cand (c->def_phi)->cand_stmt; |
| tree phi_result = gimple_phi_result (phi); |
| int one_add_cost = add_cost (speed, |
| TYPE_MODE (TREE_TYPE (phi_result))); |
| int add_costs = one_add_cost + phi_add_costs (phi, c, one_add_cost); |
| int cost = add_costs - mult_savings - c->dead_savings; |
| |
| if (dump_file && (dump_flags & TDF_DETAILS)) |
| { |
| fprintf (dump_file, " Conditional candidate %d:\n", c->cand_num); |
| fprintf (dump_file, " add_costs = %d\n", add_costs); |
| fprintf (dump_file, " mult_savings = %d\n", mult_savings); |
| fprintf (dump_file, " dead_savings = %d\n", c->dead_savings); |
| fprintf (dump_file, " cost = %d\n", cost); |
| if (cost <= COST_NEUTRAL) |
| fputs (" Replacing...\n", dump_file); |
| else |
| fputs (" Not replaced.\n", dump_file); |
| } |
| |
| if (cost <= COST_NEUTRAL) |
| replace_conditional_candidate (c); |
| } |
| } |
| else |
| replace_unconditional_candidate (c); |
| |
| if (c->sibling) |
| replace_uncond_cands_and_profitable_phis (lookup_cand (c->sibling)); |
| |
| if (c->dependent) |
| replace_uncond_cands_and_profitable_phis (lookup_cand (c->dependent)); |
| } |
| |
| /* Count the number of candidates in the tree rooted at C that have |
| not already been replaced under other interpretations. */ |
| |
| static int |
| count_candidates (slsr_cand_t c) |
| { |
| unsigned count = cand_already_replaced (c) ? 0 : 1; |
| |
| if (c->sibling) |
| count += count_candidates (lookup_cand (c->sibling)); |
| |
| if (c->dependent) |
| count += count_candidates (lookup_cand (c->dependent)); |
| |
| return count; |
| } |
| |
| /* 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. */ |
| |
| static void |
| record_increment (slsr_cand_t c, widest_int increment, bool is_phi_adjust) |
| { |
| bool found = false; |
| unsigned i; |
| |
| /* Treat increments that differ only in sign as identical so as to |
| share initializers, unless we are generating pointer arithmetic. */ |
| if (!address_arithmetic_p && wi::neg_p (increment)) |
| increment = -increment; |
| |
| for (i = 0; i < incr_vec_len; i++) |
| { |
| if (incr_vec[i].incr == increment) |
| { |
| incr_vec[i].count++; |
| found = true; |
| |
| /* If we previously recorded an initializer that doesn't |
| dominate this candidate, it's not going to be useful to |
| us after all. */ |
| if (incr_vec[i].initializer |
| && !dominated_by_p (CDI_DOMINATORS, |
| gimple_bb (c->cand_stmt), |
| incr_vec[i].init_bb)) |
| { |
| incr_vec[i].initializer = NULL_TREE; |
| incr_vec[i].init_bb = NULL; |
| } |
| |
| break; |
| } |
| } |
| |
| if (!found && incr_vec_len < MAX_INCR_VEC_LEN - 1) |
| { |
| /* 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. */ |
| incr_vec[incr_vec_len].incr = increment; |
| incr_vec[incr_vec_len].count = c->basis || is_phi_adjust ? 1 : 0; |
| incr_vec[incr_vec_len].cost = COST_INFINITE; |
| |
| /* 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 0, 1 never need initializers; |
| and phi adjustments don't ever provide initializers. */ |
| if (c->kind == CAND_ADD |
| && !is_phi_adjust |
| && c->index == increment |
| && (increment > 1 || increment < 0) |
| && (gimple_assign_rhs_code (c->cand_stmt) == PLUS_EXPR |
| || gimple_assign_rhs_code (c->cand_stmt) == POINTER_PLUS_EXPR)) |
| { |
| tree t0 = NULL_TREE; |
| tree rhs1 = gimple_assign_rhs1 (c->cand_stmt); |
| tree rhs2 = gimple_assign_rhs2 (c->cand_stmt); |
| if (operand_equal_p (rhs1, c->base_expr, 0)) |
| t0 = rhs2; |
| else if (operand_equal_p (rhs2, c->base_expr, 0)) |
| t0 = rhs1; |
| if (t0 |
| && SSA_NAME_DEF_STMT (t0) |
| && gimple_bb (SSA_NAME_DEF_STMT (t0))) |
| { |
| incr_vec[incr_vec_len].initializer = t0; |
| incr_vec[incr_vec_len++].init_bb |
| = gimple_bb (SSA_NAME_DEF_STMT (t0)); |
| } |
| else |
| { |
| incr_vec[incr_vec_len].initializer = NULL_TREE; |
| incr_vec[incr_vec_len++].init_bb = NULL; |
| } |
| } |
| else |
| { |
| incr_vec[incr_vec_len].initializer = NULL_TREE; |
| incr_vec[incr_vec_len++].init_bb = NULL; |
| } |
| } |
| } |
| |
| /* Recursive helper function for record_phi_increments. */ |
| |
| static void |
| record_phi_increments_1 (slsr_cand_t basis, gimple *phi) |
| { |
| unsigned i; |
| slsr_cand_t phi_cand = *stmt_cand_map->get (phi); |
| |
| if (phi_cand->visited) |
| return; |
| phi_cand->visited = 1; |
| |
| for (i = 0; i < gimple_phi_num_args (phi); i++) |
| { |
| tree arg = gimple_phi_arg_def (phi, i); |
| |
| if (!operand_equal_p (arg, phi_cand->base_expr, 0)) |
| { |
| gimple *arg_def = SSA_NAME_DEF_STMT (arg); |
| |
| if (gimple_code (arg_def) == GIMPLE_PHI) |
| record_phi_increments_1 (basis, arg_def); |
| else |
| { |
| slsr_cand_t arg_cand = base_cand_from_table (arg); |
| widest_int diff = arg_cand->index - basis->index; |
| record_increment (arg_cand, diff, PHI_ADJUST); |
| } |
| } |
| } |
| } |
| |
| /* 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 index-adjusting statements and the |
| index of the basis. */ |
| |
| static void |
| record_phi_increments (slsr_cand_t basis, gimple *phi) |
| { |
| record_phi_increments_1 (basis, phi); |
| clear_visited (as_a <gphi *> (phi)); |
| } |
| |
| /* 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. */ |
| |
| static void |
| record_increments (slsr_cand_t c) |
| { |
| if (!cand_already_replaced (c)) |
| { |
| if (!phi_dependent_cand_p (c)) |
| record_increment (c, cand_increment (c), NOT_PHI_ADJUST); |
| else |
| { |
| /* 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. */ |
| record_increment (c, c->index, NOT_PHI_ADJUST); |
| |
| if (c->basis) |
| record_phi_increments (lookup_cand (c->basis), |
| lookup_cand (c->def_phi)->cand_stmt); |
| } |
| } |
| |
| if (c->sibling) |
| record_increments (lookup_cand (c->sibling)); |
| |
| if (c->dependent) |
| record_increments (lookup_cand (c->dependent)); |
| } |
| |
| /* Recursive helper function for phi_incr_cost. */ |
| |
| static int |
| phi_incr_cost_1 (slsr_cand_t c, const widest_int &incr, gimple *phi, |
| int *savings) |
| { |
| unsigned i; |
| int cost = 0; |
| slsr_cand_t basis = lookup_cand (c->basis); |
| slsr_cand_t phi_cand = *stmt_cand_map->get (phi); |
| |
| if (phi_cand->visited) |
| return 0; |
| phi_cand->visited = 1; |
| |
| for (i = 0; i < gimple_phi_num_args (phi); i++) |
| { |
| tree arg = gimple_phi_arg_def (phi, i); |
| |
| if (!operand_equal_p (arg, phi_cand->base_expr, 0)) |
| { |
| gimple *arg_def = SSA_NAME_DEF_STMT (arg); |
| |
| if (gimple_code (arg_def) == GIMPLE_PHI) |
| { |
| int feeding_savings = 0; |
| tree feeding_var = gimple_phi_result (arg_def); |
| cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings); |
| if (uses_consumed_by_stmt (feeding_var, phi)) |
| *savings += feeding_savings; |
| } |
| else |
| { |
| slsr_cand_t arg_cand = base_cand_from_table (arg); |
| widest_int diff = arg_cand->index - basis->index; |
| |
| if (incr == diff) |
| { |
| tree basis_lhs = gimple_assign_lhs (basis->cand_stmt); |
| tree lhs = gimple_assign_lhs (arg_cand->cand_stmt); |
| cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs))); |
| if (uses_consumed_by_stmt (lhs, phi)) |
| *savings += stmt_cost (arg_cand->cand_stmt, true); |
| } |
| } |
| } |
| } |
| |
| return cost; |
| } |
| |
| /* 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. */ |
| |
| static int |
| phi_incr_cost (slsr_cand_t c, const widest_int &incr, gimple *phi, |
| int *savings) |
| { |
| int retval = phi_incr_cost_1 (c, incr, phi, savings); |
| clear_visited (as_a <gphi *> (phi)); |
| return retval; |
| } |
| |
| /* Return the first candidate in the tree rooted at C that has not |
| already been replaced, favoring siblings over dependents. */ |
| |
| static slsr_cand_t |
| unreplaced_cand_in_tree (slsr_cand_t c) |
| { |
| if (!cand_already_replaced (c)) |
| return c; |
| |
| if (c->sibling) |
| { |
| slsr_cand_t sib = unreplaced_cand_in_tree (lookup_cand (c->sibling)); |
| if (sib) |
| return sib; |
| } |
| |
| if (c->dependent) |
| { |
| slsr_cand_t dep = unreplaced_cand_in_tree (lookup_cand (c->dependent)); |
| if (dep) |
| return dep; |
| } |
| |
| return NULL; |
| } |
| |
| /* 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. */ |
| |
| static bool |
| optimize_cands_for_speed_p (slsr_cand_t c) |
| { |
| slsr_cand_t c2 = unreplaced_cand_in_tree (c); |
| gcc_assert (c2); |
| return optimize_bb_for_speed_p (gimple_bb (c2->cand_stmt)); |
| } |
| |
| /* 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. */ |
| |
| static int |
| lowest_cost_path (int cost_in, int repl_savings, slsr_cand_t c, |
| const widest_int &incr, bool count_phis) |
| { |
| int local_cost, sib_cost, savings = 0; |
| widest_int cand_incr = cand_abs_increment (c); |
| |
| if (cand_already_replaced (c)) |
| local_cost = cost_in; |
| else if (incr == cand_incr) |
| local_cost = cost_in - repl_savings - c->dead_savings; |
| else |
| local_cost = cost_in - c->dead_savings; |
| |
| if (count_phis |
| && phi_dependent_cand_p (c) |
| && !cand_already_replaced (c)) |
| { |
| gimple *phi = lookup_cand (c->def_phi)->cand_stmt; |
| local_cost += phi_incr_cost (c, incr, phi, &savings); |
| |
| if (uses_consumed_by_stmt (gimple_phi_result (phi), c->cand_stmt)) |
| local_cost -= savings; |
| } |
| |
| if (c->dependent) |
| local_cost = lowest_cost_path (local_cost, repl_savings, |
| lookup_cand (c->dependent), incr, |
| count_phis); |
| |
| if (c->sibling) |
| { |
| sib_cost = lowest_cost_path (cost_in, repl_savings, |
| lookup_cand (c->sibling), incr, |
| count_phis); |
| local_cost = MIN (local_cost, sib_cost); |
| } |
| |
| return local_cost; |
| } |
| |
| /* 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 int |
| total_savings (int repl_savings, slsr_cand_t c, const widest_int &incr, |
| bool count_phis) |
| { |
| int savings = 0; |
| widest_int cand_incr = cand_abs_increment (c); |
| |
| if (incr == cand_incr && !cand_already_replaced (c)) |
| savings += repl_savings + c->dead_savings; |
| |
| if (count_phis |
| && phi_dependent_cand_p (c) |
| && !cand_already_replaced (c)) |
| { |
| int phi_savings = 0; |
| gimple *phi = lookup_cand (c->def_phi)->cand_stmt; |
| savings -= phi_incr_cost (c, incr, phi, &phi_savings); |
| |
| if (uses_consumed_by_stmt (gimple_phi_result (phi), c->cand_stmt)) |
| savings += phi_savings; |
| } |
| |
| if (c->dependent) |
| savings += total_savings (repl_savings, lookup_cand (c->dependent), incr, |
| count_phis); |
| |
| if (c->sibling) |
| savings += total_savings (repl_savings, lookup_cand (c->sibling), incr, |
| count_phis); |
| |
| return savings; |
| } |
| |
| /* Use target-specific 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. */ |
| |
| static void |
| analyze_increments (slsr_cand_t first_dep, machine_mode mode, bool speed) |
| { |
| unsigned i; |
| |
| for (i = 0; i < incr_vec_len; i++) |
| { |
| HOST_WIDE_INT incr = incr_vec[i].incr.to_shwi (); |
| |
| /* 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. */ |
| if (!wi::fits_shwi_p (incr_vec[i].incr) || !incr_vec[i].count) |
| incr_vec[i].cost = COST_INFINITE; |
| |
| /* 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. */ |
| else if (incr == 0 |
| || incr == 1 |
| || (incr == -1 |
| && !POINTER_TYPE_P (first_dep->cand_type))) |
| incr_vec[i].cost = COST_NEUTRAL; |
| |
| /* 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. |
| Note that this already takes into account that the stride may |
| have been cast to a wider type, in which case this test won't |
| fire. Example: |
| |
| short int _1; |
| _2 = (int) _1; |
| _3 = _2 * 10; |
| _4 = x + _3; ADD: x + (10 * (int)_1) : int |
| _5 = _2 * 15; |
| _6 = x + _5; ADD: x + (15 * (int)_1) : int |
| |
| Although the stride was a short int initially, the stride |
| used in the analysis has been widened to an int, and such |
| widening will be done in the initializer as well. */ |
| else if (!incr_vec[i].initializer |
| && TREE_CODE (first_dep->stride) != INTEGER_CST |
| && !legal_cast_p_1 (first_dep->stride_type, |
| TREE_TYPE (gimple_assign_lhs |
| (first_dep->cand_stmt)))) |
| incr_vec[i].cost = COST_INFINITE; |
| |
| /* 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. */ |
| else if (!incr_vec[i].initializer |
| && TREE_CODE (first_dep->stride) != INTEGER_CST |
| && POINTER_TYPE_P (first_dep->stride_type)) |
| incr_vec[i].cost = COST_INFINITE; |
| |
| /* 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. */ |
| else if (first_dep->kind == CAND_MULT) |
| { |
| int cost = mult_by_coeff_cost (incr, mode, speed); |
| int repl_savings; |
| |
| if (tree_fits_shwi_p (first_dep->stride)) |
| { |
| HOST_WIDE_INT hwi_stride = tree_to_shwi (first_dep->stride); |
| repl_savings = mult_by_coeff_cost (hwi_stride, mode, speed); |
| } |
| else |
| repl_savings = mul_cost (speed, mode); |
| repl_savings -= add_cost (speed, mode); |
| |
| if (speed) |
| cost = lowest_cost_path (cost, repl_savings, first_dep, |
| incr_vec[i].incr, COUNT_PHIS); |
| else |
| cost -= total_savings (repl_savings, first_dep, incr_vec[i].incr, |
| COUNT_PHIS); |
| |
| incr_vec[i].cost = cost; |
| } |
| |
| /* 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. */ |
| else |
| { |
| int cost = 0; |
| if (!incr_vec[i].initializer) |
| cost = mult_by_coeff_cost (incr, mode, speed); |
| |
| if (speed) |
| cost = lowest_cost_path (cost, 0, first_dep, incr_vec[i].incr, |
| DONT_COUNT_PHIS); |
| else |
| cost -= total_savings (0, first_dep, incr_vec[i].incr, |
| DONT_COUNT_PHIS); |
| |
| incr_vec[i].cost = cost; |
| } |
| } |
| } |
| |
| /* 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. */ |
| |
| static basic_block |
| ncd_for_two_cands (basic_block bb1, basic_block bb2, |
| slsr_cand_t c1, slsr_cand_t c2, slsr_cand_t *where) |
| { |
| basic_block ncd; |
| |
| if (!bb1) |
| { |
| *where = c2; |
| return bb2; |
| } |
| |
| if (!bb2) |
| { |
| *where = c1; |
| return bb1; |
| } |
| |
| ncd = nearest_common_dominator (CDI_DOMINATORS, bb1, bb2); |
| |
| /* If both candidates are in the same block, the earlier |
| candidate wins. */ |
| if (bb1 == ncd && bb2 == ncd) |
| { |
| if (!c1 || (c2 && c2->cand_num < c1->cand_num)) |
| *where = c2; |
| else |
| *where = c1; |
| } |
| |
| /* Otherwise, if one of them produced a candidate in the |
| dominator, that one wins. */ |
| else if (bb1 == ncd) |
| *where = c1; |
| |
| else if (bb2 == ncd) |
| *where = c2; |
| |
| /* If neither matches the dominator, neither wins. */ |
| else |
| *where = NULL; |
| |
| return ncd; |
| } |
| |
| /* 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. */ |
| |
| static basic_block |
| ncd_with_phi (slsr_cand_t c, const widest_int &incr, gphi *phi, |
| basic_block ncd, slsr_cand_t *where) |
| { |
| unsigned i; |
| slsr_cand_t basis = lookup_cand (c->basis); |
| slsr_cand_t phi_cand = *stmt_cand_map->get (phi); |
| |
| for (i = 0; i < gimple_phi_num_args (phi); i++) |
| { |
| tree arg = gimple_phi_arg_def (phi, i); |
| |
| if (!operand_equal_p (arg, phi_cand->base_expr, 0)) |
| { |
| gimple *arg_def = SSA_NAME_DEF_STMT (arg); |
| |
| if (gimple_code (arg_def) == GIMPLE_PHI) |
| ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd, |
| where); |
| else |
| { |
| slsr_cand_t arg_cand = base_cand_from_table (arg); |
| widest_int diff = arg_cand->index - basis->index; |
| basic_block pred = gimple_phi_arg_edge (phi, i)->src; |
| |
| if ((incr == diff) || (!address_arithmetic_p && incr == -diff)) |
| ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where); |
| } |
| } |
| } |
| |
| return ncd; |
| } |
| |
| /* 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. */ |
| |
| static basic_block |
| ncd_of_cand_and_phis (slsr_cand_t c, const widest_int &incr, slsr_cand_t *where) |
| { |
| basic_block ncd = NULL; |
| |
| if (cand_abs_increment (c) == incr) |
| { |
| ncd = gimple_bb (c->cand_stmt); |
| *where = c; |
| } |
| |
| if (phi_dependent_cand_p (c)) |
| ncd = ncd_with_phi (c, incr, |
| as_a <gphi *> (lookup_cand (c->def_phi)->cand_stmt), |
| ncd, where); |
| |
| return ncd; |
| } |
| |
| |