GCC Middle and Back End API Reference
gimple-ssa-strength-reduction.cc File Reference
#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 "tree-ssa-address.h"
#include "tree-affine.h"
#include "tree-eh.h"
#include "builtins.h"
#include "tree-ssa-dce.h"
Include dependency graph for gimple-ssa-strength-reduction.cc:

Data Structures

class  slsr_cand_d
 
struct  cand_chain_d
 
class  incr_info_d
 
struct  cand_chain_hasher
 
class  find_candidates_dom_walker
 

Typedefs

typedef unsigned cand_idx
 
typedef class slsr_cand_d slsr_cand
 
typedef class slsr_cand_dslsr_cand_t
 
typedef const class slsr_cand_dconst_slsr_cand_t
 
typedef struct cand_chain_d cand_chain
 
typedef struct cand_chain_dcand_chain_t
 
typedef const struct cand_chain_dconst_cand_chain_t
 
typedef class incr_info_d incr_info
 
typedef class incr_info_dincr_info_t
 

Enumerations

enum  cand_kind { CAND_MULT , CAND_ADD , CAND_REF , CAND_PHI }
 
enum  cost_consts { COST_NEUTRAL = 0 , COST_INFINITE = 1000 }
 
enum  stride_status { UNKNOWN_STRIDE = 0 , KNOWN_STRIDE = 1 }
 
enum  phi_adjust_status { NOT_PHI_ADJUST = 0 , PHI_ADJUST = 1 }
 
enum  count_phis_status { DONT_COUNT_PHIS = 0 , COUNT_PHIS = 1 }
 

Functions

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)
 
static slsr_cand_t lookup_cand (cand_idx idx)
 
static tree get_alternative_base (tree base)
 
static cand_idx find_phi_def (tree base)
 
static bool uses_consumed_by_stmt (tree name, gimple *stmt, unsigned recurse=0)
 
static slsr_cand_t find_basis_for_base_expr (slsr_cand_t c, tree base_expr)
 
static int find_basis_for_candidate (slsr_cand_t c)
 
static void record_potential_basis (slsr_cand_t c, tree base)
 
static slsr_cand_t alloc_cand_and_find_basis (enum cand_kind kind, gimple *gs, tree base, const offset_int &index, tree stride, tree ctype, tree stype, unsigned savings)
 
static int stmt_cost (gimple *gs, bool speed)
 
static void add_cand_for_stmt (gimple *gs, slsr_cand_t c)
 
static void slsr_process_phi (gphi *phi, bool speed)
 
static offset_int backtrace_base_for_ref (tree *pbase)
 
static bool restructure_reference (tree *pbase, tree *poffset, offset_int *pindex, tree *ptype)
 
static void slsr_process_ref (gimple *gs)
 
static slsr_cand_t create_mul_ssa_cand (gimple *gs, tree base_in, tree stride_in, bool speed)
 
static slsr_cand_t create_mul_imm_cand (gimple *gs, tree base_in, tree stride_in, bool speed)
 
static void slsr_process_mul (gimple *gs, tree rhs1, tree rhs2, bool speed)
 
static slsr_cand_t create_add_ssa_cand (gimple *gs, tree base_in, tree addend_in, bool subtract_p, bool speed)
 
static slsr_cand_t create_add_imm_cand (gimple *gs, tree base_in, const offset_int &index_in, bool speed)
 
static void slsr_process_add (gimple *gs, tree rhs1, tree rhs2, bool speed)
 
static void slsr_process_neg (gimple *gs, tree rhs1, bool speed)
 
static bool legal_cast_p (gimple *gs, tree rhs)
 
static void slsr_process_cast (gimple *gs, tree rhs1, bool speed)
 
static void slsr_process_copy (gimple *gs, tree rhs1, bool speed)
 
static void dump_candidate (slsr_cand_t c)
 
static void dump_cand_vec (void)
 
int ssa_base_cand_dump_callback (cand_chain **slot, void *ignored)
 
static void dump_cand_chains (void)
 
static void dump_incr_vec (void)
 
static void replace_ref (tree *expr, slsr_cand_t c)
 
static bool valid_mem_ref_cand_p (slsr_cand_t c)
 
static void replace_refs (slsr_cand_t c)
 
static bool phi_dependent_cand_p (slsr_cand_t c)
 
static offset_int cand_increment (slsr_cand_t c)
 
static offset_int cand_abs_increment (slsr_cand_t c)
 
static bool cand_already_replaced (slsr_cand_t c)
 
static void replace_mult_candidate (slsr_cand_t c, tree basis_name, offset_int bump, auto_bitmap &sdce_worklist)
 
static void replace_unconditional_candidate (slsr_cand_t c, auto_bitmap &sdce_worklist)
 
static int incr_vec_index (const offset_int &increment)
 
static tree create_add_on_incoming_edge (slsr_cand_t c, tree basis_name, offset_int increment, edge e, location_t loc, bool known_stride)
 
static void clear_visited (gphi *phi)
 
static tree create_phi_basis_1 (slsr_cand_t c, gimple *from_phi, tree basis_name, location_t loc, bool known_stride)
 
static tree create_phi_basis (slsr_cand_t c, gimple *from_phi, tree basis_name, location_t loc, bool known_stride)
 
static void replace_conditional_candidate (slsr_cand_t c, auto_bitmap &sdce_worklist)
 
static int phi_add_costs_1 (gimple *phi, slsr_cand_t c, int one_add_cost, int *spread)
 
static int phi_add_costs (gimple *phi, slsr_cand_t c, int one_add_cost)
 
static void replace_uncond_cands_and_profitable_phis (slsr_cand_t c, auto_bitmap &sdce_worklist)
 
static int count_candidates (slsr_cand_t c)
 
static void record_increment (slsr_cand_t c, offset_int increment, bool is_phi_adjust)
 
static void record_phi_increments_1 (slsr_cand_t basis, gimple *phi)
 
static void record_phi_increments (slsr_cand_t basis, gimple *phi)
 
static void record_increments (slsr_cand_t c)
 
static int phi_incr_cost_1 (slsr_cand_t c, const offset_int &incr, gimple *phi, int *savings)
 
static int phi_incr_cost (slsr_cand_t c, const offset_int &incr, gimple *phi, int *savings)
 
static slsr_cand_t unreplaced_cand_in_tree (slsr_cand_t c)
 
static bool optimize_cands_for_speed_p (slsr_cand_t c)
 
static int lowest_cost_path (int cost_in, int repl_savings, slsr_cand_t c, const offset_int &incr, bool count_phis)
 
static int total_savings (int repl_savings, slsr_cand_t c, const offset_int &incr, bool count_phis)
 
static void analyze_increments (slsr_cand_t first_dep, machine_mode mode, bool speed)
 
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)
 
static basic_block ncd_with_phi (slsr_cand_t c, const offset_int &incr, gphi *phi, basic_block ncd, slsr_cand_t *where)
 
static basic_block ncd_of_cand_and_phis (slsr_cand_t c, const offset_int &incr, slsr_cand_t *where)
 
static basic_block nearest_common_dominator_for_cands (slsr_cand_t c, const offset_int &incr, slsr_cand_t *where)
 
static bool profitable_increment_p (unsigned index)
 
static void insert_initializers (slsr_cand_t c)
 
static bool all_phi_incrs_profitable_1 (slsr_cand_t c, gphi *phi, int *spread)
 
static bool all_phi_incrs_profitable (slsr_cand_t c, gphi *phi)
 
static gimplereplace_rhs_if_not_dup (enum tree_code new_code, tree new_rhs1, tree new_rhs2, enum tree_code old_code, tree old_rhs1, tree old_rhs2, slsr_cand_t c)
 
static void replace_one_candidate (slsr_cand_t c, unsigned i, tree basis_name, auto_bitmap &sdce_worklist)
 
static void replace_profitable_candidates (slsr_cand_t c, auto_bitmap &sdce_worklist)
 
static void analyze_candidates_and_replace (void)
 
gimple_opt_passmake_pass_strength_reduction (gcc::context *ctxt)
 

Variables

static vec< slsr_cand_tcand_vec
 
const int MAX_SPREAD = 16
 
static hash_map< gimple *, slsr_cand_t > * stmt_cand_map
 
static struct obstack cand_obstack
 
static struct obstack chain_obstack
 
static incr_info_t incr_vec
 
static unsigned incr_vec_len
 
const int MAX_INCR_VEC_LEN = 16
 
static bool address_arithmetic_p
 
static hash_table< cand_chain_hasher > * base_cand_map
 
static hash_map< tree, name_expansion * > * name_expansions
 
static hash_map< tree, tree > * alt_base_map
 

Typedef Documentation

◆ cand_chain

typedef struct cand_chain_d cand_chain

◆ cand_chain_t

typedef struct cand_chain_d * cand_chain_t

◆ cand_idx

typedef unsigned cand_idx
Straight-line strength reduction.
   Copyright (C) 2012-2024 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.   
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.   

◆ const_cand_chain_t

typedef const struct cand_chain_d* const_cand_chain_t

◆ const_slsr_cand_t

typedef const class slsr_cand_d* const_slsr_cand_t

◆ incr_info

typedef class incr_info_d incr_info

◆ incr_info_t

typedef class incr_info_d * incr_info_t

◆ slsr_cand

typedef class slsr_cand_d slsr_cand

◆ slsr_cand_t

typedef class slsr_cand_d * slsr_cand_t

Enumeration Type Documentation

◆ cand_kind

enum cand_kind
The kind of candidate.   
Enumerator
CAND_MULT 
CAND_ADD 
CAND_REF 
CAND_PHI 

◆ cost_consts

Enumerator
COST_NEUTRAL 
COST_INFINITE 

◆ count_phis_status

Enumerator
DONT_COUNT_PHIS 
COUNT_PHIS 

◆ phi_adjust_status

Enumerator
NOT_PHI_ADJUST 
PHI_ADJUST 

◆ stride_status

Enumerator
UNKNOWN_STRIDE 
KNOWN_STRIDE 

Function Documentation

◆ add_cand_for_stmt()

static void add_cand_for_stmt ( gimple * gs,
slsr_cand_t c )
static
Add an entry to the statement-to-candidate mapping.   

References gcc_assert, and stmt_cand_map.

Referenced by slsr_process_add(), slsr_process_cast(), slsr_process_copy(), slsr_process_mul(), slsr_process_neg(), slsr_process_phi(), and slsr_process_ref().

◆ all_phi_incrs_profitable()

static bool all_phi_incrs_profitable ( slsr_cand_t c,
gphi * phi )
static
Return TRUE iff all required increments for candidates feeding PHI
are profitable (and legal!) to replace on behalf of candidate C.   

References all_phi_incrs_profitable_1(), and clear_visited().

Referenced by replace_profitable_candidates().

◆ all_phi_incrs_profitable_1()

◆ alloc_cand_and_find_basis()

static slsr_cand_t alloc_cand_and_find_basis ( enum cand_kind kind,
gimple * gs,
tree base,
const offset_int & index,
tree stride,
tree ctype,
tree stype,
unsigned savings )
static
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;   

References CAND_MULT, cand_obstack, CAND_PHI, CAND_REF, cand_vec, find_basis_for_candidate(), find_phi_def(), get_alternative_base(), NULL_TREE, and record_potential_basis().

Referenced by create_add_imm_cand(), create_add_ssa_cand(), create_mul_imm_cand(), create_mul_ssa_cand(), slsr_process_cast(), slsr_process_copy(), slsr_process_phi(), and slsr_process_ref().

◆ analyze_candidates_and_replace()

◆ analyze_increments()

static void analyze_increments ( slsr_cand_t first_dep,
machine_mode mode,
bool speed )
static
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.   

References add_cost(), CAND_MULT, COST_INFINITE, COST_NEUTRAL, count, COUNT_PHIS, DONT_COUNT_PHIS, wi::fits_shwi_p(), gimple_assign_lhs(), i, incr_vec, incr_vec_len, legal_cast_p_1(), lowest_cost_path(), mul_cost(), mult_by_coeff_cost(), POINTER_TYPE_P, total_savings(), TREE_CODE, tree_fits_shwi_p(), tree_to_shwi(), and TREE_TYPE.

Referenced by analyze_candidates_and_replace().

◆ backtrace_base_for_ref()

static offset_int backtrace_base_for_ref ( tree * pbase)
static
Given PBASE which is a pointer to tree, look up the defining
statement for it and check whether the candidate is in the
form of:

  X = B + (1 * S), S is integer constant
  X = B + (i * S), S is integer one

If so, set PBASE to the candidate's base_expr and return double
int (i * S).
Otherwise, just return double int zero.   

References base_cand_from_table(), CAND_ADD, CAND_PHI, CONVERT_EXPR_P, get_unwidened(), integer_onep(), legal_cast_p_1(), lookup_cand(), NULL_TREE, STRIP_NOPS, wi::to_offset(), TREE_CODE, TREE_OPERAND, and TREE_TYPE.

Referenced by restructure_reference().

◆ base_cand_from_table()

static slsr_cand_t base_cand_from_table ( tree base_in)
static
Forward function declarations.   
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.   

References CAND_REF, NULL, SSA_NAME_DEF_STMT, and stmt_cand_map.

Referenced by all_phi_incrs_profitable_1(), backtrace_base_for_ref(), create_add_imm_cand(), create_add_ssa_cand(), create_mul_imm_cand(), create_mul_ssa_cand(), create_phi_basis_1(), find_phi_def(), ncd_with_phi(), phi_add_costs_1(), phi_incr_cost_1(), record_phi_increments_1(), slsr_process_cast(), slsr_process_copy(), and slsr_process_phi().

◆ cand_abs_increment()

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

References address_arithmetic_p, cand_increment(), and wi::neg_p().

Referenced by lowest_cost_path(), ncd_of_cand_and_phis(), replace_profitable_candidates(), and total_savings().

◆ cand_already_replaced()

static bool cand_already_replaced ( slsr_cand_t c)
inlinestatic

◆ cand_increment()

static offset_int cand_increment ( slsr_cand_t c)
static
Calculate the increment required for candidate C relative to
its basis.   

References gcc_assert, lookup_cand(), operand_equal_p(), and phi_dependent_cand_p().

Referenced by cand_abs_increment(), record_increments(), replace_one_candidate(), and replace_unconditional_candidate().

◆ clear_visited()

static void clear_visited ( gphi * phi)
static

◆ count_candidates()

static int count_candidates ( slsr_cand_t c)
static
Count the number of candidates in the tree rooted at C that have
not already been replaced under other interpretations.   

References cand_already_replaced(), count, count_candidates(), and lookup_cand().

Referenced by analyze_candidates_and_replace(), and count_candidates().

◆ create_add_imm_cand()

static slsr_cand_t create_add_imm_cand ( gimple * gs,
tree base_in,
const offset_int & index_in,
bool speed )
static
Create a candidate entry for a statement GS, where GS adds SSA
name BASE_IN to constant INDEX_IN.  Propagate any known information
about BASE_IN into the new candidate.  Return the new candidate.   

References alloc_cand_and_find_basis(), base_cand_from_table(), CAND_ADD, CAND_PHI, has_single_use(), integer_one_node, lookup_cand(), wi::multiple_of_p(), NULL_TREE, sizetype, stmt_cost(), wi::to_offset(), TREE_CODE, TREE_TYPE, and TYPE_SIGN.

Referenced by slsr_process_add().

◆ create_add_on_incoming_edge()

static tree create_add_on_incoming_edge ( slsr_cand_t c,
tree basis_name,
offset_int increment,
edge e,
location_t loc,
bool known_stride )
static
Create a new statement along edge E to add BASIS_NAME to the product
of INCREMENT and the stride of candidate C.  Create and return a new
SSA name from *VAR to be used as the LHS of the new statement.
KNOWN_STRIDE is true iff C's stride is a constant.   

References dump_file, dump_flags, gcc_assert, gcc_unreachable, gimple_build_assign(), gimple_set_location(), gsi_insert_on_edge(), i, incr_vec, incr_vec_index(), make_temp_ssa_name(), wi::neg_p(), NULL, POINTER_TYPE_P, print_gimple_stmt(), sizetype, TDF_DETAILS, wi::to_offset(), TREE_TYPE, types_compatible_p(), and wide_int_to_tree().

Referenced by create_phi_basis_1().

◆ create_add_ssa_cand()

static slsr_cand_t create_add_ssa_cand ( gimple * gs,
tree base_in,
tree addend_in,
bool subtract_p,
bool speed )
static
Create a candidate entry for a statement GS, where GS adds two
SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
subtracts ADDEND_IN from BASE_IN otherwise.  Propagate any known
information about the two SSA names into the new candidate.
Return the new candidate.   

References alloc_cand_and_find_basis(), base_cand_from_table(), CAND_ADD, CAND_MULT, CAND_PHI, has_single_use(), integer_zero_node, lookup_cand(), NULL_TREE, operand_equal_p(), sizetype, stmt_cost(), wi::to_offset(), TREE_CODE, and TREE_TYPE.

Referenced by slsr_process_add().

◆ create_mul_imm_cand()

static slsr_cand_t create_mul_imm_cand ( gimple * gs,
tree base_in,
tree stride_in,
bool speed )
static
Create a candidate entry for a statement GS, where GS multiplies
SSA name BASE_IN by constant STRIDE_IN.  Propagate any known
information about BASE_IN into the new candidate.  Return the new
candidate.   

References alloc_cand_and_find_basis(), base_cand_from_table(), CAND_ADD, CAND_MULT, CAND_PHI, wi::fits_to_tree_p(), has_single_use(), integer_onep(), lookup_cand(), NULL_TREE, sizetype, stmt_cost(), wi::to_offset(), TREE_CODE, TREE_TYPE, and wide_int_to_tree().

Referenced by slsr_process_mul(), and slsr_process_neg().

◆ create_mul_ssa_cand()

static slsr_cand_t create_mul_ssa_cand ( gimple * gs,
tree base_in,
tree stride_in,
bool speed )
static
Create a candidate entry for a statement GS, where GS multiplies
two SSA names BASE_IN and STRIDE_IN.  Propagate any known information
about the two SSA names into the new candidate.  Return the new
candidate.   

References alloc_cand_and_find_basis(), base_cand_from_table(), CAND_ADD, CAND_MULT, CAND_PHI, has_single_use(), integer_onep(), lookup_cand(), NULL_TREE, stmt_cost(), wi::to_offset(), TREE_CODE, and TREE_TYPE.

Referenced by slsr_process_mul().

◆ create_phi_basis()

static tree create_phi_basis ( slsr_cand_t c,
gimple * from_phi,
tree basis_name,
location_t loc,
bool known_stride )
static
Given a candidate C with BASIS_NAME being the LHS of C's basis which
is hidden by the phi node FROM_PHI, create a new phi node in the same
block as FROM_PHI.  The new phi is suitable for use as a basis by C,
with its phi arguments representing conditional adjustments to the
hidden basis along conditional incoming paths.  Those adjustments are
made by creating add statements (and sometimes recursively creating
phis) along those incoming paths.  LOC is the location to attach to
the introduced statements.  KNOWN_STRIDE is true iff C's stride is a
constant.   

References as_a(), clear_visited(), create_phi_basis_1(), and gcc_assert.

Referenced by replace_conditional_candidate(), and replace_profitable_candidates().

◆ create_phi_basis_1()

◆ dump_cand_chains()

static void dump_cand_chains ( void )
static
Dump the candidate chains.   

References base_cand_map, dump_file, NULL, and ssa_base_cand_dump_callback().

◆ dump_cand_vec()

static void dump_cand_vec ( void )
static
Dump the candidate vector for debug.   

References cand_vec, dump_candidate(), dump_file, FOR_EACH_VEC_ELT, i, and NULL.

◆ dump_candidate()

static void dump_candidate ( slsr_cand_t c)
static

◆ dump_incr_vec()

static void dump_incr_vec ( void )
static
Dump the increment vector for debug.   

References count, dump_file, dump_flags, i, incr_vec, incr_vec_len, print_decs(), print_generic_expr(), and TDF_DETAILS.

Referenced by analyze_candidates_and_replace().

◆ find_basis_for_base_expr()

static slsr_cand_t find_basis_for_base_expr ( slsr_cand_t c,
tree base_expr )
static
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.   

References base_cand_map, cand_chain_d::base_expr, CDI_DOMINATORS, dominated_by_p(), gimple_assign_lhs(), gimple_bb(), NULL, operand_equal_p(), SSA_NAME_OCCURS_IN_ABNORMAL_PHI, TREE_CODE, and types_compatible_p().

Referenced by find_basis_for_candidate().

◆ find_basis_for_candidate()

static int find_basis_for_candidate ( slsr_cand_t c)
static
Use the base expr from candidate C to look for possible candidates
that can serve as a basis for C.  Each potential basis must also
appear in a block that dominates the candidate statement and have
the same stride and type.  If more than one possible basis exists,
the one with highest index in the vector is chosen; this will be
the most immediately dominating basis.   

References CAND_REF, CDI_DOMINATORS, dominated_by_p(), find_basis_for_base_expr(), get_alternative_base(), gimple_bb(), gimple_phi_result(), lookup_cand(), NULL, and uses_consumed_by_stmt().

Referenced by alloc_cand_and_find_basis().

◆ find_phi_def()

static cand_idx find_phi_def ( tree base)
static
Look in the candidate table for a CAND_PHI that defines BASE and
return it if found; otherwise return NULL.   

References base_cand_from_table(), CAND_PHI, gimple_phi_result(), SSA_NAME_OCCURS_IN_ABNORMAL_PHI, and TREE_CODE.

Referenced by alloc_cand_and_find_basis().

◆ get_alternative_base()

static tree get_alternative_base ( tree base)
static
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.   

References aff_combination_to_tree(), alt_base_map, expr, gcc_assert, hash_map< KeyId, Value, Traits >::get(), name_expansions, NULL, aff_tree::offset, hash_map< KeyId, Value, Traits >::put(), tree_to_aff_combination_expand(), and TREE_TYPE.

Referenced by alloc_cand_and_find_basis(), and find_basis_for_candidate().

◆ incr_vec_index()

static int incr_vec_index ( const offset_int & increment)
inlinestatic
Return the index in the increment vector of the given INCREMENT,
or -1 if not found.  The latter can occur if more than
MAX_INCR_VEC_LEN increments have been found.   

References i, incr_vec, and incr_vec_len.

Referenced by all_phi_incrs_profitable_1(), create_add_on_incoming_edge(), and replace_profitable_candidates().

◆ insert_initializers()

static void insert_initializers ( slsr_cand_t c)
static
For each profitable increment in the increment vector not equal to
0 or 1 (or -1, for non-pointer arithmetic), find the nearest common
dominator of all statements in the candidate chain rooted at C
that require that increment, and insert an initializer
T_0 = stride * increment at that location.  Record T_0 with the
increment record.   

References CDI_DOMINATORS, COST_INFINITE, dominated_by_p(), dump_file, dump_flags, gimple_bb(), gimple_build_assign(), gimple_location(), gimple_set_location(), gsi_end_p(), gsi_for_stmt(), gsi_insert_after(), gsi_insert_before(), gsi_last_bb(), GSI_NEW_STMT, GSI_SAME_STMT, gsi_stmt(), i, incr_vec, incr_vec_len, lookup_cand(), make_temp_ssa_name(), nearest_common_dominator_for_cands(), NULL, POINTER_TYPE_P, print_gimple_stmt(), profitable_increment_p(), SSA_NAME_DEF_STMT, stmt_ends_bb_p(), TDF_DETAILS, TDF_NONE, TREE_TYPE, types_compatible_p(), and wide_int_to_tree().

Referenced by analyze_candidates_and_replace().

◆ introduce_cast_before_cand()

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

References dump_file, dump_flags, gimple_build_assign(), gimple_location(), gimple_set_location(), gsi_for_stmt(), gsi_insert_before(), GSI_SAME_STMT, make_temp_ssa_name(), NULL, print_gimple_stmt(), and TDF_DETAILS.

Referenced by replace_mult_candidate(), and replace_one_candidate().

◆ legal_cast_p()

static bool legal_cast_p ( gimple * gs,
tree rhs )
static
Return TRUE if GS is a statement that defines an SSA name from
a conversion and is legal for us to combine with an add and multiply
in the candidate table.  For example, suppose we have:

  A = B + i;
  C = (type) A;
  D = C * S;

Without the 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.   

References CONVERT_EXPR_CODE_P, gimple_assign_lhs(), gimple_assign_rhs_code(), is_gimple_assign(), legal_cast_p_1(), and TREE_TYPE.

Referenced by slsr_process_cast().

◆ legal_cast_p_1()

static bool legal_cast_p_1 ( tree lhs_type,
tree rhs_type )
static
Help function for legal_cast_p, operating on two trees.  Checks
whether it's allowable to cast from RHS to LHS.  See legal_cast_p
for more details.   

References ANY_INTEGRAL_TYPE_P, TYPE_OVERFLOW_WRAPS, and TYPE_PRECISION.

Referenced by analyze_increments(), backtrace_base_for_ref(), and legal_cast_p().

◆ lookup_cand()

◆ lowest_cost_path()

static int lowest_cost_path ( int cost_in,
int repl_savings,
slsr_cand_t c,
const offset_int & incr,
bool count_phis )
static
Add COST_IN to the lowest cost of any dependent path starting at
candidate C or any of its siblings, counting only candidates along
such paths with increment INCR.  Assume that replacing a candidate
reduces cost by REPL_SAVINGS.  Also account for savings from any
statements that would go dead.  If COUNT_PHIS is true, include
costs of introducing feeding statements for conditional candidates.   

References cand_abs_increment(), cand_already_replaced(), gimple_phi_result(), lookup_cand(), lowest_cost_path(), MIN, phi_dependent_cand_p(), phi_incr_cost(), and uses_consumed_by_stmt().

Referenced by analyze_increments(), and lowest_cost_path().

◆ make_pass_strength_reduction()

gimple_opt_pass * make_pass_strength_reduction ( gcc::context * ctxt)

◆ ncd_for_two_cands()

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 )
static
Return the nearest common dominator of BB1 and BB2.  If the blocks
are identical, return the earlier of C1 and C2 in *WHERE.  Otherwise,
if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2,
return C2 in *WHERE; and if the NCD matches neither, return NULL in
*WHERE.  Note: It is possible for one of C1 and C2 to be NULL.   

References CDI_DOMINATORS, nearest_common_dominator(), and NULL.

Referenced by ncd_with_phi(), and nearest_common_dominator_for_cands().

◆ ncd_of_cand_and_phis()

static basic_block ncd_of_cand_and_phis ( slsr_cand_t c,
const offset_int & incr,
slsr_cand_t * where )
static
Consider the candidate C together with any candidates that feed
C's phi dependence (if any).  Find and return the nearest common
dominator of those candidates requiring the given increment INCR.
If the returned block contains one or more of the candidates,
return the earliest candidate in the block in *WHERE.   

References as_a(), cand_abs_increment(), gimple_bb(), lookup_cand(), ncd_with_phi(), NULL, and phi_dependent_cand_p().

Referenced by nearest_common_dominator_for_cands().

◆ ncd_with_phi()

static basic_block ncd_with_phi ( slsr_cand_t c,
const offset_int & incr,
gphi * phi,
basic_block ncd,
slsr_cand_t * where )
static
Consider all candidates that feed PHI.  Find the nearest common
dominator of those candidates requiring the given increment INCR.
Further find and return the nearest common dominator of this result
with block NCD.  If the returned block contains one or more of the
candidates, return the earliest candidate in the block in *WHERE.   

References address_arithmetic_p, as_a(), base_cand_from_table(), gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_num_args(), i, lookup_cand(), ncd_for_two_cands(), ncd_with_phi(), NULL, operand_equal_p(), SSA_NAME_DEF_STMT, and stmt_cand_map.

Referenced by ncd_of_cand_and_phis(), and ncd_with_phi().

◆ nearest_common_dominator_for_cands()

static basic_block nearest_common_dominator_for_cands ( slsr_cand_t c,
const offset_int & incr,
slsr_cand_t * where )
static
Consider all candidates in the tree rooted at C for which INCR
represents the required increment of C relative to its basis.
Find and return the basic block that most nearly dominates all
such candidates.  If the returned block contains one or more of
the candidates, return the earliest candidate in the block in
*WHERE.   

References cand_already_replaced(), lookup_cand(), ncd_for_two_cands(), ncd_of_cand_and_phis(), nearest_common_dominator_for_cands(), and NULL.

Referenced by insert_initializers(), and nearest_common_dominator_for_cands().

◆ optimize_cands_for_speed_p()

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

References gcc_assert, gimple_bb(), optimize_bb_for_speed_p(), and unreplaced_cand_in_tree().

Referenced by analyze_candidates_and_replace().

◆ phi_add_costs()

static int phi_add_costs ( gimple * phi,
slsr_cand_t c,
int one_add_cost )
static
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.   

References as_a(), clear_visited(), and phi_add_costs_1().

Referenced by replace_uncond_cands_and_profitable_phis().

◆ phi_add_costs_1()

static int phi_add_costs_1 ( gimple * phi,
slsr_cand_t c,
int one_add_cost,
int * spread )
static
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.   

References base_cand_from_table(), CDI_DOMINATORS, COST_INFINITE, dominated_by_p(), gimple_bb(), gimple_phi_arg_def(), gimple_phi_num_args(), i, lookup_cand(), MAX_SPREAD, phi_add_costs_1(), SSA_NAME_DEF_STMT, and stmt_cand_map.

Referenced by phi_add_costs(), and phi_add_costs_1().

◆ phi_dependent_cand_p()

static bool phi_dependent_cand_p ( slsr_cand_t c)
static

◆ phi_incr_cost()

static int phi_incr_cost ( slsr_cand_t c,
const offset_int & incr,
gimple * phi,
int * savings )
static
Add up and return the costs of introducing add statements that
require the increment INCR on behalf of candidate C and phi
statement PHI.  Accumulate into *SAVINGS the potential savings
from removing existing statements that feed PHI and have no other
uses.   

References as_a(), clear_visited(), and phi_incr_cost_1().

Referenced by lowest_cost_path(), and total_savings().

◆ phi_incr_cost_1()

static int phi_incr_cost_1 ( slsr_cand_t c,
const offset_int & incr,
gimple * phi,
int * savings )
static

◆ profitable_increment_p()

static bool profitable_increment_p ( unsigned index)
inlinestatic
Return TRUE if the increment indexed by INDEX is profitable to replace.   

References COST_NEUTRAL, incr_vec, and mem_address::index.

Referenced by all_phi_incrs_profitable_1(), insert_initializers(), and replace_profitable_candidates().

◆ record_increment()

static void record_increment ( slsr_cand_t c,
offset_int increment,
bool is_phi_adjust )
static
Increase the count of INCREMENT by one in the increment vector.
INCREMENT is associated with candidate C.  If INCREMENT is to be
conditionally executed as part of a conditional candidate replacement,
IS_PHI_ADJUST is true, otherwise false.  If an initializer
T_0 = stride * I is provided by a candidate that dominates all
candidates with the same increment, also record T_0 for subsequent use.   

References address_arithmetic_p, CAND_ADD, CDI_DOMINATORS, COST_INFINITE, dominated_by_p(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_bb(), i, incr_vec, incr_vec_len, MAX_INCR_VEC_LEN, wi::neg_p(), NULL, NULL_TREE, operand_equal_p(), and SSA_NAME_DEF_STMT.

Referenced by record_increments(), and record_phi_increments_1().

◆ record_increments()

static void record_increments ( slsr_cand_t c)
static
Determine how many times each unique increment occurs in the set
of candidates rooted at C's parent, recording the data in the
increment vector.  For each unique increment I, if an initializer
T_0 = stride * I is provided by a candidate that dominates all
candidates with the same increment, also record T_0 for subsequent
use.   

References cand_already_replaced(), cand_increment(), lookup_cand(), NOT_PHI_ADJUST, phi_dependent_cand_p(), record_increment(), record_increments(), and record_phi_increments().

Referenced by analyze_candidates_and_replace(), and record_increments().

◆ record_phi_increments()

static void record_phi_increments ( slsr_cand_t basis,
gimple * phi )
static
Given phi statement PHI that hides a candidate from its BASIS, find
the increments along each incoming arc (recursively handling additional
phis that may be present) and record them.  These increments are the
difference in index between the index-adjusting statements and the
index of the basis.   

References as_a(), clear_visited(), and record_phi_increments_1().

Referenced by record_increments().

◆ record_phi_increments_1()

static void record_phi_increments_1 ( slsr_cand_t basis,
gimple * phi )
static

◆ record_potential_basis()

static void record_potential_basis ( slsr_cand_t c,
tree base )
static
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.   

References base_cand_map, cand_chain_d::base_expr, cand_chain_d::cand, chain_obstack, gcc_assert, cand_chain_d::next, and NULL.

Referenced by alloc_cand_and_find_basis().

◆ replace_conditional_candidate()

static void replace_conditional_candidate ( slsr_cand_t c,
auto_bitmap & sdce_worklist )
static
Given a candidate C whose basis is hidden by at least one intervening
phi, introduce a matching number of new phis to represent its basis
adjusted by conditional increments along possible incoming paths.  Then
replace C as though it were an unconditional candidate, using the new
basis.   

References create_phi_basis(), gimple_assign_lhs(), gimple_location(), KNOWN_STRIDE, lookup_cand(), replace_mult_candidate(), and wi::to_offset().

Referenced by replace_uncond_cands_and_profitable_phis().

◆ replace_mult_candidate()

◆ replace_one_candidate()

static void replace_one_candidate ( slsr_cand_t c,
unsigned i,
tree basis_name,
auto_bitmap & sdce_worklist )
static
Strength-reduce the statement represented by candidate C by replacing
it with an equivalent addition or subtraction.  I is the index into
the increment vector identifying C's increment.  NEW_VAR is used to
create a new SSA name if a cast needs to be introduced.  BASIS_NAME
is the rhs1 to use in creating the add/subtract.   

References address_arithmetic_p, bitmap_set_bit, cand_increment(), dump_file, dump_flags, gcc_assert, gcc_unreachable, gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_assign_set_rhs_with_ops(), gimple_build_assign(), gimple_location(), gimple_set_location(), gsi_for_stmt(), gsi_replace(), gsi_stmt(), i, incr_vec, introduce_cast_before_cand(), lookup_cand(), NULL, operand_equal_p(), print_gimple_stmt(), replace_rhs_if_not_dup(), SSA_NAME_VERSION, TDF_DETAILS, TREE_CODE, TREE_TYPE, types_compatible_p(), and update_stmt().

Referenced by replace_profitable_candidates().

◆ replace_profitable_candidates()

◆ replace_ref()

static void replace_ref ( tree * expr,
slsr_cand_t c )
static

◆ replace_refs()

static void replace_refs ( slsr_cand_t c)
static
Replace CAND_REF candidate C, each sibling of candidate C, and each
dependent of candidate C with an equivalent strength-reduced data
reference.   

References dump_file, dump_flags, gimple_assign_lhs_ptr(), gimple_assign_rhs1_ptr(), gimple_vdef(), lookup_cand(), print_gimple_stmt(), replace_ref(), replace_refs(), TDF_DETAILS, and valid_mem_ref_cand_p().

Referenced by analyze_candidates_and_replace(), and replace_refs().

◆ replace_rhs_if_not_dup()

static gimple * replace_rhs_if_not_dup ( enum tree_code new_code,
tree new_rhs1,
tree new_rhs2,
enum tree_code old_code,
tree old_rhs1,
tree old_rhs2,
slsr_cand_t c )
static
Replace the RHS of the statement represented by candidate C with
NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't
leave C unchanged or just interchange its operands.  The original
operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2.
If the replacement was made and we are doing a details dump,
return the revised statement, else NULL.   

References dump_file, dump_flags, gimple_assign_set_rhs_with_ops(), gsi_for_stmt(), gsi_stmt(), lookup_cand(), NULL, operand_equal_p(), TDF_DETAILS, and update_stmt().

Referenced by replace_one_candidate().

◆ replace_uncond_cands_and_profitable_phis()

static void replace_uncond_cands_and_profitable_phis ( slsr_cand_t c,
auto_bitmap & sdce_worklist )
static
For candidate C, each sibling of candidate C, and each dependent of
candidate C, determine whether the candidate is dependent upon a
phi that hides its basis.  If not, replace the candidate unconditionally.
Otherwise, determine whether the cost of introducing compensation code
for the candidate is offset by the gains from strength reduction.  If
so, replace the candidate and introduce the compensation code.   

References add_cost(), CAND_MULT, COST_NEUTRAL, dump_file, dump_flags, gimple_bb(), gimple_phi_result(), lookup_cand(), optimize_bb_for_speed_p(), phi_add_costs(), phi_dependent_cand_p(), replace_conditional_candidate(), replace_uncond_cands_and_profitable_phis(), replace_unconditional_candidate(), stmt_cost(), TDF_DETAILS, wi::to_offset(), TREE_TYPE, and TYPE_MODE.

Referenced by analyze_candidates_and_replace(), and replace_uncond_cands_and_profitable_phis().

◆ replace_unconditional_candidate()

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

References cand_already_replaced(), cand_increment(), gimple_assign_lhs(), lookup_cand(), replace_mult_candidate(), and wi::to_offset().

Referenced by replace_uncond_cands_and_profitable_phis().

◆ restructure_reference()

static bool restructure_reference ( tree * pbase,
tree * poffset,
offset_int * pindex,
tree * ptype )
static
Look for the following pattern:

 *PBASE:    MEM_REF (T1, C1)

 *POFFSET:  MULT_EXPR (T2, C3)        [C2 is zero]
                  or
            MULT_EXPR (PLUS_EXPR (T2, C2), C3)
                  or
            MULT_EXPR (MINUS_EXPR (T2, -C2), C3)

 *PINDEX:   C4 * BITS_PER_UNIT

If not present, leave the input values unchanged and return FALSE.
Otherwise, modify the input values as follows and return TRUE:

 *PBASE:    T1
 *POFFSET:  MULT_EXPR (T2, C3)
 *PINDEX:   C1 + (C2 * C3) + C4

When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it
will be further restructured to:

 *PBASE:    T1
 *POFFSET:  MULT_EXPR (T2', C3)
 *PINDEX:   C1 + (C2 * C3) + C4 + (C5 * C3)   

References backtrace_base_for_ref(), fold_build2, fold_convert, mem_ref_offset(), offset, SIGNED, sizetype, wi::to_offset(), TREE_CODE, TREE_OPERAND, TREE_TYPE, type(), wi::umod_floor(), and wide_int_to_tree().

Referenced by slsr_process_ref().

◆ slsr_process_add()

static void slsr_process_add ( gimple * gs,
tree rhs1,
tree rhs2,
bool speed )
static
Given GS which is an add or subtract of scalar integers or pointers,
make at least one appropriate entry in the candidate table.   

References add_cand_for_stmt(), create_add_imm_cand(), create_add_ssa_cand(), gimple_assign_rhs_code(), NULL, operand_equal_p(), POINTER_TYPE_P, wi::to_offset(), TREE_CODE, and TREE_TYPE.

Referenced by find_candidates_dom_walker::before_dom_children().

◆ slsr_process_cast()

static void slsr_process_cast ( gimple * gs,
tree rhs1,
bool speed )
static
Given GS which is a cast to a scalar integer type, determine whether
the cast is legal for strength reduction.  If so, make at least one
appropriate entry in the candidate table.   

References add_cand_for_stmt(), alloc_cand_and_find_basis(), base_cand_from_table(), CAND_ADD, CAND_MULT, CAND_PHI, gimple_assign_lhs(), has_single_use(), integer_one_node, legal_cast_p(), lookup_cand(), NULL, sizetype, stmt_cost(), and TREE_TYPE.

Referenced by find_candidates_dom_walker::before_dom_children().

◆ slsr_process_copy()

static void slsr_process_copy ( gimple * gs,
tree rhs1,
bool speed )
static
Given GS which is a copy of a scalar integer type, make at least one
appropriate entry in the candidate table.

This interface is included for completeness, but is unnecessary
if this pass immediately follows a pass that performs copy
propagation, such as DOM.   

References add_cand_for_stmt(), alloc_cand_and_find_basis(), base_cand_from_table(), CAND_ADD, CAND_MULT, CAND_PHI, has_single_use(), integer_one_node, lookup_cand(), NULL, sizetype, stmt_cost(), and TREE_TYPE.

Referenced by find_candidates_dom_walker::before_dom_children().

◆ slsr_process_mul()

static void slsr_process_mul ( gimple * gs,
tree rhs1,
tree rhs2,
bool speed )
static
Given GS which is a multiply of scalar integers, make an appropriate
entry in the candidate table.  If this is a multiply of two SSA names,
create two CAND_MULT interpretations and attempt to find a basis for
each of them.  Otherwise, create a single CAND_MULT and attempt to
find a basis.   

References add_cand_for_stmt(), create_mul_imm_cand(), create_mul_ssa_cand(), integer_zerop(), and TREE_CODE.

Referenced by find_candidates_dom_walker::before_dom_children().

◆ slsr_process_neg()

static void slsr_process_neg ( gimple * gs,
tree rhs1,
bool speed )
static
Given GS which is a negate of a scalar integer, make an appropriate
entry in the candidate table.  A negate is equivalent to a multiply
by -1.   

References add_cand_for_stmt(), create_mul_imm_cand(), and integer_minus_one_node.

Referenced by find_candidates_dom_walker::before_dom_children().

◆ slsr_process_phi()

static void slsr_process_phi ( gphi * phi,
bool speed )
static
Given PHI which contains a phi statement, determine whether it
satisfies all the requirements of a phi candidate.  If so, create
a candidate.  Note that a CAND_PHI never has a basis itself, but
is used to help find a basis for subsequent candidates.   

References add_cand_for_stmt(), alloc_cand_and_find_basis(), base_cand_from_table(), CAND_ADD, CAND_PHI, cfun, ENTRY_BLOCK_PTR_FOR_FN, gimple_bb(), gimple_phi_arg_def(), gimple_phi_num_args(), i, integer_one_node, integer_onep(), lookup_cand(), basic_block_def::loop_father, NULL, NULL_TREE, operand_equal_p(), single_succ(), sizetype, SSA_NAME_IS_DEFAULT_DEF, stmt_cost(), TREE_CODE, TREE_TYPE, and uses_consumed_by_stmt().

Referenced by find_candidates_dom_walker::before_dom_children().

◆ slsr_process_ref()

static void slsr_process_ref ( gimple * gs)
static

◆ ssa_base_cand_dump_callback()

int ssa_base_cand_dump_callback ( cand_chain ** slot,
void * ignored )
Callback used to dump the candidate chains hash table.   

References cand_chain_d::cand, dump_file, cand_chain_d::next, and print_generic_expr().

Referenced by dump_cand_chains().

◆ stmt_cost()

◆ total_savings()

static int total_savings ( int repl_savings,
slsr_cand_t c,
const offset_int & incr,
bool count_phis )
static
Compute the total savings that would accrue from all replacements
in the candidate tree rooted at C, counting only candidates with
increment INCR.  Assume that replacing a candidate reduces cost
by REPL_SAVINGS.  Also account for savings from statements that
would go dead.   

References cand_abs_increment(), cand_already_replaced(), gimple_phi_result(), lookup_cand(), phi_dependent_cand_p(), phi_incr_cost(), total_savings(), and uses_consumed_by_stmt().

Referenced by analyze_increments(), and total_savings().

◆ unreplaced_cand_in_tree()

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

References cand_already_replaced(), lookup_cand(), NULL, and unreplaced_cand_in_tree().

Referenced by optimize_cands_for_speed_p(), and unreplaced_cand_in_tree().

◆ uses_consumed_by_stmt()

static bool uses_consumed_by_stmt ( tree name,
gimple * stmt,
unsigned recurse = 0 )
static
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.   

References FOR_EACH_IMM_USE_STMT, gimple_get_lhs(), is_gimple_assign(), is_gimple_debug(), is_gimple_reg(), and uses_consumed_by_stmt().

Referenced by find_basis_for_candidate(), lowest_cost_path(), phi_incr_cost_1(), slsr_process_phi(), total_savings(), and uses_consumed_by_stmt().

◆ valid_mem_ref_cand_p()

static bool valid_mem_ref_cand_p ( slsr_cand_t c)
static
Return true if CAND_REF candidate C is a valid memory reference.   

References NULL_TREE, sizetype, TREE_CODE, TREE_OPERAND, TYPE_ADDR_SPACE, TYPE_MODE, valid_mem_ref_p(), and wide_int_to_tree().

Referenced by replace_refs().

Variable Documentation

◆ address_arithmetic_p

bool address_arithmetic_p
static
For a chain of candidates with unknown stride, indicates whether or not
we must generate pointer arithmetic when replacing statements.   

Referenced by all_phi_incrs_profitable_1(), analyze_candidates_and_replace(), cand_abs_increment(), ncd_with_phi(), record_increment(), and replace_one_candidate().

◆ alt_base_map

hash_map<tree, tree>* alt_base_map
static
Pointer map embodying a mapping from bases to alternative bases.   

Referenced by get_alternative_base().

◆ base_cand_map

hash_table<cand_chain_hasher>* base_cand_map
static
Hash table embodying a mapping from base exprs to chains of candidates.   

Referenced by dump_cand_chains(), find_basis_for_base_expr(), and record_potential_basis().

◆ cand_obstack

struct obstack cand_obstack
static
Obstack for candidates.   

Referenced by alloc_cand_and_find_basis().

◆ cand_vec

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

Referenced by alloc_cand_and_find_basis(), analyze_candidates_and_replace(), dump_cand_vec(), lookup_cand(), and undistribute_bitref_for_vector().

◆ chain_obstack

struct obstack chain_obstack
static
Obstack for candidate chains.   

Referenced by record_potential_basis().

◆ incr_vec

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

Referenced by all_phi_incrs_profitable_1(), analyze_candidates_and_replace(), analyze_increments(), create_add_on_incoming_edge(), dump_incr_vec(), incr_vec_index(), insert_initializers(), profitable_increment_p(), record_increment(), and replace_one_candidate().

◆ incr_vec_len

◆ MAX_INCR_VEC_LEN

const int MAX_INCR_VEC_LEN = 16

◆ MAX_SPREAD

const int MAX_SPREAD = 16
Constrain how many PHI nodes we will visit for a conditional
candidate (depth and breadth).   

Referenced by all_phi_incrs_profitable_1(), and phi_add_costs_1().

◆ name_expansions

hash_map<tree, name_expansion *>* name_expansions
static
Pointer map used by tree_to_aff_combination_expand.   

Referenced by get_alternative_base().

◆ stmt_cand_map