/* 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; | |

} | |