LCOV - code coverage report
Current view: top level - gcc - tree-ssa-loop-im.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 97.9 % 1680 1644
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 80 80
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Loop invariant motion.
       2              :    Copyright (C) 2003-2026 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              : #include "config.h"
      21              : #include "system.h"
      22              : #include "coretypes.h"
      23              : #include "backend.h"
      24              : #include "tree.h"
      25              : #include "gimple.h"
      26              : #include "cfghooks.h"
      27              : #include "tree-pass.h"
      28              : #include "ssa.h"
      29              : #include "gimple-pretty-print.h"
      30              : #include "fold-const.h"
      31              : #include "cfganal.h"
      32              : #include "tree-eh.h"
      33              : #include "gimple-iterator.h"
      34              : #include "tree-cfg.h"
      35              : #include "tree-ssa-loop-manip.h"
      36              : #include "tree-ssa-loop.h"
      37              : #include "tree-into-ssa.h"
      38              : #include "cfgloop.h"
      39              : #include "tree-affine.h"
      40              : #include "tree-ssa-propagate.h"
      41              : #include "trans-mem.h"
      42              : #include "gimple-fold.h"
      43              : #include "tree-scalar-evolution.h"
      44              : #include "tree-ssa-loop-niter.h"
      45              : #include "alias.h"
      46              : #include "builtins.h"
      47              : #include "tree-dfa.h"
      48              : #include "tree-ssa.h"
      49              : #include "dbgcnt.h"
      50              : #include "insn-codes.h"
      51              : #include "optabs-tree.h"
      52              : 
      53              : /* TODO:  Support for predicated code motion.  I.e.
      54              : 
      55              :    while (1)
      56              :      {
      57              :        if (cond)
      58              :          {
      59              :            a = inv;
      60              :            something;
      61              :          }
      62              :      }
      63              : 
      64              :    Where COND and INV are invariants, but evaluating INV may trap or be
      65              :    invalid from some other reason if !COND.  This may be transformed to
      66              : 
      67              :    if (cond)
      68              :      a = inv;
      69              :    while (1)
      70              :      {
      71              :        if (cond)
      72              :          something;
      73              :      }  */
      74              : 
      75              : /* The auxiliary data kept for each statement.  */
      76              : 
      77              : struct lim_aux_data
      78              : {
      79              :   class loop *max_loop; /* The outermost loop in that the statement
      80              :                                    is invariant.  */
      81              : 
      82              :   class loop *tgt_loop; /* The loop out of that we want to move the
      83              :                                    invariant.  */
      84              : 
      85              :   class loop *always_executed_in;
      86              :                                 /* The outermost loop for that we are sure
      87              :                                    the statement is executed if the loop
      88              :                                    is entered.  */
      89              : 
      90              :   unsigned cost;                /* Cost of the computation performed by the
      91              :                                    statement.  */
      92              : 
      93              :   unsigned ref;                 /* The simple_mem_ref in this stmt or 0.  */
      94              : 
      95              :   vec<gimple *> depends;  /* Vector of statements that must be also
      96              :                                    hoisted out of the loop when this statement
      97              :                                    is hoisted; i.e. those that define the
      98              :                                    operands of the statement and are inside of
      99              :                                    the MAX_LOOP loop.  */
     100              : };
     101              : 
     102              : /* Maps statements to their lim_aux_data.  */
     103              : 
     104              : static hash_map<gimple *, lim_aux_data *> *lim_aux_data_map;
     105              : 
     106              : /* Description of a memory reference location.  */
     107              : 
     108              : struct mem_ref_loc
     109              : {
     110              :   tree *ref;                    /* The reference itself.  */
     111              :   gimple *stmt;                 /* The statement in that it occurs.  */
     112              : };
     113              : 
     114              : 
     115              : /* Description of a memory reference.  */
     116              : 
     117              : class im_mem_ref
     118              : {
     119              : public:
     120              :   unsigned id : 30;             /* ID assigned to the memory reference
     121              :                                    (its index in memory_accesses.refs_list)  */
     122              :   unsigned ref_canonical : 1;   /* Whether mem.ref was canonicalized.  */
     123              :   unsigned ref_decomposed : 1;  /* Whether the ref was hashed from mem.  */
     124              :   hashval_t hash;               /* Its hash value.  */
     125              : 
     126              :   /* The memory access itself and associated caching of alias-oracle
     127              :      query meta-data.  We are using mem.ref == error_mark_node for the
     128              :      case the reference is represented by its single access stmt
     129              :      in accesses_in_loop[0].  */
     130              :   ao_ref mem;
     131              : 
     132              :   bitmap stored;                /* The set of loops in that this memory location
     133              :                                    is stored to.  */
     134              :   bitmap loaded;                /* The set of loops in that this memory location
     135              :                                    is loaded from.  */
     136              :   vec<mem_ref_loc>                accesses_in_loop;
     137              :                                 /* The locations of the accesses.  */
     138              : 
     139              :   /* The following set is computed on demand.  */
     140              :   bitmap_head dep_loop;         /* The set of loops in that the memory
     141              :                                    reference is {in,}dependent in
     142              :                                    different modes.  */
     143              : };
     144              : 
     145              : static bool in_loop_pipeline;
     146              : 
     147              : /* We use six bits per loop in the ref->dep_loop bitmap to record
     148              :    the dep_kind x dep_state combinations.  */
     149              : 
     150              : enum dep_kind { lim_raw, sm_war, sm_waw };
     151              : enum dep_state { dep_unknown, dep_independent, dep_dependent };
     152              : 
     153              : /* coldest outermost loop for given loop.  */
     154              : vec<class loop *> coldest_outermost_loop;
     155              : /* hotter outer loop nearest to given loop.  */
     156              : vec<class loop *> hotter_than_inner_loop;
     157              : 
     158              : /* Populate the loop dependence cache of REF for LOOP, KIND with STATE.  */
     159              : 
     160              : static void
     161      2127983 : record_loop_dependence (class loop *loop, im_mem_ref *ref,
     162              :                         dep_kind kind, dep_state state)
     163              : {
     164      2127983 :   gcc_assert (state != dep_unknown);
     165      2127983 :   unsigned bit = 6 * loop->num + kind * 2 + state == dep_dependent ? 1 : 0;
     166      2127983 :   bitmap_set_bit (&ref->dep_loop, bit);
     167      2127983 : }
     168              : 
     169              : /* Query the loop dependence cache of REF for LOOP, KIND.  */
     170              : 
     171              : static dep_state
     172       691293 : query_loop_dependence (class loop *loop, im_mem_ref *ref, dep_kind kind)
     173              : {
     174       691293 :   unsigned first_bit = 6 * loop->num + kind * 2;
     175       691293 :   if (bitmap_bit_p (&ref->dep_loop, first_bit))
     176              :     return dep_independent;
     177       691293 :   else if (bitmap_bit_p (&ref->dep_loop, first_bit + 1))
     178            0 :     return dep_dependent;
     179              :   return dep_unknown;
     180              : }
     181              : 
     182              : /* Mem_ref hashtable helpers.  */
     183              : 
     184              : struct mem_ref_hasher : nofree_ptr_hash <im_mem_ref>
     185              : {
     186              :   typedef ao_ref *compare_type;
     187              :   static inline hashval_t hash (const im_mem_ref *);
     188              :   static inline bool equal (const im_mem_ref *, const ao_ref *);
     189              : };
     190              : 
     191              : /* A hash function for class im_mem_ref object OBJ.  */
     192              : 
     193              : inline hashval_t
     194     11925904 : mem_ref_hasher::hash (const im_mem_ref *mem)
     195              : {
     196     11925904 :   return mem->hash;
     197              : }
     198              : 
     199              : /* An equality function for class im_mem_ref object MEM1 with
     200              :    memory reference OBJ2.  */
     201              : 
     202              : inline bool
     203     53882185 : mem_ref_hasher::equal (const im_mem_ref *mem1, const ao_ref *obj2)
     204              : {
     205     53882185 :   if (!obj2->max_size_known_p ())
     206      1477876 :     return operand_equal_p (mem1->mem.ref, obj2->ref, 0);
     207              : 
     208     52404309 :   if (!mem1->ref_decomposed)
     209              :     return false;
     210              : 
     211              :   /* obj2 is now known decomposable and the hash is based on offset,
     212              :      size and base, matching gather_mem_refs_stmt.  */
     213     51744220 :   bool refs_equal
     214     51744220 :     = ((TREE_CODE (mem1->mem.base) == MEM_REF
     215      4896307 :         && TREE_CODE (obj2->base) == MEM_REF
     216      3300834 :         && operand_equal_p (TREE_OPERAND (mem1->mem.base, 0),
     217      3300834 :                             TREE_OPERAND (obj2->base, 0), 0)
     218      1991685 :         && known_eq (mem_ref_offset (mem1->mem.base) * BITS_PER_UNIT
     219              :                      + mem1->mem.offset,
     220              :                      mem_ref_offset (obj2->base) * BITS_PER_UNIT
     221              :                      + obj2->offset))
     222     56184950 :        || (operand_equal_p (mem1->mem.base, obj2->base, 0)
     223       839146 :            && known_eq (mem1->mem.offset, obj2->offset)));
     224              : 
     225     51744220 :   return (refs_equal
     226       943814 :           && known_eq (mem1->mem.size, obj2->size)
     227       941215 :           && known_eq (mem1->mem.max_size, obj2->max_size)
     228       941215 :           && mem1->mem.volatile_p == obj2->volatile_p
     229       941199 :           && (mem1->mem.ref_alias_set == obj2->ref_alias_set
     230              :               /* We are not canonicalizing alias-sets but for the
     231              :                  special-case we didn't canonicalize yet and the
     232              :                  incoming ref is a alias-set zero MEM we pick
     233              :                  the correct one already.  */
     234        15740 :               || (!mem1->ref_canonical
     235        14179 :                   && (TREE_CODE (obj2->ref) == MEM_REF
     236        14179 :                       || TREE_CODE (obj2->ref) == TARGET_MEM_REF)
     237         8725 :                   && obj2->ref_alias_set == 0)
     238              :               /* Likewise if there's a canonical ref with alias-set zero.  */
     239        12657 :               || (mem1->ref_canonical && mem1->mem.ref_alias_set == 0))
     240       929357 :           && types_compatible_p (TREE_TYPE (mem1->mem.ref),
     241       929357 :                                  TREE_TYPE (obj2->ref)));
     242              : }
     243              : 
     244              : 
     245              : /* Description of memory accesses in loops.  */
     246              : 
     247              : static struct
     248              : {
     249              :   /* The hash table of memory references accessed in loops.  */
     250              :   hash_table<mem_ref_hasher> *refs;
     251              : 
     252              :   /* The list of memory references.  */
     253              :   vec<im_mem_ref *> refs_list;
     254              : 
     255              :   /* The set of memory references accessed in each loop.  */
     256              :   vec<bitmap_head> refs_loaded_in_loop;
     257              : 
     258              :   /* The set of memory references stored in each loop.  */
     259              :   vec<bitmap_head> refs_stored_in_loop;
     260              : 
     261              :   /* The set of memory references stored in each loop, including subloops .  */
     262              :   vec<bitmap_head> all_refs_stored_in_loop;
     263              : 
     264              :   /* Cache for expanding memory addresses.  */
     265              :   hash_map<tree, name_expansion *> *ttae_cache;
     266              : } memory_accesses;
     267              : 
     268              : /* Obstack for the bitmaps in the above data structures.  */
     269              : static bitmap_obstack lim_bitmap_obstack;
     270              : static obstack mem_ref_obstack;
     271              : 
     272              : static bool ref_indep_loop_p (class loop *, im_mem_ref *, dep_kind);
     273              : static bool ref_always_stored_p (class loop *, im_mem_ref *);
     274              : static bool refs_independent_p (im_mem_ref *, im_mem_ref *, bool = true);
     275              : 
     276              : /* Minimum cost of an expensive expression.  */
     277              : #define LIM_EXPENSIVE ((unsigned) param_lim_expensive)
     278              : 
     279              : /* The outermost loop for which execution of the header guarantees that the
     280              :    block will be executed.  */
     281              : #define ALWAYS_EXECUTED_IN(BB) ((class loop *) (BB)->aux)
     282              : #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
     283              : 
     284              : /* ID of the shared unanalyzable mem.  */
     285              : #define UNANALYZABLE_MEM_ID 0
     286              : 
     287              : /* Whether the reference was analyzable.  */
     288              : #define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
     289              : 
     290              : static struct lim_aux_data *
     291     18299571 : init_lim_data (gimple *stmt)
     292              : {
     293     18299571 :   lim_aux_data *p = XCNEW (struct lim_aux_data);
     294     18299571 :   lim_aux_data_map->put (stmt, p);
     295              : 
     296     18299571 :   return p;
     297              : }
     298              : 
     299              : static struct lim_aux_data *
     300     98936131 : get_lim_data (gimple *stmt)
     301              : {
     302     98936131 :   lim_aux_data **p = lim_aux_data_map->get (stmt);
     303     98936131 :   if (!p)
     304              :     return NULL;
     305              : 
     306     49741477 :   return *p;
     307              : }
     308              : 
     309              : /* Releases the memory occupied by DATA.  */
     310              : 
     311              : static void
     312     18299386 : free_lim_aux_data (struct lim_aux_data *data)
     313              : {
     314            0 :   data->depends.release ();
     315     18299386 :   free (data);
     316            0 : }
     317              : 
     318              : static void
     319     18299386 : clear_lim_data (gimple *stmt)
     320              : {
     321     18299386 :   lim_aux_data **p = lim_aux_data_map->get (stmt);
     322     18299386 :   if (!p)
     323              :     return;
     324              : 
     325     18299386 :   free_lim_aux_data (*p);
     326     18299386 :   *p = NULL;
     327              : }
     328              : 
     329              : 
     330              : /* The possibilities of statement movement.  */
     331              : enum move_pos
     332              :   {
     333              :     MOVE_IMPOSSIBLE,            /* No movement -- side effect expression.  */
     334              :     MOVE_PRESERVE_EXECUTION,    /* Must not cause the non-executed statement
     335              :                                    become executed -- memory accesses, ... */
     336              :     MOVE_POSSIBLE               /* Unlimited movement.  */
     337              :   };
     338              : 
     339              : 
     340              : /* If it is possible to hoist the statement STMT unconditionally,
     341              :    returns MOVE_POSSIBLE.
     342              :    If it is possible to hoist the statement STMT, but we must avoid making
     343              :    it executed if it would not be executed in the original program (e.g.
     344              :    because it may trap), return MOVE_PRESERVE_EXECUTION.
     345              :    Otherwise return MOVE_IMPOSSIBLE.  */
     346              : 
     347              : static enum move_pos
     348     49677931 : movement_possibility_1 (gimple *stmt)
     349              : {
     350     49677931 :   tree lhs;
     351     49677931 :   enum move_pos ret = MOVE_POSSIBLE;
     352              : 
     353     49677931 :   if (flag_unswitch_loops
     354     49677931 :       && gimple_code (stmt) == GIMPLE_COND)
     355              :     {
     356              :       /* If we perform unswitching, force the operands of the invariant
     357              :          condition to be moved out of the loop.  */
     358              :       return MOVE_POSSIBLE;
     359              :     }
     360              : 
     361     49299664 :   if (gimple_code (stmt) == GIMPLE_PHI
     362      2664000 :       && gimple_phi_num_args (stmt) <= 2
     363      4966898 :       && !virtual_operand_p (gimple_phi_result (stmt))
     364     50783383 :       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)))
     365              :     return MOVE_POSSIBLE;
     366              : 
     367     47816211 :   if (gimple_get_lhs (stmt) == NULL_TREE)
     368              :     return MOVE_IMPOSSIBLE;
     369              : 
     370     32586329 :   if (gimple_vdef (stmt))
     371              :     return MOVE_IMPOSSIBLE;
     372              : 
     373     13651764 :   if (stmt_ends_bb_p (stmt)
     374     12443478 :       || gimple_has_volatile_ops (stmt)
     375     13595597 :       || gimple_has_side_effects (stmt)
     376     27241470 :       || stmt_could_throw_p (cfun, stmt))
     377              :     return MOVE_IMPOSSIBLE;
     378              : 
     379     13192485 :   if (is_gimple_call (stmt))
     380              :     {
     381              :       /* While pure or const call is guaranteed to have no side effects, we
     382              :          cannot move it arbitrarily.  Consider code like
     383              : 
     384              :          char *s = something ();
     385              : 
     386              :          while (1)
     387              :            {
     388              :              if (s)
     389              :                t = strlen (s);
     390              :              else
     391              :                t = 0;
     392              :            }
     393              : 
     394              :          Here the strlen call cannot be moved out of the loop, even though
     395              :          s is invariant.  In addition to possibly creating a call with
     396              :          invalid arguments, moving out a function call that is not executed
     397              :          may cause performance regressions in case the call is costly and
     398              :          not executed at all.  */
     399       126228 :       ret = MOVE_PRESERVE_EXECUTION;
     400       126228 :       lhs = gimple_call_lhs (stmt);
     401              :     }
     402     13066257 :   else if (is_gimple_assign (stmt))
     403     11885710 :     lhs = gimple_assign_lhs (stmt);
     404              :   else
     405              :     return MOVE_IMPOSSIBLE;
     406              : 
     407     12011938 :   if (TREE_CODE (lhs) == SSA_NAME
     408     12011938 :       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
     409              :     return MOVE_IMPOSSIBLE;
     410              : 
     411     12011725 :   if (TREE_CODE (lhs) != SSA_NAME
     412     12011725 :       || gimple_could_trap_p (stmt))
     413              :     return MOVE_PRESERVE_EXECUTION;
     414              : 
     415      9564365 :   if (is_gimple_assign (stmt))
     416              :     {
     417      9446336 :       auto code = gimple_assign_rhs_code (stmt);
     418      9446336 :       tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
     419              :       /* A shift or rotate by a possibly out-of-bound count moves only where
     420              :          rewrite_to_defined_unconditional can reduce the count, and not at
     421              :          all when optimizing for size.  */
     422      9446336 :       if ((code == LSHIFT_EXPR
     423              :            || code == RSHIFT_EXPR
     424              :            || code == LROTATE_EXPR
     425      9446336 :            || code == RROTATE_EXPR)
     426       171078 :           && (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST
     427              :               /* We cannot use ranges at 'stmt' here.  */
     428       127902 :               || wi::geu_p (wi::to_wide (gimple_assign_rhs2 (stmt)),
     429      9574238 :                             element_precision (type)))
     430      9489513 :           && (!gimple_needing_rewrite_undefined (stmt, true)
     431        42048 :               || optimize_loop_for_size_p (loop_containing_stmt (stmt))))
     432              :         ret = MOVE_PRESERVE_EXECUTION;
     433              :     }
     434              : 
     435              :   /* Non local loads in a transaction cannot be hoisted out.  Well,
     436              :      unless the load happens on every path out of the loop, but we
     437              :      don't take this into account yet.  */
     438      9564365 :   if (flag_tm
     439          434 :       && gimple_in_transaction (stmt)
     440      9564468 :       && gimple_assign_single_p (stmt))
     441              :     {
     442           21 :       tree rhs = gimple_assign_rhs1 (stmt);
     443           21 :       if (DECL_P (rhs) && is_global_var (rhs))
     444              :         {
     445           18 :           if (dump_file)
     446              :             {
     447            2 :               fprintf (dump_file, "Cannot hoist conditional load of ");
     448            2 :               print_generic_expr (dump_file, rhs, TDF_SLIM);
     449            2 :               fprintf (dump_file, " because it is in a transaction.\n");
     450              :             }
     451              :           return MOVE_IMPOSSIBLE;
     452              :         }
     453              :     }
     454              : 
     455              :   return ret;
     456              : }
     457              : 
     458              : static enum move_pos
     459     49677931 : movement_possibility (gimple *stmt)
     460              : {
     461     49677931 :   enum move_pos pos = movement_possibility_1 (stmt);
     462     49677931 :   if (pos == MOVE_POSSIBLE)
     463              :     {
     464     11306030 :       use_operand_p use_p;
     465     11306030 :       ssa_op_iter ssa_iter;
     466     36668140 :       FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, ssa_iter, SSA_OP_USE)
     467     14076077 :         if (TREE_CODE (USE_FROM_PTR (use_p)) == SSA_NAME
     468     14076077 :             && ssa_name_maybe_undef_p (USE_FROM_PTR (use_p)))
     469        19997 :           return MOVE_PRESERVE_EXECUTION;
     470              :     }
     471              :   return pos;
     472              : }
     473              : 
     474              : 
     475              : /* Compare the profile count inequality of bb and loop's preheader, it is
     476              :    three-state as stated in profile-count.h, FALSE is returned if inequality
     477              :    cannot be decided.  */
     478              : bool
     479     14466794 : bb_colder_than_loop_preheader (basic_block bb, class loop *loop)
     480              : {
     481     14466794 :   gcc_assert (bb && loop);
     482     14466794 :   return bb->count < loop_preheader_edge (loop)->src->count;
     483              : }
     484              : 
     485              : /* Check coldest loop between OUTERMOST_LOOP and LOOP by comparing profile
     486              :    count.
     487              :   It does three steps check:
     488              :   1) Check whether CURR_BB is cold in it's own loop_father, if it is cold, just
     489              :   return NULL which means it should not be moved out at all;
     490              :   2) CURR_BB is NOT cold, check if pre-computed COLDEST_LOOP is outside of
     491              :   OUTERMOST_LOOP, if it is inside of OUTERMOST_LOOP, return the COLDEST_LOOP;
     492              :   3) If COLDEST_LOOP is outside of OUTERMOST_LOOP, check whether there is a
     493              :   hotter loop between OUTERMOST_LOOP and loop in pre-computed
     494              :   HOTTER_THAN_INNER_LOOP, return it's nested inner loop, otherwise return
     495              :   OUTERMOST_LOOP.
     496              :   At last, the coldest_loop is inside of OUTERMOST_LOOP, just return it as
     497              :   the hoist target.  */
     498              : 
     499              : static class loop *
     500     12794129 : get_coldest_out_loop (class loop *outermost_loop, class loop *loop,
     501              :                       basic_block curr_bb)
     502              : {
     503     12794129 :   gcc_assert (outermost_loop == loop
     504              :               || flow_loop_nested_p (outermost_loop, loop));
     505              : 
     506              :   /* If bb_colder_than_loop_preheader returns false due to three-state
     507              :     comparison, OUTERMOST_LOOP is returned finally to preserve the behavior.
     508              :     Otherwise, return the coldest loop between OUTERMOST_LOOP and LOOP.  */
     509     12794129 :   if (curr_bb && bb_colder_than_loop_preheader (curr_bb, loop))
     510              :     return NULL;
     511              : 
     512     11749521 :   class loop *coldest_loop = coldest_outermost_loop[loop->num];
     513     23499042 :   if (loop_depth (coldest_loop) < loop_depth (outermost_loop))
     514              :     {
     515       237567 :       class loop *hotter_loop = hotter_than_inner_loop[loop->num];
     516       237567 :       if (!hotter_loop
     517       244122 :           || loop_depth (hotter_loop) < loop_depth (outermost_loop))
     518              :         return outermost_loop;
     519              : 
     520              :       /*  hotter_loop is between OUTERMOST_LOOP and LOOP like:
     521              :         [loop tree root, ..., coldest_loop, ..., outermost_loop, ...,
     522              :         hotter_loop, second_coldest_loop, ..., loop]
     523              :         return second_coldest_loop to be the hoist target.  */
     524           38 :       class loop *aloop;
     525           38 :       for (aloop = hotter_loop->inner; aloop; aloop = aloop->next)
     526           38 :         if (aloop == loop || flow_loop_nested_p (aloop, loop))
     527              :           return aloop;
     528              :     }
     529              :   return coldest_loop;
     530              : }
     531              : 
     532              : /* Suppose that operand DEF is used inside the LOOP.  Returns the outermost
     533              :    loop to that we could move the expression using DEF if it did not have
     534              :    other operands, i.e. the outermost loop enclosing LOOP in that the value
     535              :    of DEF is invariant.  */
     536              : 
     537              : static class loop *
     538     20328064 : outermost_invariant_loop (tree def, class loop *loop)
     539              : {
     540     20328064 :   gimple *def_stmt;
     541     20328064 :   basic_block def_bb;
     542     20328064 :   class loop *max_loop;
     543     20328064 :   struct lim_aux_data *lim_data;
     544              : 
     545     20328064 :   if (!def)
     546       957203 :     return superloop_at_depth (loop, 1);
     547              : 
     548     19370861 :   if (TREE_CODE (def) != SSA_NAME)
     549              :     {
     550      4039851 :       gcc_assert (is_gimple_min_invariant (def));
     551      4039851 :       return superloop_at_depth (loop, 1);
     552              :     }
     553              : 
     554     15331010 :   def_stmt = SSA_NAME_DEF_STMT (def);
     555     15331010 :   def_bb = gimple_bb (def_stmt);
     556     15331010 :   if (!def_bb)
     557        76517 :     return superloop_at_depth (loop, 1);
     558              : 
     559     15254493 :   max_loop = find_common_loop (loop, def_bb->loop_father);
     560              : 
     561     15254493 :   lim_data = get_lim_data (def_stmt);
     562     15254493 :   if (lim_data != NULL && lim_data->max_loop != NULL)
     563       730136 :     max_loop = find_common_loop (max_loop,
     564              :                                  loop_outer (lim_data->max_loop));
     565     15254493 :   if (max_loop == loop)
     566              :     return NULL;
     567      1925995 :   max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
     568              : 
     569      1925995 :   return max_loop;
     570              : }
     571              : 
     572              : /* DATA is a structure containing information associated with a statement
     573              :    inside LOOP.  DEF is one of the operands of this statement.
     574              : 
     575              :    Find the outermost loop enclosing LOOP in that value of DEF is invariant
     576              :    and record this in DATA->max_loop field.  If DEF itself is defined inside
     577              :    this loop as well (i.e. we need to hoist it out of the loop if we want
     578              :    to hoist the statement represented by DATA), record the statement in that
     579              :    DEF is defined to the DATA->depends list.  Additionally if ADD_COST is true,
     580              :    add the cost of the computation of DEF to the DATA->cost.
     581              : 
     582              :    If DEF is not invariant in LOOP, return false.  Otherwise return TRUE.  */
     583              : 
     584              : static bool
     585     11956374 : add_dependency (tree def, struct lim_aux_data *data, class loop *loop,
     586              :                 bool add_cost)
     587              : {
     588     11956374 :   gimple *def_stmt = SSA_NAME_DEF_STMT (def);
     589     11956374 :   basic_block def_bb = gimple_bb (def_stmt);
     590     11956374 :   class loop *max_loop;
     591     11956374 :   struct lim_aux_data *def_data;
     592              : 
     593     11956374 :   if (!def_bb)
     594              :     return true;
     595              : 
     596     11586357 :   max_loop = outermost_invariant_loop (def, loop);
     597     11586357 :   if (!max_loop)
     598              :     return false;
     599              : 
     600      1451179 :   if (flow_loop_nested_p (data->max_loop, max_loop))
     601       433641 :     data->max_loop = max_loop;
     602              : 
     603      1451179 :   def_data = get_lim_data (def_stmt);
     604      1451179 :   if (!def_data)
     605              :     return true;
     606              : 
     607       722094 :   if (add_cost
     608              :       /* Only add the cost if the statement defining DEF is inside LOOP,
     609              :          i.e. if it is likely that by moving the invariants dependent
     610              :          on it, we will be able to avoid creating a new register for
     611              :          it (since it will be only used in these dependent invariants).  */
     612       696957 :       && def_bb->loop_father == loop)
     613       494388 :     data->cost += def_data->cost;
     614              : 
     615       722094 :   data->depends.safe_push (def_stmt);
     616              : 
     617       722094 :   return true;
     618              : }
     619              : 
     620              : /* Returns an estimate for a cost of statement STMT.  The values here
     621              :    are just ad-hoc constants, similar to costs for inlining.  */
     622              : 
     623              : static unsigned
     624       827514 : stmt_cost (gimple *stmt)
     625              : {
     626              :   /* Always try to create possibilities for unswitching.  */
     627       827514 :   if (gimple_code (stmt) == GIMPLE_COND
     628       827514 :       || gimple_code (stmt) == GIMPLE_PHI)
     629        17235 :     return LIM_EXPENSIVE;
     630              : 
     631              :   /* We should be hoisting calls if possible.  */
     632       810279 :   if (is_gimple_call (stmt))
     633              :     {
     634          897 :       tree fndecl;
     635              : 
     636              :       /* Unless the call is a builtin_constant_p; this always folds to a
     637              :          constant, so moving it is useless.  */
     638          897 :       fndecl = gimple_call_fndecl (stmt);
     639          897 :       if (fndecl && fndecl_built_in_p (fndecl, BUILT_IN_CONSTANT_P))
     640              :         return 0;
     641              : 
     642          897 :       return LIM_EXPENSIVE;
     643              :     }
     644              : 
     645              :   /* Hoisting memory references out should almost surely be a win.  */
     646       809382 :   if (gimple_references_memory_p (stmt))
     647        69424 :     return LIM_EXPENSIVE;
     648              : 
     649       739958 :   if (gimple_code (stmt) != GIMPLE_ASSIGN)
     650              :     return 1;
     651              : 
     652       739958 :   enum tree_code code = gimple_assign_rhs_code (stmt);
     653       739958 :   switch (code)
     654              :     {
     655       121618 :     case MULT_EXPR:
     656       121618 :     case WIDEN_MULT_EXPR:
     657       121618 :     case WIDEN_MULT_PLUS_EXPR:
     658       121618 :     case WIDEN_MULT_MINUS_EXPR:
     659       121618 :     case DOT_PROD_EXPR:
     660       121618 :     case TRUNC_DIV_EXPR:
     661       121618 :     case CEIL_DIV_EXPR:
     662       121618 :     case FLOOR_DIV_EXPR:
     663       121618 :     case ROUND_DIV_EXPR:
     664       121618 :     case EXACT_DIV_EXPR:
     665       121618 :     case CEIL_MOD_EXPR:
     666       121618 :     case FLOOR_MOD_EXPR:
     667       121618 :     case ROUND_MOD_EXPR:
     668       121618 :     case TRUNC_MOD_EXPR:
     669       121618 :     case RDIV_EXPR:
     670              :       /* Division and multiplication are usually expensive.  */
     671       121618 :       return LIM_EXPENSIVE;
     672              : 
     673         9048 :     case LSHIFT_EXPR:
     674         9048 :     case RSHIFT_EXPR:
     675         9048 :     case WIDEN_LSHIFT_EXPR:
     676         9048 :     case LROTATE_EXPR:
     677         9048 :     case RROTATE_EXPR:
     678              :       /* Shifts and rotates are usually expensive.  */
     679         9048 :       return LIM_EXPENSIVE;
     680              : 
     681          497 :     case COND_EXPR:
     682          497 :     case VEC_COND_EXPR:
     683              :       /* Conditionals are expensive.  */
     684          497 :       return LIM_EXPENSIVE;
     685              : 
     686         1479 :     case CONSTRUCTOR:
     687              :       /* Make vector construction cost proportional to the number
     688              :          of elements.  */
     689         1479 :       return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
     690              : 
     691              :     case SSA_NAME:
     692              :     case PAREN_EXPR:
     693              :       /* Whether or not something is wrapped inside a PAREN_EXPR
     694              :          should not change move cost.  Nor should an intermediate
     695              :          unpropagated SSA name copy.  */
     696              :       return 0;
     697              : 
     698       570326 :     default:
     699              :       /* Comparisons are usually expensive.  */
     700       570326 :       if (TREE_CODE_CLASS (code) == tcc_comparison)
     701         8822 :         return LIM_EXPENSIVE;
     702              :       return 1;
     703              :     }
     704              : }
     705              : 
     706              : /* Finds the outermost loop between OUTER and LOOP in that the memory reference
     707              :    REF is independent.  If REF is not independent in LOOP, NULL is returned
     708              :    instead.  */
     709              : 
     710              : static class loop *
     711       798730 : outermost_indep_loop (class loop *outer, class loop *loop, im_mem_ref *ref)
     712              : {
     713       798730 :   class loop *aloop;
     714              : 
     715       798730 :   if (ref->stored && bitmap_bit_p (ref->stored, loop->num))
     716              :     return NULL;
     717              : 
     718        88018 :   for (aloop = outer;
     719       721428 :        aloop != loop;
     720        88018 :        aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
     721        10329 :     if ((!ref->stored || !bitmap_bit_p (ref->stored, aloop->num))
     722       104992 :         && ref_indep_loop_p (aloop, ref, lim_raw))
     723              :       return aloop;
     724              : 
     725       618272 :   if (ref_indep_loop_p (loop, ref, lim_raw))
     726              :     return loop;
     727              :   else
     728       563986 :     return NULL;
     729              : }
     730              : 
     731              : /* If there is a simple load or store to a memory reference in STMT, returns
     732              :    the location of the memory reference, and sets IS_STORE according to whether
     733              :    it is a store or load.  Otherwise, returns NULL.  */
     734              : 
     735              : static tree *
     736      7310716 : simple_mem_ref_in_stmt (gimple *stmt, bool *is_store)
     737              : {
     738      7310716 :   tree *lhs, *rhs;
     739              : 
     740              :   /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns.  */
     741      7310716 :   if (!gimple_assign_single_p (stmt))
     742              :     return NULL;
     743              : 
     744      6019370 :   lhs = gimple_assign_lhs_ptr (stmt);
     745      6019370 :   rhs = gimple_assign_rhs1_ptr (stmt);
     746              : 
     747      9314052 :   if (TREE_CODE (*lhs) == SSA_NAME && gimple_vuse (stmt))
     748              :     {
     749      3294682 :       *is_store = false;
     750      3294682 :       return rhs;
     751              :     }
     752      2724688 :   else if (gimple_vdef (stmt)
     753      2724688 :            && (TREE_CODE (*rhs) == SSA_NAME || is_gimple_min_invariant (*rhs)))
     754              :     {
     755      2253996 :       *is_store = true;
     756      2253996 :       return lhs;
     757              :     }
     758              :   else
     759              :     return NULL;
     760              : }
     761              : 
     762              : /* From a controlling predicate in DOM determine the arguments from
     763              :    the PHI node PHI that are chosen if the predicate evaluates to
     764              :    true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
     765              :    they are non-NULL.  Returns true if the arguments can be determined,
     766              :    else return false.  */
     767              : 
     768              : static bool
     769        13910 : extract_true_false_args_from_phi (basic_block dom, gphi *phi,
     770              :                                   tree *true_arg_p, tree *false_arg_p)
     771              : {
     772        13910 :   edge te, fe;
     773        13910 :   if (! extract_true_false_controlled_edges (dom, gimple_bb (phi),
     774              :                                              &te, &fe))
     775              :     return false;
     776              : 
     777        13007 :   if (true_arg_p)
     778         1415 :     *true_arg_p = PHI_ARG_DEF (phi, te->dest_idx);
     779        13007 :   if (false_arg_p)
     780         1415 :     *false_arg_p = PHI_ARG_DEF (phi, fe->dest_idx);
     781              : 
     782              :   return true;
     783              : }
     784              : 
     785              : /* Return true if STMT is a shift or rotate whose count would have to be
     786              :    masked when moved out of LOOP, because STMT is not always executed
     787              :    when LOOP is entered.  An out-of-range constant count folds instead.  */
     788              : 
     789              : static bool
     790       226146 : shift_needs_mask_p (gimple *stmt, class loop *loop)
     791              : {
     792       226146 :   if (!gimple_needing_rewrite_undefined (stmt, true))
     793              :     return false;
     794        25547 :   enum tree_code code = gimple_assign_rhs_code (stmt);
     795        25547 :   if ((code != LSHIFT_EXPR
     796              :        && code != RSHIFT_EXPR
     797              :        && code != LROTATE_EXPR
     798        25547 :        && code != RROTATE_EXPR)
     799        25547 :       || TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST)
     800              :     return false;
     801          767 :   class loop *always = get_lim_data (stmt)->always_executed_in;
     802          767 :   return !always || !(always == loop || flow_loop_nested_p (always, loop));
     803              : }
     804              : 
     805              : /* Determine the outermost loop to that it is possible to hoist a statement
     806              :    STMT and store it to LIM_DATA (STMT)->max_loop.  To do this we determine
     807              :    the outermost loop in that the value computed by STMT is invariant.
     808              :    If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
     809              :    we preserve the fact whether STMT is executed.  It also fills other related
     810              :    information to LIM_DATA (STMT).
     811              : 
     812              :    The function returns false if STMT cannot be hoisted outside of the loop it
     813              :    is defined in, and true otherwise.  */
     814              : 
     815              : static bool
     816     12750403 : determine_max_movement (gimple *stmt, bool must_preserve_exec)
     817              : {
     818     12750403 :   basic_block bb = gimple_bb (stmt);
     819     12750403 :   class loop *loop = bb->loop_father;
     820     12750403 :   class loop *level;
     821     12750403 :   struct lim_aux_data *lim_data = get_lim_data (stmt);
     822     12750403 :   tree val;
     823     12750403 :   ssa_op_iter iter;
     824              : 
     825     12750403 :   if (must_preserve_exec)
     826      1458363 :     level = ALWAYS_EXECUTED_IN (bb);
     827              :   else
     828     11292040 :     level = superloop_at_depth (loop, 1);
     829     12750403 :   lim_data->max_loop = get_coldest_out_loop (level, loop, bb);
     830     12750403 :   if (!lim_data->max_loop)
     831              :     return false;
     832              : 
     833     11707536 :   if (gphi *phi = dyn_cast <gphi *> (stmt))
     834              :     {
     835      1426364 :       use_operand_p use_p;
     836      1426364 :       unsigned min_cost = UINT_MAX;
     837      1426364 :       unsigned total_cost = 0;
     838      1426364 :       struct lim_aux_data *def_data;
     839              : 
     840              :       /* We will end up promoting dependencies to be unconditionally
     841              :          evaluated.  For this reason the PHI cost (and thus the
     842              :          cost we remove from the loop by doing the invariant motion)
     843              :          is that of the cheapest PHI argument dependency chain.  */
     844      1641052 :       FOR_EACH_PHI_ARG (use_p, phi, iter, SSA_OP_USE)
     845              :         {
     846      1615010 :           val = USE_FROM_PTR (use_p);
     847              : 
     848      1615010 :           if (TREE_CODE (val) != SSA_NAME)
     849              :             {
     850              :               /* Assign const 1 to constants.  */
     851       132268 :               min_cost = MIN (min_cost, 1);
     852       132268 :               total_cost += 1;
     853       132268 :               continue;
     854              :             }
     855      1482742 :           if (!add_dependency (val, lim_data, loop, false))
     856              :             return false;
     857              : 
     858        82420 :           gimple *def_stmt = SSA_NAME_DEF_STMT (val);
     859        82420 :           if (gimple_bb (def_stmt)
     860        82420 :               && gimple_bb (def_stmt)->loop_father == loop)
     861              :             {
     862         3013 :               def_data = get_lim_data (def_stmt);
     863         3013 :               if (def_data)
     864              :                 {
     865         3013 :                   min_cost = MIN (min_cost, def_data->cost);
     866         3013 :                   total_cost += def_data->cost;
     867              :                 }
     868              :             }
     869              :         }
     870              : 
     871        26042 :       min_cost = MIN (min_cost, total_cost);
     872        26042 :       lim_data->cost += min_cost;
     873              : 
     874        26042 :       if (gimple_phi_num_args (phi) > 1)
     875              :         {
     876        25805 :           basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
     877        25805 :           gimple *cond;
     878        51610 :           if (gsi_end_p (gsi_last_bb (dom)))
     879              :             return false;
     880        17655 :           cond = gsi_stmt (gsi_last_bb (dom));
     881        17655 :           if (gimple_code (cond) != GIMPLE_COND)
     882              :             return false;
     883              :           /* Verify that this is an extended form of a diamond and
     884              :              the PHI arguments are completely controlled by the
     885              :              predicate in DOM.  */
     886        12495 :           if (!extract_true_false_args_from_phi (dom, phi, NULL, NULL))
     887              :             return false;
     888              : 
     889              :         /* Check if one of the dependent statement is a vector compare whether
     890              :            the target supports it,  otherwise it's invalid to hoist it out of
     891              :            the gcond it belonged to.  */
     892        11592 :         if (VECTOR_TYPE_P (TREE_TYPE (gimple_cond_lhs (cond))))
     893              :           {
     894            5 :             tree type = TREE_TYPE (gimple_cond_lhs (cond));
     895            5 :             auto code = gimple_cond_code (cond);
     896            5 :             if (!target_supports_op_p (type, code, optab_vector))
     897              :               return false;
     898              :           }
     899              : 
     900              :           /* Fold in dependencies and cost of the condition.  */
     901        14875 :           FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE)
     902              :             {
     903        12379 :               if (!add_dependency (val, lim_data, loop, false))
     904              :                 return false;
     905         3288 :               def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
     906         3288 :               if (def_data)
     907         1937 :                 lim_data->cost += def_data->cost;
     908              :             }
     909              : 
     910              :           /* We want to avoid unconditionally executing very expensive
     911              :              operations.  As costs for our dependencies cannot be
     912              :              negative just claim we are not invariand for this case.
     913              :              We also are not sure whether the control-flow inside the
     914              :              loop will vanish.  */
     915         2496 :           if (total_cost - min_cost >= 2 * LIM_EXPENSIVE
     916         1127 :               && !(min_cost != 0
     917         1127 :                    && total_cost / min_cost <= 2))
     918              :             return false;
     919              : 
     920              :           /* Assume that the control-flow in the loop will vanish.
     921              :              ???  We should verify this and not artificially increase
     922              :              the cost if that is not the case.  */
     923         1415 :           lim_data->cost += stmt_cost (stmt);
     924              :         }
     925              : 
     926              :       return true;
     927              :     }
     928              : 
     929              :   /* A stmt that receives abnormal edges cannot be hoisted.  */
     930     10281172 :   if (is_a <gcall *> (stmt)
     931     10281172 :       && (gimple_call_flags (stmt) & ECF_RETURNS_TWICE))
     932              :     return false;
     933              : 
     934     12016633 :   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
     935     10460156 :     if (!add_dependency (val, lim_data, loop, true))
     936              :       return false;
     937              : 
     938      3097134 :   if (gimple_vuse (stmt))
     939              :     {
     940       799827 :       im_mem_ref *ref
     941       799827 :         = lim_data ? memory_accesses.refs_list[lim_data->ref] : NULL;
     942       799827 :       if (ref
     943       799827 :           && MEM_ANALYZABLE (ref))
     944              :         {
     945       798730 :           lim_data->max_loop = outermost_indep_loop (lim_data->max_loop,
     946              :                                                      loop, ref);
     947       798730 :           if (!lim_data->max_loop)
     948              :             return false;
     949              :         }
     950         1097 :       else if (! add_dependency (gimple_vuse (stmt), lim_data, loop, false))
     951              :         return false;
     952              :     }
     953              : 
     954              :   /* A shift that needs its count masked is not worth moving on its own.  */
     955       826099 :   unsigned cost = stmt_cost (stmt);
     956       826099 :   if (cost >= LIM_EXPENSIVE && shift_needs_mask_p (stmt, lim_data->max_loop))
     957              :     cost = 1;
     958       826099 :   lim_data->cost += cost;
     959              : 
     960       826099 :   return true;
     961              : }
     962              : 
     963              : /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
     964              :    and that one of the operands of this statement is computed by STMT.
     965              :    Ensure that STMT (together with all the statements that define its
     966              :    operands) is hoisted at least out of the loop LEVEL.  */
     967              : 
     968              : static void
     969       759680 : set_level (gimple *stmt, class loop *orig_loop, class loop *level)
     970              : {
     971       759680 :   class loop *stmt_loop = gimple_bb (stmt)->loop_father;
     972       759680 :   struct lim_aux_data *lim_data;
     973       759680 :   gimple *dep_stmt;
     974       759680 :   unsigned i;
     975              : 
     976       759680 :   stmt_loop = find_common_loop (orig_loop, stmt_loop);
     977       759680 :   lim_data = get_lim_data (stmt);
     978       759680 :   if (lim_data != NULL && lim_data->tgt_loop != NULL)
     979       196985 :     stmt_loop = find_common_loop (stmt_loop,
     980              :                                   loop_outer (lim_data->tgt_loop));
     981       759680 :   if (flow_loop_nested_p (stmt_loop, level))
     982       759680 :     return;
     983              : 
     984       500130 :   gcc_assert (level == lim_data->max_loop
     985              :               || flow_loop_nested_p (lim_data->max_loop, level));
     986              : 
     987       500130 :   lim_data->tgt_loop = level;
     988       869357 :   FOR_EACH_VEC_ELT (lim_data->depends, i, dep_stmt)
     989       369227 :     set_level (dep_stmt, orig_loop, level);
     990              : }
     991              : 
     992              : /* Determines an outermost loop from that we want to hoist the statement STMT.
     993              :    For now we chose the outermost possible loop.  TODO -- use profiling
     994              :    information to set it more sanely.  */
     995              : 
     996              : static void
     997       326808 : set_profitable_level (gimple *stmt)
     998              : {
     999       326808 :   set_level (stmt, gimple_bb (stmt)->loop_father, get_lim_data (stmt)->max_loop);
    1000       326808 : }
    1001              : 
    1002              : /* Returns true if STMT is a call that has side effects.  */
    1003              : 
    1004              : static bool
    1005     76663879 : nonpure_call_p (gimple *stmt)
    1006              : {
    1007            0 :   if (gimple_code (stmt) != GIMPLE_CALL)
    1008              :     return false;
    1009              : 
    1010      2328650 :   return gimple_has_side_effects (stmt);
    1011              : }
    1012              : 
    1013              : /* Rewrite a/b to a*(1/b).  Return the invariant stmt to process.  */
    1014              : 
    1015              : static gimple *
    1016           35 : rewrite_reciprocal (gimple_stmt_iterator *bsi)
    1017              : {
    1018           35 :   gassign *stmt, *stmt1, *stmt2;
    1019           35 :   tree name, lhs, type;
    1020           35 :   tree real_one;
    1021           35 :   gimple_stmt_iterator gsi;
    1022              : 
    1023           35 :   stmt = as_a <gassign *> (gsi_stmt (*bsi));
    1024           35 :   lhs = gimple_assign_lhs (stmt);
    1025           35 :   type = TREE_TYPE (lhs);
    1026              : 
    1027           35 :   real_one = build_one_cst (type);
    1028              : 
    1029           35 :   name = make_temp_ssa_name (type, NULL, "reciptmp");
    1030           70 :   stmt1 = gimple_build_assign (name, RDIV_EXPR, real_one,
    1031              :                                gimple_assign_rhs2 (stmt));
    1032           35 :   stmt2 = gimple_build_assign (lhs, MULT_EXPR, name,
    1033              :                                gimple_assign_rhs1 (stmt));
    1034              : 
    1035              :   /* Replace division stmt with reciprocal and multiply stmts.
    1036              :      The multiply stmt is not invariant, so update iterator
    1037              :      and avoid rescanning.  */
    1038           35 :   gsi = *bsi;
    1039           35 :   gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
    1040           35 :   gsi_replace (&gsi, stmt2, true);
    1041              : 
    1042              :   /* Continue processing with invariant reciprocal statement.  */
    1043           35 :   return stmt1;
    1044              : }
    1045              : 
    1046              : /* Check if the pattern at *BSI is a bittest of the form
    1047              :    (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0.  */
    1048              : 
    1049              : static gimple *
    1050         9883 : rewrite_bittest (gimple_stmt_iterator *bsi)
    1051              : {
    1052         9883 :   gassign *stmt;
    1053         9883 :   gimple *stmt1;
    1054         9883 :   gassign *stmt2;
    1055         9883 :   gimple *use_stmt;
    1056         9883 :   gcond *cond_stmt;
    1057         9883 :   tree lhs, name, t, a, b;
    1058         9883 :   use_operand_p use;
    1059              : 
    1060         9883 :   stmt = as_a <gassign *> (gsi_stmt (*bsi));
    1061         9883 :   lhs = gimple_assign_lhs (stmt);
    1062              : 
    1063              :   /* Verify that the single use of lhs is a comparison against zero.  */
    1064         9883 :   if (TREE_CODE (lhs) != SSA_NAME
    1065         9883 :       || !single_imm_use (lhs, &use, &use_stmt))
    1066              :     return stmt;
    1067         9419 :   cond_stmt = dyn_cast <gcond *> (use_stmt);
    1068         5501 :   if (!cond_stmt)
    1069              :     return stmt;
    1070         5501 :   if (gimple_cond_lhs (cond_stmt) != lhs
    1071         5323 :       || (gimple_cond_code (cond_stmt) != NE_EXPR
    1072         2230 :           && gimple_cond_code (cond_stmt) != EQ_EXPR)
    1073        10824 :       || !integer_zerop (gimple_cond_rhs (cond_stmt)))
    1074              :     return stmt;
    1075              : 
    1076              :   /* Get at the operands of the shift.  The rhs is TMP1 & 1.  */
    1077         5285 :   stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
    1078         5285 :   if (gimple_code (stmt1) != GIMPLE_ASSIGN)
    1079              :     return stmt;
    1080              : 
    1081              :   /* There is a conversion in between possibly inserted by fold.  */
    1082         5189 :   if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1)))
    1083              :     {
    1084          223 :       t = gimple_assign_rhs1 (stmt1);
    1085          223 :       if (TREE_CODE (t) != SSA_NAME
    1086          223 :           || !has_single_use (t))
    1087              :         return stmt;
    1088          153 :       stmt1 = SSA_NAME_DEF_STMT (t);
    1089          153 :       if (gimple_code (stmt1) != GIMPLE_ASSIGN)
    1090              :         return stmt;
    1091              :     }
    1092              : 
    1093              :   /* Verify that B is loop invariant but A is not.  Verify that with
    1094              :      all the stmt walking we are still in the same loop.  */
    1095         5077 :   if (gimple_assign_rhs_code (stmt1) != RSHIFT_EXPR
    1096        11541 :       || loop_containing_stmt (stmt1) != loop_containing_stmt (stmt))
    1097              :     return stmt;
    1098              : 
    1099         3232 :   a = gimple_assign_rhs1 (stmt1);
    1100         3232 :   b = gimple_assign_rhs2 (stmt1);
    1101              : 
    1102         3232 :   if (outermost_invariant_loop (b, loop_containing_stmt (stmt1)) != NULL
    1103         3261 :       && outermost_invariant_loop (a, loop_containing_stmt (stmt1)) == NULL)
    1104              :     {
    1105           29 :       gimple_stmt_iterator rsi;
    1106              : 
    1107              :       /* 1 << B */
    1108           29 :       t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
    1109              :                        build_int_cst (TREE_TYPE (a), 1), b);
    1110           29 :       name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
    1111           29 :       stmt1 = gimple_build_assign (name, t);
    1112              : 
    1113              :       /* A & (1 << B) */
    1114           29 :       t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
    1115           29 :       name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
    1116           29 :       stmt2 = gimple_build_assign (name, t);
    1117              : 
    1118              :       /* Replace the SSA_NAME we compare against zero.  Adjust
    1119              :          the type of zero accordingly.  */
    1120           29 :       SET_USE (use, name);
    1121           29 :       gimple_cond_set_rhs (cond_stmt,
    1122           29 :                            build_int_cst_type (TREE_TYPE (name),
    1123              :                                                0));
    1124              : 
    1125              :       /* Don't use gsi_replace here, none of the new assignments sets
    1126              :          the variable originally set in stmt.  Move bsi to stmt1, and
    1127              :          then remove the original stmt, so that we get a chance to
    1128              :          retain debug info for it.  */
    1129           29 :       rsi = *bsi;
    1130           29 :       gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
    1131           29 :       gsi_insert_before (&rsi, stmt2, GSI_SAME_STMT);
    1132           29 :       gimple *to_release = gsi_stmt (rsi);
    1133           29 :       gsi_remove (&rsi, true);
    1134           29 :       release_defs (to_release);
    1135              : 
    1136           29 :       return stmt1;
    1137              :     }
    1138              : 
    1139              :   return stmt;
    1140              : }
    1141              : 
    1142              : /* Determine the outermost loops in that statements in basic block BB are
    1143              :    invariant, and record them to the LIM_DATA associated with the
    1144              :    statements.  */
    1145              : 
    1146              : static void
    1147     14784151 : compute_invariantness (basic_block bb)
    1148              : {
    1149     14784151 :   enum move_pos pos;
    1150     14784151 :   gimple_stmt_iterator bsi;
    1151     14784151 :   gimple *stmt;
    1152     14784151 :   bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
    1153     14784151 :   class loop *outermost = ALWAYS_EXECUTED_IN (bb);
    1154     14784151 :   struct lim_aux_data *lim_data;
    1155              : 
    1156     14784151 :   if (!loop_outer (bb->loop_father))
    1157      8550324 :     return;
    1158              : 
    1159      6233827 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1160          585 :     fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
    1161          585 :              bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
    1162              : 
    1163              :   /* Look at PHI nodes, but only if there is at most two.
    1164              :      ???  We could relax this further by post-processing the inserted
    1165              :      code and transforming adjacent cond-exprs with the same predicate
    1166              :      to control flow again.  */
    1167      6233827 :   bsi = gsi_start_phis (bb);
    1168      6233827 :   if (!gsi_end_p (bsi)
    1169      6233827 :       && ((gsi_next (&bsi), gsi_end_p (bsi))
    1170      1413485 :           || (gsi_next (&bsi), gsi_end_p (bsi))))
    1171      4419806 :     for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
    1172              :       {
    1173      2664000 :         stmt = gsi_stmt (bsi);
    1174              : 
    1175      2664000 :         pos = movement_possibility (stmt);
    1176      2664000 :         if (pos == MOVE_IMPOSSIBLE)
    1177      1180547 :           continue;
    1178              : 
    1179      1483453 :         lim_data = get_lim_data (stmt);
    1180      1483453 :         if (! lim_data)
    1181      1483453 :           lim_data = init_lim_data (stmt);
    1182      1483453 :         lim_data->always_executed_in = outermost;
    1183              : 
    1184      1483453 :         if (!determine_max_movement (stmt, false))
    1185              :           {
    1186      1481801 :             lim_data->max_loop = NULL;
    1187      1481801 :             continue;
    1188              :           }
    1189              : 
    1190         1652 :         if (dump_file && (dump_flags & TDF_DETAILS))
    1191              :           {
    1192            2 :             print_gimple_stmt (dump_file, stmt, 2);
    1193            2 :             fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
    1194            2 :                      loop_depth (lim_data->max_loop),
    1195              :                      lim_data->cost);
    1196              :           }
    1197              : 
    1198         1652 :         if (lim_data->cost >= LIM_EXPENSIVE)
    1199         1427 :           set_profitable_level (stmt);
    1200              :       }
    1201              : 
    1202     59481585 :   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
    1203              :     {
    1204     47013931 :       stmt = gsi_stmt (bsi);
    1205              : 
    1206     47013931 :       pos = movement_possibility (stmt);
    1207     47013931 :       if (pos == MOVE_IMPOSSIBLE)
    1208              :         {
    1209     35845036 :           if (nonpure_call_p (stmt))
    1210              :             {
    1211              :               maybe_never = true;
    1212              :               outermost = NULL;
    1213              :             }
    1214              :           /* Make sure to note always_executed_in for stores to make
    1215              :              store-motion work.  */
    1216     33408281 :           else if (stmt_makes_single_store (stmt))
    1217              :             {
    1218      2597110 :               struct lim_aux_data *lim_data = get_lim_data (stmt);
    1219      2597110 :               if (! lim_data)
    1220            0 :                 lim_data = init_lim_data (stmt);
    1221      2597110 :               lim_data->always_executed_in = outermost;
    1222              :             }
    1223     34623957 :           continue;
    1224     34623957 :         }
    1225              : 
    1226     12389974 :       if (is_gimple_assign (stmt)
    1227     12389974 :           && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
    1228              :               == GIMPLE_BINARY_RHS))
    1229              :         {
    1230      5970125 :           tree op0 = gimple_assign_rhs1 (stmt);
    1231      5970125 :           tree op1 = gimple_assign_rhs2 (stmt);
    1232     11940250 :           class loop *ol1 = outermost_invariant_loop (op1,
    1233              :                                         loop_containing_stmt (stmt));
    1234              : 
    1235              :           /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
    1236              :              to be hoisted out of loop, saving expensive divide.  */
    1237      5970125 :           if (pos == MOVE_POSSIBLE
    1238      5533014 :               && gimple_assign_rhs_code (stmt) == RDIV_EXPR
    1239          983 :               && flag_unsafe_math_optimizations
    1240          423 :               && !flag_trapping_math
    1241          423 :               && ol1 != NULL
    1242      5970163 :               && outermost_invariant_loop (op0, ol1) == NULL)
    1243           35 :             stmt = rewrite_reciprocal (&bsi);
    1244              : 
    1245              :           /* If the shift count is invariant, convert (A >> B) & 1 to
    1246              :              A & (1 << B) allowing the bit mask to be hoisted out of the loop
    1247              :              saving an expensive shift.  */
    1248      5970125 :           if (pos == MOVE_POSSIBLE
    1249      5533014 :               && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
    1250       199005 :               && integer_onep (op1)
    1251        20144 :               && TREE_CODE (op0) == SSA_NAME
    1252      5990269 :               && has_single_use (op0))
    1253         9883 :             stmt = rewrite_bittest (&bsi);
    1254              :         }
    1255              : 
    1256     12389974 :       lim_data = get_lim_data (stmt);
    1257     12389974 :       if (! lim_data)
    1258      9463144 :         lim_data = init_lim_data (stmt);
    1259     12389974 :       lim_data->always_executed_in = outermost;
    1260              : 
    1261     12389974 :       if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
    1262      1123024 :         continue;
    1263              : 
    1264     11266950 :       if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
    1265              :         {
    1266     10440851 :           lim_data->max_loop = NULL;
    1267     10440851 :           continue;
    1268              :         }
    1269              : 
    1270       826099 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1271              :         {
    1272          318 :           print_gimple_stmt (dump_file, stmt, 2);
    1273          318 :           fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
    1274          318 :                    loop_depth (lim_data->max_loop),
    1275              :                    lim_data->cost);
    1276              :         }
    1277              : 
    1278       826099 :       if (lim_data->cost >= LIM_EXPENSIVE)
    1279       325381 :         set_profitable_level (stmt);
    1280              :       /* When we run before PRE and PRE is active hoist all expressions
    1281              :          to the always executed loop since PRE would do so anyway
    1282              :          and we can preserve range info while PRE cannot.  */
    1283       500718 :       else if (flag_tree_pre && !in_loop_pipeline
    1284       105394 :                && outermost)
    1285              :         {
    1286        60690 :           class loop *mloop = lim_data->max_loop;
    1287       182070 :           if (loop_depth (outermost) > loop_depth (mloop))
    1288              :             {
    1289         8532 :               mloop = outermost;
    1290         8532 :               if (dump_file && (dump_flags & TDF_DETAILS))
    1291            1 :                 fprintf (dump_file, "  constraining to loop depth %d\n\n\n",
    1292              :                          loop_depth (mloop));
    1293              :             }
    1294        60690 :           set_level (stmt, bb->loop_father, mloop);
    1295              :         }
    1296              :     }
    1297              : }
    1298              : 
    1299              : /* Hoist the statements in basic block BB out of the loops prescribed by
    1300              :    data stored in LIM_DATA structures associated with each statement.  Callback
    1301              :    for walk_dominator_tree.  */
    1302              : 
    1303              : unsigned int
    1304     14824630 : move_computations_worker (basic_block bb)
    1305              : {
    1306     14824630 :   class loop *level;
    1307     14824630 :   unsigned cost = 0;
    1308     14824630 :   struct lim_aux_data *lim_data;
    1309     14824630 :   unsigned int todo = 0;
    1310              : 
    1311     14824630 :   if (!loop_outer (bb->loop_father))
    1312              :     return todo;
    1313              : 
    1314     10916295 :   for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi); )
    1315              :     {
    1316      4676256 :       gassign *new_stmt;
    1317      4676256 :       gphi *stmt = bsi.phi ();
    1318              : 
    1319      4676256 :       lim_data = get_lim_data (stmt);
    1320      4676256 :       if (lim_data == NULL)
    1321              :         {
    1322      3192803 :           gsi_next (&bsi);
    1323      3192803 :           continue;
    1324              :         }
    1325              : 
    1326      1483453 :       cost = lim_data->cost;
    1327      1483453 :       level = lim_data->tgt_loop;
    1328      1483453 :       clear_lim_data (stmt);
    1329              : 
    1330      1483453 :       if (!level)
    1331              :         {
    1332      1482016 :           gsi_next (&bsi);
    1333      1482016 :           continue;
    1334              :         }
    1335              : 
    1336         1437 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1337              :         {
    1338            2 :           fprintf (dump_file, "Moving PHI node\n");
    1339            2 :           print_gimple_stmt (dump_file, stmt, 0);
    1340            2 :           fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
    1341              :                    cost, level->num);
    1342              :         }
    1343              : 
    1344         1437 :       if (gimple_phi_num_args (stmt) == 1)
    1345              :         {
    1346           22 :           tree arg = PHI_ARG_DEF (stmt, 0);
    1347           22 :           new_stmt = gimple_build_assign (gimple_phi_result (stmt),
    1348           22 :                                           TREE_CODE (arg), arg);
    1349              :         }
    1350              :       else
    1351              :         {
    1352         1415 :           basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
    1353         1415 :           gimple *cond = gsi_stmt (gsi_last_bb (dom));
    1354         1415 :           tree arg0 = NULL_TREE, arg1 = NULL_TREE, t;
    1355              :           /* Get the PHI arguments corresponding to the true and false
    1356              :              edges of COND.  */
    1357         1415 :           extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1);
    1358         1415 :           gcc_assert (arg0 && arg1);
    1359              :           /* For `bool_val != 0`, reuse bool_val. */
    1360         1415 :           if (gimple_cond_code (cond) == NE_EXPR
    1361          649 :               && integer_zerop (gimple_cond_rhs (cond))
    1362         1989 :               && types_compatible_p (TREE_TYPE (gimple_cond_lhs (cond)),
    1363              :                                      boolean_type_node))
    1364              :             {
    1365           72 :               t = gimple_cond_lhs (cond);
    1366              :             }
    1367              :           else
    1368              :             {
    1369         1343 :               t = make_ssa_name (boolean_type_node);
    1370         1343 :               new_stmt = gimple_build_assign (t, gimple_cond_code (cond),
    1371              :                                               gimple_cond_lhs (cond),
    1372              :                                               gimple_cond_rhs (cond));
    1373         1343 :               gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
    1374              :             }
    1375         1415 :           new_stmt = gimple_build_assign (gimple_phi_result (stmt),
    1376              :                                           COND_EXPR, t, arg0, arg1);
    1377         1415 :           todo |= TODO_cleanup_cfg;
    1378              :         }
    1379         1437 :       if (!ALWAYS_EXECUTED_IN (bb)
    1380         1437 :           || (ALWAYS_EXECUTED_IN (bb) != level
    1381          100 :               && !flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level)))
    1382          871 :         reset_flow_sensitive_info (gimple_assign_lhs (new_stmt));
    1383         1437 :       gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
    1384         1437 :       remove_phi_node (&bsi, false);
    1385              :     }
    1386              : 
    1387     59558107 :   for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
    1388              :     {
    1389     47078029 :       edge e;
    1390              : 
    1391     47078029 :       gimple *stmt = gsi_stmt (bsi);
    1392              : 
    1393     47078029 :       lim_data = get_lim_data (stmt);
    1394     47078029 :       if (lim_data == NULL)
    1395              :         {
    1396     30262096 :           gsi_next (&bsi);
    1397     30262096 :           continue;
    1398              :         }
    1399              : 
    1400     16815933 :       cost = lim_data->cost;
    1401     16815933 :       level = lim_data->tgt_loop;
    1402     16815933 :       clear_lim_data (stmt);
    1403              : 
    1404     16815933 :       if (!level)
    1405              :         {
    1406     16278089 :           gsi_next (&bsi);
    1407     16278089 :           continue;
    1408              :         }
    1409              : 
    1410              :       /* We do not really want to move conditionals out of the loop; we just
    1411              :          placed it here to force its operands to be moved if necessary.  */
    1412       537844 :       if (gimple_code (stmt) == GIMPLE_COND)
    1413              :         {
    1414        15820 :           gsi_next (&bsi);
    1415        15820 :           continue;
    1416              :         }
    1417              : 
    1418       522024 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1419              :         {
    1420          387 :           fprintf (dump_file, "Moving statement ");
    1421          387 :           print_gimple_stmt (dump_file, stmt, 0);
    1422          387 :           fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
    1423              :                    cost, level->num);
    1424              :         }
    1425              : 
    1426       522024 :       e = loop_preheader_edge (level);
    1427      1044048 :       gcc_assert (!gimple_vdef (stmt));
    1428      1044048 :       if (gimple_vuse (stmt))
    1429              :         {
    1430              :           /* The new VUSE is the one from the virtual PHI in the loop
    1431              :              header or the one already present.  */
    1432        87748 :           gphi_iterator gsi2;
    1433        87748 :           for (gsi2 = gsi_start_phis (e->dest);
    1434       206916 :                !gsi_end_p (gsi2); gsi_next (&gsi2))
    1435              :             {
    1436       187881 :               gphi *phi = gsi2.phi ();
    1437       375762 :               if (virtual_operand_p (gimple_phi_result (phi)))
    1438              :                 {
    1439        68713 :                   SET_USE (gimple_vuse_op (stmt),
    1440              :                            PHI_ARG_DEF_FROM_EDGE (phi, e));
    1441        68713 :                   break;
    1442              :                 }
    1443              :             }
    1444              :         }
    1445       522024 :       gsi_remove (&bsi, false);
    1446       522024 :       if (gimple_has_lhs (stmt)
    1447       522024 :           && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME
    1448       480663 :           && (!ALWAYS_EXECUTED_IN (bb)
    1449       389964 :               || !(ALWAYS_EXECUTED_IN (bb) == level
    1450        96779 :                    || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
    1451       228279 :         reset_flow_sensitive_info (gimple_get_lhs (stmt));
    1452              :       /* In case this is a stmt that is not unconditionally executed
    1453              :          when the target loop header is executed and the stmt may
    1454              :          invoke undefined integer or pointer overflow rewrite it to
    1455              :          unsigned arithmetic.  */
    1456       522024 :       if (gimple_needing_rewrite_undefined (stmt, true)
    1457       522024 :           && (!ALWAYS_EXECUTED_IN (bb)
    1458        73963 :               || !(ALWAYS_EXECUTED_IN (bb) == level
    1459        19136 :                    || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
    1460        20235 :         gsi_insert_seq_on_edge (e, rewrite_to_defined_unconditional (stmt));
    1461              :       else
    1462       501789 :         gsi_insert_on_edge (e, stmt);
    1463              :     }
    1464              : 
    1465      6240039 :   return todo;
    1466              : }
    1467              : 
    1468              : /* Checks whether the statement defining variable *INDEX can be hoisted
    1469              :    out of the loop passed in DATA.  Callback for for_each_index.  */
    1470              : 
    1471              : static bool
    1472      1808229 : may_move_till (tree ref, tree *index, void *data)
    1473              : {
    1474      1808229 :   class loop *loop = (class loop *) data, *max_loop;
    1475              : 
    1476              :   /* If REF is an array reference, check also that the step and the lower
    1477              :      bound is invariant in LOOP.  */
    1478      1808229 :   if (TREE_CODE (ref) == ARRAY_REF)
    1479              :     {
    1480       480027 :       tree step = TREE_OPERAND (ref, 3);
    1481       480027 :       tree lbound = TREE_OPERAND (ref, 2);
    1482              : 
    1483       480027 :       max_loop = outermost_invariant_loop (step, loop);
    1484       480027 :       if (!max_loop)
    1485              :         return false;
    1486              : 
    1487       480027 :       max_loop = outermost_invariant_loop (lbound, loop);
    1488       480027 :       if (!max_loop)
    1489              :         return false;
    1490              :     }
    1491              : 
    1492      1808229 :   max_loop = outermost_invariant_loop (*index, loop);
    1493      1808229 :   if (!max_loop)
    1494      1161003 :     return false;
    1495              : 
    1496              :   return true;
    1497              : }
    1498              : 
    1499              : /* If OP is SSA NAME, force the statement that defines it to be
    1500              :    moved out of the LOOP.  ORIG_LOOP is the loop in that EXPR is used.  */
    1501              : 
    1502              : static void
    1503        37279 : force_move_till_op (tree op, class loop *orig_loop, class loop *loop)
    1504              : {
    1505        37279 :   gimple *stmt;
    1506              : 
    1507        37279 :   if (!op
    1508        37279 :       || is_gimple_min_invariant (op))
    1509              :     return;
    1510              : 
    1511         4552 :   gcc_assert (TREE_CODE (op) == SSA_NAME);
    1512              : 
    1513         4552 :   stmt = SSA_NAME_DEF_STMT (op);
    1514         4552 :   if (gimple_nop_p (stmt))
    1515              :     return;
    1516              : 
    1517         2955 :   set_level (stmt, orig_loop, loop);
    1518              : }
    1519              : 
    1520              : /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
    1521              :    the LOOP.  The reference REF is used in the loop ORIG_LOOP.  Callback for
    1522              :    for_each_index.  */
    1523              : 
    1524              : struct fmt_data
    1525              : {
    1526              :   class loop *loop;
    1527              :   class loop *orig_loop;
    1528              : };
    1529              : 
    1530              : static bool
    1531        19293 : force_move_till (tree ref, tree *index, void *data)
    1532              : {
    1533        19293 :   struct fmt_data *fmt_data = (struct fmt_data *) data;
    1534              : 
    1535        19293 :   if (TREE_CODE (ref) == ARRAY_REF)
    1536              :     {
    1537         8993 :       tree step = TREE_OPERAND (ref, 3);
    1538         8993 :       tree lbound = TREE_OPERAND (ref, 2);
    1539              : 
    1540         8993 :       force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop);
    1541         8993 :       force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop);
    1542              :     }
    1543              : 
    1544        19293 :   force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);
    1545              : 
    1546        19293 :   return true;
    1547              : }
    1548              : 
    1549              : /* A function to free the mem_ref object OBJ.  */
    1550              : 
    1551              : static void
    1552      5525146 : memref_free (class im_mem_ref *mem)
    1553              : {
    1554            0 :   mem->accesses_in_loop.release ();
    1555            0 : }
    1556              : 
    1557              : /* Allocates and returns a memory reference description for MEM whose hash
    1558              :    value is HASH and id is ID.  */
    1559              : 
    1560              : static im_mem_ref *
    1561      5525146 : mem_ref_alloc (ao_ref *mem, unsigned hash, unsigned id)
    1562              : {
    1563      5525146 :   im_mem_ref *ref = XOBNEW (&mem_ref_obstack, class im_mem_ref);
    1564      5525146 :   if (mem)
    1565      4554632 :     ref->mem = *mem;
    1566              :   else
    1567       970514 :     ao_ref_init (&ref->mem, error_mark_node);
    1568      5525146 :   ref->id = id;
    1569      5525146 :   ref->ref_canonical = false;
    1570      5525146 :   ref->ref_decomposed = false;
    1571      5525146 :   ref->hash = hash;
    1572      5525146 :   ref->stored = NULL;
    1573      5525146 :   ref->loaded = NULL;
    1574      5525146 :   bitmap_initialize (&ref->dep_loop, &lim_bitmap_obstack);
    1575      5525146 :   ref->accesses_in_loop.create (1);
    1576              : 
    1577      5525146 :   return ref;
    1578              : }
    1579              : 
    1580              : /* Records memory reference location *LOC in LOOP to the memory reference
    1581              :    description REF.  The reference occurs in statement STMT.  */
    1582              : 
    1583              : static void
    1584      6019370 : record_mem_ref_loc (im_mem_ref *ref, gimple *stmt, tree *loc)
    1585              : {
    1586      6019370 :   mem_ref_loc aref;
    1587      6019370 :   aref.stmt = stmt;
    1588      6019370 :   aref.ref = loc;
    1589            0 :   ref->accesses_in_loop.safe_push (aref);
    1590            0 : }
    1591              : 
    1592              : /* Set the LOOP bit in REF stored bitmap and allocate that if
    1593              :    necessary.  Return whether a bit was changed.  */
    1594              : 
    1595              : static bool
    1596      4699371 : set_ref_stored_in_loop (im_mem_ref *ref, class loop *loop)
    1597              : {
    1598      4699371 :   if (!ref->stored)
    1599      2711794 :     ref->stored = BITMAP_ALLOC (&lim_bitmap_obstack);
    1600      4699371 :   return bitmap_set_bit (ref->stored, loop->num);
    1601              : }
    1602              : 
    1603              : /* Marks reference REF as stored in LOOP.  */
    1604              : 
    1605              : static void
    1606      3935737 : mark_ref_stored (im_mem_ref *ref, class loop *loop)
    1607              : {
    1608      3935737 :   while (loop != current_loops->tree_root
    1609      7583724 :          && set_ref_stored_in_loop (ref, loop))
    1610      3647987 :     loop = loop_outer (loop);
    1611      3935737 : }
    1612              : 
    1613              : /* Set the LOOP bit in REF loaded bitmap and allocate that if
    1614              :    necessary.  Return whether a bit was changed.  */
    1615              : 
    1616              : static bool
    1617      6366302 : set_ref_loaded_in_loop (im_mem_ref *ref, class loop *loop)
    1618              : {
    1619      6366302 :   if (!ref->loaded)
    1620      3470038 :     ref->loaded = BITMAP_ALLOC (&lim_bitmap_obstack);
    1621      6366302 :   return bitmap_set_bit (ref->loaded, loop->num);
    1622              : }
    1623              : 
    1624              : /* Marks reference REF as loaded in LOOP.  */
    1625              : 
    1626              : static void
    1627      5056720 : mark_ref_loaded (im_mem_ref *ref, class loop *loop)
    1628              : {
    1629      5056720 :   while (loop != current_loops->tree_root
    1630     10063146 :          && set_ref_loaded_in_loop (ref, loop))
    1631      5006426 :     loop = loop_outer (loop);
    1632      5056720 : }
    1633              : 
    1634              : /* Gathers memory references in statement STMT in LOOP, storing the
    1635              :    information about them in the memory_accesses structure.  Marks
    1636              :    the vops accessed through unrecognized statements there as
    1637              :    well.  */
    1638              : 
    1639              : static void
    1640     47013867 : gather_mem_refs_stmt (class loop *loop, gimple *stmt)
    1641              : {
    1642     47013867 :   tree *mem = NULL;
    1643     47013867 :   hashval_t hash;
    1644     47013867 :   im_mem_ref **slot;
    1645     47013867 :   im_mem_ref *ref;
    1646     47013867 :   bool is_stored;
    1647     47013867 :   unsigned id;
    1648              : 
    1649     63432998 :   if (!gimple_vuse (stmt))
    1650              :     return;
    1651              : 
    1652      7310716 :   mem = simple_mem_ref_in_stmt (stmt, &is_stored);
    1653      7310716 :   if (!mem && is_gimple_assign (stmt))
    1654              :     {
    1655              :       /* For aggregate copies record distinct references but use them
    1656              :          only for disambiguation purposes.  */
    1657       470692 :       id = memory_accesses.refs_list.length ();
    1658       470692 :       ref = mem_ref_alloc (NULL, 0, id);
    1659       470692 :       memory_accesses.refs_list.safe_push (ref);
    1660       470692 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1661              :         {
    1662           30 :           fprintf (dump_file, "Unhandled memory reference %u: ", id);
    1663           30 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1664              :         }
    1665       470692 :       record_mem_ref_loc (ref, stmt, mem);
    1666       941384 :       is_stored = gimple_vdef (stmt);
    1667              :     }
    1668      6840024 :   else if (!mem)
    1669              :     {
    1670              :       /* We use the shared mem_ref for all unanalyzable refs.  */
    1671      1291346 :       id = UNANALYZABLE_MEM_ID;
    1672      1291346 :       ref = memory_accesses.refs_list[id];
    1673      1291346 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1674              :         {
    1675           21 :           fprintf (dump_file, "Unanalyzed memory reference %u: ", id);
    1676           21 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1677              :         }
    1678      2582692 :       is_stored = gimple_vdef (stmt);
    1679              :     }
    1680              :   else
    1681              :     {
    1682              :       /* We are looking for equal refs that might differ in structure
    1683              :          such as a.b vs. MEM[&a + 4].  So we key off the ao_ref but
    1684              :          make sure we can canonicalize the ref in the hashtable if
    1685              :          non-operand_equal_p refs are found.  For the lookup we mark
    1686              :          the case we want strict equality with aor.max_size == -1.  */
    1687      5548678 :       ao_ref aor;
    1688      5548678 :       ao_ref_init (&aor, *mem);
    1689      5548678 :       ao_ref_base (&aor);
    1690      5548678 :       ao_ref_alias_set (&aor);
    1691      5548678 :       HOST_WIDE_INT offset, size, max_size;
    1692      5548678 :       poly_int64 saved_maxsize = aor.max_size, mem_off;
    1693      5548678 :       tree mem_base;
    1694      5548678 :       bool ref_decomposed;
    1695      5548678 :       if (aor.max_size_known_p ()
    1696      5363413 :           && aor.offset.is_constant (&offset)
    1697      5363413 :           && aor.size.is_constant (&size)
    1698      5363413 :           && aor.max_size.is_constant (&max_size)
    1699      5363413 :           && size == max_size
    1700      4761422 :           && (size % BITS_PER_UNIT) == 0
    1701              :           /* We're canonicalizing to a MEM where TYPE_SIZE specifies the
    1702              :              size.  Make sure this is consistent with the extraction.  */
    1703      4749777 :           && poly_int_tree_p (TYPE_SIZE (TREE_TYPE (*mem)))
    1704      4749777 :           && known_eq (wi::to_poly_offset (TYPE_SIZE (TREE_TYPE (*mem))),
    1705              :                        aor.size)
    1706     10298363 :           && (mem_base = get_addr_base_and_unit_offset (aor.ref, &mem_off)))
    1707              :         {
    1708      4748551 :           ref_decomposed = true;
    1709      4748551 :           tree base = ao_ref_base (&aor);
    1710      4748551 :           poly_int64 moffset;
    1711      4748551 :           HOST_WIDE_INT mcoffset;
    1712      4748551 :           if (TREE_CODE (base) == MEM_REF
    1713      4748551 :               && (mem_ref_offset (base) * BITS_PER_UNIT + offset).to_shwi (&moffset)
    1714      4748551 :               && moffset.is_constant (&mcoffset))
    1715              :             {
    1716      2121392 :               hash = iterative_hash_expr (TREE_OPERAND (base, 0), 0);
    1717      2121392 :               hash = iterative_hash_host_wide_int (mcoffset, hash);
    1718              :             }
    1719              :           else
    1720              :             {
    1721      2627159 :               hash = iterative_hash_expr (base, 0);
    1722      2627159 :               hash = iterative_hash_host_wide_int (offset, hash);
    1723              :             }
    1724      4748551 :           hash = iterative_hash_host_wide_int (size, hash);
    1725              :         }
    1726              :       else
    1727              :         {
    1728       800127 :           ref_decomposed = false;
    1729       800127 :           hash = iterative_hash_expr (aor.ref, 0);
    1730       800127 :           aor.max_size = -1;
    1731              :         }
    1732      5548678 :       slot = memory_accesses.refs->find_slot_with_hash (&aor, hash, INSERT);
    1733      5548678 :       aor.max_size = saved_maxsize;
    1734      5548678 :       if (*slot)
    1735              :         {
    1736       994046 :           if (!(*slot)->ref_canonical
    1737       994046 :               && !operand_equal_p (*mem, (*slot)->mem.ref, 0))
    1738              :             {
    1739              :               /* If we didn't yet canonicalize the hashtable ref (which
    1740              :                  we'll end up using for code insertion) and hit a second
    1741              :                  equal ref that is not structurally equivalent create
    1742              :                  a canonical ref which is a bare MEM_REF.  */
    1743        57007 :               if (TREE_CODE (*mem) == MEM_REF
    1744        57007 :                   || TREE_CODE (*mem) == TARGET_MEM_REF)
    1745        16063 :                 (*slot)->mem = aor;
    1746              :               else
    1747              :                 {
    1748        40944 :                   tree ref_alias_type = reference_alias_ptr_type (*mem);
    1749        40944 :                   unsigned int ref_align = get_object_alignment (*mem);
    1750        40944 :                   tree ref_type = TREE_TYPE (*mem);
    1751        40944 :                   tree tmp = build1 (ADDR_EXPR, ptr_type_node,
    1752              :                                      unshare_expr (mem_base));
    1753        40944 :                   if (TYPE_ALIGN (ref_type) != ref_align)
    1754        11425 :                     ref_type = build_aligned_type (ref_type, ref_align);
    1755        40944 :                   tree new_ref
    1756        40944 :                     = fold_build2 (MEM_REF, ref_type, tmp,
    1757              :                                    build_int_cst (ref_alias_type, mem_off));
    1758        40944 :                   if ((*slot)->mem.volatile_p)
    1759           14 :                     TREE_THIS_VOLATILE (new_ref) = 1;
    1760        40944 :                   if (reverse_storage_order_for_component_p (*mem))
    1761            7 :                     REF_REVERSE_STORAGE_ORDER (new_ref) = 1;
    1762        40944 :                   (*slot)->mem.ref = new_ref;
    1763              :                   /* Make sure the recorded base and offset are consistent
    1764              :                      with the newly built ref.  */
    1765        40944 :                   if (TREE_CODE (TREE_OPERAND (new_ref, 0)) == ADDR_EXPR)
    1766              :                     ;
    1767              :                   else
    1768              :                     {
    1769        22409 :                       (*slot)->mem.base = new_ref;
    1770        22409 :                       (*slot)->mem.offset = 0;
    1771              :                     }
    1772        40944 :                   gcc_checking_assert (TREE_CODE ((*slot)->mem.ref) == MEM_REF
    1773              :                                        && is_gimple_mem_ref_addr
    1774              :                                             (TREE_OPERAND ((*slot)->mem.ref,
    1775              :                                                            0)));
    1776        40944 :                   (*slot)->mem.base_alias_set = (*slot)->mem.ref_alias_set;
    1777              :                 }
    1778        57007 :               (*slot)->ref_canonical = true;
    1779              :             }
    1780       994046 :           ref = *slot;
    1781       994046 :           id = ref->id;
    1782              :         }
    1783              :       else
    1784              :         {
    1785      4554632 :           id = memory_accesses.refs_list.length ();
    1786      4554632 :           ref = mem_ref_alloc (&aor, hash, id);
    1787      4554632 :           ref->ref_decomposed = ref_decomposed;
    1788      4554632 :           memory_accesses.refs_list.safe_push (ref);
    1789      4554632 :           *slot = ref;
    1790              : 
    1791      4554632 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1792              :             {
    1793          550 :               fprintf (dump_file, "Memory reference %u: ", id);
    1794          550 :               print_generic_expr (dump_file, ref->mem.ref, TDF_SLIM);
    1795          550 :               fprintf (dump_file, "\n");
    1796              :             }
    1797              :         }
    1798              : 
    1799      5548678 :       record_mem_ref_loc (ref, stmt, mem);
    1800              :     }
    1801      7310716 :   if (is_stored)
    1802              :     {
    1803      3935737 :       bitmap_set_bit (&memory_accesses.refs_stored_in_loop[loop->num], ref->id);
    1804      3935737 :       mark_ref_stored (ref, loop);
    1805              :     }
    1806              :   /* A not simple memory op is also a read when it is a write.  */
    1807      7310716 :   if (!is_stored || id == UNANALYZABLE_MEM_ID
    1808      2724688 :       || ref->mem.ref == error_mark_node)
    1809              :     {
    1810      5056720 :       bitmap_set_bit (&memory_accesses.refs_loaded_in_loop[loop->num], ref->id);
    1811      5056720 :       mark_ref_loaded (ref, loop);
    1812              :     }
    1813      7310716 :   init_lim_data (stmt)->ref = ref->id;
    1814      7310716 :   return;
    1815              : }
    1816              : 
    1817              : static unsigned *bb_loop_postorder;
    1818              : 
    1819              : /* qsort sort function to sort blocks after their loop fathers postorder.  */
    1820              : 
    1821              : static int
    1822    162530173 : sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_,
    1823              :                                 void *bb_loop_postorder_)
    1824              : {
    1825    162530173 :   unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
    1826    162530173 :   basic_block bb1 = *(const basic_block *)bb1_;
    1827    162530173 :   basic_block bb2 = *(const basic_block *)bb2_;
    1828    162530173 :   class loop *loop1 = bb1->loop_father;
    1829    162530173 :   class loop *loop2 = bb2->loop_father;
    1830    162530173 :   if (loop1->num == loop2->num)
    1831     76698911 :     return bb1->index - bb2->index;
    1832     85831262 :   return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
    1833              : }
    1834              : 
    1835              : /* qsort sort function to sort ref locs after their loop fathers postorder.  */
    1836              : 
    1837              : static int
    1838       994031 : sort_locs_in_loop_postorder_cmp (const void *loc1_, const void *loc2_,
    1839              :                                  void *bb_loop_postorder_)
    1840              : {
    1841       994031 :   unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
    1842       994031 :   const mem_ref_loc *loc1 = (const mem_ref_loc *)loc1_;
    1843       994031 :   const mem_ref_loc *loc2 = (const mem_ref_loc *)loc2_;
    1844       994031 :   class loop *loop1 = gimple_bb (loc1->stmt)->loop_father;
    1845       994031 :   class loop *loop2 = gimple_bb (loc2->stmt)->loop_father;
    1846       994031 :   if (loop1->num == loop2->num)
    1847              :     return 0;
    1848       149190 :   return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
    1849              : }
    1850              : 
    1851              : /* Gathers memory references in loops.  */
    1852              : 
    1853              : static void
    1854       499822 : analyze_memory_references (bool store_motion)
    1855              : {
    1856       499822 :   gimple_stmt_iterator bsi;
    1857       499822 :   basic_block bb, *bbs;
    1858       499822 :   class loop *outer;
    1859       499822 :   unsigned i, n;
    1860              : 
    1861              :   /* Collect all basic-blocks in loops and sort them after their
    1862              :      loops postorder.  */
    1863       499822 :   i = 0;
    1864       499822 :   bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
    1865     15283973 :   FOR_EACH_BB_FN (bb, cfun)
    1866     14784151 :     if (bb->loop_father != current_loops->tree_root)
    1867      6233827 :       bbs[i++] = bb;
    1868       499822 :   n = i;
    1869       499822 :   gcc_sort_r (bbs, n, sizeof (basic_block), sort_bbs_in_loop_postorder_cmp,
    1870              :               bb_loop_postorder);
    1871              : 
    1872              :   /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
    1873              :      That results in better locality for all the bitmaps.  It also
    1874              :      automatically sorts the location list of gathered memory references
    1875              :      after their loop postorder number allowing to binary-search it.  */
    1876      7233471 :   for (i = 0; i < n; ++i)
    1877              :     {
    1878      6233827 :       basic_block bb = bbs[i];
    1879     59481521 :       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
    1880     47013867 :         gather_mem_refs_stmt (bb->loop_father, gsi_stmt (bsi));
    1881              :     }
    1882              : 
    1883              :   /* Verify the list of gathered memory references is sorted after their
    1884              :      loop postorder number.  */
    1885       499822 :   if (flag_checking)
    1886              :     {
    1887              :       im_mem_ref *ref;
    1888     11550036 :       FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
    1889      6519145 :         for (unsigned j = 1; j < ref->accesses_in_loop.length (); ++j)
    1890       994031 :           gcc_assert (sort_locs_in_loop_postorder_cmp
    1891              :                         (&ref->accesses_in_loop[j-1], &ref->accesses_in_loop[j],
    1892              :                          bb_loop_postorder) <= 0);
    1893              :     }
    1894              : 
    1895       499822 :   free (bbs);
    1896              : 
    1897       499822 :   if (!store_motion)
    1898       499822 :     return;
    1899              : 
    1900              :   /* Propagate the information about accessed memory references up
    1901              :      the loop hierarchy.  */
    1902      2844272 :   for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
    1903              :     {
    1904              :       /* Finalize the overall touched references (including subloops).  */
    1905      1349405 :       bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[loop->num],
    1906      1349405 :                        &memory_accesses.refs_stored_in_loop[loop->num]);
    1907              : 
    1908              :       /* Propagate the information about accessed memory references up
    1909              :          the loop hierarchy.  */
    1910      1349405 :       outer = loop_outer (loop);
    1911      1349405 :       if (outer == current_loops->tree_root)
    1912      1040974 :         continue;
    1913              : 
    1914       308431 :       bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[outer->num],
    1915       308431 :                        &memory_accesses.all_refs_stored_in_loop[loop->num]);
    1916       498289 :     }
    1917              : }
    1918              : 
    1919              : /* Returns true if MEM1 and MEM2 may alias.  TTAE_CACHE is used as a cache in
    1920              :    tree_to_aff_combination_expand.  */
    1921              : 
    1922              : static bool
    1923       564022 : mem_refs_may_alias_p (im_mem_ref *mem1, im_mem_ref *mem2,
    1924              :                       hash_map<tree, name_expansion *> **ttae_cache,
    1925              :                       bool tbaa_p)
    1926              : {
    1927       564022 :   gcc_checking_assert (mem1->mem.ref != error_mark_node
    1928              :                        && mem2->mem.ref != error_mark_node);
    1929              : 
    1930              :   /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
    1931              :      object and their offset differ in such a way that the locations cannot
    1932              :      overlap, then they cannot alias.  */
    1933       564022 :   poly_widest_int size1, size2;
    1934      1128044 :   aff_tree off1, off2;
    1935              : 
    1936              :   /* Perform basic offset and type-based disambiguation.  */
    1937       564022 :   if (!refs_may_alias_p_1 (&mem1->mem, &mem2->mem, tbaa_p))
    1938              :     return false;
    1939              : 
    1940              :   /* The expansion of addresses may be a bit expensive, thus we only do
    1941              :      the check at -O2 and higher optimization levels.  */
    1942        69281 :   if (optimize < 2)
    1943              :     return true;
    1944              : 
    1945        59104 :   get_inner_reference_aff (mem1->mem.ref, &off1, &size1);
    1946        59104 :   get_inner_reference_aff (mem2->mem.ref, &off2, &size2);
    1947        59104 :   aff_combination_expand (&off1, ttae_cache);
    1948        59104 :   aff_combination_expand (&off2, ttae_cache);
    1949        59104 :   aff_combination_scale (&off1, -1);
    1950        59104 :   aff_combination_add (&off2, &off1);
    1951              : 
    1952        59104 :   if (aff_comb_cannot_overlap_p (&off2, size1, size2))
    1953         2407 :     return false;
    1954              : 
    1955              :   return true;
    1956       564022 : }
    1957              : 
    1958              : /* Compare function for bsearch searching for reference locations
    1959              :    in a loop.  */
    1960              : 
    1961              : static int
    1962       278114 : find_ref_loc_in_loop_cmp (const void *loop_, const void *loc_,
    1963              :                           void *bb_loop_postorder_)
    1964              : {
    1965       278114 :   unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
    1966       278114 :   class loop *loop = (class loop *)const_cast<void *>(loop_);
    1967       278114 :   mem_ref_loc *loc = (mem_ref_loc *)const_cast<void *>(loc_);
    1968       278114 :   class loop *loc_loop = gimple_bb (loc->stmt)->loop_father;
    1969       278114 :   if (loop->num  == loc_loop->num
    1970       278114 :       || flow_loop_nested_p (loop, loc_loop))
    1971              :     return 0;
    1972        64413 :   return (bb_loop_postorder[loop->num] < bb_loop_postorder[loc_loop->num]
    1973        64413 :           ? -1 : 1);
    1974              : }
    1975              : 
    1976              : /* Iterates over all locations of REF in LOOP and its subloops calling
    1977              :    fn.operator() with the location as argument.  When that operator
    1978              :    returns true the iteration is stopped and true is returned.
    1979              :    Otherwise false is returned.  */
    1980              : 
    1981              : template <typename FN>
    1982              : static bool
    1983       213701 : for_all_locs_in_loop (class loop *loop, im_mem_ref *ref, FN fn)
    1984              : {
    1985              :   unsigned i;
    1986              :   mem_ref_loc *loc;
    1987              : 
    1988              :   /* Search for the cluster of locs in the accesses_in_loop vector
    1989              :      which is sorted after postorder index of the loop father.  */
    1990       213701 :   loc = ref->accesses_in_loop.bsearch (loop, find_ref_loc_in_loop_cmp,
    1991              :                                        bb_loop_postorder);
    1992       213701 :   if (!loc)
    1993              :     return false;
    1994              : 
    1995              :   /* We have found one location inside loop or its sub-loops.  Iterate
    1996              :      both forward and backward to cover the whole cluster.  */
    1997       213701 :   i = loc - ref->accesses_in_loop.address ();
    1998       306017 :   while (i > 0)
    1999              :     {
    2000       153543 :       --i;
    2001       153543 :       mem_ref_loc *l = &ref->accesses_in_loop[i];
    2002       153543 :       if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
    2003              :         break;
    2004       127350 :       if (fn (l))
    2005              :         return true;
    2006              :     }
    2007       496065 :   for (i = loc - ref->accesses_in_loop.address ();
    2008       317398 :        i < ref->accesses_in_loop.length (); ++i)
    2009              :     {
    2010       236479 :       mem_ref_loc *l = &ref->accesses_in_loop[i];
    2011       236479 :       if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
    2012              :         break;
    2013       216258 :       if (fn (l))
    2014              :         return true;
    2015              :     }
    2016              : 
    2017              :   return false;
    2018              : }
    2019              : 
    2020              : /* Rewrites location LOC by TMP_VAR.  */
    2021              : 
    2022              : class rewrite_mem_ref_loc
    2023              : {
    2024              : public:
    2025        35357 :   rewrite_mem_ref_loc (tree tmp_var_) : tmp_var (tmp_var_) {}
    2026              :   bool operator () (mem_ref_loc *loc);
    2027              :   tree tmp_var;
    2028              : };
    2029              : 
    2030              : bool
    2031        56233 : rewrite_mem_ref_loc::operator () (mem_ref_loc *loc)
    2032              : {
    2033        56233 :   *loc->ref = tmp_var;
    2034        56233 :   update_stmt (loc->stmt);
    2035        56233 :   return false;
    2036              : }
    2037              : 
    2038              : /* Rewrites all references to REF in LOOP by variable TMP_VAR.  */
    2039              : 
    2040              : static void
    2041        35357 : rewrite_mem_refs (class loop *loop, im_mem_ref *ref, tree tmp_var)
    2042              : {
    2043            0 :   for_all_locs_in_loop (loop, ref, rewrite_mem_ref_loc (tmp_var));
    2044            0 : }
    2045              : 
    2046              : /* Stores the first reference location in LOCP.  */
    2047              : 
    2048              : class first_mem_ref_loc_1
    2049              : {
    2050              : public:
    2051        35357 :   first_mem_ref_loc_1 (mem_ref_loc **locp_) : locp (locp_) {}
    2052              :   bool operator () (mem_ref_loc *loc);
    2053              :   mem_ref_loc **locp;
    2054              : };
    2055              : 
    2056              : bool
    2057        35357 : first_mem_ref_loc_1::operator () (mem_ref_loc *loc)
    2058              : {
    2059        35357 :   *locp = loc;
    2060        35357 :   return true;
    2061              : }
    2062              : 
    2063              : /* Returns the first reference location to REF in LOOP.  */
    2064              : 
    2065              : static mem_ref_loc *
    2066        35357 : first_mem_ref_loc (class loop *loop, im_mem_ref *ref)
    2067              : {
    2068        35357 :   mem_ref_loc *locp = NULL;
    2069            0 :   for_all_locs_in_loop (loop, ref, first_mem_ref_loc_1 (&locp));
    2070        35357 :   return locp;
    2071              : }
    2072              : 
    2073              : /* Helper function for execute_sm.  Emit code to store TMP_VAR into
    2074              :    MEM along edge EX.
    2075              : 
    2076              :    The store is only done if MEM has changed.  We do this so no
    2077              :    changes to MEM occur on code paths that did not originally store
    2078              :    into it.
    2079              : 
    2080              :    The common case for execute_sm will transform:
    2081              : 
    2082              :      for (...) {
    2083              :        if (foo)
    2084              :          stuff;
    2085              :        else
    2086              :          MEM = TMP_VAR;
    2087              :      }
    2088              : 
    2089              :    into:
    2090              : 
    2091              :      lsm = MEM;
    2092              :      for (...) {
    2093              :        if (foo)
    2094              :          stuff;
    2095              :        else
    2096              :          lsm = TMP_VAR;
    2097              :      }
    2098              :      MEM = lsm;
    2099              : 
    2100              :   This function will generate:
    2101              : 
    2102              :      lsm = MEM;
    2103              : 
    2104              :      lsm_flag = false;
    2105              :      ...
    2106              :      for (...) {
    2107              :        if (foo)
    2108              :          stuff;
    2109              :        else {
    2110              :          lsm = TMP_VAR;
    2111              :          lsm_flag = true;
    2112              :        }
    2113              :      }
    2114              :      if (lsm_flag)      <--
    2115              :        MEM = lsm;       <-- (X)
    2116              : 
    2117              :   In case MEM and TMP_VAR are NULL the function will return the then
    2118              :   block so the caller can insert (X) and other related stmts.
    2119              : */
    2120              : 
    2121              : static basic_block
    2122        12075 : execute_sm_if_changed (edge ex, tree mem, tree tmp_var, tree flag,
    2123              :                        edge preheader, hash_set <basic_block> *flag_bbs,
    2124              :                        edge &append_cond_position, edge &last_cond_fallthru)
    2125              : {
    2126        12075 :   basic_block new_bb, then_bb, old_dest;
    2127        12075 :   bool loop_has_only_one_exit;
    2128        12075 :   edge then_old_edge;
    2129        12075 :   gimple_stmt_iterator gsi;
    2130        12075 :   gimple *stmt;
    2131        12075 :   bool irr = ex->flags & EDGE_IRREDUCIBLE_LOOP;
    2132              : 
    2133        12075 :   profile_count count_sum = profile_count::zero ();
    2134        12075 :   int nbbs = 0, ncount = 0;
    2135        12075 :   profile_probability flag_probability = profile_probability::uninitialized ();
    2136              : 
    2137              :   /* Flag is set in FLAG_BBS. Determine probability that flag will be true
    2138              :      at loop exit.
    2139              : 
    2140              :      This code may look fancy, but it cannot update profile very realistically
    2141              :      because we do not know the probability that flag will be true at given
    2142              :      loop exit.
    2143              : 
    2144              :      We look for two interesting extremes
    2145              :        - when exit is dominated by block setting the flag, we know it will
    2146              :          always be true.  This is a common case.
    2147              :        - when all blocks setting the flag have very low frequency we know
    2148              :          it will likely be false.
    2149              :      In all other cases we default to 2/3 for flag being true.  */
    2150              : 
    2151        12075 :   for (hash_set<basic_block>::iterator it = flag_bbs->begin ();
    2152        27113 :        it != flag_bbs->end (); ++it)
    2153              :     {
    2154        15038 :        if ((*it)->count.initialized_p ())
    2155        15025 :          count_sum += (*it)->count, ncount ++;
    2156        15038 :        if (dominated_by_p (CDI_DOMINATORS, ex->src, *it))
    2157         2538 :          flag_probability = profile_probability::always ();
    2158        15038 :        nbbs++;
    2159              :     }
    2160              : 
    2161        12075 :   profile_probability cap
    2162        12075 :           = profile_probability::guessed_always ().apply_scale (2, 3);
    2163              : 
    2164        12075 :   if (flag_probability.initialized_p ())
    2165              :     ;
    2166         9643 :   else if (ncount == nbbs
    2167        19541 :            && preheader->count () >= count_sum && preheader->count ().nonzero_p ())
    2168              :     {
    2169          172 :       flag_probability = count_sum.probability_in (preheader->count ());
    2170          172 :       if (flag_probability > cap)
    2171           77 :         flag_probability = cap;
    2172              :     }
    2173              : 
    2174        12075 :   if (!flag_probability.initialized_p ())
    2175         9471 :     flag_probability = cap;
    2176              : 
    2177              :   /* ?? Insert store after previous store if applicable.  See note
    2178              :      below.  */
    2179        12075 :   if (append_cond_position)
    2180         4130 :     ex = append_cond_position;
    2181              : 
    2182        12075 :   loop_has_only_one_exit = single_pred_p (ex->dest);
    2183              : 
    2184        12075 :   if (loop_has_only_one_exit)
    2185         5128 :     ex = split_block_after_labels (ex->dest);
    2186              :   else
    2187              :     {
    2188         6947 :       for (gphi_iterator gpi = gsi_start_phis (ex->dest);
    2189        10646 :            !gsi_end_p (gpi); gsi_next (&gpi))
    2190              :         {
    2191         4598 :           gphi *phi = gpi.phi ();
    2192         9196 :           if (virtual_operand_p (gimple_phi_result (phi)))
    2193         3699 :             continue;
    2194              : 
    2195              :           /* When the destination has a non-virtual PHI node with multiple
    2196              :              predecessors make sure we preserve the PHI structure by
    2197              :              forcing a forwarder block so that hoisting of that PHI will
    2198              :              still work.  */
    2199          899 :           split_edge (ex);
    2200          899 :           break;
    2201              :         }
    2202              :     }
    2203              : 
    2204        12075 :   old_dest = ex->dest;
    2205        12075 :   new_bb = split_edge (ex);
    2206        12075 :   if (append_cond_position)
    2207         4130 :     new_bb->count += last_cond_fallthru->count ();
    2208        12075 :   then_bb = create_empty_bb (new_bb);
    2209        12075 :   then_bb->count = new_bb->count.apply_probability (flag_probability);
    2210        12075 :   if (irr)
    2211           51 :     then_bb->flags = BB_IRREDUCIBLE_LOOP;
    2212        12075 :   add_bb_to_loop (then_bb, new_bb->loop_father);
    2213              : 
    2214        12075 :   gsi = gsi_start_bb (new_bb);
    2215        12075 :   stmt = gimple_build_cond (NE_EXPR, flag, boolean_false_node,
    2216              :                             NULL_TREE, NULL_TREE);
    2217        12075 :   gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
    2218              : 
    2219              :   /* Insert actual store.  */
    2220        12075 :   if (mem)
    2221              :     {
    2222         9617 :       gsi = gsi_start_bb (then_bb);
    2223         9617 :       stmt = gimple_build_assign (unshare_expr (mem), tmp_var);
    2224         9617 :       gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
    2225              :     }
    2226              : 
    2227        12075 :   edge e1 = single_succ_edge (new_bb);
    2228        24099 :   edge e2 = make_edge (new_bb, then_bb,
    2229              :                        EDGE_TRUE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
    2230        12075 :   e2->probability = flag_probability;
    2231              : 
    2232        12075 :   e1->flags |= EDGE_FALSE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0);
    2233        12075 :   e1->flags &= ~EDGE_FALLTHRU;
    2234              : 
    2235        12075 :   e1->probability = flag_probability.invert ();
    2236              : 
    2237        24099 :   then_old_edge = make_single_succ_edge (then_bb, old_dest,
    2238              :                              EDGE_FALLTHRU | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
    2239              : 
    2240        12075 :   set_immediate_dominator (CDI_DOMINATORS, then_bb, new_bb);
    2241              : 
    2242        12075 :   if (append_cond_position)
    2243              :     {
    2244         4130 :       basic_block prevbb = last_cond_fallthru->src;
    2245         4130 :       redirect_edge_succ (last_cond_fallthru, new_bb);
    2246         4130 :       set_immediate_dominator (CDI_DOMINATORS, new_bb, prevbb);
    2247         4130 :       set_immediate_dominator (CDI_DOMINATORS, old_dest,
    2248              :                                recompute_dominator (CDI_DOMINATORS, old_dest));
    2249              :     }
    2250              : 
    2251              :   /* ?? Because stores may alias, they must happen in the exact
    2252              :      sequence they originally happened.  Save the position right after
    2253              :      the (_lsm) store we just created so we can continue appending after
    2254              :      it and maintain the original order.  */
    2255        12075 :   append_cond_position = then_old_edge;
    2256        12075 :   last_cond_fallthru = find_edge (new_bb, old_dest);
    2257              : 
    2258        12075 :   if (!loop_has_only_one_exit)
    2259         6947 :     for (gphi_iterator gpi = gsi_start_phis (old_dest);
    2260        10476 :          !gsi_end_p (gpi); gsi_next (&gpi))
    2261              :       {
    2262         3529 :         gphi *phi = gpi.phi ();
    2263         3529 :         unsigned i;
    2264              : 
    2265        23395 :         for (i = 0; i < gimple_phi_num_args (phi); i++)
    2266        16337 :           if (gimple_phi_arg_edge (phi, i)->src == new_bb)
    2267              :             {
    2268         3529 :               tree arg = gimple_phi_arg_def (phi, i);
    2269         3529 :               add_phi_arg (phi, arg, then_old_edge, UNKNOWN_LOCATION);
    2270         3529 :               update_stmt (phi);
    2271              :             }
    2272              :       }
    2273              : 
    2274        12075 :   return then_bb;
    2275              : }
    2276              : 
    2277              : /* When REF is set on the location, set flag indicating the store.  */
    2278              : 
    2279              : class sm_set_flag_if_changed
    2280              : {
    2281              : public:
    2282         6901 :   sm_set_flag_if_changed (tree flag_, hash_set <basic_block> *bbs_)
    2283         6901 :          : flag (flag_), bbs (bbs_) {}
    2284              :   bool operator () (mem_ref_loc *loc);
    2285              :   tree flag;
    2286              :   hash_set <basic_block> *bbs;
    2287              : };
    2288              : 
    2289              : bool
    2290        12828 : sm_set_flag_if_changed::operator () (mem_ref_loc *loc)
    2291              : {
    2292              :   /* Only set the flag for writes.  */
    2293        12828 :   if (is_gimple_assign (loc->stmt)
    2294        12828 :       && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
    2295              :     {
    2296         7921 :       gimple_stmt_iterator gsi = gsi_for_stmt (loc->stmt);
    2297         7921 :       gimple *stmt = gimple_build_assign (flag, boolean_true_node);
    2298         7921 :       gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
    2299         7921 :       bbs->add (gimple_bb (stmt));
    2300              :     }
    2301        12828 :   return false;
    2302              : }
    2303              : 
    2304              : /* Helper function for execute_sm.  On every location where REF is
    2305              :    set, set an appropriate flag indicating the store.  */
    2306              : 
    2307              : static tree
    2308         6901 : execute_sm_if_changed_flag_set (class loop *loop, im_mem_ref *ref,
    2309              :                                 hash_set <basic_block> *bbs)
    2310              : {
    2311         6901 :   tree flag;
    2312         6901 :   char *str = get_lsm_tmp_name (ref->mem.ref, ~0, "_flag");
    2313         6901 :   flag = create_tmp_reg (boolean_type_node, str);
    2314         6901 :   for_all_locs_in_loop (loop, ref, sm_set_flag_if_changed (flag, bbs));
    2315         6901 :   return flag;
    2316              : }
    2317              : 
    2318        35357 : struct sm_aux
    2319              : {
    2320              :   tree tmp_var;
    2321              :   tree store_flag;
    2322              :   hash_set <basic_block> flag_bbs;
    2323              : };
    2324              : 
    2325              : /* Executes store motion of memory reference REF from LOOP.
    2326              :    Exits from the LOOP are stored in EXITS.  The initialization of the
    2327              :    temporary variable is put to the preheader of the loop, and assignments
    2328              :    to the reference from the temporary variable are emitted to exits.  */
    2329              : 
    2330              : static sm_aux *
    2331        35357 : execute_sm (class loop *loop, im_mem_ref *ref,
    2332              :             hash_map<im_mem_ref *, sm_aux *> &aux_map, bool maybe_mt,
    2333              :             bool use_other_flag_var)
    2334              : {
    2335        35357 :   gassign *load;
    2336        35357 :   struct fmt_data fmt_data;
    2337        35357 :   struct lim_aux_data *lim_data;
    2338        35357 :   bool multi_threaded_model_p = false;
    2339        35357 :   gimple_stmt_iterator gsi;
    2340        35357 :   sm_aux *aux = new sm_aux;
    2341              : 
    2342        35357 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2343              :     {
    2344           82 :       fprintf (dump_file, "Executing store motion of ");
    2345           82 :       print_generic_expr (dump_file, ref->mem.ref);
    2346           82 :       fprintf (dump_file, " from loop %d\n", loop->num);
    2347              :     }
    2348              : 
    2349        35357 :   aux->tmp_var = create_tmp_reg (TREE_TYPE (ref->mem.ref),
    2350        35357 :                                  get_lsm_tmp_name (ref->mem.ref, ~0));
    2351              : 
    2352        35357 :   fmt_data.loop = loop;
    2353        35357 :   fmt_data.orig_loop = loop;
    2354        35357 :   for_each_index (&ref->mem.ref, force_move_till, &fmt_data);
    2355              : 
    2356        70714 :   bool always_stored = ref_always_stored_p (loop, ref);
    2357        35357 :   if (maybe_mt
    2358        10966 :       && (bb_in_transaction (loop_preheader_edge (loop)->src)
    2359        10965 :           || (ref_can_have_store_data_races (ref->mem.ref) && ! always_stored)
    2360              :           /* Do not speculate a load/store when that's not a noop, either
    2361              :              because the mode cannot be transferred or because there's
    2362              :              UB involved for out-of-bound values.  */
    2363         3798 :           || !mode_can_transfer_bits (TYPE_MODE (TREE_TYPE (ref->mem.ref)))
    2364         3798 :           || TREE_CODE (TREE_TYPE (ref->mem.ref)) == BOOLEAN_TYPE
    2365         3787 :           || (TREE_CODE (ref->mem.ref) == COMPONENT_REF
    2366          884 :               && DECL_BIT_FIELD (TREE_OPERAND (ref->mem.ref, 1)))))
    2367              :     multi_threaded_model_p = true;
    2368              : 
    2369        35357 :   if (multi_threaded_model_p && !use_other_flag_var)
    2370         6901 :     aux->store_flag
    2371         6901 :       = execute_sm_if_changed_flag_set (loop, ref, &aux->flag_bbs);
    2372              :   else
    2373              :     aux->store_flag = NULL_TREE;
    2374              : 
    2375              :   /* Remember variable setup.  */
    2376        35357 :   aux_map.put (ref, aux);
    2377              : 
    2378        35357 :   rewrite_mem_refs (loop, ref, aux->tmp_var);
    2379              : 
    2380              :   /* Emit the load code on a random exit edge or into the latch if
    2381              :      the loop does not exit, so that we are sure it will be processed
    2382              :      by move_computations after all dependencies.  */
    2383        35357 :   gsi = gsi_for_stmt (first_mem_ref_loc (loop, ref)->stmt);
    2384              : 
    2385              :   /* Avoid doing a load if there was no load of the ref in the loop.
    2386              :      Esp. when the ref is not always stored we cannot optimize it
    2387              :      away later.  But when it is not always stored we must use a conditional
    2388              :      store then.  */
    2389        35357 :   if ((!always_stored && !multi_threaded_model_p)
    2390        35357 :       || (ref->loaded && bitmap_bit_p (ref->loaded, loop->num)))
    2391        18518 :     load = gimple_build_assign (aux->tmp_var, unshare_expr (ref->mem.ref));
    2392              :   else
    2393              :     {
    2394              :       /* If not emitting a load mark the uninitialized state on the
    2395              :          loop entry as not to be warned for.  */
    2396        16839 :       tree uninit = create_tmp_reg (TREE_TYPE (aux->tmp_var));
    2397        16839 :       suppress_warning (uninit, OPT_Wuninitialized);
    2398        16839 :       uninit = get_or_create_ssa_default_def (cfun, uninit);
    2399        16839 :       load = gimple_build_assign (aux->tmp_var, uninit);
    2400              :     }
    2401        35357 :   lim_data = init_lim_data (load);
    2402        35357 :   lim_data->max_loop = loop;
    2403        35357 :   lim_data->tgt_loop = loop;
    2404        35357 :   gsi_insert_before (&gsi, load, GSI_SAME_STMT);
    2405              : 
    2406        35357 :   if (aux->store_flag)
    2407              :     {
    2408         6901 :       load = gimple_build_assign (aux->store_flag, boolean_false_node);
    2409         6901 :       lim_data = init_lim_data (load);
    2410         6901 :       lim_data->max_loop = loop;
    2411         6901 :       lim_data->tgt_loop = loop;
    2412         6901 :       gsi_insert_before (&gsi, load, GSI_SAME_STMT);
    2413              :     }
    2414              : 
    2415        35357 :   return aux;
    2416              : }
    2417              : 
    2418              : /* sm_ord is used for ordinary stores we can retain order with respect
    2419              :        to other stores
    2420              :    sm_unord is used for conditional executed stores which need to be
    2421              :        able to execute in arbitrary order with respect to other stores
    2422              :    sm_other is used for stores we do not try to apply store motion to.  */
    2423              : enum sm_kind { sm_ord, sm_unord, sm_other };
    2424              : struct seq_entry
    2425              : {
    2426              :   seq_entry () = default;
    2427        51989 :   seq_entry (unsigned f, sm_kind k, tree fr = NULL)
    2428        51989 :     : first (f), second (k), from (fr) {}
    2429              :   unsigned first;
    2430              :   sm_kind second;
    2431              :   tree from;
    2432              : };
    2433              : 
    2434              : static void
    2435        33004 : execute_sm_exit (class loop *loop, edge ex, vec<seq_entry> &seq,
    2436              :                  hash_map<im_mem_ref *, sm_aux *> &aux_map, sm_kind kind,
    2437              :                  edge &append_cond_position, edge &last_cond_fallthru,
    2438              :                  bitmap clobbers_to_prune)
    2439              : {
    2440              :   /* Sink the stores to exit from the loop.  */
    2441       114960 :   for (unsigned i = seq.length (); i > 0; --i)
    2442              :     {
    2443        48952 :       im_mem_ref *ref = memory_accesses.refs_list[seq[i-1].first];
    2444        48952 :       if (seq[i-1].second == sm_other)
    2445              :         {
    2446         4887 :           gcc_assert (kind == sm_ord && seq[i-1].from != NULL_TREE);
    2447         4887 :           gassign *store;
    2448         4887 :           if (ref->mem.ref == error_mark_node)
    2449              :             {
    2450          185 :               tree lhs = gimple_assign_lhs (ref->accesses_in_loop[0].stmt);
    2451          185 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2452              :                 {
    2453            3 :                   fprintf (dump_file, "Re-issuing dependent ");
    2454            3 :                   print_generic_expr (dump_file, unshare_expr (seq[i-1].from));
    2455            3 :                   fprintf (dump_file, " of ");
    2456            3 :                   print_generic_expr (dump_file, lhs);
    2457            3 :                   fprintf (dump_file, " from loop %d on exit %d -> %d\n",
    2458            3 :                            loop->num, ex->src->index, ex->dest->index);
    2459              :                 }
    2460          185 :               store = gimple_build_assign (unshare_expr (lhs),
    2461          185 :                                            unshare_expr (seq[i-1].from));
    2462          185 :               bitmap_set_bit (clobbers_to_prune, seq[i-1].first);
    2463              :             }
    2464              :           else
    2465              :             {
    2466         4702 :               if (dump_file && (dump_flags & TDF_DETAILS))
    2467              :                 {
    2468            0 :                   fprintf (dump_file, "Re-issuing dependent store of ");
    2469            0 :                   print_generic_expr (dump_file, ref->mem.ref);
    2470            0 :                   fprintf (dump_file, " from loop %d on exit %d -> %d\n",
    2471            0 :                            loop->num, ex->src->index, ex->dest->index);
    2472              :                 }
    2473         4702 :               store = gimple_build_assign (unshare_expr (ref->mem.ref),
    2474         4702 :                                            seq[i-1].from);
    2475              :             }
    2476         4887 :           gsi_insert_on_edge (ex, store);
    2477              :         }
    2478              :       else
    2479              :         {
    2480        44065 :           sm_aux *aux = *aux_map.get (ref);
    2481        44065 :           if (!aux->store_flag || kind == sm_ord)
    2482              :             {
    2483        34448 :               gassign *store;
    2484        34448 :               store = gimple_build_assign (unshare_expr (ref->mem.ref),
    2485              :                                            aux->tmp_var);
    2486        34448 :               gsi_insert_on_edge (ex, store);
    2487        34448 :             }
    2488              :           else
    2489         9617 :             execute_sm_if_changed (ex, ref->mem.ref, aux->tmp_var,
    2490              :                                    aux->store_flag,
    2491              :                                    loop_preheader_edge (loop), &aux->flag_bbs,
    2492              :                                    append_cond_position, last_cond_fallthru);
    2493              :         }
    2494              :     }
    2495        33004 : }
    2496              : 
    2497              : /* Push the SM candidate at index PTR in the sequence SEQ down until
    2498              :    we hit the next SM candidate.  Return true if that went OK and
    2499              :    false if we could not disambiguate against another unrelated ref.
    2500              :    Update *AT to the index where the candidate now resides.  */
    2501              : 
    2502              : static bool
    2503        38724 : sm_seq_push_down (vec<seq_entry> &seq, unsigned ptr, unsigned *at)
    2504              : {
    2505        38724 :   *at = ptr;
    2506        39461 :   for (; ptr > 0; --ptr)
    2507              :     {
    2508        17719 :       seq_entry &new_cand = seq[ptr];
    2509        17719 :       seq_entry &against = seq[ptr-1];
    2510        17719 :       if (against.second == sm_ord
    2511         5740 :           || (against.second == sm_other && against.from != NULL_TREE))
    2512              :         /* Found the tail of the sequence.  */
    2513              :         break;
    2514              :       /* We may not ignore self-dependences here.  */
    2515         1044 :       if (new_cand.first == against.first
    2516              :           /* ???  We could actually handle clobbers here, but not easily
    2517              :              with LIMs dependence analysis.  */
    2518          822 :           || (memory_accesses.refs_list[new_cand.first]->mem.ref
    2519          822 :               == error_mark_node)
    2520          817 :           || (memory_accesses.refs_list[against.first]->mem.ref
    2521              :               == error_mark_node)
    2522         1837 :           || !refs_independent_p (memory_accesses.refs_list[new_cand.first],
    2523          793 :                                   memory_accesses.refs_list[against.first],
    2524              :                                   false))
    2525              :         /* ???  Prune new_cand from the list of refs to apply SM to.  */
    2526              :         return false;
    2527          737 :       std::swap (new_cand, against);
    2528          737 :       *at = ptr - 1;
    2529              :     }
    2530              :   return true;
    2531              : }
    2532              : 
    2533              : /* Computes the sequence of stores from candidates in REFS_NOT_IN_SEQ to SEQ
    2534              :    walking backwards from VDEF (or the end of BB if VDEF is NULL).  */
    2535              : 
    2536              : static int
    2537        30882 : sm_seq_valid_bb (class loop *loop, basic_block bb, tree vdef,
    2538              :                  vec<seq_entry> &seq, bitmap refs_not_in_seq,
    2539              :                  bitmap refs_not_supported, bool forked,
    2540              :                  bitmap fully_visited)
    2541              : {
    2542        35683 :   if (!vdef)
    2543       150095 :     for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi);
    2544        95883 :          gsi_prev (&gsi))
    2545              :       {
    2546       150160 :         vdef = gimple_vdef (gsi_stmt (gsi));
    2547        54277 :         if (vdef)
    2548              :           break;
    2549              :       }
    2550        27106 :   if (!vdef)
    2551              :     {
    2552         8113 :       gphi *vphi = get_virtual_phi (bb);
    2553         8113 :       if (vphi)
    2554         4064 :         vdef = gimple_phi_result (vphi);
    2555              :     }
    2556        35683 :   if (!vdef)
    2557              :     {
    2558         4049 :       if (single_pred_p (bb))
    2559              :         /* This handles the perfect nest case.  */
    2560         3272 :         return sm_seq_valid_bb (loop, single_pred (bb), vdef,
    2561              :                                 seq, refs_not_in_seq, refs_not_supported,
    2562         3272 :                                 forked, fully_visited);
    2563              :       return 0;
    2564              :     }
    2565        78820 :   do
    2566              :     {
    2567        55227 :       gimple *def = SSA_NAME_DEF_STMT (vdef);
    2568        55227 :       if (gimple_bb (def) != bb)
    2569              :         {
    2570              :           /* If we forked by processing a PHI do not allow our walk to
    2571              :              merge again until we handle that robustly.  */
    2572         2984 :           if (forked)
    2573              :             {
    2574              :               /* Mark refs_not_in_seq as unsupported.  */
    2575         1261 :               bitmap_ior_into (refs_not_supported, refs_not_in_seq);
    2576         1261 :               return 1;
    2577              :             }
    2578              :           /* Otherwise it doesn't really matter if we end up in different
    2579              :              BBs.  */
    2580              :           bb = gimple_bb (def);
    2581              :         }
    2582        53966 :       if (gphi *phi = dyn_cast <gphi *> (def))
    2583              :         {
    2584              :           /* Handle CFG merges.  Until we handle forks (gimple_bb (def) != bb)
    2585              :              this is still linear.
    2586              :              Eventually we want to cache intermediate results per BB
    2587              :              (but we can't easily cache for different exits?).  */
    2588              :           /* Stop at PHIs with possible backedges.  */
    2589        10186 :           if (bb == bb->loop_father->header
    2590         5088 :               || bb->flags & BB_IRREDUCIBLE_LOOP)
    2591              :             {
    2592              :               /* Mark refs_not_in_seq as unsupported.  */
    2593         5103 :               bitmap_ior_into (refs_not_supported, refs_not_in_seq);
    2594         5103 :               return 1;
    2595              :             }
    2596         5083 :           if (gimple_phi_num_args (phi) == 1)
    2597         1529 :             return sm_seq_valid_bb (loop, gimple_phi_arg_edge (phi, 0)->src,
    2598              :                                     gimple_phi_arg_def (phi, 0), seq,
    2599              :                                     refs_not_in_seq, refs_not_supported,
    2600         1529 :                                     false, fully_visited);
    2601         7108 :           if (bitmap_bit_p (fully_visited,
    2602         3554 :                             SSA_NAME_VERSION (gimple_phi_result (phi))))
    2603              :             return 1;
    2604         3450 :           auto_vec<seq_entry> first_edge_seq;
    2605         3450 :           auto_bitmap tem_refs_not_in_seq (&lim_bitmap_obstack);
    2606         3450 :           int eret;
    2607         3450 :           bitmap_copy (tem_refs_not_in_seq, refs_not_in_seq);
    2608         3450 :           eret = sm_seq_valid_bb (loop, gimple_phi_arg_edge (phi, 0)->src,
    2609              :                                   gimple_phi_arg_def (phi, 0),
    2610              :                                   first_edge_seq,
    2611              :                                   tem_refs_not_in_seq, refs_not_supported,
    2612              :                                   true, fully_visited);
    2613         3450 :           if (eret != 1)
    2614              :             return -1;
    2615              :           /* Simplify our lives by pruning the sequence of !sm_ord.  */
    2616         3273 :           while (!first_edge_seq.is_empty ()
    2617         7899 :                  && first_edge_seq.last ().second != sm_ord)
    2618         1176 :             first_edge_seq.pop ();
    2619         7048 :           for (unsigned int i = 1; i < gimple_phi_num_args (phi); ++i)
    2620              :             {
    2621         5502 :               tree vuse = gimple_phi_arg_def (phi, i);
    2622         5502 :               edge e = gimple_phi_arg_edge (phi, i);
    2623         5502 :               auto_vec<seq_entry> edge_seq;
    2624         5502 :               bitmap_and_compl (tem_refs_not_in_seq,
    2625              :                                 refs_not_in_seq, refs_not_supported);
    2626              :               /* If we've marked all refs we search for as unsupported
    2627              :                  we can stop processing and use the sequence as before
    2628              :                  the PHI.  */
    2629         5502 :               if (bitmap_empty_p (tem_refs_not_in_seq))
    2630              :                 return 1;
    2631         3598 :               eret = sm_seq_valid_bb (loop, e->src, vuse, edge_seq,
    2632              :                                       tem_refs_not_in_seq, refs_not_supported,
    2633              :                                       true, fully_visited);
    2634         3598 :               if (eret != 1)
    2635              :                 return -1;
    2636              :               /* Simplify our lives by pruning the sequence of !sm_ord.  */
    2637         3162 :               while (!edge_seq.is_empty ()
    2638         7810 :                      && edge_seq.last ().second != sm_ord)
    2639         1050 :                 edge_seq.pop ();
    2640         7196 :               unsigned min_len = MIN(first_edge_seq.length (),
    2641              :                                      edge_seq.length ());
    2642              :               /* Incrementally merge seqs into first_edge_seq.  */
    2643         3598 :               int first_uneq = -1;
    2644         3598 :               auto_vec<seq_entry, 2> extra_refs;
    2645         5758 :               for (unsigned int i = 0; i < min_len; ++i)
    2646              :                 {
    2647              :                   /* ???  We can more intelligently merge when we face different
    2648              :                      order by additional sinking operations in one sequence.
    2649              :                      For now we simply mark them as to be processed by the
    2650              :                      not order-preserving SM code.  */
    2651         2160 :                   if (first_edge_seq[i].first != edge_seq[i].first)
    2652              :                     {
    2653           34 :                       if (first_edge_seq[i].second == sm_ord)
    2654           21 :                         bitmap_set_bit (refs_not_supported,
    2655           21 :                                         first_edge_seq[i].first);
    2656           34 :                       if (edge_seq[i].second == sm_ord)
    2657           26 :                         bitmap_set_bit (refs_not_supported, edge_seq[i].first);
    2658           34 :                       first_edge_seq[i].second = sm_other;
    2659           34 :                       first_edge_seq[i].from = NULL_TREE;
    2660              :                       /* Record the dropped refs for later processing.  */
    2661           34 :                       if (first_uneq == -1)
    2662           32 :                         first_uneq = i;
    2663           68 :                       extra_refs.safe_push (seq_entry (edge_seq[i].first,
    2664           34 :                                                        sm_other, NULL_TREE));
    2665              :                     }
    2666              :                   /* sm_other prevails.  */
    2667         2126 :                   else if (first_edge_seq[i].second != edge_seq[i].second)
    2668              :                     {
    2669              :                       /* Make sure the ref is marked as not supported.  */
    2670            0 :                       bitmap_set_bit (refs_not_supported,
    2671            0 :                                       first_edge_seq[i].first);
    2672            0 :                       first_edge_seq[i].second = sm_other;
    2673            0 :                       first_edge_seq[i].from = NULL_TREE;
    2674              :                     }
    2675         2126 :                   else if (first_edge_seq[i].second == sm_other
    2676            4 :                            && first_edge_seq[i].from != NULL_TREE
    2677         2130 :                            && (edge_seq[i].from == NULL_TREE
    2678            4 :                                || !operand_equal_p (first_edge_seq[i].from,
    2679            4 :                                                     edge_seq[i].from, 0)))
    2680            4 :                     first_edge_seq[i].from = NULL_TREE;
    2681              :                 }
    2682              :               /* Any excess elements become sm_other since they are now
    2683              :                  coonditionally executed.  */
    2684         9890 :               if (first_edge_seq.length () > edge_seq.length ())
    2685              :                 {
    2686         6465 :                   for (unsigned i = edge_seq.length ();
    2687         8270 :                        i < first_edge_seq.length (); ++i)
    2688              :                     {
    2689         6465 :                       if (first_edge_seq[i].second == sm_ord)
    2690         3343 :                         bitmap_set_bit (refs_not_supported,
    2691         3343 :                                         first_edge_seq[i].first);
    2692         6465 :                       first_edge_seq[i].second = sm_other;
    2693              :                     }
    2694              :                 }
    2695         1793 :               else if (edge_seq.length () > first_edge_seq.length ())
    2696              :                 {
    2697            5 :                   if (first_uneq == -1)
    2698            0 :                     first_uneq = first_edge_seq.length ();
    2699            5 :                   for (unsigned i = first_edge_seq.length ();
    2700           20 :                        i < edge_seq.length (); ++i)
    2701              :                     {
    2702           15 :                       if (edge_seq[i].second == sm_ord)
    2703            5 :                         bitmap_set_bit (refs_not_supported, edge_seq[i].first);
    2704           30 :                       extra_refs.safe_push (seq_entry (edge_seq[i].first,
    2705           15 :                                                        sm_other, NULL_TREE));
    2706              :                     }
    2707              :                 }
    2708              :               /* Put unmerged refs at first_uneq to force dependence checking
    2709              :                  on them.  */
    2710         3598 :               if (first_uneq != -1)
    2711              :                 {
    2712              :                   /* Missing ordered_splice_at.  */
    2713           64 :                   if ((unsigned)first_uneq == first_edge_seq.length ())
    2714            0 :                     first_edge_seq.safe_splice (extra_refs);
    2715              :                   else
    2716              :                     {
    2717           32 :                       unsigned fes_length = first_edge_seq.length ();
    2718           32 :                       first_edge_seq.safe_grow (fes_length
    2719           32 :                                                 + extra_refs.length ());
    2720           32 :                       memmove (&first_edge_seq[first_uneq + extra_refs.length ()],
    2721           32 :                                &first_edge_seq[first_uneq],
    2722           32 :                                (fes_length - first_uneq) * sizeof (seq_entry));
    2723           64 :                       memcpy (&first_edge_seq[first_uneq],
    2724           32 :                               extra_refs.address (),
    2725           32 :                               extra_refs.length () * sizeof (seq_entry));
    2726              :                     }
    2727              :                 }
    2728         5502 :             }
    2729              :           /* Use the sequence from the first edge and push SMs down.  */
    2730         4346 :           for (unsigned i = 0; i < first_edge_seq.length (); ++i)
    2731              :             {
    2732         2800 :               unsigned id = first_edge_seq[i].first;
    2733         2800 :               seq.safe_push (first_edge_seq[i]);
    2734         2800 :               unsigned new_idx;
    2735         2800 :               if ((first_edge_seq[i].second == sm_ord
    2736         2179 :                    || (first_edge_seq[i].second == sm_other
    2737         2179 :                        && first_edge_seq[i].from != NULL_TREE))
    2738         3771 :                   && !sm_seq_push_down (seq, seq.length () - 1, &new_idx))
    2739              :                 {
    2740          125 :                   if (first_edge_seq[i].second == sm_ord)
    2741            0 :                     bitmap_set_bit (refs_not_supported, id);
    2742              :                   /* Mark it sm_other.  */
    2743          125 :                   seq[new_idx].second = sm_other;
    2744          125 :                   seq[new_idx].from = NULL_TREE;
    2745              :                 }
    2746              :             }
    2747         1546 :           bitmap_set_bit (fully_visited,
    2748         1546 :                           SSA_NAME_VERSION (gimple_phi_result (phi)));
    2749         1546 :           return 1;
    2750         3450 :         }
    2751        43780 :       lim_aux_data *data = get_lim_data (def);
    2752        43780 :       im_mem_ref *ref = memory_accesses.refs_list[data->ref];
    2753        43780 :       if (data->ref == UNANALYZABLE_MEM_ID)
    2754              :         return -1;
    2755              :       /* Stop at memory references which we can't move.  */
    2756        43780 :       else if ((ref->mem.ref == error_mark_node
    2757              :                 /* We can move end-of-storage/object down.  */
    2758          383 :                 && !gimple_clobber_p (ref->accesses_in_loop[0].stmt,
    2759              :                                       CLOBBER_STORAGE_END)
    2760          246 :                 && !gimple_clobber_p (ref->accesses_in_loop[0].stmt,
    2761              :                                       CLOBBER_OBJECT_END))
    2762        44073 :                || TREE_THIS_VOLATILE (ref->mem.ref))
    2763              :         {
    2764              :           /* Mark refs_not_in_seq as unsupported.  */
    2765          122 :           bitmap_ior_into (refs_not_supported, refs_not_in_seq);
    2766          122 :           return 1;
    2767              :         }
    2768              :       /* One of the stores we want to apply SM to and we've not yet seen.  */
    2769        43658 :       else if (bitmap_clear_bit (refs_not_in_seq, data->ref))
    2770              :         {
    2771        34662 :           seq.safe_push (seq_entry (data->ref, sm_ord));
    2772              : 
    2773              :           /* 1) push it down the queue until a SMed
    2774              :              and not ignored ref is reached, skipping all not SMed refs
    2775              :              and ignored refs via non-TBAA disambiguation.  */
    2776        34662 :           unsigned new_idx;
    2777        69324 :           if (!sm_seq_push_down (seq, seq.length () - 1, &new_idx)
    2778              :               /* If that fails but we did not fork yet continue, we'll see
    2779              :                  to re-materialize all of the stores in the sequence then.
    2780              :                  Further stores will only be pushed up to this one.  */
    2781        34662 :               && forked)
    2782              :             {
    2783            0 :               bitmap_set_bit (refs_not_supported, data->ref);
    2784              :               /* Mark it sm_other.  */
    2785            0 :               seq[new_idx].second = sm_other;
    2786              :             }
    2787              : 
    2788              :           /* 2) check whether we've seen all refs we want to SM and if so
    2789              :              declare success for the active exit  */
    2790        34662 :           if (bitmap_empty_p (refs_not_in_seq))
    2791        20065 :             return 1;
    2792              :         }
    2793              :       else
    2794              :         /* Another store not part of the final sequence.  Simply push it.  */
    2795         8996 :         seq.safe_push (seq_entry (data->ref, sm_other,
    2796         8996 :                                   gimple_assign_rhs1 (def)));
    2797              : 
    2798        23593 :       vdef = gimple_vuse (def);
    2799        23593 :     }
    2800              :   while (1);
    2801              : }
    2802              : 
    2803              : /* Hoists memory references MEM_REFS out of LOOP.  EXITS is the list of exit
    2804              :    edges of the LOOP.  */
    2805              : 
    2806              : static void
    2807        22203 : hoist_memory_references (class loop *loop, bitmap mem_refs,
    2808              :                          const vec<edge> &exits)
    2809              : {
    2810        22203 :   im_mem_ref *ref;
    2811        22203 :   unsigned  i;
    2812        22203 :   bitmap_iterator bi;
    2813              : 
    2814              :   /* There's a special case we can use ordered re-materialization for
    2815              :      conditionally executed stores which is when all stores in the loop
    2816              :      happen in the same basic-block.  In that case we know we'll reach
    2817              :      all stores and thus can simply process that BB and emit a single
    2818              :      conditional block of ordered materializations.  See PR102436.  */
    2819        22203 :   basic_block single_store_bb = NULL;
    2820        31772 :   EXECUTE_IF_SET_IN_BITMAP (&memory_accesses.all_refs_stored_in_loop[loop->num],
    2821              :                             0, i, bi)
    2822              :     {
    2823        29504 :       bool fail = false;
    2824        29504 :       ref = memory_accesses.refs_list[i];
    2825       136617 :       for (auto loc : ref->accesses_in_loop)
    2826       148649 :         if (!gimple_vdef (loc.stmt))
    2827              :           ;
    2828        32504 :         else if (!single_store_bb)
    2829              :           {
    2830        22203 :             single_store_bb = gimple_bb (loc.stmt);
    2831        22203 :             bool conditional = false;
    2832        80396 :             for (edge e : exits)
    2833        23918 :               if (!dominated_by_p (CDI_DOMINATORS, e->src, single_store_bb))
    2834              :                 {
    2835              :                   /* Conditional as seen from e.  */
    2836              :                   conditional = true;
    2837              :                   break;
    2838              :                 }
    2839        22203 :             if (!conditional)
    2840              :               {
    2841              :                 fail = true;
    2842              :                 break;
    2843              :               }
    2844              :           }
    2845        10301 :         else if (single_store_bb != gimple_bb (loc.stmt))
    2846              :           {
    2847              :             fail = true;
    2848              :             break;
    2849              :           }
    2850        29504 :       if (fail)
    2851              :         {
    2852              :           single_store_bb = NULL;
    2853              :           break;
    2854              :         }
    2855              :     }
    2856        22203 :   if (single_store_bb)
    2857              :     {
    2858              :       /* Analyze the single block with stores.  */
    2859         2268 :       auto_bitmap fully_visited;
    2860         2268 :       auto_bitmap refs_not_supported;
    2861         2268 :       auto_bitmap refs_not_in_seq;
    2862         2268 :       auto_vec<seq_entry> seq;
    2863         2268 :       bitmap_copy (refs_not_in_seq, mem_refs);
    2864         2268 :       int res = sm_seq_valid_bb (loop, single_store_bb, NULL_TREE,
    2865              :                                  seq, refs_not_in_seq, refs_not_supported,
    2866              :                                  false, fully_visited);
    2867         2268 :       if (res != 1)
    2868              :         {
    2869              :           /* Unhandled refs can still fail this.  */
    2870            0 :           bitmap_clear (mem_refs);
    2871            0 :           return;
    2872              :         }
    2873              : 
    2874              :       /* We cannot handle sm_other since we neither remember the
    2875              :          stored location nor the value at the point we execute them.  */
    2876         5431 :       for (unsigned i = 0; i < seq.length (); ++i)
    2877              :         {
    2878         3163 :           unsigned new_i;
    2879         3163 :           if (seq[i].second == sm_other
    2880         3163 :               && seq[i].from != NULL_TREE)
    2881          410 :             seq[i].from = NULL_TREE;
    2882         2753 :           else if ((seq[i].second == sm_ord
    2883            0 :                     || (seq[i].second == sm_other
    2884            0 :                         && seq[i].from != NULL_TREE))
    2885         2753 :                    && !sm_seq_push_down (seq, i, &new_i))
    2886              :             {
    2887           69 :               bitmap_set_bit (refs_not_supported, seq[new_i].first);
    2888           69 :               seq[new_i].second = sm_other;
    2889           69 :               seq[new_i].from = NULL_TREE;
    2890              :             }
    2891              :         }
    2892         2268 :       bitmap_and_compl_into (mem_refs, refs_not_supported);
    2893         2268 :       if (bitmap_empty_p (mem_refs))
    2894              :         return;
    2895              : 
    2896              :       /* Prune seq.  */
    2897         2584 :       while (seq.last ().second == sm_other
    2898         2584 :              && seq.last ().from == NULL_TREE)
    2899          368 :         seq.pop ();
    2900              : 
    2901         2216 :       hash_map<im_mem_ref *, sm_aux *> aux_map;
    2902              : 
    2903              :       /* Execute SM but delay the store materialization for ordered
    2904              :          sequences on exit.  Remember a created flag var and make
    2905              :          sure to re-use it.  */
    2906         2216 :       sm_aux *flag_var_aux = nullptr;
    2907         4900 :       EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
    2908              :         {
    2909         2684 :           ref = memory_accesses.refs_list[i];
    2910         2684 :           sm_aux *aux = execute_sm (loop, ref, aux_map, true,
    2911              :                                     flag_var_aux != nullptr);
    2912         2684 :           if (aux->store_flag)
    2913         1580 :             flag_var_aux = aux;
    2914              :         }
    2915              : 
    2916              :       /* Materialize ordered store sequences on exits.  */
    2917         2216 :       edge e;
    2918         2216 :       auto_bitmap clobbers_to_prune;
    2919         5994 :       FOR_EACH_VEC_ELT (exits, i, e)
    2920              :         {
    2921         3778 :           edge append_cond_position = NULL;
    2922         3778 :           edge last_cond_fallthru = NULL;
    2923         3778 :           edge insert_e = e;
    2924              :           /* Construct the single flag variable control flow and insert
    2925              :              the ordered seq of stores in the then block.  With
    2926              :              -fstore-data-races we can do the stores unconditionally.  */
    2927         3778 :           if (flag_var_aux)
    2928         2458 :             insert_e
    2929              :               = single_pred_edge
    2930         2458 :                   (execute_sm_if_changed (e, NULL_TREE, NULL_TREE,
    2931              :                                           flag_var_aux->store_flag,
    2932              :                                           loop_preheader_edge (loop),
    2933              :                                           &flag_var_aux->flag_bbs,
    2934              :                                           append_cond_position,
    2935              :                                           last_cond_fallthru));
    2936         3778 :           execute_sm_exit (loop, insert_e, seq, aux_map, sm_ord,
    2937              :                            append_cond_position, last_cond_fallthru,
    2938              :                            clobbers_to_prune);
    2939         3778 :           gsi_commit_one_edge_insert (insert_e, NULL);
    2940              :         }
    2941              : 
    2942              :       /* Remove clobbers inside the loop we re-materialized on exits.  */
    2943         2216 :       EXECUTE_IF_SET_IN_BITMAP (clobbers_to_prune, 0, i, bi)
    2944              :         {
    2945            0 :           gimple *stmt = memory_accesses.refs_list[i]->accesses_in_loop[0].stmt;
    2946            0 :           gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
    2947            0 :           unlink_stmt_vdef (stmt);
    2948            0 :           release_defs (stmt);
    2949            0 :           gimple_set_vdef (stmt, NULL_TREE);
    2950            0 :           gsi_remove (&gsi, true);
    2951              :         }
    2952              : 
    2953         4900 :       for (hash_map<im_mem_ref *, sm_aux *>::iterator iter = aux_map.begin ();
    2954         4900 :            iter != aux_map.end (); ++iter)
    2955         5368 :         delete (*iter).second;
    2956              : 
    2957         2216 :       return;
    2958         4484 :     }
    2959              : 
    2960              :   /* To address PR57359 before actually applying store-motion check
    2961              :      the candidates found for validity with regards to reordering
    2962              :      relative to other stores which we until here disambiguated using
    2963              :      TBAA which isn't valid.
    2964              :      What matters is the order of the last stores to the mem_refs
    2965              :      with respect to the other stores of the loop at the point of the
    2966              :      loop exits.  */
    2967              : 
    2968              :   /* For each exit compute the store order, pruning from mem_refs
    2969              :      on the fly.  */
    2970              :   /* The complexity of this is at least
    2971              :      O(number of exits * number of SM refs) but more approaching
    2972              :      O(number of exits * number of SM refs * number of stores).  */
    2973              :   /* ???  Somehow do this in a single sweep over the loop body.  */
    2974        19935 :   auto_vec<std::pair<edge, vec<seq_entry> > > sms;
    2975        19935 :   auto_bitmap refs_not_supported (&lim_bitmap_obstack);
    2976        19935 :   edge e;
    2977        40724 :   FOR_EACH_VEC_ELT (exits, i, e)
    2978              :     {
    2979        22702 :       vec<seq_entry> seq;
    2980        22702 :       seq.create (4);
    2981        22702 :       auto_bitmap refs_not_in_seq (&lim_bitmap_obstack);
    2982        22702 :       bitmap_and_compl (refs_not_in_seq, mem_refs, refs_not_supported);
    2983        22702 :       if (bitmap_empty_p (refs_not_in_seq))
    2984              :         {
    2985         1136 :           seq.release ();
    2986         1136 :           break;
    2987              :         }
    2988        21566 :       auto_bitmap fully_visited;
    2989        21566 :       int res = sm_seq_valid_bb (loop, e->src, NULL_TREE,
    2990              :                                  seq, refs_not_in_seq,
    2991              :                                  refs_not_supported, false,
    2992              :                                  fully_visited);
    2993        21566 :       if (res != 1)
    2994              :         {
    2995          777 :           bitmap_copy (refs_not_supported, mem_refs);
    2996          777 :           seq.release ();
    2997          777 :           break;
    2998              :         }
    2999        20789 :       sms.safe_push (std::make_pair (e, seq));
    3000        23479 :     }
    3001              : 
    3002              :   /* Prune pruned mem_refs from earlier processed exits.  */
    3003        19935 :   bool changed = !bitmap_empty_p (refs_not_supported);
    3004        19935 :   while (changed)
    3005              :     {
    3006         5784 :       changed = false;
    3007         5784 :       std::pair<edge, vec<seq_entry> > *seq;
    3008        40149 :       FOR_EACH_VEC_ELT (sms, i, seq)
    3009              :         {
    3010              :           bool need_to_push = false;
    3011        13357 :           for (unsigned i = 0; i < seq->second.length (); ++i)
    3012              :             {
    3013         6142 :               sm_kind kind = seq->second[i].second;
    3014         6142 :               if (kind == sm_other && seq->second[i].from == NULL_TREE)
    3015              :                 break;
    3016         5229 :               unsigned id = seq->second[i].first;
    3017         5229 :               unsigned new_idx;
    3018         5229 :               if (kind == sm_ord
    3019         5229 :                   && bitmap_bit_p (refs_not_supported, id))
    3020              :                 {
    3021         2649 :                   seq->second[i].second = sm_other;
    3022         2649 :                   gcc_assert (seq->second[i].from == NULL_TREE);
    3023              :                   need_to_push = true;
    3024              :                 }
    3025         2580 :               else if (need_to_push
    3026         2580 :                        && !sm_seq_push_down (seq->second, i, &new_idx))
    3027              :                 {
    3028              :                   /* We need to push down both sm_ord and sm_other
    3029              :                      but for the latter we need to disqualify all
    3030              :                      following refs.  */
    3031          113 :                   if (kind == sm_ord)
    3032              :                     {
    3033            7 :                       if (bitmap_set_bit (refs_not_supported, id))
    3034            7 :                         changed = true;
    3035            7 :                       seq->second[new_idx].second = sm_other;
    3036              :                     }
    3037              :                   else
    3038              :                     {
    3039          411 :                       for (unsigned j = seq->second.length () - 1;
    3040          305 :                            j > new_idx; --j)
    3041          199 :                         if (seq->second[j].second == sm_ord
    3042          321 :                             && bitmap_set_bit (refs_not_supported,
    3043          122 :                                                seq->second[j].first))
    3044              :                           changed = true;
    3045          106 :                       seq->second.truncate (new_idx);
    3046          106 :                       break;
    3047              :                     }
    3048              :                 }
    3049              :             }
    3050              :         }
    3051              :     }
    3052        19935 :   std::pair<edge, vec<seq_entry> > *seq;
    3053        61513 :   FOR_EACH_VEC_ELT (sms, i, seq)
    3054              :     {
    3055              :       /* Prune sm_other from the end.  */
    3056        66192 :       while (!seq->second.is_empty ()
    3057        45403 :              && seq->second.last ().second == sm_other)
    3058         5017 :         seq->second.pop ();
    3059              :       /* Prune duplicates from the start.  */
    3060        20789 :       auto_bitmap seen (&lim_bitmap_obstack);
    3061        20789 :       unsigned j, k;
    3062        49399 :       for (j = k = 0; j < seq->second.length (); ++j)
    3063        28610 :         if (bitmap_set_bit (seen, seq->second[j].first))
    3064              :           {
    3065        28501 :             if (k != j)
    3066           77 :               seq->second[k] = seq->second[j];
    3067        28501 :             ++k;
    3068              :           }
    3069        20789 :       seq->second.truncate (k);
    3070              :       /* And verify.  */
    3071        20789 :       seq_entry *e;
    3072        90868 :       FOR_EACH_VEC_ELT (seq->second, j, e)
    3073        28501 :         gcc_assert (e->second == sm_ord
    3074              :                     || (e->second == sm_other && e->from != NULL_TREE));
    3075        20789 :     }
    3076              : 
    3077              :   /* Verify dependence for refs we cannot handle with the order preserving
    3078              :      code (refs_not_supported) or prune them from mem_refs.  */
    3079        19935 :   auto_vec<seq_entry> unord_refs;
    3080        34774 :   EXECUTE_IF_SET_IN_BITMAP (refs_not_supported, 0, i, bi)
    3081              :     {
    3082        14839 :       ref = memory_accesses.refs_list[i];
    3083        14839 :       if (!ref_indep_loop_p (loop, ref, sm_waw))
    3084         6557 :         bitmap_clear_bit (mem_refs, i);
    3085              :       /* We've now verified store order for ref with respect to all other
    3086              :          stores in the loop does not matter.  */
    3087              :       else
    3088         8282 :         unord_refs.safe_push (seq_entry (i, sm_unord));
    3089              :     }
    3090              : 
    3091        19935 :   hash_map<im_mem_ref *, sm_aux *> aux_map;
    3092              : 
    3093              :   /* Execute SM but delay the store materialization for ordered
    3094              :      sequences on exit.  */
    3095        52608 :   EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
    3096              :     {
    3097        32673 :       ref = memory_accesses.refs_list[i];
    3098        32673 :       execute_sm (loop, ref, aux_map, bitmap_bit_p (refs_not_supported, i),
    3099              :                   false);
    3100              :     }
    3101              : 
    3102              :   /* Materialize ordered store sequences on exits.  */
    3103        19935 :   auto_bitmap clobbers_to_prune;
    3104        43765 :   FOR_EACH_VEC_ELT (exits, i, e)
    3105              :     {
    3106        23830 :       edge append_cond_position = NULL;
    3107        23830 :       edge last_cond_fallthru = NULL;
    3108        23830 :       if (i < sms.length ())
    3109              :         {
    3110        20789 :           gcc_assert (sms[i].first == e);
    3111        20789 :           execute_sm_exit (loop, e, sms[i].second, aux_map, sm_ord,
    3112              :                            append_cond_position, last_cond_fallthru,
    3113              :                            clobbers_to_prune);
    3114        20789 :           sms[i].second.release ();
    3115              :         }
    3116        23830 :       if (!unord_refs.is_empty ())
    3117         8437 :         execute_sm_exit (loop, e, unord_refs, aux_map, sm_unord,
    3118              :                          append_cond_position, last_cond_fallthru,
    3119              :                          clobbers_to_prune);
    3120              :       /* Commit edge inserts here to preserve the order of stores
    3121              :          when an exit exits multiple loops.  */
    3122        23830 :       gsi_commit_one_edge_insert (e, NULL);
    3123              :     }
    3124              : 
    3125              :   /* Remove clobbers inside the loop we re-materialized on exits.  */
    3126        20120 :   EXECUTE_IF_SET_IN_BITMAP (clobbers_to_prune, 0, i, bi)
    3127              :     {
    3128          185 :       gimple *stmt = memory_accesses.refs_list[i]->accesses_in_loop[0].stmt;
    3129          185 :       gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
    3130          185 :       unlink_stmt_vdef (stmt);
    3131          185 :       release_defs (stmt);
    3132          185 :       gimple_set_vdef (stmt, NULL_TREE);
    3133          185 :       gsi_remove (&gsi, true);
    3134              :     }
    3135              : 
    3136        52608 :   for (hash_map<im_mem_ref *, sm_aux *>::iterator iter = aux_map.begin ();
    3137        72543 :        iter != aux_map.end (); ++iter)
    3138        65346 :     delete (*iter).second;
    3139        19935 : }
    3140              : 
    3141              : class ref_always_stored
    3142              : {
    3143              : public:
    3144        93077 :   ref_always_stored (class loop *loop_)
    3145        93077 :       : loop (loop_) {}
    3146              :   bool operator () (mem_ref_loc *loc);
    3147              :   class loop *loop;
    3148              : };
    3149              : 
    3150              : bool
    3151       195464 : ref_always_stored::operator () (mem_ref_loc *loc)
    3152              : {
    3153              :   /* Make sure the statement is a store.  */
    3154       195464 :   tree lhs = gimple_get_lhs (loc->stmt);
    3155       195464 :   if (!lhs
    3156       195464 :       || !(DECL_P (lhs) || REFERENCE_CLASS_P (lhs)))
    3157              :     return false;
    3158              : 
    3159       117898 :   struct lim_aux_data *lim_data = get_lim_data (loc->stmt);
    3160       117898 :   if (!lim_data)
    3161              :     return false;
    3162              : 
    3163       117898 :   class loop *must_exec = lim_data->always_executed_in;
    3164       117898 :   if (!must_exec)
    3165              :     return false;
    3166              : 
    3167        38552 :   if (must_exec == loop
    3168        38552 :       || flow_loop_nested_p (must_exec, loop))
    3169        35219 :     return true;
    3170              : 
    3171              :   return false;
    3172              : }
    3173              : 
    3174              : /* Returns true if REF is always stored in LOOP.  */
    3175              : 
    3176              : static bool
    3177        93077 : ref_always_stored_p (class loop *loop, im_mem_ref *ref)
    3178              : {
    3179        93077 :   return for_all_locs_in_loop (loop, ref, ref_always_stored (loop));
    3180              : }
    3181              : 
    3182              : /* Returns true if LOAD_REF and STORE_REF form a "self write" pattern
    3183              :    where the stored value comes from the loaded value via SSA.
    3184              :    Example: a[i] = a[0] is safe to hoist a[0] even when i==0.  */
    3185              : 
    3186              : static bool
    3187       342587 : is_self_write (im_mem_ref *load_ref, im_mem_ref *store_ref)
    3188              : {
    3189              :   /* Only handle the simple case with a single access per ref.
    3190              :      Bail out on multiple accesses to be conservative.  */
    3191       342587 :   if (load_ref->accesses_in_loop.length () != 1
    3192       434243 :       || store_ref->accesses_in_loop.length () != 1)
    3193              :     return false;
    3194              : 
    3195        91673 :   gimple *load_stmt = load_ref->accesses_in_loop[0].stmt;
    3196        91673 :   gimple *store_stmt = store_ref->accesses_in_loop[0].stmt;
    3197              : 
    3198        91673 :   if (!is_gimple_assign (load_stmt) || !is_gimple_assign (store_stmt))
    3199              :     return false;
    3200              : 
    3201        91673 :   tree loaded_val = gimple_assign_lhs (load_stmt);
    3202        91673 :   tree stored_val = gimple_assign_rhs1 (store_stmt);
    3203              : 
    3204        91673 :   if (TREE_CODE (loaded_val) != SSA_NAME || TREE_CODE (stored_val) != SSA_NAME)
    3205              :     return false;
    3206              : 
    3207              :   /* Self write: stored value is the loaded value.  */
    3208        66452 :   if (stored_val != loaded_val)
    3209              :     return false;
    3210              : 
    3211              : 
    3212              :   /* TODO: Try to factor this out with mem_ref_hasher::equal
    3213              :      into im_compare_access_position_and_size
    3214              :      or a similar helper to centralize this delicate handling
    3215              :      complete for MEM_REF offsets and base pointer equality.
    3216              : 
    3217              :      TODO: Also ensure max_size_known_p agrees or resort to
    3218              :      alignment considerations to rule out partial overlaps.
    3219              : 
    3220              :      See:
    3221              :      https://gcc.gnu.org/pipermail/gcc-patches/2025-December/704155.html
    3222              :      For more context on TODOs above.  */
    3223              : 
    3224              :   /* They may alias.  Verify exact same location.  */
    3225         1735 :   return (operand_equal_p (load_ref->mem.base, store_ref->mem.base, 0)
    3226           46 :           && known_eq (load_ref->mem.size, store_ref->mem.size)
    3227         1781 :           && known_eq (load_ref->mem.offset, store_ref->mem.offset));
    3228              : 
    3229              : }
    3230              : 
    3231              : /* Returns true if REF1 and REF2 are independent.  */
    3232              : 
    3233              : static bool
    3234       623764 : refs_independent_p (im_mem_ref *ref1, im_mem_ref *ref2, bool tbaa_p)
    3235              : {
    3236       623764 :   if (ref1 == ref2)
    3237              :     return true;
    3238              : 
    3239       564022 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3240         3043 :     fprintf (dump_file, "Querying dependency of refs %u and %u: ",
    3241         3043 :              ref1->id, ref2->id);
    3242              : 
    3243       564022 :   if (mem_refs_may_alias_p (ref1, ref2, &memory_accesses.ttae_cache, tbaa_p))
    3244              :     {
    3245        66874 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3246           96 :         fprintf (dump_file, "dependent.\n");
    3247              :       return false;
    3248              :     }
    3249              :   else
    3250              :     {
    3251       497148 :       if (dump_file && (dump_flags & TDF_DETAILS))
    3252         2947 :         fprintf (dump_file, "independent.\n");
    3253              :       return true;
    3254              :     }
    3255              : }
    3256              : 
    3257              : /* Returns true if REF is independent on all other accessess in LOOP.
    3258              :    KIND specifies the kind of dependence to consider.
    3259              :      lim_raw assumes REF is not stored in LOOP and disambiguates RAW
    3260              :              dependences so if true REF can be hoisted out of LOOP
    3261              :      sm_war disambiguates a store REF against all other loads to see
    3262              :             whether the store can be sunk across loads out of LOOP
    3263              :      sm_waw disambiguates a store REF against all other stores to see
    3264              :             whether the store can be sunk across stores out of LOOP.  */
    3265              : 
    3266              : static bool
    3267      2127983 : ref_indep_loop_p (class loop *loop, im_mem_ref *ref, dep_kind kind)
    3268              : {
    3269      2127983 :   bool indep_p = true;
    3270      2127983 :   bitmap refs_to_check;
    3271              : 
    3272      2127983 :   if (kind == sm_war)
    3273       990269 :     refs_to_check = &memory_accesses.refs_loaded_in_loop[loop->num];
    3274              :   else
    3275      1137714 :     refs_to_check = &memory_accesses.refs_stored_in_loop[loop->num];
    3276              : 
    3277      2127983 :   if (bitmap_bit_p (refs_to_check, UNANALYZABLE_MEM_ID)
    3278      2127983 :       || ref->mem.ref == error_mark_node)
    3279              :     indep_p = false;
    3280              :   else
    3281              :     {
    3282              :       /* tri-state, { unknown, independent, dependent }  */
    3283       691293 :       dep_state state = query_loop_dependence (loop, ref, kind);
    3284       691293 :       if (state != dep_unknown)
    3285            0 :         return state == dep_independent;
    3286              : 
    3287       691293 :       class loop *inner = loop->inner;
    3288       861555 :       while (inner)
    3289              :         {
    3290       475990 :           if (!ref_indep_loop_p (inner, ref, kind))
    3291              :             {
    3292              :               indep_p = false;
    3293              :               break;
    3294              :             }
    3295       170262 :           inner = inner->next;
    3296              :         }
    3297              : 
    3298       691293 :       if (indep_p)
    3299              :         {
    3300       385565 :           unsigned i;
    3301       385565 :           bitmap_iterator bi;
    3302       963820 :           EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
    3303              :             {
    3304       649429 :               im_mem_ref *aref = memory_accesses.refs_list[i];
    3305       649429 :               if (aref->mem.ref == error_mark_node)
    3306              :                 {
    3307        26441 :                   gimple *stmt = aref->accesses_in_loop[0].stmt;
    3308        26441 :                   if ((kind == sm_war
    3309         9528 :                        && ref_maybe_used_by_stmt_p (stmt, &ref->mem,
    3310              :                                                     kind != sm_waw))
    3311        35345 :                       || stmt_may_clobber_ref_p_1 (stmt, &ref->mem,
    3312              :                                                    kind != sm_waw))
    3313              :                     {
    3314              :                       indep_p = false;
    3315              :                       break;
    3316              :                     }
    3317              :                 }
    3318              :               /* For hoisting loads (lim_raw), allow "self write": the store
    3319              :                  writes back the loaded value.  Example: a[i] = a[0]
    3320              :                  is safe even when i==0 causes aliasing.  */
    3321       622988 :               else if (kind == lim_raw
    3322       342587 :                        && ref->loaded && aref->stored
    3323       965575 :                        && is_self_write (ref, aref))
    3324              :                 {
    3325           17 :                   if (dump_file && (dump_flags & TDF_DETAILS))
    3326            2 :                     fprintf (dump_file,
    3327              :                              "Dependency of refs %u and %u: "
    3328              :                              "independent (self write).\n",
    3329            2 :                              ref->id, aref->id);
    3330              :                 }
    3331              : 
    3332       622971 :               else if (!refs_independent_p (ref, aref, kind != sm_waw))
    3333              :                 {
    3334              :                   indep_p = false;
    3335              :                   break;
    3336              :                 }
    3337              :             }
    3338              :         }
    3339              :     }
    3340              : 
    3341      2127983 :   if (dump_file && (dump_flags & TDF_DETAILS))
    3342          769 :     fprintf (dump_file, "Querying %s dependencies of ref %u in loop %d: %s\n",
    3343              :              kind == lim_raw ? "RAW" : (kind == sm_war ? "SM WAR" : "SM WAW"),
    3344          374 :              ref->id, loop->num, indep_p ? "independent" : "dependent");
    3345              : 
    3346              :   /* Record the computed result in the cache.  */
    3347      2127983 :   record_loop_dependence (loop, ref, kind,
    3348              :                           indep_p ? dep_independent : dep_dependent);
    3349              : 
    3350      2127983 :   return indep_p;
    3351              : }
    3352              : 
    3353              : class ref_in_loop_hot_body
    3354              : {
    3355              : public:
    3356        43009 :   ref_in_loop_hot_body (class loop *loop_) : l (loop_) {}
    3357              :   bool operator () (mem_ref_loc *loc);
    3358              :   class loop *l;
    3359              : };
    3360              : 
    3361              : /* Check the coldest loop between loop L and innermost loop.  If there is one
    3362              :    cold loop between L and INNER_LOOP, store motion can be performed, otherwise
    3363              :    no cold loop means no store motion.  get_coldest_out_loop also handles cases
    3364              :    when l is inner_loop.  */
    3365              : bool
    3366        43726 : ref_in_loop_hot_body::operator () (mem_ref_loc *loc)
    3367              : {
    3368        43726 :   basic_block curr_bb = gimple_bb (loc->stmt);
    3369        43726 :   class loop *inner_loop = curr_bb->loop_father;
    3370        43726 :   return get_coldest_out_loop (l, inner_loop, curr_bb);
    3371              : }
    3372              : 
    3373              : 
    3374              : /* Returns true if we can perform store motion of REF from LOOP.  */
    3375              : 
    3376              : static bool
    3377      3075446 : can_sm_ref_p (class loop *loop, im_mem_ref *ref)
    3378              : {
    3379      3075446 :   bool store_could_trap;
    3380              : 
    3381              :   /* Can't hoist unanalyzable refs.  */
    3382      3075446 :   if (!MEM_ANALYZABLE (ref))
    3383              :     return false;
    3384              : 
    3385              :   /* Can't hoist/sink aggregate copies.  */
    3386      2712247 :   if (ref->mem.ref == error_mark_node)
    3387              :     return false;
    3388              : 
    3389              :   /* It should be movable.  */
    3390      2268355 :   if (!is_gimple_reg_type (TREE_TYPE (ref->mem.ref))
    3391      2268069 :       || TREE_THIS_VOLATILE (ref->mem.ref)
    3392      4400328 :       || !for_each_index (&ref->mem.ref, may_move_till, loop))
    3393              :     return false;
    3394              : 
    3395       970970 :   store_could_trap = lhs_could_trap_p (ref->mem.ref);
    3396              : 
    3397              :   /* Do not move a load or store that can throw.  Store motion does not
    3398              :      update EH information.  */
    3399       970970 :   if (tree_could_throw_p (ref->mem.ref)
    3400       970970 :       || (flag_exceptions
    3401       690261 :           && cfun->can_throw_non_call_exceptions
    3402       541698 :           && store_could_trap))
    3403              :     return false;
    3404              : 
    3405              :   /* If a store can trap, it must be always executed in LOOP.  */
    3406       947583 :   if (store_could_trap
    3407              :       /* ???  We can at least use false here, allowing loads?  We
    3408              :          are forcing conditional stores if the ref is not always
    3409              :          stored to later anyway.  So this would only guard
    3410              :          the load we need to emit.  Thus when the ref is not
    3411              :          loaded we can elide this completely?  */
    3412      1005303 :       && !ref_always_stored_p (loop, ref))
    3413              :     return false;
    3414              : 
    3415              :   /* Verify all loads of ref can be hoisted.  */
    3416       900805 :   if (ref->loaded
    3417        94594 :       && bitmap_bit_p (ref->loaded, loop->num)
    3418       990102 :       && !ref_indep_loop_p (loop, ref, lim_raw))
    3419              :     return false;
    3420              : 
    3421              :   /* Verify the candidate can be disambiguated against all loads,
    3422              :      that is, we can elide all in-loop stores.  Disambiguation
    3423              :      against stores is done later when we cannot guarantee preserving
    3424              :      the order of stores.  */
    3425       834922 :   if (!ref_indep_loop_p (loop, ref, sm_war))
    3426              :     return false;
    3427              : 
    3428              :   /* Verify whether the candidate is hot for LOOP.  Only do store motion if the
    3429              :     candidate's profile count is hot.  Statement in cold BB shouldn't be moved
    3430              :     out of it's loop_father.  */
    3431        43009 :   if (!for_all_locs_in_loop (loop, ref, ref_in_loop_hot_body (loop)))
    3432              :     return false;
    3433              : 
    3434              :   return true;
    3435              : }
    3436              : 
    3437              : /* Marks the references in LOOP for that store motion should be performed
    3438              :    in REFS_TO_SM.  SM_EXECUTED is the set of references for that store
    3439              :    motion was performed in one of the outer loops.  */
    3440              : 
    3441              : static void
    3442      1305279 : find_refs_for_sm (class loop *loop, bitmap sm_executed, bitmap refs_to_sm)
    3443              : {
    3444      1305279 :   bitmap refs = &memory_accesses.all_refs_stored_in_loop[loop->num];
    3445      1305279 :   unsigned i;
    3446      1305279 :   bitmap_iterator bi;
    3447      1305279 :   im_mem_ref *ref;
    3448              : 
    3449      4380725 :   EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
    3450              :     {
    3451      3075446 :       ref = memory_accesses.refs_list[i];
    3452      3075446 :       if (can_sm_ref_p (loop, ref) && dbg_cnt (lim))
    3453        41985 :         bitmap_set_bit (refs_to_sm, i);
    3454              :     }
    3455      1305279 : }
    3456              : 
    3457              : /* Checks whether LOOP (with exits stored in EXITS array) is suitable
    3458              :    for a store motion optimization (i.e. whether we can insert statement
    3459              :    on its exits).  */
    3460              : 
    3461              : static bool
    3462      1349405 : loop_suitable_for_sm (class loop *loop ATTRIBUTE_UNUSED,
    3463              :                       const vec<edge> &exits)
    3464              : {
    3465      1349405 :   unsigned i;
    3466      1349405 :   edge ex;
    3467              : 
    3468      3490087 :   FOR_EACH_VEC_ELT (exits, i, ex)
    3469      2184808 :     if (ex->flags & (EDGE_ABNORMAL | EDGE_EH))
    3470              :       return false;
    3471              : 
    3472              :   return true;
    3473              : }
    3474              : 
    3475              : /* Try to perform store motion for all memory references modified inside
    3476              :    LOOP.  SM_EXECUTED is the bitmap of the memory references for that
    3477              :    store motion was executed in one of the outer loops.  */
    3478              : 
    3479              : static void
    3480      1349405 : store_motion_loop (class loop *loop, bitmap sm_executed)
    3481              : {
    3482      1349405 :   auto_vec<edge> exits = get_loop_exit_edges (loop);
    3483      1349405 :   class loop *subloop;
    3484      1349405 :   bitmap sm_in_loop = BITMAP_ALLOC (&lim_bitmap_obstack);
    3485              : 
    3486      1349405 :   if (loop_suitable_for_sm (loop, exits))
    3487              :     {
    3488      1305279 :       find_refs_for_sm (loop, sm_executed, sm_in_loop);
    3489      1305279 :       if (!bitmap_empty_p (sm_in_loop))
    3490        22203 :         hoist_memory_references (loop, sm_in_loop, exits);
    3491              :     }
    3492              : 
    3493      1349405 :   bitmap_ior_into (sm_executed, sm_in_loop);
    3494      1657836 :   for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
    3495       308431 :     store_motion_loop (subloop, sm_executed);
    3496      1349405 :   bitmap_and_compl_into (sm_executed, sm_in_loop);
    3497      1349405 :   BITMAP_FREE (sm_in_loop);
    3498      1349405 : }
    3499              : 
    3500              : /* Try to perform store motion for all memory references modified inside
    3501              :    loops.  */
    3502              : 
    3503              : static void
    3504       498289 : do_store_motion (void)
    3505              : {
    3506       498289 :   class loop *loop;
    3507       498289 :   bitmap sm_executed = BITMAP_ALLOC (&lim_bitmap_obstack);
    3508              : 
    3509      1539263 :   for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
    3510      1040974 :     store_motion_loop (loop, sm_executed);
    3511              : 
    3512       498289 :   BITMAP_FREE (sm_executed);
    3513       498289 : }
    3514              : 
    3515              : /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
    3516              :    for each such basic block bb records the outermost loop for that execution
    3517              :    of its header implies execution of bb.  CONTAINS_CALL is the bitmap of
    3518              :    blocks that contain a nonpure call.  */
    3519              : 
    3520              : static void
    3521      1356844 : fill_always_executed_in_1 (class loop *loop, sbitmap contains_call)
    3522              : {
    3523      1356844 :   basic_block bb = NULL, last = NULL;
    3524      1356844 :   edge e;
    3525      1356844 :   class loop *inn_loop = loop;
    3526              : 
    3527      1667673 :   for (class loop *inner = loop->inner; inner; inner = inner->next)
    3528       310829 :     fill_always_executed_in_1 (inner, contains_call);
    3529              : 
    3530      1356844 :   auto_vec<basic_block, 64> worklist;
    3531      1356844 :   worklist.reserve_exact (loop->num_nodes);
    3532      1356844 :   worklist.quick_push (loop->header);
    3533      3042795 :   do
    3534              :     {
    3535      3042795 :       edge_iterator ei;
    3536      3042795 :       bb = worklist.pop ();
    3537              : 
    3538      3042795 :       if (!flow_bb_inside_loop_p (inn_loop, bb))
    3539              :         {
    3540              :           /* When we are leaving a possibly infinite inner loop
    3541              :              we have to stop processing.  */
    3542       189496 :           if (!finite_loop_p (inn_loop))
    3543              :             break;
    3544              :           /* If the loop was finite we can continue with processing
    3545              :              the loop we exited to.  */
    3546       180191 :           inn_loop = bb->loop_father;
    3547              :         }
    3548              : 
    3549      3033490 :       if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
    3550      1752572 :         last = bb;
    3551              : 
    3552      3033490 :       if (bitmap_bit_p (contains_call, bb->index))
    3553              :         break;
    3554              : 
    3555              :       /* If LOOP exits from this BB stop processing.  */
    3556      5876434 :       FOR_EACH_EDGE (e, ei, bb->succs)
    3557      4179642 :         if (!flow_bb_inside_loop_p (loop, e->dest))
    3558              :           break;
    3559      2691284 :       if (e)
    3560              :         break;
    3561              : 
    3562              :       /* A loop might be infinite (TODO use simple loop analysis
    3563              :          to disprove this if possible).  */
    3564      1696792 :       if (bb->flags & BB_IRREDUCIBLE_LOOP)
    3565              :         break;
    3566              : 
    3567      1696664 :       if (bb->loop_father->header == bb)
    3568              :         /* Record that we enter into a subloop since it might not
    3569              :            be finite.  */
    3570              :         /* ???  Entering into a not always executed subloop makes
    3571              :            fill_always_executed_in quadratic in loop depth since
    3572              :            we walk those loops N times.  This is not a problem
    3573              :            in practice though, see PR102253 for a worst-case testcase.  */
    3574       633356 :         inn_loop = bb->loop_father;
    3575              : 
    3576              :       /* Walk the body of LOOP sorted by dominance relation.  Additionally,
    3577              :          if a basic block S dominates the latch, then only blocks dominated
    3578              :          by S are after it.
    3579              :          This is get_loop_body_in_dom_order using a worklist algorithm and
    3580              :          stopping once we are no longer interested in visiting further
    3581              :          blocks.  */
    3582      1696664 :       unsigned old_len = worklist.length ();
    3583      1696664 :       unsigned postpone = 0;
    3584      1696664 :       for (basic_block son = first_dom_son (CDI_DOMINATORS, bb);
    3585      3674545 :            son;
    3586      1977881 :            son = next_dom_son (CDI_DOMINATORS, son))
    3587              :         {
    3588      1977881 :           if (!flow_bb_inside_loop_p (loop, son))
    3589        22009 :             continue;
    3590      1955872 :           if (dominated_by_p (CDI_DOMINATORS, loop->latch, son))
    3591       540960 :             postpone = worklist.length ();
    3592      1955872 :           worklist.quick_push (son);
    3593              :         }
    3594      1696664 :       if (postpone)
    3595              :         /* Postponing the block that dominates the latch means
    3596              :            processing it last and thus putting it earliest in the
    3597              :            worklist.  */
    3598        87633 :         std::swap (worklist[old_len], worklist[postpone]);
    3599              :     }
    3600      3393328 :   while (!worklist.is_empty ());
    3601              : 
    3602      2148300 :   while (1)
    3603              :     {
    3604      1752572 :       if (last->loop_father == loop
    3605      1752572 :           || (ALWAYS_EXECUTED_IN (last)
    3606       161595 :               && loop_outer (ALWAYS_EXECUTED_IN (last)) == loop))
    3607              :         {
    3608      1751896 :           if (dump_enabled_p ())
    3609         2477 :             dump_printf (MSG_NOTE, "BB %d is always executed in loop %d\n",
    3610              :                          last->index, loop->num);
    3611      1751896 :           SET_ALWAYS_EXECUTED_IN (last, loop);
    3612              :         }
    3613      1752572 :       if (last == loop->header)
    3614              :         break;
    3615       395728 :       last = get_immediate_dominator (CDI_DOMINATORS, last);
    3616              :     }
    3617      1356844 : }
    3618              : 
    3619              : /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
    3620              :    for each such basic block bb records the outermost loop for that execution
    3621              :    of its header implies execution of bb.  */
    3622              : 
    3623              : static void
    3624       499822 : fill_always_executed_in (void)
    3625              : {
    3626       499822 :   basic_block bb;
    3627       499822 :   class loop *loop;
    3628              : 
    3629       499822 :   auto_sbitmap contains_call (last_basic_block_for_fn (cfun));
    3630       499822 :   bitmap_clear (contains_call);
    3631     15283973 :   FOR_EACH_BB_FN (bb, cfun)
    3632              :     {
    3633     14784151 :       if (loop_depth (bb->loop_father) == 0)
    3634              :         {
    3635              :           /* Outside of loops we can skip scanning all stmts.  */
    3636      8550324 :           bitmap_set_bit (contains_call, bb->index);
    3637      8550324 :           continue;
    3638              :         }
    3639      6233827 :       gimple_stmt_iterator gsi;
    3640     53521796 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    3641              :         {
    3642     43147493 :           if (nonpure_call_p (gsi_stmt (gsi)))
    3643              :             break;
    3644              :         }
    3645              : 
    3646      6233827 :       if (!gsi_end_p (gsi))
    3647       985780 :         bitmap_set_bit (contains_call, bb->index);
    3648              :     }
    3649              : 
    3650      1545837 :   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
    3651      1046015 :     fill_always_executed_in_1 (loop, contains_call);
    3652       499822 : }
    3653              : 
    3654              : /* Find the coldest loop preheader for LOOP, also find the nearest hotter loop
    3655              :    to LOOP.  Then recursively iterate each inner loop.  */
    3656              : 
    3657              : void
    3658      1356844 : fill_coldest_and_hotter_out_loop (class loop *coldest_loop,
    3659              :                                   class loop *hotter_loop, class loop *loop)
    3660              : {
    3661      1356844 :   if (bb_colder_than_loop_preheader (loop_preheader_edge (loop)->src,
    3662              :                                      coldest_loop))
    3663        29195 :     coldest_loop = loop;
    3664              : 
    3665      1356844 :   coldest_outermost_loop[loop->num] = coldest_loop;
    3666              : 
    3667      1356844 :   hotter_than_inner_loop[loop->num] = NULL;
    3668      1356844 :   class loop *outer_loop = loop_outer (loop);
    3669      1356844 :   if (hotter_loop
    3670      1356844 :       && bb_colder_than_loop_preheader (loop_preheader_edge (loop)->src,
    3671              :                                         hotter_loop))
    3672         2584 :     hotter_than_inner_loop[loop->num] = hotter_loop;
    3673              : 
    3674      1356844 :   if (outer_loop && outer_loop != current_loops->tree_root
    3675      1667673 :       && bb_colder_than_loop_preheader (loop_preheader_edge (loop)->src,
    3676              :                                         outer_loop))
    3677        35618 :     hotter_than_inner_loop[loop->num] = outer_loop;
    3678              : 
    3679      1356844 :   if (dump_enabled_p ())
    3680              :     {
    3681         1948 :       dump_printf (MSG_NOTE, "loop %d's coldest_outermost_loop is %d, ",
    3682              :                    loop->num, coldest_loop->num);
    3683         1948 :       if (hotter_than_inner_loop[loop->num])
    3684          319 :         dump_printf (MSG_NOTE, "hotter_than_inner_loop is %d\n",
    3685          319 :                      hotter_than_inner_loop[loop->num]->num);
    3686              :       else
    3687         1629 :         dump_printf (MSG_NOTE, "hotter_than_inner_loop is NULL\n");
    3688              :     }
    3689              : 
    3690      1356844 :   class loop *inner_loop;
    3691      1667673 :   for (inner_loop = loop->inner; inner_loop; inner_loop = inner_loop->next)
    3692       621658 :     fill_coldest_and_hotter_out_loop (coldest_loop,
    3693       310829 :                                       hotter_than_inner_loop[loop->num],
    3694              :                                       inner_loop);
    3695      1356844 : }
    3696              : 
    3697              : /* Compute the global information needed by the loop invariant motion pass.  */
    3698              : 
    3699              : static void
    3700       499822 : tree_ssa_lim_initialize (bool store_motion)
    3701              : {
    3702       499822 :   unsigned i;
    3703              : 
    3704       499822 :   bitmap_obstack_initialize (&lim_bitmap_obstack);
    3705       499822 :   gcc_obstack_init (&mem_ref_obstack);
    3706       499822 :   lim_aux_data_map = new hash_map<gimple *, lim_aux_data *>;
    3707              : 
    3708       499822 :   if (flag_tm)
    3709          104 :     compute_transaction_bits ();
    3710              : 
    3711       499822 :   memory_accesses.refs = new hash_table<mem_ref_hasher> (100);
    3712       499822 :   memory_accesses.refs_list.create (100);
    3713              :   /* Allocate a special, unanalyzable mem-ref with ID zero.  */
    3714       499822 :   memory_accesses.refs_list.quick_push
    3715       499822 :     (mem_ref_alloc (NULL, 0, UNANALYZABLE_MEM_ID));
    3716              : 
    3717       999644 :   memory_accesses.refs_loaded_in_loop.create (number_of_loops (cfun));
    3718       999644 :   memory_accesses.refs_loaded_in_loop.quick_grow_cleared (number_of_loops (cfun));
    3719       999644 :   memory_accesses.refs_stored_in_loop.create (number_of_loops (cfun));
    3720       999644 :   memory_accesses.refs_stored_in_loop.quick_grow_cleared (number_of_loops (cfun));
    3721       499822 :   if (store_motion)
    3722              :     {
    3723       996578 :       memory_accesses.all_refs_stored_in_loop.create (number_of_loops (cfun));
    3724       498289 :       memory_accesses.all_refs_stored_in_loop.quick_grow_cleared
    3725       996578 :                                                       (number_of_loops (cfun));
    3726              :     }
    3727              : 
    3728      6203134 :   for (i = 0; i < number_of_loops (cfun); i++)
    3729              :     {
    3730      2601745 :       bitmap_initialize (&memory_accesses.refs_loaded_in_loop[i],
    3731              :                          &lim_bitmap_obstack);
    3732      2601745 :       bitmap_initialize (&memory_accesses.refs_stored_in_loop[i],
    3733              :                          &lim_bitmap_obstack);
    3734      2601745 :       if (store_motion)
    3735      2589251 :         bitmap_initialize (&memory_accesses.all_refs_stored_in_loop[i],
    3736              :                            &lim_bitmap_obstack);
    3737              :     }
    3738              : 
    3739       499822 :   memory_accesses.ttae_cache = NULL;
    3740              : 
    3741              :   /* Initialize bb_loop_postorder with a mapping from loop->num to
    3742              :      its postorder index.  */
    3743       499822 :   i = 0;
    3744       999644 :   bb_loop_postorder = XNEWVEC (unsigned, number_of_loops (cfun));
    3745      2856310 :   for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
    3746      1356844 :     bb_loop_postorder[loop->num] = i++;
    3747       499822 : }
    3748              : 
    3749              : /* Cleans up after the invariant motion pass.  */
    3750              : 
    3751              : static void
    3752       499822 : tree_ssa_lim_finalize (void)
    3753              : {
    3754       499822 :   basic_block bb;
    3755       499822 :   unsigned i;
    3756       499822 :   im_mem_ref *ref;
    3757              : 
    3758     15324452 :   FOR_EACH_BB_FN (bb, cfun)
    3759     14824630 :     SET_ALWAYS_EXECUTED_IN (bb, NULL);
    3760              : 
    3761       499822 :   bitmap_obstack_release (&lim_bitmap_obstack);
    3762       999644 :   delete lim_aux_data_map;
    3763              : 
    3764       499822 :   delete memory_accesses.refs;
    3765       499822 :   memory_accesses.refs = NULL;
    3766              : 
    3767      6024968 :   FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
    3768      5525146 :     memref_free (ref);
    3769       499822 :   memory_accesses.refs_list.release ();
    3770       499822 :   obstack_free (&mem_ref_obstack, NULL);
    3771              : 
    3772       499822 :   memory_accesses.refs_loaded_in_loop.release ();
    3773       499822 :   memory_accesses.refs_stored_in_loop.release ();
    3774       499822 :   memory_accesses.all_refs_stored_in_loop.release ();
    3775              : 
    3776       499822 :   if (memory_accesses.ttae_cache)
    3777         4959 :     free_affine_expand_cache (&memory_accesses.ttae_cache);
    3778              : 
    3779       499822 :   free (bb_loop_postorder);
    3780              : 
    3781       499822 :   coldest_outermost_loop.release ();
    3782       499822 :   hotter_than_inner_loop.release ();
    3783       499822 : }
    3784              : 
    3785              : /* Moves invariants from loops.  Only "expensive" invariants are moved out --
    3786              :    i.e. those that are likely to be win regardless of the register pressure.
    3787              :    Only perform store motion if STORE_MOTION is true.  */
    3788              : 
    3789              : unsigned int
    3790       499822 : loop_invariant_motion_in_fun (function *fun, bool store_motion)
    3791              : {
    3792       499822 :   unsigned int todo = 0;
    3793              : 
    3794       499822 :   tree_ssa_lim_initialize (store_motion);
    3795              : 
    3796       499822 :   mark_ssa_maybe_undefs ();
    3797              : 
    3798              :   /* Gathers information about memory accesses in the loops.  */
    3799       499822 :   analyze_memory_references (store_motion);
    3800              : 
    3801              :   /* Fills ALWAYS_EXECUTED_IN information for basic blocks.  */
    3802       499822 :   fill_always_executed_in ();
    3803              : 
    3804              :   /* Pre-compute coldest outermost loop and nearest hotter loop of each loop.
    3805              :    */
    3806       499822 :   class loop *loop;
    3807       999644 :   coldest_outermost_loop.create (number_of_loops (cfun));
    3808       999644 :   coldest_outermost_loop.safe_grow_cleared (number_of_loops (cfun));
    3809       999644 :   hotter_than_inner_loop.create (number_of_loops (cfun));
    3810       999644 :   hotter_than_inner_loop.safe_grow_cleared (number_of_loops (cfun));
    3811      1545837 :   for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
    3812      1046015 :     fill_coldest_and_hotter_out_loop (loop, NULL, loop);
    3813              : 
    3814       499822 :   int *rpo = XNEWVEC (int, last_basic_block_for_fn (fun));
    3815       499822 :   int n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
    3816              : 
    3817              :   /* For each statement determine the outermost loop in that it is
    3818              :      invariant and cost for computing the invariant.  */
    3819     15783795 :   for (int i = 0; i < n; ++i)
    3820     14784151 :     compute_invariantness (BASIC_BLOCK_FOR_FN (fun, rpo[i]));
    3821              : 
    3822              :   /* Execute store motion.  Force the necessary invariants to be moved
    3823              :      out of the loops as well.  */
    3824       499822 :   if (store_motion)
    3825       498289 :     do_store_motion ();
    3826              : 
    3827       499822 :   free (rpo);
    3828       499822 :   rpo = XNEWVEC (int, last_basic_block_for_fn (fun));
    3829       499822 :   n = pre_and_rev_post_order_compute_fn (fun, NULL, rpo, false);
    3830              : 
    3831              :   /* Move the expressions that are expensive enough.  */
    3832     15824274 :   for (int i = 0; i < n; ++i)
    3833     14824630 :     todo |= move_computations_worker (BASIC_BLOCK_FOR_FN (fun, rpo[i]));
    3834              : 
    3835       499822 :   free (rpo);
    3836              : 
    3837       499822 :   gsi_commit_edge_inserts ();
    3838       499822 :   if (need_ssa_update_p (fun))
    3839        15133 :     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
    3840              : 
    3841       499822 :   tree_ssa_lim_finalize ();
    3842              : 
    3843       499822 :   return todo;
    3844              : }
    3845              : 
    3846              : /* Loop invariant motion pass.  */
    3847              : 
    3848              : namespace {
    3849              : 
    3850              : const pass_data pass_data_lim =
    3851              : {
    3852              :   GIMPLE_PASS, /* type */
    3853              :   "lim", /* name */
    3854              :   OPTGROUP_LOOP, /* optinfo_flags */
    3855              :   TV_LIM, /* tv_id */
    3856              :   PROP_cfg, /* properties_required */
    3857              :   0, /* properties_provided */
    3858              :   0, /* properties_destroyed */
    3859              :   0, /* todo_flags_start */
    3860              :   0, /* todo_flags_finish */
    3861              : };
    3862              : 
    3863              : class pass_lim : public gimple_opt_pass
    3864              : {
    3865              : public:
    3866      1188720 :   pass_lim (gcc::context *ctxt)
    3867      2377440 :     : gimple_opt_pass (pass_data_lim, ctxt)
    3868              :   {}
    3869              : 
    3870              :   /* opt_pass methods: */
    3871       891540 :   opt_pass * clone () final override { return new pass_lim (m_ctxt); }
    3872      1313140 :   bool gate (function *) final override { return flag_tree_loop_im != 0; }
    3873              :   unsigned int execute (function *) final override;
    3874              : 
    3875              : }; // class pass_lim
    3876              : 
    3877              : unsigned int
    3878      1312760 : pass_lim::execute (function *fun)
    3879              : {
    3880      1312760 :   in_loop_pipeline = scev_initialized_p ();
    3881      1312760 :   if (!in_loop_pipeline)
    3882      1063816 :     loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
    3883              : 
    3884      2625520 :   if (number_of_loops (fun) <= 1)
    3885              :     return 0;
    3886       498323 :   unsigned int todo = loop_invariant_motion_in_fun (fun, flag_move_loop_stores);
    3887              : 
    3888       498323 :   if (!in_loop_pipeline)
    3889       249379 :     loop_optimizer_finalize ();
    3890              :   else
    3891       248944 :     scev_reset ();
    3892              :   return todo;
    3893              : }
    3894              : 
    3895              : } // anon namespace
    3896              : 
    3897              : gimple_opt_pass *
    3898       297180 : make_pass_lim (gcc::context *ctxt)
    3899              : {
    3900       297180 :   return new pass_lim (ctxt);
    3901              : }
    3902              : 
        

Generated by: LCOV version 2.5.0-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.