LCOV - code coverage report
Current view: top level - gcc - tree-ssa-loop-im.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1138 1147 99.2 %
Date: 2020-04-04 11:58:09 Functions: 61 68 89.7 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Loop invariant motion.
       2                 :            :    Copyright (C) 2003-2020 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 "gimplify.h"
      34                 :            : #include "gimple-iterator.h"
      35                 :            : #include "tree-cfg.h"
      36                 :            : #include "tree-ssa-loop-manip.h"
      37                 :            : #include "tree-ssa-loop.h"
      38                 :            : #include "tree-into-ssa.h"
      39                 :            : #include "cfgloop.h"
      40                 :            : #include "domwalk.h"
      41                 :            : #include "tree-affine.h"
      42                 :            : #include "tree-ssa-propagate.h"
      43                 :            : #include "trans-mem.h"
      44                 :            : #include "gimple-fold.h"
      45                 :            : #include "tree-scalar-evolution.h"
      46                 :            : #include "tree-ssa-loop-niter.h"
      47                 :            : #include "alias.h"
      48                 :            : #include "builtins.h"
      49                 :            : #include "tree-dfa.h"
      50                 :            : 
      51                 :            : /* TODO:  Support for predicated code motion.  I.e.
      52                 :            : 
      53                 :            :    while (1)
      54                 :            :      {
      55                 :            :        if (cond)
      56                 :            :          {
      57                 :            :            a = inv;
      58                 :            :            something;
      59                 :            :          }
      60                 :            :      }
      61                 :            : 
      62                 :            :    Where COND and INV are invariants, but evaluating INV may trap or be
      63                 :            :    invalid from some other reason if !COND.  This may be transformed to
      64                 :            : 
      65                 :            :    if (cond)
      66                 :            :      a = inv;
      67                 :            :    while (1)
      68                 :            :      {
      69                 :            :        if (cond)
      70                 :            :          something;
      71                 :            :      }  */
      72                 :            : 
      73                 :            : /* The auxiliary data kept for each statement.  */
      74                 :            : 
      75                 :            : struct lim_aux_data
      76                 :            : {
      77                 :            :   class loop *max_loop; /* The outermost loop in that the statement
      78                 :            :                                    is invariant.  */
      79                 :            : 
      80                 :            :   class loop *tgt_loop; /* The loop out of that we want to move the
      81                 :            :                                    invariant.  */
      82                 :            : 
      83                 :            :   class loop *always_executed_in;
      84                 :            :                                 /* The outermost loop for that we are sure
      85                 :            :                                    the statement is executed if the loop
      86                 :            :                                    is entered.  */
      87                 :            : 
      88                 :            :   unsigned cost;                /* Cost of the computation performed by the
      89                 :            :                                    statement.  */
      90                 :            : 
      91                 :            :   unsigned ref;                 /* The simple_mem_ref in this stmt or 0.  */
      92                 :            : 
      93                 :            :   vec<gimple *> depends;  /* Vector of statements that must be also
      94                 :            :                                    hoisted out of the loop when this statement
      95                 :            :                                    is hoisted; i.e. those that define the
      96                 :            :                                    operands of the statement and are inside of
      97                 :            :                                    the MAX_LOOP loop.  */
      98                 :            : };
      99                 :            : 
     100                 :            : /* Maps statements to their lim_aux_data.  */
     101                 :            : 
     102                 :            : static hash_map<gimple *, lim_aux_data *> *lim_aux_data_map;
     103                 :            : 
     104                 :            : /* Description of a memory reference location.  */
     105                 :            : 
     106                 :            : struct mem_ref_loc
     107                 :            : {
     108                 :            :   tree *ref;                    /* The reference itself.  */
     109                 :            :   gimple *stmt;                 /* The statement in that it occurs.  */
     110                 :            : };
     111                 :            : 
     112                 :            : 
     113                 :            : /* Description of a memory reference.  */
     114                 :            : 
     115                 :            : class im_mem_ref
     116                 :            : {
     117                 :            : public:
     118                 :            :   unsigned id : 30;             /* ID assigned to the memory reference
     119                 :            :                                    (its index in memory_accesses.refs_list)  */
     120                 :            :   unsigned ref_canonical : 1;   /* Whether mem.ref was canonicalized.  */
     121                 :            :   unsigned ref_decomposed : 1;  /* Whether the ref was hashed from mem.  */
     122                 :            :   hashval_t hash;               /* Its hash value.  */
     123                 :            : 
     124                 :            :   /* The memory access itself and associated caching of alias-oracle
     125                 :            :      query meta-data.  */
     126                 :            :   ao_ref mem;
     127                 :            : 
     128                 :            :   bitmap stored;                /* The set of loops in that this memory location
     129                 :            :                                    is stored to.  */
     130                 :            :   vec<mem_ref_loc>                accesses_in_loop;
     131                 :            :                                 /* The locations of the accesses.  Vector
     132                 :            :                                    indexed by the loop number.  */
     133                 :            : 
     134                 :            :   /* The following sets are computed on demand.  We keep both set and
     135                 :            :      its complement, so that we know whether the information was
     136                 :            :      already computed or not.  */
     137                 :            :   bitmap_head indep_loop;       /* The set of loops in that the memory
     138                 :            :                                    reference is independent, meaning:
     139                 :            :                                    If it is stored in the loop, this store
     140                 :            :                                      is independent on all other loads and
     141                 :            :                                      stores.
     142                 :            :                                    If it is only loaded, then it is independent
     143                 :            :                                      on all stores in the loop.  */
     144                 :            :   bitmap_head dep_loop;         /* The complement of INDEP_LOOP.  */
     145                 :            : };
     146                 :            : 
     147                 :            : /* We use two bits per loop in the ref->{in,}dep_loop bitmaps, the first
     148                 :            :    to record (in)dependence against stores in the loop and its subloops, the
     149                 :            :    second to record (in)dependence against all references in the loop
     150                 :            :    and its subloops.  */
     151                 :            : #define LOOP_DEP_BIT(loopnum, storedp) (2 * (loopnum) + (storedp ? 1 : 0))
     152                 :            : 
     153                 :            : /* Mem_ref hashtable helpers.  */
     154                 :            : 
     155                 :            : struct mem_ref_hasher : nofree_ptr_hash <im_mem_ref>
     156                 :            : {
     157                 :            :   typedef ao_ref *compare_type;
     158                 :            :   static inline hashval_t hash (const im_mem_ref *);
     159                 :            :   static inline bool equal (const im_mem_ref *, const ao_ref *);
     160                 :            : };
     161                 :            : 
     162                 :            : /* A hash function for class im_mem_ref object OBJ.  */
     163                 :            : 
     164                 :            : inline hashval_t
     165                 :    6477560 : mem_ref_hasher::hash (const im_mem_ref *mem)
     166                 :            : {
     167                 :    6477560 :   return mem->hash;
     168                 :            : }
     169                 :            : 
     170                 :            : /* An equality function for class im_mem_ref object MEM1 with
     171                 :            :    memory reference OBJ2.  */
     172                 :            : 
     173                 :            : inline bool
     174                 :    7600900 : mem_ref_hasher::equal (const im_mem_ref *mem1, const ao_ref *obj2)
     175                 :            : {
     176                 :    7600900 :   if (obj2->max_size_known_p ())
     177                 :    6791290 :     return (mem1->ref_decomposed
     178                 :    6529640 :             && operand_equal_p (mem1->mem.base, obj2->base, 0)
     179                 :     727226 :             && known_eq (mem1->mem.offset, obj2->offset)
     180                 :     506531 :             && known_eq (mem1->mem.size, obj2->size)
     181                 :     505931 :             && known_eq (mem1->mem.max_size, obj2->max_size)
     182                 :     505931 :             && mem1->mem.volatile_p == obj2->volatile_p
     183                 :     505924 :             && (mem1->mem.ref_alias_set == obj2->ref_alias_set
     184                 :            :                 /* We are not canonicalizing alias-sets but for the
     185                 :            :                    special-case we didn't canonicalize yet and the
     186                 :            :                    incoming ref is a alias-set zero MEM we pick
     187                 :            :                    the correct one already.  */
     188                 :       2769 :                 || (!mem1->ref_canonical
     189                 :       2456 :                     && (TREE_CODE (obj2->ref) == MEM_REF
     190                 :       2456 :                         || TREE_CODE (obj2->ref) == TARGET_MEM_REF)
     191                 :       1028 :                     && obj2->ref_alias_set == 0)
     192                 :            :                 /* Likewise if there's a canonical ref with alias-set zero.  */
     193                 :       1945 :                 || (mem1->ref_canonical && mem1->mem.ref_alias_set == 0))
     194                 :    7295270 :             && types_compatible_p (TREE_TYPE (mem1->mem.ref),
     195                 :     503979 :                                    TREE_TYPE (obj2->ref)));
     196                 :            :   else
     197                 :     809615 :     return operand_equal_p (mem1->mem.ref, obj2->ref, 0);
     198                 :            : }
     199                 :            : 
     200                 :            : 
     201                 :            : /* Description of memory accesses in loops.  */
     202                 :            : 
     203                 :            : static struct
     204                 :            : {
     205                 :            :   /* The hash table of memory references accessed in loops.  */
     206                 :            :   hash_table<mem_ref_hasher> *refs;
     207                 :            : 
     208                 :            :   /* The list of memory references.  */
     209                 :            :   vec<im_mem_ref *> refs_list;
     210                 :            : 
     211                 :            :   /* The set of memory references accessed in each loop.  */
     212                 :            :   vec<bitmap_head> refs_in_loop;
     213                 :            : 
     214                 :            :   /* The set of memory references stored in each loop.  */
     215                 :            :   vec<bitmap_head> refs_stored_in_loop;
     216                 :            : 
     217                 :            :   /* The set of memory references stored in each loop, including subloops .  */
     218                 :            :   vec<bitmap_head> all_refs_stored_in_loop;
     219                 :            : 
     220                 :            :   /* Cache for expanding memory addresses.  */
     221                 :            :   hash_map<tree, name_expansion *> *ttae_cache;
     222                 :            : } memory_accesses;
     223                 :            : 
     224                 :            : /* Obstack for the bitmaps in the above data structures.  */
     225                 :            : static bitmap_obstack lim_bitmap_obstack;
     226                 :            : static obstack mem_ref_obstack;
     227                 :            : 
     228                 :            : static bool ref_indep_loop_p (class loop *, im_mem_ref *);
     229                 :            : static bool ref_always_accessed_p (class loop *, im_mem_ref *, bool);
     230                 :            : 
     231                 :            : /* Minimum cost of an expensive expression.  */
     232                 :            : #define LIM_EXPENSIVE ((unsigned) param_lim_expensive)
     233                 :            : 
     234                 :            : /* The outermost loop for which execution of the header guarantees that the
     235                 :            :    block will be executed.  */
     236                 :            : #define ALWAYS_EXECUTED_IN(BB) ((class loop *) (BB)->aux)
     237                 :            : #define SET_ALWAYS_EXECUTED_IN(BB, VAL) ((BB)->aux = (void *) (VAL))
     238                 :            : 
     239                 :            : /* ID of the shared unanalyzable mem.  */
     240                 :            : #define UNANALYZABLE_MEM_ID 0
     241                 :            : 
     242                 :            : /* Whether the reference was analyzable.  */
     243                 :            : #define MEM_ANALYZABLE(REF) ((REF)->id != UNANALYZABLE_MEM_ID)
     244                 :            : 
     245                 :            : static struct lim_aux_data *
     246                 :   10734300 : init_lim_data (gimple *stmt)
     247                 :            : {
     248                 :   10734300 :   lim_aux_data *p = XCNEW (struct lim_aux_data);
     249                 :   10734300 :   lim_aux_data_map->put (stmt, p);
     250                 :            : 
     251                 :   10734300 :   return p;
     252                 :            : }
     253                 :            : 
     254                 :            : static struct lim_aux_data *
     255                 :   57008600 : get_lim_data (gimple *stmt)
     256                 :            : {
     257                 :   57008600 :   lim_aux_data **p = lim_aux_data_map->get (stmt);
     258                 :   29695900 :   if (!p)
     259                 :            :     return NULL;
     260                 :            : 
     261                 :   29695900 :   return *p;
     262                 :            : }
     263                 :            : 
     264                 :            : /* Releases the memory occupied by DATA.  */
     265                 :            : 
     266                 :            : static void
     267                 :   10734300 : free_lim_aux_data (struct lim_aux_data *data)
     268                 :            : {
     269                 :   10734300 :   data->depends.release ();
     270                 :   10734300 :   free (data);
     271                 :   10734300 : }
     272                 :            : 
     273                 :            : static void
     274                 :   10734300 : clear_lim_data (gimple *stmt)
     275                 :            : {
     276                 :   10734300 :   lim_aux_data **p = lim_aux_data_map->get (stmt);
     277                 :   10734300 :   if (!p)
     278                 :            :     return;
     279                 :            : 
     280                 :   10734300 :   free_lim_aux_data (*p);
     281                 :   10734300 :   *p = NULL;
     282                 :            : }
     283                 :            : 
     284                 :            : 
     285                 :            : /* The possibilities of statement movement.  */
     286                 :            : enum move_pos
     287                 :            :   {
     288                 :            :     MOVE_IMPOSSIBLE,            /* No movement -- side effect expression.  */
     289                 :            :     MOVE_PRESERVE_EXECUTION,    /* Must not cause the non-executed statement
     290                 :            :                                    become executed -- memory accesses, ... */
     291                 :            :     MOVE_POSSIBLE               /* Unlimited movement.  */
     292                 :            :   };
     293                 :            : 
     294                 :            : 
     295                 :            : /* If it is possible to hoist the statement STMT unconditionally,
     296                 :            :    returns MOVE_POSSIBLE.
     297                 :            :    If it is possible to hoist the statement STMT, but we must avoid making
     298                 :            :    it executed if it would not be executed in the original program (e.g.
     299                 :            :    because it may trap), return MOVE_PRESERVE_EXECUTION.
     300                 :            :    Otherwise return MOVE_IMPOSSIBLE.  */
     301                 :            : 
     302                 :            : enum move_pos
     303                 :   27619400 : movement_possibility (gimple *stmt)
     304                 :            : {
     305                 :   27619400 :   tree lhs;
     306                 :   27619400 :   enum move_pos ret = MOVE_POSSIBLE;
     307                 :            : 
     308                 :   27619400 :   if (flag_unswitch_loops
     309                 :   27619400 :       && gimple_code (stmt) == GIMPLE_COND)
     310                 :            :     {
     311                 :            :       /* If we perform unswitching, force the operands of the invariant
     312                 :            :          condition to be moved out of the loop.  */
     313                 :            :       return MOVE_POSSIBLE;
     314                 :            :     }
     315                 :            : 
     316                 :   27429600 :   if (gimple_code (stmt) == GIMPLE_PHI
     317                 :    1431820 :       && gimple_phi_num_args (stmt) <= 2
     318                 :    2672220 :       && !virtual_operand_p (gimple_phi_result (stmt))
     319                 :   28130800 :       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (stmt)))
     320                 :            :     return MOVE_POSSIBLE;
     321                 :            : 
     322                 :   26728500 :   if (gimple_get_lhs (stmt) == NULL_TREE)
     323                 :            :     return MOVE_IMPOSSIBLE;
     324                 :            : 
     325                 :   19452600 :   if (gimple_vdef (stmt))
     326                 :            :     return MOVE_IMPOSSIBLE;
     327                 :            : 
     328                 :    7900900 :   if (stmt_ends_bb_p (stmt)
     329                 :    7144100 :       || gimple_has_volatile_ops (stmt)
     330                 :    7851700 :       || gimple_has_side_effects (stmt)
     331                 :   15749000 :       || stmt_could_throw_p (cfun, stmt))
     332                 :     299745 :     return MOVE_IMPOSSIBLE;
     333                 :            : 
     334                 :    7601150 :   if (is_gimple_call (stmt))
     335                 :            :     {
     336                 :            :       /* While pure or const call is guaranteed to have no side effects, we
     337                 :            :          cannot move it arbitrarily.  Consider code like
     338                 :            : 
     339                 :            :          char *s = something ();
     340                 :            : 
     341                 :            :          while (1)
     342                 :            :            {
     343                 :            :              if (s)
     344                 :            :                t = strlen (s);
     345                 :            :              else
     346                 :            :                t = 0;
     347                 :            :            }
     348                 :            : 
     349                 :            :          Here the strlen call cannot be moved out of the loop, even though
     350                 :            :          s is invariant.  In addition to possibly creating a call with
     351                 :            :          invalid arguments, moving out a function call that is not executed
     352                 :            :          may cause performance regressions in case the call is costly and
     353                 :            :          not executed at all.  */
     354                 :      48554 :       ret = MOVE_PRESERVE_EXECUTION;
     355                 :      48554 :       lhs = gimple_call_lhs (stmt);
     356                 :            :     }
     357                 :    7552600 :   else if (is_gimple_assign (stmt))
     358                 :    6821820 :     lhs = gimple_assign_lhs (stmt);
     359                 :            :   else
     360                 :            :     return MOVE_IMPOSSIBLE;
     361                 :            : 
     362                 :    6870370 :   if (TREE_CODE (lhs) == SSA_NAME
     363                 :    6870370 :       && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
     364                 :            :     return MOVE_IMPOSSIBLE;
     365                 :            : 
     366                 :    6870190 :   if (TREE_CODE (lhs) != SSA_NAME
     367                 :    6870190 :       || gimple_could_trap_p (stmt))
     368                 :    1350400 :     return MOVE_PRESERVE_EXECUTION;
     369                 :            : 
     370                 :            :   /* Non local loads in a transaction cannot be hoisted out.  Well,
     371                 :            :      unless the load happens on every path out of the loop, but we
     372                 :            :      don't take this into account yet.  */
     373                 :    5519790 :   if (flag_tm
     374                 :        423 :       && gimple_in_transaction (stmt)
     375                 :    5519790 :       && gimple_assign_single_p (stmt))
     376                 :            :     {
     377                 :         18 :       tree rhs = gimple_assign_rhs1 (stmt);
     378                 :         18 :       if (DECL_P (rhs) && is_global_var (rhs))
     379                 :            :         {
     380                 :         18 :           if (dump_file)
     381                 :            :             {
     382                 :          2 :               fprintf (dump_file, "Cannot hoist conditional load of ");
     383                 :          2 :               print_generic_expr (dump_file, rhs, TDF_SLIM);
     384                 :          2 :               fprintf (dump_file, " because it is in a transaction.\n");
     385                 :            :             }
     386                 :         18 :           return MOVE_IMPOSSIBLE;
     387                 :            :         }
     388                 :            :     }
     389                 :            : 
     390                 :            :   return ret;
     391                 :            : }
     392                 :            : 
     393                 :            : /* Suppose that operand DEF is used inside the LOOP.  Returns the outermost
     394                 :            :    loop to that we could move the expression using DEF if it did not have
     395                 :            :    other operands, i.e. the outermost loop enclosing LOOP in that the value
     396                 :            :    of DEF is invariant.  */
     397                 :            : 
     398                 :            : static class loop *
     399                 :   12205300 : outermost_invariant_loop (tree def, class loop *loop)
     400                 :            : {
     401                 :   12205300 :   gimple *def_stmt;
     402                 :   12205300 :   basic_block def_bb;
     403                 :   12205300 :   class loop *max_loop;
     404                 :   12205300 :   struct lim_aux_data *lim_data;
     405                 :            : 
     406                 :   12205300 :   if (!def)
     407                 :     646747 :     return superloop_at_depth (loop, 1);
     408                 :            : 
     409                 :   11558600 :   if (TREE_CODE (def) != SSA_NAME)
     410                 :            :     {
     411                 :    2159620 :       gcc_assert (is_gimple_min_invariant (def));
     412                 :    2159620 :       return superloop_at_depth (loop, 1);
     413                 :            :     }
     414                 :            : 
     415                 :    9398930 :   def_stmt = SSA_NAME_DEF_STMT (def);
     416                 :    9398930 :   def_bb = gimple_bb (def_stmt);
     417                 :    9398930 :   if (!def_bb)
     418                 :      49549 :     return superloop_at_depth (loop, 1);
     419                 :            : 
     420                 :    9349380 :   max_loop = find_common_loop (loop, def_bb->loop_father);
     421                 :            : 
     422                 :    9349380 :   lim_data = get_lim_data (def_stmt);
     423                 :    9349380 :   if (lim_data != NULL && lim_data->max_loop != NULL)
     424                 :    1130690 :     max_loop = find_common_loop (max_loop,
     425                 :            :                                  loop_outer (lim_data->max_loop));
     426                 :    9349380 :   if (max_loop == loop)
     427                 :            :     return NULL;
     428                 :    1501130 :   max_loop = superloop_at_depth (loop, loop_depth (max_loop) + 1);
     429                 :            : 
     430                 :    1501130 :   return max_loop;
     431                 :            : }
     432                 :            : 
     433                 :            : /* DATA is a structure containing information associated with a statement
     434                 :            :    inside LOOP.  DEF is one of the operands of this statement.
     435                 :            : 
     436                 :            :    Find the outermost loop enclosing LOOP in that value of DEF is invariant
     437                 :            :    and record this in DATA->max_loop field.  If DEF itself is defined inside
     438                 :            :    this loop as well (i.e. we need to hoist it out of the loop if we want
     439                 :            :    to hoist the statement represented by DATA), record the statement in that
     440                 :            :    DEF is defined to the DATA->depends list.  Additionally if ADD_COST is true,
     441                 :            :    add the cost of the computation of DEF to the DATA->cost.
     442                 :            : 
     443                 :            :    If DEF is not invariant in LOOP, return false.  Otherwise return TRUE.  */
     444                 :            : 
     445                 :            : static bool
     446                 :    7386620 : add_dependency (tree def, struct lim_aux_data *data, class loop *loop,
     447                 :            :                 bool add_cost)
     448                 :            : {
     449                 :    7386620 :   gimple *def_stmt = SSA_NAME_DEF_STMT (def);
     450                 :    7386620 :   basic_block def_bb = gimple_bb (def_stmt);
     451                 :    7386620 :   class loop *max_loop;
     452                 :    7386620 :   struct lim_aux_data *def_data;
     453                 :            : 
     454                 :    7386620 :   if (!def_bb)
     455                 :            :     return true;
     456                 :            : 
     457                 :    7179930 :   max_loop = outermost_invariant_loop (def, loop);
     458                 :    7179930 :   if (!max_loop)
     459                 :            :     return false;
     460                 :            : 
     461                 :    1165640 :   if (flow_loop_nested_p (data->max_loop, max_loop))
     462                 :     394687 :     data->max_loop = max_loop;
     463                 :            : 
     464                 :    1165640 :   def_data = get_lim_data (def_stmt);
     465                 :    1165640 :   if (!def_data)
     466                 :            :     return true;
     467                 :            : 
     468                 :     576044 :   if (add_cost
     469                 :            :       /* Only add the cost if the statement defining DEF is inside LOOP,
     470                 :            :          i.e. if it is likely that by moving the invariants dependent
     471                 :            :          on it, we will be able to avoid creating a new register for
     472                 :            :          it (since it will be only used in these dependent invariants).  */
     473                 :     524535 :       && def_bb->loop_father == loop)
     474                 :     386738 :     data->cost += def_data->cost;
     475                 :            : 
     476                 :     576044 :   data->depends.safe_push (def_stmt);
     477                 :            : 
     478                 :     576044 :   return true;
     479                 :            : }
     480                 :            : 
     481                 :            : /* Returns an estimate for a cost of statement STMT.  The values here
     482                 :            :    are just ad-hoc constants, similar to costs for inlining.  */
     483                 :            : 
     484                 :            : static unsigned
     485                 :     598220 : stmt_cost (gimple *stmt)
     486                 :            : {
     487                 :            :   /* Always try to create possibilities for unswitching.  */
     488                 :     598220 :   if (gimple_code (stmt) == GIMPLE_COND
     489                 :     598220 :       || gimple_code (stmt) == GIMPLE_PHI)
     490                 :      12045 :     return LIM_EXPENSIVE;
     491                 :            : 
     492                 :            :   /* We should be hoisting calls if possible.  */
     493                 :     586175 :   if (is_gimple_call (stmt))
     494                 :            :     {
     495                 :        582 :       tree fndecl;
     496                 :            : 
     497                 :            :       /* Unless the call is a builtin_constant_p; this always folds to a
     498                 :            :          constant, so moving it is useless.  */
     499                 :        582 :       fndecl = gimple_call_fndecl (stmt);
     500                 :        582 :       if (fndecl && fndecl_built_in_p (fndecl, BUILT_IN_CONSTANT_P))
     501                 :            :         return 0;
     502                 :            : 
     503                 :        582 :       return LIM_EXPENSIVE;
     504                 :            :     }
     505                 :            : 
     506                 :            :   /* Hoisting memory references out should almost surely be a win.  */
     507                 :     585593 :   if (gimple_references_memory_p (stmt))
     508                 :      43603 :     return LIM_EXPENSIVE;
     509                 :            : 
     510                 :     541990 :   if (gimple_code (stmt) != GIMPLE_ASSIGN)
     511                 :            :     return 1;
     512                 :            : 
     513                 :     541990 :   switch (gimple_assign_rhs_code (stmt))
     514                 :            :     {
     515                 :      91912 :     case MULT_EXPR:
     516                 :      91912 :     case WIDEN_MULT_EXPR:
     517                 :      91912 :     case WIDEN_MULT_PLUS_EXPR:
     518                 :      91912 :     case WIDEN_MULT_MINUS_EXPR:
     519                 :      91912 :     case DOT_PROD_EXPR:
     520                 :      91912 :     case TRUNC_DIV_EXPR:
     521                 :      91912 :     case CEIL_DIV_EXPR:
     522                 :      91912 :     case FLOOR_DIV_EXPR:
     523                 :      91912 :     case ROUND_DIV_EXPR:
     524                 :      91912 :     case EXACT_DIV_EXPR:
     525                 :      91912 :     case CEIL_MOD_EXPR:
     526                 :      91912 :     case FLOOR_MOD_EXPR:
     527                 :      91912 :     case ROUND_MOD_EXPR:
     528                 :      91912 :     case TRUNC_MOD_EXPR:
     529                 :      91912 :     case RDIV_EXPR:
     530                 :            :       /* Division and multiplication are usually expensive.  */
     531                 :      91912 :       return LIM_EXPENSIVE;
     532                 :            : 
     533                 :       8500 :     case LSHIFT_EXPR:
     534                 :       8500 :     case RSHIFT_EXPR:
     535                 :       8500 :     case WIDEN_LSHIFT_EXPR:
     536                 :       8500 :     case LROTATE_EXPR:
     537                 :       8500 :     case RROTATE_EXPR:
     538                 :            :       /* Shifts and rotates are usually expensive.  */
     539                 :       8500 :       return LIM_EXPENSIVE;
     540                 :            : 
     541                 :        798 :     case CONSTRUCTOR:
     542                 :            :       /* Make vector construction cost proportional to the number
     543                 :            :          of elements.  */
     544                 :        798 :       return CONSTRUCTOR_NELTS (gimple_assign_rhs1 (stmt));
     545                 :            : 
     546                 :            :     case SSA_NAME:
     547                 :            :     case PAREN_EXPR:
     548                 :            :       /* Whether or not something is wrapped inside a PAREN_EXPR
     549                 :            :          should not change move cost.  Nor should an intermediate
     550                 :            :          unpropagated SSA name copy.  */
     551                 :            :       return 0;
     552                 :            : 
     553                 :     406331 :     default:
     554                 :     406331 :       return 1;
     555                 :            :     }
     556                 :            : }
     557                 :            : 
     558                 :            : /* Finds the outermost loop between OUTER and LOOP in that the memory reference
     559                 :            :    REF is independent.  If REF is not independent in LOOP, NULL is returned
     560                 :            :    instead.  */
     561                 :            : 
     562                 :            : static class loop *
     563                 :     592977 : outermost_indep_loop (class loop *outer, class loop *loop, im_mem_ref *ref)
     564                 :            : {
     565                 :     592977 :   class loop *aloop;
     566                 :            : 
     567                 :     592977 :   if (ref->stored && bitmap_bit_p (ref->stored, loop->num))
     568                 :            :     return NULL;
     569                 :            : 
     570                 :      91208 :   for (aloop = outer;
     571                 :     587141 :        aloop != loop;
     572                 :     182416 :        aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
     573                 :      11277 :     if ((!ref->stored || !bitmap_bit_p (ref->stored, aloop->num))
     574                 :     100705 :         && ref_indep_loop_p (aloop, ref))
     575                 :       7715 :       return aloop;
     576                 :            : 
     577                 :     488218 :   if (ref_indep_loop_p (loop, ref))
     578                 :            :     return loop;
     579                 :            :   else
     580                 :     452330 :     return NULL;
     581                 :            : }
     582                 :            : 
     583                 :            : /* If there is a simple load or store to a memory reference in STMT, returns
     584                 :            :    the location of the memory reference, and sets IS_STORE according to whether
     585                 :            :    it is a store or load.  Otherwise, returns NULL.  */
     586                 :            : 
     587                 :            : static tree *
     588                 :    4639670 : simple_mem_ref_in_stmt (gimple *stmt, bool *is_store)
     589                 :            : {
     590                 :    4639670 :   tree *lhs, *rhs;
     591                 :            : 
     592                 :            :   /* Recognize SSA_NAME = MEM and MEM = (SSA_NAME | invariant) patterns.  */
     593                 :    4639670 :   if (!gimple_assign_single_p (stmt))
     594                 :            :     return NULL;
     595                 :            : 
     596                 :    3763900 :   lhs = gimple_assign_lhs_ptr (stmt);
     597                 :    3763900 :   rhs = gimple_assign_rhs1_ptr (stmt);
     598                 :            : 
     599                 :    3763900 :   if (TREE_CODE (*lhs) == SSA_NAME && gimple_vuse (stmt))
     600                 :            :     {
     601                 :    1954760 :       *is_store = false;
     602                 :    1954760 :       return rhs;
     603                 :            :     }
     604                 :    1809140 :   else if (gimple_vdef (stmt)
     605                 :    1809140 :            && (TREE_CODE (*rhs) == SSA_NAME || is_gimple_min_invariant (*rhs)))
     606                 :            :     {
     607                 :    1398840 :       *is_store = true;
     608                 :    1398840 :       return lhs;
     609                 :            :     }
     610                 :            :   else
     611                 :     410303 :     return NULL;
     612                 :            : }
     613                 :            : 
     614                 :            : /* From a controlling predicate in DOM determine the arguments from
     615                 :            :    the PHI node PHI that are chosen if the predicate evaluates to
     616                 :            :    true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
     617                 :            :    they are non-NULL.  Returns true if the arguments can be determined,
     618                 :            :    else return false.  */
     619                 :            : 
     620                 :            : static bool
     621                 :       9542 : extract_true_false_args_from_phi (basic_block dom, gphi *phi,
     622                 :            :                                   tree *true_arg_p, tree *false_arg_p)
     623                 :            : {
     624                 :       9542 :   edge te, fe;
     625                 :       9542 :   if (! extract_true_false_controlled_edges (dom, gimple_bb (phi),
     626                 :            :                                              &te, &fe))
     627                 :            :     return false;
     628                 :            : 
     629                 :       1373 :   if (true_arg_p)
     630                 :       1373 :     *true_arg_p = PHI_ARG_DEF (phi, te->dest_idx);
     631                 :       1373 :   if (false_arg_p)
     632                 :       1373 :     *false_arg_p = PHI_ARG_DEF (phi, fe->dest_idx);
     633                 :            : 
     634                 :            :   return true;
     635                 :            : }
     636                 :            : 
     637                 :            : /* Determine the outermost loop to that it is possible to hoist a statement
     638                 :            :    STMT and store it to LIM_DATA (STMT)->max_loop.  To do this we determine
     639                 :            :    the outermost loop in that the value computed by STMT is invariant.
     640                 :            :    If MUST_PRESERVE_EXEC is true, additionally choose such a loop that
     641                 :            :    we preserve the fact whether STMT is executed.  It also fills other related
     642                 :            :    information to LIM_DATA (STMT).
     643                 :            : 
     644                 :            :    The function returns false if STMT cannot be hoisted outside of the loop it
     645                 :            :    is defined in, and true otherwise.  */
     646                 :            : 
     647                 :            : static bool
     648                 :    7165200 : determine_max_movement (gimple *stmt, bool must_preserve_exec)
     649                 :            : {
     650                 :    7165200 :   basic_block bb = gimple_bb (stmt);
     651                 :    7165200 :   class loop *loop = bb->loop_father;
     652                 :    7165200 :   class loop *level;
     653                 :    7165200 :   struct lim_aux_data *lim_data = get_lim_data (stmt);
     654                 :    7165200 :   tree val;
     655                 :    7165200 :   ssa_op_iter iter;
     656                 :            : 
     657                 :    7165200 :   if (must_preserve_exec)
     658                 :     791916 :     level = ALWAYS_EXECUTED_IN (bb);
     659                 :            :   else
     660                 :    6373280 :     level = superloop_at_depth (loop, 1);
     661                 :    7165200 :   lim_data->max_loop = level;
     662                 :            : 
     663                 :    7165200 :   if (gphi *phi = dyn_cast <gphi *> (stmt))
     664                 :            :     {
     665                 :     701037 :       use_operand_p use_p;
     666                 :     701037 :       unsigned min_cost = UINT_MAX;
     667                 :     701037 :       unsigned total_cost = 0;
     668                 :     701037 :       struct lim_aux_data *def_data;
     669                 :            : 
     670                 :            :       /* We will end up promoting dependencies to be unconditionally
     671                 :            :          evaluated.  For this reason the PHI cost (and thus the
     672                 :            :          cost we remove from the loop by doing the invariant motion)
     673                 :            :          is that of the cheapest PHI argument dependency chain.  */
     674                 :    1211850 :       FOR_EACH_PHI_ARG (use_p, phi, iter, SSA_OP_USE)
     675                 :            :         {
     676                 :    1201810 :           val = USE_FROM_PTR (use_p);
     677                 :            : 
     678                 :    1201810 :           if (TREE_CODE (val) != SSA_NAME)
     679                 :            :             {
     680                 :            :               /* Assign const 1 to constants.  */
     681                 :     337130 :               min_cost = MIN (min_cost, 1);
     682                 :     337130 :               total_cost += 1;
     683                 :     337130 :               continue;
     684                 :            :             }
     685                 :     864681 :           if (!add_dependency (val, lim_data, loop, false))
     686                 :            :             return false;
     687                 :            : 
     688                 :     173680 :           gimple *def_stmt = SSA_NAME_DEF_STMT (val);
     689                 :     173680 :           if (gimple_bb (def_stmt)
     690                 :     173680 :               && gimple_bb (def_stmt)->loop_father == loop)
     691                 :            :             {
     692                 :       1952 :               def_data = get_lim_data (def_stmt);
     693                 :       1952 :               if (def_data)
     694                 :            :                 {
     695                 :       1952 :                   min_cost = MIN (min_cost, def_data->cost);
     696                 :       1952 :                   total_cost += def_data->cost;
     697                 :            :                 }
     698                 :            :             }
     699                 :            :         }
     700                 :            : 
     701                 :      10036 :       min_cost = MIN (min_cost, total_cost);
     702                 :      10036 :       lim_data->cost += min_cost;
     703                 :            : 
     704                 :      10036 :       if (gimple_phi_num_args (phi) > 1)
     705                 :            :         {
     706                 :       9369 :           basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
     707                 :       9369 :           gimple *cond;
     708                 :      18738 :           if (gsi_end_p (gsi_last_bb (dom)))
     709                 :            :             return false;
     710                 :       8868 :           cond = gsi_stmt (gsi_last_bb (dom));
     711                 :       8868 :           if (gimple_code (cond) != GIMPLE_COND)
     712                 :            :             return false;
     713                 :            :           /* Verify that this is an extended form of a diamond and
     714                 :            :              the PHI arguments are completely controlled by the
     715                 :            :              predicate in DOM.  */
     716                 :       8169 :           if (!extract_true_false_args_from_phi (dom, phi, NULL, NULL))
     717                 :        938 :             return false;
     718                 :            : 
     719                 :            :           /* Fold in dependencies and cost of the condition.  */
     720                 :       9832 :           FOR_EACH_SSA_TREE_OPERAND (val, cond, iter, SSA_OP_USE)
     721                 :            :             {
     722                 :       7952 :               if (!add_dependency (val, lim_data, loop, false))
     723                 :            :                 return false;
     724                 :       2601 :               def_data = get_lim_data (SSA_NAME_DEF_STMT (val));
     725                 :       2601 :               if (def_data)
     726                 :       1419 :                 lim_data->cost += def_data->cost;
     727                 :            :             }
     728                 :            : 
     729                 :            :           /* We want to avoid unconditionally executing very expensive
     730                 :            :              operations.  As costs for our dependencies cannot be
     731                 :            :              negative just claim we are not invariand for this case.
     732                 :            :              We also are not sure whether the control-flow inside the
     733                 :            :              loop will vanish.  */
     734                 :       1880 :           if (total_cost - min_cost >= 2 * LIM_EXPENSIVE
     735                 :        529 :               && !(min_cost != 0
     736                 :        529 :                    && total_cost / min_cost <= 2))
     737                 :            :             return false;
     738                 :            : 
     739                 :            :           /* Assume that the control-flow in the loop will vanish.
     740                 :            :              ???  We should verify this and not artificially increase
     741                 :            :              the cost if that is not the case.  */
     742                 :       1373 :           lim_data->cost += stmt_cost (stmt);
     743                 :            :         }
     744                 :            : 
     745                 :       2040 :       return true;
     746                 :            :     }
     747                 :            :   else
     748                 :    7660150 :     FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
     749                 :    6513250 :       if (!add_dependency (val, lim_data, loop, true))
     750                 :            :         return false;
     751                 :            : 
     752                 :    2283120 :   if (gimple_vuse (stmt))
     753                 :            :     {
     754                 :     593709 :       im_mem_ref *ref
     755                 :     593709 :         = lim_data ? memory_accesses.refs_list[lim_data->ref] : NULL;
     756                 :     593709 :       if (ref
     757                 :     593709 :           && MEM_ANALYZABLE (ref))
     758                 :            :         {
     759                 :     592977 :           lim_data->max_loop = outermost_indep_loop (lim_data->max_loop,
     760                 :            :                                                      loop, ref);
     761                 :     592977 :           if (!lim_data->max_loop)
     762                 :            :             return false;
     763                 :            :         }
     764                 :        732 :       else if (! add_dependency (gimple_vuse (stmt), lim_data, loop, false))
     765                 :            :         return false;
     766                 :            :     }
     767                 :            : 
     768                 :     596847 :   lim_data->cost += stmt_cost (stmt);
     769                 :            : 
     770                 :     596847 :   return true;
     771                 :            : }
     772                 :            : 
     773                 :            : /* Suppose that some statement in ORIG_LOOP is hoisted to the loop LEVEL,
     774                 :            :    and that one of the operands of this statement is computed by STMT.
     775                 :            :    Ensure that STMT (together with all the statements that define its
     776                 :            :    operands) is hoisted at least out of the loop LEVEL.  */
     777                 :            : 
     778                 :            : static void
     779                 :     506228 : set_level (gimple *stmt, class loop *orig_loop, class loop *level)
     780                 :            : {
     781                 :     506228 :   class loop *stmt_loop = gimple_bb (stmt)->loop_father;
     782                 :     506228 :   struct lim_aux_data *lim_data;
     783                 :     506228 :   gimple *dep_stmt;
     784                 :     506228 :   unsigned i;
     785                 :            : 
     786                 :     506228 :   stmt_loop = find_common_loop (orig_loop, stmt_loop);
     787                 :     506228 :   lim_data = get_lim_data (stmt);
     788                 :     506228 :   if (lim_data != NULL && lim_data->tgt_loop != NULL)
     789                 :     236778 :     stmt_loop = find_common_loop (stmt_loop,
     790                 :            :                                   loop_outer (lim_data->tgt_loop));
     791                 :     506228 :   if (flow_loop_nested_p (stmt_loop, level))
     792                 :     506228 :     return;
     793                 :            : 
     794                 :     349860 :   gcc_assert (level == lim_data->max_loop
     795                 :            :               || flow_loop_nested_p (lim_data->max_loop, level));
     796                 :            : 
     797                 :     349860 :   lim_data->tgt_loop = level;
     798                 :     621579 :   FOR_EACH_VEC_ELT (lim_data->depends, i, dep_stmt)
     799                 :     271719 :     set_level (dep_stmt, orig_loop, level);
     800                 :            : }
     801                 :            : 
     802                 :            : /* Determines an outermost loop from that we want to hoist the statement STMT.
     803                 :            :    For now we chose the outermost possible loop.  TODO -- use profiling
     804                 :            :    information to set it more sanely.  */
     805                 :            : 
     806                 :            : static void
     807                 :     232498 : set_profitable_level (gimple *stmt)
     808                 :            : {
     809                 :     232498 :   set_level (stmt, gimple_bb (stmt)->loop_father, get_lim_data (stmt)->max_loop);
     810                 :     232498 : }
     811                 :            : 
     812                 :            : /* Returns true if STMT is a call that has side effects.  */
     813                 :            : 
     814                 :            : static bool
     815                 :   73703100 : nonpure_call_p (gimple *stmt)
     816                 :            : {
     817                 :   54575500 :   if (gimple_code (stmt) != GIMPLE_CALL)
     818                 :            :     return false;
     819                 :            : 
     820                 :    3432740 :   return gimple_has_side_effects (stmt);
     821                 :            : }
     822                 :            : 
     823                 :            : /* Rewrite a/b to a*(1/b).  Return the invariant stmt to process.  */
     824                 :            : 
     825                 :            : static gimple *
     826                 :         16 : rewrite_reciprocal (gimple_stmt_iterator *bsi)
     827                 :            : {
     828                 :         16 :   gassign *stmt, *stmt1, *stmt2;
     829                 :         16 :   tree name, lhs, type;
     830                 :         16 :   tree real_one;
     831                 :         16 :   gimple_stmt_iterator gsi;
     832                 :            : 
     833                 :         16 :   stmt = as_a <gassign *> (gsi_stmt (*bsi));
     834                 :         16 :   lhs = gimple_assign_lhs (stmt);
     835                 :         16 :   type = TREE_TYPE (lhs);
     836                 :            : 
     837                 :         16 :   real_one = build_one_cst (type);
     838                 :            : 
     839                 :         16 :   name = make_temp_ssa_name (type, NULL, "reciptmp");
     840                 :         32 :   stmt1 = gimple_build_assign (name, RDIV_EXPR, real_one,
     841                 :            :                                gimple_assign_rhs2 (stmt));
     842                 :         16 :   stmt2 = gimple_build_assign (lhs, MULT_EXPR, name,
     843                 :            :                                gimple_assign_rhs1 (stmt));
     844                 :            : 
     845                 :            :   /* Replace division stmt with reciprocal and multiply stmts.
     846                 :            :      The multiply stmt is not invariant, so update iterator
     847                 :            :      and avoid rescanning.  */
     848                 :         16 :   gsi = *bsi;
     849                 :         16 :   gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
     850                 :         16 :   gsi_replace (&gsi, stmt2, true);
     851                 :            : 
     852                 :            :   /* Continue processing with invariant reciprocal statement.  */
     853                 :         16 :   return stmt1;
     854                 :            : }
     855                 :            : 
     856                 :            : /* Check if the pattern at *BSI is a bittest of the form
     857                 :            :    (A >> B) & 1 != 0 and in this case rewrite it to A & (1 << B) != 0.  */
     858                 :            : 
     859                 :            : static gimple *
     860                 :       4901 : rewrite_bittest (gimple_stmt_iterator *bsi)
     861                 :            : {
     862                 :       4901 :   gassign *stmt;
     863                 :       4901 :   gimple *stmt1;
     864                 :       4901 :   gassign *stmt2;
     865                 :       4901 :   gimple *use_stmt;
     866                 :       4901 :   gcond *cond_stmt;
     867                 :       4901 :   tree lhs, name, t, a, b;
     868                 :       4901 :   use_operand_p use;
     869                 :            : 
     870                 :       4901 :   stmt = as_a <gassign *> (gsi_stmt (*bsi));
     871                 :       4901 :   lhs = gimple_assign_lhs (stmt);
     872                 :            : 
     873                 :            :   /* Verify that the single use of lhs is a comparison against zero.  */
     874                 :       4901 :   if (TREE_CODE (lhs) != SSA_NAME
     875                 :       4901 :       || !single_imm_use (lhs, &use, &use_stmt))
     876                 :        200 :     return stmt;
     877                 :       4701 :   cond_stmt = dyn_cast <gcond *> (use_stmt);
     878                 :       3407 :   if (!cond_stmt)
     879                 :            :     return stmt;
     880                 :       3407 :   if (gimple_cond_lhs (cond_stmt) != lhs
     881                 :       3253 :       || (gimple_cond_code (cond_stmt) != NE_EXPR
     882                 :        808 :           && gimple_cond_code (cond_stmt) != EQ_EXPR)
     883                 :       6660 :       || !integer_zerop (gimple_cond_rhs (cond_stmt)))
     884                 :        220 :     return stmt;
     885                 :            : 
     886                 :            :   /* Get at the operands of the shift.  The rhs is TMP1 & 1.  */
     887                 :       3187 :   stmt1 = SSA_NAME_DEF_STMT (gimple_assign_rhs1 (stmt));
     888                 :       3187 :   if (gimple_code (stmt1) != GIMPLE_ASSIGN)
     889                 :            :     return stmt;
     890                 :            : 
     891                 :            :   /* There is a conversion in between possibly inserted by fold.  */
     892                 :       3130 :   if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt1)))
     893                 :            :     {
     894                 :        434 :       t = gimple_assign_rhs1 (stmt1);
     895                 :        434 :       if (TREE_CODE (t) != SSA_NAME
     896                 :        434 :           || !has_single_use (t))
     897                 :            :         return stmt;
     898                 :        183 :       stmt1 = SSA_NAME_DEF_STMT (t);
     899                 :        183 :       if (gimple_code (stmt1) != GIMPLE_ASSIGN)
     900                 :            :         return stmt;
     901                 :            :     }
     902                 :            : 
     903                 :            :   /* Verify that B is loop invariant but A is not.  Verify that with
     904                 :            :      all the stmt walking we are still in the same loop.  */
     905                 :       2867 :   if (gimple_assign_rhs_code (stmt1) != RSHIFT_EXPR
     906                 :       7463 :       || loop_containing_stmt (stmt1) != loop_containing_stmt (stmt))
     907                 :            :     return stmt;
     908                 :            : 
     909                 :       2298 :   a = gimple_assign_rhs1 (stmt1);
     910                 :       2298 :   b = gimple_assign_rhs2 (stmt1);
     911                 :            : 
     912                 :       2298 :   if (outermost_invariant_loop (b, loop_containing_stmt (stmt1)) != NULL
     913                 :       2352 :       && outermost_invariant_loop (a, loop_containing_stmt (stmt1)) == NULL)
     914                 :            :     {
     915                 :         54 :       gimple_stmt_iterator rsi;
     916                 :            : 
     917                 :            :       /* 1 << B */
     918                 :         54 :       t = fold_build2 (LSHIFT_EXPR, TREE_TYPE (a),
     919                 :            :                        build_int_cst (TREE_TYPE (a), 1), b);
     920                 :         54 :       name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
     921                 :         54 :       stmt1 = gimple_build_assign (name, t);
     922                 :            : 
     923                 :            :       /* A & (1 << B) */
     924                 :         54 :       t = fold_build2 (BIT_AND_EXPR, TREE_TYPE (a), a, name);
     925                 :         54 :       name = make_temp_ssa_name (TREE_TYPE (a), NULL, "shifttmp");
     926                 :         54 :       stmt2 = gimple_build_assign (name, t);
     927                 :            : 
     928                 :            :       /* Replace the SSA_NAME we compare against zero.  Adjust
     929                 :            :          the type of zero accordingly.  */
     930                 :         54 :       SET_USE (use, name);
     931                 :         54 :       gimple_cond_set_rhs (cond_stmt,
     932                 :         54 :                            build_int_cst_type (TREE_TYPE (name),
     933                 :         54 :                                                0));
     934                 :            : 
     935                 :            :       /* Don't use gsi_replace here, none of the new assignments sets
     936                 :            :          the variable originally set in stmt.  Move bsi to stmt1, and
     937                 :            :          then remove the original stmt, so that we get a chance to
     938                 :            :          retain debug info for it.  */
     939                 :         54 :       rsi = *bsi;
     940                 :         54 :       gsi_insert_before (bsi, stmt1, GSI_NEW_STMT);
     941                 :         54 :       gsi_insert_before (&rsi, stmt2, GSI_SAME_STMT);
     942                 :         54 :       gimple *to_release = gsi_stmt (rsi);
     943                 :         54 :       gsi_remove (&rsi, true);
     944                 :         54 :       release_defs (to_release);
     945                 :            : 
     946                 :         54 :       return stmt1;
     947                 :            :     }
     948                 :            : 
     949                 :            :   return stmt;
     950                 :            : }
     951                 :            : 
     952                 :            : /* For each statement determines the outermost loop in that it is invariant,
     953                 :            :    -   statements on whose motion it depends and the cost of the computation.
     954                 :            :    -   This information is stored to the LIM_DATA structure associated with
     955                 :            :    -   each statement.  */
     956                 :     316604 : class invariantness_dom_walker : public dom_walker
     957                 :            : {
     958                 :            : public:
     959                 :     316604 :   invariantness_dom_walker (cdi_direction direction)
     960                 :     633208 :     : dom_walker (direction) {}
     961                 :            : 
     962                 :            :   virtual edge before_dom_children (basic_block);
     963                 :            : };
     964                 :            : 
     965                 :            : /* Determine the outermost loops in that statements in basic block BB are
     966                 :            :    invariant, and record them to the LIM_DATA associated with the statements.
     967                 :            :    Callback for dom_walker.  */
     968                 :            : 
     969                 :            : edge
     970                 :    9006050 : invariantness_dom_walker::before_dom_children (basic_block bb)
     971                 :            : {
     972                 :    9006050 :   enum move_pos pos;
     973                 :    9006050 :   gimple_stmt_iterator bsi;
     974                 :    9006050 :   gimple *stmt;
     975                 :    9006050 :   bool maybe_never = ALWAYS_EXECUTED_IN (bb) == NULL;
     976                 :    9006050 :   class loop *outermost = ALWAYS_EXECUTED_IN (bb);
     977                 :    9006050 :   struct lim_aux_data *lim_data;
     978                 :            : 
     979                 :   12667300 :   if (!loop_outer (bb->loop_father))
     980                 :            :     return NULL;
     981                 :            : 
     982                 :    3661260 :   if (dump_file && (dump_flags & TDF_DETAILS))
     983                 :        106 :     fprintf (dump_file, "Basic block %d (loop %d -- depth %d):\n\n",
     984                 :            :              bb->index, bb->loop_father->num, loop_depth (bb->loop_father));
     985                 :            : 
     986                 :            :   /* Look at PHI nodes, but only if there is at most two.
     987                 :            :      ???  We could relax this further by post-processing the inserted
     988                 :            :      code and transforming adjacent cond-exprs with the same predicate
     989                 :            :      to control flow again.  */
     990                 :    3661260 :   bsi = gsi_start_phis (bb);
     991                 :    3661260 :   if (!gsi_end_p (bsi)
     992                 :    3661260 :       && ((gsi_next (&bsi), gsi_end_p (bsi))
     993                 :     721762 :           || (gsi_next (&bsi), gsi_end_p (bsi))))
     994                 :    2433570 :     for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
     995                 :            :       {
     996                 :    1431820 :         stmt = gsi_stmt (bsi);
     997                 :            : 
     998                 :    1431820 :         pos = movement_possibility (stmt);
     999                 :    1431820 :         if (pos == MOVE_IMPOSSIBLE)
    1000                 :     730782 :           continue;
    1001                 :            : 
    1002                 :     701037 :         lim_data = get_lim_data (stmt);
    1003                 :     701037 :         if (! lim_data)
    1004                 :     701037 :           lim_data = init_lim_data (stmt);
    1005                 :     701037 :         lim_data->always_executed_in = outermost;
    1006                 :            : 
    1007                 :     701037 :         if (!determine_max_movement (stmt, false))
    1008                 :            :           {
    1009                 :     698997 :             lim_data->max_loop = NULL;
    1010                 :     698997 :             continue;
    1011                 :            :           }
    1012                 :            : 
    1013                 :       2040 :         if (dump_file && (dump_flags & TDF_DETAILS))
    1014                 :            :           {
    1015                 :          2 :             print_gimple_stmt (dump_file, stmt, 2);
    1016                 :          2 :             fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
    1017                 :          2 :                      loop_depth (lim_data->max_loop),
    1018                 :            :                      lim_data->cost);
    1019                 :            :           }
    1020                 :            : 
    1021                 :       2040 :         if (lim_data->cost >= LIM_EXPENSIVE)
    1022                 :       1373 :           set_profitable_level (stmt);
    1023                 :            :       }
    1024                 :            : 
    1025                 :   33510100 :   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
    1026                 :            :     {
    1027                 :   26187500 :       stmt = gsi_stmt (bsi);
    1028                 :            : 
    1029                 :   26187500 :       pos = movement_possibility (stmt);
    1030                 :   26187500 :       if (pos == MOVE_IMPOSSIBLE)
    1031                 :            :         {
    1032                 :   19975100 :           if (nonpure_call_p (stmt))
    1033                 :            :             {
    1034                 :            :               maybe_never = true;
    1035                 :            :               outermost = NULL;
    1036                 :            :             }
    1037                 :            :           /* Make sure to note always_executed_in for stores to make
    1038                 :            :              store-motion work.  */
    1039                 :   18282300 :           else if (stmt_makes_single_store (stmt))
    1040                 :            :             {
    1041                 :    1796140 :               struct lim_aux_data *lim_data = get_lim_data (stmt);
    1042                 :    1796140 :               if (! lim_data)
    1043                 :          0 :                 lim_data = init_lim_data (stmt);
    1044                 :    1796140 :               lim_data->always_executed_in = outermost;
    1045                 :            :             }
    1046                 :   19127600 :           continue;
    1047                 :            :         }
    1048                 :            : 
    1049                 :    7059980 :       if (is_gimple_assign (stmt)
    1050                 :    7059980 :           && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
    1051                 :            :               == GIMPLE_BINARY_RHS))
    1052                 :            :         {
    1053                 :    3314290 :           tree op0 = gimple_assign_rhs1 (stmt);
    1054                 :    3314290 :           tree op1 = gimple_assign_rhs2 (stmt);
    1055                 :    6628580 :           class loop *ol1 = outermost_invariant_loop (op1,
    1056                 :            :                                         loop_containing_stmt (stmt));
    1057                 :            : 
    1058                 :            :           /* If divisor is invariant, convert a/b to a*(1/b), allowing reciprocal
    1059                 :            :              to be hoisted out of loop, saving expensive divide.  */
    1060                 :    3314290 :           if (pos == MOVE_POSSIBLE
    1061                 :    3088700 :               && gimple_assign_rhs_code (stmt) == RDIV_EXPR
    1062                 :        534 :               && flag_unsafe_math_optimizations
    1063                 :        352 :               && !flag_trapping_math
    1064                 :        352 :               && ol1 != NULL
    1065                 :    3314320 :               && outermost_invariant_loop (op0, ol1) == NULL)
    1066                 :         16 :             stmt = rewrite_reciprocal (&bsi);
    1067                 :            : 
    1068                 :            :           /* If the shift count is invariant, convert (A >> B) & 1 to
    1069                 :            :              A & (1 << B) allowing the bit mask to be hoisted out of the loop
    1070                 :            :              saving an expensive shift.  */
    1071                 :    3314290 :           if (pos == MOVE_POSSIBLE
    1072                 :    3088700 :               && gimple_assign_rhs_code (stmt) == BIT_AND_EXPR
    1073                 :     111330 :               && integer_onep (op1)
    1074                 :       9052 :               && TREE_CODE (op0) == SSA_NAME
    1075                 :    3323340 :               && has_single_use (op0))
    1076                 :       4901 :             stmt = rewrite_bittest (&bsi);
    1077                 :            :         }
    1078                 :            : 
    1079                 :    7059980 :       lim_data = get_lim_data (stmt);
    1080                 :    7059980 :       if (! lim_data)
    1081                 :    5363860 :         lim_data = init_lim_data (stmt);
    1082                 :    7059980 :       lim_data->always_executed_in = outermost;
    1083                 :            : 
    1084                 :    7059980 :       if (maybe_never && pos == MOVE_PRESERVE_EXECUTION)
    1085                 :     595812 :         continue;
    1086                 :            : 
    1087                 :    6464160 :       if (!determine_max_movement (stmt, pos == MOVE_PRESERVE_EXECUTION))
    1088                 :            :         {
    1089                 :    5867320 :           lim_data->max_loop = NULL;
    1090                 :    5867320 :           continue;
    1091                 :            :         }
    1092                 :            : 
    1093                 :     596847 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1094                 :            :         {
    1095                 :        109 :           print_gimple_stmt (dump_file, stmt, 2);
    1096                 :        109 :           fprintf (dump_file, "  invariant up to level %d, cost %d.\n\n",
    1097                 :        109 :                    loop_depth (lim_data->max_loop),
    1098                 :            :                    lim_data->cost);
    1099                 :            :         }
    1100                 :            : 
    1101                 :     596847 :       if (lim_data->cost >= LIM_EXPENSIVE)
    1102                 :     231125 :         set_profitable_level (stmt);
    1103                 :            :     }
    1104                 :            :   return NULL;
    1105                 :            : }
    1106                 :            : 
    1107                 :            : /* Hoist the statements in basic block BB out of the loops prescribed by
    1108                 :            :    data stored in LIM_DATA structures associated with each statement.  Callback
    1109                 :            :    for walk_dominator_tree.  */
    1110                 :            : 
    1111                 :            : unsigned int
    1112                 :    8725730 : move_computations_worker (basic_block bb)
    1113                 :            : {
    1114                 :    8725730 :   class loop *level;
    1115                 :    8725730 :   unsigned cost = 0;
    1116                 :    8725730 :   struct lim_aux_data *lim_data;
    1117                 :    8725730 :   unsigned int todo = 0;
    1118                 :            : 
    1119                 :   12391700 :   if (!loop_outer (bb->loop_father))
    1120                 :            :     return todo;
    1121                 :            : 
    1122                 :    6280180 :   for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (bsi); )
    1123                 :            :     {
    1124                 :    2614260 :       gassign *new_stmt;
    1125                 :    2614260 :       gphi *stmt = bsi.phi ();
    1126                 :            : 
    1127                 :    2614260 :       lim_data = get_lim_data (stmt);
    1128                 :    2614260 :       if (lim_data == NULL)
    1129                 :            :         {
    1130                 :    1913220 :           gsi_next (&bsi);
    1131                 :    1913220 :           continue;
    1132                 :            :         }
    1133                 :            : 
    1134                 :     701037 :       cost = lim_data->cost;
    1135                 :     701037 :       level = lim_data->tgt_loop;
    1136                 :     701037 :       clear_lim_data (stmt);
    1137                 :            : 
    1138                 :     701037 :       if (!level)
    1139                 :            :         {
    1140                 :     699638 :           gsi_next (&bsi);
    1141                 :     699638 :           continue;
    1142                 :            :         }
    1143                 :            : 
    1144                 :       1399 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1145                 :            :         {
    1146                 :          2 :           fprintf (dump_file, "Moving PHI node\n");
    1147                 :          2 :           print_gimple_stmt (dump_file, stmt, 0);
    1148                 :          2 :           fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
    1149                 :            :                    cost, level->num);
    1150                 :            :         }
    1151                 :            : 
    1152                 :       1399 :       if (gimple_phi_num_args (stmt) == 1)
    1153                 :            :         {
    1154                 :         26 :           tree arg = PHI_ARG_DEF (stmt, 0);
    1155                 :         26 :           new_stmt = gimple_build_assign (gimple_phi_result (stmt),
    1156                 :         26 :                                           TREE_CODE (arg), arg);
    1157                 :            :         }
    1158                 :            :       else
    1159                 :            :         {
    1160                 :       1373 :           basic_block dom = get_immediate_dominator (CDI_DOMINATORS, bb);
    1161                 :       2746 :           gimple *cond = gsi_stmt (gsi_last_bb (dom));
    1162                 :       1373 :           tree arg0 = NULL_TREE, arg1 = NULL_TREE, t;
    1163                 :            :           /* Get the PHI arguments corresponding to the true and false
    1164                 :            :              edges of COND.  */
    1165                 :       1373 :           extract_true_false_args_from_phi (dom, stmt, &arg0, &arg1);
    1166                 :       1373 :           gcc_assert (arg0 && arg1);
    1167                 :       1373 :           t = build2 (gimple_cond_code (cond), boolean_type_node,
    1168                 :            :                       gimple_cond_lhs (cond), gimple_cond_rhs (cond));
    1169                 :       1373 :           new_stmt = gimple_build_assign (gimple_phi_result (stmt),
    1170                 :            :                                           COND_EXPR, t, arg0, arg1);
    1171                 :       1373 :           todo |= TODO_cleanup_cfg;
    1172                 :            :         }
    1173                 :       2776 :       if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (new_stmt)))
    1174                 :       2666 :           && (!ALWAYS_EXECUTED_IN (bb)
    1175                 :        690 :               || (ALWAYS_EXECUTED_IN (bb) != level
    1176                 :        102 :                   && !flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
    1177                 :            :         {
    1178                 :        696 :           tree lhs = gimple_assign_lhs (new_stmt);
    1179                 :        696 :           SSA_NAME_RANGE_INFO (lhs) = NULL;
    1180                 :            :         }
    1181                 :       1399 :       gsi_insert_on_edge (loop_preheader_edge (level), new_stmt);
    1182                 :       1399 :       remove_phi_node (&bsi, false);
    1183                 :            :     }
    1184                 :            : 
    1185                 :   33575200 :   for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (bsi); )
    1186                 :            :     {
    1187                 :   26243400 :       edge e;
    1188                 :            : 
    1189                 :   26243400 :       gimple *stmt = gsi_stmt (bsi);
    1190                 :            : 
    1191                 :   26243400 :       lim_data = get_lim_data (stmt);
    1192                 :   26243400 :       if (lim_data == NULL)
    1193                 :            :         {
    1194                 :   16210100 :           gsi_next (&bsi);
    1195                 :   16210100 :           continue;
    1196                 :            :         }
    1197                 :            : 
    1198                 :   10033300 :       cost = lim_data->cost;
    1199                 :   10033300 :       level = lim_data->tgt_loop;
    1200                 :   10033300 :       clear_lim_data (stmt);
    1201                 :            : 
    1202                 :   10033300 :       if (!level)
    1203                 :            :         {
    1204                 :    9655110 :           gsi_next (&bsi);
    1205                 :    9655110 :           continue;
    1206                 :            :         }
    1207                 :            : 
    1208                 :            :       /* We do not really want to move conditionals out of the loop; we just
    1209                 :            :          placed it here to force its operands to be moved if necessary.  */
    1210                 :     378195 :       if (gimple_code (stmt) == GIMPLE_COND)
    1211                 :      10672 :         continue;
    1212                 :            : 
    1213                 :     367523 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1214                 :            :         {
    1215                 :        146 :           fprintf (dump_file, "Moving statement\n");
    1216                 :        146 :           print_gimple_stmt (dump_file, stmt, 0);
    1217                 :        146 :           fprintf (dump_file, "(cost %u) out of loop %d.\n\n",
    1218                 :            :                    cost, level->num);
    1219                 :            :         }
    1220                 :            : 
    1221                 :     367523 :       e = loop_preheader_edge (level);
    1222                 :     735046 :       gcc_assert (!gimple_vdef (stmt));
    1223                 :     735046 :       if (gimple_vuse (stmt))
    1224                 :            :         {
    1225                 :            :           /* The new VUSE is the one from the virtual PHI in the loop
    1226                 :            :              header or the one already present.  */
    1227                 :      65623 :           gphi_iterator gsi2;
    1228                 :      65623 :           for (gsi2 = gsi_start_phis (e->dest);
    1229                 :     151489 :                !gsi_end_p (gsi2); gsi_next (&gsi2))
    1230                 :            :             {
    1231                 :     138482 :               gphi *phi = gsi2.phi ();
    1232                 :     276964 :               if (virtual_operand_p (gimple_phi_result (phi)))
    1233                 :            :                 {
    1234                 :      52616 :                   SET_USE (gimple_vuse_op (stmt),
    1235                 :            :                            PHI_ARG_DEF_FROM_EDGE (phi, e));
    1236                 :      52616 :                   break;
    1237                 :            :                 }
    1238                 :            :             }
    1239                 :            :         }
    1240                 :     367523 :       gsi_remove (&bsi, false);
    1241                 :     367523 :       if (gimple_has_lhs (stmt)
    1242                 :     367523 :           && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME
    1243                 :     337747 :           && INTEGRAL_TYPE_P (TREE_TYPE (gimple_get_lhs (stmt)))
    1244                 :     279002 :           && (!ALWAYS_EXECUTED_IN (bb)
    1245                 :     126704 :               || !(ALWAYS_EXECUTED_IN (bb) == level
    1246                 :      24127 :                    || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
    1247                 :            :         {
    1248                 :     190230 :           tree lhs = gimple_get_lhs (stmt);
    1249                 :     190230 :           SSA_NAME_RANGE_INFO (lhs) = NULL;
    1250                 :            :         }
    1251                 :            :       /* In case this is a stmt that is not unconditionally executed
    1252                 :            :          when the target loop header is executed and the stmt may
    1253                 :            :          invoke undefined integer or pointer overflow rewrite it to
    1254                 :            :          unsigned arithmetic.  */
    1255                 :     367523 :       if (is_gimple_assign (stmt)
    1256                 :     366941 :           && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (stmt)))
    1257                 :     303881 :           && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (gimple_assign_lhs (stmt)))
    1258                 :      94144 :           && arith_code_with_undefined_signed_overflow
    1259                 :      94144 :                (gimple_assign_rhs_code (stmt))
    1260                 :     717782 :           && (!ALWAYS_EXECUTED_IN (bb)
    1261                 :      38651 :               || !(ALWAYS_EXECUTED_IN (bb) == level
    1262                 :      10717 :                    || flow_loop_nested_p (ALWAYS_EXECUTED_IN (bb), level))))
    1263                 :      24833 :         gsi_insert_seq_on_edge (e, rewrite_to_defined_overflow (stmt));
    1264                 :            :       else
    1265                 :     342690 :         gsi_insert_on_edge (e, stmt);
    1266                 :            :     }
    1267                 :            : 
    1268                 :    3665920 :   return todo;
    1269                 :            : }
    1270                 :            : 
    1271                 :            : /* Hoist the statements out of the loops prescribed by data stored in
    1272                 :            :    LIM_DATA structures associated with each statement.*/
    1273                 :            : 
    1274                 :            : static unsigned int
    1275                 :     316604 : move_computations (void)
    1276                 :            : {
    1277                 :     316604 :   int *rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
    1278                 :     316604 :   int n = pre_and_rev_post_order_compute_fn (cfun, NULL, rpo, false);
    1279                 :     316604 :   unsigned todo = 0;
    1280                 :            : 
    1281                 :    9042330 :   for (int i = 0; i < n; ++i)
    1282                 :    8725730 :     todo |= move_computations_worker (BASIC_BLOCK_FOR_FN (cfun, rpo[i]));
    1283                 :            : 
    1284                 :     316604 :   free (rpo);
    1285                 :            : 
    1286                 :     316604 :   gsi_commit_edge_inserts ();
    1287                 :     316604 :   if (need_ssa_update_p (cfun))
    1288                 :      11263 :     rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
    1289                 :            : 
    1290                 :     316604 :   return todo;
    1291                 :            : }
    1292                 :            : 
    1293                 :            : /* Checks whether the statement defining variable *INDEX can be hoisted
    1294                 :            :    out of the loop passed in DATA.  Callback for for_each_index.  */
    1295                 :            : 
    1296                 :            : static bool
    1297                 :    1061900 : may_move_till (tree ref, tree *index, void *data)
    1298                 :            : {
    1299                 :    1061900 :   class loop *loop = (class loop *) data, *max_loop;
    1300                 :            : 
    1301                 :            :   /* If REF is an array reference, check also that the step and the lower
    1302                 :            :      bound is invariant in LOOP.  */
    1303                 :    1061900 :   if (TREE_CODE (ref) == ARRAY_REF)
    1304                 :            :     {
    1305                 :     323400 :       tree step = TREE_OPERAND (ref, 3);
    1306                 :     323400 :       tree lbound = TREE_OPERAND (ref, 2);
    1307                 :            : 
    1308                 :     323400 :       max_loop = outermost_invariant_loop (step, loop);
    1309                 :     323400 :       if (!max_loop)
    1310                 :            :         return false;
    1311                 :            : 
    1312                 :     323400 :       max_loop = outermost_invariant_loop (lbound, loop);
    1313                 :     323400 :       if (!max_loop)
    1314                 :            :         return false;
    1315                 :            :     }
    1316                 :            : 
    1317                 :    1061900 :   max_loop = outermost_invariant_loop (*index, loop);
    1318                 :    1061900 :   if (!max_loop)
    1319                 :     714337 :     return false;
    1320                 :            : 
    1321                 :            :   return true;
    1322                 :            : }
    1323                 :            : 
    1324                 :            : /* If OP is SSA NAME, force the statement that defines it to be
    1325                 :            :    moved out of the LOOP.  ORIG_LOOP is the loop in that EXPR is used.  */
    1326                 :            : 
    1327                 :            : static void
    1328                 :      33597 : force_move_till_op (tree op, class loop *orig_loop, class loop *loop)
    1329                 :            : {
    1330                 :      33597 :   gimple *stmt;
    1331                 :            : 
    1332                 :      33597 :   if (!op
    1333                 :      33597 :       || is_gimple_min_invariant (op))
    1334                 :      30524 :     return;
    1335                 :            : 
    1336                 :       3073 :   gcc_assert (TREE_CODE (op) == SSA_NAME);
    1337                 :            : 
    1338                 :       3073 :   stmt = SSA_NAME_DEF_STMT (op);
    1339                 :       3073 :   if (gimple_nop_p (stmt))
    1340                 :            :     return;
    1341                 :            : 
    1342                 :       2011 :   set_level (stmt, orig_loop, loop);
    1343                 :            : }
    1344                 :            : 
    1345                 :            : /* Forces statement defining invariants in REF (and *INDEX) to be moved out of
    1346                 :            :    the LOOP.  The reference REF is used in the loop ORIG_LOOP.  Callback for
    1347                 :            :    for_each_index.  */
    1348                 :            : 
    1349                 :            : struct fmt_data
    1350                 :            : {
    1351                 :            :   class loop *loop;
    1352                 :            :   class loop *orig_loop;
    1353                 :            : };
    1354                 :            : 
    1355                 :            : static bool
    1356                 :      14829 : force_move_till (tree ref, tree *index, void *data)
    1357                 :            : {
    1358                 :      14829 :   struct fmt_data *fmt_data = (struct fmt_data *) data;
    1359                 :            : 
    1360                 :      14829 :   if (TREE_CODE (ref) == ARRAY_REF)
    1361                 :            :     {
    1362                 :       9384 :       tree step = TREE_OPERAND (ref, 3);
    1363                 :       9384 :       tree lbound = TREE_OPERAND (ref, 2);
    1364                 :            : 
    1365                 :       9384 :       force_move_till_op (step, fmt_data->orig_loop, fmt_data->loop);
    1366                 :       9384 :       force_move_till_op (lbound, fmt_data->orig_loop, fmt_data->loop);
    1367                 :            :     }
    1368                 :            : 
    1369                 :      14829 :   force_move_till_op (*index, fmt_data->orig_loop, fmt_data->loop);
    1370                 :            : 
    1371                 :      14829 :   return true;
    1372                 :            : }
    1373                 :            : 
    1374                 :            : /* A function to free the mem_ref object OBJ.  */
    1375                 :            : 
    1376                 :            : static void
    1377                 :    3100920 : memref_free (class im_mem_ref *mem)
    1378                 :            : {
    1379                 :          0 :   mem->accesses_in_loop.release ();
    1380                 :          0 : }
    1381                 :            : 
    1382                 :            : /* Allocates and returns a memory reference description for MEM whose hash
    1383                 :            :    value is HASH and id is ID.  */
    1384                 :            : 
    1385                 :            : static im_mem_ref *
    1386                 :    3100920 : mem_ref_alloc (ao_ref *mem, unsigned hash, unsigned id)
    1387                 :            : {
    1388                 :    3100920 :   im_mem_ref *ref = XOBNEW (&mem_ref_obstack, class im_mem_ref);
    1389                 :    3100920 :   if (mem)
    1390                 :    2784310 :     ref->mem = *mem;
    1391                 :            :   else
    1392                 :     316604 :     ao_ref_init (&ref->mem, error_mark_node);
    1393                 :    3100920 :   ref->id = id;
    1394                 :    3100920 :   ref->ref_canonical = false;
    1395                 :    3100920 :   ref->ref_decomposed = false;
    1396                 :    3100920 :   ref->hash = hash;
    1397                 :    3100920 :   ref->stored = NULL;
    1398                 :    3100920 :   bitmap_initialize (&ref->indep_loop, &lim_bitmap_obstack);
    1399                 :    3100920 :   bitmap_initialize (&ref->dep_loop, &lim_bitmap_obstack);
    1400                 :    3100920 :   ref->accesses_in_loop.create (1);
    1401                 :            : 
    1402                 :    3100920 :   return ref;
    1403                 :            : }
    1404                 :            : 
    1405                 :            : /* Records memory reference location *LOC in LOOP to the memory reference
    1406                 :            :    description REF.  The reference occurs in statement STMT.  */
    1407                 :            : 
    1408                 :            : static void
    1409                 :    3353600 : record_mem_ref_loc (im_mem_ref *ref, gimple *stmt, tree *loc)
    1410                 :            : {
    1411                 :    3353600 :   mem_ref_loc aref;
    1412                 :    3353600 :   aref.stmt = stmt;
    1413                 :    3353600 :   aref.ref = loc;
    1414                 :          0 :   ref->accesses_in_loop.safe_push (aref);
    1415                 :          0 : }
    1416                 :            : 
    1417                 :            : /* Set the LOOP bit in REF stored bitmap and allocate that if
    1418                 :            :    necessary.  Return whether a bit was changed.  */
    1419                 :            : 
    1420                 :            : static bool
    1421                 :    3114880 : set_ref_stored_in_loop (im_mem_ref *ref, class loop *loop)
    1422                 :            : {
    1423                 :    3114880 :   if (!ref->stored)
    1424                 :    1429760 :     ref->stored = BITMAP_ALLOC (&lim_bitmap_obstack);
    1425                 :    3114880 :   return bitmap_set_bit (ref->stored, loop->num);
    1426                 :            : }
    1427                 :            : 
    1428                 :            : /* Marks reference REF as stored in LOOP.  */
    1429                 :            : 
    1430                 :            : static void
    1431                 :    2653620 : mark_ref_stored (im_mem_ref *ref, class loop *loop)
    1432                 :            : {
    1433                 :    4659270 :   while (loop != current_loops->tree_root
    1434                 :    4659270 :          && set_ref_stored_in_loop (ref, loop))
    1435                 :    2005660 :     loop = loop_outer (loop);
    1436                 :    2653620 : }
    1437                 :            : 
    1438                 :            : /* Gathers memory references in statement STMT in LOOP, storing the
    1439                 :            :    information about them in the memory_accesses structure.  Marks
    1440                 :            :    the vops accessed through unrecognized statements there as
    1441                 :            :    well.  */
    1442                 :            : 
    1443                 :            : static void
    1444                 :   26187500 : gather_mem_refs_stmt (class loop *loop, gimple *stmt)
    1445                 :            : {
    1446                 :   26187500 :   tree *mem = NULL;
    1447                 :   26187500 :   hashval_t hash;
    1448                 :   26187500 :   im_mem_ref **slot;
    1449                 :   26187500 :   im_mem_ref *ref;
    1450                 :   26187500 :   bool is_stored;
    1451                 :   26187500 :   unsigned id;
    1452                 :            : 
    1453                 :   36017200 :   if (!gimple_vuse (stmt))
    1454                 :            :     return;
    1455                 :            : 
    1456                 :    4639670 :   mem = simple_mem_ref_in_stmt (stmt, &is_stored);
    1457                 :    4639670 :   if (!mem)
    1458                 :            :     {
    1459                 :            :       /* We use the shared mem_ref for all unanalyzable refs.  */
    1460                 :    1286080 :       id = UNANALYZABLE_MEM_ID;
    1461                 :    1286080 :       ref = memory_accesses.refs_list[id];
    1462                 :    1286080 :       if (dump_file && (dump_flags & TDF_DETAILS))
    1463                 :            :         {
    1464                 :          5 :           fprintf (dump_file, "Unanalyzed memory reference %u: ", id);
    1465                 :          5 :           print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
    1466                 :            :         }
    1467                 :    2572150 :       is_stored = gimple_vdef (stmt);
    1468                 :            :     }
    1469                 :            :   else
    1470                 :            :     {
    1471                 :            :       /* We are looking for equal refs that might differ in structure
    1472                 :            :          such as a.b vs. MEM[&a + 4].  So we key off the ao_ref but
    1473                 :            :          make sure we can canonicalize the ref in the hashtable if
    1474                 :            :          non-operand_equal_p refs are found.  For the lookup we mark
    1475                 :            :          the case we want strict equality with aor.max_size == -1.  */
    1476                 :    3353600 :       ao_ref aor;
    1477                 :    3353600 :       ao_ref_init (&aor, *mem);
    1478                 :    3353600 :       ao_ref_base (&aor);
    1479                 :    3353600 :       ao_ref_alias_set (&aor);
    1480                 :    3353600 :       HOST_WIDE_INT offset, size, max_size;
    1481                 :    3353600 :       poly_int64 saved_maxsize = aor.max_size, mem_off;
    1482                 :    3353600 :       tree mem_base;
    1483                 :    3353600 :       bool ref_decomposed;
    1484                 :    3353600 :       if (aor.max_size_known_p ()
    1485                 :    3238940 :           && aor.offset.is_constant (&offset)
    1486                 :    3238940 :           && aor.size.is_constant (&size)
    1487                 :    3238940 :           && aor.max_size.is_constant (&max_size)
    1488                 :    3238940 :           && size == max_size
    1489                 :    2846850 :           && (size % BITS_PER_UNIT) == 0
    1490                 :            :           /* We're canonicalizing to a MEM where TYPE_SIZE specifies the
    1491                 :            :              size.  Make sure this is consistent with the extraction.  */
    1492                 :    2845750 :           && poly_int_tree_p (TYPE_SIZE (TREE_TYPE (*mem)))
    1493                 :    6199230 :           && known_eq (wi::to_poly_offset (TYPE_SIZE (TREE_TYPE (*mem))),
    1494                 :            :                        aor.size)
    1495                 :    6199230 :           && (mem_base = get_addr_base_and_unit_offset (aor.ref, &mem_off)))
    1496                 :            :         {
    1497                 :    2841450 :           ref_decomposed = true;
    1498                 :    2841450 :           hash = iterative_hash_expr (ao_ref_base (&aor), 0);
    1499                 :    2841450 :           hash = iterative_hash_host_wide_int (offset, hash);
    1500                 :    2841450 :           hash = iterative_hash_host_wide_int (size, hash);
    1501                 :            :         }
    1502                 :            :       else
    1503                 :            :         {
    1504                 :     512146 :           ref_decomposed = false;
    1505                 :     512146 :           hash = iterative_hash_expr (aor.ref, 0);
    1506                 :     512146 :           aor.max_size = -1;
    1507                 :            :         }
    1508                 :    3353600 :       slot = memory_accesses.refs->find_slot_with_hash (&aor, hash, INSERT);
    1509                 :    3353600 :       aor.max_size = saved_maxsize;
    1510                 :    3353600 :       if (*slot)
    1511                 :            :         {
    1512                 :     569281 :           if (!(*slot)->ref_canonical 
    1513                 :     569281 :               && !operand_equal_p (*mem, (*slot)->mem.ref, 0))
    1514                 :            :             {
    1515                 :            :               /* If we didn't yet canonicalize the hashtable ref (which
    1516                 :            :                  we'll end up using for code insertion) and hit a second
    1517                 :            :                  equal ref that is not structurally equivalent create
    1518                 :            :                  a canonical ref which is a bare MEM_REF.  */
    1519                 :      18952 :               if (TREE_CODE (*mem) == MEM_REF
    1520                 :      18952 :                   || TREE_CODE (*mem) == TARGET_MEM_REF)
    1521                 :            :                 {
    1522                 :       2409 :                   (*slot)->mem.ref = *mem;
    1523                 :       2409 :                   (*slot)->mem.base_alias_set = ao_ref_base_alias_set (&aor);
    1524                 :            :                 }
    1525                 :            :               else
    1526                 :            :                 {
    1527                 :      16543 :                   tree ref_alias_type = reference_alias_ptr_type (*mem);
    1528                 :      16543 :                   unsigned int ref_align = get_object_alignment (*mem);
    1529                 :      16543 :                   tree ref_type = TREE_TYPE (*mem);
    1530                 :      16543 :                   tree tmp = build1 (ADDR_EXPR, ptr_type_node,
    1531                 :            :                                      unshare_expr (mem_base));
    1532                 :      16543 :                   if (TYPE_ALIGN (ref_type) != ref_align)
    1533                 :       1977 :                     ref_type = build_aligned_type (ref_type, ref_align);
    1534                 :      33086 :                   (*slot)->mem.ref
    1535                 :      16543 :                     = fold_build2 (MEM_REF, ref_type, tmp,
    1536                 :            :                                    build_int_cst (ref_alias_type, mem_off));
    1537                 :      16543 :                   if ((*slot)->mem.volatile_p)
    1538                 :        226 :                     TREE_THIS_VOLATILE ((*slot)->mem.ref) = 1;
    1539                 :      16543 :                   gcc_checking_assert (TREE_CODE ((*slot)->mem.ref) == MEM_REF
    1540                 :            :                                        && is_gimple_mem_ref_addr
    1541                 :            :                                             (TREE_OPERAND ((*slot)->mem.ref,
    1542                 :            :                                                            0)));
    1543                 :      16543 :                   (*slot)->mem.base_alias_set = (*slot)->mem.ref_alias_set;
    1544                 :            :                 }
    1545                 :      18952 :               (*slot)->ref_canonical = true;
    1546                 :            :             }
    1547                 :     569281 :           ref = *slot;
    1548                 :     569281 :           id = ref->id;
    1549                 :            :         }
    1550                 :            :       else
    1551                 :            :         {
    1552                 :    2784310 :           id = memory_accesses.refs_list.length ();
    1553                 :    2784310 :           ref = mem_ref_alloc (&aor, hash, id);
    1554                 :    2784310 :           ref->ref_decomposed = ref_decomposed;
    1555                 :    2784310 :           memory_accesses.refs_list.safe_push (ref);
    1556                 :    2784310 :           *slot = ref;
    1557                 :            : 
    1558                 :    2784310 :           if (dump_file && (dump_flags & TDF_DETAILS))
    1559                 :            :             {
    1560                 :        101 :               fprintf (dump_file, "Memory reference %u: ", id);
    1561                 :        101 :               print_generic_expr (dump_file, ref->mem.ref, TDF_SLIM);
    1562                 :        101 :               fprintf (dump_file, "\n");
    1563                 :            :             }
    1564                 :            :         }
    1565                 :            : 
    1566                 :    3353600 :       record_mem_ref_loc (ref, stmt, mem);
    1567                 :            :     }
    1568                 :    4639670 :   bitmap_set_bit (&memory_accesses.refs_in_loop[loop->num], ref->id);
    1569                 :    4639670 :   if (is_stored)
    1570                 :            :     {
    1571                 :    2653620 :       bitmap_set_bit (&memory_accesses.refs_stored_in_loop[loop->num], ref->id);
    1572                 :    2653620 :       mark_ref_stored (ref, loop);
    1573                 :            :     }
    1574                 :    4639670 :   init_lim_data (stmt)->ref = ref->id;
    1575                 :    4639670 :   return;
    1576                 :            : }
    1577                 :            : 
    1578                 :            : static unsigned *bb_loop_postorder;
    1579                 :            : 
    1580                 :            : /* qsort sort function to sort blocks after their loop fathers postorder.  */
    1581                 :            : 
    1582                 :            : static int
    1583                 :   92338200 : sort_bbs_in_loop_postorder_cmp (const void *bb1_, const void *bb2_,
    1584                 :            :                                 void *bb_loop_postorder_)
    1585                 :            : {
    1586                 :   92338200 :   unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
    1587                 :   92338200 :   basic_block bb1 = *(const basic_block *)bb1_;
    1588                 :   92338200 :   basic_block bb2 = *(const basic_block *)bb2_;
    1589                 :   92338200 :   class loop *loop1 = bb1->loop_father;
    1590                 :   92338200 :   class loop *loop2 = bb2->loop_father;
    1591                 :   92338200 :   if (loop1->num == loop2->num)
    1592                 :   48372200 :     return bb1->index - bb2->index;
    1593                 :   43966000 :   return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
    1594                 :            : }
    1595                 :            : 
    1596                 :            : /* qsort sort function to sort ref locs after their loop fathers postorder.  */
    1597                 :            : 
    1598                 :            : static int
    1599                 :    4165390 : sort_locs_in_loop_postorder_cmp (const void *loc1_, const void *loc2_,
    1600                 :            :                                  void *bb_loop_postorder_)
    1601                 :            : {
    1602                 :    4165390 :   unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
    1603                 :    4165390 :   const mem_ref_loc *loc1 = (const mem_ref_loc *)loc1_;
    1604                 :    4165390 :   const mem_ref_loc *loc2 = (const mem_ref_loc *)loc2_;
    1605                 :    4165390 :   class loop *loop1 = gimple_bb (loc1->stmt)->loop_father;
    1606                 :    4165390 :   class loop *loop2 = gimple_bb (loc2->stmt)->loop_father;
    1607                 :    4165390 :   if (loop1->num == loop2->num)
    1608                 :            :     return 0;
    1609                 :    1374550 :   return bb_loop_postorder[loop1->num] < bb_loop_postorder[loop2->num] ? -1 : 1;
    1610                 :            : }
    1611                 :            : 
    1612                 :            : /* Gathers memory references in loops.  */
    1613                 :            : 
    1614                 :            : static void
    1615                 :     316604 : analyze_memory_references (void)
    1616                 :            : {
    1617                 :     316604 :   gimple_stmt_iterator bsi;
    1618                 :     316604 :   basic_block bb, *bbs;
    1619                 :     316604 :   class loop *loop, *outer;
    1620                 :     316604 :   unsigned i, n;
    1621                 :            : 
    1622                 :            :   /* Collect all basic-blocks in loops and sort them after their
    1623                 :            :      loops postorder.  */
    1624                 :     316604 :   i = 0;
    1625                 :     316604 :   bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
    1626                 :    9006050 :   FOR_EACH_BB_FN (bb, cfun)
    1627                 :    8689440 :     if (bb->loop_father != current_loops->tree_root)
    1628                 :    3661260 :       bbs[i++] = bb;
    1629                 :     316604 :   n = i;
    1630                 :     316604 :   gcc_sort_r (bbs, n, sizeof (basic_block), sort_bbs_in_loop_postorder_cmp,
    1631                 :            :               bb_loop_postorder);
    1632                 :            : 
    1633                 :            :   /* Visit blocks in loop postorder and assign mem-ref IDs in that order.
    1634                 :            :      That results in better locality for all the bitmaps.  */
    1635                 :    3977870 :   for (i = 0; i < n; ++i)
    1636                 :            :     {
    1637                 :    3661260 :       basic_block bb = bbs[i];
    1638                 :   33510000 :       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
    1639                 :   26187500 :         gather_mem_refs_stmt (bb->loop_father, gsi_stmt (bsi));
    1640                 :            :     }
    1641                 :            : 
    1642                 :            :   /* Sort the location list of gathered memory references after their
    1643                 :            :      loop postorder number.  */
    1644                 :            :   im_mem_ref *ref;
    1645                 :    3417520 :   FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
    1646                 :    6201840 :     ref->accesses_in_loop.sort (sort_locs_in_loop_postorder_cmp,
    1647                 :            :                                 bb_loop_postorder);
    1648                 :            : 
    1649                 :     316604 :   free (bbs);
    1650                 :            : 
    1651                 :            :   /* Propagate the information about accessed memory references up
    1652                 :            :      the loop hierarchy.  */
    1653                 :    1046390 :   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
    1654                 :            :     {
    1655                 :            :       /* Finalize the overall touched references (including subloops).  */
    1656                 :     729787 :       bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[loop->num],
    1657                 :     729787 :                        &memory_accesses.refs_stored_in_loop[loop->num]);
    1658                 :            : 
    1659                 :            :       /* Propagate the information about accessed memory references up
    1660                 :            :          the loop hierarchy.  */
    1661                 :     729787 :       outer = loop_outer (loop);
    1662                 :     729787 :       if (outer == current_loops->tree_root)
    1663                 :     550753 :         continue;
    1664                 :            : 
    1665                 :     179034 :       bitmap_ior_into (&memory_accesses.all_refs_stored_in_loop[outer->num],
    1666                 :     179034 :                        &memory_accesses.all_refs_stored_in_loop[loop->num]);
    1667                 :            :     }
    1668                 :     316604 : }
    1669                 :            : 
    1670                 :            : /* Returns true if MEM1 and MEM2 may alias.  TTAE_CACHE is used as a cache in
    1671                 :            :    tree_to_aff_combination_expand.  */
    1672                 :            : 
    1673                 :            : static bool
    1674                 :     294222 : mem_refs_may_alias_p (im_mem_ref *mem1, im_mem_ref *mem2,
    1675                 :            :                       hash_map<tree, name_expansion *> **ttae_cache)
    1676                 :            : {
    1677                 :            :   /* Perform BASE + OFFSET analysis -- if MEM1 and MEM2 are based on the same
    1678                 :            :      object and their offset differ in such a way that the locations cannot
    1679                 :            :      overlap, then they cannot alias.  */
    1680                 :     294222 :   poly_widest_int size1, size2;
    1681                 :     294222 :   aff_tree off1, off2;
    1682                 :            : 
    1683                 :            :   /* Perform basic offset and type-based disambiguation.  */
    1684                 :     294222 :   if (!refs_may_alias_p_1 (&mem1->mem, &mem2->mem, true))
    1685                 :            :     return false;
    1686                 :            : 
    1687                 :            :   /* The expansion of addresses may be a bit expensive, thus we only do
    1688                 :            :      the check at -O2 and higher optimization levels.  */
    1689                 :      24669 :   if (optimize < 2)
    1690                 :            :     return true;
    1691                 :            : 
    1692                 :      20475 :   get_inner_reference_aff (mem1->mem.ref, &off1, &size1);
    1693                 :      20475 :   get_inner_reference_aff (mem2->mem.ref, &off2, &size2);
    1694                 :      20475 :   aff_combination_expand (&off1, ttae_cache);
    1695                 :      20475 :   aff_combination_expand (&off2, ttae_cache);
    1696                 :      20475 :   aff_combination_scale (&off1, -1);
    1697                 :      20475 :   aff_combination_add (&off2, &off1);
    1698                 :            : 
    1699                 :      20475 :   if (aff_comb_cannot_overlap_p (&off2, size1, size2))
    1700                 :       1003 :     return false;
    1701                 :            : 
    1702                 :            :   return true;
    1703                 :            : }
    1704                 :            : 
    1705                 :            : /* Compare function for bsearch searching for reference locations
    1706                 :            :    in a loop.  */
    1707                 :            : 
    1708                 :            : static int
    1709                 :     130737 : find_ref_loc_in_loop_cmp (const void *loop_, const void *loc_,
    1710                 :            :                           void *bb_loop_postorder_)
    1711                 :            : {
    1712                 :     130737 :   unsigned *bb_loop_postorder = (unsigned *)bb_loop_postorder_;
    1713                 :     130737 :   class loop *loop = (class loop *)const_cast<void *>(loop_);
    1714                 :     130737 :   mem_ref_loc *loc = (mem_ref_loc *)const_cast<void *>(loc_);
    1715                 :     130737 :   class loop *loc_loop = gimple_bb (loc->stmt)->loop_father;
    1716                 :     130737 :   if (loop->num  == loc_loop->num
    1717                 :     130737 :       || flow_loop_nested_p (loop, loc_loop))
    1718                 :     104558 :     return 0;
    1719                 :      26179 :   return (bb_loop_postorder[loop->num] < bb_loop_postorder[loc_loop->num]
    1720                 :      26179 :           ? -1 : 1);
    1721                 :            : }
    1722                 :            : 
    1723                 :            : /* Iterates over all locations of REF in LOOP and its subloops calling
    1724                 :            :    fn.operator() with the location as argument.  When that operator
    1725                 :            :    returns true the iteration is stopped and true is returned.
    1726                 :            :    Otherwise false is returned.  */
    1727                 :            : 
    1728                 :            : template <typename FN>
    1729                 :            : static bool
    1730                 :     104558 : for_all_locs_in_loop (class loop *loop, im_mem_ref *ref, FN fn)
    1731                 :            : {
    1732                 :            :   unsigned i;
    1733                 :            :   mem_ref_loc *loc;
    1734                 :            : 
    1735                 :            :   /* Search for the cluster of locs in the accesses_in_loop vector
    1736                 :            :      which is sorted after postorder index of the loop father.  */
    1737                 :     104558 :   loc = ref->accesses_in_loop.bsearch (loop, find_ref_loc_in_loop_cmp,
    1738                 :            :                                        bb_loop_postorder);
    1739                 :     104558 :   if (!loc)
    1740                 :            :     return false;
    1741                 :            : 
    1742                 :            :   /* We have found one location inside loop or its sub-loops.  Iterate
    1743                 :            :      both forward and backward to cover the whole cluster.  */
    1744                 :     209116 :   i = loc - ref->accesses_in_loop.address ();
    1745                 :     161922 :   while (i > 0)
    1746                 :            :     {
    1747                 :      81497 :       --i;
    1748                 :      81497 :       mem_ref_loc *l = &ref->accesses_in_loop[i];
    1749                 :      81497 :       if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
    1750                 :            :         break;
    1751                 :      71334 :       if (fn (l))
    1752                 :            :         return true;
    1753                 :            :     }
    1754                 :     264263 :   for (i = loc - ref->accesses_in_loop.address ();
    1755                 :     347350 :        i < ref->accesses_in_loop.length (); ++i)
    1756                 :            :     {
    1757                 :     120975 :       mem_ref_loc *l = &ref->accesses_in_loop[i];
    1758                 :     120975 :       if (!flow_bb_inside_loop_p (loop, gimple_bb (l->stmt)))
    1759                 :            :         break;
    1760                 :     111195 :       if (fn (l))
    1761                 :            :         return true;
    1762                 :            :     }
    1763                 :            : 
    1764                 :            :   return false;
    1765                 :            : }
    1766                 :            : 
    1767                 :            : /* Rewrites location LOC by TMP_VAR.  */
    1768                 :            : 
    1769                 :            : class rewrite_mem_ref_loc
    1770                 :            : {
    1771                 :            : public:
    1772                 :      22139 :   rewrite_mem_ref_loc (tree tmp_var_) : tmp_var (tmp_var_) {}
    1773                 :            :   bool operator () (mem_ref_loc *loc);
    1774                 :            :   tree tmp_var;
    1775                 :            : };
    1776                 :            : 
    1777                 :            : bool
    1778                 :      40446 : rewrite_mem_ref_loc::operator () (mem_ref_loc *loc)
    1779                 :            : {
    1780                 :      40446 :   *loc->ref = tmp_var;
    1781                 :      40446 :   update_stmt (loc->stmt);
    1782                 :      40446 :   return false;
    1783                 :            : }
    1784                 :            : 
    1785                 :            : /* Rewrites all references to REF in LOOP by variable TMP_VAR.  */
    1786                 :            : 
    1787                 :            : static void
    1788                 :      22139 : rewrite_mem_refs (class loop *loop, im_mem_ref *ref, tree tmp_var)
    1789                 :            : {
    1790                 :          0 :   for_all_locs_in_loop (loop, ref, rewrite_mem_ref_loc (tmp_var));
    1791                 :          0 : }
    1792                 :            : 
    1793                 :            : /* Stores the first reference location in LOCP.  */
    1794                 :            : 
    1795                 :            : class first_mem_ref_loc_1
    1796                 :            : {
    1797                 :            : public:
    1798                 :      22139 :   first_mem_ref_loc_1 (mem_ref_loc **locp_) : locp (locp_) {}
    1799                 :            :   bool operator () (mem_ref_loc *loc);
    1800                 :            :   mem_ref_loc **locp;
    1801                 :            : };
    1802                 :            : 
    1803                 :            : bool
    1804                 :      22139 : first_mem_ref_loc_1::operator () (mem_ref_loc *loc)
    1805                 :            : {
    1806                 :      22139 :   *locp = loc;
    1807                 :      22139 :   return true;
    1808                 :            : }
    1809                 :            : 
    1810                 :            : /* Returns the first reference location to REF in LOOP.  */
    1811                 :            : 
    1812                 :            : static mem_ref_loc *
    1813                 :      22139 : first_mem_ref_loc (class loop *loop, im_mem_ref *ref)
    1814                 :            : {
    1815                 :      22139 :   mem_ref_loc *locp = NULL;
    1816                 :          0 :   for_all_locs_in_loop (loop, ref, first_mem_ref_loc_1 (&locp));
    1817                 :      22139 :   return locp;
    1818                 :            : }
    1819                 :            : 
    1820                 :            : struct prev_flag_edges {
    1821                 :            :   /* Edge to insert new flag comparison code.  */
    1822                 :            :   edge append_cond_position;
    1823                 :            : 
    1824                 :            :   /* Edge for fall through from previous flag comparison.  */
    1825                 :            :   edge last_cond_fallthru;
    1826                 :            : };
    1827                 :            : 
    1828                 :            : /* Helper function for execute_sm.  Emit code to store TMP_VAR into
    1829                 :            :    MEM along edge EX.
    1830                 :            : 
    1831                 :            :    The store is only done if MEM has changed.  We do this so no
    1832                 :            :    changes to MEM occur on code paths that did not originally store
    1833                 :            :    into it.
    1834                 :            : 
    1835                 :            :    The common case for execute_sm will transform:
    1836                 :            : 
    1837                 :            :      for (...) {
    1838                 :            :        if (foo)
    1839                 :            :          stuff;
    1840                 :            :        else
    1841                 :            :          MEM = TMP_VAR;
    1842                 :            :      }
    1843                 :            : 
    1844                 :            :    into:
    1845                 :            : 
    1846                 :            :      lsm = MEM;
    1847                 :            :      for (...) {
    1848                 :            :        if (foo)
    1849                 :            :          stuff;
    1850                 :            :        else
    1851                 :            :          lsm = TMP_VAR;
    1852                 :            :      }
    1853                 :            :      MEM = lsm;
    1854                 :            : 
    1855                 :            :   This function will generate:
    1856                 :            : 
    1857                 :            :      lsm = MEM;
    1858                 :            : 
    1859                 :            :      lsm_flag = false;
    1860                 :            :      ...
    1861                 :            :      for (...) {
    1862                 :            :        if (foo)
    1863                 :            :          stuff;
    1864                 :            :        else {
    1865                 :            :          lsm = TMP_VAR;
    1866                 :            :          lsm_flag = true;
    1867                 :            :        }
    1868                 :            :      }
    1869                 :            :      if (lsm_flag)      <--
    1870                 :            :        MEM = lsm;       <--
    1871                 :            : */
    1872                 :            : 
    1873                 :            : static void
    1874                 :      12873 : execute_sm_if_changed (edge ex, tree mem, tree tmp_var, tree flag,
    1875                 :            :                        edge preheader, hash_set <basic_block> *flag_bbs)
    1876                 :            : {
    1877                 :      12873 :   basic_block new_bb, then_bb, old_dest;
    1878                 :      12873 :   bool loop_has_only_one_exit;
    1879                 :      12873 :   edge then_old_edge, orig_ex = ex;
    1880                 :      12873 :   gimple_stmt_iterator gsi;
    1881                 :      12873 :   gimple *stmt;
    1882                 :      12873 :   struct prev_flag_edges *prev_edges = (struct prev_flag_edges *) ex->aux;
    1883                 :      12873 :   bool irr = ex->flags & EDGE_IRREDUCIBLE_LOOP;
    1884                 :            : 
    1885                 :      12873 :   profile_count count_sum = profile_count::zero ();
    1886                 :      12873 :   int nbbs = 0, ncount = 0;
    1887                 :      12873 :   profile_probability flag_probability = profile_probability::uninitialized ();
    1888                 :            : 
    1889                 :            :   /* Flag is set in FLAG_BBS. Determine probability that flag will be true
    1890                 :            :      at loop exit.
    1891                 :            : 
    1892                 :            :      This code may look fancy, but it cannot update profile very realistically
    1893                 :            :      because we do not know the probability that flag will be true at given
    1894                 :            :      loop exit.
    1895                 :            : 
    1896                 :            :      We look for two interesting extremes
    1897                 :            :        - when exit is dominated by block setting the flag, we know it will
    1898                 :            :          always be true.  This is a common case.
    1899                 :            :        - when all blocks setting the flag have very low frequency we know
    1900                 :            :          it will likely be false.
    1901                 :            :      In all other cases we default to 2/3 for flag being true.  */
    1902                 :            : 
    1903                 :      41859 :   for (hash_set<basic_block>::iterator it = flag_bbs->begin ();
    1904                 :      28986 :        it != flag_bbs->end (); ++it)
    1905                 :            :     {
    1906                 :      16113 :        if ((*it)->count.initialized_p ())
    1907                 :      16103 :          count_sum += (*it)->count, ncount ++;
    1908                 :      16113 :        if (dominated_by_p (CDI_DOMINATORS, ex->src, *it))
    1909                 :       5969 :          flag_probability = profile_probability::always ();
    1910                 :      16113 :        nbbs++;
    1911                 :            :     }
    1912                 :            : 
    1913                 :      12873 :   profile_probability cap = profile_probability::always ().apply_scale (2, 3);
    1914                 :            : 
    1915                 :      12873 :   if (flag_probability.initialized_p ())
    1916                 :            :     ;
    1917                 :       8503 :   else if (ncount == nbbs
    1918                 :       8520 :            && preheader->count () >= count_sum && preheader->count ().nonzero_p ())
    1919                 :            :     {
    1920                 :        360 :       flag_probability = count_sum.probability_in (preheader->count ());
    1921                 :        360 :       if (flag_probability > cap)
    1922                 :         96 :         flag_probability = cap;
    1923                 :            :     }
    1924                 :            : 
    1925                 :      12873 :   if (!flag_probability.initialized_p ())
    1926                 :       8143 :     flag_probability = cap;
    1927                 :            : 
    1928                 :            :   /* ?? Insert store after previous store if applicable.  See note
    1929                 :            :      below.  */
    1930                 :      12873 :   if (prev_edges)
    1931                 :       5072 :     ex = prev_edges->append_cond_position;
    1932                 :            : 
    1933                 :      12873 :   loop_has_only_one_exit = single_pred_p (ex->dest);
    1934                 :            : 
    1935                 :      12873 :   if (loop_has_only_one_exit)
    1936                 :       3925 :     ex = split_block_after_labels (ex->dest);
    1937                 :            :   else
    1938                 :            :     {
    1939                 :       8948 :       for (gphi_iterator gpi = gsi_start_phis (ex->dest);
    1940                 :      13791 :            !gsi_end_p (gpi); gsi_next (&gpi))
    1941                 :            :         {
    1942                 :       5298 :           gphi *phi = gpi.phi ();
    1943                 :      10596 :           if (virtual_operand_p (gimple_phi_result (phi)))
    1944                 :       4843 :             continue;
    1945                 :            : 
    1946                 :            :           /* When the destination has a non-virtual PHI node with multiple
    1947                 :            :              predecessors make sure we preserve the PHI structure by
    1948                 :            :              forcing a forwarder block so that hoisting of that PHI will
    1949                 :            :              still work.  */
    1950                 :        455 :           split_edge (ex);
    1951                 :        455 :           break;
    1952                 :            :         }
    1953                 :            :     }
    1954                 :            : 
    1955                 :      12873 :   old_dest = ex->dest;
    1956                 :      12873 :   new_bb = split_edge (ex);
    1957                 :      12873 :   then_bb = create_empty_bb (new_bb);
    1958                 :      12873 :   then_bb->count = new_bb->count.apply_probability (flag_probability);
    1959                 :      12873 :   if (irr)
    1960                 :         83 :     then_bb->flags = BB_IRREDUCIBLE_LOOP;
    1961                 :      12873 :   add_bb_to_loop (then_bb, new_bb->loop_father);
    1962                 :            : 
    1963                 :      12873 :   gsi = gsi_start_bb (new_bb);
    1964                 :      12873 :   stmt = gimple_build_cond (NE_EXPR, flag, boolean_false_node,
    1965                 :            :                             NULL_TREE, NULL_TREE);
    1966                 :      12873 :   gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
    1967                 :            : 
    1968                 :      12873 :   gsi = gsi_start_bb (then_bb);
    1969                 :            :   /* Insert actual store.  */
    1970                 :      12873 :   stmt = gimple_build_assign (unshare_expr (mem), tmp_var);
    1971                 :      12873 :   gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
    1972                 :            : 
    1973                 :      12873 :   edge e1 = single_succ_edge (new_bb);
    1974                 :      25663 :   edge e2 = make_edge (new_bb, then_bb,
    1975                 :            :                        EDGE_TRUE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
    1976                 :      12873 :   e2->probability = flag_probability;
    1977                 :            : 
    1978                 :      12873 :   e1->flags |= EDGE_FALSE_VALUE | (irr ? EDGE_IRREDUCIBLE_LOOP : 0);
    1979                 :      12873 :   e1->flags &= ~EDGE_FALLTHRU;
    1980                 :            : 
    1981                 :      12873 :   e1->probability = flag_probability.invert ();
    1982                 :            : 
    1983                 :      25663 :   then_old_edge = make_single_succ_edge (then_bb, old_dest,
    1984                 :            :                              EDGE_FALLTHRU | (irr ? EDGE_IRREDUCIBLE_LOOP : 0));
    1985                 :            : 
    1986                 :      12873 :   set_immediate_dominator (CDI_DOMINATORS, then_bb, new_bb);
    1987                 :            : 
    1988                 :      12873 :   if (prev_edges)
    1989                 :            :     {
    1990                 :       5072 :       basic_block prevbb = prev_edges->last_cond_fallthru->src;
    1991                 :       5072 :       redirect_edge_succ (prev_edges->last_cond_fallthru, new_bb);
    1992                 :       5072 :       set_immediate_dominator (CDI_DOMINATORS, new_bb, prevbb);
    1993                 :       5072 :       set_immediate_dominator (CDI_DOMINATORS, old_dest,
    1994                 :            :                                recompute_dominator (CDI_DOMINATORS, old_dest));
    1995                 :            :     }
    1996                 :            : 
    1997                 :            :   /* ?? Because stores may alias, they must happen in the exact
    1998                 :            :      sequence they originally happened.  Save the position right after
    1999                 :            :      the (_lsm) store we just created so we can continue appending after
    2000                 :            :      it and maintain the original order.  */
    2001                 :      12873 :   {
    2002                 :      12873 :     struct prev_flag_edges *p;
    2003                 :            : 
    2004                 :      12873 :     if (orig_ex->aux)
    2005                 :       5072 :       orig_ex->aux = NULL;
    2006                 :      12873 :     alloc_aux_for_edge (orig_ex, sizeof (struct prev_flag_edges));
    2007                 :      12873 :     p = (struct prev_flag_edges *) orig_ex->aux;
    2008                 :      12873 :     p->append_cond_position = then_old_edge;
    2009                 :      12873 :     p->last_cond_fallthru = find_edge (new_bb, old_dest);
    2010                 :      12873 :     orig_ex->aux = (void *) p;
    2011                 :            :   }
    2012                 :            : 
    2013                 :      12873 :   if (!loop_has_only_one_exit)
    2014                 :       8948 :     for (gphi_iterator gpi = gsi_start_phis (old_dest);
    2015                 :      13780 :          !gsi_end_p (gpi); gsi_next (&gpi))
    2016                 :            :       {
    2017                 :       4832 :         gphi *phi = gpi.phi ();
    2018                 :            :         unsigned i;
    2019                 :            : 
    2020                 :      24239 :         for (i = 0; i < gimple_phi_num_args (phi); i++)
    2021                 :      19407 :           if (gimple_phi_arg_edge (phi, i)->src == new_bb)
    2022                 :            :             {
    2023                 :       4832 :               tree arg = gimple_phi_arg_def (phi, i);
    2024                 :       4832 :               add_phi_arg (phi, arg, then_old_edge, UNKNOWN_LOCATION);
    2025                 :      24239 :               update_stmt (phi);
    2026                 :            :             }
    2027                 :            :       }
    2028                 :      12873 : }
    2029                 :            : 
    2030                 :            : /* When REF is set on the location, set flag indicating the store.  */
    2031                 :            : 
    2032                 :            : class sm_set_flag_if_changed
    2033                 :            : {
    2034                 :            : public:
    2035                 :       7637 :   sm_set_flag_if_changed (tree flag_, hash_set <basic_block> *bbs_)
    2036                 :       7637 :          : flag (flag_), bbs (bbs_) {}
    2037                 :            :   bool operator () (mem_ref_loc *loc);
    2038                 :            :   tree flag;
    2039                 :            :   hash_set <basic_block> *bbs;
    2040                 :            : };
    2041                 :            : 
    2042                 :            : bool
    2043                 :      15194 : sm_set_flag_if_changed::operator () (mem_ref_loc *loc)
    2044                 :            : {
    2045                 :            :   /* Only set the flag for writes.  */
    2046                 :      15194 :   if (is_gimple_assign (loc->stmt)
    2047                 :      15194 :       && gimple_assign_lhs_ptr (loc->stmt) == loc->ref)
    2048                 :            :     {
    2049                 :       9369 :       gimple_stmt_iterator gsi = gsi_for_stmt (loc->stmt);
    2050                 :       9369 :       gimple *stmt = gimple_build_assign (flag, boolean_true_node);
    2051                 :       9369 :       gsi_insert_after (&gsi, stmt, GSI_CONTINUE_LINKING);
    2052                 :       9369 :       bbs->add (gimple_bb (stmt));
    2053                 :            :     }
    2054                 :      15194 :   return false;
    2055                 :            : }
    2056                 :            : 
    2057                 :            : /* Helper function for execute_sm.  On every location where REF is
    2058                 :            :    set, set an appropriate flag indicating the store.  */
    2059                 :            : 
    2060                 :            : static tree
    2061                 :       7637 : execute_sm_if_changed_flag_set (class loop *loop, im_mem_ref *ref,
    2062                 :            :                                 hash_set <basic_block> *bbs)
    2063                 :            : {
    2064                 :       7637 :   tree flag;
    2065                 :       7637 :   char *str = get_lsm_tmp_name (ref->mem.ref, ~0, "_flag");
    2066                 :       7637 :   flag = create_tmp_reg (boolean_type_node, str);
    2067                 :       7637 :   for_all_locs_in_loop (loop, ref, sm_set_flag_if_changed (flag, bbs));
    2068                 :       7637 :   return flag;
    2069                 :            : }
    2070                 :            : 
    2071                 :            : /* Executes store motion of memory reference REF from LOOP.
    2072                 :            :    Exits from the LOOP are stored in EXITS.  The initialization of the
    2073                 :            :    temporary variable is put to the preheader of the loop, and assignments
    2074                 :            :    to the reference from the temporary variable are emitted to exits.  */
    2075                 :            : 
    2076                 :            : static void
    2077                 :      22139 : execute_sm (class loop *loop, vec<edge> exits, im_mem_ref *ref)
    2078                 :            : {
    2079                 :      22139 :   tree tmp_var, store_flag = NULL_TREE;
    2080                 :      22139 :   unsigned i;
    2081                 :      22139 :   gassign *load;
    2082                 :      22139 :   struct fmt_data fmt_data;
    2083                 :      22139 :   edge ex;
    2084                 :      22139 :   struct lim_aux_data *lim_data;
    2085                 :      22139 :   bool multi_threaded_model_p = false;
    2086                 :      22139 :   gimple_stmt_iterator gsi;
    2087                 :      22139 :   hash_set<basic_block> flag_bbs;
    2088                 :            : 
    2089                 :      22139 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2090                 :            :     {
    2091                 :         38 :       fprintf (dump_file, "Executing store motion of ");
    2092                 :         38 :       print_generic_expr (dump_file, ref->mem.ref);
    2093                 :         38 :       fprintf (dump_file, " from loop %d\n", loop->num);
    2094                 :            :     }
    2095                 :            : 
    2096                 :      22139 :   tmp_var = create_tmp_reg (TREE_TYPE (ref->mem.ref),
    2097                 :      22139 :                             get_lsm_tmp_name (ref->mem.ref, ~0));
    2098                 :            : 
    2099                 :      22139 :   fmt_data.loop = loop;
    2100                 :      22139 :   fmt_data.orig_loop = loop;
    2101                 :      22139 :   for_each_index (&ref->mem.ref, force_move_till, &fmt_data);
    2102                 :            : 
    2103                 :      22139 :   if (bb_in_transaction (loop_preheader_edge (loop)->src)
    2104                 :      22139 :       || (! flag_store_data_races
    2105                 :      21665 :           && ! ref_always_accessed_p (loop, ref, true)))
    2106                 :       7637 :     multi_threaded_model_p = true;
    2107                 :            : 
    2108                 :       7637 :   if (multi_threaded_model_p)
    2109                 :       7637 :     store_flag = execute_sm_if_changed_flag_set (loop, ref, &flag_bbs);
    2110                 :            : 
    2111                 :      22139 :   rewrite_mem_refs (loop, ref, tmp_var);
    2112                 :            : 
    2113                 :            :   /* Emit the load code on a random exit edge or into the latch if
    2114                 :            :      the loop does not exit, so that we are sure it will be processed
    2115                 :            :      by move_computations after all dependencies.  */
    2116                 :      22139 :   gsi = gsi_for_stmt (first_mem_ref_loc (loop, ref)->stmt);
    2117                 :            : 
    2118                 :            :   /* FIXME/TODO: For the multi-threaded variant, we could avoid this
    2119                 :            :      load altogether, since the store is predicated by a flag.  We
    2120                 :            :      could, do the load only if it was originally in the loop.  */
    2121                 :      22139 :   load = gimple_build_assign (tmp_var, unshare_expr (ref->mem.ref));
    2122                 :      22139 :   lim_data = init_lim_data (load);
    2123                 :      22139 :   lim_data->max_loop = loop;
    2124                 :      22139 :   lim_data->tgt_loop = loop;
    2125                 :      22139 :   gsi_insert_before (&gsi, load, GSI_SAME_STMT);
    2126                 :            : 
    2127                 :      22139 :   if (multi_threaded_model_p)
    2128                 :            :     {
    2129                 :       7637 :       load = gimple_build_assign (store_flag, boolean_false_node);
    2130                 :       7637 :       lim_data = init_lim_data (load);
    2131                 :       7637 :       lim_data->max_loop = loop;
    2132                 :       7637 :       lim_data->tgt_loop = loop;
    2133                 :       7637 :       gsi_insert_before (&gsi, load, GSI_SAME_STMT);
    2134                 :            :     }
    2135                 :            : 
    2136                 :            :   /* Sink the store to every exit from the loop.  */
    2137                 :      72300 :   FOR_EACH_VEC_ELT (exits, i, ex)
    2138                 :      29069 :     if (!multi_threaded_model_p)
    2139                 :            :       {
    2140                 :      16196 :         gassign *store;
    2141                 :      16196 :         store = gimple_build_assign (unshare_expr (ref->mem.ref), tmp_var);
    2142                 :      16196 :         gsi_insert_on_edge (ex, store);
    2143                 :            :       }
    2144                 :            :     else
    2145                 :      12873 :       execute_sm_if_changed (ex, ref->mem.ref, tmp_var, store_flag,
    2146                 :            :                              loop_preheader_edge (loop), &flag_bbs);
    2147                 :      22139 : }
    2148                 :            : 
    2149                 :            : /* Hoists memory references MEM_REFS out of LOOP.  EXITS is the list of exit
    2150                 :            :    edges of the LOOP.  */
    2151                 :            : 
    2152                 :            : static void
    2153                 :     697658 : hoist_memory_references (class loop *loop, bitmap mem_refs,
    2154                 :            :                          vec<edge> exits)
    2155                 :            : {
    2156                 :     697658 :   im_mem_ref *ref;
    2157                 :     697658 :   unsigned  i;
    2158                 :     697658 :   bitmap_iterator bi;
    2159                 :            : 
    2160                 :     719797 :   EXECUTE_IF_SET_IN_BITMAP (mem_refs, 0, i, bi)
    2161                 :            :     {
    2162                 :      22139 :       ref = memory_accesses.refs_list[i];
    2163                 :      22139 :       execute_sm (loop, exits, ref);
    2164                 :            :     }
    2165                 :     697658 : }
    2166                 :            : 
    2167                 :            : class ref_always_accessed
    2168                 :            : {
    2169                 :            : public:
    2170                 :      52643 :   ref_always_accessed (class loop *loop_, bool stored_p_)
    2171                 :      52643 :       : loop (loop_), stored_p (stored_p_) {}
    2172                 :            :   bool operator () (mem_ref_loc *loc);
    2173                 :            :   class loop *loop;
    2174                 :            :   bool stored_p;
    2175                 :            : };
    2176                 :            : 
    2177                 :            : bool
    2178                 :     104750 : ref_always_accessed::operator () (mem_ref_loc *loc)
    2179                 :            : {
    2180                 :     104750 :   class loop *must_exec;
    2181                 :            : 
    2182                 :     104750 :   if (!get_lim_data (loc->stmt))
    2183                 :            :     return false;
    2184                 :            : 
    2185                 :            :   /* If we require an always executed store make sure the statement
    2186                 :            :      stores to the reference.  */
    2187                 :     104750 :   if (stored_p)
    2188                 :            :     {
    2189                 :     104750 :       tree lhs = gimple_get_lhs (loc->stmt);
    2190                 :     104750 :       if (!lhs
    2191                 :     104750 :           || lhs != *loc->ref)
    2192                 :            :         return false;
    2193                 :            :     }
    2194                 :            : 
    2195                 :      65548 :   must_exec = get_lim_data (loc->stmt)->always_executed_in;
    2196                 :      65548 :   if (!must_exec)
    2197                 :            :     return false;
    2198                 :            : 
    2199                 :      21782 :   if (must_exec == loop
    2200                 :      21782 :       || flow_loop_nested_p (must_exec, loop))
    2201                 :      19939 :     return true;
    2202                 :            : 
    2203                 :            :   return false;
    2204                 :            : }
    2205                 :            : 
    2206                 :            : /* Returns true if REF is always accessed in LOOP.  If STORED_P is true
    2207                 :            :    make sure REF is always stored to in LOOP.  */
    2208                 :            : 
    2209                 :            : static bool
    2210                 :      52643 : ref_always_accessed_p (class loop *loop, im_mem_ref *ref, bool stored_p)
    2211                 :            : {
    2212                 :      52643 :   return for_all_locs_in_loop (loop, ref,
    2213                 :          0 :                                ref_always_accessed (loop, stored_p));
    2214                 :            : }
    2215                 :            : 
    2216                 :            : /* Returns true if REF1 and REF2 are independent.  */
    2217                 :            : 
    2218                 :            : static bool
    2219                 :     321234 : refs_independent_p (im_mem_ref *ref1, im_mem_ref *ref2)
    2220                 :            : {
    2221                 :     321234 :   if (ref1 == ref2)
    2222                 :            :     return true;
    2223                 :            : 
    2224                 :     294222 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2225                 :        108 :     fprintf (dump_file, "Querying dependency of refs %u and %u: ",
    2226                 :        108 :              ref1->id, ref2->id);
    2227                 :            : 
    2228                 :     294222 :   if (mem_refs_may_alias_p (ref1, ref2, &memory_accesses.ttae_cache))
    2229                 :            :     {
    2230                 :      23666 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2231                 :          3 :         fprintf (dump_file, "dependent.\n");
    2232                 :      23666 :       return false;
    2233                 :            :     }
    2234                 :            :   else
    2235                 :            :     {
    2236                 :     270556 :       if (dump_file && (dump_flags & TDF_DETAILS))
    2237                 :        105 :         fprintf (dump_file, "independent.\n");
    2238                 :     270556 :       return true;
    2239                 :            :     }
    2240                 :            : }
    2241                 :            : 
    2242                 :            : /* Mark REF dependent on stores or loads (according to STORED_P) in LOOP
    2243                 :            :    and its super-loops.  */
    2244                 :            : 
    2245                 :            : static void
    2246                 :    1645690 : record_dep_loop (class loop *loop, im_mem_ref *ref, bool stored_p)
    2247                 :            : {
    2248                 :            :   /* We can propagate dependent-in-loop bits up the loop
    2249                 :            :      hierarchy to all outer loops.  */
    2250                 :    3046580 :   while (loop != current_loops->tree_root
    2251                 :    3663270 :          && bitmap_set_bit (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
    2252                 :    1400890 :     loop = loop_outer (loop);
    2253                 :    1645690 : }
    2254                 :            : 
    2255                 :            : /* Returns true if REF is independent on all other memory
    2256                 :            :    references in LOOP.  */
    2257                 :            : 
    2258                 :            : static bool
    2259                 :    1257980 : ref_indep_loop_p_1 (class loop *loop, im_mem_ref *ref, bool stored_p)
    2260                 :            : {
    2261                 :    1257980 :   stored_p |= (ref->stored && bitmap_bit_p (ref->stored, loop->num));
    2262                 :            : 
    2263                 :    1257980 :   bool indep_p = true;
    2264                 :    1257980 :   bitmap refs_to_check;
    2265                 :            : 
    2266                 :    1257980 :   if (stored_p)
    2267                 :     621389 :     refs_to_check = &memory_accesses.refs_in_loop[loop->num];
    2268                 :            :   else
    2269                 :     636590 :     refs_to_check = &memory_accesses.refs_stored_in_loop[loop->num];
    2270                 :            : 
    2271                 :    1257980 :   if (bitmap_bit_p (refs_to_check, UNANALYZABLE_MEM_ID))
    2272                 :            :     indep_p = false;
    2273                 :            :   else
    2274                 :            :     {
    2275                 :     370026 :       if (bitmap_bit_p (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
    2276                 :            :         return true;
    2277                 :     234298 :       if (bitmap_bit_p (&ref->dep_loop, LOOP_DEP_BIT (loop->num, stored_p)))
    2278                 :            :         return false;
    2279                 :            : 
    2280                 :     202062 :       class loop *inner = loop->inner;
    2281                 :     253544 :       while (inner)
    2282                 :            :         {
    2283                 :     115948 :           if (!ref_indep_loop_p_1 (inner, ref, stored_p))
    2284                 :            :             {
    2285                 :            :               indep_p = false;
    2286                 :            :               break;
    2287                 :            :             }
    2288                 :      51482 :           inner = inner->next;
    2289                 :            :         }
    2290                 :            : 
    2291                 :     202062 :       if (indep_p)
    2292                 :            :         {
    2293                 :     137596 :           unsigned i;
    2294                 :     137596 :           bitmap_iterator bi;
    2295                 :     435164 :           EXECUTE_IF_SET_IN_BITMAP (refs_to_check, 0, i, bi)
    2296                 :            :             {
    2297                 :     321234 :               im_mem_ref *aref = memory_accesses.refs_list[i];
    2298                 :     321234 :               if (!refs_independent_p (ref, aref))
    2299                 :            :                 {
    2300                 :            :                   indep_p = false;
    2301                 :            :                   break;
    2302                 :            :                 }
    2303                 :            :             }
    2304                 :            :         }
    2305                 :            :     }
    2306                 :            : 
    2307                 :    1222450 :   if (dump_file && (dump_flags & TDF_DETAILS))
    2308                 :         70 :     fprintf (dump_file, "Querying dependencies of ref %u in loop %d: %s\n",
    2309                 :         70 :              ref->id, loop->num, indep_p ? "independent" : "dependent");
    2310                 :            : 
    2311                 :            :   /* Record the computed result in the cache.  */
    2312                 :    1222450 :   if (indep_p)
    2313                 :            :     {
    2314                 :     193170 :       if (bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, stored_p))
    2315                 :     113930 :           && stored_p)
    2316                 :            :         {
    2317                 :            :           /* If it's independend against all refs then it's independent
    2318                 :            :              against stores, too.  */
    2319                 :      34690 :           bitmap_set_bit (&ref->indep_loop, LOOP_DEP_BIT (loop->num, false));
    2320                 :            :         }
    2321                 :            :     }
    2322                 :            :   else
    2323                 :            :     {
    2324                 :    1108520 :       record_dep_loop (loop, ref, stored_p);
    2325                 :    1108520 :       if (!stored_p)
    2326                 :            :         {
    2327                 :            :           /* If it's dependent against stores it's dependent against
    2328                 :            :              all refs, too.  */
    2329                 :     537169 :           record_dep_loop (loop, ref, true);
    2330                 :            :         }
    2331                 :            :     }
    2332                 :            : 
    2333                 :            :   return indep_p;
    2334                 :            : }
    2335                 :            : 
    2336                 :            : /* Returns true if REF is independent on all other memory references in
    2337                 :            :    LOOP.  */
    2338                 :            : 
    2339                 :            : static bool
    2340                 :    1142030 : ref_indep_loop_p (class loop *loop, im_mem_ref *ref)
    2341                 :            : {
    2342                 :    1142030 :   gcc_checking_assert (MEM_ANALYZABLE (ref));
    2343                 :            : 
    2344                 :    1142030 :   return ref_indep_loop_p_1 (loop, ref, false);
    2345                 :            : }
    2346                 :            : 
    2347                 :            : /* Returns true if we can perform store motion of REF from LOOP.  */
    2348                 :            : 
    2349                 :            : static bool
    2350                 :    1594130 : can_sm_ref_p (class loop *loop, im_mem_ref *ref)
    2351                 :            : {
    2352                 :    1594130 :   tree base;
    2353                 :            : 
    2354                 :            :   /* Can't hoist unanalyzable refs.  */
    2355                 :    1594130 :   if (!MEM_ANALYZABLE (ref))
    2356                 :            :     return false;
    2357                 :            : 
    2358                 :            :   /* It should be movable.  */
    2359                 :    1333130 :   if (!is_gimple_reg_type (TREE_TYPE (ref->mem.ref))
    2360                 :    1333050 :       || TREE_THIS_VOLATILE (ref->mem.ref)
    2361                 :    2652490 :       || !for_each_index (&ref->mem.ref, may_move_till, loop))
    2362                 :     728106 :     return false;
    2363                 :            : 
    2364                 :            :   /* If it can throw fail, we do not properly update EH info.  */
    2365                 :     605023 :   if (tree_could_throw_p (ref->mem.ref))
    2366                 :            :     return false;
    2367                 :            : 
    2368                 :            :   /* If it can trap, it must be always executed in LOOP.
    2369                 :            :      Readonly memory locations may trap when storing to them, but
    2370                 :            :      tree_could_trap_p is a predicate for rvalues, so check that
    2371                 :            :      explicitly.  */
    2372                 :     589454 :   base = get_base_address (ref->mem.ref);
    2373                 :     589454 :   if ((tree_could_trap_p (ref->mem.ref)
    2374                 :     558552 :        || (DECL_P (base) && TREE_READONLY (base)))
    2375                 :     620432 :       && !ref_always_accessed_p (loop, ref, true))
    2376                 :            :     return false;
    2377                 :            : 
    2378                 :            :   /* And it must be independent on all other memory references
    2379                 :            :      in LOOP.  */
    2380                 :     564385 :   if (!ref_indep_loop_p (loop, ref))
    2381                 :     542246 :     return false;
    2382                 :            : 
    2383                 :            :   return true;
    2384                 :            : }
    2385                 :            : 
    2386                 :            : /* Marks the references in LOOP for that store motion should be performed
    2387                 :            :    in REFS_TO_SM.  SM_EXECUTED is the set of references for that store
    2388                 :            :    motion was performed in one of the outer loops.  */
    2389                 :            : 
    2390                 :            : static void
    2391                 :     697658 : find_refs_for_sm (class loop *loop, bitmap sm_executed, bitmap refs_to_sm)
    2392                 :            : {
    2393                 :     697658 :   bitmap refs = &memory_accesses.all_refs_stored_in_loop[loop->num];
    2394                 :     697658 :   unsigned i;
    2395                 :     697658 :   bitmap_iterator bi;
    2396                 :     697658 :   im_mem_ref *ref;
    2397                 :            : 
    2398                 :    2291790 :   EXECUTE_IF_AND_COMPL_IN_BITMAP (refs, sm_executed, 0, i, bi)
    2399                 :            :     {
    2400                 :    1594130 :       ref = memory_accesses.refs_list[i];
    2401                 :    1594130 :       if (can_sm_ref_p (loop, ref))
    2402                 :      22139 :         bitmap_set_bit (refs_to_sm, i);
    2403                 :            :     }
    2404                 :     697658 : }
    2405                 :            : 
    2406                 :            : /* Checks whether LOOP (with exits stored in EXITS array) is suitable
    2407                 :            :    for a store motion optimization (i.e. whether we can insert statement
    2408                 :            :    on its exits).  */
    2409                 :            : 
    2410                 :            : static bool
    2411                 :     729787 : loop_suitable_for_sm (class loop *loop ATTRIBUTE_UNUSED,
    2412                 :            :                       vec<edge> exits)
    2413                 :            : {
    2414                 :     729787 :   unsigned i;
    2415                 :     729787 :   edge ex;
    2416                 :            : 
    2417                 :    1914640 :   FOR_EACH_VEC_ELT (exits, i, ex)
    2418                 :    1216980 :     if (ex->flags & (EDGE_ABNORMAL | EDGE_EH))
    2419                 :            :       return false;
    2420                 :            : 
    2421                 :            :   return true;
    2422                 :            : }
    2423                 :            : 
    2424                 :            : /* Try to perform store motion for all memory references modified inside
    2425                 :            :    LOOP.  SM_EXECUTED is the bitmap of the memory references for that
    2426                 :            :    store motion was executed in one of the outer loops.  */
    2427                 :            : 
    2428                 :            : static void
    2429                 :     729787 : store_motion_loop (class loop *loop, bitmap sm_executed)
    2430                 :            : {
    2431                 :     729787 :   vec<edge> exits = get_loop_exit_edges (loop);
    2432                 :     729787 :   class loop *subloop;
    2433                 :     729787 :   bitmap sm_in_loop = BITMAP_ALLOC (&lim_bitmap_obstack);
    2434                 :            : 
    2435                 :    1459570 :   if (loop_suitable_for_sm (loop, exits))
    2436                 :            :     {
    2437                 :     697658 :       find_refs_for_sm (loop, sm_executed, sm_in_loop);
    2438                 :     697658 :       hoist_memory_references (loop, sm_in_loop, exits);
    2439                 :            :     }
    2440                 :     729787 :   exits.release ();
    2441                 :            : 
    2442                 :     729787 :   bitmap_ior_into (sm_executed, sm_in_loop);
    2443                 :     908821 :   for (subloop = loop->inner; subloop != NULL; subloop = subloop->next)
    2444                 :     179034 :     store_motion_loop (subloop, sm_executed);
    2445                 :     729787 :   bitmap_and_compl_into (sm_executed, sm_in_loop);
    2446                 :     729787 :   BITMAP_FREE (sm_in_loop);
    2447                 :     729787 : }
    2448                 :            : 
    2449                 :            : /* Try to perform store motion for all memory references modified inside
    2450                 :            :    loops.  */
    2451                 :            : 
    2452                 :            : static void
    2453                 :     316604 : store_motion (void)
    2454                 :            : {
    2455                 :     316604 :   class loop *loop;
    2456                 :     316604 :   bitmap sm_executed = BITMAP_ALLOC (&lim_bitmap_obstack);
    2457                 :            : 
    2458                 :     867357 :   for (loop = current_loops->tree_root->inner; loop != NULL; loop = loop->next)
    2459                 :     550753 :     store_motion_loop (loop, sm_executed);
    2460                 :            : 
    2461                 :     316604 :   BITMAP_FREE (sm_executed);
    2462                 :     316604 :   gsi_commit_edge_inserts ();
    2463                 :     316604 : }
    2464                 :            : 
    2465                 :            : /* Fills ALWAYS_EXECUTED_IN information for basic blocks of LOOP, i.e.
    2466                 :            :    for each such basic block bb records the outermost loop for that execution
    2467                 :            :    of its header implies execution of bb.  CONTAINS_CALL is the bitmap of
    2468                 :            :    blocks that contain a nonpure call.  */
    2469                 :            : 
    2470                 :            : static void
    2471                 :     729787 : fill_always_executed_in_1 (class loop *loop, sbitmap contains_call)
    2472                 :            : {
    2473                 :     729787 :   basic_block bb = NULL, *bbs, last = NULL;
    2474                 :     729787 :   unsigned i;
    2475                 :     729787 :   edge e;
    2476                 :     729787 :   class loop *inn_loop = loop;
    2477                 :            : 
    2478                 :     729787 :   if (ALWAYS_EXECUTED_IN (loop->header) == NULL)
    2479                 :            :     {
    2480                 :     680730 :       bbs = get_loop_body_in_dom_order (loop);
    2481                 :            : 
    2482                 :    1218140 :       for (i = 0; i < loop->num_nodes; i++)
    2483                 :            :         {
    2484                 :    1211250 :           edge_iterator ei;
    2485                 :    1211250 :           bb = bbs[i];
    2486                 :            : 
    2487                 :    1211250 :           if (dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
    2488                 :     822128 :             last = bb;
    2489                 :            : 
    2490                 :    1211250 :           if (bitmap_bit_p (contains_call, bb->index))
    2491                 :            :             break;
    2492                 :            : 
    2493                 :    2083800 :           FOR_EACH_EDGE (e, ei, bb->succs)
    2494                 :            :             {
    2495                 :            :               /* If there is an exit from this BB.  */
    2496                 :    1501350 :               if (!flow_bb_inside_loop_p (loop, e->dest))
    2497                 :            :                 break;
    2498                 :            :               /* Or we enter a possibly non-finite loop.  */
    2499                 :    1103240 :               if (flow_loop_nested_p (bb->loop_father,
    2500                 :    1103240 :                                       e->dest->loop_father)
    2501                 :    1103240 :                   && ! finite_loop_p (e->dest->loop_father))
    2502                 :            :                 break;
    2503                 :            :             }
    2504                 :     997115 :           if (e)
    2505                 :            :             break;
    2506                 :            : 
    2507                 :            :           /* A loop might be infinite (TODO use simple loop analysis
    2508                 :            :              to disprove this if possible).  */
    2509                 :     582446 :           if (bb->flags & BB_IRREDUCIBLE_LOOP)
    2510                 :            :             break;
    2511                 :            : 
    2512                 :     582223 :           if (!flow_bb_inside_loop_p (inn_loop, bb))
    2513                 :            :             break;
    2514                 :            : 
    2515                 :     576781 :           if (bb->loop_father->header == bb)
    2516                 :            :             {
    2517                 :     282643 :               if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
    2518                 :            :                 break;
    2519                 :            : 
    2520                 :            :               /* In a loop that is always entered we may proceed anyway.
    2521                 :            :                  But record that we entered it and stop once we leave it.  */
    2522                 :     243276 :               inn_loop = bb->loop_father;
    2523                 :            :             }
    2524                 :            :         }
    2525                 :            : 
    2526                 :     963526 :       while (1)
    2527                 :            :         {
    2528                 :     822128 :           SET_ALWAYS_EXECUTED_IN (last, loop);
    2529                 :     822128 :           if (last == loop->header)
    2530                 :            :             break;
    2531                 :     141398 :           last = get_immediate_dominator (CDI_DOMINATORS, last);
    2532                 :            :         }
    2533                 :            : 
    2534                 :     680730 :       free (bbs);
    2535                 :            :     }
    2536                 :            : 
    2537                 :     908821 :   for (loop = loop->inner; loop; loop = loop->next)
    2538                 :     179034 :     fill_always_executed_in_1 (loop, contains_call);
    2539                 :     729787 : }
    2540                 :            : 
    2541                 :            : /* Fills ALWAYS_EXECUTED_IN information for basic blocks, i.e.
    2542                 :            :    for each such basic block bb records the outermost loop for that execution
    2543                 :            :    of its header implies execution of bb.  */
    2544                 :            : 
    2545                 :            : static void
    2546                 :     316604 : fill_always_executed_in (void)
    2547                 :            : {
    2548                 :     316604 :   basic_block bb;
    2549                 :     316604 :   class loop *loop;
    2550                 :            : 
    2551                 :     316604 :   auto_sbitmap contains_call (last_basic_block_for_fn (cfun));
    2552                 :     316604 :   bitmap_clear (contains_call);
    2553                 :    9006050 :   FOR_EACH_BB_FN (bb, cfun)
    2554                 :            :     {
    2555                 :    8689440 :       gimple_stmt_iterator gsi;
    2556                 :   69512100 :       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    2557                 :            :         {
    2558                 :   57160800 :           if (nonpure_call_p (gsi_stmt (gsi)))
    2559                 :            :             break;
    2560                 :            :         }
    2561                 :            : 
    2562                 :    8689440 :       if (!gsi_end_p (gsi))
    2563                 :   11131700 :         bitmap_set_bit (contains_call, bb->index);
    2564                 :            :     }
    2565                 :            : 
    2566                 :     867357 :   for (loop = current_loops->tree_root->inner; loop; loop = loop->next)
    2567                 :     550753 :     fill_always_executed_in_1 (loop, contains_call);
    2568                 :     316604 : }
    2569                 :            : 
    2570                 :            : 
    2571                 :            : /* Compute the global information needed by the loop invariant motion pass.  */
    2572                 :            : 
    2573                 :            : static void
    2574                 :     316604 : tree_ssa_lim_initialize (void)
    2575                 :            : {
    2576                 :     316604 :   class loop *loop;
    2577                 :     316604 :   unsigned i;
    2578                 :            : 
    2579                 :     316604 :   bitmap_obstack_initialize (&lim_bitmap_obstack);
    2580                 :     316604 :   gcc_obstack_init (&mem_ref_obstack);
    2581                 :     316604 :   lim_aux_data_map = new hash_map<gimple *, lim_aux_data *>;
    2582                 :            : 
    2583                 :     316604 :   if (flag_tm)
    2584                 :        120 :     compute_transaction_bits ();
    2585                 :            : 
    2586                 :     316604 :   alloc_aux_for_edges (0);
    2587                 :            : 
    2588                 :     316604 :   memory_accesses.refs = new hash_table<mem_ref_hasher> (100);
    2589                 :     316604 :   memory_accesses.refs_list.create (100);
    2590                 :            :   /* Allocate a special, unanalyzable mem-ref with ID zero.  */
    2591                 :     316604 :   memory_accesses.refs_list.quick_push
    2592                 :     316604 :     (mem_ref_alloc (NULL, 0, UNANALYZABLE_MEM_ID));
    2593                 :            : 
    2594                 :     633208 :   memory_accesses.refs_in_loop.create (number_of_loops (cfun));
    2595                 :     633208 :   memory_accesses.refs_in_loop.quick_grow (number_of_loops (cfun));
    2596                 :     633208 :   memory_accesses.refs_stored_in_loop.create (number_of_loops (cfun));
    2597                 :     633208 :   memory_accesses.refs_stored_in_loop.quick_grow (number_of_loops (cfun));
    2598                 :     633208 :   memory_accesses.all_refs_stored_in_loop.create (number_of_loops (cfun));
    2599                 :     316604 :   memory_accesses.all_refs_stored_in_loop.quick_grow (number_of_loops (cfun));
    2600                 :            : 
    2601                 :    3209130 :   for (i = 0; i < number_of_loops (cfun); i++)
    2602                 :            :     {
    2603                 :    1287960 :       bitmap_initialize (&memory_accesses.refs_in_loop[i],
    2604                 :            :                          &lim_bitmap_obstack);
    2605                 :    1287960 :       bitmap_initialize (&memory_accesses.refs_stored_in_loop[i],
    2606                 :            :                          &lim_bitmap_obstack);
    2607                 :    1287960 :       bitmap_initialize (&memory_accesses.all_refs_stored_in_loop[i],
    2608                 :            :                          &lim_bitmap_obstack);
    2609                 :            :     }
    2610                 :            : 
    2611                 :     316604 :   memory_accesses.ttae_cache = NULL;
    2612                 :            : 
    2613                 :            :   /* Initialize bb_loop_postorder with a mapping from loop->num to
    2614                 :            :      its postorder index.  */
    2615                 :     316604 :   i = 0;
    2616                 :     633208 :   bb_loop_postorder = XNEWVEC (unsigned, number_of_loops (cfun));
    2617                 :    1046390 :   FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
    2618                 :     729787 :     bb_loop_postorder[loop->num] = i++;
    2619                 :     316604 : }
    2620                 :            : 
    2621                 :            : /* Cleans up after the invariant motion pass.  */
    2622                 :            : 
    2623                 :            : static void
    2624                 :     316604 : tree_ssa_lim_finalize (void)
    2625                 :            : {
    2626                 :     316604 :   basic_block bb;
    2627                 :     316604 :   unsigned i;
    2628                 :     316604 :   im_mem_ref *ref;
    2629                 :            : 
    2630                 :     316604 :   free_aux_for_edges ();
    2631                 :            : 
    2632                 :    9042330 :   FOR_EACH_BB_FN (bb, cfun)
    2633                 :    8725730 :     SET_ALWAYS_EXECUTED_IN (bb, NULL);
    2634                 :            : 
    2635                 :     316604 :   bitmap_obstack_release (&lim_bitmap_obstack);
    2636                 :     633208 :   delete lim_aux_data_map;
    2637                 :            : 
    2638                 :     316604 :   delete memory_accesses.refs;
    2639                 :     316604 :   memory_accesses.refs = NULL;
    2640                 :            : 
    2641                 :    3417520 :   FOR_EACH_VEC_ELT (memory_accesses.refs_list, i, ref)
    2642                 :    6201840 :     memref_free (ref);
    2643                 :     316604 :   memory_accesses.refs_list.release ();
    2644                 :     316604 :   obstack_free (&mem_ref_obstack, NULL);
    2645                 :            : 
    2646                 :     316604 :   memory_accesses.refs_in_loop.release ();
    2647                 :     316604 :   memory_accesses.refs_stored_in_loop.release ();
    2648                 :     316604 :   memory_accesses.all_refs_stored_in_loop.release ();
    2649                 :            : 
    2650                 :     316604 :   if (memory_accesses.ttae_cache)
    2651                 :       2320 :     free_affine_expand_cache (&memory_accesses.ttae_cache);
    2652                 :            : 
    2653                 :     316604 :   free (bb_loop_postorder);
    2654                 :     316604 : }
    2655                 :            : 
    2656                 :            : /* Moves invariants from loops.  Only "expensive" invariants are moved out --
    2657                 :            :    i.e. those that are likely to be win regardless of the register pressure.  */
    2658                 :            : 
    2659                 :            : static unsigned int
    2660                 :     316604 : tree_ssa_lim (void)
    2661                 :            : {
    2662                 :     316604 :   unsigned int todo;
    2663                 :            : 
    2664                 :     316604 :   tree_ssa_lim_initialize ();
    2665                 :            : 
    2666                 :            :   /* Gathers information about memory accesses in the loops.  */
    2667                 :     316604 :   analyze_memory_references ();
    2668                 :            : 
    2669                 :            :   /* Fills ALWAYS_EXECUTED_IN information for basic blocks.  */
    2670                 :     316604 :   fill_always_executed_in ();
    2671                 :            : 
    2672                 :            :   /* For each statement determine the outermost loop in that it is
    2673                 :            :      invariant and cost for computing the invariant.  */
    2674                 :     316604 :   invariantness_dom_walker (CDI_DOMINATORS)
    2675                 :     316604 :     .walk (cfun->cfg->x_entry_block_ptr);
    2676                 :            : 
    2677                 :            :   /* Execute store motion.  Force the necessary invariants to be moved
    2678                 :            :      out of the loops as well.  */
    2679                 :     316604 :   store_motion ();
    2680                 :            : 
    2681                 :            :   /* Move the expressions that are expensive enough.  */
    2682                 :     316604 :   todo = move_computations ();
    2683                 :            : 
    2684                 :     316604 :   tree_ssa_lim_finalize ();
    2685                 :            : 
    2686                 :     316604 :   return todo;
    2687                 :            : }
    2688                 :            : 
    2689                 :            : /* Loop invariant motion pass.  */
    2690                 :            : 
    2691                 :            : namespace {
    2692                 :            : 
    2693                 :            : const pass_data pass_data_lim =
    2694                 :            : {
    2695                 :            :   GIMPLE_PASS, /* type */
    2696                 :            :   "lim", /* name */
    2697                 :            :   OPTGROUP_LOOP, /* optinfo_flags */
    2698                 :            :   TV_LIM, /* tv_id */
    2699                 :            :   PROP_cfg, /* properties_required */
    2700                 :            :   0, /* properties_provided */
    2701                 :            :   0, /* properties_destroyed */
    2702                 :            :   0, /* todo_flags_start */
    2703                 :            :   0, /* todo_flags_finish */
    2704                 :            : };
    2705                 :            : 
    2706                 :            : class pass_lim : public gimple_opt_pass
    2707                 :            : {
    2708                 :            : public:
    2709                 :     803092 :   pass_lim (gcc::context *ctxt)
    2710                 :    1606180 :     : gimple_opt_pass (pass_data_lim, ctxt)
    2711                 :            :   {}
    2712                 :            : 
    2713                 :            :   /* opt_pass methods: */
    2714                 :     602319 :   opt_pass * clone () { return new pass_lim (m_ctxt); }
    2715                 :     845920 :   virtual bool gate (function *) { return flag_tree_loop_im != 0; }
    2716                 :            :   virtual unsigned int execute (function *);
    2717                 :            : 
    2718                 :            : }; // class pass_lim
    2719                 :            : 
    2720                 :            : unsigned int
    2721                 :     845660 : pass_lim::execute (function *fun)
    2722                 :            : {
    2723                 :     845660 :   bool in_loop_pipeline = scev_initialized_p ();
    2724                 :     845660 :   if (!in_loop_pipeline)
    2725                 :     687511 :     loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
    2726                 :            : 
    2727                 :    1691320 :   if (number_of_loops (fun) <= 1)
    2728                 :            :     return 0;
    2729                 :     316604 :   unsigned int todo = tree_ssa_lim ();
    2730                 :            : 
    2731                 :     316604 :   if (!in_loop_pipeline)
    2732                 :     158455 :     loop_optimizer_finalize ();
    2733                 :            :   else
    2734                 :     158149 :     scev_reset ();
    2735                 :            :   return todo;
    2736                 :            : }
    2737                 :            : 
    2738                 :            : } // anon namespace
    2739                 :            : 
    2740                 :            : gimple_opt_pass *
    2741                 :     200773 : make_pass_lim (gcc::context *ctxt)
    2742                 :            : {
    2743                 :     200773 :   return new pass_lim (ctxt);
    2744                 :            : }
    2745                 :            : 
    2746                 :            : 

Generated by: LCOV version 1.0

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