LCOV - code coverage report
Current view: top level - gcc - loop-invariant.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 96.9 % 989 958
Test Date: 2026-11-14 16:39:50 Functions: 100.0 % 54 54
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* RTL-level loop invariant motion.
       2              :    Copyright (C) 2004-2026 Free Software Foundation, Inc.
       3              : 
       4              : This file is part of GCC.
       5              : 
       6              : GCC is free software; you can redistribute it and/or modify it
       7              : under the terms of the GNU General Public License as published by the
       8              : Free Software Foundation; either version 3, or (at your option) any
       9              : later version.
      10              : 
      11              : GCC is distributed in the hope that it will be useful, but WITHOUT
      12              : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14              : for more details.
      15              : 
      16              : You should have received a copy of the GNU General Public License
      17              : along with GCC; see the file COPYING3.  If not see
      18              : <http://www.gnu.org/licenses/>.  */
      19              : 
      20              : /* This implements the loop invariant motion pass.  It is very simple
      21              :    (no calls, no loads/stores, etc.).  This should be sufficient to cleanup
      22              :    things like address arithmetics -- other more complicated invariants should
      23              :    be eliminated on GIMPLE either in tree-ssa-loop-im.cc or in tree-ssa-pre.cc.
      24              : 
      25              :    We proceed loop by loop -- it is simpler than trying to handle things
      26              :    globally and should not lose much.  First we inspect all sets inside loop
      27              :    and create a dependency graph on insns (saying "to move this insn, you must
      28              :    also move the following insns").
      29              : 
      30              :    We then need to determine what to move.  We estimate the number of registers
      31              :    used and move as many invariants as possible while we still have enough free
      32              :    registers.  We prefer the expensive invariants.
      33              : 
      34              :    Then we move the selected invariants out of the loop, creating a new
      35              :    temporaries for them if necessary.  */
      36              : 
      37              : #include "config.h"
      38              : #include "system.h"
      39              : #include "coretypes.h"
      40              : #include "backend.h"
      41              : #include "target.h"
      42              : #include "rtl.h"
      43              : #include "tree.h"
      44              : #include "cfghooks.h"
      45              : #include "df.h"
      46              : #include "memmodel.h"
      47              : #include "tm_p.h"
      48              : #include "insn-config.h"
      49              : #include "regs.h"
      50              : #include "ira.h"
      51              : #include "recog.h"
      52              : #include "cfgrtl.h"
      53              : #include "cfgloop.h"
      54              : #include "expr.h"
      55              : #include "rtl-iter.h"
      56              : #include "dumpfile.h"
      57              : 
      58              : /* The data stored for the loop.  */
      59              : 
      60              : class loop_data
      61              : {
      62              : public:
      63              :   class loop *outermost_exit;   /* The outermost exit of the loop.  */
      64              :   bool has_call;                /* True if the loop contains a call.  */
      65              :   /* Maximal register pressure inside loop for given register class
      66              :      (defined only for the pressure classes).  */
      67              :   int max_reg_pressure[N_REG_CLASSES];
      68              :   /* Loop regs referenced and live pseudo-registers.  */
      69              :   bitmap_head regs_ref;
      70              :   bitmap_head regs_live;
      71              : };
      72              : 
      73              : #define LOOP_DATA(LOOP) ((class loop_data *) (LOOP)->aux)
      74              : 
      75              : /* The description of an use.  */
      76              : 
      77              : struct use
      78              : {
      79              :   rtx *pos;                     /* Position of the use.  */
      80              :   rtx_insn *insn;               /* The insn in that the use occurs.  */
      81              :   unsigned addr_use_p;          /* Whether the use occurs in an address.  */
      82              :   struct use *next;             /* Next use in the list.  */
      83              : };
      84              : 
      85              : /* The description of a def.  */
      86              : 
      87              : struct def
      88              : {
      89              :   struct use *uses;             /* The list of uses that are uniquely reached
      90              :                                    by it.  */
      91              :   unsigned n_uses;              /* Number of such uses.  */
      92              :   unsigned n_addr_uses;         /* Number of uses in addresses.  */
      93              :   unsigned invno;               /* The corresponding invariant.  */
      94              :   bool can_prop_to_addr_uses;   /* True if the corresponding inv can be
      95              :                                    propagated into its address uses.  */
      96              : };
      97              : 
      98              : /* The data stored for each invariant.  */
      99              : 
     100              : struct invariant
     101              : {
     102              :   /* The number of the invariant.  */
     103              :   unsigned invno;
     104              : 
     105              :   /* The number of the invariant with the same value.  */
     106              :   unsigned eqto;
     107              : 
     108              :   /* The number of invariants which eqto this.  */
     109              :   unsigned eqno;
     110              : 
     111              :   /* If we moved the invariant out of the loop, the original regno
     112              :      that contained its value.  */
     113              :   int orig_regno;
     114              : 
     115              :   /* If we moved the invariant out of the loop, the register that contains its
     116              :      value.  */
     117              :   rtx reg;
     118              : 
     119              :   /* The definition of the invariant.  */
     120              :   struct def *def;
     121              : 
     122              :   /* The insn in that it is defined.  */
     123              :   rtx_insn *insn;
     124              : 
     125              :   /* Whether it is always executed.  */
     126              :   bool always_executed;
     127              : 
     128              :   /* Whether to move the invariant.  */
     129              :   bool move;
     130              : 
     131              :   /* Whether the invariant is cheap when used as an address.  */
     132              :   bool cheap_address;
     133              : 
     134              :   /* Cost of the invariant.  */
     135              :   unsigned cost;
     136              : 
     137              :   /* Used for detecting already visited invariants during determining
     138              :      costs of movements.  */
     139              :   unsigned stamp;
     140              : 
     141              :   /* The invariants it depends on.  */
     142              :   bitmap depends_on;
     143              : };
     144              : 
     145              : /* Currently processed loop.  */
     146              : static class loop *curr_loop;
     147              : 
     148              : /* Table of invariants indexed by the df_ref uid field.  */
     149              : 
     150              : static unsigned int invariant_table_size = 0;
     151              : static struct invariant ** invariant_table;
     152              : 
     153              : /* Entry for hash table of invariant expressions.  */
     154              : 
     155              : struct invariant_expr_entry
     156              : {
     157              :   /* The invariant.  */
     158              :   struct invariant *inv;
     159              : 
     160              :   /* Its value.  */
     161              :   rtx expr;
     162              : 
     163              :   /* Its mode.  */
     164              :   machine_mode mode;
     165              : 
     166              :   /* Its hash.  */
     167              :   hashval_t hash;
     168              : };
     169              : 
     170              : /* The actual stamp for marking already visited invariants during determining
     171              :    costs of movements.  */
     172              : 
     173              : static unsigned actual_stamp;
     174              : 
     175              : typedef struct invariant *invariant_p;
     176              : 
     177              : 
     178              : /* The invariants.  */
     179              : 
     180              : static vec<invariant_p> invariants;
     181              : 
     182              : /* Check the size of the invariant table and realloc if necessary.  */
     183              : 
     184              : static void
     185     25091102 : check_invariant_table_size (void)
     186              : {
     187     25091102 :   if (invariant_table_size < DF_DEFS_TABLE_SIZE ())
     188              :     {
     189       302054 :       unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
     190       302054 :       invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
     191       302054 :       memset (&invariant_table[invariant_table_size], 0,
     192       302054 :               (new_size - invariant_table_size) * sizeof (struct invariant *));
     193       302054 :       invariant_table_size = new_size;
     194              :     }
     195     25091102 : }
     196              : 
     197              : /* Test for possibility of invariantness of X.  */
     198              : 
     199              : static bool
     200     19256134 : check_maybe_invariant (rtx x)
     201              : {
     202     19256134 :   enum rtx_code code = GET_CODE (x);
     203     19256134 :   int i, j;
     204     19256134 :   const char *fmt;
     205              : 
     206     19256134 :   switch (code)
     207              :     {
     208              :     CASE_CONST_ANY:
     209              :     case SYMBOL_REF:
     210              :     case CONST:
     211              :     case LABEL_REF:
     212              :       return true;
     213              : 
     214              :     case PC:
     215              :     case UNSPEC_VOLATILE:
     216              :     case CALL:
     217              :       return false;
     218              : 
     219              :     case REG:
     220              :       return true;
     221              : 
     222      1844401 :     case MEM:
     223              :       /* Load/store motion is done elsewhere.  ??? Perhaps also add it here?
     224              :          It should not be hard, and might be faster than "elsewhere".  */
     225              : 
     226              :       /* Just handle the most trivial case where we load from an unchanging
     227              :          location (most importantly, pic tables).  */
     228      1844401 :       if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
     229              :         break;
     230              : 
     231              :       return false;
     232              : 
     233          580 :     case ASM_OPERANDS:
     234              :       /* Don't mess with insns declared volatile.  */
     235          580 :       if (MEM_VOLATILE_P (x))
     236              :         return false;
     237              :       break;
     238              : 
     239              :     default:
     240              :       break;
     241              :     }
     242              : 
     243      5058420 :   fmt = GET_RTX_FORMAT (code);
     244     14127554 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     245              :     {
     246      9252687 :       if (fmt[i] == 'e')
     247              :         {
     248      8300626 :           if (!check_maybe_invariant (XEXP (x, i)))
     249              :             return false;
     250              :         }
     251       952061 :       else if (fmt[i] == 'E')
     252              :         {
     253      1594705 :           for (j = 0; j < XVECLEN (x, i); j++)
     254      1222557 :             if (!check_maybe_invariant (XVECEXP (x, i, j)))
     255              :               return false;
     256              :         }
     257              :     }
     258              : 
     259              :   return true;
     260              : }
     261              : 
     262              : /* Returns the invariant definition for USE, or NULL if USE is not
     263              :    invariant.  */
     264              : 
     265              : static struct invariant *
     266     24972890 : invariant_for_use (df_ref use)
     267              : {
     268     24972890 :   struct df_link *defs;
     269     24972890 :   df_ref def;
     270     24972890 :   basic_block bb = DF_REF_BB (use), def_bb;
     271              : 
     272     24972890 :   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
     273              :     return NULL;
     274              : 
     275     24926478 :   defs = DF_REF_CHAIN (use);
     276     24926478 :   if (!defs || defs->next)
     277              :     return NULL;
     278     17883721 :   def = defs->ref;
     279     17883721 :   check_invariant_table_size ();
     280     17883721 :   if (!invariant_table[DF_REF_ID (def)])
     281              :     return NULL;
     282              : 
     283      1520236 :   def_bb = DF_REF_BB (def);
     284      1520236 :   if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
     285              :     return NULL;
     286      1519908 :   return invariant_table[DF_REF_ID (def)];
     287              : }
     288              : 
     289              : /* Computes hash value for invariant expression X in INSN.  */
     290              : 
     291              : static hashval_t
     292      1875233 : hash_invariant_expr_1 (rtx_insn *insn, rtx x)
     293              : {
     294      1875233 :   enum rtx_code code = GET_CODE (x);
     295      1875233 :   int i, j;
     296      1875233 :   const char *fmt;
     297      1875233 :   hashval_t val = code;
     298      1875233 :   int do_not_record_p;
     299      1875233 :   df_ref use;
     300      1875233 :   struct invariant *inv;
     301              : 
     302      1875233 :   switch (code)
     303              :     {
     304       845474 :     CASE_CONST_ANY:
     305       845474 :     case SYMBOL_REF:
     306       845474 :     case CONST:
     307       845474 :     case LABEL_REF:
     308       845474 :       return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
     309              : 
     310       733645 :     case REG:
     311       733645 :       use = df_find_use (insn, x);
     312       733645 :       if (!use)
     313            0 :         return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
     314       733645 :       inv = invariant_for_use (use);
     315       733645 :       if (!inv)
     316       476064 :         return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
     317              : 
     318       257581 :       gcc_assert (inv->eqto != ~0u);
     319              :       return inv->eqto;
     320              : 
     321       296114 :     default:
     322       296114 :       break;
     323              :     }
     324              : 
     325       296114 :   fmt = GET_RTX_FORMAT (code);
     326       841992 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     327              :     {
     328       545878 :       if (fmt[i] == 'e')
     329       497394 :         val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
     330              :       else if (fmt[i] == 'E')
     331              :         {
     332         7085 :           for (j = 0; j < XVECLEN (x, i); j++)
     333         5781 :             val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
     334              :         }
     335              :       else if (fmt[i] == 'i' || fmt[i] == 'n')
     336          228 :         val ^= XINT (x, i);
     337              :       else if (fmt[i] == 'L')
     338           51 :         val ^= XLOC (x, i);
     339              :       else if (fmt[i] == 'p')
     340         7637 :         val ^= constant_lower_bound (SUBREG_BYTE (x));
     341              :     }
     342              : 
     343              :   return val;
     344              : }
     345              : 
     346              : /* Returns true if the invariant expressions E1 and E2 used in insns INSN1
     347              :    and INSN2 have always the same value.  */
     348              : 
     349              : static bool
     350      2556023 : invariant_expr_equal_p (rtx_insn *insn1, rtx e1, rtx_insn *insn2, rtx e2)
     351              : {
     352      2556023 :   enum rtx_code code = GET_CODE (e1);
     353      2556023 :   int i, j;
     354      2556023 :   const char *fmt;
     355      2556023 :   df_ref use1, use2;
     356      2556023 :   struct invariant *inv1 = NULL, *inv2 = NULL;
     357      2556023 :   rtx sub1, sub2;
     358              : 
     359              :   /* If mode of only one of the operands is VOIDmode, it is not equivalent to
     360              :      the other one.  If both are VOIDmode, we rely on the caller of this
     361              :      function to verify that their modes are the same.  */
     362      2556023 :   if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
     363              :     return false;
     364              : 
     365      1390561 :   switch (code)
     366              :     {
     367       629956 :     CASE_CONST_ANY:
     368       629956 :     case SYMBOL_REF:
     369       629956 :     case CONST:
     370       629956 :     case LABEL_REF:
     371       629956 :       return rtx_equal_p (e1, e2);
     372              : 
     373       583966 :     case REG:
     374       583966 :       use1 = df_find_use (insn1, e1);
     375       583966 :       use2 = df_find_use (insn2, e2);
     376       583966 :       if (use1)
     377       583966 :         inv1 = invariant_for_use (use1);
     378       583966 :       if (use2)
     379       583966 :         inv2 = invariant_for_use (use2);
     380              : 
     381       583966 :       if (!inv1 && !inv2)
     382       229664 :         return rtx_equal_p (e1, e2);
     383              : 
     384       354302 :       if (!inv1 || !inv2)
     385              :         return false;
     386              : 
     387       243949 :       gcc_assert (inv1->eqto != ~0u);
     388       243949 :       gcc_assert (inv2->eqto != ~0u);
     389       243949 :       return inv1->eqto == inv2->eqto;
     390              : 
     391       176639 :     default:
     392       176639 :       break;
     393              :     }
     394              : 
     395       176639 :   fmt = GET_RTX_FORMAT (code);
     396       231104 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     397              :     {
     398       207545 :       if (fmt[i] == 'e')
     399              :         {
     400       180201 :           sub1 = XEXP (e1, i);
     401       180201 :           sub2 = XEXP (e2, i);
     402              : 
     403       180201 :           if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
     404              :             return false;
     405              :         }
     406              : 
     407              :       else if (fmt[i] == 'E')
     408              :         {
     409          860 :           if (XVECLEN (e1, i) != XVECLEN (e2, i))
     410              :             return false;
     411              : 
     412         3296 :           for (j = 0; j < XVECLEN (e1, i); j++)
     413              :             {
     414         2809 :               sub1 = XVECEXP (e1, i, j);
     415         2809 :               sub2 = XVECEXP (e2, i, j);
     416              : 
     417         2809 :               if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
     418              :                 return false;
     419              :             }
     420              :         }
     421              :       else if (fmt[i] == 'i' || fmt[i] == 'n')
     422              :         {
     423           79 :           if (XINT (e1, i) != XINT (e2, i))
     424              :             return false;
     425              :         }
     426              :       else if (fmt[i] == 'p')
     427              :         {
     428         4948 :           if (maybe_ne (SUBREG_BYTE (e1), SUBREG_BYTE (e2)))
     429              :             return false;
     430              :         }
     431              :       /* Unhandled type of subexpression, we fail conservatively.  */
     432              :       else
     433              :         return false;
     434              :     }
     435              : 
     436              :   return true;
     437              : }
     438              : 
     439              : struct invariant_expr_hasher : free_ptr_hash <invariant_expr_entry>
     440              : {
     441              :   static inline hashval_t hash (const invariant_expr_entry *);
     442              :   static inline bool equal (const invariant_expr_entry *,
     443              :                             const invariant_expr_entry *);
     444              : };
     445              : 
     446              : /* Returns hash value for invariant expression entry ENTRY.  */
     447              : 
     448              : inline hashval_t
     449      3144089 : invariant_expr_hasher::hash (const invariant_expr_entry *entry)
     450              : {
     451      3144089 :   return entry->hash;
     452              : }
     453              : 
     454              : /* Compares invariant expression entries ENTRY1 and ENTRY2.  */
     455              : 
     456              : inline bool
     457      3631180 : invariant_expr_hasher::equal (const invariant_expr_entry *entry1,
     458              :                               const invariant_expr_entry *entry2)
     459              : {
     460      3631180 :   if (entry1->mode != entry2->mode)
     461              :     return 0;
     462              : 
     463      2373013 :   return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
     464      2373013 :                                  entry2->inv->insn, entry2->expr);
     465              : }
     466              : 
     467              : typedef hash_table<invariant_expr_hasher> invariant_htab_type;
     468              : 
     469              : /* Checks whether invariant with value EXPR in machine mode MODE is
     470              :    recorded in EQ.  If this is the case, return the invariant.  Otherwise
     471              :    insert INV to the table for this expression and return INV.  */
     472              : 
     473              : static struct invariant *
     474      1372058 : find_or_insert_inv (invariant_htab_type *eq, rtx expr, machine_mode mode,
     475              :                     struct invariant *inv)
     476              : {
     477      1372058 :   hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
     478      1372058 :   struct invariant_expr_entry *entry;
     479      1372058 :   struct invariant_expr_entry pentry;
     480      1372058 :   invariant_expr_entry **slot;
     481              : 
     482      1372058 :   pentry.expr = expr;
     483      1372058 :   pentry.inv = inv;
     484      1372058 :   pentry.mode = mode;
     485      1372058 :   slot = eq->find_slot_with_hash (&pentry, hash, INSERT);
     486      1372058 :   entry = *slot;
     487              : 
     488      1372058 :   if (entry)
     489       388275 :     return entry->inv;
     490              : 
     491       983783 :   entry = XNEW (struct invariant_expr_entry);
     492       983783 :   entry->inv = inv;
     493       983783 :   entry->expr = expr;
     494       983783 :   entry->mode = mode;
     495       983783 :   entry->hash = hash;
     496       983783 :   *slot = entry;
     497              : 
     498       983783 :   return inv;
     499              : }
     500              : 
     501              : /* Finds invariants identical to INV and records the equivalence.  EQ is the
     502              :    hash table of the invariants.  */
     503              : 
     504              : static void
     505      1631177 : find_identical_invariants (invariant_htab_type *eq, struct invariant *inv)
     506              : {
     507      1631177 :   unsigned depno;
     508      1631177 :   bitmap_iterator bi;
     509      1631177 :   struct invariant *dep;
     510      1631177 :   rtx expr, set;
     511      1631177 :   machine_mode mode;
     512      1631177 :   struct invariant *tmp;
     513              : 
     514      1631177 :   if (inv->eqto != ~0u)
     515       259119 :     return;
     516              : 
     517      1631177 :   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
     518              :     {
     519       259119 :       dep = invariants[depno];
     520       259119 :       find_identical_invariants (eq, dep);
     521              :     }
     522              : 
     523      1372058 :   set = single_set (inv->insn);
     524      1372058 :   expr = SET_SRC (set);
     525      1372058 :   mode = GET_MODE (expr);
     526      1372058 :   if (mode == VOIDmode)
     527       439870 :     mode = GET_MODE (SET_DEST (set));
     528              : 
     529      1372058 :   tmp = find_or_insert_inv (eq, expr, mode, inv);
     530      1372058 :   inv->eqto = tmp->invno;
     531              : 
     532      1372058 :   if (tmp->invno != inv->invno && inv->always_executed)
     533        68321 :     tmp->eqno++;
     534              : 
     535      1372058 :   if (dump_file && inv->eqto != inv->invno)
     536            0 :     fprintf (dump_file,
     537              :              "Invariant %d is equivalent to invariant %d.\n",
     538              :              inv->invno, inv->eqto);
     539              : }
     540              : 
     541              : /* Find invariants with the same value and record the equivalences.  */
     542              : 
     543              : static void
     544       671721 : merge_identical_invariants (void)
     545              : {
     546       671721 :   unsigned i;
     547       671721 :   struct invariant *inv;
     548       671721 :   invariant_htab_type eq (invariants.length ());
     549              : 
     550      2715500 :   FOR_EACH_VEC_ELT (invariants, i, inv)
     551      1372058 :     find_identical_invariants (&eq, inv);
     552       671721 : }
     553              : 
     554              : /* Determines the basic blocks inside LOOP that are always executed and
     555              :    stores their bitmap to ALWAYS_REACHED.  MAY_EXIT is a bitmap of
     556              :    basic blocks that may either exit the loop, or contain the call that
     557              :    does not have to return.  BODY is body of the loop obtained by
     558              :    get_loop_body_in_dom_order.  */
     559              : 
     560              : static void
     561      1343442 : compute_always_reached (class loop *loop, basic_block *body,
     562              :                         bitmap may_exit, bitmap always_reached)
     563              : {
     564      1343442 :   unsigned i;
     565              : 
     566      2552955 :   for (i = 0; i < loop->num_nodes; i++)
     567              :     {
     568      2540284 :       if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
     569      1609773 :         bitmap_set_bit (always_reached, i);
     570              : 
     571      2540284 :       if (bitmap_bit_p (may_exit, i))
     572              :         return;
     573              :     }
     574              : }
     575              : 
     576              : /* Finds exits out of the LOOP with body BODY.  Marks blocks in that we may
     577              :    exit the loop by cfg edge to HAS_EXIT and MAY_EXIT.  In MAY_EXIT
     578              :    additionally mark blocks that may exit due to a call.  */
     579              : 
     580              : static void
     581       671721 : find_exits (class loop *loop, basic_block *body,
     582              :             bitmap may_exit, bitmap has_exit)
     583              : {
     584       671721 :   unsigned i;
     585       671721 :   edge_iterator ei;
     586       671721 :   edge e;
     587       671721 :   class loop *outermost_exit = loop, *aexit;
     588       671721 :   bool has_call = false;
     589       671721 :   rtx_insn *insn;
     590              : 
     591      4901640 :   for (i = 0; i < loop->num_nodes; i++)
     592              :     {
     593      4229919 :       if (body[i]->loop_father == loop)
     594              :         {
     595     31138647 :           FOR_BB_INSNS (body[i], insn)
     596              :             {
     597     28487508 :               auto call = dyn_cast<rtx_call_insn *> (insn);
     598       486552 :               if (call
     599       486552 :                   && (RTL_LOOPING_CONST_OR_PURE_CALL_P (call)
     600       484559 :                       || !RTL_CONST_OR_PURE_CALL_P (call)))
     601              :                 {
     602       446277 :                   has_call = true;
     603       446277 :                   bitmap_set_bit (may_exit, i);
     604       446277 :                   break;
     605              :                 }
     606              :             }
     607              : 
     608      8027320 :           FOR_EACH_EDGE (e, ei, body[i]->succs)
     609              :             {
     610      4889629 :               if (! flow_bb_inside_loop_p (loop, e->dest))
     611              :                 {
     612      1141003 :                   bitmap_set_bit (may_exit, i);
     613      1141003 :                   bitmap_set_bit (has_exit, i);
     614      1141003 :                   outermost_exit = find_common_loop (outermost_exit,
     615      1141003 :                                                      e->dest->loop_father);
     616              :                 }
     617              :               /* If we enter a subloop that might never terminate treat
     618              :                  it like a possible exit.  */
     619      4889629 :               if (flow_loop_nested_p (loop, e->dest->loop_father))
     620       160321 :                 bitmap_set_bit (may_exit, i);
     621              :             }
     622      3137691 :           continue;
     623      3137691 :         }
     624              : 
     625              :       /* Use the data stored for the subloop to decide whether we may exit
     626              :          through it.  It is sufficient to do this for header of the loop,
     627              :          as other basic blocks inside it must be dominated by it.  */
     628      1092228 :       if (body[i]->loop_father->header != body[i])
     629       849246 :         continue;
     630              : 
     631       242982 :       if (LOOP_DATA (body[i]->loop_father)->has_call)
     632              :         {
     633        67976 :           has_call = true;
     634        67976 :           bitmap_set_bit (may_exit, i);
     635              :         }
     636       242982 :       aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
     637       242982 :       if (aexit != loop)
     638              :         {
     639       127564 :           bitmap_set_bit (may_exit, i);
     640       127564 :           bitmap_set_bit (has_exit, i);
     641              : 
     642       127564 :           if (flow_loop_nested_p (aexit, outermost_exit))
     643      4229919 :             outermost_exit = aexit;
     644              :         }
     645              :     }
     646              : 
     647       671721 :   if (loop->aux == NULL)
     648              :     {
     649       671720 :       loop->aux = xcalloc (1, sizeof (class loop_data));
     650       671720 :       bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
     651       671720 :       bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
     652              :     }
     653       671721 :   LOOP_DATA (loop)->outermost_exit = outermost_exit;
     654       671721 :   LOOP_DATA (loop)->has_call = has_call;
     655       671721 : }
     656              : 
     657              : /* Check whether we may assign a value to X from a register.  */
     658              : 
     659              : static bool
     660     13702924 : may_assign_reg_p (rtx x)
     661              : {
     662     13702924 :   return (GET_MODE (x) != VOIDmode
     663     13701410 :           && GET_MODE (x) != BLKmode
     664     13683967 :           && can_copy_p (GET_MODE (x))
     665              :           /* Do not mess with the frame pointer adjustments that can
     666              :              be generated e.g. by expand_builtin_setjmp_receiver.  */
     667     11647546 :           && x != frame_pointer_rtx
     668     25350470 :           && (!REG_P (x)
     669      9823349 :               || !HARD_REGISTER_P (x)
     670      1692589 :               || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
     671              : }
     672              : 
     673              : /* Finds definitions that may correspond to invariants in LOOP with body
     674              :    BODY.  */
     675              : 
     676              : static void
     677       671721 : find_defs (class loop *loop)
     678              : {
     679       671721 :   if (dump_file)
     680              :     {
     681           21 :       fprintf (dump_file,
     682              :                "*****starting processing of loop %d ******\n",
     683              :                loop->num);
     684              :     }
     685              : 
     686       671721 :   df_chain_add_problem (DF_UD_CHAIN);
     687       671721 :   df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
     688       671721 :   df_analyze_loop (loop);
     689       671721 :   check_invariant_table_size ();
     690              : 
     691       671721 :   if (dump_file)
     692              :     {
     693           21 :       df_dump_region (dump_file);
     694           21 :       fprintf (dump_file,
     695              :                "*****ending processing of loop %d ******\n",
     696              :                loop->num);
     697              :     }
     698       671721 : }
     699              : 
     700              : /* Creates a new invariant for definition DEF in INSN, depending on invariants
     701              :    in DEPENDS_ON.  ALWAYS_EXECUTED is true if the insn is always executed,
     702              :    unless the program ends due to a function call.  The newly created invariant
     703              :    is returned.  */
     704              : 
     705              : static struct invariant *
     706      1372058 : create_new_invariant (struct def *def, rtx_insn *insn, bitmap depends_on,
     707              :                       bool always_executed)
     708              : {
     709      1372058 :   struct invariant *inv = XNEW (struct invariant);
     710      1372058 :   rtx set = single_set (insn);
     711      1372058 :   bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
     712              : 
     713      1372058 :   inv->def = def;
     714      1372058 :   inv->always_executed = always_executed;
     715      1372058 :   inv->depends_on = depends_on;
     716              : 
     717              :   /* If the set is simple, usually by moving it we move the whole store out of
     718              :      the loop.  Otherwise we save only cost of the computation.  */
     719      1372058 :   if (def)
     720              :     {
     721       621442 :       inv->cost = set_rtx_cost (set, speed);
     722              :       /* ??? Try to determine cheapness of address computation.  Unfortunately
     723              :          the address cost is only a relative measure, we can't really compare
     724              :          it with any absolute number, but only with other address costs.
     725              :          But here we don't have any other addresses, so compare with a magic
     726              :          number anyway.  It has to be large enough to not regress PR33928
     727              :          (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
     728              :          enough to not regress 410.bwaves either (by still moving reg+reg
     729              :          invariants).
     730              :          See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html .  */
     731       621442 :       if (SCALAR_INT_MODE_P (GET_MODE (SET_DEST (set))))
     732       467904 :         inv->cheap_address = address_cost (SET_SRC (set), word_mode,
     733       467904 :                                            ADDR_SPACE_GENERIC, speed) < 3;
     734              :       else
     735       153538 :         inv->cheap_address = false;
     736              :     }
     737              :   else
     738              :     {
     739       750616 :       inv->cost = set_src_cost (SET_SRC (set), GET_MODE (SET_DEST (set)),
     740              :                                 speed);
     741       750616 :       inv->cheap_address = false;
     742              :     }
     743              : 
     744      1372058 :   inv->move = false;
     745      1372058 :   inv->reg = NULL_RTX;
     746      1372058 :   inv->orig_regno = -1;
     747      1372058 :   inv->stamp = 0;
     748      1372058 :   inv->insn = insn;
     749              : 
     750      1372058 :   inv->invno = invariants.length ();
     751      1372058 :   inv->eqto = ~0u;
     752              : 
     753              :   /* Itself.  */
     754      1372058 :   inv->eqno = 1;
     755              : 
     756      1372058 :   if (def)
     757       621442 :     def->invno = inv->invno;
     758      1372058 :   invariants.safe_push (inv);
     759              : 
     760      1372058 :   if (dump_file)
     761              :     {
     762           12 :       fprintf (dump_file,
     763              :                "Set in insn %d is invariant (%d), cost %d, depends on ",
     764           12 :                INSN_UID (insn), inv->invno, inv->cost);
     765           12 :       dump_bitmap (dump_file, inv->depends_on);
     766              :     }
     767              : 
     768      1372058 :   return inv;
     769              : }
     770              : 
     771              : /* Return a canonical version of X for the address, from the point of view,
     772              :    that all multiplications are represented as MULT instead of the multiply
     773              :    by a power of 2 being represented as ASHIFT.
     774              : 
     775              :    Callers should prepare a copy of X because this function may modify it
     776              :    in place.  */
     777              : 
     778              : static void
     779        32722 : canonicalize_address_mult (rtx x)
     780              : {
     781        32722 :   subrtx_var_iterator::array_type array;
     782       213940 :   FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
     783              :     {
     784       181218 :       rtx sub = *iter;
     785       181218 :       scalar_int_mode sub_mode;
     786       311967 :       if (is_a <scalar_int_mode> (GET_MODE (sub), &sub_mode)
     787       130749 :           && GET_CODE (sub) == ASHIFT
     788          210 :           && CONST_INT_P (XEXP (sub, 1))
     789          420 :           && INTVAL (XEXP (sub, 1)) < GET_MODE_BITSIZE (sub_mode)
     790          210 :           && INTVAL (XEXP (sub, 1)) >= 0)
     791              :         {
     792          210 :           HOST_WIDE_INT shift = INTVAL (XEXP (sub, 1));
     793          210 :           PUT_CODE (sub, MULT);
     794          210 :           XEXP (sub, 1) = gen_int_mode (HOST_WIDE_INT_1 << shift, sub_mode);
     795          210 :           iter.skip_subrtxes ();
     796              :         }
     797              :     }
     798        32722 : }
     799              : 
     800              : /* Maximum number of sub expressions in address.  We set it to
     801              :    a small integer since it's unlikely to have a complicated
     802              :    address expression.  */
     803              : 
     804              : #define MAX_CANON_ADDR_PARTS (5)
     805              : 
     806              : /* Collect sub expressions in address X with PLUS as the separator.
     807              :    Sub expressions are stored in vector ADDR_PARTS.  */
     808              : 
     809              : static void
     810        32722 : collect_address_parts (rtx x, vec<rtx> *addr_parts)
     811              : {
     812        32722 :   subrtx_var_iterator::array_type array;
     813       178776 :   FOR_EACH_SUBRTX_VAR (iter, array, x, NONCONST)
     814              :     {
     815       146054 :       rtx sub = *iter;
     816              : 
     817       146054 :       if (GET_CODE (sub) != PLUS)
     818              :         {
     819        89388 :           addr_parts->safe_push (sub);
     820        89388 :           iter.skip_subrtxes ();
     821              :         }
     822              :     }
     823        32722 : }
     824              : 
     825              : /* Compare function for sorting sub expressions X and Y based on
     826              :    precedence defined for communitive operations.  */
     827              : 
     828              : static int
     829       299046 : compare_address_parts (const void *x, const void *y)
     830              : {
     831       299046 :   const rtx *rx = (const rtx *)x;
     832       299046 :   const rtx *ry = (const rtx *)y;
     833       299046 :   int px = commutative_operand_precedence (*rx);
     834       299046 :   int py = commutative_operand_precedence (*ry);
     835              : 
     836       299046 :   return (py - px);
     837              : }
     838              : 
     839              : /* Return a canonical version address for X by following steps:
     840              :      1) Rewrite ASHIFT into MULT recursively.
     841              :      2) Divide address into sub expressions with PLUS as the
     842              :         separator.
     843              :      3) Sort sub expressions according to precedence defined
     844              :         for communative operations.
     845              :      4) Simplify CONST_INT_P sub expressions.
     846              :      5) Create new canonicalized address and return.
     847              :    Callers should prepare a copy of X because this function may
     848              :    modify it in place.  */
     849              : 
     850              : static rtx
     851        32722 : canonicalize_address (rtx x)
     852              : {
     853        32722 :   rtx res;
     854        32722 :   unsigned int i, j;
     855        32722 :   machine_mode mode = GET_MODE (x);
     856        32722 :   auto_vec<rtx, MAX_CANON_ADDR_PARTS> addr_parts;
     857              : 
     858              :   /* Rewrite ASHIFT into MULT.  */
     859        32722 :   canonicalize_address_mult (x);
     860              :   /* Divide address into sub expressions.  */
     861        32722 :   collect_address_parts (x, &addr_parts);
     862              :   /* Unlikely to have very complicated address.  */
     863        32722 :   if (addr_parts.length () < 2
     864        32722 :       || addr_parts.length () > MAX_CANON_ADDR_PARTS)
     865              :     return x;
     866              : 
     867              :   /* Sort sub expressions according to canonicalization precedence.  */
     868        32697 :   addr_parts.qsort (compare_address_parts);
     869              : 
     870              :   /* Simplify all constant int summary if possible.  */
     871       121115 :   for (i = 0; i < addr_parts.length (); i++)
     872        86173 :     if (CONST_INT_P (addr_parts[i]))
     873              :       break;
     874              : 
     875        35887 :   for (j = i + 1; j < addr_parts.length (); j++)
     876              :     {
     877         3190 :       gcc_assert (CONST_INT_P (addr_parts[j]));
     878         3190 :       addr_parts[i] = simplify_gen_binary (PLUS, mode,
     879         3190 :                                            addr_parts[i],
     880         3190 :                                            addr_parts[j]);
     881              :     }
     882              : 
     883              :   /* Chain PLUS operators to the left for !CONST_INT_P sub expressions.  */
     884        32697 :   res = addr_parts[0];
     885        55735 :   for (j = 1; j < i; j++)
     886        23038 :     res = simplify_gen_binary (PLUS, mode, res, addr_parts[j]);
     887              : 
     888              :   /* Pickup the last CONST_INT_P sub expression.  */
     889        63174 :   if (i < addr_parts.length ())
     890        30452 :     res = simplify_gen_binary (PLUS, mode, res, addr_parts[i]);
     891              : 
     892              :   return res;
     893        32722 : }
     894              : 
     895              : /* Given invariant DEF and its address USE, check if the corresponding
     896              :    invariant expr can be propagated into the use or not.  */
     897              : 
     898              : static bool
     899        57912 : inv_can_prop_to_addr_use (struct def *def, df_ref use)
     900              : {
     901        57912 :   struct invariant *inv;
     902        57912 :   rtx *pos = DF_REF_REAL_LOC (use), def_set, use_set;
     903        57912 :   rtx_insn *use_insn = DF_REF_INSN (use);
     904        57912 :   rtx_insn *def_insn;
     905        57912 :   bool ok;
     906              : 
     907        57912 :   inv = invariants[def->invno];
     908              :   /* No need to check if address expression is expensive.  */
     909        57912 :   if (!inv->cheap_address)
     910              :     return false;
     911              : 
     912        48522 :   def_insn = inv->insn;
     913        48522 :   def_set = single_set (def_insn);
     914        48522 :   if (!def_set)
     915              :     return false;
     916              : 
     917        48522 :   validate_unshare_change (use_insn, pos, SET_SRC (def_set), true);
     918        48522 :   ok = verify_changes (0);
     919              :   /* Try harder with canonicalization in address expression.  */
     920        48522 :   if (!ok && (use_set = single_set (use_insn)) != NULL_RTX)
     921              :     {
     922        36219 :       rtx src, dest, mem = NULL_RTX;
     923              : 
     924        36219 :       src = SET_SRC (use_set);
     925        36219 :       dest = SET_DEST (use_set);
     926        36219 :       if (MEM_P (src))
     927              :         mem = src;
     928        14224 :       else if (MEM_P (dest))
     929              :         mem = dest;
     930              : 
     931              :       if (mem != NULL_RTX
     932        68967 :           && !memory_address_addr_space_p (GET_MODE (mem),
     933              :                                            XEXP (mem, 0),
     934        32748 :                                            MEM_ADDR_SPACE (mem)))
     935              :         {
     936        32722 :           rtx addr = canonicalize_address (copy_rtx (XEXP (mem, 0)));
     937        65444 :           if (memory_address_addr_space_p (GET_MODE (mem),
     938        32722 :                                            addr, MEM_ADDR_SPACE (mem)))
     939        42424 :             ok = true;
     940              :         }
     941              :     }
     942        48522 :   cancel_changes (0);
     943        48522 :   return ok;
     944              : }
     945              : 
     946              : /* Record USE at DEF.  */
     947              : 
     948              : static void
     949       664076 : record_use (struct def *def, df_ref use)
     950              : {
     951       664076 :   struct use *u = XNEW (struct use);
     952              : 
     953       664076 :   u->pos = DF_REF_REAL_LOC (use);
     954       664076 :   u->insn = DF_REF_INSN (use);
     955       664076 :   u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD
     956       664076 :                    || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
     957       664076 :   u->next = def->uses;
     958       664076 :   def->uses = u;
     959       664076 :   def->n_uses++;
     960       664076 :   if (u->addr_use_p)
     961              :     {
     962              :       /* Initialize propagation information if this is the first addr
     963              :          use of the inv def.  */
     964        63784 :       if (def->n_addr_uses == 0)
     965        45429 :         def->can_prop_to_addr_uses = true;
     966              : 
     967        63784 :       def->n_addr_uses++;
     968        63784 :       if (def->can_prop_to_addr_uses && !inv_can_prop_to_addr_use (def, use))
     969        15488 :         def->can_prop_to_addr_uses = false;
     970              :     }
     971       664076 : }
     972              : 
     973              : /* Finds the invariants USE depends on and store them to the DEPENDS_ON
     974              :    bitmap.  Returns true if all dependencies of USE are known to be
     975              :    loop invariants, false otherwise.  */
     976              : 
     977              : static bool
     978      7105259 : check_dependency (basic_block bb, df_ref use, bitmap depends_on)
     979              : {
     980      7105259 :   df_ref def;
     981      7105259 :   basic_block def_bb;
     982      7105259 :   struct df_link *defs;
     983      7105259 :   struct def *def_data;
     984      7105259 :   struct invariant *inv;
     985              : 
     986      7105259 :   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
     987              :     return false;
     988              : 
     989      7070771 :   defs = DF_REF_CHAIN (use);
     990      7070771 :   if (!defs)
     991              :     {
     992      1307343 :       unsigned int regno = DF_REF_REGNO (use);
     993              : 
     994              :       /* If this is the use of an uninitialized argument register that is
     995              :          likely to be spilled, do not move it lest this might extend its
     996              :          lifetime and cause reload to die.  This can occur for a call to
     997              :          a function taking complex number arguments and moving the insns
     998              :          preparing the arguments without moving the call itself wouldn't
     999              :          gain much in practice.  */
    1000      1307343 :       if ((DF_REF_FLAGS (use) & DF_HARD_REG_LIVE)
    1001          308 :           && FUNCTION_ARG_REGNO_P (regno)
    1002      1307348 :           && targetm.class_likely_spilled_p (REGNO_REG_CLASS (regno)))
    1003              :         return false;
    1004              : 
    1005      1307342 :       return true;
    1006              :     }
    1007              : 
    1008      5763428 :   if (defs->next)
    1009              :     return false;
    1010              : 
    1011      5242497 :   def = defs->ref;
    1012      5242497 :   check_invariant_table_size ();
    1013      5242497 :   inv = invariant_table[DF_REF_ID (def)];
    1014      5242497 :   if (!inv)
    1015              :     return false;
    1016              : 
    1017       285406 :   def_data = inv->def;
    1018       285406 :   gcc_assert (def_data != NULL);
    1019              : 
    1020       285406 :   def_bb = DF_REF_BB (def);
    1021              :   /* Note that in case bb == def_bb, we know that the definition
    1022              :      dominates insn, because def has invariant_table[DF_REF_ID(def)]
    1023              :      defined and we process the insns in the basic block bb
    1024              :      sequentially.  */
    1025       285406 :   if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
    1026              :     return false;
    1027              : 
    1028       285317 :   bitmap_set_bit (depends_on, def_data->invno);
    1029       285317 :   return true;
    1030              : }
    1031              : 
    1032              : 
    1033              : /* Finds the invariants INSN depends on and store them to the DEPENDS_ON
    1034              :    bitmap.  Returns true if all dependencies of INSN are known to be
    1035              :    loop invariants, false otherwise.  */
    1036              : 
    1037              : static bool
    1038      6884658 : check_dependencies (rtx_insn *insn, bitmap depends_on)
    1039              : {
    1040      6884658 :   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
    1041      6884658 :   df_ref use;
    1042      6884658 :   basic_block bb = BLOCK_FOR_INSN (insn);
    1043              : 
    1044      8331326 :   FOR_EACH_INSN_INFO_USE (use, insn_info)
    1045      6959268 :     if (!check_dependency (bb, use, depends_on))
    1046              :       return false;
    1047      1518049 :   FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
    1048       145991 :     if (!check_dependency (bb, use, depends_on))
    1049              :       return false;
    1050              : 
    1051              :   return true;
    1052              : }
    1053              : 
    1054              : /* Pre-check candidate DEST to skip the one which cannot make a valid insn
    1055              :    during move_invariant_reg.  SIMPLE is to skip HARD_REGISTER.  */
    1056              : static bool
    1057     11647546 : pre_check_invariant_p (bool simple, rtx dest)
    1058              : {
    1059     11647546 :   if (simple && REG_P (dest) && DF_REG_DEF_COUNT (REGNO (dest)) > 1)
    1060              :     {
    1061      2770085 :       df_ref use;
    1062      2770085 :       unsigned int i = REGNO (dest);
    1063      2770085 :       struct df_insn_info *insn_info;
    1064      2770085 :       df_ref def_rec;
    1065              : 
    1066     12565607 :       for (use = DF_REG_USE_CHAIN (i); use; use = DF_REF_NEXT_REG (use))
    1067              :         {
    1068     11746094 :           rtx_insn *ref = DF_REF_INSN (use);
    1069     11746094 :           insn_info = DF_INSN_INFO_GET (ref);
    1070              : 
    1071     20579878 :           FOR_EACH_INSN_INFO_DEF (def_rec, insn_info)
    1072     10784356 :             if (DF_REF_REGNO (def_rec) == i)
    1073              :               {
    1074              :                 /* Multi definitions at this stage, most likely are due to
    1075              :                    instruction constraints, which requires both read and write
    1076              :                    on the same register.  Since move_invariant_reg is not
    1077              :                    powerful enough to handle such cases, just ignore the INV
    1078              :                    and leave the chance to others.  */
    1079              :                 return false;
    1080              :               }
    1081              :         }
    1082              :     }
    1083              :   return true;
    1084              : }
    1085              : 
    1086              : /* Finds invariant in INSN.  ALWAYS_REACHED is true if the insn is always
    1087              :    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
    1088              :    unless the program ends due to a function call.  */
    1089              : 
    1090              : static void
    1091     15997161 : find_invariant_insn (rtx_insn *insn, bool always_reached, bool always_executed)
    1092              : {
    1093     15997161 :   df_ref ref;
    1094     15997161 :   struct def *def;
    1095     15997161 :   bitmap depends_on;
    1096     15997161 :   rtx set, dest;
    1097     15997161 :   bool simple = true;
    1098     15997161 :   struct invariant *inv;
    1099              : 
    1100              :   /* Jumps have control flow side-effects.  */
    1101     15997161 :   if (JUMP_P (insn))
    1102              :     return;
    1103              : 
    1104     14076573 :   set = single_set (insn);
    1105     14076573 :   if (!set)
    1106              :     return;
    1107     13702924 :   dest = SET_DEST (set);
    1108              : 
    1109     13702924 :   if (!REG_P (dest)
    1110     13702924 :       || HARD_REGISTER_P (dest))
    1111              :     simple = false;
    1112              : 
    1113     13702924 :   if (!may_assign_reg_p (dest)
    1114     11647546 :       || !pre_check_invariant_p (simple, dest)
    1115     23399898 :       || !check_maybe_invariant (SET_SRC (set)))
    1116              :     return;
    1117              : 
    1118              :   /* If the insn can throw exception, we cannot move it at all without changing
    1119              :      cfg.  */
    1120      7603268 :   if (can_throw_internal (insn))
    1121              :     return;
    1122              : 
    1123              :   /* We cannot make trapping insn executed, unless it was executed before.  */
    1124      7596491 :   if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
    1125              :     return;
    1126              : 
    1127              :   /* inline-asm that is not always executed cannot be moved
    1128              :      as it might conditionally trap. */
    1129      6884739 :   if (!always_reached && asm_noperands (PATTERN (insn)) >= 0)
    1130              :     return;
    1131              : 
    1132      6884658 :   depends_on = BITMAP_ALLOC (NULL);
    1133      6884658 :   if (!check_dependencies (insn, depends_on))
    1134              :     {
    1135      5512600 :       BITMAP_FREE (depends_on);
    1136      5512600 :       return;
    1137              :     }
    1138              : 
    1139      1372058 :   if (simple)
    1140       621442 :     def = XCNEW (struct def);
    1141              :   else
    1142              :     def = NULL;
    1143              : 
    1144      1372058 :   inv = create_new_invariant (def, insn, depends_on, always_executed);
    1145              : 
    1146      1372058 :   if (simple)
    1147              :     {
    1148       621442 :       ref = df_find_def (insn, dest);
    1149       621442 :       check_invariant_table_size ();
    1150       621442 :       invariant_table[DF_REF_ID (ref)] = inv;
    1151              :     }
    1152              : }
    1153              : 
    1154              : /* Record registers used in INSN that have a unique invariant definition.  */
    1155              : 
    1156              : static void
    1157     15997161 : record_uses (rtx_insn *insn)
    1158              : {
    1159     15997161 :   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
    1160     15997161 :   df_ref use;
    1161     15997161 :   struct invariant *inv;
    1162              : 
    1163     38572984 :   FOR_EACH_INSN_INFO_USE (use, insn_info)
    1164              :     {
    1165     22575823 :       inv = invariant_for_use (use);
    1166     22575823 :       if (inv)
    1167       663074 :         record_use (inv->def, use);
    1168              :     }
    1169     16492651 :   FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
    1170              :     {
    1171       495490 :       inv = invariant_for_use (use);
    1172       495490 :       if (inv)
    1173         1002 :         record_use (inv->def, use);
    1174              :     }
    1175     15997161 : }
    1176              : 
    1177              : /* Finds invariants in INSN.  ALWAYS_REACHED is true if the insn is always
    1178              :    executed.  ALWAYS_EXECUTED is true if the insn is always executed,
    1179              :    unless the program ends due to a function call.  */
    1180              : 
    1181              : static void
    1182     15997161 : find_invariants_insn (rtx_insn *insn, bool always_reached, bool always_executed)
    1183              : {
    1184            0 :   find_invariant_insn (insn, always_reached, always_executed);
    1185     15997161 :   record_uses (insn);
    1186            0 : }
    1187              : 
    1188              : /* Finds invariants in basic block BB.  ALWAYS_REACHED is true if the
    1189              :    basic block is always executed.  ALWAYS_EXECUTED is true if the basic
    1190              :    block is always executed, unless the program ends due to a function
    1191              :    call.  */
    1192              : 
    1193              : static void
    1194      4229919 : find_invariants_bb (class loop *loop, basic_block bb, bool always_reached,
    1195              :                     bool always_executed)
    1196              : {
    1197      4229919 :   rtx_insn *insn;
    1198      4229919 :   basic_block preheader = loop_preheader_edge (loop)->src;
    1199              : 
    1200              :   /* Don't move insn of cold BB out of loop to preheader to reduce calculations
    1201              :      and register live range in hot loop with cold BB.  */
    1202      4229919 :   if (!always_executed && preheader->count > bb->count)
    1203              :     {
    1204       719252 :       if (dump_file)
    1205            2 :         fprintf (dump_file, "Don't move invariant from bb: %d out of loop %d\n",
    1206              :                  bb->index, loop->num);
    1207              :       return;
    1208              :     }
    1209              : 
    1210     40680574 :   FOR_BB_INSNS (bb, insn)
    1211              :     {
    1212     37169907 :       if (!NONDEBUG_INSN_P (insn))
    1213     21172746 :         continue;
    1214              : 
    1215     15997161 :       find_invariants_insn (insn, always_reached, always_executed);
    1216              : 
    1217     15997161 :       auto call = dyn_cast<rtx_call_insn *> (insn);
    1218     15997161 :       if (always_reached
    1219     15997161 :           && call
    1220     15997161 :           && (RTL_LOOPING_CONST_OR_PURE_CALL_P (call)
    1221       118659 :               || ! RTL_CONST_OR_PURE_CALL_P (call)))
    1222              :         always_reached = false;
    1223              :     }
    1224              : }
    1225              : 
    1226              : /* Finds invariants in LOOP with body BODY.  ALWAYS_REACHED is the bitmap of
    1227              :    basic blocks in BODY that are always executed.  ALWAYS_EXECUTED is the
    1228              :    bitmap of basic blocks in BODY that are always executed unless the program
    1229              :    ends due to a function call.  */
    1230              : 
    1231              : static void
    1232       671721 : find_invariants_body (class loop *loop, basic_block *body,
    1233              :                       bitmap always_reached, bitmap always_executed)
    1234              : {
    1235       671721 :   unsigned i;
    1236              : 
    1237      4901640 :   for (i = 0; i < loop->num_nodes; i++)
    1238      4229919 :     find_invariants_bb (loop, body[i], bitmap_bit_p (always_reached, i),
    1239              :                         bitmap_bit_p (always_executed, i));
    1240       671721 : }
    1241              : 
    1242              : /* Finds invariants in LOOP.  */
    1243              : 
    1244              : static void
    1245       671721 : find_invariants (class loop *loop)
    1246              : {
    1247       671721 :   auto_bitmap may_exit;
    1248       671721 :   auto_bitmap always_reached;
    1249       671721 :   auto_bitmap has_exit;
    1250       671721 :   auto_bitmap always_executed;
    1251       671721 :   basic_block *body = get_loop_body_in_dom_order (loop);
    1252              : 
    1253       671721 :   find_exits (loop, body, may_exit, has_exit);
    1254       671721 :   compute_always_reached (loop, body, may_exit, always_reached);
    1255       671721 :   compute_always_reached (loop, body, has_exit, always_executed);
    1256              : 
    1257       671721 :   find_defs (loop);
    1258       671721 :   find_invariants_body (loop, body, always_reached, always_executed);
    1259       671721 :   merge_identical_invariants ();
    1260              : 
    1261       671721 :   free (body);
    1262       671721 : }
    1263              : 
    1264              : /* Frees a list of uses USE.  */
    1265              : 
    1266              : static void
    1267       621442 : free_use_list (struct use *use)
    1268              : {
    1269       621442 :   struct use *next;
    1270              : 
    1271      1285518 :   for (; use; use = next)
    1272              :     {
    1273       664076 :       next = use->next;
    1274       664076 :       free (use);
    1275              :     }
    1276            0 : }
    1277              : 
    1278              : /* Return pressure class and number of hard registers (through *NREGS)
    1279              :    for destination of INSN. */
    1280              : static enum reg_class
    1281           15 : get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
    1282              : {
    1283           15 :   rtx reg;
    1284           15 :   enum reg_class pressure_class;
    1285           15 :   rtx set = single_set (insn);
    1286              : 
    1287              :   /* Considered invariant insns have only one set.  */
    1288           15 :   gcc_assert (set != NULL_RTX);
    1289           15 :   reg = SET_DEST (set);
    1290           15 :   if (GET_CODE (reg) == SUBREG)
    1291            0 :     reg = SUBREG_REG (reg);
    1292           15 :   if (MEM_P (reg))
    1293              :     {
    1294            0 :       *nregs = 0;
    1295            0 :       pressure_class = NO_REGS;
    1296              :     }
    1297              :   else
    1298              :     {
    1299           15 :       if (! REG_P (reg))
    1300              :         reg = NULL_RTX;
    1301           15 :       if (reg == NULL_RTX)
    1302              :         pressure_class = GENERAL_REGS;
    1303              :       else
    1304              :         {
    1305           15 :           pressure_class = reg_allocno_class (REGNO (reg));
    1306           15 :           pressure_class = ira_pressure_class_translate[pressure_class];
    1307              :         }
    1308           15 :       *nregs
    1309           15 :         = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
    1310              :     }
    1311           15 :   return pressure_class;
    1312              : }
    1313              : 
    1314              : /* Calculates cost and number of registers needed for moving invariant INV
    1315              :    out of the loop and stores them to *COST and *REGS_NEEDED.  *CL will be
    1316              :    the REG_CLASS of INV.  Return
    1317              :      -1: if INV is invalid.
    1318              :       0: if INV and its depends_on have same reg_class
    1319              :       1: if INV and its depends_on have different reg_classes.  */
    1320              : 
    1321              : static int
    1322      2590034 : get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed,
    1323              :               enum reg_class *cl)
    1324              : {
    1325      2590034 :   int i, acomp_cost;
    1326      2590034 :   unsigned aregs_needed[N_REG_CLASSES];
    1327      2590034 :   unsigned depno;
    1328      2590034 :   struct invariant *dep;
    1329      2590034 :   bitmap_iterator bi;
    1330      2590034 :   int ret = 1;
    1331              : 
    1332              :   /* Find the representative of the class of the equivalent invariants.  */
    1333      2590034 :   inv = invariants[inv->eqto];
    1334              : 
    1335      2590034 :   *comp_cost = 0;
    1336      2590034 :   if (! flag_ira_loop_pressure)
    1337      2590019 :     regs_needed[0] = 0;
    1338              :   else
    1339              :     {
    1340           75 :       for (i = 0; i < ira_pressure_classes_num; i++)
    1341           60 :         regs_needed[ira_pressure_classes[i]] = 0;
    1342              :     }
    1343              : 
    1344      2590034 :   if (inv->move
    1345      2587827 :       || inv->stamp == actual_stamp)
    1346              :     return -1;
    1347      2586537 :   inv->stamp = actual_stamp;
    1348              : 
    1349      2586537 :   if (! flag_ira_loop_pressure)
    1350      2586522 :     regs_needed[0]++;
    1351              :   else
    1352              :     {
    1353           15 :       int nregs;
    1354           15 :       enum reg_class pressure_class;
    1355              : 
    1356           15 :       pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
    1357           15 :       regs_needed[pressure_class] += nregs;
    1358           15 :       *cl = pressure_class;
    1359           15 :       ret = 0;
    1360              :     }
    1361              : 
    1362      2586537 :   if (!inv->cheap_address
    1363      1030973 :       || inv->def->n_uses == 0
    1364       818851 :       || inv->def->n_addr_uses < inv->def->n_uses
    1365              :       /* Count cost if the inv can't be propagated into address uses.  */
    1366        66381 :       || !inv->def->can_prop_to_addr_uses)
    1367      2528551 :     (*comp_cost) += inv->cost * inv->eqno;
    1368              : 
    1369              : #ifdef STACK_REGS
    1370      2586537 :   {
    1371              :     /* Hoisting constant pool constants into stack regs may cost more than
    1372              :        just single register.  On x87, the balance is affected both by the
    1373              :        small number of FP registers, and by its register stack organization,
    1374              :        that forces us to add compensation code in and around the loop to
    1375              :        shuffle the operands to the top of stack before use, and pop them
    1376              :        from the stack after the loop finishes.
    1377              : 
    1378              :        To model this effect, we increase the number of registers needed for
    1379              :        stack registers by two: one register push, and one register pop.
    1380              :        This usually has the effect that FP constant loads from the constant
    1381              :        pool are not moved out of the loop.
    1382              : 
    1383              :        Note that this also means that dependent invariants cannot be moved.
    1384              :        However, the primary purpose of this pass is to move loop invariant
    1385              :        address arithmetic out of loops, and address arithmetic that depends
    1386              :        on floating point constants is unlikely to ever occur.  */
    1387      2586537 :     rtx set = single_set (inv->insn);
    1388      2586537 :     if (set
    1389      2586537 :         && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
    1390      2598425 :         && constant_pool_constant_p (SET_SRC (set)))
    1391              :       {
    1392         7617 :         if (flag_ira_loop_pressure)
    1393            0 :           regs_needed[ira_stack_reg_pressure_class] += 2;
    1394              :         else
    1395         7617 :           regs_needed[0] += 2;
    1396              :       }
    1397              :   }
    1398              : #endif
    1399              : 
    1400      3151814 :   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
    1401              :     {
    1402       565277 :       bool check_p;
    1403       565277 :       enum reg_class dep_cl = ALL_REGS;
    1404       565277 :       int dep_ret;
    1405              : 
    1406       565277 :       dep = invariants[depno];
    1407              : 
    1408              :       /* If DEP is moved out of the loop, it is not a depends_on any more.  */
    1409       565277 :       if (dep->move)
    1410        83461 :         continue;
    1411              : 
    1412       481816 :       dep_ret = get_inv_cost (dep, &acomp_cost, aregs_needed, &dep_cl);
    1413              : 
    1414       481816 :       if (! flag_ira_loop_pressure)
    1415       481816 :         check_p = aregs_needed[0] != 0;
    1416              :       else
    1417              :         {
    1418            0 :           for (i = 0; i < ira_pressure_classes_num; i++)
    1419            0 :             if (aregs_needed[ira_pressure_classes[i]] != 0)
    1420              :               break;
    1421            0 :           check_p = i < ira_pressure_classes_num;
    1422              : 
    1423            0 :           if ((dep_ret == 1) || ((dep_ret == 0) && (*cl != dep_cl)))
    1424              :             {
    1425            0 :               *cl = ALL_REGS;
    1426            0 :               ret = 1;
    1427              :             }
    1428              :         }
    1429       481816 :       if (check_p
    1430              :           /* We need to check always_executed, since if the original value of
    1431              :              the invariant may be preserved, we may need to keep it in a
    1432              :              separate register.  TODO check whether the register has an
    1433              :              use outside of the loop.  */
    1434       478319 :           && dep->always_executed
    1435       158154 :           && !dep->def->uses->next)
    1436              :         {
    1437              :           /* If this is a single use, after moving the dependency we will not
    1438              :              need a new register.  */
    1439        95647 :           if (! flag_ira_loop_pressure)
    1440        95647 :             aregs_needed[0]--;
    1441              :           else
    1442              :             {
    1443            0 :               int nregs;
    1444            0 :               enum reg_class pressure_class;
    1445              : 
    1446            0 :               pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
    1447            0 :               aregs_needed[pressure_class] -= nregs;
    1448              :             }
    1449              :         }
    1450              : 
    1451       481816 :       if (! flag_ira_loop_pressure)
    1452       481816 :         regs_needed[0] += aregs_needed[0];
    1453              :       else
    1454              :         {
    1455            0 :           for (i = 0; i < ira_pressure_classes_num; i++)
    1456            0 :             regs_needed[ira_pressure_classes[i]]
    1457            0 :               += aregs_needed[ira_pressure_classes[i]];
    1458              :         }
    1459       481816 :       (*comp_cost) += acomp_cost;
    1460              :     }
    1461              :   return ret;
    1462              : }
    1463              : 
    1464              : /* Calculates gain for eliminating invariant INV.  REGS_USED is the number
    1465              :    of registers used in the loop, NEW_REGS is the number of new variables
    1466              :    already added due to the invariant motion.  The number of registers needed
    1467              :    for it is stored in *REGS_NEEDED.  SPEED and CALL_P are flags passed
    1468              :    through to estimate_reg_pressure_cost. */
    1469              : 
    1470              : static int
    1471      2108218 : gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
    1472              :                     unsigned *new_regs, unsigned regs_used,
    1473              :                     bool speed, bool call_p)
    1474              : {
    1475      2108218 :   int comp_cost, size_cost;
    1476              :   /* Workaround -Wmaybe-uninitialized false positive during
    1477              :      profiledbootstrap by initializing it.  */
    1478      2108218 :   enum reg_class cl = NO_REGS;
    1479      2108218 :   int ret;
    1480              : 
    1481      2108218 :   actual_stamp++;
    1482              : 
    1483      2108218 :   ret = get_inv_cost (inv, &comp_cost, regs_needed, &cl);
    1484              : 
    1485      2108218 :   if (! flag_ira_loop_pressure)
    1486              :     {
    1487      2108203 :       size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
    1488              :                                                regs_used, speed, call_p)
    1489      2108203 :                    - estimate_reg_pressure_cost (new_regs[0],
    1490              :                                                  regs_used, speed, call_p));
    1491              :     }
    1492           15 :   else if (ret < 0)
    1493              :     return -1;
    1494           15 :   else if ((ret == 0) && (cl == NO_REGS))
    1495              :     /* Hoist it anyway since it does not impact register pressure.  */
    1496              :     return 1;
    1497              :   else
    1498              :     {
    1499              :       int i;
    1500              :       enum reg_class pressure_class;
    1501              : 
    1502           19 :       for (i = 0; i < ira_pressure_classes_num; i++)
    1503              :         {
    1504           18 :           pressure_class = ira_pressure_classes[i];
    1505              : 
    1506           18 :           if (!reg_classes_intersect_p (pressure_class, cl))
    1507            3 :             continue;
    1508              : 
    1509           15 :           if ((int) new_regs[pressure_class]
    1510           15 :               + (int) regs_needed[pressure_class]
    1511           15 :               + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
    1512           15 :               + param_ira_loop_reserved_regs
    1513           15 :               > ira_class_hard_regs_num[pressure_class])
    1514              :             break;
    1515              :         }
    1516           15 :       if (i < ira_pressure_classes_num)
    1517              :         /* There will be register pressure excess and we want not to
    1518              :            make this loop invariant motion.  All loop invariants with
    1519              :            non-positive gains will be rejected in function
    1520              :            find_invariants_to_move.  Therefore we return the negative
    1521              :            number here.
    1522              : 
    1523              :            One could think that this rejects also expensive loop
    1524              :            invariant motions and this will hurt code performance.
    1525              :            However numerous experiments with different heuristics
    1526              :            taking invariant cost into account did not confirm this
    1527              :            assumption.  There are possible explanations for this
    1528              :            result:
    1529              :            o probably all expensive invariants were already moved out
    1530              :              of the loop by PRE and gimple invariant motion pass.
    1531              :            o expensive invariant execution will be hidden by insn
    1532              :              scheduling or OOO processor hardware because usually such
    1533              :              invariants have a lot of freedom to be executed
    1534              :              out-of-order.
    1535              :            Another reason for ignoring invariant cost vs spilling cost
    1536              :            heuristics is also in difficulties to evaluate accurately
    1537              :            spill cost at this stage.  */
    1538              :         return -1;
    1539              :       else
    1540              :         size_cost = 0;
    1541              :     }
    1542              : 
    1543      2108204 :   return comp_cost - size_cost;
    1544              : }
    1545              : 
    1546              : /* Finds invariant with best gain for moving.  Returns the gain, stores
    1547              :    the invariant in *BEST and number of registers needed for it to
    1548              :    *REGS_NEEDED.  REGS_USED is the number of registers used in the loop.
    1549              :    NEW_REGS is the number of new variables already added due to invariant
    1550              :    motion.  */
    1551              : 
    1552              : static int
    1553       506477 : best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
    1554              :                          unsigned *new_regs, unsigned regs_used,
    1555              :                          bool speed, bool call_p)
    1556              : {
    1557       506477 :   struct invariant *inv;
    1558       506477 :   int i, gain = 0, again;
    1559       506477 :   unsigned aregs_needed[N_REG_CLASSES], invno;
    1560              : 
    1561      4362080 :   FOR_EACH_VEC_ELT (invariants, invno, inv)
    1562              :     {
    1563      3855603 :       if (inv->move)
    1564       625074 :         continue;
    1565              : 
    1566              :       /* Only consider the "representatives" of equivalent invariants.  */
    1567      3230529 :       if (inv->eqto != inv->invno)
    1568      1122311 :         continue;
    1569              : 
    1570      2108218 :       again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
    1571              :                                   speed, call_p);
    1572      2108218 :       if (again > gain)
    1573              :         {
    1574       352660 :           gain = again;
    1575       352660 :           *best = inv;
    1576       352660 :           if (! flag_ira_loop_pressure)
    1577       352659 :             regs_needed[0] = aregs_needed[0];
    1578              :           else
    1579              :             {
    1580            5 :               for (i = 0; i < ira_pressure_classes_num; i++)
    1581            4 :                 regs_needed[ira_pressure_classes[i]]
    1582            4 :                   = aregs_needed[ira_pressure_classes[i]];
    1583              :             }
    1584              :         }
    1585              :     }
    1586              : 
    1587       506477 :   return gain;
    1588              : }
    1589              : 
    1590              : /* Marks invariant INVNO and all its dependencies for moving.  */
    1591              : 
    1592              : static void
    1593       336177 : set_move_mark (unsigned invno, int gain)
    1594              : {
    1595       336177 :   struct invariant *inv = invariants[invno];
    1596       336177 :   bitmap_iterator bi;
    1597              : 
    1598              :   /* Find the representative of the class of the equivalent invariants.  */
    1599       336177 :   inv = invariants[inv->eqto];
    1600              : 
    1601       336177 :   if (inv->move)
    1602         2226 :     return;
    1603       333951 :   inv->move = true;
    1604              : 
    1605       333951 :   if (dump_file)
    1606              :     {
    1607            3 :       if (gain >= 0)
    1608            3 :         fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
    1609              :                  invno, gain);
    1610              :       else
    1611            0 :         fprintf (dump_file, "Decided to move dependent invariant %d\n",
    1612              :                  invno);
    1613       333951 :     };
    1614              : 
    1615       410676 :   EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
    1616              :     {
    1617        76725 :       set_move_mark (invno, -1);
    1618              :     }
    1619              : }
    1620              : 
    1621              : /* Determines which invariants to move.  */
    1622              : 
    1623              : static void
    1624       671721 : find_invariants_to_move (bool speed, bool call_p)
    1625              : {
    1626       671721 :   int gain;
    1627       671721 :   unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
    1628       671721 :   struct invariant *inv = NULL;
    1629              : 
    1630       671721 :   if (!invariants.length ())
    1631       424696 :     return;
    1632              : 
    1633       247025 :   if (flag_ira_loop_pressure)
    1634              :     /* REGS_USED is actually never used when the flag is on.  */
    1635              :     regs_used = 0;
    1636              :   else
    1637              :     /* We do not really do a good job in estimating number of
    1638              :        registers used; we put some initial bound here to stand for
    1639              :        induction variables etc.  that we do not detect.  */
    1640              :     {
    1641       247024 :       unsigned int n_regs = DF_REG_SIZE (df);
    1642              : 
    1643       247024 :       regs_used = 2;
    1644              : 
    1645    134517053 :       for (i = 0; i < n_regs; i++)
    1646              :         {
    1647    134270029 :           if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
    1648              :             {
    1649              :               /* This is a value that is used but not changed inside loop.  */
    1650            0 :               regs_used++;
    1651              :             }
    1652              :         }
    1653              :     }
    1654              : 
    1655       247025 :   if (! flag_ira_loop_pressure)
    1656       247024 :     new_regs[0] = regs_needed[0] = 0;
    1657              :   else
    1658              :     {
    1659            5 :       for (i = 0; (int) i < ira_pressure_classes_num; i++)
    1660            4 :         new_regs[ira_pressure_classes[i]] = 0;
    1661              :     }
    1662      1012954 :   while ((gain = best_gain_for_invariant (&inv, regs_needed,
    1663              :                                           new_regs, regs_used,
    1664       506477 :                                           speed, call_p)) > 0)
    1665              :     {
    1666       259452 :       set_move_mark (inv->invno, gain);
    1667       259452 :       if (! flag_ira_loop_pressure)
    1668       259451 :         new_regs[0] += regs_needed[0];
    1669              :       else
    1670              :         {
    1671            5 :           for (i = 0; (int) i < ira_pressure_classes_num; i++)
    1672            4 :             new_regs[ira_pressure_classes[i]]
    1673            4 :               += regs_needed[ira_pressure_classes[i]];
    1674              :         }
    1675              :     }
    1676              : }
    1677              : 
    1678              : /* Replace the uses, reached by the definition of invariant INV, by REG.
    1679              : 
    1680              :    IN_GROUP is nonzero if this is part of a group of changes that must be
    1681              :    performed as a group.  In that case, the changes will be stored.  The
    1682              :    function `apply_change_group' will validate and apply the changes.  */
    1683              : 
    1684              : static int
    1685       248599 : replace_uses (struct invariant *inv, rtx reg, bool in_group)
    1686              : {
    1687              :   /* Replace the uses we know to be dominated.  It saves work for copy
    1688              :      propagation, and also it is necessary so that dependent invariants
    1689              :      are computed right.  */
    1690       248599 :   if (inv->def)
    1691              :     {
    1692       242458 :       struct use *use;
    1693       457746 :       for (use = inv->def->uses; use; use = use->next)
    1694       215288 :         validate_change (use->insn, use->pos, reg, true);
    1695              : 
    1696              :       /* If we aren't part of a larger group, apply the changes now.  */
    1697       242458 :       if (!in_group)
    1698        48141 :         return apply_change_group ();
    1699              :     }
    1700              : 
    1701              :   return 1;
    1702              : }
    1703              : 
    1704              : /* Whether invariant INV setting REG can be moved out of LOOP, at the end of
    1705              :    the block preceding its header.  */
    1706              : 
    1707              : static bool
    1708       333951 : can_move_invariant_reg (class loop *loop, struct invariant *inv, rtx reg)
    1709              : {
    1710       333951 :   df_ref def, use;
    1711       333951 :   unsigned int dest_regno, defs_in_loop_count = 0;
    1712       333951 :   rtx_insn *insn = inv->insn;
    1713       333951 :   basic_block bb = BLOCK_FOR_INSN (inv->insn);
    1714       333951 :   auto_vec <rtx_insn *, 16> debug_insns_to_reset;
    1715              : 
    1716              :   /* We ignore hard register and memory access for cost and complexity reasons.
    1717              :      Hard register are few at this stage and expensive to consider as they
    1718              :      require building a separate data flow.  Memory access would require using
    1719              :      df_simulate_* and can_move_insns_across functions and is more complex.  */
    1720       333951 :   if (!REG_P (reg) || HARD_REGISTER_P (reg))
    1721              :     return false;
    1722              : 
    1723              :   /* Check whether the set is always executed.  We could omit this condition if
    1724              :      we know that the register is unused outside of the loop, but it does not
    1725              :      seem worth finding out.  */
    1726       333017 :   if (!inv->always_executed)
    1727              :     return false;
    1728              : 
    1729              :   /* Check that all uses that would be dominated by def are already dominated
    1730              :      by it.  */
    1731       146964 :   dest_regno = REGNO (reg);
    1732       375454 :   for (use = DF_REG_USE_CHAIN (dest_regno); use; use = DF_REF_NEXT_REG (use))
    1733              :     {
    1734       230275 :       rtx_insn *use_insn;
    1735       230275 :       basic_block use_bb;
    1736              : 
    1737       230275 :       use_insn = DF_REF_INSN (use);
    1738       230275 :       use_bb = BLOCK_FOR_INSN (use_insn);
    1739              : 
    1740              :       /* Ignore instruction considered for moving.  */
    1741       230275 :       if (use_insn == insn)
    1742         9646 :         continue;
    1743              : 
    1744              :       /* Don't consider uses outside loop.  */
    1745       230275 :       if (!flow_bb_inside_loop_p (loop, use_bb))
    1746         9646 :         continue;
    1747              : 
    1748              :       /* Don't move if a use is not dominated by def in insn.  */
    1749       148088 :       if ((use_bb == bb && DF_INSN_LUID (insn) >= DF_INSN_LUID (use_insn))
    1750       367688 :           || !dominated_by_p (CDI_DOMINATORS, use_bb, bb))
    1751              :         {
    1752         1788 :           if (!DEBUG_INSN_P (use_insn))
    1753         1785 :             return false;
    1754            3 :           debug_insns_to_reset.safe_push (use_insn);
    1755              :         }
    1756              :     }
    1757              : 
    1758              :   /* Check for other defs.  Any other def in the loop might reach a use
    1759              :      currently reached by the def in insn.  */
    1760       291129 :   for (def = DF_REG_DEF_CHAIN (dest_regno); def; def = DF_REF_NEXT_REG (def))
    1761              :     {
    1762       152429 :       basic_block def_bb = DF_REF_BB (def);
    1763              : 
    1764              :       /* Defs in exit block cannot reach a use they weren't already.  */
    1765       152429 :       if (single_succ_p (def_bb))
    1766              :         {
    1767        45662 :           basic_block def_bb_succ;
    1768              : 
    1769        45662 :           def_bb_succ = single_succ (def_bb);
    1770        45662 :           if (!flow_bb_inside_loop_p (loop, def_bb_succ))
    1771          771 :             continue;
    1772              :         }
    1773              : 
    1774       151658 :       if (++defs_in_loop_count > 1)
    1775              :         return false;
    1776              :     }
    1777              : 
    1778              :   /* Reset debug uses if a use is not dominated by def in insn.  */
    1779       416102 :   for (auto use_insn : debug_insns_to_reset)
    1780              :     {
    1781            2 :       INSN_VAR_LOCATION_LOC (use_insn) = gen_rtx_UNKNOWN_VAR_LOC ();
    1782            2 :       df_insn_rescan (use_insn);
    1783              :     }
    1784              : 
    1785              :   return true;
    1786       333951 : }
    1787              : 
    1788              : /* Move invariant INVNO out of the LOOP.  Returns true if this succeeds, false
    1789              :    otherwise.  */
    1790              : 
    1791              : static bool
    1792      1502131 : move_invariant_reg (class loop *loop, unsigned invno)
    1793              : {
    1794      1502131 :   struct invariant *inv = invariants[invno];
    1795      1502131 :   struct invariant *repr = invariants[inv->eqto];
    1796      1502131 :   unsigned i;
    1797      1502131 :   basic_block preheader = loop_preheader_edge (loop)->src;
    1798      1502131 :   rtx reg, set, dest, note;
    1799      1502131 :   bitmap_iterator bi;
    1800      1502131 :   int regno = -1;
    1801              : 
    1802      1502131 :   if (inv->reg)
    1803              :     return true;
    1804      1372058 :   if (!repr->move)
    1805              :     return false;
    1806              : 
    1807              :   /* If this is a representative of the class of equivalent invariants,
    1808              :      really move the invariant.  Otherwise just replace its use with
    1809              :      the register used for the representative.  */
    1810       387299 :   if (inv == repr)
    1811              :     {
    1812       333951 :       if (inv->depends_on)
    1813              :         {
    1814       410676 :           EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
    1815              :             {
    1816        76725 :               if (!move_invariant_reg (loop, i))
    1817            0 :                 goto fail;
    1818              :             }
    1819              :         }
    1820              : 
    1821              :       /* If possible, just move the set out of the loop.  Otherwise, we
    1822              :          need to create a temporary register.  */
    1823       333951 :       set = single_set (inv->insn);
    1824       333951 :       reg = dest = SET_DEST (set);
    1825       333951 :       if (GET_CODE (reg) == SUBREG)
    1826           38 :         reg = SUBREG_REG (reg);
    1827       333951 :       if (REG_P (reg))
    1828       333705 :         regno = REGNO (reg);
    1829              : 
    1830       333951 :       if (!can_move_invariant_reg (loop, inv, dest))
    1831              :         {
    1832       195251 :           reg = gen_reg_rtx_and_attrs (dest);
    1833              : 
    1834              :           /* Try replacing the destination by a new pseudoregister.  */
    1835       195251 :           validate_change (inv->insn, &SET_DEST (set), reg, true);
    1836              : 
    1837              :           /* As well as all the dominated uses.  */
    1838       195251 :           replace_uses (inv, reg, true);
    1839              : 
    1840              :           /* And validate all the changes.  */
    1841       195251 :           if (!apply_change_group ())
    1842           41 :             goto fail;
    1843              : 
    1844       195210 :           emit_insn_after (gen_move_insn (dest, reg), inv->insn);
    1845              :         }
    1846       138700 :       else if (dump_file)
    1847            1 :         fprintf (dump_file, "Invariant %d moved without introducing a new "
    1848              :                             "temporary register\n", invno);
    1849       333910 :       if (JUMP_P (BB_END (preheader)))
    1850            6 :         preheader = split_edge (loop_preheader_edge (loop));
    1851       333910 :       reorder_insns (inv->insn, inv->insn, BB_END (preheader));
    1852       333910 :       df_recompute_luids (preheader);
    1853              : 
    1854              :       /* If there is a REG_EQUAL note on the insn we just moved, and the
    1855              :          insn is in a basic block that is not always executed or the note
    1856              :          contains something for which we don't know the invariant status,
    1857              :          the note may no longer be valid after we move the insn.  Note that
    1858              :          uses in REG_EQUAL notes are taken into account in the computation
    1859              :          of invariants, so it is safe to retain the note even if it contains
    1860              :          register references for which we know the invariant status.  */
    1861       333910 :       if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
    1862       333910 :           && (!inv->always_executed
    1863        35977 :               || !check_maybe_invariant (XEXP (note, 0))))
    1864        26417 :         remove_note (inv->insn, note);
    1865              :     }
    1866              :   else
    1867              :     {
    1868        53348 :       if (!move_invariant_reg (loop, repr->invno))
    1869            0 :         goto fail;
    1870        53348 :       reg = repr->reg;
    1871        53348 :       regno = repr->orig_regno;
    1872        53348 :       if (!replace_uses (inv, reg, false))
    1873            0 :         goto fail;
    1874        53348 :       set = single_set (inv->insn);
    1875        53348 :       emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
    1876        53348 :       delete_insn (inv->insn);
    1877              :     }
    1878              : 
    1879       387258 :   inv->reg = reg;
    1880       387258 :   inv->orig_regno = regno;
    1881              : 
    1882       387258 :   return true;
    1883              : 
    1884           41 : fail:
    1885              :   /* If we failed, clear move flag, so that we do not try to move inv
    1886              :      again.  */
    1887           41 :   if (dump_file)
    1888            0 :     fprintf (dump_file, "Failed to move invariant %d\n", invno);
    1889           41 :   inv->move = false;
    1890           41 :   inv->reg = NULL_RTX;
    1891           41 :   inv->orig_regno = -1;
    1892              : 
    1893           41 :   return false;
    1894              : }
    1895              : 
    1896              : /* Move selected invariant out of the LOOP.  Newly created regs are marked
    1897              :    in TEMPORARY_REGS.  */
    1898              : 
    1899              : static void
    1900       671721 : move_invariants (class loop *loop)
    1901              : {
    1902       671721 :   struct invariant *inv;
    1903       671721 :   unsigned i;
    1904              : 
    1905      2043779 :   FOR_EACH_VEC_ELT (invariants, i, inv)
    1906      1372058 :     move_invariant_reg (loop, i);
    1907       671721 :   if (flag_ira_loop_pressure && resize_reg_info ())
    1908              :     {
    1909            9 :       FOR_EACH_VEC_ELT (invariants, i, inv)
    1910            8 :         if (inv->reg != NULL_RTX)
    1911              :           {
    1912            1 :             if (inv->orig_regno >= 0)
    1913            1 :               setup_reg_classes (REGNO (inv->reg),
    1914              :                                  reg_preferred_class (inv->orig_regno),
    1915              :                                  reg_alternate_class (inv->orig_regno),
    1916              :                                  reg_allocno_class (inv->orig_regno));
    1917              :             else
    1918            0 :               setup_reg_classes (REGNO (inv->reg),
    1919              :                                  GENERAL_REGS, NO_REGS, GENERAL_REGS);
    1920              :           }
    1921              :     }
    1922              :   /* Remove the DF_UD_CHAIN problem added in find_defs before rescanning,
    1923              :      to save a bit of compile time.  */
    1924       671721 :   df_remove_problem (df_chain);
    1925       671721 :   df_process_deferred_rescans ();
    1926       671721 : }
    1927              : 
    1928              : /* Initializes invariant motion data.  */
    1929              : 
    1930              : static void
    1931       671721 : init_inv_motion_data (void)
    1932              : {
    1933       671721 :   actual_stamp = 1;
    1934              : 
    1935       671721 :   invariants.create (100);
    1936       671721 : }
    1937              : 
    1938              : /* Frees the data allocated by invariant motion.  */
    1939              : 
    1940              : static void
    1941       671721 : free_inv_motion_data (void)
    1942              : {
    1943       671721 :   unsigned i;
    1944       671721 :   struct def *def;
    1945       671721 :   struct invariant *inv;
    1946              : 
    1947       671721 :   check_invariant_table_size ();
    1948     85959590 :   for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
    1949              :     {
    1950     84616148 :       inv = invariant_table[i];
    1951     84616148 :       if (inv)
    1952              :         {
    1953       621442 :           def = inv->def;
    1954       621442 :           gcc_assert (def != NULL);
    1955              : 
    1956       621442 :           free_use_list (def->uses);
    1957       621442 :           free (def);
    1958       621442 :           invariant_table[i] = NULL;
    1959              :         }
    1960              :     }
    1961              : 
    1962      2043779 :   FOR_EACH_VEC_ELT (invariants, i, inv)
    1963              :     {
    1964      1372058 :       BITMAP_FREE (inv->depends_on);
    1965      1372058 :       free (inv);
    1966              :     }
    1967       671721 :   invariants.release ();
    1968       671721 : }
    1969              : 
    1970              : /* Move the invariants out of the LOOP.  */
    1971              : 
    1972              : static void
    1973       671721 : move_single_loop_invariants (class loop *loop)
    1974              : {
    1975       671721 :   init_inv_motion_data ();
    1976              : 
    1977       671721 :   find_invariants (loop);
    1978       671721 :   find_invariants_to_move (optimize_loop_for_speed_p (loop),
    1979       671721 :                            LOOP_DATA (loop)->has_call);
    1980       671721 :   move_invariants (loop);
    1981              : 
    1982       671721 :   free_inv_motion_data ();
    1983       671721 : }
    1984              : 
    1985              : /* Releases the auxiliary data for LOOP.  */
    1986              : 
    1987              : static void
    1988       671721 : free_loop_data (class loop *loop)
    1989              : {
    1990       671721 :   class loop_data *data = LOOP_DATA (loop);
    1991       671721 :   if (!data)
    1992              :     return;
    1993              : 
    1994       671721 :   bitmap_clear (&LOOP_DATA (loop)->regs_ref);
    1995       671721 :   bitmap_clear (&LOOP_DATA (loop)->regs_live);
    1996       671721 :   free (data);
    1997       671721 :   loop->aux = NULL;
    1998              : }
    1999              : 
    2000              : 
    2001              : 
    2002              : /* Registers currently living.  */
    2003              : static bitmap_head curr_regs_live;
    2004              : 
    2005              : /* Current reg pressure for each pressure class.  */
    2006              : static int curr_reg_pressure[N_REG_CLASSES];
    2007              : 
    2008              : /* Record all regs that are set in any one insn.  Communication from
    2009              :    mark_reg_{store,clobber} and global_conflicts.  Asm can refer to
    2010              :    all hard-registers.  */
    2011              : static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
    2012              :                      ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
    2013              : /* Number of regs stored in the previous array.  */
    2014              : static int n_regs_set;
    2015              : 
    2016              : /* Return pressure class and number of needed hard registers (through
    2017              :    *NREGS) of register REGNO.  */
    2018              : static enum reg_class
    2019          137 : get_regno_pressure_class (int regno, int *nregs)
    2020              : {
    2021          137 :   if (regno >= FIRST_PSEUDO_REGISTER)
    2022              :     {
    2023           82 :       enum reg_class pressure_class;
    2024              : 
    2025           82 :       pressure_class = reg_allocno_class (regno);
    2026           82 :       pressure_class = ira_pressure_class_translate[pressure_class];
    2027           82 :       *nregs
    2028           82 :         = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
    2029           82 :       return pressure_class;
    2030              :     }
    2031           55 :   else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
    2032           55 :            && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
    2033              :     {
    2034           12 :       *nregs = 1;
    2035           12 :       return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
    2036              :     }
    2037              :   else
    2038              :     {
    2039           43 :       *nregs = 0;
    2040           43 :       return NO_REGS;
    2041              :     }
    2042              : }
    2043              : 
    2044              : /* Increase (if INCR_P) or decrease current register pressure for
    2045              :    register REGNO.  */
    2046              : static void
    2047          134 : change_pressure (int regno, bool incr_p)
    2048              : {
    2049          134 :   int nregs;
    2050          134 :   enum reg_class pressure_class;
    2051              : 
    2052          134 :   pressure_class = get_regno_pressure_class (regno, &nregs);
    2053          134 :   if (! incr_p)
    2054           32 :     curr_reg_pressure[pressure_class] -= nregs;
    2055              :   else
    2056              :     {
    2057          102 :       curr_reg_pressure[pressure_class] += nregs;
    2058          102 :       if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
    2059              :           < curr_reg_pressure[pressure_class])
    2060           20 :         LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
    2061           20 :           = curr_reg_pressure[pressure_class];
    2062              :     }
    2063          134 : }
    2064              : 
    2065              : /* Mark REGNO birth.  */
    2066              : static void
    2067           48 : mark_regno_live (int regno)
    2068              : {
    2069           48 :   class loop *loop;
    2070              : 
    2071           48 :   for (loop = curr_loop;
    2072           96 :        loop != current_loops->tree_root;
    2073           48 :        loop = loop_outer (loop))
    2074           48 :     bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
    2075           48 :   if (!bitmap_set_bit (&curr_regs_live, regno))
    2076              :     return;
    2077           37 :   change_pressure (regno, true);
    2078              : }
    2079              : 
    2080              : /* Mark REGNO death.  */
    2081              : static void
    2082           42 : mark_regno_death (int regno)
    2083              : {
    2084           42 :   if (! bitmap_clear_bit (&curr_regs_live, regno))
    2085              :     return;
    2086           32 :   change_pressure (regno, false);
    2087              : }
    2088              : 
    2089              : /* Mark setting register REG.  */
    2090              : static void
    2091           53 : mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
    2092              :                 void *data ATTRIBUTE_UNUSED)
    2093              : {
    2094           53 :   if (GET_CODE (reg) == SUBREG)
    2095            0 :     reg = SUBREG_REG (reg);
    2096              : 
    2097           53 :   if (! REG_P (reg))
    2098              :     return;
    2099              : 
    2100           48 :   regs_set[n_regs_set++] = reg;
    2101              : 
    2102           48 :   unsigned int end_regno = END_REGNO (reg);
    2103           96 :   for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
    2104           48 :     mark_regno_live (regno);
    2105              : }
    2106              : 
    2107              : /* Mark clobbering register REG.  */
    2108              : static void
    2109           43 : mark_reg_clobber (rtx reg, const_rtx setter, void *data)
    2110              : {
    2111           43 :   if (GET_CODE (setter) == CLOBBER)
    2112           10 :     mark_reg_store (reg, setter, data);
    2113           43 : }
    2114              : 
    2115              : /* Mark register REG death.  */
    2116              : static void
    2117           42 : mark_reg_death (rtx reg)
    2118              : {
    2119           42 :   unsigned int end_regno = END_REGNO (reg);
    2120           84 :   for (unsigned int regno = REGNO (reg); regno < end_regno; ++regno)
    2121           42 :     mark_regno_death (regno);
    2122           42 : }
    2123              : 
    2124              : /* Mark occurrence of registers in X for the current loop.  */
    2125              : static void
    2126          197 : mark_ref_regs (rtx x)
    2127              : {
    2128          197 :   RTX_CODE code;
    2129          197 :   int i;
    2130          197 :   const char *fmt;
    2131              : 
    2132          197 :   if (!x)
    2133              :     return;
    2134              : 
    2135          197 :   code = GET_CODE (x);
    2136          197 :   if (code == REG)
    2137              :     {
    2138           82 :       class loop *loop;
    2139              : 
    2140           82 :       for (loop = curr_loop;
    2141          164 :            loop != current_loops->tree_root;
    2142           82 :            loop = loop_outer (loop))
    2143           82 :         bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
    2144              :       return;
    2145              :     }
    2146              : 
    2147          115 :   fmt = GET_RTX_FORMAT (code);
    2148          305 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    2149          190 :     if (fmt[i] == 'e')
    2150          143 :       mark_ref_regs (XEXP (x, i));
    2151           47 :     else if (fmt[i] == 'E')
    2152              :       {
    2153              :         int j;
    2154              : 
    2155           30 :         for (j = 0; j < XVECLEN (x, i); j++)
    2156           20 :           mark_ref_regs (XVECEXP (x, i, j));
    2157              :       }
    2158              : }
    2159              : 
    2160              : /* Calculate register pressure in the loops.  */
    2161              : static void
    2162            1 : calculate_loop_reg_pressure (void)
    2163              : {
    2164            1 :   int i;
    2165            1 :   unsigned int j;
    2166            1 :   bitmap_iterator bi;
    2167            1 :   basic_block bb;
    2168            1 :   rtx_insn *insn;
    2169            1 :   rtx link;
    2170            1 :   class loop *parent;
    2171              : 
    2172            4 :   for (auto loop : loops_list (cfun, 0))
    2173            1 :     if (loop->aux == NULL)
    2174              :       {
    2175            1 :         loop->aux = xcalloc (1, sizeof (class loop_data));
    2176            1 :         bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
    2177            1 :         bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
    2178            1 :       }
    2179            1 :   ira_setup_eliminable_regset ();
    2180            1 :   bitmap_initialize (&curr_regs_live, &reg_obstack);
    2181            9 :   FOR_EACH_BB_FN (bb, cfun)
    2182              :     {
    2183            8 :       curr_loop = bb->loop_father;
    2184            8 :       if (curr_loop == current_loops->tree_root)
    2185            4 :         continue;
    2186              : 
    2187            4 :       for (class loop *loop = curr_loop;
    2188            8 :            loop != current_loops->tree_root;
    2189            4 :            loop = loop_outer (loop))
    2190            8 :         bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
    2191              : 
    2192            4 :       bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
    2193           24 :       for (i = 0; i < ira_pressure_classes_num; i++)
    2194           16 :         curr_reg_pressure[ira_pressure_classes[i]] = 0;
    2195           69 :       EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
    2196           65 :         change_pressure (j, true);
    2197              : 
    2198           45 :       FOR_BB_INSNS (bb, insn)
    2199              :         {
    2200           41 :           if (! NONDEBUG_INSN_P (insn))
    2201            7 :             continue;
    2202              : 
    2203           34 :           mark_ref_regs (PATTERN (insn));
    2204           34 :           n_regs_set = 0;
    2205           34 :           note_stores (insn, mark_reg_clobber, NULL);
    2206              : 
    2207              :           /* Mark any registers dead after INSN as dead now.  */
    2208              : 
    2209           78 :           for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
    2210           44 :             if (REG_NOTE_KIND (link) == REG_DEAD)
    2211           22 :               mark_reg_death (XEXP (link, 0));
    2212              : 
    2213              :           /* Mark any registers set in INSN as live,
    2214              :              and mark them as conflicting with all other live regs.
    2215              :              Clobbers are processed again, so they conflict with
    2216              :              the registers that are set.  */
    2217              : 
    2218           34 :           note_stores (insn, mark_reg_store, NULL);
    2219              : 
    2220           34 :           if (AUTO_INC_DEC)
    2221              :             for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
    2222              :               if (REG_NOTE_KIND (link) == REG_INC)
    2223              :                 mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
    2224              : 
    2225          116 :           while (n_regs_set-- > 0)
    2226              :             {
    2227           96 :               rtx note = find_regno_note (insn, REG_UNUSED,
    2228           48 :                                           REGNO (regs_set[n_regs_set]));
    2229           48 :               if (! note)
    2230           28 :                 continue;
    2231              : 
    2232           20 :               mark_reg_death (XEXP (note, 0));
    2233              :             }
    2234              :         }
    2235              :     }
    2236            1 :   bitmap_release (&curr_regs_live);
    2237            1 :   if (flag_ira_region == IRA_REGION_MIXED
    2238            1 :       || flag_ira_region == IRA_REGION_ALL)
    2239            4 :     for (auto loop : loops_list (cfun, 0))
    2240              :       {
    2241           41 :         EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
    2242           40 :           if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
    2243              :             {
    2244            3 :               enum reg_class pressure_class;
    2245            3 :               int nregs;
    2246              : 
    2247            3 :               pressure_class = get_regno_pressure_class (j, &nregs);
    2248            3 :               LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
    2249              :             }
    2250            1 :       }
    2251            1 :   if (dump_file == NULL)
    2252            0 :     return;
    2253            4 :   for (auto loop : loops_list (cfun, 0))
    2254              :     {
    2255            1 :       parent = loop_outer (loop);
    2256            2 :       fprintf (dump_file, "\n  Loop %d (parent %d, header bb%d, depth %d)\n",
    2257              :                loop->num, (parent == NULL ? -1 : parent->num),
    2258            1 :                loop->header->index, loop_depth (loop));
    2259            1 :       fprintf (dump_file, "\n    ref. regnos:");
    2260           38 :       EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
    2261           37 :         fprintf (dump_file, " %d", j);
    2262            1 :       fprintf (dump_file, "\n    live regnos:");
    2263           41 :       EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
    2264           40 :         fprintf (dump_file, " %d", j);
    2265            1 :       fprintf (dump_file, "\n    Pressure:");
    2266            6 :       for (i = 0; (int) i < ira_pressure_classes_num; i++)
    2267              :         {
    2268            4 :           enum reg_class pressure_class;
    2269              : 
    2270            4 :           pressure_class = ira_pressure_classes[i];
    2271            4 :           if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
    2272            2 :             continue;
    2273            2 :           fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
    2274              :                    LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
    2275              :         }
    2276            1 :       fprintf (dump_file, "\n");
    2277            1 :     }
    2278              : }
    2279              : 
    2280              : 
    2281              : 
    2282              : /* Move the invariants out of the loops.  */
    2283              : 
    2284              : void
    2285       251838 : move_loop_invariants (void)
    2286              : {
    2287       251838 :   if (optimize == 1)
    2288        17137 :     df_live_add_problem ();
    2289              :   /* ??? This is a hack.  We should only need to call df_live_set_all_dirty
    2290              :      for optimize == 1, but can_move_invariant_reg relies on DF_INSN_LUID
    2291              :      being up-to-date.  That isn't always true (even after df_analyze)
    2292              :      because df_process_deferred_rescans doesn't necessarily cause
    2293              :      blocks to be rescanned.  */
    2294       251838 :   df_live_set_all_dirty ();
    2295       251838 :   if (flag_ira_loop_pressure)
    2296              :     {
    2297            1 :       df_analyze ();
    2298            1 :       regstat_init_n_sets_and_refs ();
    2299            1 :       ira_set_pseudo_classes (true, dump_file);
    2300            1 :       calculate_loop_reg_pressure ();
    2301            1 :       regstat_free_n_sets_and_refs ();
    2302              :     }
    2303       251838 :   df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
    2304              :   /* Process the loops, innermost first.  */
    2305      1427235 :   for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
    2306              :     {
    2307       671721 :       curr_loop = loop;
    2308              :       /* move_single_loop_invariants for very large loops is time consuming
    2309              :          and might need a lot of memory.  For -O1 only do loop invariant
    2310              :          motion for very small loops.  */
    2311       671721 :       unsigned max_bbs = param_loop_invariant_max_bbs_in_loop;
    2312       671721 :       if (optimize < 2)
    2313        44837 :         max_bbs /= 10;
    2314       671721 :       if (loop->num_nodes <= max_bbs)
    2315       671721 :         move_single_loop_invariants (loop);
    2316       251838 :     }
    2317              : 
    2318      1427235 :   for (auto loop : loops_list (cfun, 0))
    2319       671721 :       free_loop_data (loop);
    2320              : 
    2321       251838 :   if (flag_ira_loop_pressure)
    2322              :     /* There is no sense to keep this info because it was most
    2323              :        probably outdated by subsequent passes.  */
    2324            1 :     free_reg_info ();
    2325       251838 :   free (invariant_table);
    2326       251838 :   invariant_table = NULL;
    2327       251838 :   invariant_table_size = 0;
    2328              : 
    2329       251838 :   if (optimize == 1)
    2330        17137 :     df_remove_problem (df_live);
    2331              : 
    2332       251838 :   checking_verify_flow_info ();
    2333       251838 : }
        

Generated by: LCOV version 2.5.0-beta

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