LCOV - code coverage report
Current view: top level - gcc - tree-predcom.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 98.2 % 1443 1417
Test Date: 2024-09-28 13:20:55 Functions: 97.5 % 79 77
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : /* Predictive commoning.
       2                 :             :    Copyright (C) 2005-2024 Free Software Foundation, Inc.
       3                 :             : 
       4                 :             : This file is part of GCC.
       5                 :             : 
       6                 :             : GCC is free software; you can redistribute it and/or modify it
       7                 :             : under the terms of the GNU General Public License as published by the
       8                 :             : Free Software Foundation; either version 3, or (at your option) any
       9                 :             : later version.
      10                 :             : 
      11                 :             : GCC is distributed in the hope that it will be useful, but WITHOUT
      12                 :             : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :             : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :             : for more details.
      15                 :             : 
      16                 :             : You should have received a copy of the GNU General Public License
      17                 :             : along with GCC; see the file COPYING3.  If not see
      18                 :             : <http://www.gnu.org/licenses/>.  */
      19                 :             : 
      20                 :             : /* This file implements the predictive commoning optimization.  Predictive
      21                 :             :    commoning can be viewed as CSE around a loop, and with some improvements,
      22                 :             :    as generalized strength reduction-- i.e., reusing values computed in
      23                 :             :    earlier iterations of a loop in the later ones.  So far, the pass only
      24                 :             :    handles the most useful case, that is, reusing values of memory references.
      25                 :             :    If you think this is all just a special case of PRE, you are sort of right;
      26                 :             :    however, concentrating on loops is simpler, and makes it possible to
      27                 :             :    incorporate data dependence analysis to detect the opportunities, perform
      28                 :             :    loop unrolling to avoid copies together with renaming immediately,
      29                 :             :    and if needed, we could also take register pressure into account.
      30                 :             : 
      31                 :             :    Let us demonstrate what is done on an example:
      32                 :             : 
      33                 :             :    for (i = 0; i < 100; i++)
      34                 :             :      {
      35                 :             :        a[i+2] = a[i] + a[i+1];
      36                 :             :        b[10] = b[10] + i;
      37                 :             :        c[i] = c[99 - i];
      38                 :             :        d[i] = d[i + 1];
      39                 :             :      }
      40                 :             : 
      41                 :             :    1) We find data references in the loop, and split them to mutually
      42                 :             :       independent groups (i.e., we find components of a data dependence
      43                 :             :       graph).  We ignore read-read dependences whose distance is not constant.
      44                 :             :       (TODO -- we could also ignore antidependences).  In this example, we
      45                 :             :       find the following groups:
      46                 :             : 
      47                 :             :       a[i]{read}, a[i+1]{read}, a[i+2]{write}
      48                 :             :       b[10]{read}, b[10]{write}
      49                 :             :       c[99 - i]{read}, c[i]{write}
      50                 :             :       d[i + 1]{read}, d[i]{write}
      51                 :             : 
      52                 :             :    2) Inside each of the group, we verify several conditions:
      53                 :             :       a) all the references must differ in indices only, and the indices
      54                 :             :          must all have the same step
      55                 :             :       b) the references must dominate loop latch (and thus, they must be
      56                 :             :          ordered by dominance relation).
      57                 :             :       c) the distance of the indices must be a small multiple of the step
      58                 :             :       We are then able to compute the difference of the references (# of
      59                 :             :       iterations before they point to the same place as the first of them).
      60                 :             :       Also, in case there are writes in the loop, we split the groups into
      61                 :             :       chains whose head is the write whose values are used by the reads in
      62                 :             :       the same chain.  The chains are then processed independently,
      63                 :             :       making the further transformations simpler.  Also, the shorter chains
      64                 :             :       need the same number of registers, but may require lower unrolling
      65                 :             :       factor in order to get rid of the copies on the loop latch.
      66                 :             : 
      67                 :             :       In our example, we get the following chains (the chain for c is invalid).
      68                 :             : 
      69                 :             :       a[i]{read,+0}, a[i+1]{read,-1}, a[i+2]{write,-2}
      70                 :             :       b[10]{read,+0}, b[10]{write,+0}
      71                 :             :       d[i + 1]{read,+0}, d[i]{write,+1}
      72                 :             : 
      73                 :             :    3) For each read, we determine the read or write whose value it reuses,
      74                 :             :       together with the distance of this reuse.  I.e. we take the last
      75                 :             :       reference before it with distance 0, or the last of the references
      76                 :             :       with the smallest positive distance to the read.  Then, we remove
      77                 :             :       the references that are not used in any of these chains, discard the
      78                 :             :       empty groups, and propagate all the links so that they point to the
      79                 :             :       single root reference of the chain (adjusting their distance
      80                 :             :       appropriately).  Some extra care needs to be taken for references with
      81                 :             :       step 0.  In our example (the numbers indicate the distance of the
      82                 :             :       reuse),
      83                 :             : 
      84                 :             :       a[i] --> (*) 2, a[i+1] --> (*) 1, a[i+2] (*)
      85                 :             :       b[10] --> (*) 1, b[10] (*)
      86                 :             : 
      87                 :             :    4) The chains are combined together if possible.  If the corresponding
      88                 :             :       elements of two chains are always combined together with the same
      89                 :             :       operator, we remember just the result of this combination, instead
      90                 :             :       of remembering the values separately.  We may need to perform
      91                 :             :       reassociation to enable combining, for example
      92                 :             : 
      93                 :             :       e[i] + f[i+1] + e[i+1] + f[i]
      94                 :             : 
      95                 :             :       can be reassociated as
      96                 :             : 
      97                 :             :       (e[i] + f[i]) + (e[i+1] + f[i+1])
      98                 :             : 
      99                 :             :       and we can combine the chains for e and f into one chain.
     100                 :             : 
     101                 :             :    5) For each root reference (end of the chain) R, let N be maximum distance
     102                 :             :       of a reference reusing its value.  Variables R0 up to RN are created,
     103                 :             :       together with phi nodes that transfer values from R1 .. RN to
     104                 :             :       R0 .. R(N-1).
     105                 :             :       Initial values are loaded to R0..R(N-1) (in case not all references
     106                 :             :       must necessarily be accessed and they may trap, we may fail here;
     107                 :             :       TODO sometimes, the loads could be guarded by a check for the number
     108                 :             :       of iterations).  Values loaded/stored in roots are also copied to
     109                 :             :       RN.  Other reads are replaced with the appropriate variable Ri.
     110                 :             :       Everything is put to SSA form.
     111                 :             : 
     112                 :             :       As a small improvement, if R0 is dead after the root (i.e., all uses of
     113                 :             :       the value with the maximum distance dominate the root), we can avoid
     114                 :             :       creating RN and use R0 instead of it.
     115                 :             : 
     116                 :             :       In our example, we get (only the parts concerning a and b are shown):
     117                 :             :       for (i = 0; i < 100; i++)
     118                 :             :         {
     119                 :             :           f = phi (a[0], s);
     120                 :             :           s = phi (a[1], f);
     121                 :             :           x = phi (b[10], x);
     122                 :             : 
     123                 :             :           f = f + s;
     124                 :             :           a[i+2] = f;
     125                 :             :           x = x + i;
     126                 :             :           b[10] = x;
     127                 :             :         }
     128                 :             : 
     129                 :             :    6) Factor F for unrolling is determined as the smallest common multiple of
     130                 :             :       (N + 1) for each root reference (N for references for that we avoided
     131                 :             :       creating RN).  If F and the loop is small enough, loop is unrolled F
     132                 :             :       times.  The stores to RN (R0) in the copies of the loop body are
     133                 :             :       periodically replaced with R0, R1, ... (R1, R2, ...), so that they can
     134                 :             :       be coalesced and the copies can be eliminated.
     135                 :             : 
     136                 :             :       TODO -- copy propagation and other optimizations may change the live
     137                 :             :       ranges of the temporary registers and prevent them from being coalesced;
     138                 :             :       this may increase the register pressure.
     139                 :             : 
     140                 :             :       In our case, F = 2 and the (main loop of the) result is
     141                 :             : 
     142                 :             :       for (i = 0; i < ...; i += 2)
     143                 :             :         {
     144                 :             :           f = phi (a[0], f);
     145                 :             :           s = phi (a[1], s);
     146                 :             :           x = phi (b[10], x);
     147                 :             : 
     148                 :             :           f = f + s;
     149                 :             :           a[i+2] = f;
     150                 :             :           x = x + i;
     151                 :             :           b[10] = x;
     152                 :             : 
     153                 :             :           s = s + f;
     154                 :             :           a[i+3] = s;
     155                 :             :           x = x + i;
     156                 :             :           b[10] = x;
     157                 :             :        }
     158                 :             : 
     159                 :             :    Apart from predictive commoning on Load-Load and Store-Load chains, we
     160                 :             :    also support Store-Store chains -- stores killed by other store can be
     161                 :             :    eliminated.  Given below example:
     162                 :             : 
     163                 :             :      for (i = 0; i < n; i++)
     164                 :             :        {
     165                 :             :          a[i] = 1;
     166                 :             :          a[i+2] = 2;
     167                 :             :        }
     168                 :             : 
     169                 :             :    It can be replaced with:
     170                 :             : 
     171                 :             :      t0 = a[0];
     172                 :             :      t1 = a[1];
     173                 :             :      for (i = 0; i < n; i++)
     174                 :             :        {
     175                 :             :          a[i] = 1;
     176                 :             :          t2 = 2;
     177                 :             :          t0 = t1;
     178                 :             :          t1 = t2;
     179                 :             :        }
     180                 :             :      a[n] = t0;
     181                 :             :      a[n+1] = t1;
     182                 :             : 
     183                 :             :    If the loop runs more than 1 iterations, it can be further simplified into:
     184                 :             : 
     185                 :             :      for (i = 0; i < n; i++)
     186                 :             :        {
     187                 :             :          a[i] = 1;
     188                 :             :        }
     189                 :             :      a[n] = 2;
     190                 :             :      a[n+1] = 2;
     191                 :             : 
     192                 :             :    The interesting part is this can be viewed either as general store motion
     193                 :             :    or general dead store elimination in either intra/inter-iterations way.
     194                 :             : 
     195                 :             :    With trivial effort, we also support load inside Store-Store chains if the
     196                 :             :    load is dominated by a store statement in the same iteration of loop.  You
     197                 :             :    can see this as a restricted Store-Mixed-Load-Store chain.
     198                 :             : 
     199                 :             :    TODO: For now, we don't support store-store chains in multi-exit loops.  We
     200                 :             :    force to not unroll in case of store-store chain even if other chains might
     201                 :             :    ask for unroll.
     202                 :             : 
     203                 :             :    Predictive commoning can be generalized for arbitrary computations (not
     204                 :             :    just memory loads), and also nontrivial transfer functions (e.g., replacing
     205                 :             :    i * i with ii_last + 2 * i + 1), to generalize strength reduction.  */
     206                 :             : 
     207                 :             : #include "config.h"
     208                 :             : #define INCLUDE_MEMORY
     209                 :             : #include "system.h"
     210                 :             : #include "coretypes.h"
     211                 :             : #include "backend.h"
     212                 :             : #include "rtl.h"
     213                 :             : #include "tree.h"
     214                 :             : #include "gimple.h"
     215                 :             : #include "predict.h"
     216                 :             : #include "tree-pass.h"
     217                 :             : #include "ssa.h"
     218                 :             : #include "gimple-pretty-print.h"
     219                 :             : #include "alias.h"
     220                 :             : #include "fold-const.h"
     221                 :             : #include "cfgloop.h"
     222                 :             : #include "tree-eh.h"
     223                 :             : #include "gimplify.h"
     224                 :             : #include "gimple-iterator.h"
     225                 :             : #include "gimplify-me.h"
     226                 :             : #include "tree-ssa-loop-ivopts.h"
     227                 :             : #include "tree-ssa-loop-manip.h"
     228                 :             : #include "tree-ssa-loop-niter.h"
     229                 :             : #include "tree-ssa-loop.h"
     230                 :             : #include "tree-into-ssa.h"
     231                 :             : #include "tree-dfa.h"
     232                 :             : #include "tree-ssa.h"
     233                 :             : #include "tree-data-ref.h"
     234                 :             : #include "tree-scalar-evolution.h"
     235                 :             : #include "tree-affine.h"
     236                 :             : #include "builtins.h"
     237                 :             : #include "opts.h"
     238                 :             : 
     239                 :             : /* The maximum number of iterations between the considered memory
     240                 :             :    references.  */
     241                 :             : 
     242                 :             : #define MAX_DISTANCE (target_avail_regs < 16 ? 4 : 8)
     243                 :             : 
     244                 :             : /* Data references (or phi nodes that carry data reference values across
     245                 :             :    loop iterations).  */
     246                 :             : 
     247                 :             : typedef class dref_d
     248                 :             : {
     249                 :             : public:
     250                 :             :   /* The reference itself.  */
     251                 :             :   struct data_reference *ref;
     252                 :             : 
     253                 :             :   /* The statement in that the reference appears.  */
     254                 :             :   gimple *stmt;
     255                 :             : 
     256                 :             :   /* In case that STMT is a phi node, this field is set to the SSA name
     257                 :             :      defined by it in replace_phis_by_defined_names (in order to avoid
     258                 :             :      pointing to phi node that got reallocated in the meantime).  */
     259                 :             :   tree name_defined_by_phi;
     260                 :             : 
     261                 :             :   /* Distance of the reference from the root of the chain (in number of
     262                 :             :      iterations of the loop).  */
     263                 :             :   unsigned distance;
     264                 :             : 
     265                 :             :   /* Number of iterations offset from the first reference in the component.  */
     266                 :             :   widest_int offset;
     267                 :             : 
     268                 :             :   /* Number of the reference in a component, in dominance ordering.  */
     269                 :             :   unsigned pos;
     270                 :             : 
     271                 :             :   /* True if the memory reference is always accessed when the loop is
     272                 :             :      entered.  */
     273                 :             :   unsigned always_accessed : 1;
     274                 :             : } *dref;
     275                 :             : 
     276                 :             : 
     277                 :             : /* Type of the chain of the references.  */
     278                 :             : 
     279                 :             : enum chain_type
     280                 :             : {
     281                 :             :   /* The addresses of the references in the chain are constant.  */
     282                 :             :   CT_INVARIANT,
     283                 :             : 
     284                 :             :   /* There are only loads in the chain.  */
     285                 :             :   CT_LOAD,
     286                 :             : 
     287                 :             :   /* Root of the chain is store, the rest are loads.  */
     288                 :             :   CT_STORE_LOAD,
     289                 :             : 
     290                 :             :   /* There are only stores in the chain.  */
     291                 :             :   CT_STORE_STORE,
     292                 :             : 
     293                 :             :   /* A combination of two chains.  */
     294                 :             :   CT_COMBINATION
     295                 :             : };
     296                 :             : 
     297                 :             : /* Chains of data references.  */
     298                 :             : 
     299                 :             : typedef struct chain
     300                 :             : {
     301                 :       60729 :   chain (chain_type t) : type (t), op (ERROR_MARK), rslt_type (NULL_TREE),
     302                 :       60729 :     ch1 (NULL), ch2 (NULL), length (0), init_seq (NULL), fini_seq (NULL),
     303                 :       60729 :     has_max_use_after (false), all_always_accessed (false), combined (false),
     304                 :       60729 :     inv_store_elimination (false) {}
     305                 :             : 
     306                 :             :   /* Type of the chain.  */
     307                 :             :   enum chain_type type;
     308                 :             : 
     309                 :             :   /* For combination chains, the operator and the two chains that are
     310                 :             :      combined, and the type of the result.  */
     311                 :             :   enum tree_code op;
     312                 :             :   tree rslt_type;
     313                 :             :   struct chain *ch1, *ch2;
     314                 :             : 
     315                 :             :   /* The references in the chain.  */
     316                 :             :   auto_vec<dref> refs;
     317                 :             : 
     318                 :             :   /* The maximum distance of the reference in the chain from the root.  */
     319                 :             :   unsigned length;
     320                 :             : 
     321                 :             :   /* The variables used to copy the value throughout iterations.  */
     322                 :             :   auto_vec<tree> vars;
     323                 :             : 
     324                 :             :   /* Initializers for the variables.  */
     325                 :             :   auto_vec<tree> inits;
     326                 :             : 
     327                 :             :   /* Finalizers for the eliminated stores.  */
     328                 :             :   auto_vec<tree> finis;
     329                 :             : 
     330                 :             :   /* gimple stmts intializing the initial variables of the chain.  */
     331                 :             :   gimple_seq init_seq;
     332                 :             : 
     333                 :             :   /* gimple stmts finalizing the eliminated stores of the chain.  */
     334                 :             :   gimple_seq fini_seq;
     335                 :             : 
     336                 :             :   /* True if there is a use of a variable with the maximal distance
     337                 :             :      that comes after the root in the loop.  */
     338                 :             :   unsigned has_max_use_after : 1;
     339                 :             : 
     340                 :             :   /* True if all the memory references in the chain are always accessed.  */
     341                 :             :   unsigned all_always_accessed : 1;
     342                 :             : 
     343                 :             :   /* True if this chain was combined together with some other chain.  */
     344                 :             :   unsigned combined : 1;
     345                 :             : 
     346                 :             :   /* True if this is store elimination chain and eliminated stores store
     347                 :             :      loop invariant value into memory.  */
     348                 :             :   unsigned inv_store_elimination : 1;
     349                 :             : } *chain_p;
     350                 :             : 
     351                 :             : 
     352                 :             : /* Describes the knowledge about the step of the memory references in
     353                 :             :    the component.  */
     354                 :             : 
     355                 :             : enum ref_step_type
     356                 :             : {
     357                 :             :   /* The step is zero.  */
     358                 :             :   RS_INVARIANT,
     359                 :             : 
     360                 :             :   /* The step is nonzero.  */
     361                 :             :   RS_NONZERO,
     362                 :             : 
     363                 :             :   /* The step may or may not be nonzero.  */
     364                 :             :   RS_ANY
     365                 :             : };
     366                 :             : 
     367                 :             : /* Components of the data dependence graph.  */
     368                 :             : 
     369                 :      658380 : struct component
     370                 :             : {
     371                 :      329190 :   component (bool es) : comp_step (RS_ANY), eliminate_store_p (es),
     372                 :      329190 :     next (NULL) {}
     373                 :             : 
     374                 :             :   /* The references in the component.  */
     375                 :             :   auto_vec<dref> refs;
     376                 :             : 
     377                 :             :   /* What we know about the step of the references in the component.  */
     378                 :             :   enum ref_step_type comp_step;
     379                 :             : 
     380                 :             :   /* True if all references in component are stores and we try to do
     381                 :             :      intra/inter loop iteration dead store elimination.  */
     382                 :             :   bool eliminate_store_p;
     383                 :             : 
     384                 :             :   /* Next component in the list.  */
     385                 :             :   struct component *next;
     386                 :             : };
     387                 :             : 
     388                 :             : /* A class to encapsulate the global states used for predictive
     389                 :             :    commoning work on top of one given LOOP.  */
     390                 :             : 
     391                 :             : class pcom_worker
     392                 :             : {
     393                 :             : public:
     394                 :      362052 :   pcom_worker (loop_p l) : m_loop (l), m_cache (NULL) {}
     395                 :             : 
     396                 :      362052 :   ~pcom_worker ()
     397                 :             :   {
     398                 :      362052 :     free_data_refs (m_datarefs);
     399                 :      362052 :     free_dependence_relations (m_dependences);
     400                 :      362052 :     free_affine_expand_cache (&m_cache);
     401                 :      362052 :     release_chains ();
     402                 :      362052 :   }
     403                 :             : 
     404                 :             :   pcom_worker (const pcom_worker &) = delete;
     405                 :             :   pcom_worker &operator= (const pcom_worker &) = delete;
     406                 :             : 
     407                 :             :   /* Performs predictive commoning.  */
     408                 :             :   unsigned tree_predictive_commoning_loop (bool allow_unroll_p);
     409                 :             : 
     410                 :             :   /* Perform the predictive commoning optimization for chains, make this
     411                 :             :      public for being called in callback execute_pred_commoning_cbck.  */
     412                 :             :   void execute_pred_commoning (bitmap tmp_vars);
     413                 :             : 
     414                 :             : private:
     415                 :             :   /* The pointer to the given loop.  */
     416                 :             :   loop_p m_loop;
     417                 :             : 
     418                 :             :   /* All data references.  */
     419                 :             :   auto_vec<data_reference_p, 10> m_datarefs;
     420                 :             : 
     421                 :             :   /* All data dependences.  */
     422                 :             :   auto_vec<ddr_p, 10> m_dependences;
     423                 :             : 
     424                 :             :   /* All chains.  */
     425                 :             :   auto_vec<chain_p> m_chains;
     426                 :             : 
     427                 :             :   /* Bitmap of ssa names defined by looparound phi nodes covered by chains.  */
     428                 :             :   auto_bitmap m_looparound_phis;
     429                 :             : 
     430                 :             :   typedef hash_map<tree, name_expansion *> tree_expand_map_t;
     431                 :             :   /* Cache used by tree_to_aff_combination_expand.  */
     432                 :             :   tree_expand_map_t *m_cache;
     433                 :             : 
     434                 :             :   /* Splits dependence graph to components.  */
     435                 :             :   struct component *split_data_refs_to_components ();
     436                 :             : 
     437                 :             :   /* Check the conditions on references inside each of components COMPS,
     438                 :             :      and remove the unsuitable components from the list.  */
     439                 :             :   struct component *filter_suitable_components (struct component *comps);
     440                 :             : 
     441                 :             :   /* Find roots of the values and determine distances in components COMPS,
     442                 :             :      and separates the references to chains.  */
     443                 :             :   void determine_roots (struct component *comps);
     444                 :             : 
     445                 :             :   /* Prepare initializers for chains, and free chains that cannot
     446                 :             :      be used because the initializers might trap.  */
     447                 :             :   void prepare_initializers ();
     448                 :             : 
     449                 :             :   /* Generates finalizer memory reference for chains.  Returns true if
     450                 :             :      finalizer code generation for chains breaks loop closed ssa form.  */
     451                 :             :   bool prepare_finalizers ();
     452                 :             : 
     453                 :             :   /* Try to combine the chains.  */
     454                 :             :   void try_combine_chains ();
     455                 :             : 
     456                 :             :   /* Frees CHAINS.  */
     457                 :             :   void release_chains ();
     458                 :             : 
     459                 :             :   /* Frees a chain CHAIN.  */
     460                 :             :   void release_chain (chain_p chain);
     461                 :             : 
     462                 :             :   /* Prepare initializers for CHAIN.  Returns false if this is impossible
     463                 :             :      because one of these initializers may trap, true otherwise.  */
     464                 :             :   bool prepare_initializers_chain (chain_p chain);
     465                 :             : 
     466                 :             :   /* Generates finalizer memory references for CHAIN.  Returns true
     467                 :             :      if finalizer code for CHAIN can be generated, otherwise false.  */
     468                 :             :   bool prepare_finalizers_chain (chain_p chain);
     469                 :             : 
     470                 :             :   /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET.  */
     471                 :             :   void aff_combination_dr_offset (struct data_reference *dr, aff_tree *offset);
     472                 :             : 
     473                 :             :   /* Determines number of iterations of the innermost enclosing loop before
     474                 :             :      B refers to exactly the same location as A and stores it to OFF.  */
     475                 :             :   bool determine_offset (struct data_reference *a, struct data_reference *b,
     476                 :             :                          poly_widest_int *off);
     477                 :             : 
     478                 :             :   /* Returns true if the component COMP satisfies the conditions
     479                 :             :      described in 2) at the beginning of this file.  */
     480                 :             :   bool suitable_component_p (struct component *comp);
     481                 :             : 
     482                 :             :   /* Returns true if REF is a valid initializer for ROOT with given
     483                 :             :      DISTANCE (in iterations of the innermost enclosing loop).  */
     484                 :             :   bool valid_initializer_p (struct data_reference *ref, unsigned distance,
     485                 :             :                             struct data_reference *root);
     486                 :             : 
     487                 :             :   /* Finds looparound phi node of loop that copies the value of REF.  */
     488                 :             :   gphi *find_looparound_phi (dref ref, dref root);
     489                 :             : 
     490                 :             :   /* Find roots of the values and determine distances in the component
     491                 :             :      COMP.  The references are redistributed into chains.  */
     492                 :             :   void determine_roots_comp (struct component *comp);
     493                 :             : 
     494                 :             :   /* For references in CHAIN that are copied around the loop, add the
     495                 :             :      results of such copies to the chain.  */
     496                 :             :   void add_looparound_copies (chain_p chain);
     497                 :             : 
     498                 :             :   /* Returns the single statement in that NAME is used, excepting
     499                 :             :      the looparound phi nodes contained in one of the chains.  */
     500                 :             :   gimple *single_nonlooparound_use (tree name);
     501                 :             : 
     502                 :             :   /* Remove statement STMT, as well as the chain of assignments in that
     503                 :             :      it is used.  */
     504                 :             :   void remove_stmt (gimple *stmt);
     505                 :             : 
     506                 :             :   /* Perform the predictive commoning optimization for a chain CHAIN.  */
     507                 :             :   void execute_pred_commoning_chain (chain_p chain, bitmap tmp_vars);
     508                 :             : 
     509                 :             :   /* Returns the modify statement that uses NAME.  */
     510                 :             :   gimple *find_use_stmt (tree *name);
     511                 :             : 
     512                 :             :   /* If the operation used in STMT is associative and commutative, go
     513                 :             :      through the tree of the same operations and returns its root.  */
     514                 :             :   gimple *find_associative_operation_root (gimple *stmt, unsigned *distance);
     515                 :             : 
     516                 :             :   /* Returns the common statement in that NAME1 and NAME2 have a use.  */
     517                 :             :   gimple *find_common_use_stmt (tree *name1, tree *name2);
     518                 :             : 
     519                 :             :   /* Checks whether R1 and R2 are combined together using CODE, with the
     520                 :             :      result in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order
     521                 :             :      R2 CODE R1 if it is true.  */
     522                 :             :   bool combinable_refs_p (dref r1, dref r2, enum tree_code *code, bool *swap,
     523                 :             :                           tree *rslt_type);
     524                 :             : 
     525                 :             :   /* Reassociates the expression in that NAME1 and NAME2 are used so that
     526                 :             :      they are combined in a single statement, and returns this statement.  */
     527                 :             :   gimple *reassociate_to_the_same_stmt (tree name1, tree name2);
     528                 :             : 
     529                 :             :   /* Returns the statement that combines references R1 and R2.  */
     530                 :             :   gimple *stmt_combining_refs (dref r1, dref r2);
     531                 :             : 
     532                 :             :   /* Tries to combine chains CH1 and CH2 together.  */
     533                 :             :   chain_p combine_chains (chain_p ch1, chain_p ch2);
     534                 :             : };
     535                 :             : 
     536                 :             : /* Dumps data reference REF to FILE.  */
     537                 :             : 
     538                 :             : extern void dump_dref (FILE *, dref);
     539                 :             : void
     540                 :         308 : dump_dref (FILE *file, dref ref)
     541                 :             : {
     542                 :         308 :   if (ref->ref)
     543                 :             :     {
     544                 :         289 :       fprintf (file, "    ");
     545                 :         289 :       print_generic_expr (file, DR_REF (ref->ref), TDF_SLIM);
     546                 :         289 :       fprintf (file, " (id %u%s)\n", ref->pos,
     547                 :         289 :                DR_IS_READ (ref->ref) ? "" : ", write");
     548                 :             : 
     549                 :         289 :       fprintf (file, "      offset ");
     550                 :         289 :       print_decs (ref->offset, file);
     551                 :         289 :       fprintf (file, "\n");
     552                 :             : 
     553                 :         289 :       fprintf (file, "      distance %u\n", ref->distance);
     554                 :             :     }
     555                 :             :   else
     556                 :             :     {
     557                 :          19 :       if (gimple_code (ref->stmt) == GIMPLE_PHI)
     558                 :           1 :         fprintf (file, "    looparound ref\n");
     559                 :             :       else
     560                 :          18 :         fprintf (file, "    combination ref\n");
     561                 :          19 :       fprintf (file, "      in statement ");
     562                 :          19 :       print_gimple_stmt (file, ref->stmt, 0, TDF_SLIM);
     563                 :          19 :       fprintf (file, "\n");
     564                 :          19 :       fprintf (file, "      distance %u\n", ref->distance);
     565                 :             :     }
     566                 :             : 
     567                 :         308 : }
     568                 :             : 
     569                 :             : /* Dumps CHAIN to FILE.  */
     570                 :             : 
     571                 :             : extern void dump_chain (FILE *, chain_p);
     572                 :             : void
     573                 :          58 : dump_chain (FILE *file, chain_p chain)
     574                 :             : {
     575                 :          58 :   dref a;
     576                 :          58 :   const char *chain_type;
     577                 :          58 :   unsigned i;
     578                 :          58 :   tree var;
     579                 :             : 
     580                 :          58 :   switch (chain->type)
     581                 :             :     {
     582                 :             :     case CT_INVARIANT:
     583                 :             :       chain_type = "Load motion";
     584                 :             :       break;
     585                 :             : 
     586                 :          24 :     case CT_LOAD:
     587                 :          24 :       chain_type = "Loads-only";
     588                 :          24 :       break;
     589                 :             : 
     590                 :           5 :     case CT_STORE_LOAD:
     591                 :           5 :       chain_type = "Store-loads";
     592                 :           5 :       break;
     593                 :             : 
     594                 :          19 :     case CT_STORE_STORE:
     595                 :          19 :       chain_type = "Store-stores";
     596                 :          19 :       break;
     597                 :             : 
     598                 :           9 :     case CT_COMBINATION:
     599                 :           9 :       chain_type = "Combination";
     600                 :           9 :       break;
     601                 :             : 
     602                 :           0 :     default:
     603                 :           0 :       gcc_unreachable ();
     604                 :             :     }
     605                 :             : 
     606                 :          58 :   fprintf (file, "%s chain %p%s\n", chain_type, (void *) chain,
     607                 :          58 :            chain->combined ? " (combined)" : "");
     608                 :          58 :   if (chain->type != CT_INVARIANT)
     609                 :          57 :     fprintf (file, "  max distance %u%s\n", chain->length,
     610                 :          57 :              chain->has_max_use_after ? "" : ", may reuse first");
     611                 :             : 
     612                 :          58 :   if (chain->type == CT_COMBINATION)
     613                 :             :     {
     614                 :          18 :       fprintf (file, "  equal to %p %s %p in type ",
     615                 :           9 :                (void *) chain->ch1, op_symbol_code (chain->op),
     616                 :           9 :                (void *) chain->ch2);
     617                 :           9 :       print_generic_expr (file, chain->rslt_type, TDF_SLIM);
     618                 :           9 :       fprintf (file, "\n");
     619                 :             :     }
     620                 :             : 
     621                 :          58 :   if (chain->vars.exists ())
     622                 :             :     {
     623                 :           0 :       fprintf (file, "  vars");
     624                 :           0 :       FOR_EACH_VEC_ELT (chain->vars, i, var)
     625                 :             :         {
     626                 :           0 :           fprintf (file, " ");
     627                 :           0 :           print_generic_expr (file, var, TDF_SLIM);
     628                 :             :         }
     629                 :           0 :       fprintf (file, "\n");
     630                 :             :     }
     631                 :             : 
     632                 :          58 :   if (chain->inits.exists ())
     633                 :             :     {
     634                 :          41 :       fprintf (file, "  inits");
     635                 :         149 :       FOR_EACH_VEC_ELT (chain->inits, i, var)
     636                 :             :         {
     637                 :          67 :           fprintf (file, " ");
     638                 :          67 :           print_generic_expr (file, var, TDF_SLIM);
     639                 :             :         }
     640                 :          41 :       fprintf (file, "\n");
     641                 :             :     }
     642                 :             : 
     643                 :          58 :   fprintf (file, "  references:\n");
     644                 :         251 :   FOR_EACH_VEC_ELT (chain->refs, i, a)
     645                 :         135 :     dump_dref (file, a);
     646                 :             : 
     647                 :          58 :   fprintf (file, "\n");
     648                 :          58 : }
     649                 :             : 
     650                 :             : /* Dumps CHAINS to FILE.  */
     651                 :             : 
     652                 :             : void
     653                 :          34 : dump_chains (FILE *file, const vec<chain_p> &chains)
     654                 :             : {
     655                 :          34 :   chain_p chain;
     656                 :          34 :   unsigned i;
     657                 :             : 
     658                 :          92 :   FOR_EACH_VEC_ELT (chains, i, chain)
     659                 :          58 :     dump_chain (file, chain);
     660                 :          34 : }
     661                 :             : 
     662                 :             : /* Dumps COMP to FILE.  */
     663                 :             : 
     664                 :             : extern void dump_component (FILE *, struct component *);
     665                 :             : void
     666                 :         103 : dump_component (FILE *file, struct component *comp)
     667                 :             : {
     668                 :         103 :   dref a;
     669                 :         103 :   unsigned i;
     670                 :             : 
     671                 :         206 :   fprintf (file, "Component%s:\n",
     672                 :         103 :            comp->comp_step == RS_INVARIANT ? " (invariant)" : "");
     673                 :         379 :   FOR_EACH_VEC_ELT (comp->refs, i, a)
     674                 :         173 :     dump_dref (file, a);
     675                 :         103 :   fprintf (file, "\n");
     676                 :         103 : }
     677                 :             : 
     678                 :             : /* Dumps COMPS to FILE.  */
     679                 :             : 
     680                 :             : extern void dump_components (FILE *, struct component *);
     681                 :             : void
     682                 :          54 : dump_components (FILE *file, struct component *comps)
     683                 :             : {
     684                 :          54 :   struct component *comp;
     685                 :             : 
     686                 :         157 :   for (comp = comps; comp; comp = comp->next)
     687                 :         103 :     dump_component (file, comp);
     688                 :          54 : }
     689                 :             : 
     690                 :             : /* Frees a chain CHAIN.  */
     691                 :             : 
     692                 :             : void
     693                 :       90005 : pcom_worker::release_chain (chain_p chain)
     694                 :             : {
     695                 :       90005 :   dref ref;
     696                 :       90005 :   unsigned i;
     697                 :             : 
     698                 :       90005 :   if (chain == NULL)
     699                 :       90005 :     return;
     700                 :             : 
     701                 :      139287 :   FOR_EACH_VEC_ELT (chain->refs, i, ref)
     702                 :       78558 :     free (ref);
     703                 :             : 
     704                 :       60729 :   if (chain->init_seq)
     705                 :           0 :     gimple_seq_discard (chain->init_seq);
     706                 :             : 
     707                 :       60729 :   if (chain->fini_seq)
     708                 :           0 :     gimple_seq_discard (chain->fini_seq);
     709                 :             : 
     710                 :       60729 :   delete chain;
     711                 :             : }
     712                 :             : 
     713                 :             : /* Frees CHAINS.  */
     714                 :             : 
     715                 :             : void
     716                 :      362052 : pcom_worker::release_chains ()
     717                 :             : {
     718                 :      362052 :   unsigned i;
     719                 :      362052 :   chain_p chain;
     720                 :             : 
     721                 :      387830 :   FOR_EACH_VEC_ELT (m_chains, i, chain)
     722                 :       25778 :     release_chain (chain);
     723                 :      362052 : }
     724                 :             : 
     725                 :             : /* Frees list of components COMPS.  */
     726                 :             : 
     727                 :             : static void
     728                 :      140347 : release_components (struct component *comps)
     729                 :             : {
     730                 :      140347 :   struct component *act, *next;
     731                 :             : 
     732                 :      444250 :   for (act = comps; act; act = next)
     733                 :             :     {
     734                 :      303903 :       next = act->next;
     735                 :      303903 :       delete act;
     736                 :             :     }
     737                 :      140347 : }
     738                 :             : 
     739                 :             : /* Finds a root of tree given by FATHERS containing A, and performs path
     740                 :             :    shortening.  */
     741                 :             : 
     742                 :             : static unsigned
     743                 :     6171961 : component_of (vec<unsigned> &fathers, unsigned a)
     744                 :             : {
     745                 :     6171961 :   unsigned root, n;
     746                 :             : 
     747                 :     9298542 :   for (root = a; root != fathers[root]; root = fathers[root])
     748                 :     3126581 :     continue;
     749                 :             : 
     750                 :     9298542 :   for (; a != root; a = n)
     751                 :             :     {
     752                 :     3126581 :       n = fathers[a];
     753                 :     3126581 :       fathers[a] = root;
     754                 :             :     }
     755                 :             : 
     756                 :     6171961 :   return root;
     757                 :     3126581 : }
     758                 :             : 
     759                 :             : /* Join operation for DFU.  FATHERS gives the tree, SIZES are sizes of the
     760                 :             :    components, A and B are components to merge.  */
     761                 :             : 
     762                 :             : static void
     763                 :      282798 : merge_comps (vec<unsigned> &fathers, vec<unsigned> &sizes,
     764                 :             :              unsigned a, unsigned b)
     765                 :             : {
     766                 :      282798 :   unsigned ca = component_of (fathers, a);
     767                 :      282798 :   unsigned cb = component_of (fathers, b);
     768                 :             : 
     769                 :      282798 :   if (ca == cb)
     770                 :             :     return;
     771                 :             : 
     772                 :      282798 :   if (sizes[ca] < sizes[cb])
     773                 :             :     {
     774                 :       16568 :       sizes[cb] += sizes[ca];
     775                 :       16568 :       fathers[ca] = cb;
     776                 :             :     }
     777                 :             :   else
     778                 :             :     {
     779                 :      266230 :       sizes[ca] += sizes[cb];
     780                 :      266230 :       fathers[cb] = ca;
     781                 :             :     }
     782                 :             : }
     783                 :             : 
     784                 :             : /* Returns true if A is a reference that is suitable for predictive commoning
     785                 :             :    in the innermost loop that contains it.  REF_STEP is set according to the
     786                 :             :    step of the reference A.  */
     787                 :             : 
     788                 :             : static bool
     789                 :      959682 : suitable_reference_p (struct data_reference *a, enum ref_step_type *ref_step)
     790                 :             : {
     791                 :      959682 :   tree ref = DR_REF (a), step = DR_STEP (a);
     792                 :             : 
     793                 :      959682 :   if (!step
     794                 :      863121 :       || TREE_THIS_VOLATILE (ref)
     795                 :      849601 :       || !is_gimple_reg_type (TREE_TYPE (ref))
     796                 :     1795151 :       || tree_could_throw_p (ref))
     797                 :      160685 :     return false;
     798                 :             : 
     799                 :      798997 :   if (integer_zerop (step))
     800                 :       50788 :     *ref_step = RS_INVARIANT;
     801                 :      748209 :   else if (integer_nonzerop (step))
     802                 :      681855 :     *ref_step = RS_NONZERO;
     803                 :             :   else
     804                 :       66354 :     *ref_step = RS_ANY;
     805                 :             : 
     806                 :             :   return true;
     807                 :             : }
     808                 :             : 
     809                 :             : /* Stores DR_OFFSET (DR) + DR_INIT (DR) to OFFSET.  */
     810                 :             : 
     811                 :             : void
     812                 :      182228 : pcom_worker::aff_combination_dr_offset (struct data_reference *dr,
     813                 :             :                                         aff_tree *offset)
     814                 :             : {
     815                 :      182228 :   tree type = TREE_TYPE (DR_OFFSET (dr));
     816                 :      182228 :   aff_tree delta;
     817                 :             : 
     818                 :      182228 :   tree_to_aff_combination_expand (DR_OFFSET (dr), type, offset, &m_cache);
     819                 :      182228 :   aff_combination_const (&delta, type, wi::to_poly_widest (DR_INIT (dr)));
     820                 :      182228 :   aff_combination_add (offset, &delta);
     821                 :      182228 : }
     822                 :             : 
     823                 :             : /* Determines number of iterations of the innermost enclosing loop before B
     824                 :             :    refers to exactly the same location as A and stores it to OFF.  If A and
     825                 :             :    B do not have the same step, they never meet, or anything else fails,
     826                 :             :    returns false, otherwise returns true.  Both A and B are assumed to
     827                 :             :    satisfy suitable_reference_p.  */
     828                 :             : 
     829                 :             : bool
     830                 :      393292 : pcom_worker::determine_offset (struct data_reference *a,
     831                 :             :                                struct data_reference *b, poly_widest_int *off)
     832                 :             : {
     833                 :     1179876 :   aff_tree diff, baseb, step;
     834                 :      393292 :   tree typea, typeb;
     835                 :             : 
     836                 :             :   /* Check that both the references access the location in the same type.  */
     837                 :      393292 :   typea = TREE_TYPE (DR_REF (a));
     838                 :      393292 :   typeb = TREE_TYPE (DR_REF (b));
     839                 :      393292 :   if (!useless_type_conversion_p (typeb, typea))
     840                 :             :     return false;
     841                 :             : 
     842                 :             :   /* Check whether the base address and the step of both references is the
     843                 :             :      same.  */
     844                 :      374845 :   if (!operand_equal_p (DR_STEP (a), DR_STEP (b), 0)
     845                 :      374845 :       || !operand_equal_p (DR_BASE_ADDRESS (a), DR_BASE_ADDRESS (b), 0))
     846                 :      273865 :     return false;
     847                 :             : 
     848                 :      100980 :   if (integer_zerop (DR_STEP (a)))
     849                 :             :     {
     850                 :             :       /* If the references have loop invariant address, check that they access
     851                 :             :          exactly the same location.  */
     852                 :        9886 :       *off = 0;
     853                 :        9886 :       return (operand_equal_p (DR_OFFSET (a), DR_OFFSET (b), 0)
     854                 :        9886 :               && operand_equal_p (DR_INIT (a), DR_INIT (b), 0));
     855                 :             :     }
     856                 :             : 
     857                 :             :   /* Compare the offsets of the addresses, and check whether the difference
     858                 :             :      is a multiple of step.  */
     859                 :       91094 :   aff_combination_dr_offset (a, &diff);
     860                 :       91094 :   aff_combination_dr_offset (b, &baseb);
     861                 :       91094 :   aff_combination_scale (&baseb, -1);
     862                 :       91094 :   aff_combination_add (&diff, &baseb);
     863                 :             : 
     864                 :       91094 :   tree_to_aff_combination_expand (DR_STEP (a), TREE_TYPE (DR_STEP (a)),
     865                 :             :                                   &step, &m_cache);
     866                 :       91094 :   return aff_combination_constant_multiple_p (&diff, &step, off);
     867                 :      393292 : }
     868                 :             : 
     869                 :             : /* Returns the last basic block in LOOP for that we are sure that
     870                 :             :    it is executed whenever the loop is entered.  */
     871                 :             : 
     872                 :             : static basic_block
     873                 :      207866 : last_always_executed_block (class loop *loop)
     874                 :             : {
     875                 :      207866 :   unsigned i;
     876                 :      207866 :   auto_vec<edge> exits = get_loop_exit_edges (loop);
     877                 :      207866 :   edge ex;
     878                 :      207866 :   basic_block last = loop->latch;
     879                 :             : 
     880                 :      531977 :   FOR_EACH_VEC_ELT (exits, i, ex)
     881                 :      324111 :     last = nearest_common_dominator (CDI_DOMINATORS, last, ex->src);
     882                 :             : 
     883                 :      207866 :   return last;
     884                 :      207866 : }
     885                 :             : 
     886                 :             : /* Splits dependence graph on DATAREFS described by DEPENDENCES to
     887                 :             :    components.  */
     888                 :             : 
     889                 :             : struct component *
     890                 :      207866 : pcom_worker::split_data_refs_to_components ()
     891                 :             : {
     892                 :      207866 :   unsigned i, n = m_datarefs.length ();
     893                 :      207866 :   unsigned ca, ia, ib, bad;
     894                 :      207866 :   struct data_reference *dr, *dra, *drb;
     895                 :      207866 :   struct data_dependence_relation *ddr;
     896                 :      207866 :   struct component *comp_list = NULL, *comp;
     897                 :      207866 :   dref dataref;
     898                 :             :   /* Don't do store elimination if loop has multiple exit edges.  */
     899                 :      207866 :   bool eliminate_store_p = single_exit (m_loop) != NULL;
     900                 :      207866 :   basic_block last_always_executed = last_always_executed_block (m_loop);
     901                 :      207866 :   auto_bitmap no_store_store_comps;
     902                 :      207866 :   auto_vec<unsigned> comp_father (n + 1);
     903                 :      207866 :   auto_vec<unsigned> comp_size (n + 1);
     904                 :      207866 :   comp_father.quick_grow (n + 1);
     905                 :      207866 :   comp_size.quick_grow (n + 1);
     906                 :             : 
     907                 :     1028234 :   FOR_EACH_VEC_ELT (m_datarefs, i, dr)
     908                 :             :     {
     909                 :      612658 :       if (!DR_REF (dr))
     910                 :             :           /* A fake reference for call or asm_expr that may clobber memory;
     911                 :             :              just fail.  */
     912                 :             :           return NULL;
     913                 :             :       /* predcom pass isn't prepared to handle calls with data references.  */
     914                 :      612658 :       if (is_gimple_call (DR_STMT (dr)))
     915                 :             :         return NULL;
     916                 :      612502 :       dr->aux = (void *) (size_t) i;
     917                 :      612502 :       comp_father[i] = i;
     918                 :      612502 :       comp_size[i] = 1;
     919                 :             :     }
     920                 :             : 
     921                 :             :   /* A component reserved for the "bad" data references.  */
     922                 :      207710 :   comp_father[n] = n;
     923                 :      207710 :   comp_size[n] = 1;
     924                 :             : 
     925                 :      819698 :   FOR_EACH_VEC_ELT (m_datarefs, i, dr)
     926                 :             :     {
     927                 :      611988 :       enum ref_step_type dummy;
     928                 :             : 
     929                 :      611988 :       if (!suitable_reference_p (dr, &dummy))
     930                 :             :         {
     931                 :      160685 :           ia = (unsigned) (size_t) dr->aux;
     932                 :      160685 :           merge_comps (comp_father, comp_size, n, ia);
     933                 :             :         }
     934                 :             :     }
     935                 :             : 
     936                 :     8076126 :   FOR_EACH_VEC_ELT (m_dependences, i, ddr)
     937                 :             :     {
     938                 :             :       poly_widest_int dummy_off;
     939                 :             : 
     940                 :     3934208 :       if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
     941                 :     1812953 :         continue;
     942                 :             : 
     943                 :     2121255 :       dra = DDR_A (ddr);
     944                 :     2121255 :       drb = DDR_B (ddr);
     945                 :             : 
     946                 :             :       /* Don't do store elimination if there is any unknown dependence for
     947                 :             :          any store data reference.  */
     948                 :     1457850 :       if ((DR_IS_WRITE (dra) || DR_IS_WRITE (drb))
     949                 :     2466271 :           && (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
     950                 :      274706 :               || DDR_NUM_DIST_VECTS (ddr) == 0))
     951                 :             :         eliminate_store_p = false;
     952                 :             : 
     953                 :     2121255 :       ia = component_of (comp_father, (unsigned) (size_t) dra->aux);
     954                 :     2121255 :       ib = component_of (comp_father, (unsigned) (size_t) drb->aux);
     955                 :     2121255 :       if (ia == ib)
     956                 :     1577708 :         continue;
     957                 :             : 
     958                 :      543547 :       bad = component_of (comp_father, n);
     959                 :             : 
     960                 :             :       /* If both A and B are reads, we may ignore unsuitable dependences.  */
     961                 :      543547 :       if (DR_IS_READ (dra) && DR_IS_READ (drb))
     962                 :             :         {
     963                 :      306155 :           if (ia == bad || ib == bad
     964                 :      622942 :               || !determine_offset (dra, drb, &dummy_off))
     965                 :      311371 :             continue;
     966                 :             :         }
     967                 :             :       /* If A is read and B write or vice versa and there is unsuitable
     968                 :             :          dependence, instead of merging both components into a component
     969                 :             :          that will certainly not pass suitable_component_p, just put the
     970                 :             :          read into bad component, perhaps at least the write together with
     971                 :             :          all the other data refs in it's component will be optimizable.  */
     972                 :      211787 :       else if (DR_IS_READ (dra) && ib != bad)
     973                 :             :         {
     974                 :      147435 :           if (ia == bad)
     975                 :             :             {
     976                 :       97561 :               bitmap_set_bit (no_store_store_comps, ib);
     977                 :       97561 :               continue;
     978                 :             :             }
     979                 :       49874 :           else if (!determine_offset (dra, drb, &dummy_off))
     980                 :             :             {
     981                 :       23504 :               bitmap_set_bit (no_store_store_comps, ib);
     982                 :       23504 :               merge_comps (comp_father, comp_size, bad, ia);
     983                 :       23504 :               continue;
     984                 :             :             }
     985                 :             :         }
     986                 :       64352 :       else if (DR_IS_READ (drb) && ia != bad)
     987                 :             :         {
     988                 :       21480 :           if (ib == bad)
     989                 :             :             {
     990                 :       14625 :               bitmap_set_bit (no_store_store_comps, ia);
     991                 :       14625 :               continue;
     992                 :             :             }
     993                 :        6855 :           else if (!determine_offset (dra, drb, &dummy_off))
     994                 :             :             {
     995                 :        3214 :               bitmap_set_bit (no_store_store_comps, ia);
     996                 :        3214 :               merge_comps (comp_father, comp_size, bad, ib);
     997                 :        3214 :               continue;
     998                 :             :             }
     999                 :             :         }
    1000                 :       31278 :       else if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb)
    1001                 :       26137 :                && ia != bad && ib != bad
    1002                 :       50232 :                && !determine_offset (dra, drb, &dummy_off))
    1003                 :             :         {
    1004                 :        2123 :           merge_comps (comp_father, comp_size, bad, ia);
    1005                 :        2123 :           merge_comps (comp_father, comp_size, bad, ib);
    1006                 :        2123 :           continue;
    1007                 :             :         }
    1008                 :             : 
    1009                 :       91149 :       merge_comps (comp_father, comp_size, ia, ib);
    1010                 :     3934208 :     }
    1011                 :             : 
    1012                 :      207710 :   if (eliminate_store_p)
    1013                 :             :     {
    1014                 :       94656 :       tree niters = number_of_latch_executions (m_loop);
    1015                 :             : 
    1016                 :             :       /* Don't do store elimination if niters info is unknown because stores
    1017                 :             :          in the last iteration can't be eliminated and we need to recover it
    1018                 :             :          after loop.  */
    1019                 :       94656 :       eliminate_store_p = (niters != NULL_TREE && niters != chrec_dont_know);
    1020                 :             :     }
    1021                 :             : 
    1022                 :      207710 :   auto_vec<struct component *> comps;
    1023                 :      207710 :   comps.safe_grow_cleared (n, true);
    1024                 :      207710 :   bad = component_of (comp_father, n);
    1025                 :     1027408 :   FOR_EACH_VEC_ELT (m_datarefs, i, dr)
    1026                 :             :     {
    1027                 :      611988 :       ia = (unsigned) (size_t) dr->aux;
    1028                 :      611988 :       ca = component_of (comp_father, ia);
    1029                 :      611988 :       if (ca == bad)
    1030                 :      232613 :         continue;
    1031                 :             : 
    1032                 :      379375 :       comp = comps[ca];
    1033                 :      379375 :       if (!comp)
    1034                 :             :         {
    1035                 :      329190 :           comp = new component (eliminate_store_p);
    1036                 :      329190 :           comp->refs.reserve_exact (comp_size[ca]);
    1037                 :      329190 :           comps[ca] = comp;
    1038                 :             :         }
    1039                 :             : 
    1040                 :      379375 :       dataref = XCNEW (class dref_d);
    1041                 :      379375 :       dataref->ref = dr;
    1042                 :      379375 :       dataref->stmt = DR_STMT (dr);
    1043                 :      379375 :       dataref->offset = 0;
    1044                 :      379375 :       dataref->distance = 0;
    1045                 :             : 
    1046                 :      379375 :       dataref->always_accessed
    1047                 :      379375 :               = dominated_by_p (CDI_DOMINATORS, last_always_executed,
    1048                 :      379375 :                                 gimple_bb (dataref->stmt));
    1049                 :      379375 :       dataref->pos = comp->refs.length ();
    1050                 :      379375 :       comp->refs.quick_push (dataref);
    1051                 :             :     }
    1052                 :             : 
    1053                 :      207710 :   if (eliminate_store_p)
    1054                 :             :     {
    1055                 :       80468 :       bitmap_iterator bi;
    1056                 :       81078 :       EXECUTE_IF_SET_IN_BITMAP (no_store_store_comps, 0, ia, bi)
    1057                 :             :         {
    1058                 :         610 :           ca = component_of (comp_father, ia);
    1059                 :         610 :           if (ca != bad)
    1060                 :         502 :             comps[ca]->eliminate_store_p = false;
    1061                 :             :         }
    1062                 :             :     }
    1063                 :             : 
    1064                 :      819698 :   for (i = 0; i < n; i++)
    1065                 :             :     {
    1066                 :      611988 :       comp = comps[i];
    1067                 :      611988 :       if (comp)
    1068                 :             :         {
    1069                 :      329190 :           comp->next = comp_list;
    1070                 :      329190 :           comp_list = comp;
    1071                 :             :         }
    1072                 :             :     }
    1073                 :      207710 :   return comp_list;
    1074                 :      415576 : }
    1075                 :             : 
    1076                 :             : /* Returns true if the component COMP satisfies the conditions
    1077                 :             :    described in 2) at the beginning of this file.  */
    1078                 :             : 
    1079                 :             : bool
    1080                 :      329190 : pcom_worker::suitable_component_p (struct component *comp)
    1081                 :             : {
    1082                 :      329190 :   unsigned i;
    1083                 :      329190 :   dref a, first;
    1084                 :      329190 :   basic_block ba, bp = m_loop->header;
    1085                 :      329190 :   bool ok, has_write = false;
    1086                 :             : 
    1087                 :      678431 :   FOR_EACH_VEC_ELT (comp->refs, i, a)
    1088                 :             :     {
    1089                 :      368758 :       ba = gimple_bb (a->stmt);
    1090                 :             : 
    1091                 :      368758 :       if (!just_once_each_iteration_p (m_loop, ba))
    1092                 :             :         return false;
    1093                 :             : 
    1094                 :      349241 :       gcc_assert (dominated_by_p (CDI_DOMINATORS, ba, bp));
    1095                 :      349241 :       bp = ba;
    1096                 :             : 
    1097                 :      349241 :       if (DR_IS_WRITE (a->ref))
    1098                 :      122511 :         has_write = true;
    1099                 :             :     }
    1100                 :             : 
    1101                 :      309673 :   first = comp->refs[0];
    1102                 :      309673 :   ok = suitable_reference_p (first->ref, &comp->comp_step);
    1103                 :      309673 :   gcc_assert (ok);
    1104                 :      309673 :   first->offset = 0;
    1105                 :             : 
    1106                 :      657321 :   FOR_EACH_VEC_ELT (comp->refs, i, a)
    1107                 :             :     {
    1108                 :      347694 :       if (has_write && comp->comp_step == RS_NONZERO)
    1109                 :             :         {
    1110                 :             :           /* Punt for non-invariant references where step isn't a multiple
    1111                 :             :              of reference size.  If step is smaller than reference size,
    1112                 :             :              it overlaps the access in next iteration, if step is larger,
    1113                 :             :              but not multiple of the access size, there could be overlap
    1114                 :             :              in some later iteration.  There might be more latent issues
    1115                 :             :              about this in predcom or data reference analysis.  If the
    1116                 :             :              reference is a COMPONENT_REF, also check if step isn't a
    1117                 :             :              multiple of the containg aggregate size.  See PR111683.  */
    1118                 :      123248 :           tree ref = DR_REF (a->ref);
    1119                 :      123248 :           tree step = DR_STEP (a->ref);
    1120                 :      123248 :           if (TREE_CODE (ref) == COMPONENT_REF
    1121                 :      123248 :               && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))
    1122                 :          55 :             ref = TREE_OPERAND (ref, 0);
    1123                 :      123320 :           do
    1124                 :             :             {
    1125                 :      123284 :               tree sz = TYPE_SIZE_UNIT (TREE_TYPE (ref));
    1126                 :      123284 :               if (TREE_CODE (sz) != INTEGER_CST)
    1127                 :          46 :                 return false;
    1128                 :      246568 :               if (wi::multiple_of_p (wi::to_offset (step),
    1129                 :      246568 :                                      wi::to_offset (sz), SIGNED))
    1130                 :             :                 break;
    1131                 :          82 :               if (TREE_CODE (ref) != COMPONENT_REF)
    1132                 :             :                 return false;
    1133                 :          36 :               ref = TREE_OPERAND (ref, 0);
    1134                 :          36 :             }
    1135                 :             :           while (1);
    1136                 :             :         }
    1137                 :      347648 :       if (i == 0)
    1138                 :      309627 :         continue;
    1139                 :             :       /* Polynomial offsets are no use, since we need to know the
    1140                 :             :          gap between iteration numbers at compile time.  */
    1141                 :             :       poly_widest_int offset;
    1142                 :       38021 :       if (!determine_offset (first->ref, a->ref, &offset)
    1143                 :       38021 :           || !offset.is_constant (&a->offset))
    1144                 :           0 :         return false;
    1145                 :             : 
    1146                 :       38021 :       enum ref_step_type a_step;
    1147                 :       38021 :       gcc_checking_assert (suitable_reference_p (a->ref, &a_step)
    1148                 :             :                            && a_step == comp->comp_step);
    1149                 :       38021 :     }
    1150                 :             : 
    1151                 :             :   /* If there is a write inside the component, we must know whether the
    1152                 :             :      step is nonzero or not -- we would not otherwise be able to recognize
    1153                 :             :      whether the value accessed by reads comes from the OFFSET-th iteration
    1154                 :             :      or the previous one.  */
    1155                 :      309627 :   if (has_write && comp->comp_step == RS_ANY)
    1156                 :             :     return false;
    1157                 :             : 
    1158                 :             :   return true;
    1159                 :             : }
    1160                 :             : 
    1161                 :             : /* Check the conditions on references inside each of components COMPS,
    1162                 :             :    and remove the unsuitable components from the list.  The new list
    1163                 :             :    of components is returned.  The conditions are described in 2) at
    1164                 :             :    the beginning of this file.  */
    1165                 :             : 
    1166                 :             : struct component *
    1167                 :      140347 : pcom_worker::filter_suitable_components (struct component *comps)
    1168                 :             : {
    1169                 :      140347 :   struct component **comp, *act;
    1170                 :             : 
    1171                 :      469537 :   for (comp = &comps; *comp; )
    1172                 :             :     {
    1173                 :      329190 :       act = *comp;
    1174                 :      329190 :       if (suitable_component_p (act))
    1175                 :      303903 :         comp = &act->next;
    1176                 :             :       else
    1177                 :             :         {
    1178                 :       25287 :           dref ref;
    1179                 :       25287 :           unsigned i;
    1180                 :             : 
    1181                 :       25287 :           *comp = act->next;
    1182                 :       64020 :           FOR_EACH_VEC_ELT (act->refs, i, ref)
    1183                 :       38733 :             free (ref);
    1184                 :       25287 :           delete act;
    1185                 :             :         }
    1186                 :             :     }
    1187                 :             : 
    1188                 :      140347 :   return comps;
    1189                 :             : }
    1190                 :             : 
    1191                 :             : /* Compares two drefs A and B by their offset and position.  Callback for
    1192                 :             :    qsort.  */
    1193                 :             : 
    1194                 :             : static int
    1195                 :      168155 : order_drefs (const void *a, const void *b)
    1196                 :             : {
    1197                 :      168155 :   const dref *const da = (const dref *) a;
    1198                 :      168155 :   const dref *const db = (const dref *) b;
    1199                 :      168155 :   int offcmp = wi::cmps ((*da)->offset, (*db)->offset);
    1200                 :             : 
    1201                 :      168155 :   if (offcmp != 0)
    1202                 :             :     return offcmp;
    1203                 :             : 
    1204                 :       95305 :   return (*da)->pos - (*db)->pos;
    1205                 :             : }
    1206                 :             : 
    1207                 :             : /* Compares two drefs A and B by their position.  Callback for qsort.  */
    1208                 :             : 
    1209                 :             : static int
    1210                 :          48 : order_drefs_by_pos (const void *a, const void *b)
    1211                 :             : {
    1212                 :          48 :   const dref *const da = (const dref *) a;
    1213                 :          48 :   const dref *const db = (const dref *) b;
    1214                 :             : 
    1215                 :          48 :   return (*da)->pos - (*db)->pos;
    1216                 :             : }
    1217                 :             : 
    1218                 :             : /* Returns root of the CHAIN.  */
    1219                 :             : 
    1220                 :             : static inline dref
    1221                 :       90688 : get_chain_root (chain_p chain)
    1222                 :             : {
    1223                 :      181376 :   return chain->refs[0];
    1224                 :             : }
    1225                 :             : 
    1226                 :             : /* Given CHAIN, returns the last write ref at DISTANCE, or NULL if it doesn't
    1227                 :             :    exist.  */
    1228                 :             : 
    1229                 :             : static inline dref
    1230                 :          85 : get_chain_last_write_at (chain_p chain, unsigned distance)
    1231                 :             : {
    1232                 :         297 :   for (unsigned i = chain->refs.length (); i > 0; i--)
    1233                 :         200 :     if (DR_IS_WRITE (chain->refs[i - 1]->ref)
    1234                 :         200 :         && distance == chain->refs[i - 1]->distance)
    1235                 :             :       return chain->refs[i - 1];
    1236                 :             : 
    1237                 :             :   return NULL;
    1238                 :             : }
    1239                 :             : 
    1240                 :             : /* Given CHAIN, returns the last write ref with the same distance before load
    1241                 :             :    at index LOAD_IDX, or NULL if it doesn't exist.  */
    1242                 :             : 
    1243                 :             : static inline dref
    1244                 :           5 : get_chain_last_write_before_load (chain_p chain, unsigned load_idx)
    1245                 :             : {
    1246                 :           5 :   gcc_assert (load_idx < chain->refs.length ());
    1247                 :             : 
    1248                 :           5 :   unsigned distance = chain->refs[load_idx]->distance;
    1249                 :             : 
    1250                 :           5 :   for (unsigned i = load_idx; i > 0; i--)
    1251                 :           5 :     if (DR_IS_WRITE (chain->refs[i - 1]->ref)
    1252                 :           5 :         && distance == chain->refs[i - 1]->distance)
    1253                 :             :       return chain->refs[i - 1];
    1254                 :             : 
    1255                 :             :   return NULL;
    1256                 :             : }
    1257                 :             : 
    1258                 :             : /* Adds REF to the chain CHAIN.  */
    1259                 :             : 
    1260                 :             : static void
    1261                 :       15735 : add_ref_to_chain (chain_p chain, dref ref)
    1262                 :             : {
    1263                 :       15735 :   dref root = get_chain_root (chain);
    1264                 :             : 
    1265                 :       15735 :   gcc_assert (wi::les_p (root->offset, ref->offset));
    1266                 :       15735 :   widest_int dist = ref->offset - root->offset;
    1267                 :       15735 :   gcc_assert (wi::fits_uhwi_p (dist));
    1268                 :             : 
    1269                 :       15735 :   chain->refs.safe_push (ref);
    1270                 :             : 
    1271                 :       15735 :   ref->distance = dist.to_uhwi ();
    1272                 :             : 
    1273                 :       15735 :   if (ref->distance >= chain->length)
    1274                 :             :     {
    1275                 :       15735 :       chain->length = ref->distance;
    1276                 :       15735 :       chain->has_max_use_after = false;
    1277                 :             :     }
    1278                 :             : 
    1279                 :             :   /* Promote this chain to CT_STORE_STORE if it has multiple stores.  */
    1280                 :       15735 :   if (DR_IS_WRITE (ref->ref))
    1281                 :          62 :     chain->type = CT_STORE_STORE;
    1282                 :             : 
    1283                 :             :   /* Don't set the flag for store-store chain since there is no use.  */
    1284                 :       15735 :   if (chain->type != CT_STORE_STORE
    1285                 :       15671 :       && ref->distance == chain->length
    1286                 :       15671 :       && ref->pos > root->pos)
    1287                 :        7245 :     chain->has_max_use_after = true;
    1288                 :             : 
    1289                 :       15735 :   chain->all_always_accessed &= ref->always_accessed;
    1290                 :       15735 : }
    1291                 :             : 
    1292                 :             : /* Returns the chain for invariant component COMP.  */
    1293                 :             : 
    1294                 :             : static chain_p
    1295                 :       12421 : make_invariant_chain (struct component *comp)
    1296                 :             : {
    1297                 :       12421 :   chain_p chain = new struct chain (CT_INVARIANT);
    1298                 :       12421 :   unsigned i;
    1299                 :       12421 :   dref ref;
    1300                 :             : 
    1301                 :       12421 :   chain->all_always_accessed = true;
    1302                 :             : 
    1303                 :       26852 :   FOR_EACH_VEC_ELT (comp->refs, i, ref)
    1304                 :             :     {
    1305                 :       14431 :       chain->refs.safe_push (ref);
    1306                 :       14431 :       chain->all_always_accessed &= ref->always_accessed;
    1307                 :             :     }
    1308                 :             : 
    1309                 :       12421 :   chain->inits = vNULL;
    1310                 :       12421 :   chain->finis = vNULL;
    1311                 :             : 
    1312                 :       12421 :   return chain;
    1313                 :             : }
    1314                 :             : 
    1315                 :             : /* Make a new chain of type TYPE rooted at REF.  */
    1316                 :             : 
    1317                 :             : static chain_p
    1318                 :       48270 : make_rooted_chain (dref ref, enum chain_type type)
    1319                 :             : {
    1320                 :       48270 :   chain_p chain = new struct chain (type);
    1321                 :             : 
    1322                 :       48270 :   chain->refs.safe_push (ref);
    1323                 :       48270 :   chain->all_always_accessed = ref->always_accessed;
    1324                 :       48270 :   ref->distance = 0;
    1325                 :             : 
    1326                 :       48270 :   chain->inits = vNULL;
    1327                 :       48270 :   chain->finis = vNULL;
    1328                 :             : 
    1329                 :       48270 :   return chain;
    1330                 :             : }
    1331                 :             : 
    1332                 :             : /* Returns true if CHAIN is not trivial.  */
    1333                 :             : 
    1334                 :             : static bool
    1335                 :       77546 : nontrivial_chain_p (chain_p chain)
    1336                 :             : {
    1337                 :       48270 :   return chain != NULL && chain->refs.length () > 1;
    1338                 :             : }
    1339                 :             : 
    1340                 :             : /* Returns the ssa name that contains the value of REF, or NULL_TREE if there
    1341                 :             :    is no such name.  */
    1342                 :             : 
    1343                 :             : static tree
    1344                 :      116210 : name_for_ref (dref ref)
    1345                 :             : {
    1346                 :      116210 :   tree name;
    1347                 :             : 
    1348                 :      116210 :   if (is_gimple_assign (ref->stmt))
    1349                 :             :     {
    1350                 :      116186 :       if (!ref->ref || DR_IS_READ (ref->ref))
    1351                 :      116186 :         name = gimple_assign_lhs (ref->stmt);
    1352                 :             :       else
    1353                 :           0 :         name = gimple_assign_rhs1 (ref->stmt);
    1354                 :             :     }
    1355                 :             :   else
    1356                 :          24 :     name = PHI_RESULT (ref->stmt);
    1357                 :             : 
    1358                 :      116210 :   return (TREE_CODE (name) == SSA_NAME ? name : NULL_TREE);
    1359                 :             : }
    1360                 :             : 
    1361                 :             : /* Returns true if REF is a valid initializer for ROOT with given DISTANCE (in
    1362                 :             :    iterations of the innermost enclosing loop).  */
    1363                 :             : 
    1364                 :             : bool
    1365                 :          20 : pcom_worker::valid_initializer_p (struct data_reference *ref, unsigned distance,
    1366                 :             :                                   struct data_reference *root)
    1367                 :             : {
    1368                 :          80 :   aff_tree diff, base, step;
    1369                 :             :   poly_widest_int off;
    1370                 :             : 
    1371                 :             :   /* Both REF and ROOT must be accessing the same object.  */
    1372                 :          20 :   if (!operand_equal_p (DR_BASE_ADDRESS (ref), DR_BASE_ADDRESS (root), 0))
    1373                 :             :     return false;
    1374                 :             : 
    1375                 :             :   /* The initializer is defined outside of loop, hence its address must be
    1376                 :             :      invariant inside the loop.  */
    1377                 :          20 :   gcc_assert (integer_zerop (DR_STEP (ref)));
    1378                 :             : 
    1379                 :             :   /* If the address of the reference is invariant, initializer must access
    1380                 :             :      exactly the same location.  */
    1381                 :          20 :   if (integer_zerop (DR_STEP (root)))
    1382                 :           0 :     return (operand_equal_p (DR_OFFSET (ref), DR_OFFSET (root), 0)
    1383                 :           0 :             && operand_equal_p (DR_INIT (ref), DR_INIT (root), 0));
    1384                 :             : 
    1385                 :             :   /* Verify that this index of REF is equal to the root's index at
    1386                 :             :      -DISTANCE-th iteration.  */
    1387                 :          20 :   aff_combination_dr_offset (root, &diff);
    1388                 :          20 :   aff_combination_dr_offset (ref, &base);
    1389                 :          20 :   aff_combination_scale (&base, -1);
    1390                 :          20 :   aff_combination_add (&diff, &base);
    1391                 :             : 
    1392                 :          20 :   tree_to_aff_combination_expand (DR_STEP (root), TREE_TYPE (DR_STEP (root)),
    1393                 :             :                                   &step, &m_cache);
    1394                 :          20 :   if (!aff_combination_constant_multiple_p (&diff, &step, &off))
    1395                 :             :     return false;
    1396                 :             : 
    1397                 :          20 :   if (maybe_ne (off, distance))
    1398                 :             :     return false;
    1399                 :             : 
    1400                 :             :   return true;
    1401                 :          20 : }
    1402                 :             : 
    1403                 :             : /* Finds looparound phi node of loop that copies the value of REF, and if its
    1404                 :             :    initial value is correct (equal to initial value of REF shifted by one
    1405                 :             :    iteration), returns the phi node.  Otherwise, NULL_TREE is returned.  ROOT
    1406                 :             :    is the root of the current chain.  */
    1407                 :             : 
    1408                 :             : gphi *
    1409                 :       31004 : pcom_worker::find_looparound_phi (dref ref, dref root)
    1410                 :             : {
    1411                 :       31004 :   tree name, init, init_ref;
    1412                 :       31004 :   gimple *init_stmt;
    1413                 :       31004 :   edge latch = loop_latch_edge (m_loop);
    1414                 :       31004 :   struct data_reference init_dr;
    1415                 :       31004 :   gphi_iterator psi;
    1416                 :             : 
    1417                 :       31004 :   if (is_gimple_assign (ref->stmt))
    1418                 :             :     {
    1419                 :       30991 :       if (DR_IS_READ (ref->ref))
    1420                 :       28796 :         name = gimple_assign_lhs (ref->stmt);
    1421                 :             :       else
    1422                 :        2195 :         name = gimple_assign_rhs1 (ref->stmt);
    1423                 :             :     }
    1424                 :             :   else
    1425                 :          13 :     name = PHI_RESULT (ref->stmt);
    1426                 :       31004 :   if (!name)
    1427                 :             :     return NULL;
    1428                 :             : 
    1429                 :       31004 :   tree entry_vuse = NULL_TREE;
    1430                 :       31004 :   gphi *phi = NULL;
    1431                 :      291046 :   for (psi = gsi_start_phis (m_loop->header); !gsi_end_p (psi); gsi_next (&psi))
    1432                 :             :     {
    1433                 :      260066 :       gphi *p = psi.phi ();
    1434                 :      260066 :       if (PHI_ARG_DEF_FROM_EDGE (p, latch) == name)
    1435                 :             :         phi = p;
    1436                 :      520084 :       else if (virtual_operand_p (gimple_phi_result (p)))
    1437                 :       21030 :         entry_vuse = PHI_ARG_DEF_FROM_EDGE (p, loop_preheader_edge (m_loop));
    1438                 :      260066 :       if (phi && entry_vuse)
    1439                 :             :         break;
    1440                 :             :     }
    1441                 :       31004 :   if (!phi || !entry_vuse)
    1442                 :             :     return NULL;
    1443                 :             : 
    1444                 :          24 :   init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (m_loop));
    1445                 :          24 :   if (TREE_CODE (init) != SSA_NAME)
    1446                 :             :     return NULL;
    1447                 :          22 :   init_stmt = SSA_NAME_DEF_STMT (init);
    1448                 :          22 :   if (gimple_code (init_stmt) != GIMPLE_ASSIGN)
    1449                 :             :     return NULL;
    1450                 :          20 :   gcc_assert (gimple_assign_lhs (init_stmt) == init);
    1451                 :             : 
    1452                 :          20 :   init_ref = gimple_assign_rhs1 (init_stmt);
    1453                 :          20 :   if (!REFERENCE_CLASS_P (init_ref)
    1454                 :          20 :       && !DECL_P (init_ref))
    1455                 :             :     return NULL;
    1456                 :             : 
    1457                 :             :   /* Analyze the behavior of INIT_REF with respect to LOOP (innermost
    1458                 :             :      loop enclosing PHI).  */
    1459                 :          20 :   memset (&init_dr, 0, sizeof (struct data_reference));
    1460                 :          20 :   DR_REF (&init_dr) = init_ref;
    1461                 :          20 :   DR_STMT (&init_dr) = phi;
    1462                 :          20 :   if (!dr_analyze_innermost (&DR_INNERMOST (&init_dr), init_ref, m_loop,
    1463                 :          20 :                              init_stmt))
    1464                 :             :     return NULL;
    1465                 :             : 
    1466                 :          20 :   if (!valid_initializer_p (&init_dr, ref->distance + 1, root->ref))
    1467                 :             :     return NULL;
    1468                 :             : 
    1469                 :             :   /* Make sure nothing clobbers the location we re-use the initial value
    1470                 :             :      from.  */
    1471                 :          40 :   if (entry_vuse != gimple_vuse (init_stmt))
    1472                 :             :     {
    1473                 :           7 :       ao_ref ref;
    1474                 :           7 :       ao_ref_init (&ref, init_ref);
    1475                 :           7 :       unsigned limit = param_sccvn_max_alias_queries_per_access;
    1476                 :           7 :       tree vdef = entry_vuse;
    1477                 :           7 :       do
    1478                 :             :         {
    1479                 :           7 :           gimple *def = SSA_NAME_DEF_STMT (vdef);
    1480                 :           7 :           if (limit-- == 0 || gimple_code (def) == GIMPLE_PHI)
    1481                 :           7 :             return NULL;
    1482                 :           7 :           if (stmt_may_clobber_ref_p_1 (def, &ref))
    1483                 :             :             /* When the stmt is an assign to init_ref we could in theory
    1484                 :             :                use its RHS for the initial value of the looparound PHI
    1485                 :             :                we replace in prepare_initializers_chain, but we have
    1486                 :             :                no convenient place to store this info at the moment.  */
    1487                 :             :             return NULL;
    1488                 :           0 :           vdef = gimple_vuse (def);
    1489                 :             :         }
    1490                 :           0 :       while (vdef != gimple_vuse (init_stmt));
    1491                 :             :     }
    1492                 :             : 
    1493                 :             :   return phi;
    1494                 :             : }
    1495                 :             : 
    1496                 :             : /* Adds a reference for the looparound copy of REF in PHI to CHAIN.  */
    1497                 :             : 
    1498                 :             : static void
    1499                 :          13 : insert_looparound_copy (chain_p chain, dref ref, gphi *phi)
    1500                 :             : {
    1501                 :          13 :   dref nw = XCNEW (class dref_d), aref;
    1502                 :          13 :   unsigned i;
    1503                 :             : 
    1504                 :          13 :   nw->stmt = phi;
    1505                 :          13 :   nw->distance = ref->distance + 1;
    1506                 :          13 :   nw->always_accessed = 1;
    1507                 :             : 
    1508                 :          50 :   FOR_EACH_VEC_ELT (chain->refs, i, aref)
    1509                 :          38 :     if (aref->distance >= nw->distance)
    1510                 :             :       break;
    1511                 :          13 :   chain->refs.safe_insert (i, nw);
    1512                 :             : 
    1513                 :          13 :   if (nw->distance > chain->length)
    1514                 :             :     {
    1515                 :          12 :       chain->length = nw->distance;
    1516                 :          12 :       chain->has_max_use_after = false;
    1517                 :             :     }
    1518                 :          13 : }
    1519                 :             : 
    1520                 :             : /* For references in CHAIN that are copied around the loop (created previously
    1521                 :             :    by PRE, or by user), add the results of such copies to the chain.  This
    1522                 :             :    enables us to remove the copies by unrolling, and may need less registers
    1523                 :             :    (also, it may allow us to combine chains together).  */
    1524                 :             : 
    1525                 :             : void
    1526                 :       15372 : pcom_worker::add_looparound_copies (chain_p chain)
    1527                 :             : {
    1528                 :       15372 :   unsigned i;
    1529                 :       15372 :   dref ref, root = get_chain_root (chain);
    1530                 :       15372 :   gphi *phi;
    1531                 :             : 
    1532                 :       15372 :   if (chain->type == CT_STORE_STORE)
    1533                 :       15372 :     return;
    1534                 :             : 
    1535                 :       46327 :   FOR_EACH_VEC_ELT (chain->refs, i, ref)
    1536                 :             :     {
    1537                 :       31004 :       phi = find_looparound_phi (ref, root);
    1538                 :       31004 :       if (!phi)
    1539                 :       30991 :         continue;
    1540                 :             : 
    1541                 :          13 :       bitmap_set_bit (m_looparound_phis, SSA_NAME_VERSION (PHI_RESULT (phi)));
    1542                 :          13 :       insert_looparound_copy (chain, ref, phi);
    1543                 :             :     }
    1544                 :             : }
    1545                 :             : 
    1546                 :             : /* Find roots of the values and determine distances in the component COMP.
    1547                 :             :    The references are redistributed into chains.  */
    1548                 :             : 
    1549                 :             : void
    1550                 :      303903 : pcom_worker::determine_roots_comp (struct component *comp)
    1551                 :             : {
    1552                 :      303903 :   unsigned i;
    1553                 :      303903 :   dref a;
    1554                 :      303903 :   chain_p chain = NULL;
    1555                 :      303903 :   widest_int last_ofs = 0;
    1556                 :      303903 :   enum chain_type type;
    1557                 :             : 
    1558                 :             :   /* Invariants are handled specially.  */
    1559                 :      303903 :   if (comp->comp_step == RS_INVARIANT)
    1560                 :             :     {
    1561                 :       12421 :       chain = make_invariant_chain (comp);
    1562                 :       12421 :       m_chains.safe_push (chain);
    1563                 :       12421 :       return;
    1564                 :             :     }
    1565                 :             : 
    1566                 :             :   /* Trivial component.  */
    1567                 :      291482 :   if (comp->refs.length () <= 1)
    1568                 :             :     {
    1569                 :      262206 :       if (comp->refs.length () == 1)
    1570                 :             :         {
    1571                 :      262206 :           free (comp->refs[0]);
    1572                 :      262206 :           comp->refs.truncate (0);
    1573                 :             :         }
    1574                 :      262206 :       return;
    1575                 :             :     }
    1576                 :             : 
    1577                 :       29276 :   comp->refs.qsort (order_drefs);
    1578                 :             : 
    1579                 :             :   /* For Store-Store chain, we only support load if it is dominated by a
    1580                 :             :      store statement in the same iteration of loop.  */
    1581                 :       29276 :   if (comp->eliminate_store_p)
    1582                 :       33048 :     for (a = NULL, i = 0; i < comp->refs.length (); i++)
    1583                 :             :       {
    1584                 :       16468 :         if (DR_IS_WRITE (comp->refs[i]->ref))
    1585                 :             :           a = comp->refs[i];
    1586                 :       14905 :         else if (a == NULL || a->offset != comp->refs[i]->offset)
    1587                 :             :           {
    1588                 :             :             /* If there is load that is not dominated by a store in the
    1589                 :             :                same iteration of loop, clear the flag so no Store-Store
    1590                 :             :                chain is generated for this component.  */
    1591                 :       14892 :             comp->eliminate_store_p = false;
    1592                 :       14892 :             break;
    1593                 :             :           }
    1594                 :             :       }
    1595                 :             : 
    1596                 :             :   /* Determine roots and create chains for components.  */
    1597                 :       93281 :   FOR_EACH_VEC_ELT (comp->refs, i, a)
    1598                 :             :     {
    1599                 :      176280 :       if (!chain
    1600                 :       34729 :           || (chain->type == CT_LOAD && DR_IS_WRITE (a->ref))
    1601                 :       19760 :           || (!comp->eliminate_store_p && DR_IS_WRITE (a->ref))
    1602                 :      162739 :           || wi::leu_p (MAX_DISTANCE, a->offset - last_ofs))
    1603                 :             :         {
    1604                 :       48270 :           if (nontrivial_chain_p (chain))
    1605                 :             :             {
    1606                 :         905 :               add_looparound_copies (chain);
    1607                 :         905 :               m_chains.safe_push (chain);
    1608                 :             :             }
    1609                 :             :           else
    1610                 :       47365 :             release_chain (chain);
    1611                 :             : 
    1612                 :             :           /* Determine type of the chain.  If the root reference is a load,
    1613                 :             :              this can only be a CT_LOAD chain; other chains are intialized
    1614                 :             :              to CT_STORE_LOAD and might be promoted to CT_STORE_STORE when
    1615                 :             :              new reference is added.  */
    1616                 :       48270 :           type = DR_IS_READ (a->ref) ? CT_LOAD : CT_STORE_LOAD;
    1617                 :       48270 :           chain = make_rooted_chain (a, type);
    1618                 :       48270 :           last_ofs = a->offset;
    1619                 :       48270 :           continue;
    1620                 :             :         }
    1621                 :             : 
    1622                 :       15735 :       add_ref_to_chain (chain, a);
    1623                 :             :     }
    1624                 :             : 
    1625                 :       29276 :   if (nontrivial_chain_p (chain))
    1626                 :             :     {
    1627                 :       14467 :       add_looparound_copies (chain);
    1628                 :       14467 :       m_chains.safe_push (chain);
    1629                 :             :     }
    1630                 :             :   else
    1631                 :       14809 :     release_chain (chain);
    1632                 :      303903 : }
    1633                 :             : 
    1634                 :             : /* Find roots of the values and determine distances in components COMPS, and
    1635                 :             :    separates the references to chains.  */
    1636                 :             : 
    1637                 :             : void
    1638                 :      140347 : pcom_worker::determine_roots (struct component *comps)
    1639                 :             : {
    1640                 :      140347 :   struct component *comp;
    1641                 :             : 
    1642                 :      444250 :   for (comp = comps; comp; comp = comp->next)
    1643                 :      303903 :     determine_roots_comp (comp);
    1644                 :      140347 : }
    1645                 :             : 
    1646                 :             : /* Replace the reference in statement STMT with temporary variable
    1647                 :             :    NEW_TREE.  If SET is true, NEW_TREE is instead initialized to the value of
    1648                 :             :    the reference in the statement.  IN_LHS is true if the reference
    1649                 :             :    is in the lhs of STMT, false if it is in rhs.  */
    1650                 :             : 
    1651                 :             : static void
    1652                 :       33533 : replace_ref_with (gimple *stmt, tree new_tree, bool set, bool in_lhs)
    1653                 :             : {
    1654                 :       33533 :   tree val;
    1655                 :       33533 :   gassign *new_stmt;
    1656                 :       33533 :   gimple_stmt_iterator bsi, psi;
    1657                 :             : 
    1658                 :       33533 :   if (gimple_code (stmt) == GIMPLE_PHI)
    1659                 :             :     {
    1660                 :           1 :       gcc_assert (!in_lhs && !set);
    1661                 :             : 
    1662                 :           1 :       val = PHI_RESULT (stmt);
    1663                 :           1 :       bsi = gsi_after_labels (gimple_bb (stmt));
    1664                 :           1 :       psi = gsi_for_stmt (stmt);
    1665                 :           1 :       remove_phi_node (&psi, false);
    1666                 :             : 
    1667                 :             :       /* Turn the phi node into GIMPLE_ASSIGN.  */
    1668                 :           1 :       new_stmt = gimple_build_assign (val, new_tree);
    1669                 :           1 :       gsi_insert_before (&bsi, new_stmt, GSI_NEW_STMT);
    1670                 :       17094 :       return;
    1671                 :             :     }
    1672                 :             : 
    1673                 :             :   /* Since the reference is of gimple_reg type, it should only
    1674                 :             :      appear as lhs or rhs of modify statement.  */
    1675                 :       33532 :   gcc_assert (is_gimple_assign (stmt));
    1676                 :             : 
    1677                 :       33532 :   bsi = gsi_for_stmt (stmt);
    1678                 :             : 
    1679                 :             :   /* If we do not need to initialize NEW_TREE, just replace the use of OLD.  */
    1680                 :       33532 :   if (!set)
    1681                 :             :     {
    1682                 :       17092 :       gcc_assert (!in_lhs);
    1683                 :       17092 :       gimple_assign_set_rhs_from_tree (&bsi, new_tree);
    1684                 :       17092 :       stmt = gsi_stmt (bsi);
    1685                 :       17092 :       update_stmt (stmt);
    1686                 :       17092 :       return;
    1687                 :             :     }
    1688                 :             : 
    1689                 :       16440 :   if (in_lhs)
    1690                 :             :     {
    1691                 :             :       /* We have statement
    1692                 :             : 
    1693                 :             :          OLD = VAL
    1694                 :             : 
    1695                 :             :          If OLD is a memory reference, then VAL is gimple_val, and we transform
    1696                 :             :          this to
    1697                 :             : 
    1698                 :             :          OLD = VAL
    1699                 :             :          NEW = VAL
    1700                 :             : 
    1701                 :             :          Otherwise, we are replacing a combination chain,
    1702                 :             :          VAL is the expression that performs the combination, and OLD is an
    1703                 :             :          SSA name.  In this case, we transform the assignment to
    1704                 :             : 
    1705                 :             :          OLD = VAL
    1706                 :             :          NEW = OLD
    1707                 :             : 
    1708                 :             :          */
    1709                 :             : 
    1710                 :        3659 :       val = gimple_assign_lhs (stmt);
    1711                 :        3659 :       if (TREE_CODE (val) != SSA_NAME)
    1712                 :             :         {
    1713                 :        3640 :           val = gimple_assign_rhs1 (stmt);
    1714                 :        3640 :           gcc_assert (gimple_assign_single_p (stmt));
    1715                 :        3640 :           if (TREE_CLOBBER_P (val))
    1716                 :           0 :             val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (new_tree));
    1717                 :             :           else
    1718                 :        3640 :             gcc_assert (gimple_assign_copy_p (stmt));
    1719                 :             :         }
    1720                 :             :     }
    1721                 :             :   else
    1722                 :             :     {
    1723                 :             :       /* VAL = OLD
    1724                 :             : 
    1725                 :             :          is transformed to
    1726                 :             : 
    1727                 :             :          VAL = OLD
    1728                 :             :          NEW = VAL  */
    1729                 :             : 
    1730                 :       12781 :       val = gimple_assign_lhs (stmt);
    1731                 :             :     }
    1732                 :             : 
    1733                 :       16440 :   new_stmt = gimple_build_assign (new_tree, unshare_expr (val));
    1734                 :       16440 :   gsi_insert_after (&bsi, new_stmt, GSI_NEW_STMT);
    1735                 :             : }
    1736                 :             : 
    1737                 :             : /* Returns a memory reference to DR in the (NITERS + ITER)-th iteration
    1738                 :             :    of the loop it was analyzed in.  Append init stmts to STMTS.  */
    1739                 :             : 
    1740                 :             : static tree
    1741                 :       22113 : ref_at_iteration (data_reference_p dr, int iter,
    1742                 :             :                   gimple_seq *stmts, tree niters = NULL_TREE)
    1743                 :             : {
    1744                 :       22113 :   tree off = DR_OFFSET (dr);
    1745                 :       22113 :   tree coff = DR_INIT (dr);
    1746                 :       22113 :   tree ref = DR_REF (dr);
    1747                 :       22113 :   enum tree_code ref_code = ERROR_MARK;
    1748                 :       22113 :   tree ref_type = NULL_TREE;
    1749                 :       22113 :   tree ref_op1 = NULL_TREE;
    1750                 :       22113 :   tree ref_op2 = NULL_TREE;
    1751                 :       22113 :   tree new_offset;
    1752                 :             : 
    1753                 :       22113 :   if (iter != 0)
    1754                 :             :     {
    1755                 :       22080 :       new_offset = size_binop (MULT_EXPR, DR_STEP (dr), ssize_int (iter));
    1756                 :       22080 :       if (TREE_CODE (new_offset) == INTEGER_CST)
    1757                 :       22074 :         coff = size_binop (PLUS_EXPR, coff, new_offset);
    1758                 :             :       else
    1759                 :           6 :         off = size_binop (PLUS_EXPR, off, new_offset);
    1760                 :             :     }
    1761                 :             : 
    1762                 :       22113 :   if (niters != NULL_TREE)
    1763                 :             :     {
    1764                 :          61 :       niters = fold_convert (ssizetype, niters);
    1765                 :          61 :       new_offset = size_binop (MULT_EXPR, DR_STEP (dr), niters);
    1766                 :          61 :       if (TREE_CODE (niters) == INTEGER_CST)
    1767                 :          35 :         coff = size_binop (PLUS_EXPR, coff, new_offset);
    1768                 :             :       else
    1769                 :          26 :         off = size_binop (PLUS_EXPR, off, new_offset);
    1770                 :             :     }
    1771                 :             : 
    1772                 :             :   /* While data-ref analysis punts on bit offsets it still handles
    1773                 :             :      bitfield accesses at byte boundaries.  Cope with that.  Note that
    1774                 :             :      if the bitfield object also starts at a byte-boundary we can simply
    1775                 :             :      replicate the COMPONENT_REF, but we have to subtract the component's
    1776                 :             :      byte-offset from the MEM_REF address first.
    1777                 :             :      Otherwise we simply build a BIT_FIELD_REF knowing that the bits
    1778                 :             :      start at offset zero.  */
    1779                 :       22113 :   if (TREE_CODE (ref) == COMPONENT_REF
    1780                 :       22113 :       && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))
    1781                 :             :     {
    1782                 :          33 :       unsigned HOST_WIDE_INT boff;
    1783                 :          33 :       tree field = TREE_OPERAND (ref, 1);
    1784                 :          33 :       tree offset = component_ref_field_offset (ref);
    1785                 :          33 :       ref_type = TREE_TYPE (ref);
    1786                 :          33 :       boff = tree_to_uhwi (DECL_FIELD_BIT_OFFSET (field));
    1787                 :             :       /* This can occur in Ada.  See the comment in get_bit_range.  */
    1788                 :          33 :       if (boff % BITS_PER_UNIT != 0
    1789                 :          33 :           || !tree_fits_uhwi_p (offset))
    1790                 :             :         {
    1791                 :           0 :           ref_code = BIT_FIELD_REF;
    1792                 :           0 :           ref_op1 = DECL_SIZE (field);
    1793                 :           0 :           ref_op2 = bitsize_zero_node;
    1794                 :             :         }
    1795                 :             :       else
    1796                 :             :         {
    1797                 :          33 :           boff >>= LOG2_BITS_PER_UNIT;
    1798                 :          33 :           boff += tree_to_uhwi (offset);
    1799                 :          33 :           coff = size_binop (MINUS_EXPR, coff, ssize_int (boff));
    1800                 :          33 :           ref_code = COMPONENT_REF;
    1801                 :          33 :           ref_op1 = field;
    1802                 :          33 :           ref_op2 = TREE_OPERAND (ref, 2);
    1803                 :          33 :           ref = TREE_OPERAND (ref, 0);
    1804                 :             :         }
    1805                 :             :     }
    1806                 :             :   /* We may not associate the constant offset across the pointer plus
    1807                 :             :      expression because that might form a pointer to before the object
    1808                 :             :      then.  But for some cases we can retain that to allow tree_could_trap_p
    1809                 :             :      to return false - see gcc.dg/tree-ssa/predcom-1.c  */
    1810                 :       22113 :   tree addr, alias_ptr;
    1811                 :       22113 :   if (integer_zerop  (off))
    1812                 :             :     {
    1813                 :       21738 :       alias_ptr = fold_convert (reference_alias_ptr_type (ref), coff);
    1814                 :       21738 :       addr = DR_BASE_ADDRESS (dr);
    1815                 :             :     }
    1816                 :             :   else
    1817                 :             :     {
    1818                 :         375 :       alias_ptr = build_zero_cst (reference_alias_ptr_type (ref));
    1819                 :         375 :       off = size_binop (PLUS_EXPR, off, coff);
    1820                 :         375 :       addr = fold_build_pointer_plus (DR_BASE_ADDRESS (dr), off);
    1821                 :             :     }
    1822                 :       22113 :   addr = force_gimple_operand_1 (unshare_expr (addr), stmts,
    1823                 :             :                                  is_gimple_mem_ref_addr, NULL_TREE);
    1824                 :       22113 :   tree type = build_aligned_type (TREE_TYPE (ref),
    1825                 :             :                                   get_object_alignment (ref));
    1826                 :       22113 :   ref = build2 (MEM_REF, type, addr, alias_ptr);
    1827                 :       22113 :   if (ref_type)
    1828                 :          33 :     ref = build3 (ref_code, ref_type, ref, ref_op1, ref_op2);
    1829                 :       22113 :   return ref;
    1830                 :             : }
    1831                 :             : 
    1832                 :             : /* Get the initialization expression for the INDEX-th temporary variable
    1833                 :             :    of CHAIN.  */
    1834                 :             : 
    1835                 :             : static tree
    1836                 :        9444 : get_init_expr (chain_p chain, unsigned index)
    1837                 :             : {
    1838                 :        9444 :   if (chain->type == CT_COMBINATION)
    1839                 :             :     {
    1840                 :          70 :       tree e1 = get_init_expr (chain->ch1, index);
    1841                 :          70 :       tree e2 = get_init_expr (chain->ch2, index);
    1842                 :             : 
    1843                 :          70 :       return fold_build2 (chain->op, chain->rslt_type, e1, e2);
    1844                 :             :     }
    1845                 :             :   else
    1846                 :        9374 :     return chain->inits[index];
    1847                 :             : }
    1848                 :             : 
    1849                 :             : /* Returns a new temporary variable used for the I-th variable carrying
    1850                 :             :    value of REF.  The variable's uid is marked in TMP_VARS.  */
    1851                 :             : 
    1852                 :             : static tree
    1853                 :       17934 : predcom_tmp_var (tree ref, unsigned i, bitmap tmp_vars)
    1854                 :             : {
    1855                 :       17934 :   tree type = TREE_TYPE (ref);
    1856                 :             :   /* We never access the components of the temporary variable in predictive
    1857                 :             :      commoning.  */
    1858                 :       17934 :   tree var = create_tmp_reg (type, get_lsm_tmp_name (ref, i));
    1859                 :       17934 :   bitmap_set_bit (tmp_vars, DECL_UID (var));
    1860                 :       17934 :   return var;
    1861                 :             : }
    1862                 :             : 
    1863                 :             : /* Creates the variables for CHAIN, as well as phi nodes for them and
    1864                 :             :    initialization on entry to LOOP.  Uids of the newly created
    1865                 :             :    temporary variables are marked in TMP_VARS.  */
    1866                 :             : 
    1867                 :             : static void
    1868                 :       14986 : initialize_root_vars (class loop *loop, chain_p chain, bitmap tmp_vars)
    1869                 :             : {
    1870                 :       14986 :   unsigned i;
    1871                 :       14986 :   unsigned n = chain->length;
    1872                 :       14986 :   dref root = get_chain_root (chain);
    1873                 :       14986 :   bool reuse_first = !chain->has_max_use_after;
    1874                 :       14986 :   tree ref, init, var, next;
    1875                 :       14986 :   gphi *phi;
    1876                 :       14986 :   gimple_seq stmts;
    1877                 :       14986 :   edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
    1878                 :             : 
    1879                 :             :   /* If N == 0, then all the references are within the single iteration.  And
    1880                 :             :      since this is an nonempty chain, reuse_first cannot be true.  */
    1881                 :       14986 :   gcc_assert (n > 0 || !reuse_first);
    1882                 :             : 
    1883                 :       14986 :   chain->vars.create (n + 1);
    1884                 :             : 
    1885                 :       14986 :   if (chain->type == CT_COMBINATION)
    1886                 :          19 :     ref = gimple_assign_lhs (root->stmt);
    1887                 :             :   else
    1888                 :       14967 :     ref = DR_REF (root->ref);
    1889                 :             : 
    1890                 :       46171 :   for (i = 0; i < n + (reuse_first ? 0 : 1); i++)
    1891                 :             :     {
    1892                 :       16196 :       var = predcom_tmp_var (ref, i, tmp_vars);
    1893                 :       16196 :       chain->vars.quick_push (var);
    1894                 :             :     }
    1895                 :       14986 :   if (reuse_first)
    1896                 :        8055 :     chain->vars.quick_push (chain->vars[0]);
    1897                 :             : 
    1898                 :       39237 :   FOR_EACH_VEC_ELT (chain->vars, i, var)
    1899                 :       24251 :     chain->vars[i] = make_ssa_name (var);
    1900                 :             : 
    1901                 :       24251 :   for (i = 0; i < n; i++)
    1902                 :             :     {
    1903                 :        9265 :       var = chain->vars[i];
    1904                 :        9265 :       next = chain->vars[i + 1];
    1905                 :        9265 :       init = get_init_expr (chain, i);
    1906                 :             : 
    1907                 :        9265 :       init = force_gimple_operand (init, &stmts, true, NULL_TREE);
    1908                 :        9265 :       if (stmts)
    1909                 :        9264 :         gsi_insert_seq_on_edge_immediate (entry, stmts);
    1910                 :             : 
    1911                 :        9265 :       phi = create_phi_node (var, loop->header);
    1912                 :        9265 :       add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
    1913                 :        9265 :       add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
    1914                 :             :     }
    1915                 :       14986 : }
    1916                 :             : 
    1917                 :             : /* For inter-iteration store elimination CHAIN in LOOP, returns true if
    1918                 :             :    all stores to be eliminated store loop invariant values into memory.
    1919                 :             :    In this case, we can use these invariant values directly after LOOP.  */
    1920                 :             : 
    1921                 :             : static bool
    1922                 :          33 : is_inv_store_elimination_chain (class loop *loop, chain_p chain)
    1923                 :             : {
    1924                 :          33 :   if (chain->length == 0 || chain->type != CT_STORE_STORE)
    1925                 :             :     return false;
    1926                 :             : 
    1927                 :          33 :   gcc_assert (!chain->has_max_use_after);
    1928                 :             : 
    1929                 :             :   /* If loop iterates for unknown times or fewer times than chain->length,
    1930                 :             :      we still need to setup root variable and propagate it with PHI node.  */
    1931                 :          33 :   tree niters = number_of_latch_executions (loop);
    1932                 :          33 :   if (TREE_CODE (niters) != INTEGER_CST
    1933                 :          33 :       || wi::leu_p (wi::to_wide (niters), chain->length))
    1934                 :          11 :     return false;
    1935                 :             : 
    1936                 :             :   /* Check stores in chain for elimination if they only store loop invariant
    1937                 :             :      values.  */
    1938                 :          44 :   for (unsigned i = 0; i < chain->length; i++)
    1939                 :             :     {
    1940                 :          34 :       dref a = get_chain_last_write_at (chain, i);
    1941                 :          34 :       if (a == NULL)
    1942                 :           6 :         continue;
    1943                 :             : 
    1944                 :          28 :       gimple *def_stmt, *stmt = a->stmt;
    1945                 :          28 :       if (!gimple_assign_single_p (stmt))
    1946                 :             :         return false;
    1947                 :             : 
    1948                 :          28 :       tree val = gimple_assign_rhs1 (stmt);
    1949                 :          28 :       if (TREE_CLOBBER_P (val))
    1950                 :             :         return false;
    1951                 :             : 
    1952                 :          28 :       if (CONSTANT_CLASS_P (val))
    1953                 :          16 :         continue;
    1954                 :             : 
    1955                 :          12 :       if (TREE_CODE (val) != SSA_NAME)
    1956                 :             :         return false;
    1957                 :             : 
    1958                 :          12 :       def_stmt = SSA_NAME_DEF_STMT (val);
    1959                 :          12 :       if (gimple_nop_p (def_stmt))
    1960                 :           0 :         continue;
    1961                 :             : 
    1962                 :          12 :       if (flow_bb_inside_loop_p (loop, gimple_bb (def_stmt)))
    1963                 :             :         return false;
    1964                 :             :     }
    1965                 :             :   return true;
    1966                 :             : }
    1967                 :             : 
    1968                 :             : /* Creates root variables for store elimination CHAIN in which stores for
    1969                 :             :    elimination only store loop invariant values.  In this case, we neither
    1970                 :             :    need to load root variables before loop nor propagate it with PHI nodes.  */
    1971                 :             : 
    1972                 :             : static void
    1973                 :          10 : initialize_root_vars_store_elim_1 (chain_p chain)
    1974                 :             : {
    1975                 :          10 :   tree var;
    1976                 :          10 :   unsigned i, n = chain->length;
    1977                 :             : 
    1978                 :          10 :   chain->vars.create (n);
    1979                 :          10 :   chain->vars.safe_grow_cleared (n, true);
    1980                 :             : 
    1981                 :             :   /* Initialize root value for eliminated stores at each distance.  */
    1982                 :          32 :   for (i = 0; i < n; i++)
    1983                 :             :     {
    1984                 :          22 :       dref a = get_chain_last_write_at (chain, i);
    1985                 :          22 :       if (a == NULL)
    1986                 :           6 :         continue;
    1987                 :             : 
    1988                 :          16 :       var = gimple_assign_rhs1 (a->stmt);
    1989                 :          16 :       chain->vars[a->distance] = var;
    1990                 :             :     }
    1991                 :             : 
    1992                 :             :   /* We don't propagate values with PHI nodes, so manually propagate value
    1993                 :             :      to bubble positions.  */
    1994                 :          10 :   var = chain->vars[0];
    1995                 :          22 :   for (i = 1; i < n; i++)
    1996                 :             :     {
    1997                 :          12 :       if (chain->vars[i] != NULL_TREE)
    1998                 :             :         {
    1999                 :           6 :           var = chain->vars[i];
    2000                 :           6 :           continue;
    2001                 :             :         }
    2002                 :           6 :       chain->vars[i] = var;
    2003                 :             :     }
    2004                 :             : 
    2005                 :             :   /* Revert the vector.  */
    2006                 :          17 :   for (i = 0; i < n / 2; i++)
    2007                 :           7 :     std::swap (chain->vars[i], chain->vars[n - i - 1]);
    2008                 :          10 : }
    2009                 :             : 
    2010                 :             : /* Creates root variables for store elimination CHAIN in which stores for
    2011                 :             :    elimination store loop variant values.  In this case, we may need to
    2012                 :             :    load root variables before LOOP and propagate it with PHI nodes.  Uids
    2013                 :             :    of the newly created root variables are marked in TMP_VARS.  */
    2014                 :             : 
    2015                 :             : static void
    2016                 :          23 : initialize_root_vars_store_elim_2 (class loop *loop,
    2017                 :             :                                    chain_p chain, bitmap tmp_vars)
    2018                 :             : {
    2019                 :          23 :   unsigned i, n = chain->length;
    2020                 :          23 :   tree ref, init, var, next, val, phi_result;
    2021                 :          23 :   gimple *stmt;
    2022                 :          23 :   gimple_seq stmts;
    2023                 :             : 
    2024                 :          23 :   chain->vars.create (n);
    2025                 :             : 
    2026                 :          23 :   ref = DR_REF (get_chain_root (chain)->ref);
    2027                 :          62 :   for (i = 0; i < n; i++)
    2028                 :             :     {
    2029                 :          39 :       var = predcom_tmp_var (ref, i, tmp_vars);
    2030                 :          39 :       chain->vars.quick_push (var);
    2031                 :             :     }
    2032                 :             : 
    2033                 :          62 :   FOR_EACH_VEC_ELT (chain->vars, i, var)
    2034                 :          39 :     chain->vars[i] = make_ssa_name (var);
    2035                 :             : 
    2036                 :             :   /* Root values are either rhs operand of stores to be eliminated, or
    2037                 :             :      loaded from memory before loop.  */
    2038                 :          23 :   auto_vec<tree> vtemps;
    2039                 :          23 :   vtemps.safe_grow_cleared (n, true);
    2040                 :          62 :   for (i = 0; i < n; i++)
    2041                 :             :     {
    2042                 :          39 :       init = get_init_expr (chain, i);
    2043                 :          39 :       if (init == NULL_TREE)
    2044                 :             :         {
    2045                 :             :           /* Root value is rhs operand of the store to be eliminated if
    2046                 :             :              it isn't loaded from memory before loop.  */
    2047                 :          29 :           dref a = get_chain_last_write_at (chain, i);
    2048                 :          29 :           val = gimple_assign_rhs1 (a->stmt);
    2049                 :          29 :           if (TREE_CLOBBER_P (val))
    2050                 :             :             {
    2051                 :           0 :               val = get_or_create_ssa_default_def (cfun, SSA_NAME_VAR (var));
    2052                 :           0 :               gimple_assign_set_rhs1 (a->stmt, val);
    2053                 :             :             }
    2054                 :             : 
    2055                 :          29 :           vtemps[n - i - 1] = val;
    2056                 :             :         }
    2057                 :             :       else
    2058                 :             :         {
    2059                 :          10 :           edge latch = loop_latch_edge (loop);
    2060                 :          10 :           edge entry = loop_preheader_edge (loop);
    2061                 :             : 
    2062                 :             :           /* Root value is loaded from memory before loop, we also need
    2063                 :             :              to add PHI nodes to propagate the value across iterations.  */
    2064                 :          10 :           init = force_gimple_operand (init, &stmts, true, NULL_TREE);
    2065                 :          10 :           if (stmts)
    2066                 :          10 :             gsi_insert_seq_on_edge_immediate (entry, stmts);
    2067                 :             : 
    2068                 :          10 :           next = chain->vars[n - i];
    2069                 :          10 :           phi_result = copy_ssa_name (next);
    2070                 :          10 :           gphi *phi = create_phi_node (phi_result, loop->header);
    2071                 :          10 :           add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
    2072                 :          10 :           add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
    2073                 :          10 :           vtemps[n - i - 1] = phi_result;
    2074                 :             :         }
    2075                 :             :     }
    2076                 :             : 
    2077                 :             :   /* Find the insertion position.  */
    2078                 :          23 :   dref last = get_chain_root (chain);
    2079                 :          77 :   for (i = 0; i < chain->refs.length (); i++)
    2080                 :             :     {
    2081                 :          54 :       if (chain->refs[i]->pos > last->pos)
    2082                 :           6 :         last = chain->refs[i];
    2083                 :             :     }
    2084                 :             : 
    2085                 :          23 :   gimple_stmt_iterator gsi = gsi_for_stmt (last->stmt);
    2086                 :             : 
    2087                 :             :   /* Insert statements copying root value to root variable.  */
    2088                 :          85 :   for (i = 0; i < n; i++)
    2089                 :             :     {
    2090                 :          39 :       var = chain->vars[i];
    2091                 :          39 :       val = vtemps[i];
    2092                 :          39 :       stmt = gimple_build_assign (var, val);
    2093                 :          39 :       gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
    2094                 :             :     }
    2095                 :          23 : }
    2096                 :             : 
    2097                 :             : /* Generates stores for CHAIN's eliminated stores in LOOP's last
    2098                 :             :    (CHAIN->length - 1) iterations.  */
    2099                 :             : 
    2100                 :             : static void
    2101                 :          33 : finalize_eliminated_stores (class loop *loop, chain_p chain)
    2102                 :             : {
    2103                 :          33 :   unsigned i, n = chain->length;
    2104                 :             : 
    2105                 :          94 :   for (i = 0; i < n; i++)
    2106                 :             :     {
    2107                 :          61 :       tree var = chain->vars[i];
    2108                 :          61 :       tree fini = chain->finis[n - i - 1];
    2109                 :          61 :       gimple *stmt = gimple_build_assign (fini, var);
    2110                 :             : 
    2111                 :          61 :       gimple_seq_add_stmt_without_update (&chain->fini_seq, stmt);
    2112                 :             :     }
    2113                 :             : 
    2114                 :          33 :   if (chain->fini_seq)
    2115                 :             :     {
    2116                 :          33 :       gsi_insert_seq_on_edge_immediate (single_exit (loop), chain->fini_seq);
    2117                 :          33 :       chain->fini_seq = NULL;
    2118                 :             :     }
    2119                 :          33 : }
    2120                 :             : 
    2121                 :             : /* Initializes a variable for load motion for ROOT and prepares phi nodes and
    2122                 :             :    initialization on entry to LOOP if necessary.  The ssa name for the variable
    2123                 :             :    is stored in VARS.  If WRITTEN is true, also a phi node to copy its value
    2124                 :             :    around the loop is created.  Uid of the newly created temporary variable
    2125                 :             :    is marked in TMP_VARS.  INITS is the list containing the (single)
    2126                 :             :    initializer.  */
    2127                 :             : 
    2128                 :             : static void
    2129                 :        1699 : initialize_root_vars_lm (class loop *loop, dref root, bool written,
    2130                 :             :                          vec<tree> *vars, const vec<tree> &inits,
    2131                 :             :                          bitmap tmp_vars)
    2132                 :             : {
    2133                 :        1699 :   unsigned i;
    2134                 :        1699 :   tree ref = DR_REF (root->ref), init, var, next;
    2135                 :        1699 :   gimple_seq stmts;
    2136                 :        1699 :   gphi *phi;
    2137                 :        1699 :   edge entry = loop_preheader_edge (loop), latch = loop_latch_edge (loop);
    2138                 :             : 
    2139                 :             :   /* Find the initializer for the variable, and check that it cannot
    2140                 :             :      trap.  */
    2141                 :        1699 :   init = inits[0];
    2142                 :             : 
    2143                 :        2024 :   vars->create (written ? 2 : 1);
    2144                 :        1699 :   var = predcom_tmp_var (ref, 0, tmp_vars);
    2145                 :        1699 :   vars->quick_push (var);
    2146                 :        1699 :   if (written)
    2147                 :        1374 :     vars->quick_push ((*vars)[0]);
    2148                 :             : 
    2149                 :        4772 :   FOR_EACH_VEC_ELT (*vars, i, var)
    2150                 :        3073 :     (*vars)[i] = make_ssa_name (var);
    2151                 :             : 
    2152                 :        1699 :   var = (*vars)[0];
    2153                 :             : 
    2154                 :        1699 :   init = force_gimple_operand (init, &stmts, written, NULL_TREE);
    2155                 :        1699 :   if (stmts)
    2156                 :        1374 :     gsi_insert_seq_on_edge_immediate (entry, stmts);
    2157                 :             : 
    2158                 :        1699 :   if (written)
    2159                 :             :     {
    2160                 :        1374 :       next = (*vars)[1];
    2161                 :        1374 :       phi = create_phi_node (var, loop->header);
    2162                 :        1374 :       add_phi_arg (phi, init, entry, UNKNOWN_LOCATION);
    2163                 :        1374 :       add_phi_arg (phi, next, latch, UNKNOWN_LOCATION);
    2164                 :             :     }
    2165                 :             :   else
    2166                 :             :     {
    2167                 :         325 :       gassign *init_stmt = gimple_build_assign (var, init);
    2168                 :         325 :       gsi_insert_on_edge_immediate (entry, init_stmt);
    2169                 :             :     }
    2170                 :        1699 : }
    2171                 :             : 
    2172                 :             : 
    2173                 :             : /* Execute load motion for references in chain CHAIN.  Uids of the newly
    2174                 :             :    created temporary variables are marked in TMP_VARS.  */
    2175                 :             : 
    2176                 :             : static void
    2177                 :       10667 : execute_load_motion (class loop *loop, chain_p chain, bitmap tmp_vars)
    2178                 :             : {
    2179                 :       10667 :   auto_vec<tree> vars;
    2180                 :       10667 :   dref a;
    2181                 :       10667 :   unsigned n_writes = 0, ridx, i;
    2182                 :       10667 :   tree var;
    2183                 :             : 
    2184                 :       10667 :   gcc_assert (chain->type == CT_INVARIANT);
    2185                 :       10667 :   gcc_assert (!chain->combined);
    2186                 :       23071 :   FOR_EACH_VEC_ELT (chain->refs, i, a)
    2187                 :       12404 :     if (DR_IS_WRITE (a->ref))
    2188                 :       10627 :       n_writes++;
    2189                 :             : 
    2190                 :             :   /* If there are no reads in the loop, there is nothing to do.  */
    2191                 :       21334 :   if (n_writes == chain->refs.length ())
    2192                 :        8968 :     return;
    2193                 :             : 
    2194                 :        1699 :   initialize_root_vars_lm (loop, get_chain_root (chain), n_writes > 0,
    2195                 :             :                            &vars, chain->inits, tmp_vars);
    2196                 :             : 
    2197                 :        1699 :   ridx = 0;
    2198                 :        6629 :   FOR_EACH_VEC_ELT (chain->refs, i, a)
    2199                 :             :     {
    2200                 :        3231 :       bool is_read = DR_IS_READ (a->ref);
    2201                 :             : 
    2202                 :        3231 :       if (DR_IS_WRITE (a->ref))
    2203                 :             :         {
    2204                 :        1454 :           n_writes--;
    2205                 :        1454 :           if (n_writes)
    2206                 :             :             {
    2207                 :          80 :               var = vars[0];
    2208                 :          80 :               var = make_ssa_name (SSA_NAME_VAR (var));
    2209                 :          80 :               vars[0] = var;
    2210                 :             :             }
    2211                 :             :           else
    2212                 :             :             ridx = 1;
    2213                 :             :         }
    2214                 :             : 
    2215                 :        3231 :       replace_ref_with (a->stmt, vars[ridx],
    2216                 :        3231 :                         !is_read, !is_read);
    2217                 :             :     }
    2218                 :       10667 : }
    2219                 :             : 
    2220                 :             : /* Returns the single statement in that NAME is used, excepting
    2221                 :             :    the looparound phi nodes contained in one of the chains.  If there is no
    2222                 :             :    such statement, or more statements, NULL is returned.  */
    2223                 :             : 
    2224                 :             : gimple *
    2225                 :       63973 : pcom_worker::single_nonlooparound_use (tree name)
    2226                 :             : {
    2227                 :       63973 :   use_operand_p use;
    2228                 :       63973 :   imm_use_iterator it;
    2229                 :       63973 :   gimple *stmt, *ret = NULL;
    2230                 :             : 
    2231                 :      129025 :   FOR_EACH_IMM_USE_FAST (use, it, name)
    2232                 :             :     {
    2233                 :       65608 :       stmt = USE_STMT (use);
    2234                 :             : 
    2235                 :       65608 :       if (gimple_code (stmt) == GIMPLE_PHI)
    2236                 :             :         {
    2237                 :             :           /* Ignore uses in looparound phi nodes.  Uses in other phi nodes
    2238                 :             :              could not be processed anyway, so just fail for them.  */
    2239                 :         408 :           if (bitmap_bit_p (m_looparound_phis,
    2240                 :         204 :                             SSA_NAME_VERSION (PHI_RESULT (stmt))))
    2241                 :          60 :             continue;
    2242                 :             : 
    2243                 :             :           return NULL;
    2244                 :             :         }
    2245                 :       65404 :       else if (is_gimple_debug (stmt))
    2246                 :        1227 :         continue;
    2247                 :       64177 :       else if (ret != NULL)
    2248                 :             :         return NULL;
    2249                 :             :       else
    2250                 :             :         ret = stmt;
    2251                 :             :     }
    2252                 :             : 
    2253                 :             :   return ret;
    2254                 :             : }
    2255                 :             : 
    2256                 :             : /* Remove statement STMT, as well as the chain of assignments in that it is
    2257                 :             :    used.  */
    2258                 :             : 
    2259                 :             : void
    2260                 :         204 : pcom_worker::remove_stmt (gimple *stmt)
    2261                 :             : {
    2262                 :         204 :   tree name;
    2263                 :         204 :   gimple *next;
    2264                 :         204 :   gimple_stmt_iterator psi;
    2265                 :             : 
    2266                 :         204 :   if (gimple_code (stmt) == GIMPLE_PHI)
    2267                 :             :     {
    2268                 :          12 :       name = PHI_RESULT (stmt);
    2269                 :          12 :       next = single_nonlooparound_use (name);
    2270                 :          12 :       reset_debug_uses (stmt);
    2271                 :          12 :       psi = gsi_for_stmt (stmt);
    2272                 :          12 :       remove_phi_node (&psi, true);
    2273                 :             : 
    2274                 :          12 :       if (!next
    2275                 :          11 :           || !gimple_assign_ssa_name_copy_p (next)
    2276                 :          16 :           || gimple_assign_rhs1 (next) != name)
    2277                 :           8 :         return;
    2278                 :             : 
    2279                 :             :       stmt = next;
    2280                 :             :     }
    2281                 :             : 
    2282                 :         280 :   while (1)
    2283                 :             :     {
    2284                 :         238 :       gimple_stmt_iterator bsi;
    2285                 :             : 
    2286                 :         238 :       bsi = gsi_for_stmt (stmt);
    2287                 :             : 
    2288                 :         238 :       name = gimple_assign_lhs (stmt);
    2289                 :         238 :       if (TREE_CODE (name) == SSA_NAME)
    2290                 :             :         {
    2291                 :         176 :           next = single_nonlooparound_use (name);
    2292                 :         176 :           reset_debug_uses (stmt);
    2293                 :             :         }
    2294                 :             :       else
    2295                 :             :         {
    2296                 :             :           /* This is a store to be eliminated.  */
    2297                 :         124 :           gcc_assert (gimple_vdef (stmt) != NULL);
    2298                 :             :           next = NULL;
    2299                 :             :         }
    2300                 :             : 
    2301                 :         238 :       unlink_stmt_vdef (stmt);
    2302                 :         238 :       gsi_remove (&bsi, true);
    2303                 :         238 :       release_defs (stmt);
    2304                 :             : 
    2305                 :         238 :       if (!next
    2306                 :         113 :           || !gimple_assign_ssa_name_copy_p (next)
    2307                 :         280 :           || gimple_assign_rhs1 (next) != name)
    2308                 :         196 :         return;
    2309                 :             : 
    2310                 :          42 :       stmt = next;
    2311                 :          42 :     }
    2312                 :             : }
    2313                 :             : 
    2314                 :             : /* Perform the predictive commoning optimization for a chain CHAIN.
    2315                 :             :    Uids of the newly created temporary variables are marked in TMP_VARS.*/
    2316                 :             : 
    2317                 :             : void
    2318                 :       15111 : pcom_worker::execute_pred_commoning_chain (chain_p chain,
    2319                 :             :                               bitmap tmp_vars)
    2320                 :             : {
    2321                 :       15111 :   unsigned i;
    2322                 :       15111 :   dref a;
    2323                 :       15111 :   tree var;
    2324                 :       15111 :   bool in_lhs;
    2325                 :             : 
    2326                 :       15111 :   if (chain->combined)
    2327                 :             :     {
    2328                 :             :       /* For combined chains, just remove the statements that are used to
    2329                 :             :          compute the values of the expression (except for the root one).
    2330                 :             :          We delay this until after all chains are processed.  */
    2331                 :             :     }
    2332                 :       15035 :   else if (chain->type == CT_STORE_STORE)
    2333                 :             :     {
    2334                 :          49 :       if (chain->length > 0)
    2335                 :             :         {
    2336                 :          33 :           if (chain->inv_store_elimination)
    2337                 :             :             {
    2338                 :             :               /* If dead stores in this chain only store loop invariant
    2339                 :             :                  values, we can simply record the invariant value and use
    2340                 :             :                  it directly after loop.  */
    2341                 :          10 :               initialize_root_vars_store_elim_1 (chain);
    2342                 :             :             }
    2343                 :             :           else
    2344                 :             :             {
    2345                 :             :               /* If dead stores in this chain store loop variant values,
    2346                 :             :                  we need to set up the variables by loading from memory
    2347                 :             :                  before loop and propagating it with PHI nodes.  */
    2348                 :          23 :               initialize_root_vars_store_elim_2 (m_loop, chain, tmp_vars);
    2349                 :             :             }
    2350                 :             : 
    2351                 :             :           /* For inter-iteration store elimination chain, stores at each
    2352                 :             :              distance in loop's last (chain->length - 1) iterations can't
    2353                 :             :              be eliminated, because there is no following killing store.
    2354                 :             :              We need to generate these stores after loop.  */
    2355                 :          33 :           finalize_eliminated_stores (m_loop, chain);
    2356                 :             :         }
    2357                 :             : 
    2358                 :          49 :       bool last_store_p = true;
    2359                 :         214 :       for (i = chain->refs.length (); i > 0; i--)
    2360                 :             :         {
    2361                 :         116 :           a = chain->refs[i - 1];
    2362                 :             :           /* Preserve the last store of the chain.  Eliminate other stores
    2363                 :             :              which are killed by the last one.  */
    2364                 :         116 :           if (DR_IS_WRITE (a->ref))
    2365                 :             :             {
    2366                 :         111 :               if (last_store_p)
    2367                 :             :                 last_store_p = false;
    2368                 :             :               else
    2369                 :          62 :                 remove_stmt (a->stmt);
    2370                 :             : 
    2371                 :         111 :               continue;
    2372                 :             :             }
    2373                 :             : 
    2374                 :             :           /* Any load in Store-Store chain must be dominated by a previous
    2375                 :             :              store, we replace the load reference with rhs of the store.  */
    2376                 :           5 :           dref b = get_chain_last_write_before_load (chain, i - 1);
    2377                 :           5 :           gcc_assert (b != NULL);
    2378                 :           5 :           var = gimple_assign_rhs1 (b->stmt);
    2379                 :           5 :           replace_ref_with (a->stmt, var, false, false);
    2380                 :             :         }
    2381                 :             :     }
    2382                 :             :   else
    2383                 :             :     {
    2384                 :             :       /* For non-combined chains, set up the variables that hold its value.  */
    2385                 :       14986 :       initialize_root_vars (m_loop, chain, tmp_vars);
    2386                 :       14986 :       a = get_chain_root (chain);
    2387                 :       14986 :       in_lhs = (chain->type == CT_STORE_LOAD
    2388                 :       14986 :                 || chain->type == CT_COMBINATION);
    2389                 :       14986 :       replace_ref_with (a->stmt, chain->vars[chain->length], true, in_lhs);
    2390                 :             : 
    2391                 :             :       /* Replace the uses of the original references by these variables.  */
    2392                 :       45283 :       for (i = 1; chain->refs.iterate (i, &a); i++)
    2393                 :             :         {
    2394                 :       15311 :           var = chain->vars[chain->length - a->distance];
    2395                 :       15311 :           replace_ref_with (a->stmt, var, false, false);
    2396                 :             :         }
    2397                 :             :     }
    2398                 :       15111 : }
    2399                 :             : 
    2400                 :             : /* Determines the unroll factor necessary to remove as many temporary variable
    2401                 :             :    copies as possible.  CHAINS is the list of chains that will be
    2402                 :             :    optimized.  */
    2403                 :             : 
    2404                 :             : static unsigned
    2405                 :        2971 : determine_unroll_factor (const vec<chain_p> &chains)
    2406                 :             : {
    2407                 :        2971 :   chain_p chain;
    2408                 :        2971 :   unsigned factor = 1, af, nfactor, i;
    2409                 :        2971 :   unsigned max = param_max_unroll_times;
    2410                 :             : 
    2411                 :        6921 :   FOR_EACH_VEC_ELT (chains, i, chain)
    2412                 :             :     {
    2413                 :        3976 :       if (chain->type == CT_INVARIANT)
    2414                 :        1703 :         continue;
    2415                 :             :       /* For now we can't handle unrolling when eliminating stores.  */
    2416                 :        2273 :       else if (chain->type == CT_STORE_STORE)
    2417                 :             :         return 1;
    2418                 :             : 
    2419                 :        2250 :       if (chain->combined)
    2420                 :             :         {
    2421                 :             :           /* For combined chains, we can't handle unrolling if we replace
    2422                 :             :              looparound PHIs.  */
    2423                 :             :           dref a;
    2424                 :             :           unsigned j;
    2425                 :         155 :           for (j = 1; chain->refs.iterate (j, &a); j++)
    2426                 :          97 :             if (gimple_code (a->stmt) == GIMPLE_PHI)
    2427                 :          26 :               return 1;
    2428                 :          58 :           continue;
    2429                 :          58 :         }
    2430                 :             : 
    2431                 :             :       /* The best unroll factor for this chain is equal to the number of
    2432                 :             :          temporary variables that we create for it.  */
    2433                 :        2189 :       af = chain->length;
    2434                 :        2189 :       if (chain->has_max_use_after)
    2435                 :        1317 :         af++;
    2436                 :             : 
    2437                 :        2189 :       nfactor = factor * af / gcd (factor, af);
    2438                 :        2189 :       if (nfactor <= max)
    2439                 :        3950 :         factor = nfactor;
    2440                 :             :     }
    2441                 :             : 
    2442                 :             :   return factor;
    2443                 :             : }
    2444                 :             : 
    2445                 :             : /* Perform the predictive commoning optimization for chains.
    2446                 :             :    Uids of the newly created temporary variables are marked in TMP_VARS.  */
    2447                 :             : 
    2448                 :             : void
    2449                 :       14153 : pcom_worker::execute_pred_commoning (bitmap tmp_vars)
    2450                 :             : {
    2451                 :       14153 :   chain_p chain;
    2452                 :       14153 :   unsigned i;
    2453                 :             : 
    2454                 :       39931 :   FOR_EACH_VEC_ELT (m_chains, i, chain)
    2455                 :             :     {
    2456                 :       25778 :       if (chain->type == CT_INVARIANT)
    2457                 :       10667 :         execute_load_motion (m_loop, chain, tmp_vars);
    2458                 :             :       else
    2459                 :       15111 :         execute_pred_commoning_chain (chain, tmp_vars);
    2460                 :             :     }
    2461                 :             : 
    2462                 :       39931 :   FOR_EACH_VEC_ELT (m_chains, i, chain)
    2463                 :             :     {
    2464                 :       25778 :       if (chain->type == CT_INVARIANT)
    2465                 :             :         ;
    2466                 :       15111 :       else if (chain->combined)
    2467                 :             :         {
    2468                 :             :           /* For combined chains, just remove the statements that are used to
    2469                 :             :              compute the values of the expression (except for the root one).  */
    2470                 :             :           dref a;
    2471                 :             :           unsigned j;
    2472                 :       25996 :           for (j = 1; chain->refs.iterate (j, &a); j++)
    2473                 :         142 :             remove_stmt (a->stmt);
    2474                 :             :         }
    2475                 :             :     }
    2476                 :       14153 : }
    2477                 :             : 
    2478                 :             : /* For each reference in CHAINS, if its defining statement is
    2479                 :             :    phi node, record the ssa name that is defined by it.  */
    2480                 :             : 
    2481                 :             : static void
    2482                 :         591 : replace_phis_by_defined_names (vec<chain_p> &chains)
    2483                 :             : {
    2484                 :         591 :   chain_p chain;
    2485                 :         591 :   dref a;
    2486                 :         591 :   unsigned i, j;
    2487                 :             : 
    2488                 :        1869 :   FOR_EACH_VEC_ELT (chains, i, chain)
    2489                 :        2618 :     FOR_EACH_VEC_ELT (chain->refs, j, a)
    2490                 :             :       {
    2491                 :        1340 :         if (gimple_code (a->stmt) == GIMPLE_PHI)
    2492                 :             :           {
    2493                 :           1 :             a->name_defined_by_phi = PHI_RESULT (a->stmt);
    2494                 :           1 :             a->stmt = NULL;
    2495                 :             :           }
    2496                 :             :       }
    2497                 :         591 : }
    2498                 :             : 
    2499                 :             : /* For each reference in CHAINS, if name_defined_by_phi is not
    2500                 :             :    NULL, use it to set the stmt field.  */
    2501                 :             : 
    2502                 :             : static void
    2503                 :         591 : replace_names_by_phis (vec<chain_p> chains)
    2504                 :             : {
    2505                 :         591 :   chain_p chain;
    2506                 :         591 :   dref a;
    2507                 :         591 :   unsigned i, j;
    2508                 :             : 
    2509                 :        1869 :   FOR_EACH_VEC_ELT (chains, i, chain)
    2510                 :        2618 :     FOR_EACH_VEC_ELT (chain->refs, j, a)
    2511                 :        1340 :       if (a->stmt == NULL)
    2512                 :             :         {
    2513                 :           1 :           a->stmt = SSA_NAME_DEF_STMT (a->name_defined_by_phi);
    2514                 :           1 :           gcc_assert (gimple_code (a->stmt) == GIMPLE_PHI);
    2515                 :           1 :           a->name_defined_by_phi = NULL_TREE;
    2516                 :             :         }
    2517                 :         591 : }
    2518                 :             : 
    2519                 :             : /* Wrapper over execute_pred_commoning, to pass it as a callback
    2520                 :             :    to tree_transform_and_unroll_loop.  */
    2521                 :             : 
    2522                 :             : struct epcc_data
    2523                 :             : {
    2524                 :             :   vec<chain_p> chains;
    2525                 :             :   bitmap tmp_vars;
    2526                 :             :   pcom_worker *worker;
    2527                 :             : };
    2528                 :             : 
    2529                 :             : static void
    2530                 :         591 : execute_pred_commoning_cbck (class loop *loop ATTRIBUTE_UNUSED, void *data)
    2531                 :             : {
    2532                 :         591 :   struct epcc_data *const dta = (struct epcc_data *) data;
    2533                 :         591 :   pcom_worker *worker = dta->worker;
    2534                 :             : 
    2535                 :             :   /* Restore phi nodes that were replaced by ssa names before
    2536                 :             :      tree_transform_and_unroll_loop (see detailed description in
    2537                 :             :      tree_predictive_commoning_loop).  */
    2538                 :         591 :   replace_names_by_phis (dta->chains);
    2539                 :         591 :   worker->execute_pred_commoning (dta->tmp_vars);
    2540                 :         591 : }
    2541                 :             : 
    2542                 :             : /* Base NAME and all the names in the chain of phi nodes that use it
    2543                 :             :    on variable VAR.  The phi nodes are recognized by being in the copies of
    2544                 :             :    the header of the LOOP.  */
    2545                 :             : 
    2546                 :             : static void
    2547                 :         641 : base_names_in_chain_on (class loop *loop, tree name, tree var)
    2548                 :             : {
    2549                 :         641 :   gimple *stmt, *phi;
    2550                 :         641 :   imm_use_iterator iter;
    2551                 :             : 
    2552                 :         641 :   replace_ssa_name_symbol (name, var);
    2553                 :             : 
    2554                 :        2063 :   while (1)
    2555                 :             :     {
    2556                 :        1352 :       phi = NULL;
    2557                 :        2000 :       FOR_EACH_IMM_USE_STMT (stmt, iter, name)
    2558                 :             :         {
    2559                 :        1359 :           if (gimple_code (stmt) == GIMPLE_PHI
    2560                 :        1359 :               && flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
    2561                 :             :             {
    2562                 :             :               phi = stmt;
    2563                 :             :               break;
    2564                 :             :             }
    2565                 :        1352 :         }
    2566                 :        1352 :       if (!phi)
    2567                 :         641 :         return;
    2568                 :             : 
    2569                 :         711 :       name = PHI_RESULT (phi);
    2570                 :         711 :       replace_ssa_name_symbol (name, var);
    2571                 :         711 :     }
    2572                 :             : }
    2573                 :             : 
    2574                 :             : /* Given an unrolled LOOP after predictive commoning, remove the
    2575                 :             :    register copies arising from phi nodes by changing the base
    2576                 :             :    variables of SSA names.  TMP_VARS is the set of the temporary variables
    2577                 :             :    for those we want to perform this.  */
    2578                 :             : 
    2579                 :             : static void
    2580                 :         591 : eliminate_temp_copies (class loop *loop, bitmap tmp_vars)
    2581                 :             : {
    2582                 :         591 :   edge e;
    2583                 :         591 :   gphi *phi;
    2584                 :         591 :   gimple *stmt;
    2585                 :         591 :   tree name, use, var;
    2586                 :         591 :   gphi_iterator psi;
    2587                 :             : 
    2588                 :         591 :   e = loop_latch_edge (loop);
    2589                 :        3055 :   for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); gsi_next (&psi))
    2590                 :             :     {
    2591                 :        2464 :       phi = psi.phi ();
    2592                 :        2464 :       name = PHI_RESULT (phi);
    2593                 :        2464 :       var = SSA_NAME_VAR (name);
    2594                 :        1590 :       if (!var || !bitmap_bit_p (tmp_vars, DECL_UID (var)))
    2595                 :        1823 :         continue;
    2596                 :         641 :       use = PHI_ARG_DEF_FROM_EDGE (phi, e);
    2597                 :         641 :       gcc_assert (TREE_CODE (use) == SSA_NAME);
    2598                 :             : 
    2599                 :             :       /* Base all the ssa names in the ud and du chain of NAME on VAR.  */
    2600                 :         641 :       stmt = SSA_NAME_DEF_STMT (use);
    2601                 :         676 :       while (gimple_code (stmt) == GIMPLE_PHI
    2602                 :             :              /* In case we could not unroll the loop enough to eliminate
    2603                 :             :                 all copies, we may reach the loop header before the defining
    2604                 :             :                 statement (in that case, some register copies will be present
    2605                 :             :                 in loop latch in the final code, corresponding to the newly
    2606                 :             :                 created looparound phi nodes).  */
    2607                 :         676 :              && gimple_bb (stmt) != loop->header)
    2608                 :             :         {
    2609                 :          70 :           gcc_assert (single_pred_p (gimple_bb (stmt)));
    2610                 :          35 :           use = PHI_ARG_DEF (stmt, 0);
    2611                 :          35 :           stmt = SSA_NAME_DEF_STMT (use);
    2612                 :             :         }
    2613                 :             : 
    2614                 :         641 :       base_names_in_chain_on (loop, use, var);
    2615                 :             :     }
    2616                 :         591 : }
    2617                 :             : 
    2618                 :             : /* Returns true if CHAIN is suitable to be combined.  */
    2619                 :             : 
    2620                 :             : static bool
    2621                 :      110201 : chain_can_be_combined_p (chain_p chain)
    2622                 :             : {
    2623                 :      110201 :   return (!chain->combined
    2624                 :      110035 :           && (chain->type == CT_LOAD || chain->type == CT_COMBINATION));
    2625                 :             : }
    2626                 :             : 
    2627                 :             : /* Returns the modify statement that uses NAME.  Skips over assignment
    2628                 :             :    statements, NAME is replaced with the actual name used in the returned
    2629                 :             :    statement.  */
    2630                 :             : 
    2631                 :             : gimple *
    2632                 :       62142 : pcom_worker::find_use_stmt (tree *name)
    2633                 :             : {
    2634                 :       63785 :   gimple *stmt;
    2635                 :       63785 :   tree rhs, lhs;
    2636                 :             : 
    2637                 :             :   /* Skip over assignments.  */
    2638                 :       65428 :   while (1)
    2639                 :             :     {
    2640                 :       63785 :       stmt = single_nonlooparound_use (*name);
    2641                 :       63785 :       if (!stmt)
    2642                 :             :         return NULL;
    2643                 :             : 
    2644                 :       63229 :       if (gimple_code (stmt) != GIMPLE_ASSIGN)
    2645                 :             :         return NULL;
    2646                 :             : 
    2647                 :       62083 :       lhs = gimple_assign_lhs (stmt);
    2648                 :       62083 :       if (TREE_CODE (lhs) != SSA_NAME)
    2649                 :             :         return NULL;
    2650                 :             : 
    2651                 :       61969 :       if (gimple_assign_copy_p (stmt))
    2652                 :             :         {
    2653                 :        1643 :           rhs = gimple_assign_rhs1 (stmt);
    2654                 :        1643 :           if (rhs != *name)
    2655                 :             :             return NULL;
    2656                 :             : 
    2657                 :        1643 :           *name = lhs;
    2658                 :             :         }
    2659                 :       60326 :       else if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
    2660                 :             :                == GIMPLE_BINARY_RHS)
    2661                 :             :         return stmt;
    2662                 :             :       else
    2663                 :             :         return NULL;
    2664                 :             :     }
    2665                 :             : }
    2666                 :             : 
    2667                 :             : /* Returns true if we may perform reassociation for operation CODE in TYPE.  */
    2668                 :             : 
    2669                 :             : static bool
    2670                 :        1059 : may_reassociate_p (tree type, enum tree_code code)
    2671                 :             : {
    2672                 :         658 :   if (FLOAT_TYPE_P (type)
    2673                 :        1379 :       && !flag_unsafe_math_optimizations)
    2674                 :             :     return false;
    2675                 :             : 
    2676                 :         741 :   return (commutative_tree_code (code)
    2677                 :         741 :           && associative_tree_code (code));
    2678                 :             : }
    2679                 :             : 
    2680                 :             : /* If the operation used in STMT is associative and commutative, go through the
    2681                 :             :    tree of the same operations and returns its root.  Distance to the root
    2682                 :             :    is stored in DISTANCE.  */
    2683                 :             : 
    2684                 :             : gimple *
    2685                 :        1059 : pcom_worker::find_associative_operation_root (gimple *stmt, unsigned *distance)
    2686                 :             : {
    2687                 :        1059 :   tree lhs;
    2688                 :        1059 :   gimple *next;
    2689                 :        1059 :   enum tree_code code = gimple_assign_rhs_code (stmt);
    2690                 :        1059 :   tree type = TREE_TYPE (gimple_assign_lhs (stmt));
    2691                 :        1059 :   unsigned dist = 0;
    2692                 :             : 
    2693                 :        1059 :   if (!may_reassociate_p (type, code))
    2694                 :             :     return NULL;
    2695                 :             : 
    2696                 :        4031 :   while (1)
    2697                 :             :     {
    2698                 :        2353 :       lhs = gimple_assign_lhs (stmt);
    2699                 :        2353 :       gcc_assert (TREE_CODE (lhs) == SSA_NAME);
    2700                 :             : 
    2701                 :        2353 :       next = find_use_stmt (&lhs);
    2702                 :        2353 :       if (!next
    2703                 :        2353 :           || gimple_assign_rhs_code (next) != code)
    2704                 :             :         break;
    2705                 :             : 
    2706                 :        1678 :       stmt = next;
    2707                 :        1678 :       dist++;
    2708                 :             :     }
    2709                 :             : 
    2710                 :         675 :   if (distance)
    2711                 :         196 :     *distance = dist;
    2712                 :             :   return stmt;
    2713                 :             : }
    2714                 :             : 
    2715                 :             : /* Returns the common statement in that NAME1 and NAME2 have a use.  If there
    2716                 :             :    is no such statement, returns NULL_TREE.  In case the operation used on
    2717                 :             :    NAME1 and NAME2 is associative and commutative, returns the root of the
    2718                 :             :    tree formed by this operation instead of the statement that uses NAME1 or
    2719                 :             :    NAME2.  */
    2720                 :             : 
    2721                 :             : gimple *
    2722                 :       57996 : pcom_worker::find_common_use_stmt (tree *name1, tree *name2)
    2723                 :             : {
    2724                 :       57996 :   gimple *stmt1, *stmt2;
    2725                 :             : 
    2726                 :       57996 :   stmt1 = find_use_stmt (name1);
    2727                 :       57996 :   if (!stmt1)
    2728                 :             :     return NULL;
    2729                 :             : 
    2730                 :         767 :   stmt2 = find_use_stmt (name2);
    2731                 :         767 :   if (!stmt2)
    2732                 :             :     return NULL;
    2733                 :             : 
    2734                 :         674 :   if (stmt1 == stmt2)
    2735                 :             :     return stmt1;
    2736                 :             : 
    2737                 :         623 :   stmt1 = find_associative_operation_root (stmt1, NULL);
    2738                 :         623 :   if (!stmt1)
    2739                 :             :     return NULL;
    2740                 :         240 :   stmt2 = find_associative_operation_root (stmt2, NULL);
    2741                 :         240 :   if (!stmt2)
    2742                 :             :     return NULL;
    2743                 :             : 
    2744                 :         239 :   return (stmt1 == stmt2 ? stmt1 : NULL);
    2745                 :             : }
    2746                 :             : 
    2747                 :             : /* Checks whether R1 and R2 are combined together using CODE, with the result
    2748                 :             :    in RSLT_TYPE, in order R1 CODE R2 if SWAP is false and in order R2 CODE R1
    2749                 :             :    if it is true.  If CODE is ERROR_MARK, set these values instead.  */
    2750                 :             : 
    2751                 :             : bool
    2752                 :       57996 : pcom_worker::combinable_refs_p (dref r1, dref r2,
    2753                 :             :                    enum tree_code *code, bool *swap, tree *rslt_type)
    2754                 :             : {
    2755                 :       57996 :   enum tree_code acode;
    2756                 :       57996 :   bool aswap;
    2757                 :       57996 :   tree atype;
    2758                 :       57996 :   tree name1, name2;
    2759                 :       57996 :   gimple *stmt;
    2760                 :             : 
    2761                 :       57996 :   name1 = name_for_ref (r1);
    2762                 :       57996 :   name2 = name_for_ref (r2);
    2763                 :       57996 :   gcc_assert (name1 != NULL_TREE && name2 != NULL_TREE);
    2764                 :             : 
    2765                 :       57996 :   stmt = find_common_use_stmt (&name1, &name2);
    2766                 :             : 
    2767                 :       57996 :   if (!stmt
    2768                 :             :       /* A simple post-dominance check - make sure the combination
    2769                 :             :          is executed under the same condition as the references.  */
    2770                 :       57996 :       || (gimple_bb (stmt) != gimple_bb (r1->stmt)
    2771                 :          20 :           && gimple_bb (stmt) != gimple_bb (r2->stmt)))
    2772                 :             :     return false;
    2773                 :             : 
    2774                 :         135 :   acode = gimple_assign_rhs_code (stmt);
    2775                 :         135 :   aswap = (!commutative_tree_code (acode)
    2776                 :         135 :            && gimple_assign_rhs1 (stmt) != name1);
    2777                 :         135 :   atype = TREE_TYPE (gimple_assign_lhs (stmt));
    2778                 :             : 
    2779                 :         135 :   if (*code == ERROR_MARK)
    2780                 :             :     {
    2781                 :          54 :       *code = acode;
    2782                 :          54 :       *swap = aswap;
    2783                 :          54 :       *rslt_type = atype;
    2784                 :          54 :       return true;
    2785                 :             :     }
    2786                 :             : 
    2787                 :          81 :   return (*code == acode
    2788                 :          71 :           && *swap == aswap
    2789                 :         152 :           && *rslt_type == atype);
    2790                 :             : }
    2791                 :             : 
    2792                 :             : /* Remove OP from the operation on rhs of STMT, and replace STMT with
    2793                 :             :    an assignment of the remaining operand.  */
    2794                 :             : 
    2795                 :             : static void
    2796                 :         196 : remove_name_from_operation (gimple *stmt, tree op)
    2797                 :             : {
    2798                 :         196 :   tree other_op;
    2799                 :         196 :   gimple_stmt_iterator si;
    2800                 :             : 
    2801                 :         196 :   gcc_assert (is_gimple_assign (stmt));
    2802                 :             : 
    2803                 :         196 :   if (gimple_assign_rhs1 (stmt) == op)
    2804                 :          82 :     other_op = gimple_assign_rhs2 (stmt);
    2805                 :             :   else
    2806                 :             :     other_op = gimple_assign_rhs1 (stmt);
    2807                 :             : 
    2808                 :         196 :   si = gsi_for_stmt (stmt);
    2809                 :         196 :   gimple_assign_set_rhs_from_tree (&si, other_op);
    2810                 :             : 
    2811                 :             :   /* We should not have reallocated STMT.  */
    2812                 :         196 :   gcc_assert (gsi_stmt (si) == stmt);
    2813                 :             : 
    2814                 :         196 :   update_stmt (stmt);
    2815                 :         196 : }
    2816                 :             : 
    2817                 :             : /* Reassociates the expression in that NAME1 and NAME2 are used so that they
    2818                 :             :    are combined in a single statement, and returns this statement.  */
    2819                 :             : 
    2820                 :             : gimple *
    2821                 :          98 : pcom_worker::reassociate_to_the_same_stmt (tree name1, tree name2)
    2822                 :             : {
    2823                 :          98 :   gimple *stmt1, *stmt2, *root1, *root2, *s1, *s2;
    2824                 :          98 :   gassign *new_stmt, *tmp_stmt;
    2825                 :          98 :   tree new_name, tmp_name, var, r1, r2;
    2826                 :          98 :   unsigned dist1, dist2;
    2827                 :          98 :   enum tree_code code;
    2828                 :          98 :   tree type = TREE_TYPE (name1);
    2829                 :          98 :   gimple_stmt_iterator bsi;
    2830                 :             : 
    2831                 :          98 :   stmt1 = find_use_stmt (&name1);
    2832                 :          98 :   stmt2 = find_use_stmt (&name2);
    2833                 :          98 :   root1 = find_associative_operation_root (stmt1, &dist1);
    2834                 :          98 :   root2 = find_associative_operation_root (stmt2, &dist2);
    2835                 :          98 :   code = gimple_assign_rhs_code (stmt1);
    2836                 :             : 
    2837                 :          98 :   gcc_assert (root1 && root2 && root1 == root2
    2838                 :             :               && code == gimple_assign_rhs_code (stmt2));
    2839                 :             : 
    2840                 :             :   /* Find the root of the nearest expression in that both NAME1 and NAME2
    2841                 :             :      are used.  */
    2842                 :          98 :   r1 = name1;
    2843                 :          98 :   s1 = stmt1;
    2844                 :          98 :   r2 = name2;
    2845                 :          98 :   s2 = stmt2;
    2846                 :             : 
    2847                 :         388 :   while (dist1 > dist2)
    2848                 :             :     {
    2849                 :         290 :       s1 = find_use_stmt (&r1);
    2850                 :         290 :       r1 = gimple_assign_lhs (s1);
    2851                 :         290 :       dist1--;
    2852                 :             :     }
    2853                 :         216 :   while (dist2 > dist1)
    2854                 :             :     {
    2855                 :         118 :       s2 = find_use_stmt (&r2);
    2856                 :         118 :       r2 = gimple_assign_lhs (s2);
    2857                 :         118 :       dist2--;
    2858                 :             :     }
    2859                 :             : 
    2860                 :         200 :   while (s1 != s2)
    2861                 :             :     {
    2862                 :         102 :       s1 = find_use_stmt (&r1);
    2863                 :         102 :       r1 = gimple_assign_lhs (s1);
    2864                 :         102 :       s2 = find_use_stmt (&r2);
    2865                 :         102 :       r2 = gimple_assign_lhs (s2);
    2866                 :             :     }
    2867                 :             : 
    2868                 :             :   /* Remove NAME1 and NAME2 from the statements in that they are used
    2869                 :             :      currently.  */
    2870                 :          98 :   remove_name_from_operation (stmt1, name1);
    2871                 :          98 :   remove_name_from_operation (stmt2, name2);
    2872                 :             : 
    2873                 :             :   /* Insert the new statement combining NAME1 and NAME2 before S1, and
    2874                 :             :      combine it with the rhs of S1.  */
    2875                 :          98 :   var = create_tmp_reg (type, "predreastmp");
    2876                 :          98 :   new_name = make_ssa_name (var);
    2877                 :          98 :   new_stmt = gimple_build_assign (new_name, code, name1, name2);
    2878                 :             : 
    2879                 :          98 :   var = create_tmp_reg (type, "predreastmp");
    2880                 :          98 :   tmp_name = make_ssa_name (var);
    2881                 :             : 
    2882                 :             :   /* Rhs of S1 may now be either a binary expression with operation
    2883                 :             :      CODE, or gimple_val (in case that stmt1 == s1 or stmt2 == s1,
    2884                 :             :      so that name1 or name2 was removed from it).  */
    2885                 :          98 :   tmp_stmt = gimple_build_assign (tmp_name, gimple_assign_rhs_code (s1),
    2886                 :             :                                   gimple_assign_rhs1 (s1),
    2887                 :             :                                   gimple_assign_rhs2 (s1));
    2888                 :             : 
    2889                 :          98 :   bsi = gsi_for_stmt (s1);
    2890                 :          98 :   gimple_assign_set_rhs_with_ops (&bsi, code, new_name, tmp_name);
    2891                 :          98 :   s1 = gsi_stmt (bsi);
    2892                 :          98 :   update_stmt (s1);
    2893                 :             : 
    2894                 :          98 :   gsi_insert_before (&bsi, new_stmt, GSI_SAME_STMT);
    2895                 :          98 :   gsi_insert_before (&bsi, tmp_stmt, GSI_SAME_STMT);
    2896                 :             : 
    2897                 :          98 :   return new_stmt;
    2898                 :             : }
    2899                 :             : 
    2900                 :             : /* Returns the statement that combines references R1 and R2.  In case R1
    2901                 :             :    and R2 are not used in the same statement, but they are used with an
    2902                 :             :    associative and commutative operation in the same expression, reassociate
    2903                 :             :    the expression so that they are used in the same statement.  */
    2904                 :             : 
    2905                 :             : gimple *
    2906                 :         109 : pcom_worker::stmt_combining_refs (dref r1, dref r2)
    2907                 :             : {
    2908                 :         109 :   gimple *stmt1, *stmt2;
    2909                 :         109 :   tree name1 = name_for_ref (r1);
    2910                 :         109 :   tree name2 = name_for_ref (r2);
    2911                 :             : 
    2912                 :         109 :   stmt1 = find_use_stmt (&name1);
    2913                 :         109 :   stmt2 = find_use_stmt (&name2);
    2914                 :         109 :   if (stmt1 == stmt2)
    2915                 :             :     return stmt1;
    2916                 :             : 
    2917                 :          98 :   return reassociate_to_the_same_stmt (name1, name2);
    2918                 :             : }
    2919                 :             : 
    2920                 :             : /* Tries to combine chains CH1 and CH2 together.  If this succeeds, the
    2921                 :             :    description of the new chain is returned, otherwise we return NULL.  */
    2922                 :             : 
    2923                 :             : chain_p
    2924                 :       71009 : pcom_worker::combine_chains (chain_p ch1, chain_p ch2)
    2925                 :             : {
    2926                 :       71009 :   dref r1, r2, nw;
    2927                 :       71009 :   enum tree_code op = ERROR_MARK;
    2928                 :       71009 :   bool swap = false;
    2929                 :       71009 :   chain_p new_chain;
    2930                 :       71009 :   unsigned i;
    2931                 :       71009 :   tree rslt_type = NULL_TREE;
    2932                 :             : 
    2933                 :       71009 :   if (ch1 == ch2)
    2934                 :             :     return NULL;
    2935                 :       58209 :   if (ch1->length != ch2->length)
    2936                 :             :     return NULL;
    2937                 :             : 
    2938                 :      174543 :   if (ch1->refs.length () != ch2->refs.length ())
    2939                 :             :     return NULL;
    2940                 :             : 
    2941                 :         125 :   for (i = 0; (ch1->refs.iterate (i, &r1)
    2942                 :      116030 :                && ch2->refs.iterate (i, &r2)); i++)
    2943                 :             :     {
    2944                 :       57996 :       if (r1->distance != r2->distance)
    2945                 :             :         return NULL;
    2946                 :             : 
    2947                 :       57996 :       if (!combinable_refs_p (r1, r2, &op, &swap, &rslt_type))
    2948                 :             :         return NULL;
    2949                 :             :     }
    2950                 :             : 
    2951                 :          38 :   if (swap)
    2952                 :           1 :     std::swap (ch1, ch2);
    2953                 :             : 
    2954                 :          38 :   new_chain = new struct chain (CT_COMBINATION);
    2955                 :          38 :   new_chain->op = op;
    2956                 :          38 :   new_chain->ch1 = ch1;
    2957                 :          38 :   new_chain->ch2 = ch2;
    2958                 :          38 :   new_chain->rslt_type = rslt_type;
    2959                 :          38 :   new_chain->length = ch1->length;
    2960                 :             : 
    2961                 :         147 :   for (i = 0; (ch1->refs.iterate (i, &r1)
    2962                 :         256 :                && ch2->refs.iterate (i, &r2)); i++)
    2963                 :             :     {
    2964                 :         109 :       nw = XCNEW (class dref_d);
    2965                 :         109 :       nw->stmt = stmt_combining_refs (r1, r2);
    2966                 :         109 :       nw->distance = r1->distance;
    2967                 :             : 
    2968                 :         109 :       new_chain->refs.safe_push (nw);
    2969                 :             :     }
    2970                 :             : 
    2971                 :          38 :   ch1->combined = true;
    2972                 :          38 :   ch2->combined = true;
    2973                 :          38 :   return new_chain;
    2974                 :             : }
    2975                 :             : 
    2976                 :             : /* Recursively update position information of all offspring chains to ROOT
    2977                 :             :    chain's position information.  */
    2978                 :             : 
    2979                 :             : static void
    2980                 :          38 : update_pos_for_combined_chains (chain_p root)
    2981                 :             : {
    2982                 :          38 :   chain_p ch1 = root->ch1, ch2 = root->ch2;
    2983                 :          38 :   dref ref, ref1, ref2;
    2984                 :          38 :   for (unsigned j = 0; (root->refs.iterate (j, &ref)
    2985                 :         109 :                         && ch1->refs.iterate (j, &ref1)
    2986                 :         403 :                         && ch2->refs.iterate (j, &ref2)); ++j)
    2987                 :         109 :     ref1->pos = ref2->pos = ref->pos;
    2988                 :             : 
    2989                 :          38 :   if (ch1->type == CT_COMBINATION)
    2990                 :          19 :     update_pos_for_combined_chains (ch1);
    2991                 :          38 :   if (ch2->type == CT_COMBINATION)
    2992                 :             :     update_pos_for_combined_chains (ch2);
    2993                 :          38 : }
    2994                 :             : 
    2995                 :             : /* Returns true if statement S1 dominates statement S2.  */
    2996                 :             : 
    2997                 :             : static bool
    2998                 :          15 : pcom_stmt_dominates_stmt_p (gimple *s1, gimple *s2)
    2999                 :             : {
    3000                 :          15 :   basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
    3001                 :             : 
    3002                 :          15 :   if (!bb1 || s1 == s2)
    3003                 :             :     return true;
    3004                 :             : 
    3005                 :          15 :   if (bb1 == bb2)
    3006                 :          15 :     return gimple_uid (s1) < gimple_uid (s2);
    3007                 :             : 
    3008                 :           0 :   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
    3009                 :             : }
    3010                 :             : 
    3011                 :             : /* Try to combine the chains.  */
    3012                 :             : 
    3013                 :             : void
    3014                 :       14153 : pcom_worker::try_combine_chains ()
    3015                 :             : {
    3016                 :       14153 :   unsigned i, j;
    3017                 :       14153 :   chain_p ch1, ch2, cch;
    3018                 :       14153 :   auto_vec<chain_p> worklist;
    3019                 :       14153 :   bool combined_p = false;
    3020                 :             : 
    3021                 :       39893 :   FOR_EACH_VEC_ELT (m_chains, i, ch1)
    3022                 :       51480 :     if (chain_can_be_combined_p (ch1))
    3023                 :       12838 :       worklist.safe_push (ch1);
    3024                 :             : 
    3025                 :       54058 :   while (!worklist.is_empty ())
    3026                 :             :     {
    3027                 :       12876 :       ch1 = worklist.pop ();
    3028                 :       12876 :       if (!chain_can_be_combined_p (ch1))
    3029                 :          38 :         continue;
    3030                 :             : 
    3031                 :      111414 :       FOR_EACH_VEC_ELT (m_chains, j, ch2)
    3032                 :             :         {
    3033                 :       71585 :           if (!chain_can_be_combined_p (ch2))
    3034                 :         576 :             continue;
    3035                 :             : 
    3036                 :       71009 :           cch = combine_chains (ch1, ch2);
    3037                 :       71009 :           if (cch)
    3038                 :             :             {
    3039                 :          38 :               worklist.safe_push (cch);
    3040                 :          38 :               m_chains.safe_push (cch);
    3041                 :          38 :               combined_p = true;
    3042                 :          38 :               break;
    3043                 :             :             }
    3044                 :             :         }
    3045                 :             :     }
    3046                 :       14153 :   if (!combined_p)
    3047                 :       14139 :     return;
    3048                 :             : 
    3049                 :             :   /* Setup UID for all statements in dominance order.  */
    3050                 :          14 :   basic_block *bbs = get_loop_body_in_dom_order (m_loop);
    3051                 :          14 :   renumber_gimple_stmt_uids_in_blocks (bbs, m_loop->num_nodes);
    3052                 :          14 :   free (bbs);
    3053                 :             : 
    3054                 :             :   /* Re-association in combined chains may generate statements different to
    3055                 :             :      order of references of the original chain.  We need to keep references
    3056                 :             :      of combined chain in dominance order so that all uses will be inserted
    3057                 :             :      after definitions.  Note:
    3058                 :             :        A) This is necessary for all combined chains.
    3059                 :             :        B) This is only necessary for ZERO distance references because other
    3060                 :             :           references inherit value from loop carried PHIs.
    3061                 :             : 
    3062                 :             :      We first update position information for all combined chains.  */
    3063                 :          14 :   dref ref;
    3064                 :         114 :   for (i = 0; m_chains.iterate (i, &ch1); ++i)
    3065                 :             :     {
    3066                 :         100 :       if (ch1->type != CT_COMBINATION || ch1->combined)
    3067                 :          81 :         continue;
    3068                 :             : 
    3069                 :          70 :       for (j = 0; ch1->refs.iterate (j, &ref); ++j)
    3070                 :          51 :         ref->pos = gimple_uid (ref->stmt);
    3071                 :             : 
    3072                 :          19 :       update_pos_for_combined_chains (ch1);
    3073                 :             :     }
    3074                 :             :   /* Then sort references according to newly updated position information.  */
    3075                 :         128 :   for (i = 0; m_chains.iterate (i, &ch1); ++i)
    3076                 :             :     {
    3077                 :         100 :       if (ch1->type != CT_COMBINATION && !ch1->combined)
    3078                 :           5 :         continue;
    3079                 :             : 
    3080                 :             :       /* Find the first reference with non-ZERO distance.  */
    3081                 :          95 :       if (ch1->length == 0)
    3082                 :         107 :         j = ch1->refs.length();
    3083                 :             :       else
    3084                 :             :         {
    3085                 :         166 :           for (j = 0; ch1->refs.iterate (j, &ref); ++j)
    3086                 :         166 :             if (ref->distance != 0)
    3087                 :             :               break;
    3088                 :             :         }
    3089                 :             : 
    3090                 :             :       /* Sort all ZERO distance references by position.  */
    3091                 :          95 :       qsort (&ch1->refs[0], j, sizeof (ch1->refs[0]), order_drefs_by_pos);
    3092                 :             : 
    3093                 :          95 :       if (ch1->combined)
    3094                 :          76 :         continue;
    3095                 :             : 
    3096                 :             :       /* For ZERO length chain, has_max_use_after must be true since root
    3097                 :             :          combined stmt must dominates others.  */
    3098                 :          19 :       if (ch1->length == 0)
    3099                 :             :         {
    3100                 :           4 :           ch1->has_max_use_after = true;
    3101                 :           4 :           continue;
    3102                 :             :         }
    3103                 :             :       /* Check if there is use at max distance after root for combined chains
    3104                 :             :          and set flag accordingly.  */
    3105                 :          15 :       ch1->has_max_use_after = false;
    3106                 :          15 :       gimple *root_stmt = get_chain_root (ch1)->stmt;
    3107                 :         140 :       for (j = 1; ch1->refs.iterate (j, &ref); ++j)
    3108                 :             :         {
    3109                 :          28 :           if (ref->distance == ch1->length
    3110                 :          28 :               && !pcom_stmt_dominates_stmt_p (ref->stmt, root_stmt))
    3111                 :             :             {
    3112                 :           3 :               ch1->has_max_use_after = true;
    3113                 :           3 :               break;
    3114                 :             :             }
    3115                 :             :         }
    3116                 :             :     }
    3117                 :       14153 : }
    3118                 :             : 
    3119                 :             : /* Prepare initializers for store elimination CHAIN in LOOP.  Returns false
    3120                 :             :    if this is impossible because one of these initializers may trap, true
    3121                 :             :    otherwise.  */
    3122                 :             : 
    3123                 :             : static bool
    3124                 :          49 : prepare_initializers_chain_store_elim (class loop *loop, chain_p chain)
    3125                 :             : {
    3126                 :          49 :   unsigned i, n = chain->length;
    3127                 :             : 
    3128                 :             :   /* For now we can't eliminate stores if some of them are conditional
    3129                 :             :      executed.  */
    3130                 :          49 :   if (!chain->all_always_accessed)
    3131                 :             :     return false;
    3132                 :             : 
    3133                 :             :   /* Nothing to intialize for intra-iteration store elimination.  */
    3134                 :          49 :   if (n == 0 && chain->type == CT_STORE_STORE)
    3135                 :             :     return true;
    3136                 :             : 
    3137                 :             :   /* For store elimination chain, there is nothing to initialize if stores
    3138                 :             :      to be eliminated only store loop invariant values into memory.  */
    3139                 :          33 :   if (chain->type == CT_STORE_STORE
    3140                 :          33 :       && is_inv_store_elimination_chain (loop, chain))
    3141                 :             :     {
    3142                 :          10 :       chain->inv_store_elimination = true;
    3143                 :          10 :       return true;
    3144                 :             :     }
    3145                 :             : 
    3146                 :          23 :   chain->inits.create (n);
    3147                 :          23 :   chain->inits.safe_grow_cleared (n, true);
    3148                 :             : 
    3149                 :             :   /* For store eliminatin chain like below:
    3150                 :             : 
    3151                 :             :      for (i = 0; i < len; i++)
    3152                 :             :        {
    3153                 :             :          a[i] = 1;
    3154                 :             :          // a[i + 1] = ...
    3155                 :             :          a[i + 2] = 3;
    3156                 :             :        }
    3157                 :             : 
    3158                 :             :      store to a[i + 1] is missed in loop body, it acts like bubbles.  The
    3159                 :             :      content of a[i + 1] remain the same if the loop iterates fewer times
    3160                 :             :      than chain->length.  We need to set up root variables for such stores
    3161                 :             :      by loading from memory before loop.  Note we only need to load bubble
    3162                 :             :      elements because loop body is guaranteed to be executed at least once
    3163                 :             :      after loop's preheader edge.  */
    3164                 :          23 :   auto_vec<bool> bubbles;
    3165                 :          23 :   bubbles.safe_grow_cleared (n + 1, true);
    3166                 :         177 :   for (i = 0; i < chain->refs.length (); i++)
    3167                 :          54 :     bubbles[chain->refs[i]->distance] = true;
    3168                 :             : 
    3169                 :          23 :   struct data_reference *dr = get_chain_root (chain)->ref;
    3170                 :          62 :   for (i = 0; i < n; i++)
    3171                 :             :     {
    3172                 :          39 :       if (bubbles[i])
    3173                 :          29 :         continue;
    3174                 :             : 
    3175                 :          10 :       gimple_seq stmts = NULL;
    3176                 :             : 
    3177                 :          10 :       tree init = ref_at_iteration (dr, (int) 0 - i, &stmts);
    3178                 :          10 :       if (stmts)
    3179                 :           2 :         gimple_seq_add_seq_without_update (&chain->init_seq, stmts);
    3180                 :             : 
    3181                 :          10 :       chain->inits[i] = init;
    3182                 :             :     }
    3183                 :             : 
    3184                 :          23 :   return true;
    3185                 :          23 : }
    3186                 :             : 
    3187                 :             : /* Prepare initializers for CHAIN.  Returns false if this is impossible
    3188                 :             :    because one of these initializers may trap, true otherwise.  */
    3189                 :             : 
    3190                 :             : bool
    3191                 :       27793 : pcom_worker::prepare_initializers_chain (chain_p chain)
    3192                 :             : {
    3193                 :       27793 :   unsigned i, n = (chain->type == CT_INVARIANT) ? 1 : chain->length;
    3194                 :       27793 :   struct data_reference *dr = get_chain_root (chain)->ref;
    3195                 :       27793 :   tree init;
    3196                 :       27793 :   dref laref;
    3197                 :       27793 :   edge entry = loop_preheader_edge (m_loop);
    3198                 :             : 
    3199                 :       27793 :   if (chain->type == CT_STORE_STORE)
    3200                 :          49 :     return prepare_initializers_chain_store_elim (m_loop, chain);
    3201                 :             : 
    3202                 :             :   /* Find the initializers for the variables, and check that they cannot
    3203                 :             :      trap.  */
    3204                 :       27744 :   chain->inits.create (n);
    3205                 :       77543 :   for (i = 0; i < n; i++)
    3206                 :       22055 :     chain->inits.quick_push (NULL_TREE);
    3207                 :             : 
    3208                 :             :   /* If we have replaced some looparound phi nodes, use their initializers
    3209                 :             :      instead of creating our own.  */
    3210                 :       73179 :   FOR_EACH_VEC_ELT (chain->refs, i, laref)
    3211                 :             :     {
    3212                 :       45435 :       if (gimple_code (laref->stmt) != GIMPLE_PHI)
    3213                 :       45422 :         continue;
    3214                 :             : 
    3215                 :          13 :       gcc_assert (laref->distance > 0);
    3216                 :          13 :       chain->inits[n - laref->distance] 
    3217                 :          26 :         = PHI_ARG_DEF_FROM_EDGE (laref->stmt, entry);
    3218                 :             :     }
    3219                 :             : 
    3220                 :       47746 :   for (i = 0; i < n; i++)
    3221                 :             :     {
    3222                 :       22055 :       gimple_seq stmts = NULL;
    3223                 :             : 
    3224                 :       22055 :       if (chain->inits[i] != NULL_TREE)
    3225                 :          13 :         continue;
    3226                 :             : 
    3227                 :       22042 :       init = ref_at_iteration (dr, (int) i - n, &stmts);
    3228                 :       22042 :       if (!chain->all_always_accessed && tree_could_trap_p (init))
    3229                 :             :         {
    3230                 :        2053 :           gimple_seq_discard (stmts);
    3231                 :        2053 :           return false;
    3232                 :             :         }
    3233                 :             : 
    3234                 :       19989 :       if (stmts)
    3235                 :        1106 :         gimple_seq_add_seq_without_update (&chain->init_seq, stmts);
    3236                 :             : 
    3237                 :       19989 :       chain->inits[i] = init;
    3238                 :             :     }
    3239                 :             : 
    3240                 :             :   return true;
    3241                 :             : }
    3242                 :             : 
    3243                 :             : /* Prepare initializers for chains, and free chains that cannot
    3244                 :             :    be used because the initializers might trap.  */
    3245                 :             : 
    3246                 :             : void
    3247                 :       14153 : pcom_worker::prepare_initializers ()
    3248                 :             : {
    3249                 :       14153 :   chain_p chain;
    3250                 :       14153 :   unsigned i;
    3251                 :             : 
    3252                 :       83892 :   for (i = 0; i < m_chains.length (); )
    3253                 :             :     {
    3254                 :       27793 :       chain = m_chains[i];
    3255                 :       27793 :       if (prepare_initializers_chain (chain))
    3256                 :       25740 :         i++;
    3257                 :             :       else
    3258                 :             :         {
    3259                 :        2053 :           release_chain (chain);
    3260                 :        2053 :           m_chains.unordered_remove (i);
    3261                 :             :         }
    3262                 :             :     }
    3263                 :       14153 : }
    3264                 :             : 
    3265                 :             : /* Generates finalizer memory references for CHAIN.  Returns true
    3266                 :             :    if finalizer code for CHAIN can be generated, otherwise false.  */
    3267                 :             : 
    3268                 :             : bool
    3269                 :          33 : pcom_worker::prepare_finalizers_chain (chain_p chain)
    3270                 :             : {
    3271                 :          33 :   unsigned i, n = chain->length;
    3272                 :          33 :   struct data_reference *dr = get_chain_root (chain)->ref;
    3273                 :          33 :   tree fini, niters = number_of_latch_executions (m_loop);
    3274                 :             : 
    3275                 :             :   /* For now we can't eliminate stores if some of them are conditional
    3276                 :             :      executed.  */
    3277                 :          33 :   if (!chain->all_always_accessed)
    3278                 :             :     return false;
    3279                 :             : 
    3280                 :          33 :   chain->finis.create (n);
    3281                 :         127 :   for (i = 0; i < n; i++)
    3282                 :          61 :     chain->finis.quick_push (NULL_TREE);
    3283                 :             : 
    3284                 :             :   /* We never use looparound phi node for store elimination chains.  */
    3285                 :             : 
    3286                 :             :   /* Find the finalizers for the variables, and check that they cannot
    3287                 :             :      trap.  */
    3288                 :          94 :   for (i = 0; i < n; i++)
    3289                 :             :     {
    3290                 :          61 :       gimple_seq stmts = NULL;
    3291                 :          61 :       gcc_assert (chain->finis[i] == NULL_TREE);
    3292                 :             : 
    3293                 :          61 :       if (TREE_CODE (niters) != INTEGER_CST && TREE_CODE (niters) != SSA_NAME)
    3294                 :             :         {
    3295                 :          11 :           niters = unshare_expr (niters);
    3296                 :          11 :           niters = force_gimple_operand (niters, &stmts, true, NULL);
    3297                 :          11 :           if (stmts)
    3298                 :             :             {
    3299                 :          11 :               gimple_seq_add_seq_without_update (&chain->fini_seq, stmts);
    3300                 :          11 :               stmts = NULL;
    3301                 :             :             }
    3302                 :             :         }
    3303                 :          61 :       fini = ref_at_iteration (dr, (int) 0 - i, &stmts, niters);
    3304                 :          61 :       if (stmts)
    3305                 :          26 :         gimple_seq_add_seq_without_update (&chain->fini_seq, stmts);
    3306                 :             : 
    3307                 :          61 :       chain->finis[i] = fini;
    3308                 :             :     }
    3309                 :             : 
    3310                 :             :   return true;
    3311                 :             : }
    3312                 :             : 
    3313                 :             : /* Generates finalizer memory reference for chains.  Returns true if
    3314                 :             :    finalizer code generation for chains breaks loop closed ssa form.  */
    3315                 :             : 
    3316                 :             : bool
    3317                 :       14153 : pcom_worker::prepare_finalizers ()
    3318                 :             : {
    3319                 :       14153 :   chain_p chain;
    3320                 :       14153 :   unsigned i;
    3321                 :       14153 :   bool loop_closed_ssa = false;
    3322                 :             : 
    3323                 :       79786 :   for (i = 0; i < m_chains.length ();)
    3324                 :             :     {
    3325                 :       25740 :       chain = m_chains[i];
    3326                 :             : 
    3327                 :             :       /* Finalizer is only necessary for inter-iteration store elimination
    3328                 :             :          chains.  */
    3329                 :       25740 :       if (chain->length == 0 || chain->type != CT_STORE_STORE)
    3330                 :             :         {
    3331                 :       25707 :           i++;
    3332                 :       25707 :           continue;
    3333                 :             :         }
    3334                 :             : 
    3335                 :          33 :       if (prepare_finalizers_chain (chain))
    3336                 :             :         {
    3337                 :          33 :           i++;
    3338                 :             :           /* Be conservative, assume loop closed ssa form is corrupted
    3339                 :             :              by store-store chain.  Though it's not always the case if
    3340                 :             :              eliminated stores only store loop invariant values into
    3341                 :             :              memory.  */
    3342                 :          33 :           loop_closed_ssa = true;
    3343                 :             :         }
    3344                 :             :       else
    3345                 :             :         {
    3346                 :           0 :           release_chain (chain);
    3347                 :           0 :           m_chains.unordered_remove (i);
    3348                 :             :         }
    3349                 :             :     }
    3350                 :       14153 :   return loop_closed_ssa;
    3351                 :             : }
    3352                 :             : 
    3353                 :             : /* Insert all initializing gimple stmts into LOOP's entry edge.  */
    3354                 :             : 
    3355                 :             : static void
    3356                 :       14153 : insert_init_seqs (class loop *loop, vec<chain_p> &chains)
    3357                 :             : {
    3358                 :       14153 :   unsigned i;
    3359                 :       14153 :   edge entry = loop_preheader_edge (loop);
    3360                 :             : 
    3361                 :       94015 :   for (i = 0; i < chains.length (); ++i)
    3362                 :       25778 :     if (chains[i]->init_seq)
    3363                 :             :       {
    3364                 :        1070 :         gsi_insert_seq_on_edge_immediate (entry, chains[i]->init_seq);
    3365                 :        1070 :         chains[i]->init_seq = NULL;
    3366                 :             :       }
    3367                 :       14153 : }
    3368                 :             : 
    3369                 :             : /* Performs predictive commoning for LOOP.  Sets bit 1<<1 of return value
    3370                 :             :    if LOOP was unrolled; Sets bit 1<<2 of return value if loop closed ssa
    3371                 :             :    form was corrupted.  Non-zero return value indicates some changes were
    3372                 :             :    applied to this loop.  */
    3373                 :             : 
    3374                 :             : unsigned
    3375                 :      362052 : pcom_worker::tree_predictive_commoning_loop (bool allow_unroll_p)
    3376                 :             : {
    3377                 :      362052 :   struct component *components;
    3378                 :      362052 :   unsigned unroll_factor = 0;
    3379                 :      362052 :   class tree_niter_desc desc;
    3380                 :      362052 :   bool unroll = false, loop_closed_ssa = false;
    3381                 :             : 
    3382                 :      362052 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3383                 :          56 :     fprintf (dump_file, "Processing loop %d\n", m_loop->num);
    3384                 :             : 
    3385                 :             :   /* Nothing for predicitive commoning if loop only iterates 1 time.  */
    3386                 :      362052 :   if (get_max_loop_iterations_int (m_loop) == 0)
    3387                 :             :     {
    3388                 :       19876 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3389                 :           1 :         fprintf (dump_file, "Loop iterates only 1 time, nothing to do.\n");
    3390                 :             : 
    3391                 :       19876 :       return 0;
    3392                 :             :     }
    3393                 :             : 
    3394                 :             :   /* Find the data references and split them into components according to their
    3395                 :             :      dependence relations.  */
    3396                 :      342176 :   auto_vec<loop_p, 3> loop_nest;
    3397                 :      342176 :   if (!compute_data_dependences_for_loop (m_loop, true, &loop_nest, &m_datarefs,
    3398                 :             :                                           &m_dependences))
    3399                 :             :     {
    3400                 :      134310 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3401                 :           0 :         fprintf (dump_file, "Cannot analyze data dependencies\n");
    3402                 :      134310 :       return 0;
    3403                 :             :     }
    3404                 :             : 
    3405                 :      207866 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3406                 :          55 :     dump_data_dependence_relations (dump_file, m_dependences);
    3407                 :             : 
    3408                 :      207866 :   components = split_data_refs_to_components ();
    3409                 :             : 
    3410                 :      207866 :   loop_nest.release ();
    3411                 :      207866 :   if (!components)
    3412                 :             :     return 0;
    3413                 :             : 
    3414                 :      140347 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3415                 :             :     {
    3416                 :          54 :       fprintf (dump_file, "Initial state:\n\n");
    3417                 :          54 :       dump_components (dump_file, components);
    3418                 :             :     }
    3419                 :             : 
    3420                 :             :   /* Find the suitable components and split them into chains.  */
    3421                 :      140347 :   components = filter_suitable_components (components);
    3422                 :             : 
    3423                 :      140347 :   auto_bitmap tmp_vars;
    3424                 :      140347 :   determine_roots (components);
    3425                 :      140347 :   release_components (components);
    3426                 :             : 
    3427                 :      140347 :   if (!m_chains.exists ())
    3428                 :             :     {
    3429                 :      126194 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3430                 :          20 :         fprintf (dump_file,
    3431                 :             :                  "Predictive commoning failed: no suitable chains\n");
    3432                 :      126194 :       return 0;
    3433                 :             :     }
    3434                 :             : 
    3435                 :       14153 :   prepare_initializers ();
    3436                 :       14153 :   loop_closed_ssa = prepare_finalizers ();
    3437                 :             : 
    3438                 :             :   /* Try to combine the chains that are always worked with together.  */
    3439                 :       14153 :   try_combine_chains ();
    3440                 :             : 
    3441                 :       14153 :   insert_init_seqs (m_loop, m_chains);
    3442                 :             : 
    3443                 :       14153 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3444                 :             :     {
    3445                 :          34 :       fprintf (dump_file, "Before commoning:\n\n");
    3446                 :          34 :       dump_chains (dump_file, m_chains);
    3447                 :             :     }
    3448                 :             : 
    3449                 :       14153 :   if (allow_unroll_p)
    3450                 :             :     /* Determine the unroll factor, and if the loop should be unrolled, ensure
    3451                 :             :        that its number of iterations is divisible by the factor.  */
    3452                 :        2971 :     unroll_factor = determine_unroll_factor (m_chains);
    3453                 :             : 
    3454                 :        2971 :   if (unroll_factor > 1)
    3455                 :         604 :     unroll = can_unroll_loop_p (m_loop, unroll_factor, &desc);
    3456                 :             : 
    3457                 :             :   /* Execute the predictive commoning transformations, and possibly unroll the
    3458                 :             :      loop.  */
    3459                 :         604 :   if (unroll)
    3460                 :             :     {
    3461                 :         591 :       struct epcc_data dta;
    3462                 :             : 
    3463                 :         591 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3464                 :           9 :         fprintf (dump_file, "Unrolling %u times.\n", unroll_factor);
    3465                 :             : 
    3466                 :         591 :       dta.tmp_vars = tmp_vars;
    3467                 :         591 :       dta.chains = m_chains.to_vec_legacy ();
    3468                 :         591 :       dta.worker = this;
    3469                 :             : 
    3470                 :             :       /* Cfg manipulations performed in tree_transform_and_unroll_loop before
    3471                 :             :          execute_pred_commoning_cbck is called may cause phi nodes to be
    3472                 :             :          reallocated, which is a problem since CHAINS may point to these
    3473                 :             :          statements.  To fix this, we store the ssa names defined by the
    3474                 :             :          phi nodes here instead of the phi nodes themselves, and restore
    3475                 :             :          the phi nodes in execute_pred_commoning_cbck.  A bit hacky.  */
    3476                 :         591 :       replace_phis_by_defined_names (m_chains);
    3477                 :             : 
    3478                 :         591 :       tree_transform_and_unroll_loop (m_loop, unroll_factor, &desc,
    3479                 :             :                                       execute_pred_commoning_cbck, &dta);
    3480                 :         591 :       eliminate_temp_copies (m_loop, tmp_vars);
    3481                 :             :     }
    3482                 :             :   else
    3483                 :             :     {
    3484                 :       13562 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3485                 :          25 :         fprintf (dump_file,
    3486                 :             :                  "Executing predictive commoning without unrolling.\n");
    3487                 :       13562 :       execute_pred_commoning (tmp_vars);
    3488                 :             :     }
    3489                 :             : 
    3490                 :       41836 :   return (unroll ? 2 : 1) | (loop_closed_ssa ? 4 : 1);
    3491                 :      482523 : }
    3492                 :             : 
    3493                 :             : /* Runs predictive commoning.  */
    3494                 :             : 
    3495                 :             : unsigned
    3496                 :      190067 : tree_predictive_commoning (bool allow_unroll_p)
    3497                 :             : {
    3498                 :      190067 :   unsigned ret = 0, changed = 0;
    3499                 :             : 
    3500                 :      190067 :   initialize_original_copy_tables ();
    3501                 :      952063 :   for (auto loop : loops_list (cfun, LI_ONLY_INNERMOST))
    3502                 :      381862 :     if (optimize_loop_for_speed_p (loop))
    3503                 :             :       {
    3504                 :      362052 :         pcom_worker w(loop);
    3505                 :      362052 :         changed |= w.tree_predictive_commoning_loop (allow_unroll_p);
    3506                 :      362052 :       }
    3507                 :      190067 :   free_original_copy_tables ();
    3508                 :             : 
    3509                 :      190067 :   if (changed > 0)
    3510                 :             :     {
    3511                 :        9528 :       ret = TODO_update_ssa_only_virtuals;
    3512                 :             : 
    3513                 :             :       /* Some loop(s) got unrolled.  */
    3514                 :        9528 :       if (changed > 1)
    3515                 :             :         {
    3516                 :         545 :           scev_reset ();
    3517                 :             : 
    3518                 :             :           /* Need to fix up loop closed SSA.  */
    3519                 :         545 :           if (changed >= 4)
    3520                 :          32 :             rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
    3521                 :             : 
    3522                 :             :           ret |= TODO_cleanup_cfg;
    3523                 :             :         }
    3524                 :             :     }
    3525                 :             : 
    3526                 :             :   if (ret != 0)
    3527                 :        9528 :     cfun->pending_TODOs |= PENDING_TODO_force_next_scalar_cleanup;
    3528                 :             : 
    3529                 :      190067 :   return ret;
    3530                 :             : }
    3531                 :             : 
    3532                 :             : /* Predictive commoning Pass.  */
    3533                 :             : 
    3534                 :             : static unsigned
    3535                 :      190067 : run_tree_predictive_commoning (struct function *fun, bool allow_unroll_p)
    3536                 :             : {
    3537                 :      380134 :   if (number_of_loops (fun) <= 1)
    3538                 :             :     return 0;
    3539                 :             : 
    3540                 :      190067 :   return tree_predictive_commoning (allow_unroll_p);
    3541                 :             : }
    3542                 :             : 
    3543                 :             : namespace {
    3544                 :             : 
    3545                 :             : const pass_data pass_data_predcom =
    3546                 :             : {
    3547                 :             :   GIMPLE_PASS, /* type */
    3548                 :             :   "pcom", /* name */
    3549                 :             :   OPTGROUP_LOOP, /* optinfo_flags */
    3550                 :             :   TV_PREDCOM, /* tv_id */
    3551                 :             :   PROP_cfg, /* properties_required */
    3552                 :             :   0, /* properties_provided */
    3553                 :             :   0, /* properties_destroyed */
    3554                 :             :   0, /* todo_flags_start */
    3555                 :             :   0, /* todo_flags_finish */
    3556                 :             : };
    3557                 :             : 
    3558                 :             : class pass_predcom : public gimple_opt_pass
    3559                 :             : {
    3560                 :             : public:
    3561                 :      273196 :   pass_predcom (gcc::context *ctxt)
    3562                 :      546392 :     : gimple_opt_pass (pass_data_predcom, ctxt)
    3563                 :             :   {}
    3564                 :             : 
    3565                 :             :   /* opt_pass methods: */
    3566                 :             :   bool
    3567                 :      221759 :   gate (function *) final override
    3568                 :             :   {
    3569                 :      221759 :     if (flag_predictive_commoning != 0)
    3570                 :             :       return true;
    3571                 :             :     /* Loop vectorization enables predictive commoning implicitly
    3572                 :             :        only if predictive commoning isn't set explicitly, and it
    3573                 :             :        doesn't allow unrolling.  */
    3574                 :      197039 :     if (flag_tree_loop_vectorize
    3575                 :      165348 :         && !OPTION_SET_P (flag_predictive_commoning))
    3576                 :      165348 :       return true;
    3577                 :             : 
    3578                 :             :     return false;
    3579                 :             :   }
    3580                 :             : 
    3581                 :             :   unsigned int
    3582                 :      190067 :   execute (function *fun) final override
    3583                 :             :   {
    3584                 :      190067 :     bool allow_unroll_p = flag_predictive_commoning != 0;
    3585                 :      190067 :     return run_tree_predictive_commoning (fun, allow_unroll_p);
    3586                 :             :   }
    3587                 :             : 
    3588                 :             : }; // class pass_predcom
    3589                 :             : 
    3590                 :             : } // anon namespace
    3591                 :             : 
    3592                 :             : gimple_opt_pass *
    3593                 :      273196 : make_pass_predcom (gcc::context *ctxt)
    3594                 :             : {
    3595                 :      273196 :   return new pass_predcom (ctxt);
    3596                 :             : }
        

Generated by: LCOV version 2.1-beta

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,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.