LCOV - code coverage report
Current view: top level - gcc - loop-invariant.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 955 981 97.3 %
Date: 2020-03-28 11:57:23 Functions: 50 54 92.6 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

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

Generated by: LCOV version 1.0

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