LCOV - code coverage report
Current view: top level - gcc - gimple-ssa-strength-reduction.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1435 1610 89.1 %
Date: 2020-04-04 11:58:09 Functions: 74 76 97.4 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Straight-line strength reduction.
       2                 :            :    Copyright (C) 2012-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify it under
       8                 :            : the terms of the GNU General Public License as published by the Free
       9                 :            : Software Foundation; either version 3, or (at your option) any later
      10                 :            : version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :            : for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : /* There are many algorithms for performing strength reduction on
      22                 :            :    loops.  This is not one of them.  IVOPTS handles strength reduction
      23                 :            :    of induction variables just fine.  This pass is intended to pick
      24                 :            :    up the crumbs it leaves behind, by considering opportunities for
      25                 :            :    strength reduction along dominator paths.
      26                 :            : 
      27                 :            :    Strength reduction addresses explicit multiplies, and certain
      28                 :            :    multiplies implicit in addressing expressions.  It would also be
      29                 :            :    possible to apply strength reduction to divisions and modulos,
      30                 :            :    but such opportunities are relatively uncommon.
      31                 :            : 
      32                 :            :    Strength reduction is also currently restricted to integer operations.
      33                 :            :    If desired, it could be extended to floating-point operations under
      34                 :            :    control of something like -funsafe-math-optimizations.  */
      35                 :            : 
      36                 :            : #include "config.h"
      37                 :            : #include "system.h"
      38                 :            : #include "coretypes.h"
      39                 :            : #include "backend.h"
      40                 :            : #include "rtl.h"
      41                 :            : #include "tree.h"
      42                 :            : #include "gimple.h"
      43                 :            : #include "cfghooks.h"
      44                 :            : #include "tree-pass.h"
      45                 :            : #include "ssa.h"
      46                 :            : #include "expmed.h"
      47                 :            : #include "gimple-pretty-print.h"
      48                 :            : #include "fold-const.h"
      49                 :            : #include "gimple-iterator.h"
      50                 :            : #include "gimplify-me.h"
      51                 :            : #include "stor-layout.h"
      52                 :            : #include "cfgloop.h"
      53                 :            : #include "tree-cfg.h"
      54                 :            : #include "domwalk.h"
      55                 :            : #include "tree-ssa-address.h"
      56                 :            : #include "tree-affine.h"
      57                 :            : #include "tree-eh.h"
      58                 :            : #include "builtins.h"
      59                 :            : 
      60                 :            : /* Information about a strength reduction candidate.  Each statement
      61                 :            :    in the candidate table represents an expression of one of the
      62                 :            :    following forms (the special case of CAND_REF will be described
      63                 :            :    later):
      64                 :            : 
      65                 :            :    (CAND_MULT)  S1:  X = (B + i) * S
      66                 :            :    (CAND_ADD)   S1:  X = B + (i * S)
      67                 :            : 
      68                 :            :    Here X and B are SSA names, i is an integer constant, and S is
      69                 :            :    either an SSA name or a constant.  We call B the "base," i the
      70                 :            :    "index", and S the "stride."
      71                 :            : 
      72                 :            :    Any statement S0 that dominates S1 and is of the form:
      73                 :            : 
      74                 :            :    (CAND_MULT)  S0:  Y = (B + i') * S
      75                 :            :    (CAND_ADD)   S0:  Y = B + (i' * S)
      76                 :            : 
      77                 :            :    is called a "basis" for S1.  In both cases, S1 may be replaced by
      78                 :            :    
      79                 :            :                 S1':  X = Y + (i - i') * S,
      80                 :            : 
      81                 :            :    where (i - i') * S is folded to the extent possible.
      82                 :            : 
      83                 :            :    All gimple statements are visited in dominator order, and each
      84                 :            :    statement that may contribute to one of the forms of S1 above is
      85                 :            :    given at least one entry in the candidate table.  Such statements
      86                 :            :    include addition, pointer addition, subtraction, multiplication,
      87                 :            :    negation, copies, and nontrivial type casts.  If a statement may
      88                 :            :    represent more than one expression of the forms of S1 above, 
      89                 :            :    multiple "interpretations" are stored in the table and chained
      90                 :            :    together.  Examples:
      91                 :            : 
      92                 :            :    * An add of two SSA names may treat either operand as the base.
      93                 :            :    * A multiply of two SSA names, likewise.
      94                 :            :    * A copy or cast may be thought of as either a CAND_MULT with
      95                 :            :      i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0.
      96                 :            : 
      97                 :            :    Candidate records are allocated from an obstack.  They are addressed
      98                 :            :    both from a hash table keyed on S1, and from a vector of candidate
      99                 :            :    pointers arranged in predominator order.
     100                 :            : 
     101                 :            :    Opportunity note
     102                 :            :    ----------------
     103                 :            :    Currently we don't recognize:
     104                 :            : 
     105                 :            :      S0: Y = (S * i') - B
     106                 :            :      S1: X = (S * i) - B
     107                 :            : 
     108                 :            :    as a strength reduction opportunity, even though this S1 would
     109                 :            :    also be replaceable by the S1' above.  This can be added if it
     110                 :            :    comes up in practice.
     111                 :            : 
     112                 :            :    Strength reduction in addressing
     113                 :            :    --------------------------------
     114                 :            :    There is another kind of candidate known as CAND_REF.  A CAND_REF
     115                 :            :    describes a statement containing a memory reference having 
     116                 :            :    complex addressing that might benefit from strength reduction.
     117                 :            :    Specifically, we are interested in references for which 
     118                 :            :    get_inner_reference returns a base address, offset, and bitpos as
     119                 :            :    follows:
     120                 :            : 
     121                 :            :      base:    MEM_REF (T1, C1)
     122                 :            :      offset:  MULT_EXPR (PLUS_EXPR (T2, C2), C3)
     123                 :            :      bitpos:  C4 * BITS_PER_UNIT
     124                 :            : 
     125                 :            :    Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are 
     126                 :            :    arbitrary integer constants.  Note that C2 may be zero, in which
     127                 :            :    case the offset will be MULT_EXPR (T2, C3).
     128                 :            : 
     129                 :            :    When this pattern is recognized, the original memory reference
     130                 :            :    can be replaced with:
     131                 :            : 
     132                 :            :      MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
     133                 :            :               C1 + (C2 * C3) + C4)
     134                 :            : 
     135                 :            :    which distributes the multiply to allow constant folding.  When
     136                 :            :    two or more addressing expressions can be represented by MEM_REFs
     137                 :            :    of this form, differing only in the constants C1, C2, and C4,
     138                 :            :    making this substitution produces more efficient addressing during
     139                 :            :    the RTL phases.  When there are not at least two expressions with
     140                 :            :    the same values of T1, T2, and C3, there is nothing to be gained
     141                 :            :    by the replacement.
     142                 :            : 
     143                 :            :    Strength reduction of CAND_REFs uses the same infrastructure as
     144                 :            :    that used by CAND_MULTs and CAND_ADDs.  We record T1 in the base (B)
     145                 :            :    field, MULT_EXPR (T2, C3) in the stride (S) field, and 
     146                 :            :    C1 + (C2 * C3) + C4 in the index (i) field.  A basis for a CAND_REF
     147                 :            :    is thus another CAND_REF with the same B and S values.  When at 
     148                 :            :    least two CAND_REFs are chained together using the basis relation,
     149                 :            :    each of them is replaced as above, resulting in improved code
     150                 :            :    generation for addressing.
     151                 :            : 
     152                 :            :    Conditional candidates
     153                 :            :    ======================
     154                 :            : 
     155                 :            :    Conditional candidates are best illustrated with an example.
     156                 :            :    Consider the code sequence:
     157                 :            : 
     158                 :            :    (1)  x_0 = ...;
     159                 :            :    (2)  a_0 = x_0 * 5;          MULT (B: x_0; i: 0; S: 5)
     160                 :            :         if (...)
     161                 :            :    (3)    x_1 = x_0 + 1;        ADD  (B: x_0, i: 1; S: 1)
     162                 :            :    (4)  x_2 = PHI <x_0, x_1>;   PHI  (B: x_0, i: 0, S: 1)
     163                 :            :    (5)  x_3 = x_2 + 1;          ADD  (B: x_2, i: 1, S: 1)
     164                 :            :    (6)  a_1 = x_3 * 5;          MULT (B: x_2, i: 1; S: 5)
     165                 :            : 
     166                 :            :    Here strength reduction is complicated by the uncertain value of x_2.
     167                 :            :    A legitimate transformation is:
     168                 :            : 
     169                 :            :    (1)  x_0 = ...;
     170                 :            :    (2)  a_0 = x_0 * 5;
     171                 :            :         if (...)
     172                 :            :           {
     173                 :            :    (3)      [x_1 = x_0 + 1;]
     174                 :            :    (3a)     t_1 = a_0 + 5;
     175                 :            :           }
     176                 :            :    (4)  [x_2 = PHI <x_0, x_1>;]
     177                 :            :    (4a) t_2 = PHI <a_0, t_1>;
     178                 :            :    (5)  [x_3 = x_2 + 1;]
     179                 :            :    (6r) a_1 = t_2 + 5;
     180                 :            : 
     181                 :            :    where the bracketed instructions may go dead.
     182                 :            : 
     183                 :            :    To recognize this opportunity, we have to observe that statement (6)
     184                 :            :    has a "hidden basis" (2).  The hidden basis is unlike a normal basis
     185                 :            :    in that the statement and the hidden basis have different base SSA
     186                 :            :    names (x_2 and x_0, respectively).  The relationship is established
     187                 :            :    when a statement's base name (x_2) is defined by a phi statement (4),
     188                 :            :    each argument of which (x_0, x_1) has an identical "derived base name."
     189                 :            :    If the argument is defined by a candidate (as x_1 is by (3)) that is a
     190                 :            :    CAND_ADD having a stride of 1, the derived base name of the argument is
     191                 :            :    the base name of the candidate (x_0).  Otherwise, the argument itself
     192                 :            :    is its derived base name (as is the case with argument x_0).
     193                 :            : 
     194                 :            :    The hidden basis for statement (6) is the nearest dominating candidate
     195                 :            :    whose base name is the derived base name (x_0) of the feeding phi (4), 
     196                 :            :    and whose stride is identical to that of the statement.  We can then
     197                 :            :    create the new "phi basis" (4a) and feeding adds along incoming arcs (3a),
     198                 :            :    allowing the final replacement of (6) by the strength-reduced (6r).
     199                 :            : 
     200                 :            :    To facilitate this, a new kind of candidate (CAND_PHI) is introduced.
     201                 :            :    A CAND_PHI is not a candidate for replacement, but is maintained in the
     202                 :            :    candidate table to ease discovery of hidden bases.  Any phi statement
     203                 :            :    whose arguments share a common derived base name is entered into the
     204                 :            :    table with the derived base name, an (arbitrary) index of zero, and a
     205                 :            :    stride of 1.  A statement with a hidden basis can then be detected by
     206                 :            :    simply looking up its feeding phi definition in the candidate table,
     207                 :            :    extracting the derived base name, and searching for a basis in the
     208                 :            :    usual manner after substituting the derived base name.
     209                 :            : 
     210                 :            :    Note that the transformation is only valid when the original phi and 
     211                 :            :    the statements that define the phi's arguments are all at the same
     212                 :            :    position in the loop hierarchy.  */
     213                 :            : 
     214                 :            : 
     215                 :            : /* Index into the candidate vector, offset by 1.  VECs are zero-based,
     216                 :            :    while cand_idx's are one-based, with zero indicating null.  */
     217                 :            : typedef unsigned cand_idx;
     218                 :            : 
     219                 :            : /* The kind of candidate.  */
     220                 :            : enum cand_kind
     221                 :            : {
     222                 :            :   CAND_MULT,
     223                 :            :   CAND_ADD,
     224                 :            :   CAND_REF,
     225                 :            :   CAND_PHI
     226                 :            : };
     227                 :            : 
     228                 :            : class slsr_cand_d
     229                 :            : {
     230                 :            : public:
     231                 :            :   /* The candidate statement S1.  */
     232                 :            :   gimple *cand_stmt;
     233                 :            : 
     234                 :            :   /* The base expression B:  often an SSA name, but not always.  */
     235                 :            :   tree base_expr;
     236                 :            : 
     237                 :            :   /* The stride S.  */
     238                 :            :   tree stride;
     239                 :            : 
     240                 :            :   /* The index constant i.  */
     241                 :            :   widest_int index;
     242                 :            : 
     243                 :            :   /* The type of the candidate.  This is normally the type of base_expr,
     244                 :            :      but casts may have occurred when combining feeding instructions.
     245                 :            :      A candidate can only be a basis for candidates of the same final type.
     246                 :            :      (For CAND_REFs, this is the type to be used for operand 1 of the
     247                 :            :      replacement MEM_REF.)  */
     248                 :            :   tree cand_type;
     249                 :            : 
     250                 :            :   /* The type to be used to interpret the stride field when the stride
     251                 :            :      is not a constant.  Normally the same as the type of the recorded
     252                 :            :      stride, but when the stride has been cast we need to maintain that
     253                 :            :      knowledge in order to make legal substitutions without losing 
     254                 :            :      precision.  When the stride is a constant, this will be sizetype.  */
     255                 :            :   tree stride_type;
     256                 :            : 
     257                 :            :   /* The kind of candidate (CAND_MULT, etc.).  */
     258                 :            :   enum cand_kind kind;
     259                 :            : 
     260                 :            :   /* Index of this candidate in the candidate vector.  */
     261                 :            :   cand_idx cand_num;
     262                 :            : 
     263                 :            :   /* Index of the next candidate record for the same statement.
     264                 :            :      A statement may be useful in more than one way (e.g., due to
     265                 :            :      commutativity).  So we can have multiple "interpretations"
     266                 :            :      of a statement.  */
     267                 :            :   cand_idx next_interp;
     268                 :            : 
     269                 :            :   /* Index of the first candidate record in a chain for the same
     270                 :            :      statement.  */
     271                 :            :   cand_idx first_interp;
     272                 :            : 
     273                 :            :   /* Index of the basis statement S0, if any, in the candidate vector.  */
     274                 :            :   cand_idx basis;
     275                 :            : 
     276                 :            :   /* First candidate for which this candidate is a basis, if one exists.  */
     277                 :            :   cand_idx dependent;
     278                 :            : 
     279                 :            :   /* Next candidate having the same basis as this one.  */
     280                 :            :   cand_idx sibling;
     281                 :            : 
     282                 :            :   /* If this is a conditional candidate, the CAND_PHI candidate
     283                 :            :      that defines the base SSA name B.  */
     284                 :            :   cand_idx def_phi;
     285                 :            : 
     286                 :            :   /* Savings that can be expected from eliminating dead code if this
     287                 :            :      candidate is replaced.  */
     288                 :            :   int dead_savings;
     289                 :            : 
     290                 :            :   /* For PHI candidates, use a visited flag to keep from processing the
     291                 :            :      same PHI twice from multiple paths.  */
     292                 :            :   int visited;
     293                 :            : 
     294                 :            :   /* We sometimes have to cache a phi basis with a phi candidate to
     295                 :            :      avoid processing it twice.  Valid only if visited==1.  */
     296                 :            :   tree cached_basis;
     297                 :            : };
     298                 :            : 
     299                 :            : typedef class slsr_cand_d slsr_cand, *slsr_cand_t;
     300                 :            : typedef const class slsr_cand_d *const_slsr_cand_t;
     301                 :            : 
     302                 :            : /* Pointers to candidates are chained together as part of a mapping
     303                 :            :    from base expressions to the candidates that use them.  */
     304                 :            : 
     305                 :            : struct cand_chain_d
     306                 :            : {
     307                 :            :   /* Base expression for the chain of candidates:  often, but not
     308                 :            :      always, an SSA name.  */
     309                 :            :   tree base_expr;
     310                 :            : 
     311                 :            :   /* Pointer to a candidate.  */
     312                 :            :   slsr_cand_t cand;
     313                 :            : 
     314                 :            :   /* Chain pointer.  */
     315                 :            :   struct cand_chain_d *next;
     316                 :            : 
     317                 :            : };
     318                 :            : 
     319                 :            : typedef struct cand_chain_d cand_chain, *cand_chain_t;
     320                 :            : typedef const struct cand_chain_d *const_cand_chain_t;
     321                 :            : 
     322                 :            : /* Information about a unique "increment" associated with candidates
     323                 :            :    having an SSA name for a stride.  An increment is the difference
     324                 :            :    between the index of the candidate and the index of its basis,
     325                 :            :    i.e., (i - i') as discussed in the module commentary.
     326                 :            : 
     327                 :            :    When we are not going to generate address arithmetic we treat
     328                 :            :    increments that differ only in sign as the same, allowing sharing
     329                 :            :    of the cost of initializers.  The absolute value of the increment
     330                 :            :    is stored in the incr_info.  */
     331                 :            : 
     332                 :            : class incr_info_d
     333                 :            : {
     334                 :            : public:
     335                 :            :   /* The increment that relates a candidate to its basis.  */
     336                 :            :   widest_int incr;
     337                 :            : 
     338                 :            :   /* How many times the increment occurs in the candidate tree.  */
     339                 :            :   unsigned count;
     340                 :            : 
     341                 :            :   /* Cost of replacing candidates using this increment.  Negative and
     342                 :            :      zero costs indicate replacement should be performed.  */
     343                 :            :   int cost;
     344                 :            : 
     345                 :            :   /* If this increment is profitable but is not -1, 0, or 1, it requires
     346                 :            :      an initializer T_0 = stride * incr to be found or introduced in the
     347                 :            :      nearest common dominator of all candidates.  This field holds T_0
     348                 :            :      for subsequent use.  */
     349                 :            :   tree initializer;
     350                 :            : 
     351                 :            :   /* If the initializer was found to already exist, this is the block
     352                 :            :      where it was found.  */
     353                 :            :   basic_block init_bb;
     354                 :            : };
     355                 :            : 
     356                 :            : typedef class incr_info_d incr_info, *incr_info_t;
     357                 :            : 
     358                 :            : /* Candidates are maintained in a vector.  If candidate X dominates
     359                 :            :    candidate Y, then X appears before Y in the vector; but the
     360                 :            :    converse does not necessarily hold.  */
     361                 :            : static vec<slsr_cand_t> cand_vec;
     362                 :            : 
     363                 :            : enum cost_consts
     364                 :            : {
     365                 :            :   COST_NEUTRAL = 0,
     366                 :            :   COST_INFINITE = 1000
     367                 :            : };
     368                 :            : 
     369                 :            : enum stride_status
     370                 :            : {
     371                 :            :   UNKNOWN_STRIDE = 0,
     372                 :            :   KNOWN_STRIDE = 1
     373                 :            : };
     374                 :            : 
     375                 :            : enum phi_adjust_status
     376                 :            : {
     377                 :            :   NOT_PHI_ADJUST = 0,
     378                 :            :   PHI_ADJUST = 1
     379                 :            : };
     380                 :            : 
     381                 :            : enum count_phis_status
     382                 :            : {
     383                 :            :   DONT_COUNT_PHIS = 0,
     384                 :            :   COUNT_PHIS = 1
     385                 :            : };
     386                 :            : 
     387                 :            : /* Constrain how many PHI nodes we will visit for a conditional
     388                 :            :    candidate (depth and breadth).  */
     389                 :            : const int MAX_SPREAD = 16;
     390                 :            : 
     391                 :            : /* Pointer map embodying a mapping from statements to candidates.  */
     392                 :            : static hash_map<gimple *, slsr_cand_t> *stmt_cand_map;
     393                 :            : 
     394                 :            : /* Obstack for candidates.  */
     395                 :            : static struct obstack cand_obstack;
     396                 :            : 
     397                 :            : /* Obstack for candidate chains.  */
     398                 :            : static struct obstack chain_obstack;
     399                 :            : 
     400                 :            : /* An array INCR_VEC of incr_infos is used during analysis of related
     401                 :            :    candidates having an SSA name for a stride.  INCR_VEC_LEN describes
     402                 :            :    its current length.  MAX_INCR_VEC_LEN is used to avoid costly
     403                 :            :    pathological cases. */
     404                 :            : static incr_info_t incr_vec;
     405                 :            : static unsigned incr_vec_len;
     406                 :            : const int MAX_INCR_VEC_LEN = 16;
     407                 :            : 
     408                 :            : /* For a chain of candidates with unknown stride, indicates whether or not
     409                 :            :    we must generate pointer arithmetic when replacing statements.  */
     410                 :            : static bool address_arithmetic_p;
     411                 :            : 
     412                 :            : /* Forward function declarations.  */
     413                 :            : static slsr_cand_t base_cand_from_table (tree);
     414                 :            : static tree introduce_cast_before_cand (slsr_cand_t, tree, tree);
     415                 :            : static bool legal_cast_p_1 (tree, tree);
     416                 :            : 
     417                 :            : /* Produce a pointer to the IDX'th candidate in the candidate vector.  */
     418                 :            : 
     419                 :            : static slsr_cand_t
     420                 :    5777330 : lookup_cand (cand_idx idx)
     421                 :            : {
     422                 :          0 :   return cand_vec[idx];
     423                 :            : }
     424                 :            : 
     425                 :            : /* Helper for hashing a candidate chain header.  */
     426                 :            : 
     427                 :            : struct cand_chain_hasher : nofree_ptr_hash <cand_chain>
     428                 :            : {
     429                 :            :   static inline hashval_t hash (const cand_chain *);
     430                 :            :   static inline bool equal (const cand_chain *, const cand_chain *);
     431                 :            : };
     432                 :            : 
     433                 :            : inline hashval_t
     434                 :   17882400 : cand_chain_hasher::hash (const cand_chain *p)
     435                 :            : {
     436                 :   17882400 :   tree base_expr = p->base_expr;
     437                 :   17882400 :   return iterative_hash_expr (base_expr, 0);
     438                 :            : }
     439                 :            : 
     440                 :            : inline bool
     441                 :   14348100 : cand_chain_hasher::equal (const cand_chain *chain1, const cand_chain *chain2)
     442                 :            : {
     443                 :   14348100 :   return operand_equal_p (chain1->base_expr, chain2->base_expr, 0);
     444                 :            : }
     445                 :            : 
     446                 :            : /* Hash table embodying a mapping from base exprs to chains of candidates.  */
     447                 :            : static hash_table<cand_chain_hasher> *base_cand_map;
     448                 :            : 
     449                 :            : /* Pointer map used by tree_to_aff_combination_expand.  */
     450                 :            : static hash_map<tree, name_expansion *> *name_expansions;
     451                 :            : /* Pointer map embodying a mapping from bases to alternative bases.  */
     452                 :            : static hash_map<tree, tree> *alt_base_map;
     453                 :            : 
     454                 :            : /* Given BASE, use the tree affine combiniation facilities to
     455                 :            :    find the underlying tree expression for BASE, with any
     456                 :            :    immediate offset excluded.
     457                 :            : 
     458                 :            :    N.B. we should eliminate this backtracking with better forward
     459                 :            :    analysis in a future release.  */
     460                 :            : 
     461                 :            : static tree
     462                 :      78171 : get_alternative_base (tree base)
     463                 :            : {
     464                 :      78171 :   tree *result = alt_base_map->get (base);
     465                 :            : 
     466                 :      67586 :   if (result == NULL)
     467                 :            :     {
     468                 :      10585 :       tree expr;
     469                 :      10585 :       aff_tree aff;
     470                 :            : 
     471                 :      10585 :       tree_to_aff_combination_expand (base, TREE_TYPE (base),
     472                 :            :                                       &aff, &name_expansions);
     473                 :      10585 :       aff.offset = 0;
     474                 :      10585 :       expr = aff_combination_to_tree (&aff);
     475                 :            : 
     476                 :      21069 :       gcc_assert (!alt_base_map->put (base, base == expr ? NULL : expr));
     477                 :            : 
     478                 :      10585 :       return expr == base ? NULL : expr;
     479                 :            :     }
     480                 :            : 
     481                 :      67586 :   return *result;
     482                 :            : }
     483                 :            : 
     484                 :            : /* Look in the candidate table for a CAND_PHI that defines BASE and
     485                 :            :    return it if found; otherwise return NULL.  */
     486                 :            : 
     487                 :            : static cand_idx
     488                 :    1658960 : find_phi_def (tree base)
     489                 :            : {
     490                 :    1658960 :   slsr_cand_t c;
     491                 :            : 
     492                 :    1658960 :   if (TREE_CODE (base) != SSA_NAME)
     493                 :            :     return 0;
     494                 :            : 
     495                 :    1658960 :   c = base_cand_from_table (base);
     496                 :            : 
     497                 :     123369 :   if (!c || c->kind != CAND_PHI
     498                 :    1665950 :       || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (c->cand_stmt)))
     499                 :            :     return 0;
     500                 :            : 
     501                 :       6990 :   return c->cand_num;
     502                 :            : }
     503                 :            : 
     504                 :            : /* Determine whether all uses of NAME are directly or indirectly
     505                 :            :    used by STMT.  That is, we want to know whether if STMT goes
     506                 :            :    dead, the definition of NAME also goes dead.  */
     507                 :            : static bool
     508                 :     262123 : uses_consumed_by_stmt (tree name, gimple *stmt, unsigned recurse = 0)
     509                 :            : {
     510                 :     262123 :   gimple *use_stmt;
     511                 :     262123 :   imm_use_iterator iter;
     512                 :     262123 :   bool retval = true;
     513                 :            : 
     514                 :     483087 :   FOR_EACH_IMM_USE_STMT (use_stmt, iter, name)
     515                 :            :     {
     516                 :     344169 :       if (use_stmt == stmt || is_gimple_debug (use_stmt))
     517                 :     217837 :         continue;
     518                 :            : 
     519                 :     126332 :       if (!is_gimple_assign (use_stmt)
     520                 :      42833 :           || !gimple_get_lhs (use_stmt)
     521                 :      42833 :           || !is_gimple_reg (gimple_get_lhs (use_stmt))
     522                 :      35680 :           || recurse >= 10
     523                 :     161992 :           || !uses_consumed_by_stmt (gimple_get_lhs (use_stmt), stmt,
     524                 :            :                                      recurse + 1))
     525                 :            :         {
     526                 :     123205 :           retval = false;
     527                 :     344169 :           BREAK_FROM_IMM_USE_STMT (iter);
     528                 :            :         }
     529                 :            :     }
     530                 :            : 
     531                 :     262123 :   return retval;
     532                 :            : }
     533                 :            : 
     534                 :            : /* Helper routine for find_basis_for_candidate.  May be called twice:
     535                 :            :    once for the candidate's base expr, and optionally again either for
     536                 :            :    the candidate's phi definition or for a CAND_REF's alternative base
     537                 :            :    expression.  */
     538                 :            : 
     539                 :            : static slsr_cand_t
     540                 :    5217510 : find_basis_for_base_expr (slsr_cand_t c, tree base_expr)
     541                 :            : {
     542                 :    5217510 :   cand_chain mapping_key;
     543                 :    5217510 :   cand_chain_t chain;
     544                 :    5217510 :   slsr_cand_t basis = NULL;
     545                 :            : 
     546                 :            :   // Limit potential of N^2 behavior for long candidate chains.
     547                 :    5217510 :   int iters = 0;
     548                 :    5217510 :   int max_iters = param_max_slsr_candidate_scan;
     549                 :            : 
     550                 :    5217510 :   mapping_key.base_expr = base_expr;
     551                 :    5217510 :   chain = base_cand_map->find (&mapping_key);
     552                 :            : 
     553                 :   23863300 :   for (; chain && iters < max_iters; chain = chain->next, ++iters)
     554                 :            :     {
     555                 :   18645800 :       slsr_cand_t one_basis = chain->cand;
     556                 :            : 
     557                 :   33535300 :       if (one_basis->kind != c->kind
     558                 :   11068900 :           || one_basis->cand_stmt == c->cand_stmt
     559                 :   11068600 :           || !operand_equal_p (one_basis->stride, c->stride, 0)
     560                 :    5947950 :           || !types_compatible_p (one_basis->cand_type, c->cand_type)
     561                 :    4916700 :           || !types_compatible_p (one_basis->stride_type, c->stride_type)
     562                 :   23562500 :           || !dominated_by_p (CDI_DOMINATORS,
     563                 :    4916700 :                               gimple_bb (c->cand_stmt),
     564                 :    4916700 :                               gimple_bb (one_basis->cand_stmt)))
     565                 :   14889500 :         continue;
     566                 :            : 
     567                 :    3756340 :       tree lhs = gimple_assign_lhs (one_basis->cand_stmt);
     568                 :    3756340 :       if (lhs && TREE_CODE (lhs) == SSA_NAME
     569                 :    7490880 :           && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
     570                 :         27 :         continue;
     571                 :            : 
     572                 :    3756310 :       if (!basis || basis->cand_num < one_basis->cand_num)
     573                 :    1229520 :         basis = one_basis;
     574                 :            :     }
     575                 :            : 
     576                 :    5217510 :   return basis;
     577                 :            : }
     578                 :            : 
     579                 :            : /* Use the base expr from candidate C to look for possible candidates
     580                 :            :    that can serve as a basis for C.  Each potential basis must also
     581                 :            :    appear in a block that dominates the candidate statement and have
     582                 :            :    the same stride and type.  If more than one possible basis exists,
     583                 :            :    the one with highest index in the vector is chosen; this will be
     584                 :            :    the most immediately dominating basis.  */
     585                 :            : 
     586                 :            : static int
     587                 :    5210530 : find_basis_for_candidate (slsr_cand_t c)
     588                 :            : {
     589                 :    5210530 :   slsr_cand_t basis = find_basis_for_base_expr (c, c->base_expr);
     590                 :            : 
     591                 :            :   /* If a candidate doesn't have a basis using its base expression,
     592                 :            :      it may have a basis hidden by one or more intervening phis.  */
     593                 :    5210530 :   if (!basis && c->def_phi)
     594                 :            :     {
     595                 :       6862 :       basic_block basis_bb, phi_bb;
     596                 :       6862 :       slsr_cand_t phi_cand = lookup_cand (c->def_phi);
     597                 :       6862 :       basis = find_basis_for_base_expr (c, phi_cand->base_expr);
     598                 :            : 
     599                 :       6862 :       if (basis)
     600                 :            :         {
     601                 :            :           /* A hidden basis must dominate the phi-definition of the
     602                 :            :              candidate's base name.  */
     603                 :       5871 :           phi_bb = gimple_bb (phi_cand->cand_stmt);
     604                 :       5871 :           basis_bb = gimple_bb (basis->cand_stmt);
     605                 :            : 
     606                 :       5871 :           if (phi_bb == basis_bb
     607                 :       5871 :               || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb))
     608                 :            :             {
     609                 :          6 :               basis = NULL;
     610                 :          6 :               c->basis = 0;
     611                 :            :             }
     612                 :            : 
     613                 :            :           /* If we found a hidden basis, estimate additional dead-code
     614                 :            :              savings if the phi and its feeding statements can be removed.  */
     615                 :       5871 :           tree feeding_var = gimple_phi_result (phi_cand->cand_stmt);
     616                 :       5871 :           if (basis && uses_consumed_by_stmt (feeding_var, c->cand_stmt))
     617                 :       1214 :             c->dead_savings += phi_cand->dead_savings;
     618                 :            :         }
     619                 :            :     }
     620                 :            : 
     621                 :    5210530 :   if (flag_expensive_optimizations && !basis && c->kind == CAND_REF)
     622                 :            :     {
     623                 :      31371 :       tree alt_base_expr = get_alternative_base (c->base_expr);
     624                 :      31371 :       if (alt_base_expr)
     625                 :        113 :         basis = find_basis_for_base_expr (c, alt_base_expr);
     626                 :            :     }
     627                 :            : 
     628                 :    5210530 :   if (basis)
     629                 :            :     {
     630                 :     970452 :       c->sibling = basis->dependent;
     631                 :     970452 :       basis->dependent = c->cand_num;
     632                 :     970452 :       return basis->cand_num;
     633                 :            :     }
     634                 :            : 
     635                 :            :   return 0;
     636                 :            : }
     637                 :            : 
     638                 :            : /* Record a mapping from BASE to C, indicating that C may potentially serve
     639                 :            :    as a basis using that base expression.  BASE may be the same as
     640                 :            :    C->BASE_EXPR; alternatively BASE can be a different tree that share the
     641                 :            :    underlining expression of C->BASE_EXPR.  */
     642                 :            : 
     643                 :            : static void
     644                 :    5238250 : record_potential_basis (slsr_cand_t c, tree base)
     645                 :            : {
     646                 :    5238250 :   cand_chain_t node;
     647                 :    5238250 :   cand_chain **slot;
     648                 :            : 
     649                 :    5238250 :   gcc_assert (base);
     650                 :            : 
     651                 :    5238250 :   node = (cand_chain_t) obstack_alloc (&chain_obstack, sizeof (cand_chain));
     652                 :    5238250 :   node->base_expr = base;
     653                 :    5238250 :   node->cand = c;
     654                 :    5238250 :   node->next = NULL;
     655                 :    5238250 :   slot = base_cand_map->find_slot (node, INSERT);
     656                 :            : 
     657                 :    5238250 :   if (*slot)
     658                 :            :     {
     659                 :    2770850 :       cand_chain_t head = (cand_chain_t) (*slot);
     660                 :    2770850 :       node->next = head->next;
     661                 :    2770850 :       head->next = node;
     662                 :            :     }
     663                 :            :   else
     664                 :    2467400 :     *slot = node;
     665                 :    5238250 : }
     666                 :            : 
     667                 :            : /* Allocate storage for a new candidate and initialize its fields.
     668                 :            :    Attempt to find a basis for the candidate.
     669                 :            : 
     670                 :            :    For CAND_REF, an alternative base may also be recorded and used
     671                 :            :    to find a basis.  This helps cases where the expression hidden
     672                 :            :    behind BASE (which is usually an SSA_NAME) has immediate offset,
     673                 :            :    e.g.
     674                 :            : 
     675                 :            :      a2[i][j] = 1;
     676                 :            :      a2[i + 20][j] = 2;  */
     677                 :            : 
     678                 :            : static slsr_cand_t
     679                 :    5238040 : alloc_cand_and_find_basis (enum cand_kind kind, gimple *gs, tree base,
     680                 :            :                            const widest_int &index, tree stride, tree ctype,
     681                 :            :                            tree stype, unsigned savings)
     682                 :            : {
     683                 :    5238040 :   slsr_cand_t c = (slsr_cand_t) obstack_alloc (&cand_obstack,
     684                 :            :                                                sizeof (slsr_cand));
     685                 :    5238040 :   c->cand_stmt = gs;
     686                 :    5238040 :   c->base_expr = base;
     687                 :    5238040 :   c->stride = stride;
     688                 :    5238040 :   c->index = index;
     689                 :    5238040 :   c->cand_type = ctype;
     690                 :    5238040 :   c->stride_type = stype;
     691                 :    5238040 :   c->kind = kind;
     692                 :    5238040 :   c->cand_num = cand_vec.length ();
     693                 :    5238040 :   c->next_interp = 0;
     694                 :    5238040 :   c->first_interp = c->cand_num;
     695                 :    5238040 :   c->dependent = 0;
     696                 :    5238040 :   c->sibling = 0;
     697                 :    5238040 :   c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0;
     698                 :    5238040 :   c->dead_savings = savings;
     699                 :    5238040 :   c->visited = 0;
     700                 :    5238040 :   c->cached_basis = NULL_TREE;
     701                 :            : 
     702                 :    5238040 :   cand_vec.safe_push (c);
     703                 :            : 
     704                 :    5238040 :   if (kind == CAND_PHI)
     705                 :      27512 :     c->basis = 0;
     706                 :            :   else
     707                 :    5210530 :     c->basis = find_basis_for_candidate (c);
     708                 :            : 
     709                 :    5238040 :   record_potential_basis (c, base);
     710                 :    5238040 :   if (flag_expensive_optimizations && kind == CAND_REF)
     711                 :            :     {
     712                 :      46800 :       tree alt_base = get_alternative_base (base);
     713                 :      46800 :       if (alt_base)
     714                 :        204 :         record_potential_basis (c, alt_base);
     715                 :            :     }
     716                 :            : 
     717                 :    5238040 :   return c;
     718                 :            : }
     719                 :            : 
     720                 :            : /* Determine the target cost of statement GS when compiling according
     721                 :            :    to SPEED.  */
     722                 :            : 
     723                 :            : static int
     724                 :    1019000 : stmt_cost (gimple *gs, bool speed)
     725                 :            : {
     726                 :    1019000 :   tree lhs, rhs1, rhs2;
     727                 :    1019000 :   machine_mode lhs_mode;
     728                 :            : 
     729                 :    1019000 :   gcc_assert (is_gimple_assign (gs));
     730                 :    1019000 :   lhs = gimple_assign_lhs (gs);
     731                 :    1019000 :   rhs1 = gimple_assign_rhs1 (gs);
     732                 :    1019000 :   lhs_mode = TYPE_MODE (TREE_TYPE (lhs));
     733                 :            :   
     734                 :    1019000 :   switch (gimple_assign_rhs_code (gs))
     735                 :            :     {
     736                 :     251906 :     case MULT_EXPR:
     737                 :     251906 :       rhs2 = gimple_assign_rhs2 (gs);
     738                 :            : 
     739                 :     251906 :       if (tree_fits_shwi_p (rhs2))
     740                 :     206879 :         return mult_by_coeff_cost (tree_to_shwi (rhs2), lhs_mode, speed);
     741                 :            : 
     742                 :      45027 :       gcc_assert (TREE_CODE (rhs1) != INTEGER_CST);
     743                 :      45027 :       return mul_cost (speed, lhs_mode);
     744                 :            : 
     745                 :     247211 :     case PLUS_EXPR:
     746                 :     247211 :     case POINTER_PLUS_EXPR:
     747                 :     247211 :     case MINUS_EXPR:
     748                 :     247211 :       return add_cost (speed, lhs_mode);
     749                 :            : 
     750                 :       8298 :     case NEGATE_EXPR:
     751                 :       8298 :       return neg_cost (speed, lhs_mode);
     752                 :            : 
     753                 :     462260 :     CASE_CONVERT:
     754                 :     924520 :       return convert_cost (lhs_mode, TYPE_MODE (TREE_TYPE (rhs1)), speed);
     755                 :            : 
     756                 :            :     /* Note that we don't assign costs to copies that in most cases
     757                 :            :        will go away.  */
     758                 :            :     case SSA_NAME:
     759                 :            :       return 0;
     760                 :            :       
     761                 :          0 :     default:
     762                 :          0 :       ;
     763                 :            :     }
     764                 :            :   
     765                 :          0 :   gcc_unreachable ();
     766                 :            :   return 0;
     767                 :            : }
     768                 :            : 
     769                 :            : /* Look up the defining statement for BASE_IN and return a pointer
     770                 :            :    to its candidate in the candidate table, if any; otherwise NULL.
     771                 :            :    Only CAND_ADD and CAND_MULT candidates are returned.  */
     772                 :            : 
     773                 :            : static slsr_cand_t
     774                 :    9878540 : base_cand_from_table (tree base_in)
     775                 :            : {
     776                 :    9878540 :   slsr_cand_t *result;
     777                 :            : 
     778                 :    9878540 :   gimple *def = SSA_NAME_DEF_STMT (base_in);
     779                 :    9878540 :   if (!def)
     780                 :            :     return (slsr_cand_t) NULL;
     781                 :            : 
     782                 :    9878540 :   result = stmt_cand_map->get (def);
     783                 :            :   
     784                 :    2644450 :   if (result && (*result)->kind != CAND_REF)
     785                 :    2625980 :     return *result;
     786                 :            : 
     787                 :            :   return (slsr_cand_t) NULL;
     788                 :            : }
     789                 :            : 
     790                 :            : /* Add an entry to the statement-to-candidate mapping.  */
     791                 :            : 
     792                 :            : static void
     793                 :    3777380 : add_cand_for_stmt (gimple *gs, slsr_cand_t c)
     794                 :            : {
     795                 :    3777380 :   gcc_assert (!stmt_cand_map->put (gs, c));
     796                 :    3777380 : }
     797                 :            : 
     798                 :            : /* Given PHI which contains a phi statement, determine whether it
     799                 :            :    satisfies all the requirements of a phi candidate.  If so, create
     800                 :            :    a candidate.  Note that a CAND_PHI never has a basis itself, but
     801                 :            :    is used to help find a basis for subsequent candidates.  */
     802                 :            : 
     803                 :            : static void
     804                 :    3089360 : slsr_process_phi (gphi *phi, bool speed)
     805                 :            : {
     806                 :    3089360 :   unsigned i;
     807                 :    3089360 :   tree arg0_base = NULL_TREE, base_type;
     808                 :    3089360 :   slsr_cand_t c;
     809                 :    3089360 :   class loop *cand_loop = gimple_bb (phi)->loop_father;
     810                 :    3089360 :   unsigned savings = 0;
     811                 :            : 
     812                 :            :   /* A CAND_PHI requires each of its arguments to have the same
     813                 :            :      derived base name.  (See the module header commentary for a
     814                 :            :      definition of derived base names.)  Furthermore, all feeding
     815                 :            :      definitions must be in the same position in the loop hierarchy
     816                 :            :      as PHI.  */
     817                 :            : 
     818                 :    3251040 :   for (i = 0; i < gimple_phi_num_args (phi); i++)
     819                 :            :     {
     820                 :    3223530 :       slsr_cand_t arg_cand;
     821                 :    3223530 :       tree arg = gimple_phi_arg_def (phi, i);
     822                 :    3223530 :       tree derived_base_name = NULL_TREE;
     823                 :    3223530 :       gimple *arg_stmt = NULL;
     824                 :    3223530 :       basic_block arg_bb = NULL;
     825                 :            : 
     826                 :    3223530 :       if (TREE_CODE (arg) != SSA_NAME)
     827                 :            :         return;
     828                 :            : 
     829                 :    2846760 :       arg_cand = base_cand_from_table (arg);
     830                 :            : 
     831                 :    2846760 :       if (arg_cand)
     832                 :            :         {
     833                 :     371516 :           while (arg_cand->kind != CAND_ADD && arg_cand->kind != CAND_PHI)
     834                 :            :             {
     835                 :      32489 :               if (!arg_cand->next_interp)
     836                 :            :                 return;
     837                 :            : 
     838                 :       5215 :               arg_cand = lookup_cand (arg_cand->next_interp);
     839                 :            :             }
     840                 :            : 
     841                 :     339027 :           if (!integer_onep (arg_cand->stride))
     842                 :            :             return;
     843                 :            : 
     844                 :     220518 :           derived_base_name = arg_cand->base_expr;
     845                 :     220518 :           arg_stmt = arg_cand->cand_stmt;
     846                 :     220518 :           arg_bb = gimple_bb (arg_stmt);
     847                 :            : 
     848                 :            :           /* Gather potential dead code savings if the phi statement
     849                 :            :              can be removed later on.  */
     850                 :     220518 :           if (uses_consumed_by_stmt (arg, phi))
     851                 :            :             {
     852                 :     134549 :               if (gimple_code (arg_stmt) == GIMPLE_PHI)
     853                 :       1379 :                 savings += arg_cand->dead_savings;
     854                 :            :               else
     855                 :     133170 :                 savings += stmt_cost (arg_stmt, speed);
     856                 :            :             }
     857                 :            :         }
     858                 :    2480460 :       else if (SSA_NAME_IS_DEFAULT_DEF (arg))
     859                 :            :         {
     860                 :     111278 :           derived_base_name = arg;
     861                 :     111278 :           arg_bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
     862                 :            :         }
     863                 :            : 
     864                 :    2700970 :       if (!arg_bb || arg_bb->loop_father != cand_loop)
     865                 :            :         return;
     866                 :            : 
     867                 :     172145 :       if (i == 0)
     868                 :            :         arg0_base = derived_base_name;
     869                 :      28397 :       else if (!operand_equal_p (derived_base_name, arg0_base, 0))
     870                 :            :         return;
     871                 :            :     }
     872                 :            : 
     873                 :            :   /* Create the candidate.  "alloc_cand_and_find_basis" is named
     874                 :            :      misleadingly for this case, as no basis will be sought for a
     875                 :            :      CAND_PHI.  */
     876                 :      27512 :   base_type = TREE_TYPE (arg0_base);
     877                 :            : 
     878                 :      55024 :   c = alloc_cand_and_find_basis (CAND_PHI, phi, arg0_base,
     879                 :      27512 :                                  0, integer_one_node, base_type,
     880                 :            :                                  sizetype, savings);
     881                 :            : 
     882                 :            :   /* Add the candidate to the statement-candidate mapping.  */
     883                 :      27512 :   add_cand_for_stmt (phi, c);
     884                 :            : }
     885                 :            : 
     886                 :            : /* Given PBASE which is a pointer to tree, look up the defining
     887                 :            :    statement for it and check whether the candidate is in the
     888                 :            :    form of:
     889                 :            : 
     890                 :            :      X = B + (1 * S), S is integer constant
     891                 :            :      X = B + (i * S), S is integer one
     892                 :            : 
     893                 :            :    If so, set PBASE to the candidate's base_expr and return double
     894                 :            :    int (i * S).
     895                 :            :    Otherwise, just return double int zero.  */
     896                 :            : 
     897                 :            : static widest_int
     898                 :      55144 : backtrace_base_for_ref (tree *pbase)
     899                 :            : {
     900                 :      55144 :   tree base_in = *pbase;
     901                 :      55144 :   slsr_cand_t base_cand;
     902                 :            : 
     903                 :      55144 :   STRIP_NOPS (base_in);
     904                 :            : 
     905                 :            :   /* Strip off widening conversion(s) to handle cases where
     906                 :            :      e.g. 'B' is widened from an 'int' in order to calculate
     907                 :            :      a 64-bit address.  */
     908                 :      55144 :   if (CONVERT_EXPR_P (base_in)
     909                 :      57347 :       && legal_cast_p_1 (TREE_TYPE (base_in),
     910                 :       2203 :                          TREE_TYPE (TREE_OPERAND (base_in, 0))))
     911                 :       1388 :     base_in = get_unwidened (base_in, NULL_TREE);
     912                 :            : 
     913                 :      55144 :   if (TREE_CODE (base_in) != SSA_NAME)
     914                 :       1727 :     return 0;
     915                 :            : 
     916                 :      53417 :   base_cand = base_cand_from_table (base_in);
     917                 :            : 
     918                 :      76423 :   while (base_cand && base_cand->kind != CAND_PHI)
     919                 :            :     {
     920                 :      53744 :       if (base_cand->kind == CAND_ADD
     921                 :      51415 :           && base_cand->index == 1
     922                 :      76748 :           && TREE_CODE (base_cand->stride) == INTEGER_CST)
     923                 :            :         {
     924                 :            :           /* X = B + (1 * S), S is integer constant.  */
     925                 :       3198 :           *pbase = base_cand->base_expr;
     926                 :       3198 :           return wi::to_widest (base_cand->stride);
     927                 :            :         }
     928                 :      50546 :       else if (base_cand->kind == CAND_ADD
     929                 :      48217 :                && TREE_CODE (base_cand->stride) == INTEGER_CST
     930                 :      78086 :                && integer_onep (base_cand->stride))
     931                 :            :         {
     932                 :            :           /* X = B + (i * S), S is integer one.  */
     933                 :      27540 :           *pbase = base_cand->base_expr;
     934                 :      27540 :           return base_cand->index;
     935                 :            :         }
     936                 :            : 
     937                 :      23006 :       base_cand = lookup_cand (base_cand->next_interp);
     938                 :            :     }
     939                 :            : 
     940                 :      22679 :   return 0;
     941                 :            : }
     942                 :            : 
     943                 :            : /* Look for the following pattern:
     944                 :            : 
     945                 :            :     *PBASE:    MEM_REF (T1, C1)
     946                 :            : 
     947                 :            :     *POFFSET:  MULT_EXPR (T2, C3)        [C2 is zero]
     948                 :            :                      or
     949                 :            :                MULT_EXPR (PLUS_EXPR (T2, C2), C3)
     950                 :            :                      or
     951                 :            :                MULT_EXPR (MINUS_EXPR (T2, -C2), C3)
     952                 :            : 
     953                 :            :     *PINDEX:   C4 * BITS_PER_UNIT
     954                 :            : 
     955                 :            :    If not present, leave the input values unchanged and return FALSE.
     956                 :            :    Otherwise, modify the input values as follows and return TRUE:
     957                 :            : 
     958                 :            :     *PBASE:    T1
     959                 :            :     *POFFSET:  MULT_EXPR (T2, C3)
     960                 :            :     *PINDEX:   C1 + (C2 * C3) + C4
     961                 :            : 
     962                 :            :    When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it
     963                 :            :    will be further restructured to:
     964                 :            : 
     965                 :            :     *PBASE:    T1
     966                 :            :     *POFFSET:  MULT_EXPR (T2', C3)
     967                 :            :     *PINDEX:   C1 + (C2 * C3) + C4 + (C5 * C3)  */
     968                 :            : 
     969                 :            : static bool
     970                 :    4873890 : restructure_reference (tree *pbase, tree *poffset, widest_int *pindex,
     971                 :            :                        tree *ptype)
     972                 :            : {
     973                 :    4873890 :   tree base = *pbase, offset = *poffset;
     974                 :    4873890 :   widest_int index = *pindex;
     975                 :    4873890 :   tree mult_op0, t1, t2, type;
     976                 :    4873890 :   widest_int c1, c2, c3, c4, c5;
     977                 :    4873890 :   offset_int mem_offset;
     978                 :            : 
     979                 :    4873890 :   if (!base
     980                 :    4873890 :       || !offset
     981                 :     237998 :       || TREE_CODE (base) != MEM_REF
     982                 :      79225 :       || !mem_ref_offset (base).is_constant (&mem_offset)
     983                 :      79225 :       || TREE_CODE (offset) != MULT_EXPR
     984                 :      55633 :       || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST
     985                 :    4929520 :       || wi::umod_floor (index, BITS_PER_UNIT) != 0)
     986                 :    4818260 :     return false;
     987                 :            : 
     988                 :      55631 :   t1 = TREE_OPERAND (base, 0);
     989                 :      55631 :   c1 = widest_int::from (mem_offset, SIGNED);
     990                 :      55631 :   type = TREE_TYPE (TREE_OPERAND (base, 1));
     991                 :            : 
     992                 :      55631 :   mult_op0 = TREE_OPERAND (offset, 0);
     993                 :      55631 :   c3 = wi::to_widest (TREE_OPERAND (offset, 1));
     994                 :            : 
     995                 :      55631 :   if (TREE_CODE (mult_op0) == PLUS_EXPR)
     996                 :            : 
     997                 :       3751 :     if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST)
     998                 :            :       {
     999                 :       3264 :         t2 = TREE_OPERAND (mult_op0, 0);
    1000                 :       3264 :         c2 = wi::to_widest (TREE_OPERAND (mult_op0, 1));
    1001                 :            :       }
    1002                 :            :     else
    1003                 :            :       return false;
    1004                 :            : 
    1005                 :      51880 :   else if (TREE_CODE (mult_op0) == MINUS_EXPR)
    1006                 :            : 
    1007                 :          0 :     if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST)
    1008                 :            :       {
    1009                 :          0 :         t2 = TREE_OPERAND (mult_op0, 0);
    1010                 :          0 :         c2 = -wi::to_widest (TREE_OPERAND (mult_op0, 1));
    1011                 :            :       }
    1012                 :            :     else
    1013                 :            :       return false;
    1014                 :            : 
    1015                 :            :   else
    1016                 :            :     {
    1017                 :      51880 :       t2 = mult_op0;
    1018                 :      51880 :       c2 = 0;
    1019                 :            :     }
    1020                 :            : 
    1021                 :      55144 :   c4 = index >> LOG2_BITS_PER_UNIT;
    1022                 :      55144 :   c5 = backtrace_base_for_ref (&t2);
    1023                 :            : 
    1024                 :      55144 :   *pbase = t1;
    1025                 :      55144 :   *poffset = fold_build2 (MULT_EXPR, sizetype, fold_convert (sizetype, t2),
    1026                 :            :                           wide_int_to_tree (sizetype, c3));
    1027                 :      55144 :   *pindex = c1 + c2 * c3 + c4 + c5 * c3;
    1028                 :      55144 :   *ptype = type;
    1029                 :            : 
    1030                 :      55144 :   return true;
    1031                 :            : }
    1032                 :            : 
    1033                 :            : /* Given GS which contains a data reference, create a CAND_REF entry in
    1034                 :            :    the candidate table and attempt to find a basis.  */
    1035                 :            : 
    1036                 :            : static void
    1037                 :    9109090 : slsr_process_ref (gimple *gs)
    1038                 :            : {
    1039                 :    9109090 :   tree ref_expr, base, offset, type;
    1040                 :    9109090 :   poly_int64 bitsize, bitpos;
    1041                 :    9109090 :   machine_mode mode;
    1042                 :    9109090 :   int unsignedp, reversep, volatilep;
    1043                 :    9109090 :   slsr_cand_t c;
    1044                 :            : 
    1045                 :   18218200 :   if (gimple_vdef (gs))
    1046                 :    5677210 :     ref_expr = gimple_assign_lhs (gs);
    1047                 :            :   else
    1048                 :    3431880 :     ref_expr = gimple_assign_rhs1 (gs);
    1049                 :            : 
    1050                 :    9109090 :   if (!handled_component_p (ref_expr)
    1051                 :    4913620 :       || TREE_CODE (ref_expr) == BIT_FIELD_REF
    1052                 :    4898390 :       || (TREE_CODE (ref_expr) == COMPONENT_REF
    1053                 :    4232360 :           && DECL_BIT_FIELD (TREE_OPERAND (ref_expr, 1))))
    1054                 :    9053940 :     return;
    1055                 :            : 
    1056                 :    4874850 :   base = get_inner_reference (ref_expr, &bitsize, &bitpos, &offset, &mode,
    1057                 :            :                               &unsignedp, &reversep, &volatilep);
    1058                 :    4874850 :   HOST_WIDE_INT cbitpos;
    1059                 :    4874850 :   if (reversep || !bitpos.is_constant (&cbitpos))
    1060                 :            :     return;
    1061                 :    4873890 :   widest_int index = cbitpos;
    1062                 :            : 
    1063                 :    4873890 :   if (!restructure_reference (&base, &offset, &index, &type))
    1064                 :            :     return;
    1065                 :            : 
    1066                 :      55144 :   c = alloc_cand_and_find_basis (CAND_REF, gs, base, index, offset,
    1067                 :            :                                  type, sizetype, 0);
    1068                 :            : 
    1069                 :            :   /* Add the candidate to the statement-candidate mapping.  */
    1070                 :      55144 :   add_cand_for_stmt (gs, c);
    1071                 :            : }
    1072                 :            : 
    1073                 :            : /* Create a candidate entry for a statement GS, where GS multiplies
    1074                 :            :    two SSA names BASE_IN and STRIDE_IN.  Propagate any known information
    1075                 :            :    about the two SSA names into the new candidate.  Return the new
    1076                 :            :    candidate.  */
    1077                 :            : 
    1078                 :            : static slsr_cand_t
    1079                 :     189030 : create_mul_ssa_cand (gimple *gs, tree base_in, tree stride_in, bool speed)
    1080                 :            : {
    1081                 :     189030 :   tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
    1082                 :     189030 :   tree stype = NULL_TREE;
    1083                 :     189030 :   widest_int index;
    1084                 :     189030 :   unsigned savings = 0;
    1085                 :     189030 :   slsr_cand_t c;
    1086                 :     189030 :   slsr_cand_t base_cand = base_cand_from_table (base_in);
    1087                 :            : 
    1088                 :            :   /* Look at all interpretations of the base candidate, if necessary,
    1089                 :            :      to find information to propagate into this candidate.  */
    1090                 :     259908 :   while (base_cand && !base && base_cand->kind != CAND_PHI)
    1091                 :            :     {
    1092                 :            : 
    1093                 :      70878 :       if (base_cand->kind == CAND_MULT && integer_onep (base_cand->stride))
    1094                 :            :         {
    1095                 :            :           /* Y = (B + i') * 1
    1096                 :            :              X = Y * Z
    1097                 :            :              ================
    1098                 :            :              X = (B + i') * Z  */
    1099                 :         90 :           base = base_cand->base_expr;
    1100                 :         90 :           index = base_cand->index;
    1101                 :         90 :           stride = stride_in;
    1102                 :         90 :           ctype = base_cand->cand_type;
    1103                 :         90 :           stype = TREE_TYPE (stride_in);
    1104                 :         90 :           if (has_single_use (base_in))
    1105                 :        140 :             savings = (base_cand->dead_savings 
    1106                 :         70 :                        + stmt_cost (base_cand->cand_stmt, speed));
    1107                 :            :         }
    1108                 :      70788 :       else if (base_cand->kind == CAND_ADD
    1109                 :      61106 :                && TREE_CODE (base_cand->stride) == INTEGER_CST)
    1110                 :            :         {
    1111                 :            :           /* Y = B + (i' * S), S constant
    1112                 :            :              X = Y * Z
    1113                 :            :              ============================
    1114                 :            :              X = B + ((i' * S) * Z)  */
    1115                 :      45212 :           base = base_cand->base_expr;
    1116                 :      45212 :           index = base_cand->index * wi::to_widest (base_cand->stride);
    1117                 :      45212 :           stride = stride_in;
    1118                 :      45212 :           ctype = base_cand->cand_type;
    1119                 :      45212 :           stype = TREE_TYPE (stride_in);
    1120                 :      45212 :           if (has_single_use (base_in))
    1121                 :      49876 :             savings = (base_cand->dead_savings
    1122                 :      24938 :                        + stmt_cost (base_cand->cand_stmt, speed));
    1123                 :            :         }
    1124                 :            : 
    1125                 :      70878 :       base_cand = lookup_cand (base_cand->next_interp);
    1126                 :            :     }
    1127                 :            : 
    1128                 :     189030 :   if (!base)
    1129                 :            :     {
    1130                 :            :       /* No interpretations had anything useful to propagate, so
    1131                 :            :          produce X = (Y + 0) * Z.  */
    1132                 :     143728 :       base = base_in;
    1133                 :     143728 :       index = 0;
    1134                 :     143728 :       stride = stride_in;
    1135                 :     143728 :       ctype = TREE_TYPE (base_in);
    1136                 :     143728 :       stype = TREE_TYPE (stride_in);
    1137                 :            :     }
    1138                 :            : 
    1139                 :     189030 :   c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride,
    1140                 :            :                                  ctype, stype, savings);
    1141                 :     189030 :   return c;
    1142                 :            : }
    1143                 :            : 
    1144                 :            : /* Create a candidate entry for a statement GS, where GS multiplies
    1145                 :            :    SSA name BASE_IN by constant STRIDE_IN.  Propagate any known
    1146                 :            :    information about BASE_IN into the new candidate.  Return the new
    1147                 :            :    candidate.  */
    1148                 :            : 
    1149                 :            : static slsr_cand_t
    1150                 :     435021 : create_mul_imm_cand (gimple *gs, tree base_in, tree stride_in, bool speed)
    1151                 :            : {
    1152                 :     435021 :   tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
    1153                 :     435021 :   widest_int index, temp;
    1154                 :     435021 :   unsigned savings = 0;
    1155                 :     435021 :   slsr_cand_t c;
    1156                 :     435021 :   slsr_cand_t base_cand = base_cand_from_table (base_in);
    1157                 :            : 
    1158                 :            :   /* Look at all interpretations of the base candidate, if necessary,
    1159                 :            :      to find information to propagate into this candidate.  */
    1160                 :     737562 :   while (base_cand && !base && base_cand->kind != CAND_PHI)
    1161                 :            :     {
    1162                 :     302541 :       if (base_cand->kind == CAND_MULT
    1163                 :      32289 :           && TREE_CODE (base_cand->stride) == INTEGER_CST)
    1164                 :            :         {
    1165                 :            :           /* Y = (B + i') * S, S constant
    1166                 :            :              X = Y * c
    1167                 :            :              ============================
    1168                 :            :              X = (B + i') * (S * c)  */
    1169                 :      16901 :           temp = wi::to_widest (base_cand->stride) * wi::to_widest (stride_in);
    1170                 :      16901 :           if (wi::fits_to_tree_p (temp, TREE_TYPE (stride_in)))
    1171                 :            :             {
    1172                 :      16772 :               base = base_cand->base_expr;
    1173                 :      16772 :               index = base_cand->index;
    1174                 :      16772 :               stride = wide_int_to_tree (TREE_TYPE (stride_in), temp);
    1175                 :      16772 :               ctype = base_cand->cand_type;
    1176                 :      16772 :               if (has_single_use (base_in))
    1177                 :      16100 :                 savings = (base_cand->dead_savings 
    1178                 :       8050 :                            + stmt_cost (base_cand->cand_stmt, speed));
    1179                 :            :             }
    1180                 :            :         }
    1181                 :     285640 :       else if (base_cand->kind == CAND_ADD && integer_onep (base_cand->stride))
    1182                 :            :         {
    1183                 :            :           /* Y = B + (i' * 1)
    1184                 :            :              X = Y * c
    1185                 :            :              ===========================
    1186                 :            :              X = (B + i') * c  */
    1187                 :     196107 :           base = base_cand->base_expr;
    1188                 :     196107 :           index = base_cand->index;
    1189                 :     196107 :           stride = stride_in;
    1190                 :     196107 :           ctype = base_cand->cand_type;
    1191                 :     196107 :           if (has_single_use (base_in))
    1192                 :     315824 :             savings = (base_cand->dead_savings
    1193                 :     157912 :                        + stmt_cost (base_cand->cand_stmt, speed));
    1194                 :            :         }
    1195                 :      89533 :       else if (base_cand->kind == CAND_ADD
    1196                 :      74145 :                && base_cand->index == 1
    1197                 :     153017 :                && TREE_CODE (base_cand->stride) == INTEGER_CST)
    1198                 :            :         {
    1199                 :            :           /* Y = B + (1 * S), S constant
    1200                 :            :              X = Y * c
    1201                 :            :              ===========================
    1202                 :            :              X = (B + S) * c  */
    1203                 :          0 :           base = base_cand->base_expr;
    1204                 :          0 :           index = wi::to_widest (base_cand->stride);
    1205                 :          0 :           stride = stride_in;
    1206                 :          0 :           ctype = base_cand->cand_type;
    1207                 :          0 :           if (has_single_use (base_in))
    1208                 :          0 :             savings = (base_cand->dead_savings
    1209                 :          0 :                        + stmt_cost (base_cand->cand_stmt, speed));
    1210                 :            :         }
    1211                 :            : 
    1212                 :     302541 :       base_cand = lookup_cand (base_cand->next_interp);
    1213                 :            :     }
    1214                 :            : 
    1215                 :     435021 :   if (!base)
    1216                 :            :     {
    1217                 :            :       /* No interpretations had anything useful to propagate, so
    1218                 :            :          produce X = (Y + 0) * c.  */
    1219                 :     222142 :       base = base_in;
    1220                 :     222142 :       index = 0;
    1221                 :     222142 :       stride = stride_in;
    1222                 :     222142 :       ctype = TREE_TYPE (base_in);
    1223                 :            :     }
    1224                 :            : 
    1225                 :     435021 :   c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride,
    1226                 :            :                                  ctype, sizetype, savings);
    1227                 :     435021 :   return c;
    1228                 :            : }
    1229                 :            : 
    1230                 :            : /* Given GS which is a multiply of scalar integers, make an appropriate
    1231                 :            :    entry in the candidate table.  If this is a multiply of two SSA names,
    1232                 :            :    create two CAND_MULT interpretations and attempt to find a basis for
    1233                 :            :    each of them.  Otherwise, create a single CAND_MULT and attempt to
    1234                 :            :    find a basis.  */
    1235                 :            : 
    1236                 :            : static void
    1237                 :     470701 : slsr_process_mul (gimple *gs, tree rhs1, tree rhs2, bool speed)
    1238                 :            : {
    1239                 :     470701 :   slsr_cand_t c, c2;
    1240                 :            : 
    1241                 :            :   /* If this is a multiply of an SSA name with itself, it is highly
    1242                 :            :      unlikely that we will get a strength reduction opportunity, so
    1243                 :            :      don't record it as a candidate.  This simplifies the logic for
    1244                 :            :      finding a basis, so if this is removed that must be considered.  */
    1245                 :     470701 :   if (rhs1 == rhs2)
    1246                 :            :     return;
    1247                 :            : 
    1248                 :     467847 :   if (TREE_CODE (rhs2) == SSA_NAME)
    1249                 :            :     {
    1250                 :            :       /* Record an interpretation of this statement in the candidate table
    1251                 :            :          assuming RHS1 is the base expression and RHS2 is the stride.  */
    1252                 :      94515 :       c = create_mul_ssa_cand (gs, rhs1, rhs2, speed);
    1253                 :            : 
    1254                 :            :       /* Add the first interpretation to the statement-candidate mapping.  */
    1255                 :      94515 :       add_cand_for_stmt (gs, c);
    1256                 :            : 
    1257                 :            :       /* Record another interpretation of this statement assuming RHS1
    1258                 :            :          is the stride and RHS2 is the base expression.  */
    1259                 :      94515 :       c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed);
    1260                 :      94515 :       c->next_interp = c2->cand_num;
    1261                 :      94515 :       c2->first_interp = c->cand_num;
    1262                 :            :     }
    1263                 :     373332 :   else if (TREE_CODE (rhs2) == INTEGER_CST && !integer_zerop (rhs2))
    1264                 :            :     {
    1265                 :            :       /* Record an interpretation for the multiply-immediate.  */
    1266                 :     373332 :       c = create_mul_imm_cand (gs, rhs1, rhs2, speed);
    1267                 :            : 
    1268                 :            :       /* Add the interpretation to the statement-candidate mapping.  */
    1269                 :     373332 :       add_cand_for_stmt (gs, c);
    1270                 :            :     }
    1271                 :            : }
    1272                 :            : 
    1273                 :            : /* Create a candidate entry for a statement GS, where GS adds two
    1274                 :            :    SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
    1275                 :            :    subtracts ADDEND_IN from BASE_IN otherwise.  Propagate any known
    1276                 :            :    information about the two SSA names into the new candidate.
    1277                 :            :    Return the new candidate.  */
    1278                 :            : 
    1279                 :            : static slsr_cand_t
    1280                 :    1125490 : create_add_ssa_cand (gimple *gs, tree base_in, tree addend_in,
    1281                 :            :                      bool subtract_p, bool speed)
    1282                 :            : {
    1283                 :    1125490 :   tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
    1284                 :    1125490 :   tree stype = NULL_TREE;
    1285                 :    1125490 :   widest_int index;
    1286                 :    1125490 :   unsigned savings = 0;
    1287                 :    1125490 :   slsr_cand_t c;
    1288                 :    1125490 :   slsr_cand_t base_cand = base_cand_from_table (base_in);
    1289                 :    1125490 :   slsr_cand_t addend_cand = base_cand_from_table (addend_in);
    1290                 :            : 
    1291                 :            :   /* The most useful transformation is a multiply-immediate feeding
    1292                 :            :      an add or subtract.  Look for that first.  */
    1293                 :    2053250 :   while (addend_cand && !base && addend_cand->kind != CAND_PHI)
    1294                 :            :     {
    1295                 :     927757 :       if (addend_cand->kind == CAND_MULT
    1296                 :     511664 :           && addend_cand->index == 0
    1297                 :    1405990 :           && TREE_CODE (addend_cand->stride) == INTEGER_CST)
    1298                 :            :         {
    1299                 :            :           /* Z = (B + 0) * S, S constant
    1300                 :            :              X = Y +/- Z
    1301                 :            :              ===========================
    1302                 :            :              X = Y + ((+/-1 * S) * B)  */
    1303                 :     379499 :           base = base_in;
    1304                 :     379499 :           index = wi::to_widest (addend_cand->stride);
    1305                 :     379499 :           if (subtract_p)
    1306                 :      32155 :             index = -index;
    1307                 :     379499 :           stride = addend_cand->base_expr;
    1308                 :     379499 :           ctype = TREE_TYPE (base_in);
    1309                 :     379499 :           stype = addend_cand->cand_type;
    1310                 :     379499 :           if (has_single_use (addend_in))
    1311                 :     611530 :             savings = (addend_cand->dead_savings
    1312                 :     305765 :                        + stmt_cost (addend_cand->cand_stmt, speed));
    1313                 :            :         }
    1314                 :            : 
    1315                 :     927757 :       addend_cand = lookup_cand (addend_cand->next_interp);
    1316                 :            :     }
    1317                 :            : 
    1318                 :    1553010 :   while (base_cand && !base && base_cand->kind != CAND_PHI)
    1319                 :            :     {
    1320                 :     427519 :       if (base_cand->kind == CAND_ADD
    1321                 :     427519 :           && (base_cand->index == 0
    1322                 :     219633 :               || operand_equal_p (base_cand->stride,
    1323                 :     219633 :                                   integer_zero_node, 0)))
    1324                 :            :         {
    1325                 :            :           /* Y = B + (i' * S), i' * S = 0
    1326                 :            :              X = Y +/- Z
    1327                 :            :              ============================
    1328                 :            :              X = B + (+/-1 * Z)  */
    1329                 :      63688 :           base = base_cand->base_expr;
    1330                 :     120232 :           index = subtract_p ? -1 : 1;
    1331                 :      63688 :           stride = addend_in;
    1332                 :      63688 :           ctype = base_cand->cand_type;
    1333                 :      63688 :           stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype
    1334                 :      63688 :                    : TREE_TYPE (addend_in));
    1335                 :      63688 :           if (has_single_use (base_in))
    1336                 :      89754 :             savings = (base_cand->dead_savings
    1337                 :      44877 :                        + stmt_cost (base_cand->cand_stmt, speed));
    1338                 :            :         }
    1339                 :     363831 :       else if (subtract_p)
    1340                 :            :         {
    1341                 :      49593 :           slsr_cand_t subtrahend_cand = base_cand_from_table (addend_in);
    1342                 :            : 
    1343                 :      66717 :           while (subtrahend_cand && !base && subtrahend_cand->kind != CAND_PHI)
    1344                 :            :             {
    1345                 :      17124 :               if (subtrahend_cand->kind == CAND_MULT
    1346                 :       2553 :                   && subtrahend_cand->index == 0
    1347                 :      19543 :                   && TREE_CODE (subtrahend_cand->stride) == INTEGER_CST)
    1348                 :            :                 {
    1349                 :            :                   /* Z = (B + 0) * S, S constant
    1350                 :            :                      X = Y - Z
    1351                 :            :                      ===========================
    1352                 :            :                      Value:  X = Y + ((-1 * S) * B)  */
    1353                 :          0 :                   base = base_in;
    1354                 :          0 :                   index = wi::to_widest (subtrahend_cand->stride);
    1355                 :          0 :                   index = -index;
    1356                 :          0 :                   stride = subtrahend_cand->base_expr;
    1357                 :          0 :                   ctype = TREE_TYPE (base_in);
    1358                 :          0 :                   stype = subtrahend_cand->cand_type;
    1359                 :          0 :                   if (has_single_use (addend_in))
    1360                 :          0 :                     savings = (subtrahend_cand->dead_savings 
    1361                 :          0 :                                + stmt_cost (subtrahend_cand->cand_stmt, speed));
    1362                 :            :                 }
    1363                 :            : 
    1364                 :      17124 :               subtrahend_cand = lookup_cand (subtrahend_cand->next_interp);
    1365                 :            :             }
    1366                 :            :         }
    1367                 :            :       
    1368                 :     427519 :       base_cand = lookup_cand (base_cand->next_interp);
    1369                 :            :     }
    1370                 :            : 
    1371                 :    1125490 :   if (!base)
    1372                 :            :     {
    1373                 :            :       /* No interpretations had anything useful to propagate, so
    1374                 :            :          produce X = Y + (1 * Z).  */
    1375                 :     682303 :       base = base_in;
    1376                 :    1263330 :       index = subtract_p ? -1 : 1;
    1377                 :     682303 :       stride = addend_in;
    1378                 :     682303 :       ctype = TREE_TYPE (base_in);
    1379                 :     682303 :       stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype
    1380                 :     682303 :                : TREE_TYPE (addend_in));
    1381                 :            :     }
    1382                 :            : 
    1383                 :    1125490 :   c = alloc_cand_and_find_basis (CAND_ADD, gs, base, index, stride,
    1384                 :            :                                  ctype, stype, savings);
    1385                 :    1125490 :   return c;
    1386                 :            : }
    1387                 :            : 
    1388                 :            : /* Create a candidate entry for a statement GS, where GS adds SSA
    1389                 :            :    name BASE_IN to constant INDEX_IN.  Propagate any known information
    1390                 :            :    about BASE_IN into the new candidate.  Return the new candidate.  */
    1391                 :            : 
    1392                 :            : static slsr_cand_t
    1393                 :    1203910 : create_add_imm_cand (gimple *gs, tree base_in, const widest_int &index_in,
    1394                 :            :                      bool speed)
    1395                 :            : {
    1396                 :    1203910 :   enum cand_kind kind = CAND_ADD;
    1397                 :    1203910 :   tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
    1398                 :    1203910 :   tree stype = NULL_TREE;
    1399                 :    1203910 :   widest_int index, multiple;
    1400                 :    1203910 :   unsigned savings = 0;
    1401                 :    1203910 :   slsr_cand_t c;
    1402                 :    1203910 :   slsr_cand_t base_cand = base_cand_from_table (base_in);
    1403                 :            : 
    1404                 :    1579300 :   while (base_cand && !base && base_cand->kind != CAND_PHI)
    1405                 :            :     {
    1406                 :     375397 :       signop sign = TYPE_SIGN (TREE_TYPE (base_cand->stride));
    1407                 :            : 
    1408                 :     375397 :       if (TREE_CODE (base_cand->stride) == INTEGER_CST
    1409                 :     375397 :           && wi::multiple_of_p (index_in, wi::to_widest (base_cand->stride),
    1410                 :            :                                 sign, &multiple))
    1411                 :            :         {
    1412                 :            :           /* Y = (B + i') * S, S constant, c = kS for some integer k
    1413                 :            :              X = Y + c
    1414                 :            :              ============================
    1415                 :            :              X = (B + (i'+ k)) * S  
    1416                 :            :           OR
    1417                 :            :              Y = B + (i' * S), S constant, c = kS for some integer k
    1418                 :            :              X = Y + c
    1419                 :            :              ============================
    1420                 :            :              X = (B + (i'+ k)) * S  */
    1421                 :     249401 :           kind = base_cand->kind;
    1422                 :     249401 :           base = base_cand->base_expr;
    1423                 :     249401 :           index = base_cand->index + multiple;
    1424                 :     249401 :           stride = base_cand->stride;
    1425                 :     249401 :           ctype = base_cand->cand_type;
    1426                 :     249401 :           stype = base_cand->stride_type;
    1427                 :     249401 :           if (has_single_use (base_in))
    1428                 :     208062 :             savings = (base_cand->dead_savings 
    1429                 :     104031 :                        + stmt_cost (base_cand->cand_stmt, speed));
    1430                 :            :         }
    1431                 :            : 
    1432                 :     375397 :       base_cand = lookup_cand (base_cand->next_interp);
    1433                 :            :     }
    1434                 :            : 
    1435                 :    1203910 :   if (!base)
    1436                 :            :     {
    1437                 :            :       /* No interpretations had anything useful to propagate, so
    1438                 :            :          produce X = Y + (c * 1).  */
    1439                 :     954507 :       kind = CAND_ADD;
    1440                 :     954507 :       base = base_in;
    1441                 :     954507 :       index = index_in;
    1442                 :     954507 :       stride = integer_one_node;
    1443                 :     954507 :       ctype = TREE_TYPE (base_in);
    1444                 :     954507 :       stype = sizetype;
    1445                 :            :     }
    1446                 :            : 
    1447                 :    1203910 :   c = alloc_cand_and_find_basis (kind, gs, base, index, stride,
    1448                 :            :                                  ctype, stype, savings);
    1449                 :    1203910 :   return c;
    1450                 :            : }
    1451                 :            : 
    1452                 :            : /* Given GS which is an add or subtract of scalar integers or pointers,
    1453                 :            :    make at least one appropriate entry in the candidate table.  */
    1454                 :            : 
    1455                 :            : static void
    1456                 :    1977700 : slsr_process_add (gimple *gs, tree rhs1, tree rhs2, bool speed)
    1457                 :            : {
    1458                 :    1977700 :   bool subtract_p = gimple_assign_rhs_code (gs) == MINUS_EXPR;
    1459                 :    1977700 :   slsr_cand_t c = NULL, c2;
    1460                 :            : 
    1461                 :    1977700 :   if (TREE_CODE (rhs2) == SSA_NAME)
    1462                 :            :     {
    1463                 :            :       /* First record an interpretation assuming RHS1 is the base expression
    1464                 :            :          and RHS2 is the stride.  But it doesn't make sense for the
    1465                 :            :          stride to be a pointer, so don't record a candidate in that case.  */
    1466                 :     773796 :       if (!POINTER_TYPE_P (TREE_TYPE (rhs2)))
    1467                 :            :         {
    1468                 :     773796 :           c = create_add_ssa_cand (gs, rhs1, rhs2, subtract_p, speed);
    1469                 :            : 
    1470                 :            :           /* Add the first interpretation to the statement-candidate
    1471                 :            :              mapping.  */
    1472                 :     773796 :           add_cand_for_stmt (gs, c);
    1473                 :            :         }
    1474                 :            : 
    1475                 :            :       /* If the two RHS operands are identical, or this is a subtract,
    1476                 :            :          we're done.  */
    1477                 :     773796 :       if (operand_equal_p (rhs1, rhs2, 0) || subtract_p)
    1478                 :            :         return;
    1479                 :            : 
    1480                 :            :       /* Otherwise, record another interpretation assuming RHS2 is the
    1481                 :            :          base expression and RHS1 is the stride, again provided that the
    1482                 :            :          stride is not a pointer.  */
    1483                 :     633224 :       if (!POINTER_TYPE_P (TREE_TYPE (rhs1)))
    1484                 :            :         {
    1485                 :     351694 :           c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed);
    1486                 :     351694 :           if (c)
    1487                 :            :             {
    1488                 :     351694 :               c->next_interp = c2->cand_num;
    1489                 :     351694 :               c2->first_interp = c->cand_num;
    1490                 :            :             }
    1491                 :            :           else
    1492                 :          0 :             add_cand_for_stmt (gs, c2);
    1493                 :            :         }
    1494                 :            :     }
    1495                 :    1203910 :   else if (TREE_CODE (rhs2) == INTEGER_CST)
    1496                 :            :     {
    1497                 :            :       /* Record an interpretation for the add-immediate.  */
    1498                 :    1203910 :       widest_int index = wi::to_widest (rhs2);
    1499                 :    1203910 :       if (subtract_p)
    1500                 :      16735 :         index = -index;
    1501                 :            : 
    1502                 :    1203910 :       c = create_add_imm_cand (gs, rhs1, index, speed);
    1503                 :            : 
    1504                 :            :       /* Add the interpretation to the statement-candidate mapping.  */
    1505                 :    1203910 :       add_cand_for_stmt (gs, c);
    1506                 :            :     }
    1507                 :            : }
    1508                 :            : 
    1509                 :            : /* Given GS which is a negate of a scalar integer, make an appropriate
    1510                 :            :    entry in the candidate table.  A negate is equivalent to a multiply
    1511                 :            :    by -1.  */
    1512                 :            : 
    1513                 :            : static void
    1514                 :      61689 : slsr_process_neg (gimple *gs, tree rhs1, bool speed)
    1515                 :            : {
    1516                 :            :   /* Record a CAND_MULT interpretation for the multiply by -1.  */
    1517                 :      61689 :   slsr_cand_t c = create_mul_imm_cand (gs, rhs1, integer_minus_one_node, speed);
    1518                 :            : 
    1519                 :            :   /* Add the interpretation to the statement-candidate mapping.  */
    1520                 :      61689 :   add_cand_for_stmt (gs, c);
    1521                 :      61689 : }
    1522                 :            : 
    1523                 :            : /* Help function for legal_cast_p, operating on two trees.  Checks
    1524                 :            :    whether it's allowable to cast from RHS to LHS.  See legal_cast_p
    1525                 :            :    for more details.  */
    1526                 :            : 
    1527                 :            : static bool
    1528                 :    1873790 : legal_cast_p_1 (tree lhs_type, tree rhs_type)
    1529                 :            : {
    1530                 :    1873790 :   unsigned lhs_size, rhs_size;
    1531                 :    1873790 :   bool lhs_wraps, rhs_wraps;
    1532                 :            : 
    1533                 :    1873790 :   lhs_size = TYPE_PRECISION (lhs_type);
    1534                 :    1873790 :   rhs_size = TYPE_PRECISION (rhs_type);
    1535                 :    2330960 :   lhs_wraps = ANY_INTEGRAL_TYPE_P (lhs_type) && TYPE_OVERFLOW_WRAPS (lhs_type);
    1536                 :    2597030 :   rhs_wraps = ANY_INTEGRAL_TYPE_P (rhs_type) && TYPE_OVERFLOW_WRAPS (rhs_type);
    1537                 :            : 
    1538                 :    1873790 :   if (lhs_size < rhs_size
    1539                 :    1707020 :       || (rhs_wraps && !lhs_wraps)
    1540                 :    1156960 :       || (rhs_wraps && lhs_wraps && rhs_size != lhs_size))
    1541                 :     816214 :     return false;
    1542                 :            : 
    1543                 :            :   return true;
    1544                 :            : }
    1545                 :            : 
    1546                 :            : /* Return TRUE if GS is a statement that defines an SSA name from
    1547                 :            :    a conversion and is legal for us to combine with an add and multiply
    1548                 :            :    in the candidate table.  For example, suppose we have:
    1549                 :            : 
    1550                 :            :      A = B + i;
    1551                 :            :      C = (type) A;
    1552                 :            :      D = C * S;
    1553                 :            : 
    1554                 :            :    Without the type-cast, we would create a CAND_MULT for D with base B,
    1555                 :            :    index i, and stride S.  We want to record this candidate only if it
    1556                 :            :    is equivalent to apply the type cast following the multiply:
    1557                 :            : 
    1558                 :            :      A = B + i;
    1559                 :            :      E = A * S;
    1560                 :            :      D = (type) E;
    1561                 :            : 
    1562                 :            :    We will record the type with the candidate for D.  This allows us
    1563                 :            :    to use a similar previous candidate as a basis.  If we have earlier seen
    1564                 :            : 
    1565                 :            :      A' = B + i';
    1566                 :            :      C' = (type) A';
    1567                 :            :      D' = C' * S;
    1568                 :            : 
    1569                 :            :    we can replace D with
    1570                 :            : 
    1571                 :            :      D = D' + (i - i') * S;
    1572                 :            : 
    1573                 :            :    But if moving the type-cast would change semantics, we mustn't do this.
    1574                 :            : 
    1575                 :            :    This is legitimate for casts from a non-wrapping integral type to
    1576                 :            :    any integral type of the same or larger size.  It is not legitimate
    1577                 :            :    to convert a wrapping type to a non-wrapping type, or to a wrapping
    1578                 :            :    type of a different size.  I.e., with a wrapping type, we must
    1579                 :            :    assume that the addition B + i could wrap, in which case performing
    1580                 :            :    the multiply before or after one of the "illegal" type casts will
    1581                 :            :    have different semantics.  */
    1582                 :            : 
    1583                 :            : static bool
    1584                 :    1869820 : legal_cast_p (gimple *gs, tree rhs)
    1585                 :            : {
    1586                 :    1869820 :   if (!is_gimple_assign (gs)
    1587                 :    1869820 :       || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs)))
    1588                 :            :     return false;
    1589                 :            : 
    1590                 :    1869820 :   return legal_cast_p_1 (TREE_TYPE (gimple_assign_lhs (gs)), TREE_TYPE (rhs));
    1591                 :            : }
    1592                 :            : 
    1593                 :            : /* Given GS which is a cast to a scalar integer type, determine whether
    1594                 :            :    the cast is legal for strength reduction.  If so, make at least one
    1595                 :            :    appropriate entry in the candidate table.  */
    1596                 :            : 
    1597                 :            : static void
    1598                 :    1869820 : slsr_process_cast (gimple *gs, tree rhs1, bool speed)
    1599                 :            : {
    1600                 :    1869820 :   tree lhs, ctype;
    1601                 :    1869820 :   slsr_cand_t base_cand, c = NULL, c2;
    1602                 :    1869820 :   unsigned savings = 0;
    1603                 :            : 
    1604                 :    1869820 :   if (!legal_cast_p (gs, rhs1))
    1605                 :            :     return;
    1606                 :            : 
    1607                 :    1054460 :   lhs = gimple_assign_lhs (gs);
    1608                 :    1054460 :   base_cand = base_cand_from_table (rhs1);
    1609                 :    1054460 :   ctype = TREE_TYPE (lhs);
    1610                 :            : 
    1611                 :    1054460 :   if (base_cand && base_cand->kind != CAND_PHI)
    1612                 :            :     {
    1613                 :            :       slsr_cand_t first_cand = NULL;
    1614                 :            : 
    1615                 :     494921 :       while (base_cand)
    1616                 :            :         {
    1617                 :            :           /* Propagate all data from the base candidate except the type,
    1618                 :            :              which comes from the cast, and the base candidate's cast,
    1619                 :            :              which is no longer applicable.  */
    1620                 :     279396 :           if (has_single_use (rhs1))
    1621                 :     340528 :             savings = (base_cand->dead_savings 
    1622                 :     170264 :                        + stmt_cost (base_cand->cand_stmt, speed));
    1623                 :            : 
    1624                 :     558792 :           c = alloc_cand_and_find_basis (base_cand->kind, gs,
    1625                 :            :                                          base_cand->base_expr,
    1626                 :     279396 :                                          base_cand->index, base_cand->stride,
    1627                 :            :                                          ctype, base_cand->stride_type,
    1628                 :            :                                          savings);
    1629                 :     279396 :           if (!first_cand)
    1630                 :     215525 :             first_cand = c;
    1631                 :            : 
    1632                 :     279396 :           if (first_cand != c)
    1633                 :      63871 :             c->first_interp = first_cand->cand_num;
    1634                 :            : 
    1635                 :     279396 :           base_cand = lookup_cand (base_cand->next_interp);
    1636                 :            :         }
    1637                 :            :     }
    1638                 :            :   else 
    1639                 :            :     {
    1640                 :            :       /* If nothing is known about the RHS, create fresh CAND_ADD and
    1641                 :            :          CAND_MULT interpretations:
    1642                 :            : 
    1643                 :            :          X = Y + (0 * 1)
    1644                 :            :          X = (Y + 0) * 1
    1645                 :            : 
    1646                 :            :          The first of these is somewhat arbitrary, but the choice of
    1647                 :            :          1 for the stride simplifies the logic for propagating casts
    1648                 :            :          into their uses.  */
    1649                 :     838933 :       c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0,
    1650                 :            :                                      integer_one_node, ctype, sizetype, 0);
    1651                 :     838933 :       c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0,
    1652                 :            :                                       integer_one_node, ctype, sizetype, 0);
    1653                 :     838933 :       c->next_interp = c2->cand_num;
    1654                 :     838933 :       c2->first_interp = c->cand_num;
    1655                 :            :     }
    1656                 :            : 
    1657                 :            :   /* Add the first (or only) interpretation to the statement-candidate
    1658                 :            :      mapping.  */
    1659                 :    1054460 :   add_cand_for_stmt (gs, c);
    1660                 :            : }
    1661                 :            : 
    1662                 :            : /* Given GS which is a copy of a scalar integer type, make at least one
    1663                 :            :    appropriate entry in the candidate table.
    1664                 :            : 
    1665                 :            :    This interface is included for completeness, but is unnecessary
    1666                 :            :    if this pass immediately follows a pass that performs copy 
    1667                 :            :    propagation, such as DOM.  */
    1668                 :            : 
    1669                 :            : static void
    1670                 :     133026 : slsr_process_copy (gimple *gs, tree rhs1, bool speed)
    1671                 :            : {
    1672                 :     133026 :   slsr_cand_t base_cand, c = NULL, c2;
    1673                 :     133026 :   unsigned savings = 0;
    1674                 :            : 
    1675                 :     133026 :   base_cand = base_cand_from_table (rhs1);
    1676                 :            : 
    1677                 :     133026 :   if (base_cand && base_cand->kind != CAND_PHI)
    1678                 :            :     {
    1679                 :            :       slsr_cand_t first_cand = NULL;
    1680                 :            : 
    1681                 :     117754 :       while (base_cand)
    1682                 :            :         {
    1683                 :            :           /* Propagate all data from the base candidate.  */
    1684                 :      71378 :           if (has_single_use (rhs1))
    1685                 :     134314 :             savings = (base_cand->dead_savings 
    1686                 :      67157 :                        + stmt_cost (base_cand->cand_stmt, speed));
    1687                 :            : 
    1688                 :     142756 :           c = alloc_cand_and_find_basis (base_cand->kind, gs,
    1689                 :            :                                          base_cand->base_expr,
    1690                 :      71378 :                                          base_cand->index, base_cand->stride,
    1691                 :            :                                          base_cand->cand_type,
    1692                 :            :                                          base_cand->stride_type, savings);
    1693                 :      71378 :           if (!first_cand)
    1694                 :      46376 :             first_cand = c;
    1695                 :            : 
    1696                 :      71378 :           if (first_cand != c)
    1697                 :      25002 :             c->first_interp = first_cand->cand_num;
    1698                 :            : 
    1699                 :      71378 :           base_cand = lookup_cand (base_cand->next_interp);
    1700                 :            :         }
    1701                 :            :     }
    1702                 :            :   else 
    1703                 :            :     {
    1704                 :            :       /* If nothing is known about the RHS, create fresh CAND_ADD and
    1705                 :            :          CAND_MULT interpretations:
    1706                 :            : 
    1707                 :            :          X = Y + (0 * 1)
    1708                 :            :          X = (Y + 0) * 1
    1709                 :            : 
    1710                 :            :          The first of these is somewhat arbitrary, but the choice of
    1711                 :            :          1 for the stride simplifies the logic for propagating casts
    1712                 :            :          into their uses.  */
    1713                 :      86650 :       c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0,
    1714                 :      86650 :                                      integer_one_node, TREE_TYPE (rhs1),
    1715                 :            :                                      sizetype, 0);
    1716                 :      86650 :       c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0,
    1717                 :      86650 :                                       integer_one_node, TREE_TYPE (rhs1),
    1718                 :            :                                       sizetype, 0);
    1719                 :      86650 :       c->next_interp = c2->cand_num;
    1720                 :      86650 :       c2->first_interp = c->cand_num;
    1721                 :            :     }
    1722                 :            : 
    1723                 :            :   /* Add the first (or only) interpretation to the statement-candidate
    1724                 :            :      mapping.  */
    1725                 :     133026 :   add_cand_for_stmt (gs, c);
    1726                 :     133026 : }
    1727                 :            : 
    1728                 :     686776 : class find_candidates_dom_walker : public dom_walker
    1729                 :            : {
    1730                 :            : public:
    1731                 :     686776 :   find_candidates_dom_walker (cdi_direction direction)
    1732                 :    1373550 :     : dom_walker (direction) {}
    1733                 :            :   virtual edge before_dom_children (basic_block);
    1734                 :            : };
    1735                 :            : 
    1736                 :            : /* Find strength-reduction candidates in block BB.  */
    1737                 :            : 
    1738                 :            : edge
    1739                 :    7318720 : find_candidates_dom_walker::before_dom_children (basic_block bb)
    1740                 :            : {
    1741                 :    7318720 :   bool speed = optimize_bb_for_speed_p (bb);
    1742                 :            : 
    1743                 :   10408100 :   for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
    1744                 :    3089360 :        gsi_next (&gsi))
    1745                 :    3089360 :     slsr_process_phi (gsi.phi (), speed);
    1746                 :            : 
    1747                 :   70564300 :   for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
    1748                 :   55926900 :        gsi_next (&gsi))
    1749                 :            :     {
    1750                 :   55926900 :       gimple *gs = gsi_stmt (gsi);
    1751                 :            : 
    1752                 :   55926900 :       if (stmt_could_throw_p (cfun, gs))
    1753                 :    2402200 :         continue;
    1754                 :            : 
    1755                 :   74675400 :       if (gimple_vuse (gs) && gimple_assign_single_p (gs))
    1756                 :    9109090 :         slsr_process_ref (gs);
    1757                 :            : 
    1758                 :   44415600 :       else if (is_gimple_assign (gs)
    1759                 :   44415600 :                && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs)))
    1760                 :    1863410 :                    || POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs)))))
    1761                 :            :         {
    1762                 :    6134840 :           tree rhs1 = NULL_TREE, rhs2 = NULL_TREE;
    1763                 :            : 
    1764                 :    6134840 :           switch (gimple_assign_rhs_code (gs))
    1765                 :            :             {
    1766                 :    1831130 :             case MULT_EXPR:
    1767                 :    1831130 :             case PLUS_EXPR:
    1768                 :    1831130 :               rhs1 = gimple_assign_rhs1 (gs);
    1769                 :    1831130 :               rhs2 = gimple_assign_rhs2 (gs);
    1770                 :            :               /* Should never happen, but currently some buggy situations
    1771                 :            :                  in earlier phases put constants in rhs1.  */
    1772                 :    1831130 :               if (TREE_CODE (rhs1) != SSA_NAME)
    1773                 :        650 :                 continue;
    1774                 :            :               break;
    1775                 :            : 
    1776                 :            :             /* Possible future opportunity: rhs1 of a ptr+ can be
    1777                 :            :                an ADDR_EXPR.  */
    1778                 :     708114 :             case POINTER_PLUS_EXPR:
    1779                 :     708114 :             case MINUS_EXPR:
    1780                 :     708114 :               rhs2 = gimple_assign_rhs2 (gs);
    1781                 :    2858630 :               gcc_fallthrough ();
    1782                 :            : 
    1783                 :    2858630 :             CASE_CONVERT:
    1784                 :    2858630 :             case SSA_NAME:
    1785                 :    2858630 :             case NEGATE_EXPR:
    1786                 :    2858630 :               rhs1 = gimple_assign_rhs1 (gs);
    1787                 :    2858630 :               if (TREE_CODE (rhs1) != SSA_NAME)
    1788                 :     176170 :                 continue;
    1789                 :            :               break;
    1790                 :            : 
    1791                 :    5958020 :             default:
    1792                 :    5958020 :               ;
    1793                 :            :             }
    1794                 :            : 
    1795                 :    5958020 :           switch (gimple_assign_rhs_code (gs))
    1796                 :            :             {
    1797                 :     470701 :             case MULT_EXPR:
    1798                 :     470701 :               slsr_process_mul (gs, rhs1, rhs2, speed);
    1799                 :     470701 :               break;
    1800                 :            : 
    1801                 :    1977700 :             case PLUS_EXPR:
    1802                 :    1977700 :             case POINTER_PLUS_EXPR:
    1803                 :    1977700 :             case MINUS_EXPR:
    1804                 :    1977700 :               slsr_process_add (gs, rhs1, rhs2, speed);
    1805                 :    1977700 :               break;
    1806                 :            : 
    1807                 :      61689 :             case NEGATE_EXPR:
    1808                 :      61689 :               slsr_process_neg (gs, rhs1, speed);
    1809                 :      61689 :               break;
    1810                 :            : 
    1811                 :    1869820 :             CASE_CONVERT:
    1812                 :    1869820 :               slsr_process_cast (gs, rhs1, speed);
    1813                 :    1869820 :               break;
    1814                 :            : 
    1815                 :     133026 :             case SSA_NAME:
    1816                 :     133026 :               slsr_process_copy (gs, rhs1, speed);
    1817                 :     133026 :               break;
    1818                 :            : 
    1819                 :            :             default:
    1820                 :            :               ;
    1821                 :            :             }
    1822                 :            :         }
    1823                 :            :     }
    1824                 :    7318720 :   return NULL;
    1825                 :            : }
    1826                 :            : 
    1827                 :            : /* Dump a candidate for debug.  */
    1828                 :            : 
    1829                 :            : static void
    1830                 :         31 : dump_candidate (slsr_cand_t c)
    1831                 :            : {
    1832                 :         31 :   fprintf (dump_file, "%3d  [%d] ", c->cand_num,
    1833                 :         31 :            gimple_bb (c->cand_stmt)->index);
    1834                 :         31 :   print_gimple_stmt (dump_file, c->cand_stmt, 0);
    1835                 :         31 :   switch (c->kind)
    1836                 :            :     {
    1837                 :          3 :     case CAND_MULT:
    1838                 :          3 :       fputs ("     MULT : (", dump_file);
    1839                 :          3 :       print_generic_expr (dump_file, c->base_expr);
    1840                 :          3 :       fputs (" + ", dump_file);
    1841                 :          3 :       print_decs (c->index, dump_file);
    1842                 :          3 :       fputs (") * ", dump_file);
    1843                 :          3 :       if (TREE_CODE (c->stride) != INTEGER_CST
    1844                 :          3 :           && c->stride_type != TREE_TYPE (c->stride))
    1845                 :            :         {
    1846                 :          0 :           fputs ("(", dump_file);
    1847                 :          0 :           print_generic_expr (dump_file, c->stride_type);
    1848                 :          0 :           fputs (")", dump_file);
    1849                 :            :         }
    1850                 :          3 :       print_generic_expr (dump_file, c->stride);
    1851                 :          3 :       fputs (" : ", dump_file);
    1852                 :          3 :       break;
    1853                 :         17 :     case CAND_ADD:
    1854                 :         17 :       fputs ("     ADD  : ", dump_file);
    1855                 :         17 :       print_generic_expr (dump_file, c->base_expr);
    1856                 :         17 :       fputs (" + (", dump_file);
    1857                 :         17 :       print_decs (c->index, dump_file);
    1858                 :         17 :       fputs (" * ", dump_file);
    1859                 :         17 :       if (TREE_CODE (c->stride) != INTEGER_CST
    1860                 :         17 :           && c->stride_type != TREE_TYPE (c->stride))
    1861                 :            :         {
    1862                 :          0 :           fputs ("(", dump_file);
    1863                 :          0 :           print_generic_expr (dump_file, c->stride_type);
    1864                 :          0 :           fputs (")", dump_file);
    1865                 :            :         }
    1866                 :         17 :       print_generic_expr (dump_file, c->stride);
    1867                 :         17 :       fputs (") : ", dump_file);
    1868                 :         17 :       break;
    1869                 :         11 :     case CAND_REF:
    1870                 :         11 :       fputs ("     REF  : ", dump_file);
    1871                 :         11 :       print_generic_expr (dump_file, c->base_expr);
    1872                 :         11 :       fputs (" + (", dump_file);
    1873                 :         11 :       print_generic_expr (dump_file, c->stride);
    1874                 :         11 :       fputs (") + ", dump_file);
    1875                 :         11 :       print_decs (c->index, dump_file);
    1876                 :         11 :       fputs (" : ", dump_file);
    1877                 :         11 :       break;
    1878                 :          0 :     case CAND_PHI:
    1879                 :          0 :       fputs ("     PHI  : ", dump_file);
    1880                 :          0 :       print_generic_expr (dump_file, c->base_expr);
    1881                 :          0 :       fputs (" + (unknown * ", dump_file);
    1882                 :          0 :       print_generic_expr (dump_file, c->stride);
    1883                 :          0 :       fputs (") : ", dump_file);
    1884                 :          0 :       break;
    1885                 :          0 :     default:
    1886                 :          0 :       gcc_unreachable ();
    1887                 :            :     }
    1888                 :         31 :   print_generic_expr (dump_file, c->cand_type);
    1889                 :         31 :   fprintf (dump_file, "\n     basis: %d  dependent: %d  sibling: %d\n",
    1890                 :            :            c->basis, c->dependent, c->sibling);
    1891                 :         31 :   fprintf (dump_file,
    1892                 :            :            "     next-interp: %d  first-interp: %d  dead-savings: %d\n",
    1893                 :            :            c->next_interp, c->first_interp, c->dead_savings);
    1894                 :         31 :   if (c->def_phi)
    1895                 :          0 :     fprintf (dump_file, "     phi:  %d\n", c->def_phi);
    1896                 :         31 :   fputs ("\n", dump_file);
    1897                 :         31 : }
    1898                 :            : 
    1899                 :            : /* Dump the candidate vector for debug.  */
    1900                 :            : 
    1901                 :            : static void
    1902                 :          3 : dump_cand_vec (void)
    1903                 :            : {
    1904                 :          3 :   unsigned i;
    1905                 :          3 :   slsr_cand_t c;
    1906                 :            : 
    1907                 :          3 :   fprintf (dump_file, "\nStrength reduction candidate vector:\n\n");
    1908                 :            :   
    1909                 :         37 :   FOR_EACH_VEC_ELT (cand_vec, i, c)
    1910                 :         34 :     if (c != NULL)
    1911                 :         31 :       dump_candidate (c);
    1912                 :          3 : }
    1913                 :            : 
    1914                 :            : /* Callback used to dump the candidate chains hash table.  */
    1915                 :            : 
    1916                 :            : int
    1917                 :         15 : ssa_base_cand_dump_callback (cand_chain **slot, void *ignored ATTRIBUTE_UNUSED)
    1918                 :            : {
    1919                 :         15 :   const_cand_chain_t chain = *slot;
    1920                 :         15 :   cand_chain_t p;
    1921                 :            : 
    1922                 :         15 :   print_generic_expr (dump_file, chain->base_expr);
    1923                 :         15 :   fprintf (dump_file, " -> %d", chain->cand->cand_num);
    1924                 :            : 
    1925                 :         40 :   for (p = chain->next; p; p = p->next)
    1926                 :         25 :     fprintf (dump_file, " -> %d", p->cand->cand_num);
    1927                 :            : 
    1928                 :         15 :   fputs ("\n", dump_file);
    1929                 :         15 :   return 1;
    1930                 :            : }
    1931                 :            : 
    1932                 :            : /* Dump the candidate chains.  */
    1933                 :            : 
    1934                 :            : static void
    1935                 :          3 : dump_cand_chains (void)
    1936                 :            : {
    1937                 :          3 :   fprintf (dump_file, "\nStrength reduction candidate chains:\n\n");
    1938                 :          3 :   base_cand_map->traverse_noresize <void *, ssa_base_cand_dump_callback>
    1939                 :          3 :     (NULL);
    1940                 :          3 :   fputs ("\n", dump_file);
    1941                 :          3 : }
    1942                 :            : 
    1943                 :            : /* Dump the increment vector for debug.  */
    1944                 :            : 
    1945                 :            : static void
    1946                 :      54588 : dump_incr_vec (void)
    1947                 :            : {
    1948                 :      54588 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1949                 :            :     {
    1950                 :          0 :       unsigned i;
    1951                 :            : 
    1952                 :          0 :       fprintf (dump_file, "\nIncrement vector:\n\n");
    1953                 :            :   
    1954                 :          0 :       for (i = 0; i < incr_vec_len; i++)
    1955                 :            :         {
    1956                 :          0 :           fprintf (dump_file, "%3d  increment:   ", i);
    1957                 :          0 :           print_decs (incr_vec[i].incr, dump_file);
    1958                 :          0 :           fprintf (dump_file, "\n     count:       %d", incr_vec[i].count);
    1959                 :          0 :           fprintf (dump_file, "\n     cost:        %d", incr_vec[i].cost);
    1960                 :          0 :           fputs ("\n     initializer: ", dump_file);
    1961                 :          0 :           print_generic_expr (dump_file, incr_vec[i].initializer);
    1962                 :          0 :           fputs ("\n\n", dump_file);
    1963                 :            :         }
    1964                 :            :     }
    1965                 :      54588 : }
    1966                 :            : 
    1967                 :            : /* Replace *EXPR in candidate C with an equivalent strength-reduced
    1968                 :            :    data reference.  */
    1969                 :            : 
    1970                 :            : static void
    1971                 :      19942 : replace_ref (tree *expr, slsr_cand_t c)
    1972                 :            : {
    1973                 :      19942 :   tree add_expr, mem_ref, acc_type = TREE_TYPE (*expr);
    1974                 :      19942 :   unsigned HOST_WIDE_INT misalign;
    1975                 :      19942 :   unsigned align;
    1976                 :            : 
    1977                 :            :   /* Ensure the memory reference carries the minimum alignment
    1978                 :            :      requirement for the data type.  See PR58041.  */
    1979                 :      19942 :   get_object_alignment_1 (*expr, &align, &misalign);
    1980                 :      19942 :   if (misalign != 0)
    1981                 :        326 :     align = least_bit_hwi (misalign);
    1982                 :      19942 :   if (align < TYPE_ALIGN (acc_type))
    1983                 :         18 :     acc_type = build_aligned_type (acc_type, align);
    1984                 :            : 
    1985                 :      19942 :   add_expr = fold_build2 (POINTER_PLUS_EXPR, c->cand_type,
    1986                 :            :                           c->base_expr, c->stride);
    1987                 :      19942 :   mem_ref = fold_build2 (MEM_REF, acc_type, add_expr,
    1988                 :            :                          wide_int_to_tree (c->cand_type, c->index));
    1989                 :            : 
    1990                 :            :   /* Gimplify the base addressing expression for the new MEM_REF tree.  */
    1991                 :      19942 :   gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
    1992                 :      39884 :   TREE_OPERAND (mem_ref, 0)
    1993                 :      19942 :     = force_gimple_operand_gsi (&gsi, TREE_OPERAND (mem_ref, 0),
    1994                 :            :                                 /*simple_p=*/true, NULL,
    1995                 :            :                                 /*before=*/true, GSI_SAME_STMT);
    1996                 :      19942 :   copy_ref_info (mem_ref, *expr);
    1997                 :      19942 :   *expr = mem_ref;
    1998                 :      19942 :   update_stmt (c->cand_stmt);
    1999                 :      19942 : }
    2000                 :            : 
    2001                 :            : /* Return true if CAND_REF candidate C is a valid memory reference.  */
    2002                 :            : 
    2003                 :            : static bool
    2004                 :       6221 : valid_mem_ref_cand_p (slsr_cand_t c)
    2005                 :            : {
    2006                 :       6221 :   if (TREE_CODE (TREE_OPERAND (c->stride, 1)) != INTEGER_CST)
    2007                 :            :     return false;
    2008                 :            : 
    2009                 :       6221 :   struct mem_address addr
    2010                 :      12442 :     = { NULL_TREE, c->base_expr, TREE_OPERAND (c->stride, 0),
    2011                 :       6221 :         TREE_OPERAND (c->stride, 1), wide_int_to_tree (sizetype, c->index) };
    2012                 :            : 
    2013                 :       6221 :   return
    2014                 :       6221 :     valid_mem_ref_p (TYPE_MODE (c->cand_type), TYPE_ADDR_SPACE (c->cand_type),
    2015                 :       6221 :                      &addr);
    2016                 :            : }
    2017                 :            : 
    2018                 :            : /* Replace CAND_REF candidate C, each sibling of candidate C, and each
    2019                 :            :    dependent of candidate C with an equivalent strength-reduced data
    2020                 :            :    reference.  */
    2021                 :            : 
    2022                 :            : static void
    2023                 :       7008 : replace_refs (slsr_cand_t c)
    2024                 :            : {
    2025                 :            :   /* Replacing a chain of only 2 candidates which are valid memory references
    2026                 :            :      is generally counter-productive because you cannot recoup the additional
    2027                 :            :      calculation added in front of them.  */
    2028                 :      22754 :   if (c->basis == 0
    2029                 :       6795 :       && c->dependent
    2030                 :       6795 :       && !lookup_cand (c->dependent)->dependent
    2031                 :       3409 :       && valid_mem_ref_cand_p (c)
    2032                 :      25566 :       && valid_mem_ref_cand_p (lookup_cand (c->dependent)))
    2033                 :            :     return;
    2034                 :            : 
    2035                 :      19942 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2036                 :            :     {
    2037                 :          9 :       fputs ("Replacing reference: ", dump_file);
    2038                 :          9 :       print_gimple_stmt (dump_file, c->cand_stmt, 0);
    2039                 :            :     }
    2040                 :            : 
    2041                 :      39884 :   if (gimple_vdef (c->cand_stmt))
    2042                 :            :     {
    2043                 :       8113 :       tree *lhs = gimple_assign_lhs_ptr (c->cand_stmt);
    2044                 :       8113 :       replace_ref (lhs, c);
    2045                 :            :     }
    2046                 :            :   else
    2047                 :            :     {
    2048                 :      11829 :       tree *rhs = gimple_assign_rhs1_ptr (c->cand_stmt);
    2049                 :      11829 :       replace_ref (rhs, c);
    2050                 :            :     }
    2051                 :            : 
    2052                 :      19942 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2053                 :            :     {
    2054                 :          9 :       fputs ("With: ", dump_file);
    2055                 :          9 :       print_gimple_stmt (dump_file, c->cand_stmt, 0);
    2056                 :          9 :       fputs ("\n", dump_file);
    2057                 :            :     }
    2058                 :            : 
    2059                 :      19942 :   if (c->sibling)
    2060                 :        213 :     replace_refs (lookup_cand (c->sibling));
    2061                 :            : 
    2062                 :      19942 :   if (c->dependent)
    2063                 :      15746 :     replace_refs (lookup_cand (c->dependent));
    2064                 :            : }
    2065                 :            : 
    2066                 :            : /* Return TRUE if candidate C is dependent upon a PHI.  */
    2067                 :            : 
    2068                 :            : static bool
    2069                 :    2076950 : phi_dependent_cand_p (slsr_cand_t c)
    2070                 :            : {
    2071                 :            :   /* A candidate is not necessarily dependent upon a PHI just because
    2072                 :            :      it has a phi definition for its base name.  It may have a basis
    2073                 :            :      that relies upon the same phi definition, in which case the PHI
    2074                 :            :      is irrelevant to this candidate.  */
    2075                 :    2076950 :   return (c->def_phi
    2076                 :       6540 :           && c->basis
    2077                 :    2083490 :           && lookup_cand (c->basis)->def_phi != c->def_phi);
    2078                 :            : }
    2079                 :            : 
    2080                 :            : /* Calculate the increment required for candidate C relative to 
    2081                 :            :    its basis.  */
    2082                 :            : 
    2083                 :            : static widest_int
    2084                 :    1106090 : cand_increment (slsr_cand_t c)
    2085                 :            : {
    2086                 :    1106090 :   slsr_cand_t basis;
    2087                 :            : 
    2088                 :            :   /* If the candidate doesn't have a basis, just return its own
    2089                 :            :      index.  This is useful in record_increments to help us find
    2090                 :            :      an existing initializer.  Also, if the candidate's basis is
    2091                 :            :      hidden by a phi, then its own index will be the increment
    2092                 :            :      from the newly introduced phi basis.  */
    2093                 :    1106090 :   if (!c->basis || phi_dependent_cand_p (c))
    2094                 :      54809 :     return c->index;
    2095                 :            : 
    2096                 :    1051280 :   basis = lookup_cand (c->basis);
    2097                 :    1051280 :   gcc_assert (operand_equal_p (c->base_expr, basis->base_expr, 0));
    2098                 :    1051280 :   return c->index - basis->index;
    2099                 :            : }
    2100                 :            : 
    2101                 :            : /* Calculate the increment required for candidate C relative to
    2102                 :            :    its basis.  If we aren't going to generate pointer arithmetic
    2103                 :            :    for this candidate, return the absolute value of that increment
    2104                 :            :    instead.  */
    2105                 :            : 
    2106                 :            : static inline widest_int
    2107                 :      88883 : cand_abs_increment (slsr_cand_t c)
    2108                 :            : {
    2109                 :      88883 :   widest_int increment = cand_increment (c);
    2110                 :            : 
    2111                 :     172294 :   if (!address_arithmetic_p && wi::neg_p (increment))
    2112                 :       2817 :     increment = -increment;
    2113                 :            : 
    2114                 :      88883 :   return increment;
    2115                 :            : }
    2116                 :            : 
    2117                 :            : /* Return TRUE iff candidate C has already been replaced under
    2118                 :            :    another interpretation.  */
    2119                 :            : 
    2120                 :            : static inline bool
    2121                 :    1279360 : cand_already_replaced (slsr_cand_t c)
    2122                 :            : {
    2123                 :    1279360 :   return (gimple_bb (c->cand_stmt) == 0);
    2124                 :            : }
    2125                 :            : 
    2126                 :            : /* Common logic used by replace_unconditional_candidate and
    2127                 :            :    replace_conditional_candidate.  */
    2128                 :            : 
    2129                 :            : static void
    2130                 :     864134 : replace_mult_candidate (slsr_cand_t c, tree basis_name, widest_int bump)
    2131                 :            : {
    2132                 :     864134 :   tree target_type = TREE_TYPE (gimple_assign_lhs (c->cand_stmt));
    2133                 :     864134 :   enum tree_code cand_code = gimple_assign_rhs_code (c->cand_stmt);
    2134                 :            : 
    2135                 :            :   /* It is not useful to replace casts, copies, negates, or adds of
    2136                 :            :      an SSA name and a constant.  */
    2137                 :     864134 :   if (cand_code == SSA_NAME
    2138                 :     806628 :       || CONVERT_EXPR_CODE_P (cand_code)
    2139                 :     419217 :       || cand_code == PLUS_EXPR
    2140                 :     419217 :       || cand_code == POINTER_PLUS_EXPR
    2141                 :      72746 :       || cand_code == MINUS_EXPR
    2142                 :      72746 :       || cand_code == NEGATE_EXPR)
    2143                 :            :     return;
    2144                 :            : 
    2145                 :      63299 :   enum tree_code code = PLUS_EXPR;
    2146                 :      63299 :   tree bump_tree;
    2147                 :      63299 :   gimple *stmt_to_print = NULL;
    2148                 :            : 
    2149                 :      63299 :   if (wi::neg_p (bump))
    2150                 :            :     {
    2151                 :       7283 :       code = MINUS_EXPR;
    2152                 :       7283 :       bump = -bump;
    2153                 :            :     }
    2154                 :            : 
    2155                 :            :   /* It is possible that the resulting bump doesn't fit in target_type.
    2156                 :            :      Abandon the replacement in this case.  This does not affect
    2157                 :            :      siblings or dependents of C.  */
    2158                 :     126598 :   if (bump != wi::ext (bump, TYPE_PRECISION (target_type),
    2159                 :      63299 :                        TYPE_SIGN (target_type)))
    2160                 :         75 :     return;
    2161                 :            : 
    2162                 :      63224 :   bump_tree = wide_int_to_tree (target_type, bump);
    2163                 :            : 
    2164                 :            :   /* If the basis name and the candidate's LHS have incompatible types,
    2165                 :            :      introduce a cast.  */
    2166                 :      63224 :   if (!useless_type_conversion_p (target_type, TREE_TYPE (basis_name)))
    2167                 :          0 :     basis_name = introduce_cast_before_cand (c, target_type, basis_name);
    2168                 :            : 
    2169                 :      63224 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2170                 :            :     {
    2171                 :          0 :       fputs ("Replacing: ", dump_file);
    2172                 :          0 :       print_gimple_stmt (dump_file, c->cand_stmt, 0);
    2173                 :            :     }
    2174                 :            : 
    2175                 :      63224 :   if (bump == 0)
    2176                 :            :     {
    2177                 :      40760 :       tree lhs = gimple_assign_lhs (c->cand_stmt);
    2178                 :      40760 :       gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
    2179                 :      40760 :       gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
    2180                 :      40760 :       slsr_cand_t cc = lookup_cand (c->first_interp);
    2181                 :      40760 :       gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
    2182                 :      40760 :       gsi_replace (&gsi, copy_stmt, false);
    2183                 :      81520 :       while (cc)
    2184                 :            :         {
    2185                 :      40760 :           cc->cand_stmt = copy_stmt;
    2186                 :      40760 :           cc = lookup_cand (cc->next_interp);
    2187                 :            :         }
    2188                 :      40760 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2189                 :            :         stmt_to_print = copy_stmt;
    2190                 :            :     }
    2191                 :            :   else
    2192                 :            :     {
    2193                 :      22464 :       tree rhs1, rhs2;
    2194                 :      22464 :       if (cand_code != NEGATE_EXPR) {
    2195                 :      22464 :         rhs1 = gimple_assign_rhs1 (c->cand_stmt);
    2196                 :      22464 :         rhs2 = gimple_assign_rhs2 (c->cand_stmt);
    2197                 :            :       }
    2198                 :      22464 :       if (cand_code != NEGATE_EXPR
    2199                 :      22464 :           && ((operand_equal_p (rhs1, basis_name, 0)
    2200                 :          0 :                && operand_equal_p (rhs2, bump_tree, 0))
    2201                 :      22464 :               || (operand_equal_p (rhs1, bump_tree, 0)
    2202                 :          0 :                   && operand_equal_p (rhs2, basis_name, 0))))
    2203                 :            :         {
    2204                 :          0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2205                 :            :             {
    2206                 :          0 :               fputs ("(duplicate, not actually replacing)", dump_file);
    2207                 :          0 :               stmt_to_print = c->cand_stmt;
    2208                 :            :             }
    2209                 :            :         }
    2210                 :            :       else
    2211                 :            :         {
    2212                 :      22464 :           gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
    2213                 :      22464 :           slsr_cand_t cc = lookup_cand (c->first_interp);
    2214                 :      22464 :           gimple_assign_set_rhs_with_ops (&gsi, code, basis_name, bump_tree);
    2215                 :      22464 :           update_stmt (gsi_stmt (gsi));
    2216                 :      44928 :           while (cc)
    2217                 :            :             {
    2218                 :      22464 :               cc->cand_stmt = gsi_stmt (gsi);
    2219                 :      22464 :               cc = lookup_cand (cc->next_interp);
    2220                 :            :             }
    2221                 :      22464 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2222                 :          0 :             stmt_to_print = gsi_stmt (gsi);
    2223                 :            :         }
    2224                 :            :     }
    2225                 :            :   
    2226                 :      63224 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2227                 :            :     {
    2228                 :          0 :       fputs ("With: ", dump_file);
    2229                 :          0 :       print_gimple_stmt (dump_file, stmt_to_print, 0);
    2230                 :          0 :       fputs ("\n", dump_file);
    2231                 :            :     }
    2232                 :            : }
    2233                 :            : 
    2234                 :            : /* Replace candidate C with an add or subtract.   Note that we only
    2235                 :            :    operate on CAND_MULTs with known strides, so we will never generate
    2236                 :            :    a POINTER_PLUS_EXPR.  Each candidate X = (B + i) * S is replaced by
    2237                 :            :    X = Y + ((i - i') * S), as described in the module commentary.  The
    2238                 :            :    folded value ((i - i') * S) is referred to here as the "bump."  */
    2239                 :            : 
    2240                 :            : static void
    2241                 :     863852 : replace_unconditional_candidate (slsr_cand_t c)
    2242                 :            : {
    2243                 :     863852 :   slsr_cand_t basis;
    2244                 :            : 
    2245                 :     863852 :   if (cand_already_replaced (c))
    2246                 :          0 :     return;
    2247                 :            : 
    2248                 :     863852 :   basis = lookup_cand (c->basis);
    2249                 :     863852 :   widest_int bump = cand_increment (c) * wi::to_widest (c->stride);
    2250                 :            : 
    2251                 :     863852 :   replace_mult_candidate (c, gimple_assign_lhs (basis->cand_stmt), bump);
    2252                 :            : }
    2253                 :            : 
    2254                 :            : /* Return the index in the increment vector of the given INCREMENT,
    2255                 :            :    or -1 if not found.  The latter can occur if more than
    2256                 :            :    MAX_INCR_VEC_LEN increments have been found.  */
    2257                 :            : 
    2258                 :            : static inline int
    2259                 :      82234 : incr_vec_index (const widest_int &increment)
    2260                 :            : {
    2261                 :      82234 :   unsigned i;
    2262                 :            :   
    2263                 :     238376 :   for (i = 0; i < incr_vec_len && increment != incr_vec[i].incr; i++)
    2264                 :            :     ;
    2265                 :            : 
    2266                 :      82234 :   if (i < incr_vec_len)
    2267                 :      82234 :     return i;
    2268                 :            :   else
    2269                 :            :     return -1;
    2270                 :            : }
    2271                 :            : 
    2272                 :            : /* Create a new statement along edge E to add BASIS_NAME to the product
    2273                 :            :    of INCREMENT and the stride of candidate C.  Create and return a new
    2274                 :            :    SSA name from *VAR to be used as the LHS of the new statement.
    2275                 :            :    KNOWN_STRIDE is true iff C's stride is a constant.  */
    2276                 :            : 
    2277                 :            : static tree
    2278                 :        358 : create_add_on_incoming_edge (slsr_cand_t c, tree basis_name,
    2279                 :            :                              widest_int increment, edge e, location_t loc,
    2280                 :            :                              bool known_stride)
    2281                 :            : {
    2282                 :        358 :   tree lhs, basis_type;
    2283                 :        358 :   gassign *new_stmt, *cast_stmt = NULL;
    2284                 :            : 
    2285                 :            :   /* If the add candidate along this incoming edge has the same
    2286                 :            :      index as C's hidden basis, the hidden basis represents this
    2287                 :            :      edge correctly.  */
    2288                 :        358 :   if (increment == 0)
    2289                 :            :     return basis_name;
    2290                 :            : 
    2291                 :        288 :   basis_type = TREE_TYPE (basis_name);
    2292                 :        288 :   lhs = make_temp_ssa_name (basis_type, NULL, "slsr");
    2293                 :            : 
    2294                 :            :   /* Occasionally people convert integers to pointers without a 
    2295                 :            :      cast, leading us into trouble if we aren't careful.  */
    2296                 :        576 :   enum tree_code plus_code
    2297                 :        288 :     = POINTER_TYPE_P (basis_type) ? POINTER_PLUS_EXPR : PLUS_EXPR;
    2298                 :            : 
    2299                 :        288 :   if (known_stride)
    2300                 :            :     {
    2301                 :        218 :       tree bump_tree;
    2302                 :        218 :       enum tree_code code = plus_code;
    2303                 :        218 :       widest_int bump = increment * wi::to_widest (c->stride);
    2304                 :        218 :       if (wi::neg_p (bump) && !POINTER_TYPE_P (basis_type))
    2305                 :            :         {
    2306                 :         38 :           code = MINUS_EXPR;
    2307                 :         38 :           bump = -bump;
    2308                 :            :         }
    2309                 :            : 
    2310                 :        218 :       tree stride_type = POINTER_TYPE_P (basis_type) ? sizetype : basis_type;
    2311                 :        218 :       bump_tree = wide_int_to_tree (stride_type, bump);
    2312                 :        218 :       new_stmt = gimple_build_assign (lhs, code, basis_name, bump_tree);
    2313                 :            :     }
    2314                 :            :   else
    2315                 :            :     {
    2316                 :         70 :       int i;
    2317                 :        140 :       bool negate_incr = !POINTER_TYPE_P (basis_type) && wi::neg_p (increment);
    2318                 :         73 :       i = incr_vec_index (negate_incr ? -increment : increment);
    2319                 :         70 :       gcc_assert (i >= 0);
    2320                 :            : 
    2321                 :         70 :       if (incr_vec[i].initializer)
    2322                 :            :         {
    2323                 :         18 :           enum tree_code code = negate_incr ? MINUS_EXPR : plus_code;
    2324                 :         18 :           new_stmt = gimple_build_assign (lhs, code, basis_name,
    2325                 :            :                                           incr_vec[i].initializer);
    2326                 :            :         }
    2327                 :            :       else {
    2328                 :         52 :         tree stride;
    2329                 :            : 
    2330                 :         52 :         if (!types_compatible_p (TREE_TYPE (c->stride), c->stride_type))
    2331                 :            :           {
    2332                 :          0 :             tree cast_stride = make_temp_ssa_name (c->stride_type, NULL,
    2333                 :            :                                                    "slsr");
    2334                 :          0 :             cast_stmt = gimple_build_assign (cast_stride, NOP_EXPR,
    2335                 :            :                                              c->stride);
    2336                 :          0 :             stride = cast_stride;
    2337                 :            :           }
    2338                 :            :         else
    2339                 :         52 :           stride = c->stride;
    2340                 :            : 
    2341                 :         52 :         if (increment == 1)
    2342                 :         52 :           new_stmt = gimple_build_assign (lhs, plus_code, basis_name, stride);
    2343                 :          0 :         else if (increment == -1)
    2344                 :          0 :           new_stmt = gimple_build_assign (lhs, MINUS_EXPR, basis_name, stride);
    2345                 :            :         else
    2346                 :          0 :           gcc_unreachable ();
    2347                 :            :       }
    2348                 :            :     }
    2349                 :            : 
    2350                 :        288 :   if (cast_stmt)
    2351                 :            :     {
    2352                 :          0 :       gimple_set_location (cast_stmt, loc);
    2353                 :          0 :       gsi_insert_on_edge (e, cast_stmt);
    2354                 :            :     }
    2355                 :            : 
    2356                 :        288 :   gimple_set_location (new_stmt, loc);
    2357                 :        288 :   gsi_insert_on_edge (e, new_stmt);
    2358                 :            : 
    2359                 :        288 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2360                 :            :     {
    2361                 :          0 :       if (cast_stmt)
    2362                 :            :         {
    2363                 :          0 :           fprintf (dump_file, "Inserting cast on edge %d->%d: ",
    2364                 :          0 :                    e->src->index, e->dest->index);
    2365                 :          0 :           print_gimple_stmt (dump_file, cast_stmt, 0);
    2366                 :            :         }
    2367                 :          0 :       fprintf (dump_file, "Inserting on edge %d->%d: ", e->src->index,
    2368                 :          0 :                e->dest->index);
    2369                 :          0 :       print_gimple_stmt (dump_file, new_stmt, 0);
    2370                 :            :     }
    2371                 :            : 
    2372                 :            :   return lhs;
    2373                 :            : }
    2374                 :            : 
    2375                 :            : /* Clear the visited field for a tree of PHI candidates.  */
    2376                 :            : 
    2377                 :            : static void
    2378                 :       3330 : clear_visited (gphi *phi)
    2379                 :            : {
    2380                 :       3330 :   unsigned i;
    2381                 :       3330 :   slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
    2382                 :            : 
    2383                 :       3330 :   if (phi_cand->visited)
    2384                 :            :     {
    2385                 :       3330 :       phi_cand->visited = 0;
    2386                 :            : 
    2387                 :       6740 :       for (i = 0; i < gimple_phi_num_args (phi); i++)
    2388                 :            :         {
    2389                 :       3410 :           tree arg = gimple_phi_arg_def (phi, i);
    2390                 :       3410 :           gimple *arg_def = SSA_NAME_DEF_STMT (arg);
    2391                 :       3410 :           if (gimple_code (arg_def) == GIMPLE_PHI)
    2392                 :          2 :             clear_visited (as_a <gphi *> (arg_def));
    2393                 :            :         }
    2394                 :            :     }
    2395                 :       3330 : }
    2396                 :            : 
    2397                 :            : /* Recursive helper function for create_phi_basis.  */
    2398                 :            : 
    2399                 :            : static tree
    2400                 :        348 : create_phi_basis_1 (slsr_cand_t c, gimple *from_phi, tree basis_name,
    2401                 :            :                     location_t loc, bool known_stride)
    2402                 :            : {
    2403                 :        348 :   int i;
    2404                 :        348 :   tree name, phi_arg;
    2405                 :        348 :   gphi *phi;
    2406                 :        348 :   slsr_cand_t basis = lookup_cand (c->basis);
    2407                 :        348 :   int nargs = gimple_phi_num_args (from_phi);
    2408                 :        348 :   basic_block phi_bb = gimple_bb (from_phi);
    2409                 :        348 :   slsr_cand_t phi_cand = *stmt_cand_map->get (from_phi);
    2410                 :        348 :   auto_vec<tree> phi_args (nargs);
    2411                 :            : 
    2412                 :        348 :   if (phi_cand->visited)
    2413                 :          0 :     return phi_cand->cached_basis;
    2414                 :        348 :   phi_cand->visited = 1;
    2415                 :            : 
    2416                 :            :   /* Process each argument of the existing phi that represents
    2417                 :            :      conditionally-executed add candidates.  */
    2418                 :        714 :   for (i = 0; i < nargs; i++)
    2419                 :            :     {
    2420                 :        366 :       edge e = (*phi_bb->preds)[i];
    2421                 :        366 :       tree arg = gimple_phi_arg_def (from_phi, i);
    2422                 :        366 :       tree feeding_def;
    2423                 :            : 
    2424                 :            :       /* If the phi argument is the base name of the CAND_PHI, then
    2425                 :            :          this incoming arc should use the hidden basis.  */
    2426                 :        366 :       if (operand_equal_p (arg, phi_cand->base_expr, 0))
    2427                 :          9 :         if (basis->index == 0)
    2428                 :          7 :           feeding_def = gimple_assign_lhs (basis->cand_stmt);
    2429                 :            :         else
    2430                 :            :           {
    2431                 :          2 :             widest_int incr = -basis->index;
    2432                 :          2 :             feeding_def = create_add_on_incoming_edge (c, basis_name, incr,
    2433                 :            :                                                        e, loc, known_stride);
    2434                 :            :           }
    2435                 :            :       else
    2436                 :            :         {
    2437                 :        357 :           gimple *arg_def = SSA_NAME_DEF_STMT (arg);
    2438                 :            : 
    2439                 :            :           /* If there is another phi along this incoming edge, we must
    2440                 :            :              process it in the same fashion to ensure that all basis
    2441                 :            :              adjustments are made along its incoming edges.  */
    2442                 :        357 :           if (gimple_code (arg_def) == GIMPLE_PHI)
    2443                 :          1 :             feeding_def = create_phi_basis_1 (c, arg_def, basis_name,
    2444                 :            :                                               loc, known_stride);
    2445                 :            :           else
    2446                 :            :             {
    2447                 :        356 :               slsr_cand_t arg_cand = base_cand_from_table (arg);
    2448                 :        356 :               widest_int diff = arg_cand->index - basis->index;
    2449                 :        356 :               feeding_def = create_add_on_incoming_edge (c, basis_name, diff,
    2450                 :            :                                                          e, loc, known_stride);
    2451                 :            :             }
    2452                 :            :         }
    2453                 :            : 
    2454                 :            :       /* Because of recursion, we need to save the arguments in a vector
    2455                 :            :          so we can create the PHI statement all at once.  Otherwise the
    2456                 :            :          storage for the half-created PHI can be reclaimed.  */
    2457                 :        366 :       phi_args.safe_push (feeding_def);
    2458                 :            :     }
    2459                 :            : 
    2460                 :            :   /* Create the new phi basis.  */
    2461                 :        348 :   name = make_temp_ssa_name (TREE_TYPE (basis_name), NULL, "slsr");
    2462                 :        348 :   phi = create_phi_node (name, phi_bb);
    2463                 :        348 :   SSA_NAME_DEF_STMT (name) = phi;
    2464                 :            : 
    2465                 :        714 :   FOR_EACH_VEC_ELT (phi_args, i, phi_arg)
    2466                 :            :     {
    2467                 :        366 :       edge e = (*phi_bb->preds)[i];
    2468                 :        366 :       add_phi_arg (phi, phi_arg, e, loc);
    2469                 :            :     }
    2470                 :            : 
    2471                 :        348 :   update_stmt (phi);
    2472                 :            : 
    2473                 :        348 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2474                 :            :     {
    2475                 :          0 :       fputs ("Introducing new phi basis: ", dump_file);
    2476                 :          0 :       print_gimple_stmt (dump_file, phi, 0);
    2477                 :            :     }
    2478                 :            : 
    2479                 :        348 :   phi_cand->cached_basis = name;
    2480                 :        348 :   return name;
    2481                 :            : }
    2482                 :            : 
    2483                 :            : /* Given a candidate C with BASIS_NAME being the LHS of C's basis which
    2484                 :            :    is hidden by the phi node FROM_PHI, create a new phi node in the same
    2485                 :            :    block as FROM_PHI.  The new phi is suitable for use as a basis by C,
    2486                 :            :    with its phi arguments representing conditional adjustments to the
    2487                 :            :    hidden basis along conditional incoming paths.  Those adjustments are
    2488                 :            :    made by creating add statements (and sometimes recursively creating
    2489                 :            :    phis) along those incoming paths.  LOC is the location to attach to
    2490                 :            :    the introduced statements.  KNOWN_STRIDE is true iff C's stride is a
    2491                 :            :    constant.  */
    2492                 :            : 
    2493                 :            : static tree
    2494                 :        347 : create_phi_basis (slsr_cand_t c, gimple *from_phi, tree basis_name,
    2495                 :            :                   location_t loc, bool known_stride)
    2496                 :            : {
    2497                 :        347 :   tree retval = create_phi_basis_1 (c, from_phi, basis_name, loc,
    2498                 :            :                                     known_stride);
    2499                 :        347 :   gcc_assert (retval);
    2500                 :        347 :   clear_visited (as_a <gphi *> (from_phi));
    2501                 :        347 :   return retval;
    2502                 :            : }
    2503                 :            : 
    2504                 :            : /* Given a candidate C whose basis is hidden by at least one intervening
    2505                 :            :    phi, introduce a matching number of new phis to represent its basis
    2506                 :            :    adjusted by conditional increments along possible incoming paths.  Then
    2507                 :            :    replace C as though it were an unconditional candidate, using the new
    2508                 :            :    basis.  */
    2509                 :            : 
    2510                 :            : static void
    2511                 :        282 : replace_conditional_candidate (slsr_cand_t c)
    2512                 :            : {
    2513                 :        282 :   tree basis_name, name;
    2514                 :        282 :   slsr_cand_t basis;
    2515                 :        282 :   location_t loc;
    2516                 :            : 
    2517                 :            :   /* Look up the LHS SSA name from C's basis.  This will be the 
    2518                 :            :      RHS1 of the adds we will introduce to create new phi arguments.  */
    2519                 :        282 :   basis = lookup_cand (c->basis);
    2520                 :        282 :   basis_name = gimple_assign_lhs (basis->cand_stmt);
    2521                 :            : 
    2522                 :            :   /* Create a new phi statement which will represent C's true basis
    2523                 :            :      after the transformation is complete.  */
    2524                 :        282 :   loc = gimple_location (c->cand_stmt);
    2525                 :        282 :   name = create_phi_basis (c, lookup_cand (c->def_phi)->cand_stmt,
    2526                 :            :                            basis_name, loc, KNOWN_STRIDE);
    2527                 :            : 
    2528                 :            :   /* Replace C with an add of the new basis phi and a constant.  */
    2529                 :        282 :   widest_int bump = c->index * wi::to_widest (c->stride);
    2530                 :            : 
    2531                 :        282 :   replace_mult_candidate (c, name, bump);
    2532                 :        282 : }
    2533                 :            : 
    2534                 :            : /* Recursive helper function for phi_add_costs.  SPREAD is a measure of
    2535                 :            :    how many PHI nodes we have visited at this point in the tree walk.  */
    2536                 :            : 
    2537                 :            : static int
    2538                 :       2746 : phi_add_costs_1 (gimple *phi, slsr_cand_t c, int one_add_cost, int *spread)
    2539                 :            : {
    2540                 :       2746 :   unsigned i;
    2541                 :       2746 :   int cost = 0;
    2542                 :       2746 :   slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
    2543                 :            : 
    2544                 :       2746 :   if (phi_cand->visited)
    2545                 :            :     return 0;
    2546                 :            : 
    2547                 :       2746 :   phi_cand->visited = 1;
    2548                 :       2746 :   (*spread)++;
    2549                 :            : 
    2550                 :            :   /* If we work our way back to a phi that isn't dominated by the hidden
    2551                 :            :      basis, this isn't a candidate for replacement.  Indicate this by
    2552                 :            :      returning an unreasonably high cost.  It's not easy to detect
    2553                 :            :      these situations when determining the basis, so we defer the
    2554                 :            :      decision until now.  */
    2555                 :       2746 :   basic_block phi_bb = gimple_bb (phi);
    2556                 :       2746 :   slsr_cand_t basis = lookup_cand (c->basis);
    2557                 :       2746 :   basic_block basis_bb = gimple_bb (basis->cand_stmt);
    2558                 :            : 
    2559                 :       2746 :   if (phi_bb == basis_bb || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb))
    2560                 :          0 :     return COST_INFINITE;
    2561                 :            : 
    2562                 :       5499 :   for (i = 0; i < gimple_phi_num_args (phi); i++)
    2563                 :            :     {
    2564                 :       2753 :       tree arg = gimple_phi_arg_def (phi, i);
    2565                 :            : 
    2566                 :       2753 :       if (arg != phi_cand->base_expr)
    2567                 :            :         {
    2568                 :       2751 :           gimple *arg_def = SSA_NAME_DEF_STMT (arg);
    2569                 :            : 
    2570                 :       2751 :           if (gimple_code (arg_def) == GIMPLE_PHI)
    2571                 :            :             {
    2572                 :          1 :               cost += phi_add_costs_1 (arg_def, c, one_add_cost, spread);
    2573                 :            : 
    2574                 :          1 :               if (cost >= COST_INFINITE || *spread > MAX_SPREAD)
    2575                 :            :                 return COST_INFINITE;
    2576                 :            :             }
    2577                 :            :           else
    2578                 :            :             {
    2579                 :       2750 :               slsr_cand_t arg_cand = base_cand_from_table (arg);
    2580                 :            : 
    2581                 :       5500 :               if (arg_cand->index != c->index)
    2582                 :       2663 :                 cost += one_add_cost;
    2583                 :            :             }
    2584                 :            :         }
    2585                 :            :     }
    2586                 :            : 
    2587                 :            :   return cost;
    2588                 :            : }
    2589                 :            : 
    2590                 :            : /* Compute the expected costs of inserting basis adjustments for
    2591                 :            :    candidate C with phi-definition PHI.  The cost of inserting 
    2592                 :            :    one adjustment is given by ONE_ADD_COST.  If PHI has arguments
    2593                 :            :    which are themselves phi results, recursively calculate costs
    2594                 :            :    for those phis as well.  */
    2595                 :            : 
    2596                 :            : static int
    2597                 :       2745 : phi_add_costs (gimple *phi, slsr_cand_t c, int one_add_cost)
    2598                 :            : {
    2599                 :       2745 :   int spread = 0;
    2600                 :       2745 :   int retval = phi_add_costs_1 (phi, c, one_add_cost, &spread);
    2601                 :       2745 :   clear_visited (as_a <gphi *> (phi));
    2602                 :       2745 :   return retval;
    2603                 :            : }
    2604                 :            : /* For candidate C, each sibling of candidate C, and each dependent of
    2605                 :            :    candidate C, determine whether the candidate is dependent upon a 
    2606                 :            :    phi that hides its basis.  If not, replace the candidate unconditionally.
    2607                 :            :    Otherwise, determine whether the cost of introducing compensation code
    2608                 :            :    for the candidate is offset by the gains from strength reduction.  If
    2609                 :            :    so, replace the candidate and introduce the compensation code.  */
    2610                 :            : 
    2611                 :            : static void
    2612                 :     869618 : replace_uncond_cands_and_profitable_phis (slsr_cand_t c)
    2613                 :            : {
    2614                 :     869618 :   if (phi_dependent_cand_p (c))
    2615                 :            :     {
    2616                 :            :       /* A multiply candidate with a stride of 1 is just an artifice
    2617                 :            :          of a copy or cast; there is no value in replacing it.  */
    2618                 :       5766 :       if (c->kind == CAND_MULT && wi::to_widest (c->stride) != 1)
    2619                 :            :         {
    2620                 :            :           /* A candidate dependent upon a phi will replace a multiply by 
    2621                 :            :              a constant with an add, and will insert at most one add for
    2622                 :            :              each phi argument.  Add these costs with the potential dead-code
    2623                 :            :              savings to determine profitability.  */
    2624                 :       2745 :           bool speed = optimize_bb_for_speed_p (gimple_bb (c->cand_stmt));
    2625                 :       2745 :           int mult_savings = stmt_cost (c->cand_stmt, speed);
    2626                 :       2745 :           gimple *phi = lookup_cand (c->def_phi)->cand_stmt;
    2627                 :       2745 :           tree phi_result = gimple_phi_result (phi);
    2628                 :       2745 :           int one_add_cost = add_cost (speed, 
    2629                 :       2745 :                                        TYPE_MODE (TREE_TYPE (phi_result)));
    2630                 :       2745 :           int add_costs = one_add_cost + phi_add_costs (phi, c, one_add_cost);
    2631                 :       2745 :           int cost = add_costs - mult_savings - c->dead_savings;
    2632                 :            : 
    2633                 :       2745 :           if (dump_file && (dump_flags & TDF_DETAILS))
    2634                 :            :             {
    2635                 :          0 :               fprintf (dump_file, "  Conditional candidate %d:\n", c->cand_num);
    2636                 :          0 :               fprintf (dump_file, "    add_costs = %d\n", add_costs);
    2637                 :          0 :               fprintf (dump_file, "    mult_savings = %d\n", mult_savings);
    2638                 :          0 :               fprintf (dump_file, "    dead_savings = %d\n", c->dead_savings);
    2639                 :          0 :               fprintf (dump_file, "    cost = %d\n", cost);
    2640                 :          0 :               if (cost <= COST_NEUTRAL)
    2641                 :          0 :                 fputs ("  Replacing...\n", dump_file);
    2642                 :            :               else
    2643                 :          0 :                 fputs ("  Not replaced.\n", dump_file);
    2644                 :            :             }
    2645                 :            : 
    2646                 :       2745 :           if (cost <= COST_NEUTRAL)
    2647                 :        282 :             replace_conditional_candidate (c);
    2648                 :            :         }
    2649                 :            :     }
    2650                 :            :   else
    2651                 :     863852 :     replace_unconditional_candidate (c);
    2652                 :            : 
    2653                 :     869618 :   if (c->sibling)
    2654                 :      25974 :     replace_uncond_cands_and_profitable_phis (lookup_cand (c->sibling));
    2655                 :            : 
    2656                 :     869618 :   if (c->dependent)
    2657                 :     462198 :     replace_uncond_cands_and_profitable_phis (lookup_cand (c->dependent));
    2658                 :     869618 : }
    2659                 :            : 
    2660                 :            : /* Count the number of candidates in the tree rooted at C that have
    2661                 :            :    not already been replaced under other interpretations.  */
    2662                 :            : 
    2663                 :            : static int
    2664                 :      57522 : count_candidates (slsr_cand_t c)
    2665                 :            : {
    2666                 :     136645 :   unsigned count = cand_already_replaced (c) ? 0 : 1;
    2667                 :            : 
    2668                 :     136645 :   if (c->sibling)
    2669                 :       2934 :     count += count_candidates (lookup_cand (c->sibling));
    2670                 :            : 
    2671                 :     136645 :   if (c->dependent)
    2672                 :      79123 :     count += count_candidates (lookup_cand (c->dependent));
    2673                 :            : 
    2674                 :      57522 :   return count;
    2675                 :            : }
    2676                 :            : 
    2677                 :            : /* Increase the count of INCREMENT by one in the increment vector.
    2678                 :            :    INCREMENT is associated with candidate C.  If INCREMENT is to be
    2679                 :            :    conditionally executed as part of a conditional candidate replacement,
    2680                 :            :    IS_PHI_ADJUST is true, otherwise false.  If an initializer
    2681                 :            :    T_0 = stride * I is provided by a candidate that dominates all
    2682                 :            :    candidates with the same increment, also record T_0 for subsequent use.  */
    2683                 :            : 
    2684                 :            : static void
    2685                 :     136761 : record_increment (slsr_cand_t c, widest_int increment, bool is_phi_adjust)
    2686                 :            : {
    2687                 :     136761 :   bool found = false;
    2688                 :     136761 :   unsigned i;
    2689                 :            : 
    2690                 :            :   /* Treat increments that differ only in sign as identical so as to
    2691                 :            :      share initializers, unless we are generating pointer arithmetic.  */
    2692                 :     267330 :   if (!address_arithmetic_p && wi::neg_p (increment))
    2693                 :       4951 :     increment = -increment;
    2694                 :            : 
    2695                 :     210602 :   for (i = 0; i < incr_vec_len; i++)
    2696                 :            :     {
    2697                 :     212079 :       if (incr_vec[i].incr == increment)
    2698                 :            :         {
    2699                 :      32435 :           incr_vec[i].count++;
    2700                 :      32435 :           found = true;
    2701                 :            : 
    2702                 :            :           /* If we previously recorded an initializer that doesn't
    2703                 :            :              dominate this candidate, it's not going to be useful to
    2704                 :            :              us after all.  */
    2705                 :      32435 :           if (incr_vec[i].initializer
    2706                 :      32435 :               && !dominated_by_p (CDI_DOMINATORS,
    2707                 :        873 :                                   gimple_bb (c->cand_stmt),
    2708                 :        873 :                                   incr_vec[i].init_bb))
    2709                 :            :             {
    2710                 :          0 :               incr_vec[i].initializer = NULL_TREE;
    2711                 :          0 :               incr_vec[i].init_bb = NULL;
    2712                 :            :             }
    2713                 :            :           
    2714                 :            :           break;
    2715                 :            :         }
    2716                 :            :     }
    2717                 :            : 
    2718                 :     104326 :   if (!found && incr_vec_len < MAX_INCR_VEC_LEN - 1)
    2719                 :            :     {
    2720                 :            :       /* The first time we see an increment, create the entry for it.
    2721                 :            :          If this is the root candidate which doesn't have a basis, set
    2722                 :            :          the count to zero.  We're only processing it so it can possibly
    2723                 :            :          provide an initializer for other candidates.  */
    2724                 :     104326 :       incr_vec[incr_vec_len].incr = increment;
    2725                 :     104326 :       incr_vec[incr_vec_len].count = c->basis || is_phi_adjust ? 1 : 0;
    2726                 :     104326 :       incr_vec[incr_vec_len].cost = COST_INFINITE;
    2727                 :            :       
    2728                 :            :       /* Optimistically record the first occurrence of this increment
    2729                 :            :          as providing an initializer (if it does); we will revise this
    2730                 :            :          opinion later if it doesn't dominate all other occurrences.
    2731                 :            :          Exception:  increments of 0, 1 never need initializers;
    2732                 :            :          and phi adjustments don't ever provide initializers.  */
    2733                 :     104326 :       if (c->kind == CAND_ADD
    2734                 :      97939 :           && !is_phi_adjust
    2735                 :     195484 :           && c->index == increment
    2736                 :      45675 :           && (increment > 1 || increment < 0)
    2737                 :     115315 :           && (gimple_assign_rhs_code (c->cand_stmt) == PLUS_EXPR
    2738                 :       2678 :               || gimple_assign_rhs_code (c->cand_stmt) == POINTER_PLUS_EXPR))
    2739                 :            :         {
    2740                 :      10219 :           tree t0 = NULL_TREE;
    2741                 :      10219 :           tree rhs1 = gimple_assign_rhs1 (c->cand_stmt);
    2742                 :      10219 :           tree rhs2 = gimple_assign_rhs2 (c->cand_stmt);
    2743                 :      10219 :           if (operand_equal_p (rhs1, c->base_expr, 0))
    2744                 :            :             t0 = rhs2;
    2745                 :       5693 :           else if (operand_equal_p (rhs2, c->base_expr, 0))
    2746                 :            :             t0 = rhs1;
    2747                 :      10153 :           if (t0
    2748                 :      10153 :               && SSA_NAME_DEF_STMT (t0)
    2749                 :      20306 :               && gimple_bb (SSA_NAME_DEF_STMT (t0)))
    2750                 :            :             {
    2751                 :      10153 :               incr_vec[incr_vec_len].initializer = t0;
    2752                 :      10153 :               incr_vec[incr_vec_len++].init_bb
    2753                 :      10153 :                 = gimple_bb (SSA_NAME_DEF_STMT (t0));
    2754                 :            :             }
    2755                 :            :           else
    2756                 :            :             {
    2757                 :         66 :               incr_vec[incr_vec_len].initializer = NULL_TREE;
    2758                 :         66 :               incr_vec[incr_vec_len++].init_bb = NULL;
    2759                 :            :             }
    2760                 :            :         }
    2761                 :            :       else
    2762                 :            :         {
    2763                 :      94107 :           incr_vec[incr_vec_len].initializer = NULL_TREE;
    2764                 :      94107 :           incr_vec[incr_vec_len++].init_bb = NULL;
    2765                 :            :         }
    2766                 :            :     }
    2767                 :     136761 : }
    2768                 :            : 
    2769                 :            : /* Recursive helper function for record_phi_increments.  */
    2770                 :            : 
    2771                 :            : static void
    2772                 :         99 : record_phi_increments_1 (slsr_cand_t basis, gimple *phi)
    2773                 :            : {
    2774                 :         99 :   unsigned i;
    2775                 :         99 :   slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
    2776                 :            :   
    2777                 :         99 :   if (phi_cand->visited)
    2778                 :            :     return;
    2779                 :         99 :   phi_cand->visited = 1;
    2780                 :            : 
    2781                 :        215 :   for (i = 0; i < gimple_phi_num_args (phi); i++)
    2782                 :            :     {
    2783                 :        116 :       tree arg = gimple_phi_arg_def (phi, i);
    2784                 :        116 :       gimple *arg_def = SSA_NAME_DEF_STMT (arg);
    2785                 :            : 
    2786                 :        116 :       if (gimple_code (arg_def) == GIMPLE_PHI)
    2787                 :          0 :         record_phi_increments_1 (basis, arg_def);
    2788                 :            :       else
    2789                 :            :         {
    2790                 :        116 :           widest_int diff;
    2791                 :            : 
    2792                 :        116 :           if (operand_equal_p (arg, phi_cand->base_expr, 0))
    2793                 :            :             {
    2794                 :          8 :               diff = -basis->index;
    2795                 :          8 :               record_increment (phi_cand, diff, PHI_ADJUST);
    2796                 :            :             }
    2797                 :            :           else
    2798                 :            :             {
    2799                 :        108 :               slsr_cand_t arg_cand = base_cand_from_table (arg);
    2800                 :        108 :               diff = arg_cand->index - basis->index;
    2801                 :        108 :               record_increment (arg_cand, diff, PHI_ADJUST);
    2802                 :            :             }
    2803                 :            :         }
    2804                 :            :     }
    2805                 :            : }
    2806                 :            : 
    2807                 :            : /* Given phi statement PHI that hides a candidate from its BASIS, find
    2808                 :            :    the increments along each incoming arc (recursively handling additional
    2809                 :            :    phis that may be present) and record them.  These increments are the
    2810                 :            :    difference in index between the index-adjusting statements and the
    2811                 :            :    index of the basis.  */
    2812                 :            : 
    2813                 :            : static void
    2814                 :         99 : record_phi_increments (slsr_cand_t basis, gimple *phi)
    2815                 :            : {
    2816                 :         99 :   record_phi_increments_1 (basis, phi);
    2817                 :         99 :   clear_visited (as_a <gphi *> (phi));
    2818                 :         99 : }
    2819                 :            : 
    2820                 :            : /* Determine how many times each unique increment occurs in the set
    2821                 :            :    of candidates rooted at C's parent, recording the data in the
    2822                 :            :    increment vector.  For each unique increment I, if an initializer
    2823                 :            :    T_0 = stride * I is provided by a candidate that dominates all
    2824                 :            :    candidates with the same increment, also record T_0 for subsequent
    2825                 :            :    use.  */
    2826                 :            : 
    2827                 :            : static void
    2828                 :      57522 : record_increments (slsr_cand_t c)
    2829                 :            : {
    2830                 :     136645 :   if (!cand_already_replaced (c))
    2831                 :            :     {
    2832                 :     136645 :       if (!phi_dependent_cand_p (c))
    2833                 :     136546 :         record_increment (c, cand_increment (c), NOT_PHI_ADJUST);
    2834                 :            :       else
    2835                 :            :         {
    2836                 :            :           /* A candidate with a basis hidden by a phi will have one
    2837                 :            :              increment for its relationship to the index represented by
    2838                 :            :              the phi, and potentially additional increments along each
    2839                 :            :              incoming edge.  For the root of the dependency tree (which
    2840                 :            :              has no basis), process just the initial index in case it has
    2841                 :            :              an initializer that can be used by subsequent candidates.  */
    2842                 :         99 :           record_increment (c, c->index, NOT_PHI_ADJUST);
    2843                 :            : 
    2844                 :         99 :           if (c->basis)
    2845                 :         99 :             record_phi_increments (lookup_cand (c->basis),
    2846                 :         99 :                                    lookup_cand (c->def_phi)->cand_stmt);
    2847                 :            :         }
    2848                 :            :     }
    2849                 :            : 
    2850                 :     136645 :   if (c->sibling)
    2851                 :       2934 :     record_increments (lookup_cand (c->sibling));
    2852                 :            : 
    2853                 :     136645 :   if (c->dependent)
    2854                 :      79123 :     record_increments (lookup_cand (c->dependent));
    2855                 :      57522 : }
    2856                 :            : 
    2857                 :            : /* Recursive helper function for phi_incr_cost.  */
    2858                 :            : 
    2859                 :            : static int
    2860                 :         44 : phi_incr_cost_1 (slsr_cand_t c, const widest_int &incr, gimple *phi,
    2861                 :            :                  int *savings)
    2862                 :            : {
    2863                 :         44 :   unsigned i;
    2864                 :         44 :   int cost = 0;
    2865                 :         44 :   slsr_cand_t basis = lookup_cand (c->basis);
    2866                 :         44 :   slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
    2867                 :            : 
    2868                 :         44 :   if (phi_cand->visited)
    2869                 :            :     return 0;
    2870                 :         44 :   phi_cand->visited = 1;
    2871                 :            : 
    2872                 :        109 :   for (i = 0; i < gimple_phi_num_args (phi); i++)
    2873                 :            :     {
    2874                 :         65 :       tree arg = gimple_phi_arg_def (phi, i);
    2875                 :         65 :       gimple *arg_def = SSA_NAME_DEF_STMT (arg);
    2876                 :            : 
    2877                 :         65 :       if (gimple_code (arg_def) == GIMPLE_PHI)
    2878                 :            :         {
    2879                 :          0 :           int feeding_savings = 0;
    2880                 :          0 :           tree feeding_var = gimple_phi_result (arg_def);
    2881                 :          0 :           cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings);
    2882                 :          0 :           if (uses_consumed_by_stmt (feeding_var, phi))
    2883                 :          0 :             *savings += feeding_savings;
    2884                 :            :         }
    2885                 :            :       else
    2886                 :            :         {
    2887                 :         65 :           widest_int diff;
    2888                 :         65 :           slsr_cand_t arg_cand;
    2889                 :            : 
    2890                 :            :           /* When the PHI argument is just a pass-through to the base
    2891                 :            :              expression of the hidden basis, the difference is zero minus
    2892                 :            :              the index of the basis.  There is no potential savings by
    2893                 :            :              eliminating a statement in this case.  */
    2894                 :         65 :           if (operand_equal_p (arg, phi_cand->base_expr, 0))
    2895                 :            :             {
    2896                 :          8 :               arg_cand = (slsr_cand_t)NULL;
    2897                 :          8 :               diff = -basis->index;
    2898                 :            :             }
    2899                 :            :           else
    2900                 :            :             {
    2901                 :         57 :               arg_cand = base_cand_from_table (arg);
    2902                 :         57 :               diff = arg_cand->index - basis->index;
    2903                 :            :             }
    2904                 :            :           
    2905                 :        166 :           if (incr == diff)
    2906                 :            :             {
    2907                 :         36 :               tree basis_lhs = gimple_assign_lhs (basis->cand_stmt);
    2908                 :         36 :               cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs)));
    2909                 :         36 :               if (arg_cand)
    2910                 :            :                 {
    2911                 :         36 :                   tree lhs = gimple_assign_lhs (arg_cand->cand_stmt);
    2912                 :         36 :                   if (uses_consumed_by_stmt (lhs, phi))
    2913                 :         16 :                     *savings += stmt_cost (arg_cand->cand_stmt, true);
    2914                 :            :                 }
    2915                 :            :             }
    2916                 :            :         }
    2917                 :            :     }
    2918                 :            : 
    2919                 :            :   return cost;
    2920                 :            : }
    2921                 :            : 
    2922                 :            : /* Add up and return the costs of introducing add statements that
    2923                 :            :    require the increment INCR on behalf of candidate C and phi
    2924                 :            :    statement PHI.  Accumulate into *SAVINGS the potential savings
    2925                 :            :    from removing existing statements that feed PHI and have no other
    2926                 :            :    uses.  */
    2927                 :            : 
    2928                 :            : static int
    2929                 :         44 : phi_incr_cost (slsr_cand_t c, const widest_int &incr, gimple *phi,
    2930                 :            :                int *savings)
    2931                 :            : {
    2932                 :         44 :   int retval = phi_incr_cost_1 (c, incr, phi, savings);
    2933                 :         44 :   clear_visited (as_a <gphi *> (phi));
    2934                 :         44 :   return retval;
    2935                 :            : }
    2936                 :            : 
    2937                 :            : /* Return the first candidate in the tree rooted at C that has not
    2938                 :            :    already been replaced, favoring siblings over dependents.  */
    2939                 :            : 
    2940                 :            : static slsr_cand_t
    2941                 :      54588 : unreplaced_cand_in_tree (slsr_cand_t c)
    2942                 :            : {
    2943                 :      54588 :   if (!cand_already_replaced (c))
    2944                 :            :     return c;
    2945                 :            : 
    2946                 :          0 :   if (c->sibling)
    2947                 :            :     {
    2948                 :          0 :       slsr_cand_t sib = unreplaced_cand_in_tree (lookup_cand (c->sibling));
    2949                 :          0 :       if (sib)
    2950                 :            :         return sib;
    2951                 :            :     }
    2952                 :            : 
    2953                 :          0 :   if (c->dependent)
    2954                 :            :     {
    2955                 :          0 :       slsr_cand_t dep = unreplaced_cand_in_tree (lookup_cand (c->dependent));
    2956                 :          0 :       if (dep)
    2957                 :          0 :         return dep;
    2958                 :            :     }
    2959                 :            : 
    2960                 :            :   return NULL;
    2961                 :            : }
    2962                 :            : 
    2963                 :            : /* Return TRUE if the candidates in the tree rooted at C should be
    2964                 :            :    optimized for speed, else FALSE.  We estimate this based on the block
    2965                 :            :    containing the most dominant candidate in the tree that has not yet
    2966                 :            :    been replaced.  */
    2967                 :            : 
    2968                 :            : static bool
    2969                 :      54588 : optimize_cands_for_speed_p (slsr_cand_t c)
    2970                 :            : {
    2971                 :      54588 :   slsr_cand_t c2 = unreplaced_cand_in_tree (c);
    2972                 :      54588 :   gcc_assert (c2);
    2973                 :      54588 :   return optimize_bb_for_speed_p (gimple_bb (c2->cand_stmt));
    2974                 :            : }
    2975                 :            : 
    2976                 :            : /* Add COST_IN to the lowest cost of any dependent path starting at
    2977                 :            :    candidate C or any of its siblings, counting only candidates along
    2978                 :            :    such paths with increment INCR.  Assume that replacing a candidate
    2979                 :            :    reduces cost by REPL_SAVINGS.  Also account for savings from any
    2980                 :            :    statements that would go dead.  If COUNT_PHIS is true, include
    2981                 :            :    costs of introducing feeding statements for conditional candidates.  */
    2982                 :            : 
    2983                 :            : static int
    2984                 :       4698 : lowest_cost_path (int cost_in, int repl_savings, slsr_cand_t c,
    2985                 :            :                   const widest_int &incr, bool count_phis)
    2986                 :            : {
    2987                 :       4698 :   int local_cost, sib_cost, savings = 0;
    2988                 :       4698 :   widest_int cand_incr = cand_abs_increment (c);
    2989                 :            : 
    2990                 :       4698 :   if (cand_already_replaced (c))
    2991                 :            :     local_cost = cost_in;
    2992                 :       9350 :   else if (incr == cand_incr)
    2993                 :       2744 :     local_cost = cost_in - repl_savings - c->dead_savings;
    2994                 :            :   else
    2995                 :       1954 :     local_cost = cost_in - c->dead_savings;
    2996                 :            : 
    2997                 :       4698 :   if (count_phis
    2998                 :        261 :       && phi_dependent_cand_p (c)
    2999                 :       4729 :       && !cand_already_replaced (c))
    3000                 :            :     {
    3001                 :         31 :       gimple *phi = lookup_cand (c->def_phi)->cand_stmt;
    3002                 :         31 :       local_cost += phi_incr_cost (c, incr, phi, &savings);
    3003                 :            : 
    3004                 :         31 :       if (uses_consumed_by_stmt (gimple_phi_result (phi), c->cand_stmt))
    3005                 :         11 :         local_cost -= savings;
    3006                 :            :     }
    3007                 :            : 
    3008                 :       4698 :   if (c->dependent)
    3009                 :       2513 :     local_cost = lowest_cost_path (local_cost, repl_savings, 
    3010                 :            :                                    lookup_cand (c->dependent), incr,
    3011                 :            :                                    count_phis);
    3012                 :            : 
    3013                 :       4698 :   if (c->sibling)
    3014                 :            :     {
    3015                 :          4 :       sib_cost = lowest_cost_path (cost_in, repl_savings,
    3016                 :            :                                    lookup_cand (c->sibling), incr,
    3017                 :            :                                    count_phis);
    3018                 :          4 :       local_cost = MIN (local_cost, sib_cost);
    3019                 :            :     }
    3020                 :            : 
    3021                 :       4698 :   return local_cost;
    3022                 :            : }
    3023                 :            : 
    3024                 :            : /* Compute the total savings that would accrue from all replacements
    3025                 :            :    in the candidate tree rooted at C, counting only candidates with
    3026                 :            :    increment INCR.  Assume that replacing a candidate reduces cost
    3027                 :            :    by REPL_SAVINGS.  Also account for savings from statements that
    3028                 :            :    would go dead.  */
    3029                 :            : 
    3030                 :            : static int
    3031                 :         45 : total_savings (int repl_savings, slsr_cand_t c, const widest_int &incr,
    3032                 :            :                bool count_phis)
    3033                 :            : {
    3034                 :         45 :   int savings = 0;
    3035                 :         45 :   widest_int cand_incr = cand_abs_increment (c);
    3036                 :            : 
    3037                 :         90 :   if (incr == cand_incr && !cand_already_replaced (c))
    3038                 :         28 :     savings += repl_savings + c->dead_savings;
    3039                 :            : 
    3040                 :         45 :   if (count_phis
    3041                 :         14 :       && phi_dependent_cand_p (c)
    3042                 :         58 :       && !cand_already_replaced (c))
    3043                 :            :     {
    3044                 :         13 :       int phi_savings = 0;
    3045                 :         13 :       gimple *phi = lookup_cand (c->def_phi)->cand_stmt;
    3046                 :         13 :       savings -= phi_incr_cost (c, incr, phi, &phi_savings);
    3047                 :            : 
    3048                 :         13 :       if (uses_consumed_by_stmt (gimple_phi_result (phi), c->cand_stmt))
    3049                 :          1 :         savings += phi_savings;
    3050                 :            :     }
    3051                 :            : 
    3052                 :         45 :   if (c->dependent)
    3053                 :         13 :     savings += total_savings (repl_savings, lookup_cand (c->dependent), incr,
    3054                 :            :                               count_phis);
    3055                 :            : 
    3056                 :         45 :   if (c->sibling)
    3057                 :          0 :     savings += total_savings (repl_savings, lookup_cand (c->sibling), incr,
    3058                 :            :                               count_phis);
    3059                 :            : 
    3060                 :         45 :   return savings;
    3061                 :            : }
    3062                 :            : 
    3063                 :            : /* Use target-specific costs to determine and record which increments
    3064                 :            :    in the current candidate tree are profitable to replace, assuming
    3065                 :            :    MODE and SPEED.  FIRST_DEP is the first dependent of the root of
    3066                 :            :    the candidate tree.
    3067                 :            : 
    3068                 :            :    One slight limitation here is that we don't account for the possible
    3069                 :            :    introduction of casts in some cases.  See replace_one_candidate for
    3070                 :            :    the cases where these are introduced.  This should probably be cleaned
    3071                 :            :    up sometime.  */
    3072                 :            : 
    3073                 :            : static void
    3074                 :      54588 : analyze_increments (slsr_cand_t first_dep, machine_mode mode, bool speed)
    3075                 :            : {
    3076                 :      54588 :   unsigned i;
    3077                 :            : 
    3078                 :     158914 :   for (i = 0; i < incr_vec_len; i++)
    3079                 :            :     {
    3080                 :     104326 :       HOST_WIDE_INT incr = incr_vec[i].incr.to_shwi ();
    3081                 :            : 
    3082                 :            :       /* If somehow this increment is bigger than a HWI, we won't
    3083                 :            :          be optimizing candidates that use it.  And if the increment
    3084                 :            :          has a count of zero, nothing will be done with it.  */
    3085                 :     104326 :       if (!wi::fits_shwi_p (incr_vec[i].incr) || !incr_vec[i].count)
    3086                 :      48946 :         incr_vec[i].cost = COST_INFINITE;
    3087                 :            : 
    3088                 :            :       /* Increments of 0, 1, and -1 are always profitable to replace,
    3089                 :            :          because they always replace a multiply or add with an add or
    3090                 :            :          copy, and may cause one or more existing instructions to go
    3091                 :            :          dead.  Exception:  -1 can't be assumed to be profitable for
    3092                 :            :          pointer addition.  */
    3093                 :      55380 :       else if (incr == 0
    3094                 :      55380 :                || incr == 1
    3095                 :       2250 :                || (incr == -1
    3096                 :          1 :                    && !POINTER_TYPE_P (first_dep->cand_type)))
    3097                 :      53130 :         incr_vec[i].cost = COST_NEUTRAL;
    3098                 :            : 
    3099                 :            :       /* If we need to add an initializer, give up if a cast from the
    3100                 :            :          candidate's type to its stride's type can lose precision.
    3101                 :            :          Note that this already takes into account that the stride may
    3102                 :            :          have been cast to a wider type, in which case this test won't
    3103                 :            :          fire.  Example:
    3104                 :            : 
    3105                 :            :            short int _1;
    3106                 :            :            _2 = (int) _1;
    3107                 :            :            _3 = _2 * 10;
    3108                 :            :            _4 = x + _3;    ADD: x + (10 * (int)_1) : int
    3109                 :            :            _5 = _2 * 15;
    3110                 :            :            _6 = x + _5;    ADD: x + (15 * (int)_1) : int
    3111                 :            : 
    3112                 :            :          Although the stride was a short int initially, the stride
    3113                 :            :          used in the analysis has been widened to an int, and such
    3114                 :            :          widening will be done in the initializer as well.  */
    3115                 :       2250 :       else if (!incr_vec[i].initializer
    3116                 :       1767 :                && TREE_CODE (first_dep->stride) != INTEGER_CST
    3117                 :       4017 :                && !legal_cast_p_1 (first_dep->stride_type,
    3118                 :       1767 :                                    TREE_TYPE (gimple_assign_lhs
    3119                 :            :                                               (first_dep->cand_stmt))))
    3120                 :         37 :         incr_vec[i].cost = COST_INFINITE;
    3121                 :            : 
    3122                 :            :       /* If we need to add an initializer, make sure we don't introduce
    3123                 :            :          a multiply by a pointer type, which can happen in certain cast
    3124                 :            :          scenarios.  */
    3125                 :       2213 :       else if (!incr_vec[i].initializer
    3126                 :       1730 :                && TREE_CODE (first_dep->stride) != INTEGER_CST
    3127                 :       1730 :                && POINTER_TYPE_P (first_dep->stride_type))
    3128                 :          0 :         incr_vec[i].cost = COST_INFINITE;
    3129                 :            : 
    3130                 :            :       /* For any other increment, if this is a multiply candidate, we
    3131                 :            :          must introduce a temporary T and initialize it with
    3132                 :            :          T_0 = stride * increment.  When optimizing for speed, walk the
    3133                 :            :          candidate tree to calculate the best cost reduction along any
    3134                 :            :          path; if it offsets the fixed cost of inserting the initializer,
    3135                 :            :          replacing the increment is profitable.  When optimizing for
    3136                 :            :          size, instead calculate the total cost reduction from replacing
    3137                 :            :          all candidates with this increment.  */
    3138                 :       2213 :       else if (first_dep->kind == CAND_MULT)
    3139                 :            :         {
    3140                 :         55 :           int cost = mult_by_coeff_cost (incr, mode, speed);
    3141                 :         55 :           int repl_savings;
    3142                 :            : 
    3143                 :         55 :           if (tree_fits_shwi_p (first_dep->stride))
    3144                 :            :             {
    3145                 :          0 :               HOST_WIDE_INT hwi_stride = tree_to_shwi (first_dep->stride);
    3146                 :          0 :               repl_savings = mult_by_coeff_cost (hwi_stride, mode, speed);
    3147                 :            :             }
    3148                 :            :           else
    3149                 :         55 :             repl_savings = mul_cost (speed, mode);
    3150                 :         55 :           repl_savings -= add_cost (speed, mode);
    3151                 :            : 
    3152                 :         55 :           if (speed)
    3153                 :         49 :             cost = lowest_cost_path (cost, repl_savings, first_dep,
    3154                 :         49 :                                      incr_vec[i].incr, COUNT_PHIS);
    3155                 :            :           else
    3156                 :          6 :             cost -= total_savings (repl_savings, first_dep, incr_vec[i].incr,
    3157                 :            :                                    COUNT_PHIS);
    3158                 :            : 
    3159                 :         55 :           incr_vec[i].cost = cost;
    3160                 :            :         }
    3161                 :            : 
    3162                 :            :       /* If this is an add candidate, the initializer may already
    3163                 :            :          exist, so only calculate the cost of the initializer if it
    3164                 :            :          doesn't.  We are replacing one add with another here, so the
    3165                 :            :          known replacement savings is zero.  We will account for removal
    3166                 :            :          of dead instructions in lowest_cost_path or total_savings.  */
    3167                 :            :       else
    3168                 :            :         {
    3169                 :       2158 :           int cost = 0;
    3170                 :       2158 :           if (!incr_vec[i].initializer)
    3171                 :       1675 :             cost = mult_by_coeff_cost (incr, mode, speed);
    3172                 :            : 
    3173                 :       2158 :           if (speed)
    3174                 :       2132 :             cost = lowest_cost_path (cost, 0, first_dep, incr_vec[i].incr,
    3175                 :            :                                      DONT_COUNT_PHIS);
    3176                 :            :           else
    3177                 :         26 :             cost -= total_savings (0, first_dep, incr_vec[i].incr,
    3178                 :            :                                    DONT_COUNT_PHIS);
    3179                 :            : 
    3180                 :       2158 :           incr_vec[i].cost = cost;
    3181                 :            :         }
    3182                 :            :     }
    3183                 :      54588 : }
    3184                 :            : 
    3185                 :            : /* Return the nearest common dominator of BB1 and BB2.  If the blocks
    3186                 :            :    are identical, return the earlier of C1 and C2 in *WHERE.  Otherwise,
    3187                 :            :    if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2,
    3188                 :            :    return C2 in *WHERE; and if the NCD matches neither, return NULL in
    3189                 :            :    *WHERE.  Note: It is possible for one of C1 and C2 to be NULL.  */
    3190                 :            : 
    3191                 :            : static basic_block
    3192                 :        826 : ncd_for_two_cands (basic_block bb1, basic_block bb2,
    3193                 :            :                    slsr_cand_t c1, slsr_cand_t c2, slsr_cand_t *where)
    3194                 :            : {
    3195                 :        826 :   basic_block ncd;
    3196                 :            : 
    3197                 :        826 :   if (!bb1)
    3198                 :            :     {
    3199                 :        627 :       *where = c2;
    3200                 :        627 :       return bb2;
    3201                 :            :     }
    3202                 :            : 
    3203                 :        199 :   if (!bb2)
    3204                 :            :     {
    3205                 :          0 :       *where = c1;
    3206                 :          0 :       return bb1;
    3207                 :            :     }
    3208                 :            : 
    3209                 :        199 :   ncd = nearest_common_dominator (CDI_DOMINATORS, bb1, bb2);
    3210                 :            :       
    3211                 :            :   /* If both candidates are in the same block, the earlier
    3212                 :            :      candidate wins.  */
    3213                 :        199 :   if (bb1 == ncd && bb2 == ncd)
    3214                 :            :     {
    3215                 :        158 :       if (!c1 || (c2 && c2->cand_num < c1->cand_num))
    3216                 :        158 :         *where = c2;
    3217                 :            :       else
    3218                 :          0 :         *where = c1;
    3219                 :            :     }
    3220                 :            : 
    3221                 :            :   /* Otherwise, if one of them produced a candidate in the
    3222                 :            :      dominator, that one wins.  */
    3223                 :         41 :   else if (bb1 == ncd)
    3224                 :          5 :     *where = c1;
    3225                 :            : 
    3226                 :         36 :   else if (bb2 == ncd)
    3227                 :         34 :     *where = c2;
    3228                 :            : 
    3229                 :            :   /* If neither matches the dominator, neither wins.  */
    3230                 :            :   else
    3231                 :          2 :     *where = NULL;
    3232                 :            : 
    3233                 :            :   return ncd;
    3234                 :            : }
    3235                 :            : 
    3236                 :            : /* Consider all candidates that feed PHI.  Find the nearest common
    3237                 :            :    dominator of those candidates requiring the given increment INCR.
    3238                 :            :    Further find and return the nearest common dominator of this result
    3239                 :            :    with block NCD.  If the returned block contains one or more of the
    3240                 :            :    candidates, return the earliest candidate in the block in *WHERE.  */
    3241                 :            : 
    3242                 :            : static basic_block
    3243                 :         13 : ncd_with_phi (slsr_cand_t c, const widest_int &incr, gphi *phi,
    3244                 :            :               basic_block ncd, slsr_cand_t *where)
    3245                 :            : {
    3246                 :         13 :   unsigned i;
    3247                 :         13 :   slsr_cand_t basis = lookup_cand (c->basis);
    3248                 :         13 :   slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
    3249                 :            : 
    3250                 :         40 :   for (i = 0; i < gimple_phi_num_args (phi); i++)
    3251                 :            :     {
    3252                 :         27 :       tree arg = gimple_phi_arg_def (phi, i);
    3253                 :         27 :       gimple *arg_def = SSA_NAME_DEF_STMT (arg);
    3254                 :            : 
    3255                 :         27 :       if (gimple_code (arg_def) == GIMPLE_PHI)
    3256                 :          0 :         ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd, where);
    3257                 :            :       else 
    3258                 :            :         {
    3259                 :         27 :           widest_int diff;
    3260                 :            : 
    3261                 :         27 :           if (operand_equal_p (arg, phi_cand->base_expr, 0))
    3262                 :          7 :             diff = -basis->index;
    3263                 :            :           else
    3264                 :            :             {
    3265                 :         20 :               slsr_cand_t arg_cand = base_cand_from_table (arg);
    3266                 :         20 :               diff = arg_cand->index - basis->index;
    3267                 :            :             }
    3268                 :            :           
    3269                 :         27 :           basic_block pred = gimple_phi_arg_edge (phi, i)->src;
    3270                 :            :           
    3271                 :         78 :           if ((incr == diff) || (!address_arithmetic_p && incr == -diff))
    3272                 :         18 :             ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where);
    3273                 :            :         }
    3274                 :            :     }
    3275                 :            : 
    3276                 :         13 :   return ncd;
    3277                 :            : }
    3278                 :            : 
    3279                 :            : /* Consider the candidate C together with any candidates that feed
    3280                 :            :    C's phi dependence (if any).  Find and return the nearest common
    3281                 :            :    dominator of those candidates requiring the given increment INCR.
    3282                 :            :    If the returned block contains one or more of the candidates,
    3283                 :            :    return the earliest candidate in the block in *WHERE.  */
    3284                 :            : 
    3285                 :            : static basic_block
    3286                 :       2083 : ncd_of_cand_and_phis (slsr_cand_t c, const widest_int &incr, slsr_cand_t *where)
    3287                 :            : {
    3288                 :       2083 :   basic_block ncd = NULL;
    3289                 :            : 
    3290                 :       4120 :   if (cand_abs_increment (c) == incr)
    3291                 :            :     {
    3292                 :        797 :       ncd = gimple_bb (c->cand_stmt);
    3293                 :        797 :       *where = c;
    3294                 :            :     }
    3295                 :            :   
    3296                 :       2083 :   if (phi_dependent_cand_p (c))
    3297                 :         13 :     ncd = ncd_with_phi (c, incr,
    3298                 :         13 :                         as_a <gphi *> (lookup_cand (c->def_phi)->cand_stmt),
    3299                 :            :                         ncd, where);
    3300                 :            : 
    3301                 :       2083 :   return ncd;
    3302                 :            : }
    3303                 :            : 
    3304                 :            : /* Consider all candidates in the tree rooted at C for which INCR
    3305                 :            :    represents the required increment of C relative to its basis.
    3306                 :            :    Find and return the basic block that most nearly dominates all
    3307                 :            :    such candidates.  If the returned block contains one or more of
    3308                 :            :    the candidates, return the earliest candidate in the block in
    3309                 :            :    *WHERE.  */
    3310                 :            : 
    3311                 :            : static basic_block
    3312                 :       2083 : nearest_common_dominator_for_cands (slsr_cand_t c, const widest_int &incr,
    3313                 :            :                                     slsr_cand_t *where)
    3314                 :            : {
    3315                 :       2083 :   basic_block sib_ncd = NULL, dep_ncd = NULL, this_ncd = NULL, ncd;
    3316                 :       2083 :   slsr_cand_t sib_where = NULL, dep_where = NULL, this_where = NULL, new_where;
    3317                 :            : 
    3318                 :            :   /* First find the NCD of all siblings and dependents.  */
    3319                 :       2083 :   if (c->sibling)
    3320                 :          1 :     sib_ncd = nearest_common_dominator_for_cands (lookup_cand (c->sibling),
    3321                 :            :                                                   incr, &sib_where);
    3322                 :       2083 :   if (c->dependent)
    3323                 :       1466 :     dep_ncd = nearest_common_dominator_for_cands (lookup_cand (c->dependent),
    3324                 :            :                                                   incr, &dep_where);
    3325                 :       2083 :   if (!sib_ncd && !dep_ncd)
    3326                 :            :     {
    3327                 :       1038 :       new_where = NULL;
    3328                 :       1038 :       ncd = NULL;
    3329                 :            :     }
    3330                 :       1045 :   else if (sib_ncd && !dep_ncd)
    3331                 :            :     {
    3332                 :          1 :       new_where = sib_where;
    3333                 :          1 :       ncd = sib_ncd;
    3334                 :            :     }
    3335                 :       1044 :   else if (dep_ncd && !sib_ncd)
    3336                 :            :     {
    3337                 :       1044 :       new_where = dep_where;
    3338                 :       1044 :       ncd = dep_ncd;
    3339                 :            :     }
    3340                 :            :   else
    3341                 :          0 :     ncd = ncd_for_two_cands (sib_ncd, dep_ncd, sib_where,
    3342                 :            :                              dep_where, &new_where);
    3343                 :            : 
    3344                 :            :   /* If the candidate's increment doesn't match the one we're interested
    3345                 :            :      in (and nor do any increments for feeding defs of a phi-dependence),
    3346                 :            :      then the result depends only on siblings and dependents.  */
    3347                 :       2083 :   this_ncd = ncd_of_cand_and_phis (c, incr, &this_where);
    3348                 :            : 
    3349                 :       2083 :   if (!this_ncd || cand_already_replaced (c))
    3350                 :            :     {
    3351                 :       1275 :       *where = new_where;
    3352                 :       1275 :       return ncd;
    3353                 :            :     }
    3354                 :            : 
    3355                 :            :   /* Otherwise, compare this candidate with the result from all siblings
    3356                 :            :      and dependents.  */
    3357                 :        808 :   ncd = ncd_for_two_cands (ncd, this_ncd, new_where, this_where, where);
    3358                 :            : 
    3359                 :        808 :   return ncd;
    3360                 :            : }
    3361                 :            : 
    3362                 :            : /* Return TRUE if the increment indexed by INDEX is profitable to replace.  */
    3363                 :            : 
    3364                 :            : static inline bool
    3365                 :     186490 : profitable_increment_p (unsigned index)
    3366                 :            : {
    3367                 :     186490 :   return (incr_vec[index].cost <= COST_NEUTRAL);
    3368                 :            : }
    3369                 :            : 
    3370                 :            : /* For each profitable increment in the increment vector not equal to
    3371                 :            :    0 or 1 (or -1, for non-pointer arithmetic), find the nearest common
    3372                 :            :    dominator of all statements in the candidate chain rooted at C
    3373                 :            :    that require that increment, and insert an initializer
    3374                 :            :    T_0 = stride * increment at that location.  Record T_0 with the
    3375                 :            :    increment record.  */
    3376                 :            : 
    3377                 :            : static void
    3378                 :      54588 : insert_initializers (slsr_cand_t c)
    3379                 :            : {
    3380                 :      54588 :   unsigned i;
    3381                 :            : 
    3382                 :     158914 :   for (i = 0; i < incr_vec_len; i++)
    3383                 :            :     {
    3384                 :     104326 :       basic_block bb;
    3385                 :     104326 :       slsr_cand_t where = NULL;
    3386                 :     104326 :       gassign *init_stmt;
    3387                 :     104326 :       gassign *cast_stmt = NULL;
    3388                 :     104326 :       tree new_name, incr_tree, init_stride;
    3389                 :     104326 :       widest_int incr = incr_vec[i].incr;
    3390                 :            : 
    3391                 :     207553 :       if (!profitable_increment_p (i)
    3392                 :      54229 :           || incr == 1
    3393                 :      51918 :           || (incr == -1
    3394                 :          0 :               && (!POINTER_TYPE_P (lookup_cand (c->basis)->cand_type)))
    3395                 :     156244 :           || incr == 0)
    3396                 :     103710 :         continue;
    3397                 :            : 
    3398                 :            :       /* We may have already identified an existing initializer that
    3399                 :            :          will suffice.  */
    3400                 :       1099 :       if (incr_vec[i].initializer)
    3401                 :            :         {
    3402                 :        483 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3403                 :            :             {
    3404                 :          0 :               fputs ("Using existing initializer: ", dump_file);
    3405                 :          0 :               print_gimple_stmt (dump_file,
    3406                 :          0 :                                  SSA_NAME_DEF_STMT (incr_vec[i].initializer),
    3407                 :            :                                  0, TDF_NONE);
    3408                 :            :             }
    3409                 :        483 :           continue;
    3410                 :            :         }
    3411                 :            : 
    3412                 :            :       /* Find the block that most closely dominates all candidates
    3413                 :            :          with this increment.  If there is at least one candidate in
    3414                 :            :          that block, the earliest one will be returned in WHERE.  */
    3415                 :        616 :       bb = nearest_common_dominator_for_cands (c, incr, &where);
    3416                 :            : 
    3417                 :            :       /* If the NCD is not dominated by the block containing the
    3418                 :            :          definition of the stride, we can't legally insert a
    3419                 :            :          single initializer.  Mark the increment as unprofitable
    3420                 :            :          so we don't make any replacements.  FIXME: Multiple
    3421                 :            :          initializers could be placed with more analysis.  */
    3422                 :        616 :       gimple *stride_def = SSA_NAME_DEF_STMT (c->stride);
    3423                 :        616 :       basic_block stride_bb = gimple_bb (stride_def);
    3424                 :            : 
    3425                 :        616 :       if (stride_bb && !dominated_by_p (CDI_DOMINATORS, bb, stride_bb))
    3426                 :            :         {
    3427                 :          0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3428                 :          0 :             fprintf (dump_file,
    3429                 :            :                      "Initializer #%d cannot be legally placed\n", i);
    3430                 :          0 :           incr_vec[i].cost = COST_INFINITE;
    3431                 :          0 :           continue;
    3432                 :            :         }
    3433                 :            : 
    3434                 :            :       /* If the nominal stride has a different type than the recorded
    3435                 :            :          stride type, build a cast from the nominal stride to that type.  */
    3436                 :        616 :       if (!types_compatible_p (TREE_TYPE (c->stride), c->stride_type))
    3437                 :            :         {
    3438                 :        553 :           init_stride = make_temp_ssa_name (c->stride_type, NULL, "slsr");
    3439                 :        553 :           cast_stmt = gimple_build_assign (init_stride, NOP_EXPR, c->stride);
    3440                 :            :         }
    3441                 :            :       else
    3442                 :         63 :         init_stride = c->stride;
    3443                 :            : 
    3444                 :            :       /* Create a new SSA name to hold the initializer's value.  */
    3445                 :        616 :       new_name = make_temp_ssa_name (c->stride_type, NULL, "slsr");
    3446                 :        616 :       incr_vec[i].initializer = new_name;
    3447                 :            : 
    3448                 :            :       /* Create the initializer and insert it in the latest possible
    3449                 :            :          dominating position.  */
    3450                 :        616 :       incr_tree = wide_int_to_tree (c->stride_type, incr);
    3451                 :        616 :       init_stmt = gimple_build_assign (new_name, MULT_EXPR,
    3452                 :            :                                        init_stride, incr_tree);
    3453                 :        616 :       if (where)
    3454                 :            :         {
    3455                 :        605 :           gimple_stmt_iterator gsi = gsi_for_stmt (where->cand_stmt);
    3456                 :        605 :           location_t loc = gimple_location (where->cand_stmt);
    3457                 :            : 
    3458                 :        605 :           if (cast_stmt)
    3459                 :            :             {
    3460                 :        553 :               gsi_insert_before (&gsi, cast_stmt, GSI_SAME_STMT);
    3461                 :        553 :               gimple_set_location (cast_stmt, loc);
    3462                 :            :             }
    3463                 :            : 
    3464                 :        605 :           gsi_insert_before (&gsi, init_stmt, GSI_SAME_STMT);
    3465                 :        605 :           gimple_set_location (init_stmt, loc);
    3466                 :            :         }
    3467                 :            :       else
    3468                 :            :         {
    3469                 :         11 :           gimple_stmt_iterator gsi = gsi_last_bb (bb);
    3470                 :         11 :           gimple *basis_stmt = lookup_cand (c->basis)->cand_stmt;
    3471                 :         11 :           location_t loc = gimple_location (basis_stmt);
    3472                 :            : 
    3473                 :         11 :           if (!gsi_end_p (gsi) && stmt_ends_bb_p (gsi_stmt (gsi)))
    3474                 :            :             {
    3475                 :         10 :               if (cast_stmt)
    3476                 :            :                 {
    3477                 :          0 :                   gsi_insert_before (&gsi, cast_stmt, GSI_SAME_STMT);
    3478                 :          0 :                   gimple_set_location (cast_stmt, loc);
    3479                 :            :                 }
    3480                 :         10 :               gsi_insert_before (&gsi, init_stmt, GSI_SAME_STMT);
    3481                 :            :             }
    3482                 :            :           else
    3483                 :            :             {
    3484                 :          1 :               if (cast_stmt)
    3485                 :            :                 {
    3486                 :          0 :                   gsi_insert_after (&gsi, cast_stmt, GSI_NEW_STMT);
    3487                 :          0 :                   gimple_set_location (cast_stmt, loc);
    3488                 :            :                 }
    3489                 :          1 :               gsi_insert_after (&gsi, init_stmt, GSI_NEW_STMT);
    3490                 :            :             }
    3491                 :            : 
    3492                 :         11 :           gimple_set_location (init_stmt, gimple_location (basis_stmt));
    3493                 :            :         }
    3494                 :            : 
    3495                 :        616 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3496                 :            :         {
    3497                 :          0 :           if (cast_stmt)
    3498                 :            :             {
    3499                 :          0 :               fputs ("Inserting stride cast: ", dump_file);
    3500                 :          0 :               print_gimple_stmt (dump_file, cast_stmt, 0);
    3501                 :            :             }
    3502                 :          0 :           fputs ("Inserting initializer: ", dump_file);
    3503                 :          0 :           print_gimple_stmt (dump_file, init_stmt, 0);
    3504                 :            :         }
    3505                 :            :     }
    3506                 :      54588 : }
    3507                 :            : 
    3508                 :            : /* Recursive helper function for all_phi_incrs_profitable.  */
    3509                 :            : 
    3510                 :            : static bool
    3511                 :         93 : all_phi_incrs_profitable_1 (slsr_cand_t c, gphi *phi, int *spread)
    3512                 :            : {
    3513                 :         93 :   unsigned i;
    3514                 :         93 :   slsr_cand_t basis = lookup_cand (c->basis);
    3515                 :         93 :   slsr_cand_t phi_cand = *stmt_cand_map->get (phi);
    3516                 :            : 
    3517                 :         93 :   if (phi_cand->visited)
    3518                 :            :     return true;
    3519                 :            : 
    3520                 :         93 :   phi_cand->visited = 1;
    3521                 :         93 :   (*spread)++;
    3522                 :            : 
    3523                 :            :   /* If the basis doesn't dominate the PHI (including when the PHI is
    3524                 :            :      in the same block as the basis), we won't be able to create a PHI
    3525                 :            :      using the basis here.  */
    3526                 :         93 :   basic_block basis_bb = gimple_bb (basis->cand_stmt);
    3527                 :         93 :   basic_block phi_bb = gimple_bb (phi);
    3528                 :            : 
    3529                 :         93 :   if (phi_bb == basis_bb
    3530                 :         93 :       || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb))
    3531                 :          0 :     return false;
    3532                 :            : 
    3533                 :        172 :   for (i = 0; i < gimple_phi_num_args (phi); i++)
    3534                 :            :     {
    3535                 :            :       /* If the PHI arg resides in a block not dominated by the basis,
    3536                 :            :          we won't be able to create a PHI using the basis here.  */
    3537                 :        107 :       basic_block pred_bb = gimple_phi_arg_edge (phi, i)->src;
    3538                 :            : 
    3539                 :        107 :       if (!dominated_by_p (CDI_DOMINATORS, pred_bb, basis_bb))
    3540                 :            :         return false;
    3541                 :            : 
    3542                 :        107 :       tree arg = gimple_phi_arg_def (phi, i);
    3543                 :        107 :       gimple *arg_def = SSA_NAME_DEF_STMT (arg);
    3544                 :            : 
    3545                 :        107 :       if (gimple_code (arg_def) == GIMPLE_PHI)
    3546                 :            :         {
    3547                 :          0 :           if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def), spread)
    3548                 :          0 :               || *spread > MAX_SPREAD)
    3549                 :            :             return false;
    3550                 :            :         }
    3551                 :            :       else
    3552                 :            :         {
    3553                 :        107 :           int j;
    3554                 :        107 :           widest_int increment;
    3555                 :            : 
    3556                 :        107 :           if (operand_equal_p (arg, phi_cand->base_expr, 0))
    3557                 :          8 :             increment = -basis->index;
    3558                 :            :           else
    3559                 :            :             {
    3560                 :         99 :               slsr_cand_t arg_cand = base_cand_from_table (arg);
    3561                 :         99 :               increment = arg_cand->index - basis->index;
    3562                 :            :             }
    3563                 :            : 
    3564                 :        214 :           if (!address_arithmetic_p && wi::neg_p (increment))
    3565                 :         13 :             increment = -increment;
    3566                 :            : 
    3567                 :        107 :           j = incr_vec_index (increment);
    3568                 :            : 
    3569                 :        107 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3570                 :            :             {
    3571                 :          0 :               fprintf (dump_file, "  Conditional candidate %d, phi: ",
    3572                 :            :                        c->cand_num);
    3573                 :          0 :               print_gimple_stmt (dump_file, phi, 0);
    3574                 :          0 :               fputs ("    increment: ", dump_file);
    3575                 :          0 :               print_decs (increment, dump_file);
    3576                 :          0 :               if (j < 0)
    3577                 :          0 :                 fprintf (dump_file,
    3578                 :            :                          "\n  Not replaced; incr_vec overflow.\n");
    3579                 :            :               else {
    3580                 :          0 :                 fprintf (dump_file, "\n    cost: %d\n", incr_vec[j].cost);
    3581                 :          0 :                 if (profitable_increment_p (j))
    3582                 :          0 :                   fputs ("  Replacing...\n", dump_file);
    3583                 :            :                 else
    3584                 :          0 :                   fputs ("  Not replaced.\n", dump_file);
    3585                 :            :               }
    3586                 :            :             }
    3587                 :            : 
    3588                 :        107 :           if (j < 0 || !profitable_increment_p (j))
    3589                 :         28 :             return false;
    3590                 :            :         }
    3591                 :            :     }
    3592                 :            : 
    3593                 :            :   return true;
    3594                 :            : }
    3595                 :            :   
    3596                 :            : /* Return TRUE iff all required increments for candidates feeding PHI
    3597                 :            :    are profitable (and legal!) to replace on behalf of candidate C.  */
    3598                 :            : 
    3599                 :            : static bool
    3600                 :         93 : all_phi_incrs_profitable (slsr_cand_t c, gphi *phi)
    3601                 :            : {
    3602                 :         93 :   int spread = 0;
    3603                 :          0 :   bool retval = all_phi_incrs_profitable_1 (c, phi, &spread);
    3604                 :         93 :   clear_visited (phi);
    3605                 :         93 :   return retval;
    3606                 :            : }
    3607                 :            : 
    3608                 :            : /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of
    3609                 :            :    type TO_TYPE, and insert it in front of the statement represented
    3610                 :            :    by candidate C.  Use *NEW_VAR to create the new SSA name.  Return
    3611                 :            :    the new SSA name.  */
    3612                 :            : 
    3613                 :            : static tree
    3614                 :       1700 : introduce_cast_before_cand (slsr_cand_t c, tree to_type, tree from_expr)
    3615                 :            : {
    3616                 :       1700 :   tree cast_lhs;
    3617                 :       1700 :   gassign *cast_stmt;
    3618                 :       1700 :   gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
    3619                 :            : 
    3620                 :       1700 :   cast_lhs = make_temp_ssa_name (to_type, NULL, "slsr");
    3621                 :       1700 :   cast_stmt = gimple_build_assign (cast_lhs, NOP_EXPR, from_expr);
    3622                 :       1700 :   gimple_set_location (cast_stmt, gimple_location (c->cand_stmt));
    3623                 :       1700 :   gsi_insert_before (&gsi, cast_stmt, GSI_SAME_STMT);
    3624                 :            : 
    3625                 :       1700 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3626                 :            :     {
    3627                 :          0 :       fputs ("  Inserting: ", dump_file);
    3628                 :          0 :       print_gimple_stmt (dump_file, cast_stmt, 0);
    3629                 :            :     }
    3630                 :            : 
    3631                 :       1700 :   return cast_lhs;
    3632                 :            : }
    3633                 :            : 
    3634                 :            : /* Replace the RHS of the statement represented by candidate C with 
    3635                 :            :    NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't
    3636                 :            :    leave C unchanged or just interchange its operands.  The original
    3637                 :            :    operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2.
    3638                 :            :    If the replacement was made and we are doing a details dump,
    3639                 :            :    return the revised statement, else NULL.  */
    3640                 :            : 
    3641                 :            : static gimple *
    3642                 :       5698 : replace_rhs_if_not_dup (enum tree_code new_code, tree new_rhs1, tree new_rhs2,
    3643                 :            :                         enum tree_code old_code, tree old_rhs1, tree old_rhs2,
    3644                 :            :                         slsr_cand_t c)
    3645                 :            : {
    3646                 :       5698 :   if (new_code != old_code
    3647                 :       5698 :       || ((!operand_equal_p (new_rhs1, old_rhs1, 0)
    3648                 :          0 :            || !operand_equal_p (new_rhs2, old_rhs2, 0))
    3649                 :       3418 :           && (!operand_equal_p (new_rhs1, old_rhs2, 0)
    3650                 :          0 :               || !operand_equal_p (new_rhs2, old_rhs1, 0))))
    3651                 :            :     {
    3652                 :       5698 :       gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
    3653                 :       5698 :       slsr_cand_t cc = lookup_cand (c->first_interp);
    3654                 :       5698 :       gimple_assign_set_rhs_with_ops (&gsi, new_code, new_rhs1, new_rhs2);
    3655                 :       5698 :       update_stmt (gsi_stmt (gsi));
    3656                 :      16370 :       while (cc)
    3657                 :            :         {
    3658                 :      10672 :           cc->cand_stmt = gsi_stmt (gsi);
    3659                 :      10672 :           cc = lookup_cand (cc->next_interp);
    3660                 :            :         }
    3661                 :            : 
    3662                 :       5698 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3663                 :          0 :         return gsi_stmt (gsi);
    3664                 :            :     }
    3665                 :            : 
    3666                 :          0 :   else if (dump_file && (dump_flags & TDF_DETAILS))
    3667                 :          0 :     fputs ("  (duplicate, not actually replacing)\n", dump_file);
    3668                 :            : 
    3669                 :            :   return NULL;
    3670                 :            : }
    3671                 :            : 
    3672                 :            : /* Strength-reduce the statement represented by candidate C by replacing
    3673                 :            :    it with an equivalent addition or subtraction.  I is the index into
    3674                 :            :    the increment vector identifying C's increment.  NEW_VAR is used to
    3675                 :            :    create a new SSA name if a cast needs to be introduced.  BASIS_NAME
    3676                 :            :    is the rhs1 to use in creating the add/subtract.  */
    3677                 :            : 
    3678                 :            : static void
    3679                 :      16805 : replace_one_candidate (slsr_cand_t c, unsigned i, tree basis_name)
    3680                 :            : {
    3681                 :      16805 :   gimple *stmt_to_print = NULL;
    3682                 :      16805 :   tree orig_rhs1, orig_rhs2;
    3683                 :      16805 :   tree rhs2;
    3684                 :      16805 :   enum tree_code orig_code, repl_code;
    3685                 :      16805 :   widest_int cand_incr;
    3686                 :            : 
    3687                 :      16805 :   orig_code = gimple_assign_rhs_code (c->cand_stmt);
    3688                 :      16805 :   orig_rhs1 = gimple_assign_rhs1 (c->cand_stmt);
    3689                 :      16805 :   orig_rhs2 = gimple_assign_rhs2 (c->cand_stmt);
    3690                 :      16805 :   cand_incr = cand_increment (c);
    3691                 :            : 
    3692                 :            :   /* If orig_rhs2 is NULL, we have already replaced this in situ with
    3693                 :            :      a copy statement under another interpretation.  */
    3694                 :      16805 :   if (!orig_rhs2)
    3695                 :          0 :     return;
    3696                 :            : 
    3697                 :      16805 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3698                 :            :     {
    3699                 :          0 :       fputs ("Replacing: ", dump_file);
    3700                 :          0 :       print_gimple_stmt (dump_file, c->cand_stmt, 0);
    3701                 :          0 :       stmt_to_print = c->cand_stmt;
    3702                 :            :     }
    3703                 :            : 
    3704                 :      16805 :   if (address_arithmetic_p)
    3705                 :            :     repl_code = POINTER_PLUS_EXPR;
    3706                 :            :   else
    3707                 :      13494 :     repl_code = PLUS_EXPR;
    3708                 :            : 
    3709                 :            :   /* If the increment has an initializer T_0, replace the candidate
    3710                 :            :      statement with an add of the basis name and the initializer.  */
    3711                 :      16805 :   if (incr_vec[i].initializer)
    3712                 :            :     {
    3713                 :       1554 :       tree init_type = TREE_TYPE (incr_vec[i].initializer);
    3714                 :       1554 :       tree orig_type = TREE_TYPE (orig_rhs2);
    3715                 :            : 
    3716                 :       1554 :       if (types_compatible_p (orig_type, init_type))
    3717                 :       1554 :         rhs2 = incr_vec[i].initializer;
    3718                 :            :       else
    3719                 :          0 :         rhs2 = introduce_cast_before_cand (c, orig_type,
    3720                 :          0 :                                            incr_vec[i].initializer);
    3721                 :            : 
    3722                 :       3108 :       if (incr_vec[i].incr != cand_incr)
    3723                 :            :         {
    3724                 :        337 :           gcc_assert (repl_code == PLUS_EXPR);
    3725                 :            :           repl_code = MINUS_EXPR;
    3726                 :            :         }
    3727                 :            : 
    3728                 :       1554 :       stmt_to_print = replace_rhs_if_not_dup (repl_code, basis_name, rhs2,
    3729                 :            :                                               orig_code, orig_rhs1, orig_rhs2,
    3730                 :            :                                               c);
    3731                 :            :     }
    3732                 :            : 
    3733                 :            :   /* Otherwise, the increment is one of -1, 0, and 1.  Replace
    3734                 :            :      with a subtract of the stride from the basis name, a copy
    3735                 :            :      from the basis name, or an add of the stride to the basis
    3736                 :            :      name, respectively.  It may be necessary to introduce a
    3737                 :            :      cast (or reuse an existing cast).  */
    3738                 :      15251 :   else if (cand_incr == 1)
    3739                 :            :     {
    3740                 :       4144 :       tree stride_type = TREE_TYPE (c->stride);
    3741                 :       4144 :       tree orig_type = TREE_TYPE (orig_rhs2);
    3742                 :            :       
    3743                 :       4144 :       if (types_compatible_p (orig_type, stride_type))
    3744                 :       2582 :         rhs2 = c->stride;
    3745                 :            :       else
    3746                 :       1562 :         rhs2 = introduce_cast_before_cand (c, orig_type, c->stride);
    3747                 :            :       
    3748                 :       4144 :       stmt_to_print = replace_rhs_if_not_dup (repl_code, basis_name, rhs2,
    3749                 :            :                                               orig_code, orig_rhs1, orig_rhs2,
    3750                 :            :                                               c);
    3751                 :            :     }
    3752                 :            : 
    3753                 :      11107 :   else if (cand_incr == -1)
    3754                 :            :     {
    3755                 :        306 :       tree stride_type = TREE_TYPE (c->stride);
    3756                 :        306 :       tree orig_type = TREE_TYPE (orig_rhs2);
    3757                 :        306 :       gcc_assert (repl_code != POINTER_PLUS_EXPR);
    3758                 :            :       
    3759                 :        306 :       if (types_compatible_p (orig_type, stride_type))
    3760                 :        168 :         rhs2 = c->stride;
    3761                 :            :       else
    3762                 :        138 :         rhs2 = introduce_cast_before_cand (c, orig_type, c->stride);
    3763                 :            :       
    3764                 :        306 :       if (orig_code != MINUS_EXPR
    3765                 :         48 :           || !operand_equal_p (basis_name, orig_rhs1, 0)
    3766                 :        306 :           || !operand_equal_p (rhs2, orig_rhs2, 0))
    3767                 :            :         {
    3768                 :        306 :           gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
    3769                 :        306 :           slsr_cand_t cc = lookup_cand (c->first_interp);
    3770                 :        306 :           gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, basis_name, rhs2);
    3771                 :        306 :           update_stmt (gsi_stmt (gsi));
    3772                 :        870 :           while (cc)
    3773                 :            :             {
    3774                 :        564 :               cc->cand_stmt = gsi_stmt (gsi);
    3775                 :        564 :               cc = lookup_cand (cc->next_interp);
    3776                 :            :             }
    3777                 :            : 
    3778                 :        306 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3779                 :          0 :             stmt_to_print = gsi_stmt (gsi);
    3780                 :            :         }
    3781                 :          0 :       else if (dump_file && (dump_flags & TDF_DETAILS))
    3782                 :          0 :         fputs ("  (duplicate, not actually replacing)\n", dump_file);
    3783                 :            :     }
    3784                 :            : 
    3785                 :      10801 :   else if (cand_incr == 0)
    3786                 :            :     {
    3787                 :      10801 :       tree lhs = gimple_assign_lhs (c->cand_stmt);
    3788                 :      10801 :       tree lhs_type = TREE_TYPE (lhs);
    3789                 :      10801 :       tree basis_type = TREE_TYPE (basis_name);
    3790                 :            :       
    3791                 :      10801 :       if (types_compatible_p (lhs_type, basis_type))
    3792                 :            :         {
    3793                 :      10801 :           gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
    3794                 :      10801 :           gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
    3795                 :      10801 :           slsr_cand_t cc = lookup_cand (c->first_interp);
    3796                 :      10801 :           gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
    3797                 :      10801 :           gsi_replace (&gsi, copy_stmt, false);
    3798                 :      29038 :           while (cc)
    3799                 :            :             {
    3800                 :      18237 :               cc->cand_stmt = copy_stmt;
    3801                 :      18237 :               cc = lookup_cand (cc->next_interp);
    3802                 :            :             }
    3803                 :            : 
    3804                 :      10801 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3805                 :            :             stmt_to_print = copy_stmt;
    3806                 :            :         }
    3807                 :            :       else
    3808                 :            :         {
    3809                 :          0 :           gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
    3810                 :          0 :           gassign *cast_stmt = gimple_build_assign (lhs, NOP_EXPR, basis_name);
    3811                 :          0 :           slsr_cand_t cc = lookup_cand (c->first_interp);
    3812                 :          0 :           gimple_set_location (cast_stmt, gimple_location (c->cand_stmt));
    3813                 :          0 :           gsi_replace (&gsi, cast_stmt, false);
    3814                 :          0 :           while (cc)
    3815                 :            :             {
    3816                 :          0 :               cc->cand_stmt = cast_stmt;
    3817                 :          0 :               cc = lookup_cand (cc->next_interp);
    3818                 :            :             }
    3819                 :            : 
    3820                 :          0 :           if (dump_file && (dump_flags & TDF_DETAILS))
    3821                 :            :             stmt_to_print = cast_stmt;
    3822                 :            :         }
    3823                 :            :     }
    3824                 :            :   else
    3825                 :          0 :     gcc_unreachable ();
    3826                 :            :   
    3827                 :      16805 :   if (dump_file && (dump_flags & TDF_DETAILS) && stmt_to_print)
    3828                 :            :     {
    3829                 :          0 :       fputs ("With: ", dump_file);
    3830                 :          0 :       print_gimple_stmt (dump_file, stmt_to_print, 0);
    3831                 :          0 :       fputs ("\n", dump_file);
    3832                 :            :     }
    3833                 :            : }
    3834                 :            : 
    3835                 :            : /* For each candidate in the tree rooted at C, replace it with
    3836                 :            :    an increment if such has been shown to be profitable.  */
    3837                 :            : 
    3838                 :            : static void
    3839                 :      82057 : replace_profitable_candidates (slsr_cand_t c)
    3840                 :            : {
    3841                 :      82057 :   if (!cand_already_replaced (c))
    3842                 :            :     {
    3843                 :      82057 :       widest_int increment = cand_abs_increment (c);
    3844                 :      82057 :       enum tree_code orig_code = gimple_assign_rhs_code (c->cand_stmt);
    3845                 :      82057 :       int i;
    3846                 :            : 
    3847                 :      82057 :       i = incr_vec_index (increment);
    3848                 :            : 
    3849                 :            :       /* Only process profitable increments.  Nothing useful can be done
    3850                 :            :          to a cast or copy.  */
    3851                 :      82057 :       if (i >= 0
    3852                 :      82057 :           && profitable_increment_p (i) 
    3853                 :      80869 :           && orig_code != SSA_NAME
    3854                 :     124641 :           && !CONVERT_EXPR_CODE_P (orig_code))
    3855                 :            :         {
    3856                 :      16833 :           if (phi_dependent_cand_p (c))
    3857                 :            :             {
    3858                 :         93 :               gphi *phi = as_a <gphi *> (lookup_cand (c->def_phi)->cand_stmt);
    3859                 :            : 
    3860                 :        186 :               if (all_phi_incrs_profitable (c, phi))
    3861                 :            :                 {
    3862                 :            :                   /* Look up the LHS SSA name from C's basis.  This will be 
    3863                 :            :                      the RHS1 of the adds we will introduce to create new
    3864                 :            :                      phi arguments.  */
    3865                 :         65 :                   slsr_cand_t basis = lookup_cand (c->basis);
    3866                 :         65 :                   tree basis_name = gimple_assign_lhs (basis->cand_stmt);
    3867                 :            : 
    3868                 :            :                   /* Create a new phi statement that will represent C's true
    3869                 :            :                      basis after the transformation is complete.  */
    3870                 :         65 :                   location_t loc = gimple_location (c->cand_stmt);
    3871                 :         65 :                   tree name = create_phi_basis (c, phi, basis_name,
    3872                 :            :                                                 loc, UNKNOWN_STRIDE);
    3873                 :            : 
    3874                 :            :                   /* Replace C with an add of the new basis phi and the
    3875                 :            :                      increment.  */
    3876                 :         65 :                   replace_one_candidate (c, i, name);
    3877                 :            :                 }
    3878                 :            :             }
    3879                 :            :           else
    3880                 :            :             {
    3881                 :      16740 :               slsr_cand_t basis = lookup_cand (c->basis);
    3882                 :      16740 :               tree basis_name = gimple_assign_lhs (basis->cand_stmt);
    3883                 :      16740 :               replace_one_candidate (c, i, basis_name);
    3884                 :            :             }
    3885                 :            :         }
    3886                 :            :     }
    3887                 :            : 
    3888                 :      82057 :   if (c->sibling)
    3889                 :       2934 :     replace_profitable_candidates (lookup_cand (c->sibling));
    3890                 :            : 
    3891                 :      82057 :   if (c->dependent)
    3892                 :      24535 :     replace_profitable_candidates (lookup_cand (c->dependent));
    3893                 :      82057 : }
    3894                 :            : 
    3895                 :            : /* Analyze costs of related candidates in the candidate vector,
    3896                 :            :    and make beneficial replacements.  */
    3897                 :            : 
    3898                 :            : static void
    3899                 :     686776 : analyze_candidates_and_replace (void)
    3900                 :            : {
    3901                 :     686776 :   unsigned i;
    3902                 :     686776 :   slsr_cand_t c;
    3903                 :            : 
    3904                 :            :   /* Each candidate that has a null basis and a non-null
    3905                 :            :      dependent is the root of a tree of related statements.
    3906                 :            :      Analyze each tree to determine a subset of those
    3907                 :            :      statements that can be replaced with maximum benefit.
    3908                 :            : 
    3909                 :            :      Note the first NULL element is skipped.  */
    3910                 :    5924820 :   FOR_EACH_VEC_ELT_FROM (cand_vec, i, c, 1)
    3911                 :            :     {
    3912                 :    5238040 :       slsr_cand_t first_dep;
    3913                 :            : 
    3914                 :    5238040 :       if (c->basis != 0 || c->dependent == 0)
    3915                 :    4795220 :         continue;
    3916                 :            : 
    3917                 :     442829 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3918                 :          7 :         fprintf (dump_file, "\nProcessing dependency tree rooted at %d.\n",
    3919                 :            :                  c->cand_num);
    3920                 :            : 
    3921                 :     442829 :       first_dep = lookup_cand (c->dependent);
    3922                 :            : 
    3923                 :            :       /* If this is a chain of CAND_REFs, unconditionally replace
    3924                 :            :          each of them with a strength-reduced data reference.  */
    3925                 :     442829 :       if (c->kind == CAND_REF)
    3926                 :       6795 :         replace_refs (c);
    3927                 :            : 
    3928                 :            :       /* If the common stride of all related candidates is a known
    3929                 :            :          constant, each candidate without a phi-dependence can be
    3930                 :            :          profitably replaced.  Each replaces a multiply by a single
    3931                 :            :          add, with the possibility that a feeding add also goes dead.
    3932                 :            :          A candidate with a phi-dependence is replaced only if the
    3933                 :            :          compensation code it requires is offset by the strength
    3934                 :            :          reduction savings.  */
    3935                 :     436034 :       else if (TREE_CODE (c->stride) == INTEGER_CST)
    3936                 :     381446 :         replace_uncond_cands_and_profitable_phis (first_dep);
    3937                 :            : 
    3938                 :            :       /* When the stride is an SSA name, it may still be profitable
    3939                 :            :          to replace some or all of the dependent candidates, depending
    3940                 :            :          on whether the introduced increments can be reused, or are
    3941                 :            :          less expensive to calculate than the replaced statements.  */
    3942                 :            :       else
    3943                 :            :         {
    3944                 :      54588 :           machine_mode mode;
    3945                 :      54588 :           bool speed;
    3946                 :            : 
    3947                 :            :           /* Determine whether we'll be generating pointer arithmetic
    3948                 :            :              when replacing candidates.  */
    3949                 :     109176 :           address_arithmetic_p = (c->kind == CAND_ADD
    3950                 :      54588 :                                   && POINTER_TYPE_P (c->cand_type));
    3951                 :            : 
    3952                 :            :           /* If all candidates have already been replaced under other
    3953                 :            :              interpretations, nothing remains to be done.  */
    3954                 :      54588 :           if (!count_candidates (c))
    3955                 :          0 :             continue;
    3956                 :            : 
    3957                 :            :           /* Construct an array of increments for this candidate chain.  */
    3958                 :      54588 :           incr_vec = XNEWVEC (incr_info, MAX_INCR_VEC_LEN);
    3959                 :      54588 :           incr_vec_len = 0;
    3960                 :      54588 :           record_increments (c);
    3961                 :            : 
    3962                 :            :           /* Determine which increments are profitable to replace.  */
    3963                 :      54588 :           mode = TYPE_MODE (TREE_TYPE (gimple_assign_lhs (c->cand_stmt)));
    3964                 :      54588 :           speed = optimize_cands_for_speed_p (c);
    3965                 :      54588 :           analyze_increments (first_dep, mode, speed);
    3966                 :            : 
    3967                 :            :           /* Insert initializers of the form T_0 = stride * increment
    3968                 :            :              for use in profitable replacements.  */
    3969                 :      54588 :           insert_initializers (first_dep);
    3970                 :      54588 :           dump_incr_vec ();
    3971                 :            : 
    3972                 :            :           /* Perform the replacements.  */
    3973                 :      54588 :           replace_profitable_candidates (first_dep);
    3974                 :      54588 :           free (incr_vec);
    3975                 :            :         }
    3976                 :            :     }
    3977                 :            : 
    3978                 :            :   /* For conditional candidates, we may have uncommitted insertions
    3979                 :            :      on edges to clean up.  */
    3980                 :     686776 :   gsi_commit_edge_inserts ();
    3981                 :     686776 : }
    3982                 :            : 
    3983                 :            : namespace {
    3984                 :            : 
    3985                 :            : const pass_data pass_data_strength_reduction =
    3986                 :            : {
    3987                 :            :   GIMPLE_PASS, /* type */
    3988                 :            :   "slsr", /* name */
    3989                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    3990                 :            :   TV_GIMPLE_SLSR, /* tv_id */
    3991                 :            :   ( PROP_cfg | PROP_ssa ), /* properties_required */
    3992                 :            :   0, /* properties_provided */
    3993                 :            :   0, /* properties_destroyed */
    3994                 :            :   0, /* todo_flags_start */
    3995                 :            :   0, /* todo_flags_finish */
    3996                 :            : };
    3997                 :            : 
    3998                 :            : class pass_strength_reduction : public gimple_opt_pass
    3999                 :            : {
    4000                 :            : public:
    4001                 :     200773 :   pass_strength_reduction (gcc::context *ctxt)
    4002                 :     401546 :     : gimple_opt_pass (pass_data_strength_reduction, ctxt)
    4003                 :            :   {}
    4004                 :            : 
    4005                 :            :   /* opt_pass methods: */
    4006                 :     686787 :   virtual bool gate (function *) { return flag_tree_slsr; }
    4007                 :            :   virtual unsigned int execute (function *);
    4008                 :            : 
    4009                 :            : }; // class pass_strength_reduction
    4010                 :            : 
    4011                 :            : unsigned
    4012                 :     686776 : pass_strength_reduction::execute (function *fun)
    4013                 :            : {
    4014                 :            :   /* Create the obstack where candidates will reside.  */
    4015                 :     686776 :   gcc_obstack_init (&cand_obstack);
    4016                 :            : 
    4017                 :            :   /* Allocate the candidate vector and initialize the first NULL element.  */
    4018                 :     686776 :   cand_vec.create (128);
    4019                 :     686776 :   cand_vec.safe_push (NULL);
    4020                 :            : 
    4021                 :            :   /* Allocate the mapping from statements to candidate indices.  */
    4022                 :     686776 :   stmt_cand_map = new hash_map<gimple *, slsr_cand_t>;
    4023                 :            : 
    4024                 :            :   /* Create the obstack where candidate chains will reside.  */
    4025                 :     686776 :   gcc_obstack_init (&chain_obstack);
    4026                 :            : 
    4027                 :            :   /* Allocate the mapping from base expressions to candidate chains.  */
    4028                 :     686776 :   base_cand_map = new hash_table<cand_chain_hasher> (500);
    4029                 :            : 
    4030                 :            :   /* Allocate the mapping from bases to alternative bases.  */
    4031                 :     686776 :   alt_base_map = new hash_map<tree, tree>;
    4032                 :            : 
    4033                 :            :   /* Initialize the loop optimizer.  We need to detect flow across
    4034                 :            :      back edges, and this gives us dominator information as well.  */
    4035                 :     686776 :   loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
    4036                 :            : 
    4037                 :            :   /* Walk the CFG in predominator order looking for strength reduction
    4038                 :            :      candidates.  */
    4039                 :     686776 :   find_candidates_dom_walker (CDI_DOMINATORS)
    4040                 :     686776 :     .walk (fun->cfg->x_entry_block_ptr);
    4041                 :            : 
    4042                 :     686776 :   if (dump_file && (dump_flags & TDF_DETAILS))
    4043                 :            :     {
    4044                 :          3 :       dump_cand_vec ();
    4045                 :          3 :       dump_cand_chains ();
    4046                 :            :     }
    4047                 :            : 
    4048                 :    1373550 :   delete alt_base_map;
    4049                 :     686776 :   free_affine_expand_cache (&name_expansions);
    4050                 :            : 
    4051                 :            :   /* Analyze costs and make appropriate replacements.  */
    4052                 :     686776 :   analyze_candidates_and_replace ();
    4053                 :            : 
    4054                 :     686776 :   loop_optimizer_finalize ();
    4055                 :     686776 :   delete base_cand_map;
    4056                 :     686776 :   base_cand_map = NULL;
    4057                 :     686776 :   obstack_free (&chain_obstack, NULL);
    4058                 :    1373550 :   delete stmt_cand_map;
    4059                 :     686776 :   cand_vec.release ();
    4060                 :     686776 :   obstack_free (&cand_obstack, NULL);
    4061                 :            : 
    4062                 :     686776 :   return 0;
    4063                 :            : }
    4064                 :            : 
    4065                 :            : } // anon namespace
    4066                 :            : 
    4067                 :            : gimple_opt_pass *
    4068                 :     200773 : make_pass_strength_reduction (gcc::context *ctxt)
    4069                 :            : {
    4070                 :     200773 :   return new pass_strength_reduction (ctxt);
    4071                 :            : }

Generated by: LCOV version 1.0

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto --enable-host-shared. GCC test suite is run with the built compiler.