LCOV - code coverage report
Current view: top level - gcc - lra.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1080 1220 88.5 %
Date: 2020-04-04 11:58:09 Functions: 64 72 88.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* LRA (local register allocator) driver and LRA utilities.
       2                 :            :    Copyright (C) 2010-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Vladimir Makarov <vmakarov@redhat.com>.
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify it under
       8                 :            : the terms of the GNU General Public License as published by the Free
       9                 :            : Software Foundation; either version 3, or (at your option) any later
      10                 :            : version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :            : for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.    */
      20                 :            : 
      21                 :            : 
      22                 :            : /* The Local Register Allocator (LRA) is a replacement of former
      23                 :            :    reload pass.  It is focused to simplify code solving the reload
      24                 :            :    pass tasks, to make the code maintenance easier, and to implement new
      25                 :            :    perspective optimizations.
      26                 :            : 
      27                 :            :    The major LRA design solutions are:
      28                 :            :      o division small manageable, separated sub-tasks
      29                 :            :      o reflection of all transformations and decisions in RTL as more
      30                 :            :        as possible
      31                 :            :      o insn constraints as a primary source of the info (minimizing
      32                 :            :        number of target-depended macros/hooks)
      33                 :            : 
      34                 :            :    In brief LRA works by iterative insn process with the final goal is
      35                 :            :    to satisfy all insn and address constraints:
      36                 :            :      o New reload insns (in brief reloads) and reload pseudos might be
      37                 :            :        generated;
      38                 :            :      o Some pseudos might be spilled to assign hard registers to
      39                 :            :        new reload pseudos;
      40                 :            :      o Recalculating spilled pseudo values (rematerialization);
      41                 :            :      o Changing spilled pseudos to stack memory or their equivalences;
      42                 :            :      o Allocation stack memory changes the address displacement and
      43                 :            :        new iteration is needed.
      44                 :            : 
      45                 :            :    Here is block diagram of LRA passes:
      46                 :            : 
      47                 :            :                                 ------------------------
      48                 :            :            ---------------     | Undo inheritance for   |     ---------------
      49                 :            :           | Memory-memory |    | spilled pseudos,       |    | New (and old) |
      50                 :            :           | move coalesce |<---| splits for pseudos got |<-- |   pseudos     |
      51                 :            :            ---------------     | the same hard regs,    |    |  assignment   |
      52                 :            :   Start           |            | and optional reloads   |     ---------------
      53                 :            :     |             |             ------------------------            ^
      54                 :            :     V             |              ----------------                   |
      55                 :            :  -----------      V             | Update virtual |                  |
      56                 :            : |  Remove   |----> ------------>|    register    |                  |
      57                 :            : | scratches |     ^             |  displacements |                  |
      58                 :            :  -----------      |              ----------------                   |
      59                 :            :                   |                      |                          |
      60                 :            :                   |                      V         New              |
      61                 :            :                   |                 ------------  pseudos   -------------------
      62                 :            :                   |                |Constraints:| or insns | Inheritance/split |
      63                 :            :                   |                |    RTL     |--------->|  transformations  |
      64                 :            :                   |                | transfor-  |          |    in EBB scope   |
      65                 :            :                   | substi-        |  mations   |           -------------------
      66                 :            :                   | tutions         ------------
      67                 :            :                   |                     | No change
      68                 :            :           ----------------              V
      69                 :            :          | Spilled pseudo |      -------------------
      70                 :            :          |    to memory   |<----| Rematerialization |
      71                 :            :          |  substitution  |      -------------------
      72                 :            :           ----------------        
      73                 :            :                   | No susbtitions
      74                 :            :                   V                
      75                 :            :       -------------------------
      76                 :            :      | Hard regs substitution, |
      77                 :            :      |  devirtalization, and   |------> Finish
      78                 :            :      | restoring scratches got |
      79                 :            :      |         memory          |
      80                 :            :       -------------------------
      81                 :            : 
      82                 :            :    To speed up the process:
      83                 :            :      o We process only insns affected by changes on previous
      84                 :            :        iterations;
      85                 :            :      o We don't use DFA-infrastructure because it results in much slower
      86                 :            :        compiler speed than a special IR described below does;
      87                 :            :      o We use a special insn representation for quick access to insn
      88                 :            :        info which is always *synchronized* with the current RTL;
      89                 :            :        o Insn IR is minimized by memory.  It is divided on three parts:
      90                 :            :          o one specific for each insn in RTL (only operand locations);
      91                 :            :          o one common for all insns in RTL with the same insn code
      92                 :            :            (different operand attributes from machine descriptions);
      93                 :            :          o one oriented for maintenance of live info (list of pseudos).
      94                 :            :        o Pseudo data:
      95                 :            :          o all insns where the pseudo is referenced;
      96                 :            :          o live info (conflicting hard regs, live ranges, # of
      97                 :            :            references etc);
      98                 :            :          o data used for assigning (preferred hard regs, costs etc).
      99                 :            : 
     100                 :            :    This file contains LRA driver, LRA utility functions and data, and
     101                 :            :    code for dealing with scratches.  */
     102                 :            : 
     103                 :            : #include "config.h"
     104                 :            : #include "system.h"
     105                 :            : #include "coretypes.h"
     106                 :            : #include "backend.h"
     107                 :            : #include "target.h"
     108                 :            : #include "rtl.h"
     109                 :            : #include "tree.h"
     110                 :            : #include "predict.h"
     111                 :            : #include "df.h"
     112                 :            : #include "memmodel.h"
     113                 :            : #include "tm_p.h"
     114                 :            : #include "optabs.h"
     115                 :            : #include "regs.h"
     116                 :            : #include "ira.h"
     117                 :            : #include "recog.h"
     118                 :            : #include "expr.h"
     119                 :            : #include "cfgrtl.h"
     120                 :            : #include "cfgbuild.h"
     121                 :            : #include "lra.h"
     122                 :            : #include "lra-int.h"
     123                 :            : #include "print-rtl.h"
     124                 :            : #include "function-abi.h"
     125                 :            : 
     126                 :            : /* Dump bitmap SET with TITLE and BB INDEX.  */
     127                 :            : void
     128                 :       1806 : lra_dump_bitmap_with_title (const char *title, bitmap set, int index)
     129                 :            : {
     130                 :       1806 :   unsigned int i;
     131                 :       1806 :   int count;
     132                 :       1806 :   bitmap_iterator bi;
     133                 :       1806 :   static const int max_nums_on_line = 10;
     134                 :            : 
     135                 :       1806 :   if (bitmap_empty_p (set))
     136                 :       1806 :     return;
     137                 :          0 :   fprintf (lra_dump_file, "  %s %d:", title, index);
     138                 :          0 :   fprintf (lra_dump_file, "\n");
     139                 :          0 :   count = max_nums_on_line + 1;
     140                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (set, 0, i, bi)
     141                 :            :     {
     142                 :          0 :       if (count > max_nums_on_line)
     143                 :            :         {
     144                 :          0 :           fprintf (lra_dump_file, "\n    ");
     145                 :          0 :           count = 0;
     146                 :            :         }
     147                 :          0 :       fprintf (lra_dump_file, " %4u", i);
     148                 :          0 :       count++;
     149                 :            :     }
     150                 :          0 :   fprintf (lra_dump_file, "\n");
     151                 :            : }
     152                 :            : 
     153                 :            : /* Hard registers currently not available for allocation.  It can
     154                 :            :    changed after some hard  registers become not eliminable.  */
     155                 :            : HARD_REG_SET lra_no_alloc_regs;
     156                 :            : 
     157                 :            : static int get_new_reg_value (void);
     158                 :            : static void expand_reg_info (void);
     159                 :            : static void invalidate_insn_recog_data (int);
     160                 :            : static int get_insn_freq (rtx_insn *);
     161                 :            : static void invalidate_insn_data_regno_info (lra_insn_recog_data_t,
     162                 :            :                                              rtx_insn *, int);
     163                 :            : static void remove_scratches_1 (rtx_insn *);
     164                 :            : 
     165                 :            : /* Expand all regno related info needed for LRA.  */
     166                 :            : static void
     167                 :    5250720 : expand_reg_data (int old)
     168                 :            : {
     169                 :    5250720 :   resize_reg_info ();
     170                 :    5250720 :   expand_reg_info ();
     171                 :    5250720 :   ira_expand_reg_equiv ();
     172                 :    5252710 :   for (int i = (int) max_reg_num () - 1; i >= old; i--)
     173                 :       1988 :     lra_change_class (i, ALL_REGS, "      Set", true);
     174                 :    5250720 : }
     175                 :            : 
     176                 :            : /* Create and return a new reg of ORIGINAL mode.  If ORIGINAL is NULL
     177                 :            :    or of VOIDmode, use MD_MODE for the new reg.  Initialize its
     178                 :            :    register class to RCLASS.  Print message about assigning class
     179                 :            :    RCLASS containing new register name TITLE unless it is NULL.  Use
     180                 :            :    attributes of ORIGINAL if it is a register.  The created register
     181                 :            :    will have unique held value.  */
     182                 :            : rtx
     183                 :    5248730 : lra_create_new_reg_with_unique_value (machine_mode md_mode, rtx original,
     184                 :            :                                       enum reg_class rclass, const char *title)
     185                 :            : {
     186                 :    5248730 :   machine_mode mode;
     187                 :    5248730 :   rtx new_reg;
     188                 :            : 
     189                 :    5248730 :   if (original == NULL_RTX || (mode = GET_MODE (original)) == VOIDmode)
     190                 :            :     mode = md_mode;
     191                 :    5248730 :   lra_assert (mode != VOIDmode);
     192                 :    5248730 :   new_reg = gen_reg_rtx (mode);
     193                 :    5248730 :   if (original == NULL_RTX || ! REG_P (original))
     194                 :            :     {
     195                 :    1707510 :       if (lra_dump_file != NULL)
     196                 :         25 :         fprintf (lra_dump_file, "      Creating newreg=%i", REGNO (new_reg));
     197                 :            :     }
     198                 :            :   else
     199                 :            :     {
     200                 :    3541220 :       if (ORIGINAL_REGNO (original) >= FIRST_PSEUDO_REGISTER)
     201                 :    3531410 :         ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original);
     202                 :    3541220 :       REG_USERVAR_P (new_reg) = REG_USERVAR_P (original);
     203                 :    3541220 :       REG_POINTER (new_reg) = REG_POINTER (original);
     204                 :    3541220 :       REG_ATTRS (new_reg) = REG_ATTRS (original);
     205                 :    3541220 :       if (lra_dump_file != NULL)
     206                 :        227 :         fprintf (lra_dump_file, "      Creating newreg=%i from oldreg=%i",
     207                 :            :                  REGNO (new_reg), REGNO (original));
     208                 :            :     }
     209                 :    5248730 :   if (lra_dump_file != NULL)
     210                 :            :     {
     211                 :        252 :       if (title != NULL)
     212                 :        238 :         fprintf (lra_dump_file, ", assigning class %s to%s%s r%d",
     213                 :        252 :                  reg_class_names[rclass], *title == '\0' ? "" : " ",
     214                 :            :                  title, REGNO (new_reg));
     215                 :        252 :       fprintf (lra_dump_file, "\n");
     216                 :            :     }
     217                 :    5248730 :   expand_reg_data (max_reg_num ());
     218                 :    5248730 :   setup_reg_classes (REGNO (new_reg), rclass, NO_REGS, rclass);
     219                 :    5248730 :   return new_reg;
     220                 :            : }
     221                 :            : 
     222                 :            : /* Analogous to the previous function but also inherits value of
     223                 :            :    ORIGINAL.  */
     224                 :            : rtx
     225                 :    3612560 : lra_create_new_reg (machine_mode md_mode, rtx original,
     226                 :            :                     enum reg_class rclass, const char *title)
     227                 :            : {
     228                 :    3612560 :   rtx new_reg;
     229                 :            : 
     230                 :    3612560 :   new_reg
     231                 :    3612560 :     = lra_create_new_reg_with_unique_value (md_mode, original, rclass, title);
     232                 :    3612560 :   if (original != NULL_RTX && REG_P (original))
     233                 :    2279710 :     lra_assign_reg_val (REGNO (original), REGNO (new_reg));
     234                 :    3612560 :   return new_reg;
     235                 :            : }
     236                 :            : 
     237                 :            : /* Set up for REGNO unique hold value.  */
     238                 :            : void
     239                 :        565 : lra_set_regno_unique_value (int regno)
     240                 :            : {
     241                 :        565 :   lra_reg_info[regno].val = get_new_reg_value ();
     242                 :        565 : }
     243                 :            : 
     244                 :            : /* Invalidate INSN related info used by LRA.  The info should never be
     245                 :            :    used after that.  */
     246                 :            : void
     247                 :    9219230 : lra_invalidate_insn_data (rtx_insn *insn)
     248                 :            : {
     249                 :    9219230 :   lra_invalidate_insn_regno_info (insn);
     250                 :    9219230 :   invalidate_insn_recog_data (INSN_UID (insn));
     251                 :    9219230 : }
     252                 :            : 
     253                 :            : /* Mark INSN deleted and invalidate the insn related info used by
     254                 :            :    LRA.  */
     255                 :            : void
     256                 :    1705090 : lra_set_insn_deleted (rtx_insn *insn)
     257                 :            : {
     258                 :    1705090 :   lra_invalidate_insn_data (insn);
     259                 :    1705090 :   SET_INSN_DELETED (insn);
     260                 :    1705090 : }
     261                 :            : 
     262                 :            : /* Delete an unneeded INSN and any previous insns who sole purpose is
     263                 :            :    loading data that is dead in INSN.  */
     264                 :            : void
     265                 :          0 : lra_delete_dead_insn (rtx_insn *insn)
     266                 :            : {
     267                 :          0 :   rtx_insn *prev = prev_real_insn (insn);
     268                 :          0 :   rtx prev_dest;
     269                 :            : 
     270                 :            :   /* If the previous insn sets a register that dies in our insn,
     271                 :            :      delete it too.  */
     272                 :          0 :   if (prev && GET_CODE (PATTERN (prev)) == SET
     273                 :          0 :       && (prev_dest = SET_DEST (PATTERN (prev)), REG_P (prev_dest))
     274                 :          0 :       && reg_mentioned_p (prev_dest, PATTERN (insn))
     275                 :          0 :       && find_regno_note (insn, REG_DEAD, REGNO (prev_dest))
     276                 :          0 :       && ! side_effects_p (SET_SRC (PATTERN (prev))))
     277                 :          0 :     lra_delete_dead_insn (prev);
     278                 :            : 
     279                 :          0 :   lra_set_insn_deleted (insn);
     280                 :          0 : }
     281                 :            : 
     282                 :            : /* Emit insn x = y + z.  Return NULL if we failed to do it.
     283                 :            :    Otherwise, return the insn.  We don't use gen_add3_insn as it might
     284                 :            :    clobber CC.  */
     285                 :            : static rtx_insn *
     286                 :     611460 : emit_add3_insn (rtx x, rtx y, rtx z)
     287                 :            : {
     288                 :     611460 :   rtx_insn *last;
     289                 :            : 
     290                 :     611460 :   last = get_last_insn ();
     291                 :            : 
     292                 :     611460 :   if (have_addptr3_insn (x, y, z))
     293                 :            :     {
     294                 :          0 :       rtx_insn *insn = gen_addptr3_insn (x, y, z);
     295                 :            : 
     296                 :            :       /* If the target provides an "addptr" pattern it hopefully does
     297                 :            :          for a reason.  So falling back to the normal add would be
     298                 :            :          a bug.  */
     299                 :          0 :       lra_assert (insn != NULL_RTX);
     300                 :          0 :       emit_insn (insn);
     301                 :          0 :       return insn;
     302                 :            :     }
     303                 :            : 
     304                 :     611460 :   rtx_insn *insn = emit_insn (gen_rtx_SET (x, gen_rtx_PLUS (GET_MODE (y),
     305                 :            :                                                             y, z)));
     306                 :    1222920 :   if (recog_memoized (insn) < 0)
     307                 :            :     {
     308                 :         95 :       delete_insns_since (last);
     309                 :         95 :       insn = NULL;
     310                 :            :     }
     311                 :            :   return insn;
     312                 :            : }
     313                 :            : 
     314                 :            : /* Emit insn x = x + y.  Return the insn.  We use gen_add2_insn as the
     315                 :            :    last resort.  */
     316                 :            : static rtx_insn *
     317                 :         95 : emit_add2_insn (rtx x, rtx y)
     318                 :            : {
     319                 :         95 :   rtx_insn *insn = emit_add3_insn (x, x, y);
     320                 :         95 :   if (insn == NULL_RTX)
     321                 :            :     {
     322                 :          0 :       insn = gen_add2_insn (x, y);
     323                 :          0 :       if (insn != NULL_RTX)
     324                 :          0 :         emit_insn (insn);
     325                 :            :     }
     326                 :         95 :   return insn;
     327                 :            : }
     328                 :            : 
     329                 :            : /* Target checks operands through operand predicates to recognize an
     330                 :            :    insn.  We should have a special precaution to generate add insns
     331                 :            :    which are frequent results of elimination.
     332                 :            : 
     333                 :            :    Emit insns for x = y + z.  X can be used to store intermediate
     334                 :            :    values and should be not in Y and Z when we use X to store an
     335                 :            :    intermediate value.  Y + Z should form [base] [+ index[ * scale]] [
     336                 :            :    + disp] where base and index are registers, disp and scale are
     337                 :            :    constants.  Y should contain base if it is present, Z should
     338                 :            :    contain disp if any.  index[*scale] can be part of Y or Z.  */
     339                 :            : void
     340                 :     611365 : lra_emit_add (rtx x, rtx y, rtx z)
     341                 :            : {
     342                 :     611365 :   int old;
     343                 :     611365 :   rtx_insn *last;
     344                 :     611365 :   rtx a1, a2, base, index, disp, scale, index_scale;
     345                 :     611365 :   bool ok_p;
     346                 :            : 
     347                 :     611365 :   rtx_insn *add3_insn = emit_add3_insn (x, y, z);
     348                 :     611365 :   old = max_reg_num ();
     349                 :     611365 :   if (add3_insn != NULL)
     350                 :            :     ;
     351                 :            :   else
     352                 :            :     {
     353                 :         95 :       disp = a2 = NULL_RTX;
     354                 :         95 :       if (GET_CODE (y) == PLUS)
     355                 :            :         {
     356                 :          0 :           a1 = XEXP (y, 0);
     357                 :          0 :           a2 = XEXP (y, 1);
     358                 :          0 :           disp = z;
     359                 :            :         }
     360                 :            :       else
     361                 :            :         {
     362                 :         95 :           a1 = y;
     363                 :         95 :           if (CONSTANT_P (z))
     364                 :            :             disp = z;
     365                 :            :           else
     366                 :          0 :             a2 = z;
     367                 :            :         }
     368                 :         95 :       index_scale = scale = NULL_RTX;
     369                 :         95 :       if (GET_CODE (a1) == MULT)
     370                 :            :         {
     371                 :          0 :           index_scale = a1;
     372                 :          0 :           index = XEXP (a1, 0);
     373                 :          0 :           scale = XEXP (a1, 1);
     374                 :          0 :           base = a2;
     375                 :            :         }
     376                 :         95 :       else if (a2 != NULL_RTX && GET_CODE (a2) == MULT)
     377                 :            :         {
     378                 :          0 :           index_scale = a2;
     379                 :          0 :           index = XEXP (a2, 0);
     380                 :          0 :           scale = XEXP (a2, 1);
     381                 :          0 :           base = a1;
     382                 :            :         }
     383                 :            :       else
     384                 :            :         {
     385                 :            :           base = a1;
     386                 :            :           index = a2;
     387                 :            :         }
     388                 :         95 :       if ((base != NULL_RTX && ! (REG_P (base) || GET_CODE (base) == SUBREG))
     389                 :         95 :           || (index != NULL_RTX
     390                 :          0 :               && ! (REG_P (index) || GET_CODE (index) == SUBREG))
     391                 :         95 :           || (disp != NULL_RTX && ! CONSTANT_P (disp))
     392                 :         95 :           || (scale != NULL_RTX && ! CONSTANT_P (scale)))
     393                 :            :         {
     394                 :            :           /* Probably we have no 3 op add.  Last chance is to use 2-op
     395                 :            :              add insn.  To succeed, don't move Z to X as an address
     396                 :            :              segment always comes in Y.  Otherwise, we might fail when
     397                 :            :              adding the address segment to register.  */
     398                 :          0 :           lra_assert (x != y && x != z);
     399                 :          0 :           emit_move_insn (x, y);
     400                 :          0 :           rtx_insn *insn = emit_add2_insn (x, z);
     401                 :          0 :           lra_assert (insn != NULL_RTX);
     402                 :            :         }
     403                 :            :       else
     404                 :            :         {
     405                 :         95 :           if (index_scale == NULL_RTX)
     406                 :         95 :             index_scale = index;
     407                 :         95 :           if (disp == NULL_RTX)
     408                 :            :             {
     409                 :            :               /* Generate x = index_scale; x = x + base.  */
     410                 :          0 :               lra_assert (index_scale != NULL_RTX && base != NULL_RTX);
     411                 :          0 :               emit_move_insn (x, index_scale);
     412                 :          0 :               rtx_insn *insn = emit_add2_insn (x, base);
     413                 :          0 :               lra_assert (insn != NULL_RTX);
     414                 :            :             }
     415                 :         95 :           else if (scale == NULL_RTX)
     416                 :            :             {
     417                 :            :               /* Try x = base + disp.  */
     418                 :         95 :               lra_assert (base != NULL_RTX);
     419                 :         95 :               last = get_last_insn ();
     420                 :         95 :               rtx_insn *move_insn =
     421                 :         95 :                 emit_move_insn (x, gen_rtx_PLUS (GET_MODE (base), base, disp));
     422                 :        190 :               if (recog_memoized (move_insn) < 0)
     423                 :            :                 {
     424                 :         95 :                   delete_insns_since (last);
     425                 :            :                   /* Generate x = disp; x = x + base.  */
     426                 :         95 :                   emit_move_insn (x, disp);
     427                 :         95 :                   rtx_insn *add2_insn = emit_add2_insn (x, base);
     428                 :         95 :                   lra_assert (add2_insn != NULL_RTX);
     429                 :            :                 }
     430                 :            :               /* Generate x = x + index.  */
     431                 :         95 :               if (index != NULL_RTX)
     432                 :            :                 {
     433                 :          0 :                   rtx_insn *insn = emit_add2_insn (x, index);
     434                 :          0 :                   lra_assert (insn != NULL_RTX);
     435                 :            :                 }
     436                 :            :             }
     437                 :            :           else
     438                 :            :             {
     439                 :            :               /* Try x = index_scale; x = x + disp; x = x + base.  */
     440                 :          0 :               last = get_last_insn ();
     441                 :          0 :               rtx_insn *move_insn = emit_move_insn (x, index_scale);
     442                 :          0 :               ok_p = false;
     443                 :          0 :               if (recog_memoized (move_insn) >= 0)
     444                 :            :                 {
     445                 :          0 :                   rtx_insn *insn = emit_add2_insn (x, disp);
     446                 :          0 :                   if (insn != NULL_RTX)
     447                 :            :                     {
     448                 :          0 :                       if (base == NULL_RTX)
     449                 :            :                         ok_p = true;
     450                 :            :                       else
     451                 :            :                         {
     452                 :          0 :                           insn = emit_add2_insn (x, base);
     453                 :          0 :                           if (insn != NULL_RTX)
     454                 :            :                             ok_p = true;
     455                 :            :                         }
     456                 :            :                     }
     457                 :            :                 }
     458                 :            :               if (! ok_p)
     459                 :            :                 {
     460                 :          0 :                   rtx_insn *insn;
     461                 :            :                   
     462                 :          0 :                   delete_insns_since (last);
     463                 :            :                   /* Generate x = disp; x = x + base; x = x + index_scale.  */
     464                 :          0 :                   emit_move_insn (x, disp);
     465                 :          0 :                   if (base != NULL_RTX)
     466                 :            :                     {
     467                 :          0 :                       insn = emit_add2_insn (x, base);
     468                 :          0 :                       lra_assert (insn != NULL_RTX);
     469                 :            :                     }
     470                 :          0 :                   insn = emit_add2_insn (x, index_scale);
     471                 :          0 :                   lra_assert (insn != NULL_RTX);
     472                 :            :                 }
     473                 :            :             }
     474                 :            :         }
     475                 :            :     }
     476                 :            :   /* Functions emit_... can create pseudos -- so expand the pseudo
     477                 :            :      data.  */
     478                 :     611365 :   if (old != max_reg_num ())
     479                 :          0 :     expand_reg_data (old);
     480                 :     611365 : }
     481                 :            : 
     482                 :            : /* The number of emitted reload insns so far.  */
     483                 :            : int lra_curr_reload_num;
     484                 :            : 
     485                 :            : /* Emit x := y, processing special case when y = u + v or y = u + v *
     486                 :            :    scale + w through emit_add (Y can be an address which is base +
     487                 :            :    index reg * scale + displacement in general case).  X may be used
     488                 :            :    as intermediate result therefore it should be not in Y.  */
     489                 :            : void
     490                 :    5908170 : lra_emit_move (rtx x, rtx y)
     491                 :            : {
     492                 :    5908170 :   int old;
     493                 :            : 
     494                 :    5908170 :   if (GET_CODE (y) != PLUS)
     495                 :            :     {
     496                 :    5296890 :       if (rtx_equal_p (x, y))
     497                 :            :         return;
     498                 :    5296890 :       old = max_reg_num ();
     499                 :    5296890 :       rtx_insn *insn = emit_move_insn (x, y);
     500                 :            :       /* The move pattern may require scratch registers, so convert them
     501                 :            :          into real registers now.  */
     502                 :    5296890 :       if (insn != NULL_RTX)
     503                 :    5296890 :         remove_scratches_1 (insn);
     504                 :    5296890 :       if (REG_P (x))
     505                 :    4886760 :         lra_reg_info[ORIGINAL_REGNO (x)].last_reload = ++lra_curr_reload_num;
     506                 :            :       /* Function emit_move can create pseudos -- so expand the pseudo
     507                 :            :          data.  */
     508                 :    5296890 :       if (old != max_reg_num ())
     509                 :       1988 :         expand_reg_data (old);
     510                 :    5296890 :       return;
     511                 :            :     }
     512                 :     611280 :   lra_emit_add (x, XEXP (y, 0), XEXP (y, 1));
     513                 :            : }
     514                 :            : 
     515                 :            : /* Update insn operands which are duplication of operands whose
     516                 :            :    numbers are in array of NOPS (with end marker -1).  The insn is
     517                 :            :    represented by its LRA internal representation ID.  */
     518                 :            : void
     519                 :    1111220 : lra_update_dups (lra_insn_recog_data_t id, signed char *nops)
     520                 :            : {
     521                 :    1111220 :   int i, j, nop;
     522                 :    1111220 :   struct lra_static_insn_data *static_id = id->insn_static_data;
     523                 :            : 
     524                 :    1452970 :   for (i = 0; i < static_id->n_dups; i++)
     525                 :     683508 :     for (j = 0; (nop = nops[j]) >= 0; j++)
     526                 :     341754 :       if (static_id->dup_num[i] == nop)
     527                 :     128106 :         *id->dup_loc[i] = *id->operand_loc[nop];
     528                 :    1111220 : }
     529                 :            : 
     530                 :            : 
     531                 :            : 
     532                 :            : /* This page contains code dealing with info about registers in the
     533                 :            :    insns.  */
     534                 :            : 
     535                 :            : /* Pools for insn reg info.  */
     536                 :            : object_allocator<lra_insn_reg> lra_insn_reg_pool ("insn regs");
     537                 :            : 
     538                 :            : /* Create LRA insn related info about a reference to REGNO in INSN
     539                 :            :    with TYPE (in/out/inout), biggest reference mode MODE, flag that it
     540                 :            :    is reference through subreg (SUBREG_P), and reference to the next
     541                 :            :    insn reg info (NEXT).  If REGNO can be early clobbered,
     542                 :            :    alternatives in which it can be early clobbered are given by
     543                 :            :    EARLY_CLOBBER_ALTS.  */
     544                 :            : static struct lra_insn_reg *
     545                 :  169618000 : new_insn_reg (rtx_insn *insn, int regno, enum op_type type,
     546                 :            :               machine_mode mode, bool subreg_p,
     547                 :            :               alternative_mask early_clobber_alts,
     548                 :            :               struct lra_insn_reg *next)
     549                 :            : {
     550                 :  169618000 :   lra_insn_reg *ir = lra_insn_reg_pool.allocate ();
     551                 :  169618000 :   ir->type = type;
     552                 :  169618000 :   ir->biggest_mode = mode;
     553                 :  169618000 :   if (NONDEBUG_INSN_P (insn)
     554                 :  169618000 :       && partial_subreg_p (lra_reg_info[regno].biggest_mode, mode))
     555                 :   28050000 :     lra_reg_info[regno].biggest_mode = mode;
     556                 :  169618000 :   ir->subreg_p = subreg_p;
     557                 :  169618000 :   ir->early_clobber_alts = early_clobber_alts;
     558                 :  169618000 :   ir->regno = regno;
     559                 :  169618000 :   ir->next = next;
     560                 :  169618000 :   return ir;
     561                 :            : }
     562                 :            : 
     563                 :            : /* Free insn reg info list IR.  */
     564                 :            : static void
     565                 :          0 : free_insn_regs (struct lra_insn_reg *ir)
     566                 :            : {
     567                 :  166780000 :   struct lra_insn_reg *next_ir;
     568                 :            : 
     569                 :  166780000 :   for (; ir != NULL; ir = next_ir)
     570                 :            :     {
     571                 :   78240600 :       next_ir = ir->next;
     572                 :   78240600 :       lra_insn_reg_pool.remove (ir);
     573                 :            :     }
     574                 :          0 : }
     575                 :            : 
     576                 :            : /* Finish pool for insn reg info.  */
     577                 :            : static void
     578                 :     944096 : finish_insn_regs (void)
     579                 :            : {
     580                 :     944096 :   lra_insn_reg_pool.release ();
     581                 :     944096 : }
     582                 :            : 
     583                 :            : 
     584                 :            : 
     585                 :            : /* This page contains code dealing LRA insn info (or in other words
     586                 :            :    LRA internal insn representation).  */
     587                 :            : 
     588                 :            : /* Map INSN_CODE -> the static insn data.  This info is valid during
     589                 :            :    all translation unit.  */
     590                 :            : struct lra_static_insn_data *insn_code_data[NUM_INSN_CODES];
     591                 :            : 
     592                 :            : /* Debug insns are represented as a special insn with one input
     593                 :            :    operand which is RTL expression in var_location.  */
     594                 :            : 
     595                 :            : /* The following data are used as static insn operand data for all
     596                 :            :    debug insns.  If structure lra_operand_data is changed, the
     597                 :            :    initializer should be changed too.  */
     598                 :            : static struct lra_operand_data debug_operand_data =
     599                 :            :   {
     600                 :            :     NULL, /* alternative  */
     601                 :            :     0, /* early_clobber_alts */
     602                 :            :     E_VOIDmode, /* We are not interesting in the operand mode.  */
     603                 :            :     OP_IN,
     604                 :            :     0, 0, 0
     605                 :            :   };
     606                 :            : 
     607                 :            : /* The following data are used as static insn data for all debug
     608                 :            :    bind insns.  If structure lra_static_insn_data is changed, the
     609                 :            :    initializer should be changed too.  */
     610                 :            : static struct lra_static_insn_data debug_bind_static_data =
     611                 :            :   {
     612                 :            :     &debug_operand_data,
     613                 :            :     0,  /* Duplication operands #.  */
     614                 :            :     -1, /* Commutative operand #.  */
     615                 :            :     1,  /* Operands #.  There is only one operand which is debug RTL
     616                 :            :            expression.  */
     617                 :            :     0,  /* Duplications #.  */
     618                 :            :     0,  /* Alternatives #.  We are not interesting in alternatives
     619                 :            :            because we does not proceed debug_insns for reloads.  */
     620                 :            :     NULL, /* Hard registers referenced in machine description.  */
     621                 :            :     NULL  /* Descriptions of operands in alternatives.  */
     622                 :            :   };
     623                 :            : 
     624                 :            : /* The following data are used as static insn data for all debug
     625                 :            :    marker insns.  If structure lra_static_insn_data is changed, the
     626                 :            :    initializer should be changed too.  */
     627                 :            : static struct lra_static_insn_data debug_marker_static_data =
     628                 :            :   {
     629                 :            :     &debug_operand_data,
     630                 :            :     0,  /* Duplication operands #.  */
     631                 :            :     -1, /* Commutative operand #.  */
     632                 :            :     0,  /* Operands #.  There isn't any operand.  */
     633                 :            :     0,  /* Duplications #.  */
     634                 :            :     0,  /* Alternatives #.  We are not interesting in alternatives
     635                 :            :            because we does not proceed debug_insns for reloads.  */
     636                 :            :     NULL, /* Hard registers referenced in machine description.  */
     637                 :            :     NULL  /* Descriptions of operands in alternatives.  */
     638                 :            :   };
     639                 :            : 
     640                 :            : /* Called once per compiler work to initialize some LRA data related
     641                 :            :    to insns.  */
     642                 :            : static void
     643                 :     149606 : init_insn_code_data_once (void)
     644                 :            : {
     645                 :     149606 :   memset (insn_code_data, 0, sizeof (insn_code_data));
     646                 :          0 : }
     647                 :            : 
     648                 :            : /* Called once per compiler work to finalize some LRA data related to
     649                 :            :    insns.  */
     650                 :            : static void
     651                 :     198377 : finish_insn_code_data_once (void)
     652                 :            : {
     653                 : 1683030000 :   for (unsigned int i = 0; i < NUM_INSN_CODES; i++)
     654                 :            :     {
     655                 : 1682830000 :       if (insn_code_data[i] != NULL)
     656                 :            :         {
     657                 :    1609430 :           free (insn_code_data[i]);
     658                 :    1609430 :           insn_code_data[i] = NULL;
     659                 :            :         }
     660                 :            :     }
     661                 :     198377 : }
     662                 :            : 
     663                 :            : /* Return static insn data, allocate and setup if necessary.  Although
     664                 :            :    dup_num is static data (it depends only on icode), to set it up we
     665                 :            :    need to extract insn first.  So recog_data should be valid for
     666                 :            :    normal insn (ICODE >= 0) before the call.  */
     667                 :            : static struct lra_static_insn_data *
     668                 :   59860700 : get_static_insn_data (int icode, int nop, int ndup, int nalt)
     669                 :            : {
     670                 :   59860700 :   struct lra_static_insn_data *data;
     671                 :   59860700 :   size_t n_bytes;
     672                 :            : 
     673                 :   59860700 :   lra_assert (icode < (int) NUM_INSN_CODES);
     674                 :   59860700 :   if (icode >= 0 && (data = insn_code_data[icode]) != NULL)
     675                 :            :     return data;
     676                 :    2248950 :   lra_assert (nop >= 0 && ndup >= 0 && nalt >= 0);
     677                 :    2248950 :   n_bytes = sizeof (struct lra_static_insn_data)
     678                 :    2248950 :             + sizeof (struct lra_operand_data) * nop
     679                 :    2248950 :             + sizeof (int) * ndup;
     680                 :    2248950 :   data = XNEWVAR (struct lra_static_insn_data, n_bytes);
     681                 :    2248950 :   data->operand_alternative = NULL;
     682                 :    2248950 :   data->n_operands = nop;
     683                 :    2248950 :   data->n_dups = ndup;
     684                 :    2248950 :   data->n_alternatives = nalt;
     685                 :    2248950 :   data->operand = ((struct lra_operand_data *)
     686                 :            :                    ((char *) data + sizeof (struct lra_static_insn_data)));
     687                 :    2248950 :   data->dup_num = ((int *) ((char *) data->operand
     688                 :    2248950 :                             + sizeof (struct lra_operand_data) * nop));
     689                 :    2248950 :   if (icode >= 0)
     690                 :            :     {
     691                 :    1609430 :       int i;
     692                 :            : 
     693                 :    1609430 :       insn_code_data[icode] = data;
     694                 :    5314400 :       for (i = 0; i < nop; i++)
     695                 :            :         {
     696                 :    3704970 :           data->operand[i].constraint
     697                 :    3704970 :             = insn_data[icode].operand[i].constraint;
     698                 :    3704970 :           data->operand[i].mode = insn_data[icode].operand[i].mode;
     699                 :    3704970 :           data->operand[i].strict_low = insn_data[icode].operand[i].strict_low;
     700                 :    3704970 :           data->operand[i].is_operator
     701                 :    3704970 :             = insn_data[icode].operand[i].is_operator;
     702                 :    3704970 :           data->operand[i].type
     703                 :    3704970 :             = (data->operand[i].constraint[0] == '=' ? OP_OUT
     704                 :            :                : data->operand[i].constraint[0] == '+' ? OP_INOUT
     705                 :            :                : OP_IN);
     706                 :    3704970 :           data->operand[i].is_address = false;
     707                 :            :         }
     708                 :    1711350 :       for (i = 0; i < ndup; i++)
     709                 :     101921 :         data->dup_num[i] = recog_data.dup_num[i];
     710                 :            :     }
     711                 :            :   return data;
     712                 :            : }
     713                 :            : 
     714                 :            : /* The current length of the following array.  */
     715                 :            : int lra_insn_recog_data_len;
     716                 :            : 
     717                 :            : /* Map INSN_UID -> the insn recog data (NULL if unknown).  */
     718                 :            : lra_insn_recog_data_t *lra_insn_recog_data;
     719                 :            : 
     720                 :            : /* Alloc pool we allocate entries for lra_insn_recog_data from.  */
     721                 :            : static object_allocator<class lra_insn_recog_data>
     722                 :            :   lra_insn_recog_data_pool ("insn recog data pool");
     723                 :            : 
     724                 :            : /* Initialize LRA data about insns.  */
     725                 :            : static void
     726                 :     944096 : init_insn_recog_data (void)
     727                 :            : {
     728                 :     944096 :   lra_insn_recog_data_len = 0;
     729                 :     944096 :   lra_insn_recog_data = NULL;
     730                 :          0 : }
     731                 :            : 
     732                 :            : /* Expand, if necessary, LRA data about insns.  */
     733                 :            : static void
     734                 :  120748000 : check_and_expand_insn_recog_data (int index)
     735                 :            : {
     736                 :  120748000 :   int i, old;
     737                 :            : 
     738                 :  120748000 :   if (lra_insn_recog_data_len > index)
     739                 :            :     return;
     740                 :    2312820 :   old = lra_insn_recog_data_len;
     741                 :    2312820 :   lra_insn_recog_data_len = index * 3 / 2 + 1;
     742                 :    2312820 :   lra_insn_recog_data = XRESIZEVEC (lra_insn_recog_data_t,
     743                 :            :                                     lra_insn_recog_data,
     744                 :            :                                     lra_insn_recog_data_len);
     745                 :  183762000 :   for (i = old; i < lra_insn_recog_data_len; i++)
     746                 :  181449000 :     lra_insn_recog_data[i] = NULL;
     747                 :            : }
     748                 :            : 
     749                 :            : /* Finish LRA DATA about insn.  */
     750                 :            : static void
     751                 :   87899800 : free_insn_recog_data (lra_insn_recog_data_t data)
     752                 :            : {
     753                 :   87899800 :   if (data->operand_loc != NULL)
     754                 :   80727000 :     free (data->operand_loc);
     755                 :   87899800 :   if (data->dup_loc != NULL)
     756                 :     368920 :     free (data->dup_loc);
     757                 :   87899800 :   if (data->arg_hard_regs != NULL)
     758                 :    2982750 :     free (data->arg_hard_regs);
     759                 :   87899800 :   if (data->icode < 0 && NONDEBUG_INSN_P (data->insn))
     760                 :            :     {
     761                 :     639514 :       if (data->insn_static_data->operand_alternative != NULL)
     762                 :      34685 :         free (const_cast <operand_alternative *>
     763                 :            :               (data->insn_static_data->operand_alternative));
     764                 :     639514 :       free_insn_regs (data->insn_static_data->hard_regs);
     765                 :     639514 :       free (data->insn_static_data);
     766                 :            :     }
     767                 :   87899800 :   free_insn_regs (data->regs);
     768                 :   87899800 :   data->regs = NULL;
     769                 :   87899800 :   lra_insn_recog_data_pool.remove (data);
     770                 :   87899800 : }
     771                 :            : 
     772                 :            : /* Pools for copies.  */
     773                 :            : static object_allocator<lra_copy> lra_copy_pool ("lra copies");
     774                 :            : 
     775                 :            : /* Finish LRA data about all insns.  */
     776                 :            : static void
     777                 :     944096 : finish_insn_recog_data (void)
     778                 :            : {
     779                 :     944096 :   int i;
     780                 :     944096 :   lra_insn_recog_data_t data;
     781                 :            : 
     782                 :  182393000 :   for (i = 0; i < lra_insn_recog_data_len; i++)
     783                 :  181449000 :     if ((data = lra_insn_recog_data[i]) != NULL)
     784                 :   78571500 :       free_insn_recog_data (data);
     785                 :     944096 :   finish_insn_regs ();
     786                 :     944096 :   lra_copy_pool.release ();
     787                 :     944096 :   lra_insn_reg_pool.release ();
     788                 :     944096 :   lra_insn_recog_data_pool.release ();
     789                 :     944096 :   free (lra_insn_recog_data);
     790                 :     944096 : }
     791                 :            : 
     792                 :            : /* Setup info about operands in alternatives of LRA DATA of insn.  */
     793                 :            : static void
     794                 :    1971980 : setup_operand_alternative (lra_insn_recog_data_t data,
     795                 :            :                            const operand_alternative *op_alt)
     796                 :            : {
     797                 :    1971980 :   int i, j, nop, nalt;
     798                 :    1971980 :   int icode = data->icode;
     799                 :    1971980 :   struct lra_static_insn_data *static_data = data->insn_static_data;
     800                 :            : 
     801                 :    1971980 :   static_data->commutative = -1;
     802                 :    1971980 :   nop = static_data->n_operands;
     803                 :    1971980 :   nalt = static_data->n_alternatives;
     804                 :    1971980 :   static_data->operand_alternative = op_alt;
     805                 :    5791740 :   for (i = 0; i < nop; i++)
     806                 :            :     {
     807                 :    3819760 :       static_data->operand[i].early_clobber_alts = 0;
     808                 :    3819760 :       static_data->operand[i].is_address = false;
     809                 :    3819760 :       if (static_data->operand[i].constraint[0] == '%')
     810                 :            :         {
     811                 :            :           /* We currently only support one commutative pair of operands.  */
     812                 :     240738 :           if (static_data->commutative < 0)
     813                 :     240440 :             static_data->commutative = i;
     814                 :            :           else
     815                 :        298 :             lra_assert (icode < 0); /* Asm  */
     816                 :            :           /* The last operand should not be marked commutative.  */
     817                 :     240738 :           lra_assert (i != nop - 1);
     818                 :            :         }
     819                 :            :     }
     820                 :   11530100 :   for (j = 0; j < nalt; j++)
     821                 :   30165800 :     for (i = 0; i < nop; i++, op_alt++)
     822                 :            :       {
     823                 :   20607700 :         if (op_alt->earlyclobber)
     824                 :      12150 :           static_data->operand[i].early_clobber_alts |= (alternative_mask) 1 << j;
     825                 :   20607700 :         static_data->operand[i].is_address |= op_alt->is_address;
     826                 :            :       }
     827                 :    1971980 : }
     828                 :            : 
     829                 :            : /* Recursively process X and collect info about registers, which are
     830                 :            :    not the insn operands, in X with TYPE (in/out/inout) and flag that
     831                 :            :    it is early clobbered in the insn (EARLY_CLOBBER) and add the info
     832                 :            :    to LIST.  X is a part of insn given by DATA.  Return the result
     833                 :            :    list.  */
     834                 :            : static struct lra_insn_reg *
     835                 :  253904000 : collect_non_operand_hard_regs (rtx_insn *insn, rtx *x,
     836                 :            :                                lra_insn_recog_data_t data,
     837                 :            :                                struct lra_insn_reg *list,
     838                 :            :                                enum op_type type, bool early_clobber)
     839                 :            : {
     840                 :  253904000 :   int i, j, regno, last;
     841                 :  253904000 :   bool subreg_p;
     842                 :  253904000 :   machine_mode mode;
     843                 :  253904000 :   struct lra_insn_reg *curr;
     844                 :  253904000 :   rtx op = *x;
     845                 :  253904000 :   enum rtx_code code = GET_CODE (op);
     846                 :  253904000 :   const char *fmt = GET_RTX_FORMAT (code);
     847                 :            : 
     848                 :  645705000 :   for (i = 0; i < data->insn_static_data->n_operands; i++)
     849                 :  508091000 :     if (! data->insn_static_data->operand[i].is_operator
     850                 :  474630000 :         && x == data->operand_loc[i])
     851                 :            :       /* It is an operand loc. Stop here.  */
     852                 :            :       return list;
     853                 :  144290000 :   for (i = 0; i < data->insn_static_data->n_dups; i++)
     854                 :    7368480 :     if (x == data->dup_loc[i])
     855                 :            :       /* It is a dup loc. Stop here.  */
     856                 :            :       return list;
     857                 :  136921000 :   mode = GET_MODE (op);
     858                 :  136921000 :   subreg_p = false;
     859                 :  136921000 :   if (code == SUBREG)
     860                 :            :     {
     861                 :        705 :       mode = wider_subreg_mode (op);
     862                 :        705 :       if (read_modify_subreg_p (op))
     863                 :          0 :         subreg_p = true;
     864                 :        705 :       op = SUBREG_REG (op);
     865                 :        705 :       code = GET_CODE (op);
     866                 :            :     }
     867                 :  136921000 :   if (REG_P (op))
     868                 :            :     {
     869                 :   15229800 :       if ((regno = REGNO (op)) >= FIRST_PSEUDO_REGISTER)
     870                 :            :         return list;
     871                 :            :       /* Process all regs even unallocatable ones as we need info
     872                 :            :          about all regs for rematerialization pass.  */
     873                 :   30459500 :       for (last = end_hard_regno (mode, regno); regno < last; regno++)
     874                 :            :         {
     875                 :   15773600 :           for (curr = list; curr != NULL; curr = curr->next)
     876                 :     660048 :             if (curr->regno == regno && curr->subreg_p == subreg_p
     877                 :     127129 :                 && curr->biggest_mode == mode)
     878                 :            :               {
     879                 :     116185 :                 if (curr->type != type)
     880                 :     116185 :                   curr->type = OP_INOUT;
     881                 :     116185 :                 if (early_clobber)
     882                 :          0 :                   curr->early_clobber_alts = ALL_ALTERNATIVES;
     883                 :            :                 break;
     884                 :            :               }
     885                 :   15229700 :           if (curr == NULL)
     886                 :            :             {
     887                 :            :               /* This is a new hard regno or the info cannot be
     888                 :            :                  integrated into the found structure.    */
     889                 :            : #ifdef STACK_REGS
     890                 :   15113600 :               early_clobber
     891                 :   23733000 :                 = (early_clobber
     892                 :            :                    /* This clobber is to inform popping floating
     893                 :            :                       point stack only.  */
     894                 :   15113600 :                    && ! (FIRST_STACK_REG <= regno
     895                 :            :                          && regno <= LAST_STACK_REG));
     896                 :            : #endif
     897                 :   15113600 :               list = new_insn_reg (data->insn, regno, type, mode, subreg_p,
     898                 :            :                                    early_clobber ? ALL_ALTERNATIVES : 0, list);
     899                 :            :             }
     900                 :            :         }
     901                 :   15229700 :       return list;
     902                 :            :     }
     903                 :  121691000 :   switch (code)
     904                 :            :     {
     905                 :   56857500 :     case SET:
     906                 :   56857500 :       list = collect_non_operand_hard_regs (insn, &SET_DEST (op), data,
     907                 :            :                                             list, OP_OUT, false);
     908                 :   56857500 :       list = collect_non_operand_hard_regs (insn, &SET_SRC (op), data,
     909                 :            :                                             list, OP_IN, false);
     910                 :   56857500 :       break;
     911                 :    6731110 :     case CLOBBER:
     912                 :            :       /* We treat clobber of non-operand hard registers as early clobber.  */
     913                 :    6731110 :       list = collect_non_operand_hard_regs (insn, &XEXP (op, 0), data,
     914                 :            :                                             list, OP_OUT, true);
     915                 :    6731110 :       break;
     916                 :          0 :     case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
     917                 :          0 :       list = collect_non_operand_hard_regs (insn, &XEXP (op, 0), data,
     918                 :            :                                             list, OP_INOUT, false);
     919                 :          0 :       break;
     920                 :          0 :     case PRE_MODIFY: case POST_MODIFY:
     921                 :          0 :       list = collect_non_operand_hard_regs (insn, &XEXP (op, 0), data,
     922                 :            :                                             list, OP_INOUT, false);
     923                 :          0 :       list = collect_non_operand_hard_regs (insn, &XEXP (op, 1), data,
     924                 :            :                                             list, OP_IN, false);
     925                 :          0 :       break;
     926                 :   58102600 :     default:
     927                 :   58102600 :       fmt = GET_RTX_FORMAT (code);
     928                 :  141077000 :       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
     929                 :            :         {
     930                 :   82974100 :           if (fmt[i] == 'e')
     931                 :   57905600 :             list = collect_non_operand_hard_regs (insn, &XEXP (op, i), data,
     932                 :            :                                                   list, OP_IN, false);
     933                 :   25068600 :           else if (fmt[i] == 'E')
     934                 :   24541400 :             for (j = XVECLEN (op, i) - 1; j >= 0; j--)
     935                 :   16242000 :               list = collect_non_operand_hard_regs (insn, &XVECEXP (op, i, j),
     936                 :            :                                                     data, list, OP_IN, false);
     937                 :            :         }
     938                 :            :     }
     939                 :            :   return list;
     940                 :            : }
     941                 :            : 
     942                 :            : /* Set up and return info about INSN.  Set up the info if it is not set up
     943                 :            :    yet.  */
     944                 :            : lra_insn_recog_data_t
     945                 :   87899800 : lra_set_insn_recog_data (rtx_insn *insn)
     946                 :            : {
     947                 :   87899800 :   lra_insn_recog_data_t data;
     948                 :   87899800 :   int i, n, icode;
     949                 :   87899800 :   rtx **locs;
     950                 :   87899800 :   unsigned int uid = INSN_UID (insn);
     951                 :   87899800 :   struct lra_static_insn_data *insn_static_data;
     952                 :            : 
     953                 :   87899800 :   check_and_expand_insn_recog_data (uid);
     954                 :   87899800 :   if (DEBUG_INSN_P (insn))
     955                 :            :     icode = -1;
     956                 :            :   else
     957                 :            :     {
     958                 :   59860700 :       icode = INSN_CODE (insn);
     959                 :   59860700 :       if (icode < 0)
     960                 :            :         /* It might be a new simple insn which is not recognized yet.  */
     961                 :    6439520 :         INSN_CODE (insn) = icode = recog_memoized (insn);
     962                 :            :     }
     963                 :   87899800 :   data = lra_insn_recog_data_pool.allocate ();
     964                 :   87899800 :   lra_insn_recog_data[uid] = data;
     965                 :   87899800 :   data->insn = insn;
     966                 :   87899800 :   data->used_insn_alternative = LRA_UNKNOWN_ALT;
     967                 :   87899800 :   data->icode = icode;
     968                 :   87899800 :   data->regs = NULL;
     969                 :   87899800 :   if (DEBUG_INSN_P (insn))
     970                 :            :     {
     971                 :   28039100 :       data->dup_loc = NULL;
     972                 :   28039100 :       data->arg_hard_regs = NULL;
     973                 :   28039100 :       data->preferred_alternatives = ALL_ALTERNATIVES;
     974                 :   28039100 :       if (DEBUG_BIND_INSN_P (insn))
     975                 :            :         {
     976                 :   21834100 :           data->insn_static_data = &debug_bind_static_data;
     977                 :   21834100 :           data->operand_loc = XNEWVEC (rtx *, 1);
     978                 :   21834100 :           data->operand_loc[0] = &INSN_VAR_LOCATION_LOC (insn);
     979                 :            :         }
     980                 :    6205020 :       else if (DEBUG_MARKER_INSN_P (insn))
     981                 :            :         {
     982                 :    6205020 :           data->insn_static_data = &debug_marker_static_data;
     983                 :    6205020 :           data->operand_loc = NULL;
     984                 :            :         }
     985                 :   28039100 :       return data;
     986                 :            :     }
     987                 :   59860700 :   if (icode < 0)
     988                 :            :     {
     989                 :     639514 :       int nop, nalt;
     990                 :     639514 :       machine_mode operand_mode[MAX_RECOG_OPERANDS];
     991                 :     639514 :       const char *constraints[MAX_RECOG_OPERANDS];
     992                 :            : 
     993                 :     639514 :       nop = asm_noperands (PATTERN (insn));
     994                 :     639514 :       data->operand_loc = data->dup_loc = NULL;
     995                 :     639514 :       nalt = 1;
     996                 :     639514 :       if (nop < 0)
     997                 :            :         {
     998                 :            :           /* It is a special insn like USE or CLOBBER.  We should
     999                 :            :              recognize any regular insn otherwise LRA can do nothing
    1000                 :            :              with this insn.  */
    1001                 :     551775 :           gcc_assert (GET_CODE (PATTERN (insn)) == USE
    1002                 :            :                       || GET_CODE (PATTERN (insn)) == CLOBBER
    1003                 :            :                       || GET_CODE (PATTERN (insn)) == ASM_INPUT);
    1004                 :    1103550 :           data->insn_static_data = insn_static_data
    1005                 :     551775 :             = get_static_insn_data (-1, 0, 0, nalt);
    1006                 :            :         }
    1007                 :            :       else
    1008                 :            :         {
    1009                 :            :           /* expand_asm_operands makes sure there aren't too many
    1010                 :            :              operands.  */
    1011                 :      87739 :           lra_assert (nop <= MAX_RECOG_OPERANDS);
    1012                 :      87739 :           if (nop != 0)
    1013                 :      34685 :             data->operand_loc = XNEWVEC (rtx *, nop);
    1014                 :            :           /* Now get the operand values and constraints out of the
    1015                 :            :              insn.  */
    1016                 :      87739 :           decode_asm_operands (PATTERN (insn), NULL,
    1017                 :            :                                data->operand_loc,
    1018                 :            :                                constraints, operand_mode, NULL);
    1019                 :      87739 :           if (nop > 0)
    1020                 :      97836 :             for (const char *p =constraints[0]; *p; p++)
    1021                 :      63151 :               nalt += *p == ',';
    1022                 :     175478 :           data->insn_static_data = insn_static_data
    1023                 :      87739 :             = get_static_insn_data (-1, nop, 0, nalt);
    1024                 :     202536 :           for (i = 0; i < nop; i++)
    1025                 :            :             {
    1026                 :     114797 :               insn_static_data->operand[i].mode = operand_mode[i];
    1027                 :     114797 :               insn_static_data->operand[i].constraint = constraints[i];
    1028                 :     114797 :               insn_static_data->operand[i].strict_low = false;
    1029                 :     114797 :               insn_static_data->operand[i].is_operator = false;
    1030                 :     114797 :               insn_static_data->operand[i].is_address = false;
    1031                 :            :             }
    1032                 :            :         }
    1033                 :     754311 :       for (i = 0; i < insn_static_data->n_operands; i++)
    1034                 :     114797 :         insn_static_data->operand[i].type
    1035                 :     159081 :           = (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
    1036                 :            :              : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
    1037                 :            :              : OP_IN);
    1038                 :     639514 :       data->preferred_alternatives = ALL_ALTERNATIVES;
    1039                 :     639514 :       if (nop > 0)
    1040                 :            :         {
    1041                 :      34685 :           operand_alternative *op_alt = XCNEWVEC (operand_alternative,
    1042                 :            :                                                   nalt * nop);
    1043                 :      34685 :           preprocess_constraints (nop, nalt, constraints, op_alt,
    1044                 :            :                                   data->operand_loc);
    1045                 :      34685 :           setup_operand_alternative (data, op_alt);
    1046                 :            :         }
    1047                 :            :     }
    1048                 :            :   else
    1049                 :            :     {
    1050                 :   59221200 :       insn_extract (insn);
    1051                 :  118442000 :       data->insn_static_data = insn_static_data
    1052                 :  118442000 :         = get_static_insn_data (icode, insn_data[icode].n_operands,
    1053                 :   59221200 :                                 insn_data[icode].n_dups,
    1054                 :   59221200 :                                 insn_data[icode].n_alternatives);
    1055                 :   59221200 :       n = insn_static_data->n_operands;
    1056                 :   59221200 :       if (n == 0)
    1057                 :            :         locs = NULL;
    1058                 :            :       else
    1059                 :            :         {
    1060                 :   58858200 :           locs = XNEWVEC (rtx *, n);
    1061                 :   58858200 :           memcpy (locs, recog_data.operand_loc, n * sizeof (rtx *));
    1062                 :            :         }
    1063                 :   59221200 :       data->operand_loc = locs;
    1064                 :   59221200 :       n = insn_static_data->n_dups;
    1065                 :   59221200 :       if (n == 0)
    1066                 :            :         locs = NULL;
    1067                 :            :       else
    1068                 :            :         {
    1069                 :     368920 :           locs = XNEWVEC (rtx *, n);
    1070                 :     368920 :           memcpy (locs, recog_data.dup_loc, n * sizeof (rtx *));
    1071                 :            :         }
    1072                 :   59221200 :       data->dup_loc = locs;
    1073                 :   59221200 :       data->preferred_alternatives = get_preferred_alternatives (insn);
    1074                 :   59221200 :       const operand_alternative *op_alt = preprocess_insn_constraints (icode);
    1075                 :   59221200 :       if (!insn_static_data->operand_alternative)
    1076                 :    1937290 :         setup_operand_alternative (data, op_alt);
    1077                 :   57283900 :       else if (op_alt != insn_static_data->operand_alternative)
    1078                 :      27622 :         insn_static_data->operand_alternative = op_alt;
    1079                 :            :     }
    1080                 :   59860700 :   if (GET_CODE (PATTERN (insn)) == CLOBBER || GET_CODE (PATTERN (insn)) == USE)
    1081                 :     549944 :     insn_static_data->hard_regs = NULL;
    1082                 :            :   else
    1083                 :   59310700 :     insn_static_data->hard_regs
    1084                 :   59310700 :       = collect_non_operand_hard_regs (insn, &PATTERN (insn), data,
    1085                 :            :                                        NULL, OP_IN, false);
    1086                 :   59860700 :   data->arg_hard_regs = NULL;
    1087                 :   59860700 :   if (CALL_P (insn))
    1088                 :            :     {
    1089                 :    3971300 :       bool use_p;
    1090                 :    3971300 :       rtx link;
    1091                 :    3971300 :       int n_hard_regs, regno, arg_hard_regs[FIRST_PSEUDO_REGISTER];
    1092                 :            : 
    1093                 :    3971300 :       n_hard_regs = 0;
    1094                 :            :       /* Finding implicit hard register usage.  We believe it will be
    1095                 :            :          not changed whatever transformations are used.  Call insns
    1096                 :            :          are such example.  */
    1097                 :    3971300 :       for (link = CALL_INSN_FUNCTION_USAGE (insn);
    1098                 :   10715400 :            link != NULL_RTX;
    1099                 :    6744140 :            link = XEXP (link, 1))
    1100                 :    6744140 :         if (((use_p = GET_CODE (XEXP (link, 0)) == USE)
    1101                 :     233285 :              || GET_CODE (XEXP (link, 0)) == CLOBBER)
    1102                 :    6914760 :             && REG_P (XEXP (XEXP (link, 0), 0)))
    1103                 :            :           {
    1104                 :    6657060 :             regno = REGNO (XEXP (XEXP (link, 0), 0));
    1105                 :    6657060 :             lra_assert (regno < FIRST_PSEUDO_REGISTER);
    1106                 :            :             /* It is an argument register.  */
    1107                 :   13351900 :             for (i = REG_NREGS (XEXP (XEXP (link, 0), 0)) - 1; i >= 0; i--)
    1108                 :   13389800 :               arg_hard_regs[n_hard_regs++]
    1109                 :    6865500 :                 = regno + i + (use_p ? 0 : FIRST_PSEUDO_REGISTER);
    1110                 :            :           }
    1111                 :            : 
    1112                 :    3971300 :       if (n_hard_regs != 0)
    1113                 :            :         {
    1114                 :    2982750 :           arg_hard_regs[n_hard_regs++] = -1;
    1115                 :    2982750 :           data->arg_hard_regs = XNEWVEC (int, n_hard_regs);
    1116                 :    2982750 :           memcpy (data->arg_hard_regs, arg_hard_regs,
    1117                 :            :                   sizeof (int) * n_hard_regs);
    1118                 :            :         }
    1119                 :            :     }
    1120                 :            :   /* Some output operand can be recognized only from the context not
    1121                 :            :      from the constraints which are empty in this case.  Call insn may
    1122                 :            :      contain a hard register in set destination with empty constraint
    1123                 :            :      and extract_insn treats them as an input.  */
    1124                 :  186029000 :   for (i = 0; i < insn_static_data->n_operands; i++)
    1125                 :            :     {
    1126                 :  126168000 :       int j;
    1127                 :  126168000 :       rtx pat, set;
    1128                 :  126168000 :       struct lra_operand_data *operand = &insn_static_data->operand[i];
    1129                 :            : 
    1130                 :            :       /* ??? Should we treat 'X' the same way.  It looks to me that
    1131                 :            :          'X' means anything and empty constraint means we do not
    1132                 :            :          care.  */
    1133                 :  126168000 :       if (operand->type != OP_IN || *operand->constraint != '\0'
    1134                 :   15757100 :           || operand->is_operator)
    1135                 :  114922000 :         continue;
    1136                 :   11246400 :       pat = PATTERN (insn);
    1137                 :   11246400 :       if (GET_CODE (pat) == SET)
    1138                 :            :         {
    1139                 :    8664030 :           if (data->operand_loc[i] != &SET_DEST (pat))
    1140                 :    8582490 :             continue;
    1141                 :            :         }
    1142                 :    2582320 :       else if (GET_CODE (pat) == PARALLEL)
    1143                 :            :         {
    1144                 :     654148 :           for (j = XVECLEN (pat, 0) - 1; j >= 0; j--)
    1145                 :            :             {
    1146                 :     447986 :               set = XVECEXP (PATTERN (insn), 0, j);
    1147                 :     447986 :               if (GET_CODE (set) == SET
    1148                 :     275738 :                   && &SET_DEST (set) == data->operand_loc[i])
    1149                 :            :                 break;
    1150                 :            :             }
    1151                 :     206296 :           if (j < 0)
    1152                 :     206162 :             continue;
    1153                 :            :         }
    1154                 :            :       else
    1155                 :    2376020 :         continue;
    1156                 :      81670 :       operand->type = OP_OUT;
    1157                 :            :     }
    1158                 :            :   return data;
    1159                 :            : }
    1160                 :            : 
    1161                 :            : /* Return info about insn give by UID.  The info should be already set
    1162                 :            :    up.  */
    1163                 :            : static lra_insn_recog_data_t
    1164                 :      48102 : get_insn_recog_data_by_uid (int uid)
    1165                 :            : {
    1166                 :      48102 :   lra_insn_recog_data_t data;
    1167                 :            : 
    1168                 :      48102 :   data = lra_insn_recog_data[uid];
    1169                 :          0 :   lra_assert (data != NULL);
    1170                 :      48102 :   return data;
    1171                 :            : }
    1172                 :            : 
    1173                 :            : /* Invalidate all info about insn given by its UID.  */
    1174                 :            : static void
    1175                 :    9328260 : invalidate_insn_recog_data (int uid)
    1176                 :            : {
    1177                 :    9328260 :   lra_insn_recog_data_t data;
    1178                 :            : 
    1179                 :    9328260 :   data = lra_insn_recog_data[uid];
    1180                 :    9328260 :   lra_assert (data != NULL);
    1181                 :    9328260 :   free_insn_recog_data (data);
    1182                 :    9328260 :   lra_insn_recog_data[uid] = NULL;
    1183                 :    9328260 : }
    1184                 :            : 
    1185                 :            : /* Update all the insn info about INSN.  It is usually called when
    1186                 :            :    something in the insn was changed.  Return the updated info.  */
    1187                 :            : lra_insn_recog_data_t
    1188                 :   27247100 : lra_update_insn_recog_data (rtx_insn *insn)
    1189                 :            : {
    1190                 :   27247100 :   lra_insn_recog_data_t data;
    1191                 :   27247100 :   int n;
    1192                 :   27247100 :   unsigned int uid = INSN_UID (insn);
    1193                 :   27247100 :   struct lra_static_insn_data *insn_static_data;
    1194                 :   27247100 :   poly_int64 sp_offset = 0;
    1195                 :            : 
    1196                 :   27247100 :   check_and_expand_insn_recog_data (uid);
    1197                 :   27247100 :   if ((data = lra_insn_recog_data[uid]) != NULL
    1198                 :   27247100 :       && data->icode != INSN_CODE (insn))
    1199                 :            :     {
    1200                 :     109032 :       sp_offset = data->sp_offset;
    1201                 :     109032 :       invalidate_insn_data_regno_info (data, insn, get_insn_freq (insn));
    1202                 :     109032 :       invalidate_insn_recog_data (uid);
    1203                 :     109032 :       data = NULL;
    1204                 :            :     }
    1205                 :   27247100 :   if (data == NULL)
    1206                 :            :     {
    1207                 :     109032 :       data = lra_get_insn_recog_data (insn);
    1208                 :            :       /* Initiate or restore SP offset.  */
    1209                 :     109032 :       data->sp_offset = sp_offset;
    1210                 :     109032 :       return data;
    1211                 :            :     }
    1212                 :   27138000 :   insn_static_data = data->insn_static_data;
    1213                 :   27138000 :   data->used_insn_alternative = LRA_UNKNOWN_ALT;
    1214                 :   27138000 :   if (DEBUG_INSN_P (insn))
    1215                 :            :     return data;
    1216                 :   22879200 :   if (data->icode < 0)
    1217                 :            :     {
    1218                 :       2750 :       int nop;
    1219                 :       2750 :       machine_mode operand_mode[MAX_RECOG_OPERANDS];
    1220                 :       2750 :       const char *constraints[MAX_RECOG_OPERANDS];
    1221                 :            : 
    1222                 :       2750 :       nop = asm_noperands (PATTERN (insn));
    1223                 :       2750 :       if (nop >= 0)
    1224                 :            :         {
    1225                 :       2750 :           lra_assert (nop == data->insn_static_data->n_operands);
    1226                 :            :           /* Now get the operand values and constraints out of the
    1227                 :            :              insn.  */
    1228                 :       2750 :           decode_asm_operands (PATTERN (insn), NULL,
    1229                 :            :                                data->operand_loc,
    1230                 :            :                                constraints, operand_mode, NULL);
    1231                 :            : 
    1232                 :       2750 :           if (flag_checking)
    1233                 :      10273 :             for (int i = 0; i < nop; i++)
    1234                 :       7523 :               lra_assert
    1235                 :            :                 (insn_static_data->operand[i].mode == operand_mode[i]
    1236                 :            :                  && insn_static_data->operand[i].constraint == constraints[i]
    1237                 :            :                  && ! insn_static_data->operand[i].is_operator);
    1238                 :            :         }
    1239                 :            : 
    1240                 :       2750 :       if (flag_checking)
    1241                 :      10273 :         for (int i = 0; i < insn_static_data->n_operands; i++)
    1242                 :      12959 :           lra_assert
    1243                 :            :             (insn_static_data->operand[i].type
    1244                 :            :              == (insn_static_data->operand[i].constraint[0] == '=' ? OP_OUT
    1245                 :            :                  : insn_static_data->operand[i].constraint[0] == '+' ? OP_INOUT
    1246                 :            :                  : OP_IN));
    1247                 :            :     }
    1248                 :            :   else
    1249                 :            :     {
    1250                 :   22876500 :       insn_extract (insn);
    1251                 :   22876500 :       n = insn_static_data->n_operands;
    1252                 :   22876500 :       if (n != 0)
    1253                 :   22876500 :         memcpy (data->operand_loc, recog_data.operand_loc, n * sizeof (rtx *));
    1254                 :   22876500 :       n = insn_static_data->n_dups;
    1255                 :   22876500 :       if (n != 0)
    1256                 :      34783 :         memcpy (data->dup_loc, recog_data.dup_loc, n * sizeof (rtx *));
    1257                 :   22876500 :       lra_assert (check_bool_attrs (insn));
    1258                 :            :     }
    1259                 :            :   return data;
    1260                 :            : }
    1261                 :            : 
    1262                 :            : /* Set up that INSN is using alternative ALT now.  */
    1263                 :            : void
    1264                 :   74405900 : lra_set_used_insn_alternative (rtx_insn *insn, int alt)
    1265                 :            : {
    1266                 :   74405900 :   lra_insn_recog_data_t data;
    1267                 :            : 
    1268                 :   74405900 :   data = lra_get_insn_recog_data (insn);
    1269                 :   74405900 :   data->used_insn_alternative = alt;
    1270                 :   74405900 : }
    1271                 :            : 
    1272                 :            : /* Set up that insn with UID is using alternative ALT now.  The insn
    1273                 :            :    info should be already set up.  */
    1274                 :            : void
    1275                 :    5601460 : lra_set_used_insn_alternative_by_uid (int uid, int alt)
    1276                 :            : {
    1277                 :    5601460 :   lra_insn_recog_data_t data;
    1278                 :            : 
    1279                 :    5601460 :   check_and_expand_insn_recog_data (uid);
    1280                 :    5601460 :   data = lra_insn_recog_data[uid];
    1281                 :    5601460 :   lra_assert (data != NULL);
    1282                 :    5601460 :   data->used_insn_alternative = alt;
    1283                 :    5601460 : }
    1284                 :            : 
    1285                 :            : 
    1286                 :            : 
    1287                 :            : /* This page contains code dealing with common register info and
    1288                 :            :    pseudo copies.  */
    1289                 :            : 
    1290                 :            : /* The size of the following array.  */
    1291                 :            : static int reg_info_size;
    1292                 :            : /* Common info about each register.  */
    1293                 :            : class lra_reg *lra_reg_info;
    1294                 :            : 
    1295                 :            : HARD_REG_SET hard_regs_spilled_into;
    1296                 :            : 
    1297                 :            : /* Last register value.  */
    1298                 :            : static int last_reg_value;
    1299                 :            : 
    1300                 :            : /* Return new register value.  */
    1301                 :            : static int
    1302                 :  170735000 : get_new_reg_value (void)
    1303                 :            : {
    1304                 :  170735000 :   return ++last_reg_value;
    1305                 :            : }
    1306                 :            : 
    1307                 :            : /* Vec referring to pseudo copies.  */
    1308                 :            : static vec<lra_copy_t> copy_vec;
    1309                 :            : 
    1310                 :            : /* Initialize I-th element of lra_reg_info.  */
    1311                 :            : static inline void
    1312                 :  170734000 : initialize_lra_reg_info_element (int i)
    1313                 :            : {
    1314                 :  170734000 :   bitmap_initialize (&lra_reg_info[i].insn_bitmap, &reg_obstack);
    1315                 :            : #ifdef STACK_REGS
    1316                 :  170734000 :   lra_reg_info[i].no_stack_p = false;
    1317                 :            : #endif
    1318                 :  170734000 :   CLEAR_HARD_REG_SET (lra_reg_info[i].conflict_hard_regs);
    1319                 :  170734000 :   lra_reg_info[i].preferred_hard_regno1 = -1;
    1320                 :  170734000 :   lra_reg_info[i].preferred_hard_regno2 = -1;
    1321                 :  170734000 :   lra_reg_info[i].preferred_hard_regno_profit1 = 0;
    1322                 :  170734000 :   lra_reg_info[i].preferred_hard_regno_profit2 = 0;
    1323                 :  170734000 :   lra_reg_info[i].biggest_mode = VOIDmode;
    1324                 :  170734000 :   lra_reg_info[i].live_ranges = NULL;
    1325                 :  170734000 :   lra_reg_info[i].nrefs = lra_reg_info[i].freq = 0;
    1326                 :  170734000 :   lra_reg_info[i].last_reload = 0;
    1327                 :  170734000 :   lra_reg_info[i].restore_rtx = NULL_RTX;
    1328                 :  170734000 :   lra_reg_info[i].val = get_new_reg_value ();
    1329                 :  170734000 :   lra_reg_info[i].offset = 0;
    1330                 :  170734000 :   lra_reg_info[i].copies = NULL;
    1331                 :  170734000 : }
    1332                 :            : 
    1333                 :            : /* Initialize common reg info and copies.  */
    1334                 :            : static void
    1335                 :     944096 : init_reg_info (void)
    1336                 :            : {
    1337                 :     944096 :   int i;
    1338                 :            : 
    1339                 :     944096 :   last_reg_value = 0;
    1340                 :     944096 :   reg_info_size = max_reg_num () * 3 / 2 + 1;
    1341                 :     944096 :   lra_reg_info = XNEWVEC (class lra_reg, reg_info_size);
    1342                 :  170487000 :   for (i = 0; i < reg_info_size; i++)
    1343                 :  169543000 :     initialize_lra_reg_info_element (i);
    1344                 :     944096 :   copy_vec.truncate (0);
    1345                 :     944096 :   CLEAR_HARD_REG_SET (hard_regs_spilled_into);
    1346                 :     944096 : }
    1347                 :            : 
    1348                 :            : 
    1349                 :            : /* Finish common reg info and copies.  */
    1350                 :            : static void
    1351                 :     944096 : finish_reg_info (void)
    1352                 :            : {
    1353                 :     944096 :   int i;
    1354                 :            : 
    1355                 :  171678000 :   for (i = 0; i < reg_info_size; i++)
    1356                 :  170734000 :     bitmap_clear (&lra_reg_info[i].insn_bitmap);
    1357                 :     944096 :   free (lra_reg_info);
    1358                 :     944096 :   reg_info_size = 0;
    1359                 :     944096 : }
    1360                 :            : 
    1361                 :            : /* Expand common reg info if it is necessary.  */
    1362                 :            : static void
    1363                 :  166324000 : expand_reg_info (void)
    1364                 :            : {
    1365                 :  166324000 :   int i, old = reg_info_size;
    1366                 :            : 
    1367                 :  166324000 :   if (reg_info_size > max_reg_num ())
    1368                 :            :     return;
    1369                 :       1488 :   reg_info_size = max_reg_num () * 3 / 2 + 1;
    1370                 :       1488 :   lra_reg_info = XRESIZEVEC (class lra_reg, lra_reg_info, reg_info_size);
    1371                 :    1192110 :   for (i = old; i < reg_info_size; i++)
    1372                 :    1190620 :     initialize_lra_reg_info_element (i);
    1373                 :            : }
    1374                 :            : 
    1375                 :            : /* Free all copies.  */
    1376                 :            : void
    1377                 :    1134610 : lra_free_copies (void)
    1378                 :            : {
    1379                 :    4800120 :   lra_copy_t cp;
    1380                 :            : 
    1381                 :    4109130 :   while (copy_vec.length () != 0)
    1382                 :            :     {
    1383                 :    3665500 :       cp = copy_vec.pop ();
    1384                 :    3665500 :       lra_reg_info[cp->regno1].copies = lra_reg_info[cp->regno2].copies = NULL;
    1385                 :    8465620 :       lra_copy_pool.remove (cp);
    1386                 :            :     }
    1387                 :    1134610 : }
    1388                 :            : 
    1389                 :            : /* Create copy of two pseudos REGNO1 and REGNO2.  The copy execution
    1390                 :            :    frequency is FREQ.  */
    1391                 :            : void
    1392                 :    4349560 : lra_create_copy (int regno1, int regno2, int freq)
    1393                 :            : {
    1394                 :    4349560 :   bool regno1_dest_p;
    1395                 :    4349560 :   lra_copy_t cp;
    1396                 :            : 
    1397                 :    4349560 :   lra_assert (regno1 != regno2);
    1398                 :    4349560 :   regno1_dest_p = true;
    1399                 :    4349560 :   if (regno1 > regno2)
    1400                 :            :     {
    1401                 :     742531 :       std::swap (regno1, regno2);
    1402                 :     742531 :       regno1_dest_p = false;
    1403                 :            :     }
    1404                 :    4349560 :   cp = lra_copy_pool.allocate ();
    1405                 :    4349560 :   copy_vec.safe_push (cp);
    1406                 :    4349560 :   cp->regno1_dest_p = regno1_dest_p;
    1407                 :    4349560 :   cp->freq = freq;
    1408                 :    4349560 :   cp->regno1 = regno1;
    1409                 :    4349560 :   cp->regno2 = regno2;
    1410                 :    4349560 :   cp->regno1_next = lra_reg_info[regno1].copies;
    1411                 :    4349560 :   lra_reg_info[regno1].copies = cp;
    1412                 :    4349560 :   cp->regno2_next = lra_reg_info[regno2].copies;
    1413                 :    4349560 :   lra_reg_info[regno2].copies = cp;
    1414                 :    4349560 :   if (lra_dump_file != NULL)
    1415                 :         70 :     fprintf (lra_dump_file, "         Creating copy r%d%sr%d@%d\n",
    1416                 :            :              regno1, regno1_dest_p ? "<-" : "->", regno2, freq);
    1417                 :    4349560 : }
    1418                 :            : 
    1419                 :            : /* Return N-th (0, 1, ...) copy.  If there is no copy, return
    1420                 :            :    NULL.  */
    1421                 :            : lra_copy_t
    1422                 :    3003780 : lra_get_copy (int n)
    1423                 :            : {
    1424                 :    5355960 :   if (n >= (int) copy_vec.length ())
    1425                 :            :     return NULL;
    1426                 :    2018910 :   return copy_vec[n];
    1427                 :            : }
    1428                 :            : 
    1429                 :            : 
    1430                 :            : 
    1431                 :            : /* This page contains code dealing with info about registers in
    1432                 :            :    insns.  */
    1433                 :            : 
    1434                 :            : /* Process X of INSN recursively and add info (operand type is given
    1435                 :            :    by TYPE) about registers in X to the insn DATA.  If X can be early
    1436                 :            :    clobbered, alternatives in which it can be early clobbered are given
    1437                 :            :    by EARLY_CLOBBER_ALTS.  */
    1438                 :            : static void
    1439                 :  339430000 : add_regs_to_insn_regno_info (lra_insn_recog_data_t data, rtx x,
    1440                 :            :                              rtx_insn *insn, enum op_type type,
    1441                 :            :                              alternative_mask early_clobber_alts)
    1442                 :            : {
    1443                 :  352978000 :   int i, j, regno;
    1444                 :  352978000 :   bool subreg_p;
    1445                 :  352978000 :   machine_mode mode;
    1446                 :  352978000 :   const char *fmt;
    1447                 :  352978000 :   enum rtx_code code;
    1448                 :  352978000 :   struct lra_insn_reg *curr;
    1449                 :            : 
    1450                 :  352978000 :   code = GET_CODE (x);
    1451                 :  352978000 :   mode = GET_MODE (x);
    1452                 :  352978000 :   subreg_p = false;
    1453                 :  352978000 :   if (GET_CODE (x) == SUBREG)
    1454                 :            :     {
    1455                 :    2399370 :       mode = wider_subreg_mode (x);
    1456                 :    2399370 :       if (read_modify_subreg_p (x))
    1457                 :     920993 :         subreg_p = true;
    1458                 :    2399370 :       x = SUBREG_REG (x);
    1459                 :    2399370 :       code = GET_CODE (x);
    1460                 :            :     }
    1461                 :  352978000 :   if (REG_P (x))
    1462                 :            :     {
    1463                 :  160129000 :       regno = REGNO (x);
    1464                 :            :       /* Process all regs even unallocatable ones as we need info about
    1465                 :            :          all regs for rematerialization pass.  */
    1466                 :  160129000 :       expand_reg_info ();
    1467                 :  160129000 :       if (bitmap_set_bit (&lra_reg_info[regno].insn_bitmap, INSN_UID (insn)))
    1468                 :            :         {
    1469                 :  154452000 :           data->regs = new_insn_reg (data->insn, regno, type, mode, subreg_p,
    1470                 :            :                                      early_clobber_alts, data->regs);
    1471                 :  154452000 :           return;
    1472                 :            :         }
    1473                 :            :       else
    1474                 :            :         {
    1475                 :    6793320 :           for (curr = data->regs; curr != NULL; curr = curr->next)
    1476                 :    6793320 :             if (curr->regno == regno)
    1477                 :            :               {
    1478                 :    5677340 :                 if (curr->subreg_p != subreg_p || curr->biggest_mode != mode)
    1479                 :            :                   /* The info cannot be integrated into the found
    1480                 :            :                      structure.  */
    1481                 :      52868 :                   data->regs = new_insn_reg (data->insn, regno, type, mode,
    1482                 :            :                                              subreg_p, early_clobber_alts,
    1483                 :            :                                              data->regs);
    1484                 :            :                 else
    1485                 :            :                   {
    1486                 :    5624480 :                     if (curr->type != type)
    1487                 :    4056290 :                       curr->type = OP_INOUT;
    1488                 :    5624480 :                     curr->early_clobber_alts |= early_clobber_alts;
    1489                 :            :                   }
    1490                 :    5677340 :                 return;
    1491                 :            :               }
    1492                 :          0 :           gcc_unreachable ();
    1493                 :            :         }
    1494                 :            :     }
    1495                 :            : 
    1496                 :  192849000 :   switch (code)
    1497                 :            :     {
    1498                 :       1208 :     case SET:
    1499                 :       1208 :       add_regs_to_insn_regno_info (data, SET_DEST (x), insn, OP_OUT, 0);
    1500                 :       1208 :       add_regs_to_insn_regno_info (data, SET_SRC (x), insn, OP_IN, 0);
    1501                 :       1208 :       break;
    1502                 :   10628500 :     case CLOBBER:
    1503                 :            :       /* We treat clobber of non-operand hard registers as early
    1504                 :            :          clobber.  */
    1505                 :   10628500 :       add_regs_to_insn_regno_info (data, XEXP (x, 0), insn, OP_OUT,
    1506                 :            :                                    ALL_ALTERNATIVES);
    1507                 :   10628500 :       break;
    1508                 :    2842670 :     case PRE_INC: case PRE_DEC: case POST_INC: case POST_DEC:
    1509                 :    2842670 :       add_regs_to_insn_regno_info (data, XEXP (x, 0), insn, OP_INOUT, 0);
    1510                 :    2842670 :       break;
    1511                 :      75134 :     case PRE_MODIFY: case POST_MODIFY:
    1512                 :      75134 :       add_regs_to_insn_regno_info (data, XEXP (x, 0), insn, OP_INOUT, 0);
    1513                 :      75134 :       add_regs_to_insn_regno_info (data, XEXP (x, 1), insn, OP_IN, 0);
    1514                 :      75134 :       break;
    1515                 :  179301000 :     default:
    1516                 :  179301000 :       if ((code != PARALLEL && code != EXPR_LIST) || type != OP_OUT)
    1517                 :            :         /* Some targets place small structures in registers for return
    1518                 :            :            values of functions, and those registers are wrapped in
    1519                 :            :            PARALLEL that we may see as the destination of a SET.  Here
    1520                 :            :            is an example:
    1521                 :            : 
    1522                 :            :            (call_insn 13 12 14 2 (set (parallel:BLK [
    1523                 :            :                 (expr_list:REG_DEP_TRUE (reg:DI 0 ax)
    1524                 :            :                     (const_int 0 [0]))
    1525                 :            :                 (expr_list:REG_DEP_TRUE (reg:DI 1 dx)
    1526                 :            :                     (const_int 8 [0x8]))
    1527                 :            :                ])
    1528                 :            :              (call (mem:QI (symbol_ref:DI (...  */
    1529                 :  179278000 :         type = OP_IN;
    1530                 :  179301000 :       fmt = GET_RTX_FORMAT (code);
    1531                 :  484175000 :       for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    1532                 :            :         {
    1533                 :  304874000 :           if (fmt[i] == 'e')
    1534                 :  125577000 :             add_regs_to_insn_regno_info (data, XEXP (x, i), insn, type, 0);
    1535                 :  179297000 :           else if (fmt[i] == 'E')
    1536                 :            :             {
    1537                 :    1263340 :               for (j = XVECLEN (x, i) - 1; j >= 0; j--)
    1538                 :     898514 :                 add_regs_to_insn_regno_info (data, XVECEXP (x, i, j), insn,
    1539                 :            :                                              type, 0);
    1540                 :            :             }
    1541                 :            :         }
    1542                 :            :     }
    1543                 :            : }
    1544                 :            : 
    1545                 :            : /* Return execution frequency of INSN.  */
    1546                 :            : static int
    1547                 :   97251100 : get_insn_freq (rtx_insn *insn)
    1548                 :            : {
    1549                 :   97251100 :   basic_block bb = BLOCK_FOR_INSN (insn);
    1550                 :            : 
    1551                 :   97251100 :   gcc_checking_assert (bb != NULL);
    1552                 :   97251100 :   return REG_FREQ_FROM_BB (bb);
    1553                 :            : }
    1554                 :            : 
    1555                 :            : /* Invalidate all reg info of INSN with DATA and execution frequency
    1556                 :            :    FREQ.  Update common info about the invalidated registers.  */
    1557                 :            : static void
    1558                 :  128886000 : invalidate_insn_data_regno_info (lra_insn_recog_data_t data, rtx_insn *insn,
    1559                 :            :                                  int freq)
    1560                 :            : {
    1561                 :  128886000 :   int uid;
    1562                 :  128886000 :   bool debug_p;
    1563                 :  128886000 :   unsigned int i;
    1564                 :  128886000 :   struct lra_insn_reg *ir, *next_ir;
    1565                 :            : 
    1566                 :  128886000 :   uid = INSN_UID (insn);
    1567                 :  128886000 :   debug_p = DEBUG_INSN_P (insn);
    1568                 :  205277000 :   for (ir = data->regs; ir != NULL; ir = next_ir)
    1569                 :            :     {
    1570                 :   76391200 :       i = ir->regno;
    1571                 :   76391200 :       next_ir = ir->next;
    1572                 :   76391200 :       lra_insn_reg_pool.remove (ir);
    1573                 :   76391200 :       bitmap_clear_bit (&lra_reg_info[i].insn_bitmap, uid);
    1574                 :   76391200 :       if (i >= FIRST_PSEUDO_REGISTER && ! debug_p)
    1575                 :            :         {
    1576                 :   51481400 :           lra_reg_info[i].nrefs--;
    1577                 :   51481400 :           lra_reg_info[i].freq -= freq;
    1578                 :   51481400 :           lra_assert (lra_reg_info[i].nrefs >= 0 && lra_reg_info[i].freq >= 0);
    1579                 :            :         }
    1580                 :            :     }
    1581                 :  128886000 :   data->regs = NULL;
    1582                 :  128886000 : }
    1583                 :            : 
    1584                 :            : /* Invalidate all reg info of INSN.  Update common info about the
    1585                 :            :    invalidated registers.  */
    1586                 :            : void
    1587                 :    9219230 : lra_invalidate_insn_regno_info (rtx_insn *insn)
    1588                 :            : {
    1589                 :    9219230 :   invalidate_insn_data_regno_info (lra_get_insn_recog_data (insn), insn,
    1590                 :            :                                    get_insn_freq (insn));
    1591                 :    9219230 : }
    1592                 :            : 
    1593                 :            : /* Update common reg info from reg info of insn given by its DATA and
    1594                 :            :    execution frequency FREQ.  */
    1595                 :            : static void
    1596                 :   87922900 : setup_insn_reg_info (lra_insn_recog_data_t data, int freq)
    1597                 :            : {
    1598                 :   87922900 :   unsigned int i;
    1599                 :   87922900 :   struct lra_insn_reg *ir;
    1600                 :            : 
    1601                 :  233270000 :   for (ir = data->regs; ir != NULL; ir = ir->next)
    1602                 :  145347000 :     if ((i = ir->regno) >= FIRST_PSEUDO_REGISTER)
    1603                 :            :       {
    1604                 :   96978500 :         lra_reg_info[i].nrefs++;
    1605                 :   96978500 :         lra_reg_info[i].freq += freq;
    1606                 :            :       }
    1607                 :          0 : }
    1608                 :            : 
    1609                 :            : /* Set up insn reg info of INSN.  Update common reg info from reg info
    1610                 :            :    of INSN.  */
    1611                 :            : void
    1612                 :  119558000 : lra_update_insn_regno_info (rtx_insn *insn)
    1613                 :            : {
    1614                 :  119558000 :   int i, freq;
    1615                 :  119558000 :   lra_insn_recog_data_t data;
    1616                 :  119558000 :   struct lra_static_insn_data *static_data;
    1617                 :  119558000 :   enum rtx_code code;
    1618                 :  119558000 :   rtx link;
    1619                 :            :   
    1620                 :  119558000 :   if (! INSN_P (insn))
    1621                 :            :     return;
    1622                 :  119558000 :   data = lra_get_insn_recog_data (insn);
    1623                 :  119558000 :   static_data = data->insn_static_data;
    1624                 :  119558000 :   freq = NONDEBUG_INSN_P (insn) ? get_insn_freq (insn) : 0;
    1625                 :  119558000 :   invalidate_insn_data_regno_info (data, insn, freq);
    1626                 :  331844000 :   for (i = static_data->n_operands - 1; i >= 0; i--)
    1627                 :  212286000 :     add_regs_to_insn_regno_info (data, *data->operand_loc[i], insn,
    1628                 :  212286000 :                                  static_data->operand[i].type,
    1629                 :  212286000 :                                  static_data->operand[i].early_clobber_alts);
    1630                 :  119558000 :   if ((code = GET_CODE (PATTERN (insn))) == CLOBBER || code == USE)
    1631                 :     553683 :     add_regs_to_insn_regno_info (data, XEXP (PATTERN (insn), 0), insn,
    1632                 :     553683 :                                  code == USE ? OP_IN : OP_OUT, 0);
    1633                 :  119558000 :   if (CALL_P (insn))
    1634                 :            :     /* On some targets call insns can refer to pseudos in memory in
    1635                 :            :        CALL_INSN_FUNCTION_USAGE list.  Process them in order to
    1636                 :            :        consider their occurrences in calls for different
    1637                 :            :        transformations (e.g. inheritance) with given pseudos.  */
    1638                 :    3989600 :     for (link = CALL_INSN_FUNCTION_USAGE (insn);
    1639                 :   10773100 :          link != NULL_RTX;
    1640                 :    6783480 :          link = XEXP (link, 1))
    1641                 :            :       {
    1642                 :    6783480 :         code = GET_CODE (XEXP (link, 0));
    1643                 :    6783480 :         if ((code == USE || code == CLOBBER)
    1644                 :    6720810 :             && MEM_P (XEXP (XEXP (link, 0), 0)))
    1645                 :      38885 :           add_regs_to_insn_regno_info (data, XEXP (XEXP (link, 0), 0), insn,
    1646                 :      38885 :                                        code == USE ? OP_IN : OP_OUT, 0);
    1647                 :            :       }
    1648                 :  119558000 :   if (NONDEBUG_INSN_P (insn))
    1649                 :   87922900 :     setup_insn_reg_info (data, freq);
    1650                 :            : }
    1651                 :            : 
    1652                 :            : /* Return reg info of insn given by it UID.  */
    1653                 :            : struct lra_insn_reg *
    1654                 :      48102 : lra_get_insn_regs (int uid)
    1655                 :            : {
    1656                 :      48102 :   lra_insn_recog_data_t data;
    1657                 :            : 
    1658                 :      48102 :   data = get_insn_recog_data_by_uid (uid);
    1659                 :      48102 :   return data->regs;
    1660                 :            : }
    1661                 :            : 
    1662                 :            : 
    1663                 :            : 
    1664                 :            : /* Recursive hash function for RTL X.  */
    1665                 :            : hashval_t
    1666                 :     117412 : lra_rtx_hash (rtx x)
    1667                 :            : {
    1668                 :     117412 :   int i, j;
    1669                 :     117412 :   enum rtx_code code;
    1670                 :     117412 :   const char *fmt;
    1671                 :     117412 :   hashval_t val = 0;
    1672                 :            : 
    1673                 :     117412 :   if (x == 0)
    1674                 :            :     return val;
    1675                 :            : 
    1676                 :     117412 :   code = GET_CODE (x);
    1677                 :     117412 :   val += (int) code + 4095;
    1678                 :            : 
    1679                 :            :   /* Some RTL can be compared nonrecursively.  */
    1680                 :     117412 :   switch (code)
    1681                 :            :     {
    1682                 :          0 :     case REG:
    1683                 :          0 :       return val + REGNO (x);
    1684                 :            : 
    1685                 :        223 :     case LABEL_REF:
    1686                 :        223 :       return iterative_hash_object (XEXP (x, 0), val);
    1687                 :            : 
    1688                 :      10538 :     case SYMBOL_REF:
    1689                 :      10538 :       return iterative_hash_object (XSTR (x, 0), val);
    1690                 :            : 
    1691                 :            :     case SCRATCH:
    1692                 :            :     case CONST_DOUBLE:
    1693                 :            :     case CONST_VECTOR:
    1694                 :            :       return val;
    1695                 :            : 
    1696                 :      93036 :     case CONST_INT:
    1697                 :      93036 :       return val + UINTVAL (x);
    1698                 :            : 
    1699                 :      12621 :     default:
    1700                 :      12621 :       break;
    1701                 :            :     }
    1702                 :            : 
    1703                 :            :   /* Hash the elements.  */
    1704                 :      12621 :   fmt = GET_RTX_FORMAT (code);
    1705                 :      16470 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    1706                 :            :     {
    1707                 :       3849 :       switch (fmt[i])
    1708                 :            :         {
    1709                 :          0 :         case 'w':
    1710                 :          0 :           val += XWINT (x, i);
    1711                 :          0 :           break;
    1712                 :            : 
    1713                 :          0 :         case 'n':
    1714                 :          0 :         case 'i':
    1715                 :          0 :           val += XINT (x, i);
    1716                 :          0 :           break;
    1717                 :            : 
    1718                 :          0 :         case 'V':
    1719                 :          0 :         case 'E':
    1720                 :          0 :           val += XVECLEN (x, i);
    1721                 :            : 
    1722                 :          0 :           for (j = 0; j < XVECLEN (x, i); j++)
    1723                 :          0 :             val += lra_rtx_hash (XVECEXP (x, i, j));
    1724                 :            :           break;
    1725                 :            : 
    1726                 :       3849 :         case 'e':
    1727                 :       3849 :           val += lra_rtx_hash (XEXP (x, i));
    1728                 :       3849 :           break;
    1729                 :            : 
    1730                 :          0 :         case 'S':
    1731                 :          0 :         case 's':
    1732                 :          0 :           val += htab_hash_string (XSTR (x, i));
    1733                 :          0 :           break;
    1734                 :            : 
    1735                 :            :         case 'u':
    1736                 :            :         case '0':
    1737                 :            :         case 't':
    1738                 :            :           break;
    1739                 :            : 
    1740                 :            :           /* It is believed that rtx's at this level will never
    1741                 :            :              contain anything but integers and other rtx's, except for
    1742                 :            :              within LABEL_REFs and SYMBOL_REFs.  */
    1743                 :          0 :         default:
    1744                 :          0 :           abort ();
    1745                 :            :         }
    1746                 :            :     }
    1747                 :            :   return val;
    1748                 :            : }
    1749                 :            : 
    1750                 :            : 
    1751                 :            : 
    1752                 :            : /* This page contains code dealing with stack of the insns which
    1753                 :            :    should be processed by the next constraint pass.  */
    1754                 :            : 
    1755                 :            : /* Bitmap used to put an insn on the stack only in one exemplar.  */
    1756                 :            : static sbitmap lra_constraint_insn_stack_bitmap;
    1757                 :            : 
    1758                 :            : /* The stack itself.  */
    1759                 :            : vec<rtx_insn *> lra_constraint_insn_stack;
    1760                 :            : 
    1761                 :            : /* Put INSN on the stack.  If ALWAYS_UPDATE is true, always update the reg
    1762                 :            :    info for INSN, otherwise only update it if INSN is not already on the
    1763                 :            :    stack.  */
    1764                 :            : static inline void
    1765                 :  112521000 : lra_push_insn_1 (rtx_insn *insn, bool always_update)
    1766                 :            : {
    1767                 :  112521000 :   unsigned int uid = INSN_UID (insn);
    1768                 :  112521000 :   if (always_update)
    1769                 :    2950620 :     lra_update_insn_regno_info (insn);
    1770                 :  112521000 :   if (uid >= SBITMAP_SIZE (lra_constraint_insn_stack_bitmap))
    1771                 :     338506 :     lra_constraint_insn_stack_bitmap =
    1772                 :     338506 :       sbitmap_resize (lra_constraint_insn_stack_bitmap, 3 * uid / 2, 0);
    1773                 :  112521000 :   if (bitmap_bit_p (lra_constraint_insn_stack_bitmap, uid))
    1774                 :            :     return;
    1775                 :   96055800 :   bitmap_set_bit (lra_constraint_insn_stack_bitmap, uid);
    1776                 :   96055800 :   if (! always_update)
    1777                 :   95972100 :     lra_update_insn_regno_info (insn);
    1778                 :   96055800 :   lra_constraint_insn_stack.safe_push (insn);
    1779                 :            : }
    1780                 :            : 
    1781                 :            : /* Put INSN on the stack.  */
    1782                 :            : void
    1783                 :  109571000 : lra_push_insn (rtx_insn *insn)
    1784                 :            : {
    1785                 :  109571000 :   lra_push_insn_1 (insn, false);
    1786                 :  109571000 : }
    1787                 :            : 
    1788                 :            : /* Put INSN on the stack and update its reg info.  */
    1789                 :            : void
    1790                 :    2950620 : lra_push_insn_and_update_insn_regno_info (rtx_insn *insn)
    1791                 :            : {
    1792                 :    2950620 :   lra_push_insn_1 (insn, true);
    1793                 :    2950620 : }
    1794                 :            : 
    1795                 :            : /* Put insn with UID on the stack.  */
    1796                 :            : void
    1797                 :    5137350 : lra_push_insn_by_uid (unsigned int uid)
    1798                 :            : {
    1799                 :    5137350 :   lra_push_insn (lra_insn_recog_data[uid]->insn);
    1800                 :    5137350 : }
    1801                 :            : 
    1802                 :            : /* Take the last-inserted insns off the stack and return it.  */
    1803                 :            : rtx_insn *
    1804                 :   96055500 : lra_pop_insn (void)
    1805                 :            : {
    1806                 :   96055500 :   rtx_insn *insn = lra_constraint_insn_stack.pop ();
    1807                 :   96055500 :   bitmap_clear_bit (lra_constraint_insn_stack_bitmap, INSN_UID (insn));
    1808                 :   96055500 :   return insn;
    1809                 :            : }
    1810                 :            : 
    1811                 :            : /* Return the current size of the insn stack.  */
    1812                 :            : unsigned int
    1813                 :  100080000 : lra_insn_stack_length (void)
    1814                 :            : {
    1815                 :  100080000 :   return lra_constraint_insn_stack.length ();
    1816                 :            : }
    1817                 :            : 
    1818                 :            : /* Push insns FROM to TO (excluding it) going in reverse order.  */
    1819                 :            : static void
    1820                 :    7193620 : push_insns (rtx_insn *from, rtx_insn *to)
    1821                 :            : {
    1822                 :    7193620 :   rtx_insn *insn;
    1823                 :            : 
    1824                 :    7193620 :   if (from == NULL_RTX)
    1825                 :            :     return;
    1826                 :  224465000 :   for (insn = from; insn != to; insn = PREV_INSN (insn))
    1827                 :  108636000 :     if (INSN_P (insn))
    1828                 :   87790800 :       lra_push_insn (insn);
    1829                 :            : }
    1830                 :            : 
    1831                 :            : /* Set up sp offset for insn in range [FROM, LAST].  The offset is
    1832                 :            :    taken from the next BB insn after LAST or zero if there in such
    1833                 :            :    insn.  */
    1834                 :            : static void
    1835                 :    6249520 : setup_sp_offset (rtx_insn *from, rtx_insn *last)
    1836                 :            : {
    1837                 :    6249520 :   rtx_insn *before = next_nonnote_nondebug_insn_bb (last);
    1838                 :    6237720 :   poly_int64 offset = (before == NULL_RTX || ! INSN_P (before)
    1839                 :   12415900 :                        ? 0 : lra_get_insn_recog_data (before)->sp_offset);
    1840                 :            : 
    1841                 :   12694300 :   for (rtx_insn *insn = from; insn != NEXT_INSN (last); insn = NEXT_INSN (insn))
    1842                 :    6444740 :     lra_get_insn_recog_data (insn)->sp_offset = offset;
    1843                 :    6249520 : }
    1844                 :            : 
    1845                 :            : /* Emit insns BEFORE before INSN and insns AFTER after INSN.  Put the
    1846                 :            :    insns onto the stack.  Print about emitting the insns with
    1847                 :            :    TITLE.  */
    1848                 :            : void
    1849                 :   49689400 : lra_process_new_insns (rtx_insn *insn, rtx_insn *before, rtx_insn *after,
    1850                 :            :                        const char *title)
    1851                 :            : {
    1852                 :   49689400 :   rtx_insn *last;
    1853                 :            : 
    1854                 :   49689400 :   if (before == NULL_RTX && after == NULL_RTX)
    1855                 :            :     return;
    1856                 :    5153180 :   if (lra_dump_file != NULL)
    1857                 :            :     {
    1858                 :        238 :       dump_insn_slim (lra_dump_file, insn);
    1859                 :        238 :       if (before != NULL_RTX)
    1860                 :            :         {
    1861                 :        210 :           fprintf (lra_dump_file,"    %s before:\n", title);
    1862                 :        210 :           dump_rtl_slim (lra_dump_file, before, NULL, -1, 0);
    1863                 :            :         }
    1864                 :        238 :       if (after != NULL_RTX)
    1865                 :            :         {
    1866                 :        195 :           fprintf (lra_dump_file, "    %s after:\n", title);
    1867                 :        195 :           dump_rtl_slim (lra_dump_file, after, NULL, -1, 0);
    1868                 :            :         }
    1869                 :        238 :       fprintf (lra_dump_file, "\n");
    1870                 :            :     }
    1871                 :    5153180 :   if (before != NULL_RTX)
    1872                 :            :     {
    1873                 :    3798200 :       if (cfun->can_throw_non_call_exceptions)
    1874                 :    1098510 :         copy_reg_eh_region_note_forward (insn, before, NULL);
    1875                 :    3798200 :       emit_insn_before (before, insn);
    1876                 :    3798200 :       push_insns (PREV_INSN (insn), PREV_INSN (before));
    1877                 :    3798200 :       setup_sp_offset (before, PREV_INSN (insn));
    1878                 :            :     }
    1879                 :    5153180 :   if (after != NULL_RTX)
    1880                 :            :     {
    1881                 :    2451320 :       if (cfun->can_throw_non_call_exceptions)
    1882                 :     765085 :         copy_reg_eh_region_note_forward (insn, after, NULL);
    1883                 :    2456130 :       for (last = after; NEXT_INSN (last) != NULL_RTX; last = NEXT_INSN (last))
    1884                 :            :         ;
    1885                 :    2451320 :       emit_insn_after (after, insn);
    1886                 :    2451320 :       push_insns (last, insn);
    1887                 :    2451320 :       setup_sp_offset (after, last);
    1888                 :            :     }
    1889                 :    5153180 :   if (cfun->can_throw_non_call_exceptions)
    1890                 :            :     {
    1891                 :    1709270 :       rtx note = find_reg_note (insn, REG_EH_REGION, NULL_RTX);
    1892                 :    1709270 :       if (note && !insn_could_throw_p (insn))
    1893                 :       1089 :         remove_note (insn, note);
    1894                 :            :     }
    1895                 :            : }
    1896                 :            : 
    1897                 :            : 
    1898                 :            : /* Replace all references to register OLD_REGNO in *LOC with pseudo
    1899                 :            :    register NEW_REG.  Try to simplify subreg of constant if SUBREG_P.
    1900                 :            :    DEBUG_P is if LOC is within a DEBUG_INSN.  Return true if any
    1901                 :            :    change was made.  */
    1902                 :            : bool
    1903                 :   18839000 : lra_substitute_pseudo (rtx *loc, int old_regno, rtx new_reg, bool subreg_p,
    1904                 :            :                        bool debug_p)
    1905                 :            : {
    1906                 :   18839000 :   rtx x = *loc;
    1907                 :   18839000 :   bool result = false;
    1908                 :   18839000 :   enum rtx_code code;
    1909                 :   18839000 :   const char *fmt;
    1910                 :   18839000 :   int i, j;
    1911                 :            : 
    1912                 :   18839000 :   if (x == NULL_RTX)
    1913                 :            :     return false;
    1914                 :            : 
    1915                 :   16097200 :   code = GET_CODE (x);
    1916                 :   16097200 :   if (code == SUBREG && subreg_p)
    1917                 :            :     {
    1918                 :          0 :       rtx subst, inner = SUBREG_REG (x);
    1919                 :            :       /* Transform subreg of constant while we still have inner mode
    1920                 :            :          of the subreg.  The subreg internal should not be an insn
    1921                 :            :          operand.  */
    1922                 :          0 :       if (REG_P (inner) && (int) REGNO (inner) == old_regno
    1923                 :          0 :           && CONSTANT_P (new_reg)
    1924                 :          0 :           && (subst = simplify_subreg (GET_MODE (x), new_reg, GET_MODE (inner),
    1925                 :          0 :                                        SUBREG_BYTE (x))) != NULL_RTX)
    1926                 :            :         {
    1927                 :          0 :           *loc = subst;
    1928                 :          0 :           return true;
    1929                 :            :         }
    1930                 :            :       
    1931                 :            :     }
    1932                 :   16097200 :   else if (code == REG && (int) REGNO (x) == old_regno)
    1933                 :            :     {
    1934                 :    3534000 :       machine_mode mode = GET_MODE (x);
    1935                 :    3534000 :       machine_mode inner_mode = GET_MODE (new_reg);
    1936                 :            : 
    1937                 :    3534000 :       if (mode != inner_mode
    1938                 :         13 :           && ! (CONST_SCALAR_INT_P (new_reg) && SCALAR_INT_MODE_P (mode)))
    1939                 :            :         {
    1940                 :         13 :           poly_uint64 offset = 0;
    1941                 :         13 :           if (partial_subreg_p (mode, inner_mode)
    1942                 :         13 :               && SCALAR_INT_MODE_P (inner_mode))
    1943                 :         13 :             offset = subreg_lowpart_offset (mode, inner_mode);
    1944                 :         13 :           if (debug_p)
    1945                 :         13 :             new_reg = gen_rtx_raw_SUBREG (mode, new_reg, offset);
    1946                 :            :           else
    1947                 :          0 :             new_reg = gen_rtx_SUBREG (mode, new_reg, offset);
    1948                 :            :         }
    1949                 :    3534000 :       *loc = new_reg;
    1950                 :    3534000 :       return true;
    1951                 :            :     }
    1952                 :            : 
    1953                 :            :   /* Scan all the operand sub-expressions.  */
    1954                 :   12563200 :   fmt = GET_RTX_FORMAT (code);
    1955                 :   46709000 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    1956                 :            :     {
    1957                 :   34145800 :       if (fmt[i] == 'e')
    1958                 :            :         {
    1959                 :   15589300 :           if (lra_substitute_pseudo (&XEXP (x, i), old_regno,
    1960                 :            :                                      new_reg, subreg_p, debug_p))
    1961                 :    7789600 :             result = true;
    1962                 :            :         }
    1963                 :   18556400 :       else if (fmt[i] == 'E')
    1964                 :            :         {
    1965                 :     747440 :           for (j = XVECLEN (x, i) - 1; j >= 0; j--)
    1966                 :     507886 :             if (lra_substitute_pseudo (&XVECEXP (x, i, j), old_regno,
    1967                 :            :                                        new_reg, subreg_p, debug_p))
    1968                 :     228353 :               result = true;
    1969                 :            :         }
    1970                 :            :     }
    1971                 :            :   return result;
    1972                 :            : }
    1973                 :            : 
    1974                 :            : /* Call lra_substitute_pseudo within an insn.  Try to simplify subreg
    1975                 :            :    of constant if SUBREG_P.  This won't update the insn ptr, just the
    1976                 :            :    contents of the insn.  */
    1977                 :            : bool
    1978                 :    1805110 : lra_substitute_pseudo_within_insn (rtx_insn *insn, int old_regno,
    1979                 :            :                                    rtx new_reg, bool subreg_p)
    1980                 :            : {
    1981                 :    1805110 :   rtx loc = insn;
    1982                 :    1805110 :   return lra_substitute_pseudo (&loc, old_regno, new_reg, subreg_p,
    1983                 :    1805110 :                                 DEBUG_INSN_P (insn));
    1984                 :            : }
    1985                 :            : 
    1986                 :            : 
    1987                 :            : 
    1988                 :            : /* This page contains code dealing with scratches (changing them onto
    1989                 :            :    pseudos and restoring them from the pseudos).
    1990                 :            : 
    1991                 :            :    We change scratches into pseudos at the beginning of LRA to
    1992                 :            :    simplify dealing with them (conflicts, hard register assignments).
    1993                 :            : 
    1994                 :            :    If the pseudo denoting scratch was spilled it means that we do need
    1995                 :            :    a hard register for it.  Such pseudos are transformed back to
    1996                 :            :    scratches at the end of LRA.  */
    1997                 :            : 
    1998                 :            : /* Description of location of a former scratch operand.  */
    1999                 :            : struct sloc
    2000                 :            : {
    2001                 :            :   rtx_insn *insn; /* Insn where the scratch was.  */
    2002                 :            :   int nop;  /* Number of the operand which was a scratch.  */
    2003                 :            :   int icode;  /* Original icode from which scratch was removed.  */
    2004                 :            : };
    2005                 :            : 
    2006                 :            : typedef struct sloc *sloc_t;
    2007                 :            : 
    2008                 :            : /* Locations of the former scratches.  */
    2009                 :            : static vec<sloc_t> scratches;
    2010                 :            : 
    2011                 :            : /* Bitmap of scratch regnos.  */
    2012                 :            : static bitmap_head scratch_bitmap;
    2013                 :            : 
    2014                 :            : /* Bitmap of scratch operands.  */
    2015                 :            : static bitmap_head scratch_operand_bitmap;
    2016                 :            : 
    2017                 :            : /* Return true if pseudo REGNO is made of SCRATCH.  */
    2018                 :            : bool
    2019                 :  192732000 : lra_former_scratch_p (int regno)
    2020                 :            : {
    2021                 :  192732000 :   return bitmap_bit_p (&scratch_bitmap, regno);
    2022                 :            : }
    2023                 :            : 
    2024                 :            : /* Return true if the operand NOP of INSN is a former scratch.  */
    2025                 :            : bool
    2026                 :    2994550 : lra_former_scratch_operand_p (rtx_insn *insn, int nop)
    2027                 :            : {
    2028                 :    2994550 :   return bitmap_bit_p (&scratch_operand_bitmap,
    2029                 :    2994550 :                        INSN_UID (insn) * MAX_RECOG_OPERANDS + nop) != 0;
    2030                 :            : }
    2031                 :            : 
    2032                 :            : /* Register operand NOP in INSN as a former scratch.  It will be
    2033                 :            :    changed to scratch back, if it is necessary, at the LRA end.  */
    2034                 :            : void
    2035                 :      83866 : lra_register_new_scratch_op (rtx_insn *insn, int nop, int icode)
    2036                 :            : {
    2037                 :      83866 :   lra_insn_recog_data_t id = lra_get_insn_recog_data (insn);
    2038                 :      83866 :   rtx op = *id->operand_loc[nop];
    2039                 :      83866 :   sloc_t loc = XNEW (struct sloc);
    2040                 :      83866 :   lra_assert (REG_P (op));
    2041                 :      83866 :   loc->insn = insn;
    2042                 :      83866 :   loc->nop = nop;
    2043                 :      83866 :   loc->icode = icode;
    2044                 :      83866 :   scratches.safe_push (loc);
    2045                 :      83866 :   bitmap_set_bit (&scratch_bitmap, REGNO (op));
    2046                 :      83866 :   bitmap_set_bit (&scratch_operand_bitmap,
    2047                 :      83866 :                   INSN_UID (insn) * MAX_RECOG_OPERANDS + nop);
    2048                 :      83866 :   add_reg_note (insn, REG_UNUSED, op);
    2049                 :      83866 : }
    2050                 :            : 
    2051                 :            : /* Change INSN's scratches into pseudos and save their location.  */
    2052                 :            : static void
    2053                 :   86642900 : remove_scratches_1 (rtx_insn *insn)
    2054                 :            : {
    2055                 :   86642900 :   int i;
    2056                 :   86642900 :   bool insn_changed_p;
    2057                 :   86642900 :   rtx reg;
    2058                 :   86642900 :   lra_insn_recog_data_t id;
    2059                 :   86642900 :   struct lra_static_insn_data *static_id;
    2060                 :            : 
    2061                 :   86642900 :   id = lra_get_insn_recog_data (insn);
    2062                 :   86642900 :   static_id = id->insn_static_data;
    2063                 :   86642900 :   insn_changed_p = false;
    2064                 :  232192000 :   for (i = 0; i < static_id->n_operands; i++)
    2065                 :  145549000 :     if (GET_CODE (*id->operand_loc[i]) == SCRATCH
    2066                 :      83864 :         && GET_MODE (*id->operand_loc[i]) != VOIDmode)
    2067                 :            :       {
    2068                 :      83864 :         insn_changed_p = true;
    2069                 :     167728 :         *id->operand_loc[i] = reg
    2070                 :      83864 :           = lra_create_new_reg (static_id->operand[i].mode,
    2071                 :            :                                 *id->operand_loc[i], ALL_REGS, NULL);
    2072                 :      83864 :         lra_register_new_scratch_op (insn, i, id->icode);
    2073                 :      83864 :         if (lra_dump_file != NULL)
    2074                 :         14 :           fprintf (lra_dump_file,
    2075                 :            :                    "Removing SCRATCH in insn #%u (nop %d)\n",
    2076                 :         14 :                    INSN_UID (insn), i);
    2077                 :            :       }
    2078                 :   86642900 :   if (insn_changed_p)
    2079                 :            :     /* Because we might use DF right after caller-saves sub-pass
    2080                 :            :        we need to keep DF info up to date.  */
    2081                 :      81817 :     df_insn_rescan (insn);
    2082                 :   86642900 : }
    2083                 :            : 
    2084                 :            : /* Change scratches into pseudos and save their location.  */
    2085                 :            : static void
    2086                 :     944096 : remove_scratches (void)
    2087                 :            : {
    2088                 :     944096 :   basic_block bb;
    2089                 :     944096 :   rtx_insn *insn;
    2090                 :            : 
    2091                 :     944096 :   scratches.create (get_max_uid ());
    2092                 :     944096 :   bitmap_initialize (&scratch_bitmap, &reg_obstack);
    2093                 :     944096 :   bitmap_initialize (&scratch_operand_bitmap, &reg_obstack);
    2094                 :   10066000 :   FOR_EACH_BB_FN (bb, cfun)
    2095                 :  205186000 :     FOR_BB_INSNS (bb, insn)
    2096                 :   98032300 :     if (INSN_P (insn))
    2097                 :   81346000 :       remove_scratches_1 (insn);
    2098                 :     944096 : }
    2099                 :            : 
    2100                 :            : /* Changes pseudos created by function remove_scratches onto scratches.  */
    2101                 :            : static void
    2102                 :     944096 : restore_scratches (void)
    2103                 :            : {
    2104                 :     944096 :   int regno;
    2105                 :     944096 :   unsigned i;
    2106                 :     944096 :   sloc_t loc;
    2107                 :     944096 :   rtx_insn *last = NULL;
    2108                 :     944096 :   lra_insn_recog_data_t id = NULL;
    2109                 :            : 
    2110                 :    1027960 :   for (i = 0; scratches.iterate (i, &loc); i++)
    2111                 :            :     {
    2112                 :            :       /* Ignore already deleted insns.  */
    2113                 :      83866 :       if (NOTE_P (loc->insn)
    2114                 :          0 :           && NOTE_KIND (loc->insn) == NOTE_INSN_DELETED)
    2115                 :          0 :         continue;
    2116                 :      83866 :       if (last != loc->insn)
    2117                 :            :         {
    2118                 :      81819 :           last = loc->insn;
    2119                 :      81819 :           id = lra_get_insn_recog_data (last);
    2120                 :            :         }
    2121                 :      83866 :       if (loc->icode != id->icode)
    2122                 :            :         {
    2123                 :            :           /* The icode doesn't match, which means the insn has been modified
    2124                 :            :              (e.g. register elimination).  The scratch cannot be restored.  */
    2125                 :          0 :           continue;
    2126                 :            :         }
    2127                 :      83866 :       if (REG_P (*id->operand_loc[loc->nop])
    2128                 :      83866 :           && ((regno = REGNO (*id->operand_loc[loc->nop]))
    2129                 :            :               >= FIRST_PSEUDO_REGISTER)
    2130                 :     167732 :           && lra_get_regno_hard_regno (regno) < 0)
    2131                 :            :         {
    2132                 :            :           /* It should be only case when scratch register with chosen
    2133                 :            :              constraint 'X' did not get memory or hard register.  */
    2134                 :       3023 :           lra_assert (lra_former_scratch_p (regno));
    2135                 :       3023 :           *id->operand_loc[loc->nop]
    2136                 :       3023 :             = gen_rtx_SCRATCH (GET_MODE (*id->operand_loc[loc->nop]));
    2137                 :       3023 :           lra_update_dup (id, loc->nop);
    2138                 :       3023 :           if (lra_dump_file != NULL)
    2139                 :          0 :             fprintf (lra_dump_file, "Restoring SCRATCH in insn #%u(nop %d)\n",
    2140                 :          0 :                      INSN_UID (loc->insn), loc->nop);
    2141                 :            :         }
    2142                 :            :     }
    2143                 :    1027960 :   for (i = 0; scratches.iterate (i, &loc); i++)
    2144                 :      83866 :     free (loc);
    2145                 :     944096 :   scratches.release ();
    2146                 :     944096 :   bitmap_clear (&scratch_bitmap);
    2147                 :     944096 :   bitmap_clear (&scratch_operand_bitmap);
    2148                 :     944096 : }
    2149                 :            : 
    2150                 :            : 
    2151                 :            : 
    2152                 :            : /* Function checks RTL for correctness.  If FINAL_P is true, it is
    2153                 :            :    done at the end of LRA and the check is more rigorous.  */
    2154                 :            : static void
    2155                 :    1888170 : check_rtl (bool final_p)
    2156                 :            : {
    2157                 :    1888170 :   basic_block bb;
    2158                 :    1888170 :   rtx_insn *insn;
    2159                 :            : 
    2160                 :    1888170 :   lra_assert (! final_p || reload_completed);
    2161                 :   20132200 :   FOR_EACH_BB_FN (bb, cfun)
    2162                 :  408225000 :     FOR_BB_INSNS (bb, insn)
    2163                 :  194990000 :     if (NONDEBUG_INSN_P (insn)
    2164                 :  103839000 :         && GET_CODE (PATTERN (insn)) != USE
    2165                 :  102874000 :         && GET_CODE (PATTERN (insn)) != CLOBBER
    2166                 :  297791000 :         && GET_CODE (PATTERN (insn)) != ASM_INPUT)
    2167                 :            :       {
    2168                 :  102797000 :         if (final_p)
    2169                 :            :           {
    2170                 :   50011400 :             extract_constrain_insn (insn);
    2171                 :   50011400 :             continue;
    2172                 :            :           }
    2173                 :            :         /* LRA code is based on assumption that all addresses can be
    2174                 :            :            correctly decomposed.  LRA can generate reloads for
    2175                 :            :            decomposable addresses.  The decomposition code checks the
    2176                 :            :            correctness of the addresses.  So we don't need to check
    2177                 :            :            the addresses here.  Don't call insn_invalid_p here, it can
    2178                 :            :            change the code at this stage.  */
    2179                 :   52873400 :         if (recog_memoized (insn) < 0 && asm_noperands (PATTERN (insn)) < 0)
    2180                 :          0 :           fatal_insn_not_found (insn);
    2181                 :            :       }
    2182                 :    1888170 : }
    2183                 :            : 
    2184                 :            : /* Determine if the current function has an exception receiver block
    2185                 :            :    that reaches the exit block via non-exceptional edges  */
    2186                 :            : static bool
    2187                 :        798 : has_nonexceptional_receiver (void)
    2188                 :            : {
    2189                 :        798 :   edge e;
    2190                 :        798 :   edge_iterator ei;
    2191                 :        798 :   basic_block *tos, *worklist, bb;
    2192                 :            : 
    2193                 :            :   /* If we're not optimizing, then just err on the safe side.  */
    2194                 :        798 :   if (!optimize)
    2195                 :            :     return true;
    2196                 :            : 
    2197                 :            :   /* First determine which blocks can reach exit via normal paths.  */
    2198                 :        702 :   tos = worklist = XNEWVEC (basic_block, n_basic_blocks_for_fn (cfun) + 1);
    2199                 :            : 
    2200                 :       5144 :   FOR_EACH_BB_FN (bb, cfun)
    2201                 :       4442 :     bb->flags &= ~BB_REACHABLE;
    2202                 :            : 
    2203                 :            :   /* Place the exit block on our worklist.  */
    2204                 :        702 :   EXIT_BLOCK_PTR_FOR_FN (cfun)->flags |= BB_REACHABLE;
    2205                 :        702 :   *tos++ = EXIT_BLOCK_PTR_FOR_FN (cfun);
    2206                 :            : 
    2207                 :            :   /* Iterate: find everything reachable from what we've already seen.  */
    2208                 :       2810 :   while (tos != worklist)
    2209                 :            :     {
    2210                 :       2664 :       bb = *--tos;
    2211                 :            : 
    2212                 :       4830 :       FOR_EACH_EDGE (e, ei, bb->preds)
    2213                 :       2722 :         if (e->flags & EDGE_ABNORMAL)
    2214                 :            :           {
    2215                 :        556 :             free (worklist);
    2216                 :        556 :             return true;
    2217                 :            :           }
    2218                 :            :         else
    2219                 :            :           {
    2220                 :       2166 :             basic_block src = e->src;
    2221                 :            : 
    2222                 :       2166 :             if (!(src->flags & BB_REACHABLE))
    2223                 :            :               {
    2224                 :       2043 :                 src->flags |= BB_REACHABLE;
    2225                 :       2043 :                 *tos++ = src;
    2226                 :            :               }
    2227                 :            :           }
    2228                 :            :     }
    2229                 :        146 :   free (worklist);
    2230                 :            :   /* No exceptional block reached exit unexceptionally.  */
    2231                 :        146 :   return false;
    2232                 :            : }
    2233                 :            : 
    2234                 :            : 
    2235                 :            : /* Process recursively X of INSN and add REG_INC notes if necessary.  */
    2236                 :            : static void
    2237                 :          0 : add_auto_inc_notes (rtx_insn *insn, rtx x)
    2238                 :            : {
    2239                 :          0 :   enum rtx_code code = GET_CODE (x);
    2240                 :          0 :   const char *fmt;
    2241                 :          0 :   int i, j;
    2242                 :            : 
    2243                 :          0 :   if (code == MEM && auto_inc_p (XEXP (x, 0)))
    2244                 :            :     {
    2245                 :          0 :       add_reg_note (insn, REG_INC, XEXP (XEXP (x, 0), 0));
    2246                 :          0 :       return;
    2247                 :            :     }
    2248                 :            : 
    2249                 :            :   /* Scan all X sub-expressions.  */
    2250                 :          0 :   fmt = GET_RTX_FORMAT (code);
    2251                 :          0 :   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
    2252                 :            :     {
    2253                 :          0 :       if (fmt[i] == 'e')
    2254                 :          0 :         add_auto_inc_notes (insn, XEXP (x, i));
    2255                 :          0 :       else if (fmt[i] == 'E')
    2256                 :          0 :         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
    2257                 :          0 :           add_auto_inc_notes (insn, XVECEXP (x, i, j));
    2258                 :            :     }
    2259                 :            : }
    2260                 :            : 
    2261                 :            : 
    2262                 :            : /* Remove all REG_DEAD and REG_UNUSED notes and regenerate REG_INC.
    2263                 :            :    We change pseudos by hard registers without notification of DF and
    2264                 :            :    that can make the notes obsolete.  DF-infrastructure does not deal
    2265                 :            :    with REG_INC notes -- so we should regenerate them here.  */
    2266                 :            : static void
    2267                 :     944096 : update_inc_notes (void)
    2268                 :            : {
    2269                 :     944096 :   rtx *pnote;
    2270                 :     944096 :   basic_block bb;
    2271                 :     944096 :   rtx_insn *insn;
    2272                 :            : 
    2273                 :   10066000 :   FOR_EACH_BB_FN (bb, cfun)
    2274                 :  203048000 :     FOR_BB_INSNS (bb, insn)
    2275                 :   96962900 :     if (NONDEBUG_INSN_P (insn))
    2276                 :            :       {
    2277                 :   50532600 :         pnote = &REG_NOTES (insn);
    2278                 :  102231000 :         while (*pnote != 0)
    2279                 :            :           {
    2280                 :   51698800 :             if (REG_NOTE_KIND (*pnote) == REG_DEAD
    2281                 :   51698800 :                 || REG_NOTE_KIND (*pnote) == REG_UNUSED
    2282                 :   16359800 :                 || REG_NOTE_KIND (*pnote) == REG_INC)
    2283                 :   35338900 :               *pnote = XEXP (*pnote, 1);
    2284                 :            :             else
    2285                 :   16359800 :               pnote = &XEXP (*pnote, 1);
    2286                 :            :           }
    2287                 :            : 
    2288                 :            :         if (AUTO_INC_DEC)
    2289                 :            :           add_auto_inc_notes (insn, PATTERN (insn));
    2290                 :            :       }
    2291                 :     944096 : }
    2292                 :            : 
    2293                 :            : /* Set to 1 while in lra.  */
    2294                 :            : int lra_in_progress;
    2295                 :            : 
    2296                 :            : /* Start of pseudo regnos before the LRA.  */
    2297                 :            : int lra_new_regno_start;
    2298                 :            : 
    2299                 :            : /* Start of reload pseudo regnos before the new spill pass.  */
    2300                 :            : int lra_constraint_new_regno_start;
    2301                 :            : 
    2302                 :            : /* Avoid spilling pseudos with regno more than the following value if
    2303                 :            :    it is possible.  */
    2304                 :            : int lra_bad_spill_regno_start;
    2305                 :            : 
    2306                 :            : /* Inheritance pseudo regnos before the new spill pass.  */
    2307                 :            : bitmap_head lra_inheritance_pseudos;
    2308                 :            : 
    2309                 :            : /* Split regnos before the new spill pass.  */
    2310                 :            : bitmap_head lra_split_regs;
    2311                 :            : 
    2312                 :            : /* Reload pseudo regnos before the new assignment pass which still can
    2313                 :            :    be spilled after the assignment pass as memory is also accepted in
    2314                 :            :    insns for the reload pseudos.  */
    2315                 :            : bitmap_head lra_optional_reload_pseudos;
    2316                 :            : 
    2317                 :            : /* Pseudo regnos used for subreg reloads before the new assignment
    2318                 :            :    pass.  Such pseudos still can be spilled after the assignment
    2319                 :            :    pass.  */
    2320                 :            : bitmap_head lra_subreg_reload_pseudos;
    2321                 :            : 
    2322                 :            : /* File used for output of LRA debug information.  */
    2323                 :            : FILE *lra_dump_file;
    2324                 :            : 
    2325                 :            : /* True if we found an asm error.  */
    2326                 :            : bool lra_asm_error_p;
    2327                 :            : 
    2328                 :            : /* True if we should try spill into registers of different classes
    2329                 :            :    instead of memory.  */
    2330                 :            : bool lra_reg_spill_p;
    2331                 :            : 
    2332                 :            : /* Set up value LRA_REG_SPILL_P.  */
    2333                 :            : static void
    2334                 :     944096 : setup_reg_spill_flag (void)
    2335                 :            : {
    2336                 :     944096 :   int cl, mode;
    2337                 :            : 
    2338                 :     944096 :   if (targetm.spill_class != NULL)
    2339                 :   29267000 :     for (cl = 0; cl < (int) LIM_REG_CLASSES; cl++)
    2340                 : 3172160000 :       for (mode = 0; mode < MAX_MACHINE_MODE; mode++)
    2341                 : 3143840000 :         if (targetm.spill_class ((enum reg_class) cl,
    2342                 :            :                                  (machine_mode) mode) != NO_REGS)
    2343                 :            :           {
    2344                 :          0 :             lra_reg_spill_p = true;
    2345                 :          0 :             return;
    2346                 :            :           }
    2347                 :     944096 :   lra_reg_spill_p = false;
    2348                 :            : }
    2349                 :            : 
    2350                 :            : /* True if the current function is too big to use regular algorithms
    2351                 :            :    in LRA. In other words, we should use simpler and faster algorithms
    2352                 :            :    in LRA.  It also means we should not worry about generation code
    2353                 :            :    for caller saves.  The value is set up in IRA.  */
    2354                 :            : bool lra_simple_p;
    2355                 :            : 
    2356                 :            : /* Major LRA entry function.  F is a file should be used to dump LRA
    2357                 :            :    debug info.  */
    2358                 :            : void
    2359                 :     944096 : lra (FILE *f)
    2360                 :            : {
    2361                 :     944096 :   int i;
    2362                 :     944096 :   bool live_p, inserted_p;
    2363                 :            : 
    2364                 :     944096 :   lra_dump_file = f;
    2365                 :     944096 :   lra_asm_error_p = false;
    2366                 :            :   
    2367                 :     944096 :   timevar_push (TV_LRA);
    2368                 :            : 
    2369                 :            :   /* Make sure that the last insn is a note.  Some subsequent passes
    2370                 :            :      need it.  */
    2371                 :     944096 :   emit_note (NOTE_INSN_DELETED);
    2372                 :            : 
    2373                 :     944096 :   lra_no_alloc_regs = ira_no_alloc_regs;
    2374                 :            : 
    2375                 :     944096 :   init_reg_info ();
    2376                 :     944096 :   expand_reg_info ();
    2377                 :            : 
    2378                 :     944096 :   init_insn_recog_data ();
    2379                 :            : 
    2380                 :            :   /* Some quick check on RTL generated by previous passes.  */
    2381                 :     944096 :   if (flag_checking)
    2382                 :     944084 :     check_rtl (false);
    2383                 :            : 
    2384                 :     944096 :   lra_in_progress = 1;
    2385                 :            : 
    2386                 :     944096 :   lra_live_range_iter = lra_coalesce_iter = lra_constraint_iter = 0;
    2387                 :     944096 :   lra_assignment_iter = lra_assignment_iter_after_spill = 0;
    2388                 :     944096 :   lra_inheritance_iter = lra_undo_inheritance_iter = 0;
    2389                 :     944096 :   lra_rematerialization_iter = 0;
    2390                 :            : 
    2391                 :     944096 :   setup_reg_spill_flag ();
    2392                 :            : 
    2393                 :            :   /* Function remove_scratches can creates new pseudos for clobbers --
    2394                 :            :      so set up lra_constraint_new_regno_start before its call to
    2395                 :            :      permit changing reg classes for pseudos created by this
    2396                 :            :      simplification.  */
    2397                 :     944096 :   lra_constraint_new_regno_start = lra_new_regno_start = max_reg_num ();
    2398                 :     944096 :   lra_bad_spill_regno_start = INT_MAX;
    2399                 :     944096 :   remove_scratches ();
    2400                 :            : 
    2401                 :            :   /* A function that has a non-local label that can reach the exit
    2402                 :            :      block via non-exceptional paths must save all call-saved
    2403                 :            :      registers.  */
    2404                 :     944096 :   if (cfun->has_nonlocal_label && has_nonexceptional_receiver ())
    2405                 :        652 :     crtl->saves_all_registers = 1;
    2406                 :            : 
    2407                 :     944096 :   if (crtl->saves_all_registers)
    2408                 :      52822 :     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
    2409                 :      52136 :       if (!crtl->abi->clobbers_full_reg_p (i)
    2410                 :       6138 :           && !fixed_regs[i]
    2411                 :      52136 :           && !LOCAL_REGNO (i))
    2412                 :       4080 :         df_set_regs_ever_live (i, true);
    2413                 :            : 
    2414                 :            :   /* We don't DF from now and avoid its using because it is to
    2415                 :            :      expensive when a lot of RTL changes are made.  */
    2416                 :     944096 :   df_set_flags (DF_NO_INSN_RESCAN);
    2417                 :     944096 :   lra_constraint_insn_stack.create (get_max_uid ());
    2418                 :     944096 :   lra_constraint_insn_stack_bitmap = sbitmap_alloc (get_max_uid ());
    2419                 :     944096 :   bitmap_clear (lra_constraint_insn_stack_bitmap);
    2420                 :     944096 :   lra_live_ranges_init ();
    2421                 :     944096 :   lra_constraints_init ();
    2422                 :     944096 :   lra_curr_reload_num = 0;
    2423                 :     944096 :   push_insns (get_last_insn (), NULL);
    2424                 :            :   /* It is needed for the 1st coalescing.  */
    2425                 :     944096 :   bitmap_initialize (&lra_inheritance_pseudos, &reg_obstack);
    2426                 :     944096 :   bitmap_initialize (&lra_split_regs, &reg_obstack);
    2427                 :     944096 :   bitmap_initialize (&lra_optional_reload_pseudos, &reg_obstack);
    2428                 :     944096 :   bitmap_initialize (&lra_subreg_reload_pseudos, &reg_obstack);
    2429                 :     944096 :   live_p = false;
    2430                 :     944096 :   if (maybe_ne (get_frame_size (), 0) && crtl->stack_alignment_needed)
    2431                 :            :     /* If we have a stack frame, we must align it now.  The stack size
    2432                 :            :        may be a part of the offset computation for register
    2433                 :            :        elimination.  */
    2434                 :     396685 :     assign_stack_local (BLKmode, 0, crtl->stack_alignment_needed);
    2435                 :     944096 :   lra_init_equiv ();
    2436                 :    2012400 :   for (;;)
    2437                 :            :     {
    2438                 :    2012400 :       for (;;)
    2439                 :            :         {
    2440                 :    2012400 :           bool reloads_p = lra_constraints (lra_constraint_iter == 0);
    2441                 :            :           /* Constraint transformations may result in that eliminable
    2442                 :            :              hard regs become uneliminable and pseudos which use them
    2443                 :            :              should be spilled.  It is better to do it before pseudo
    2444                 :            :              assignments.
    2445                 :            : 
    2446                 :            :              For example, rs6000 can make
    2447                 :            :              RS6000_PIC_OFFSET_TABLE_REGNUM uneliminable if we started
    2448                 :            :              to use a constant pool.  */
    2449                 :    2012400 :           lra_eliminate (false, false);
    2450                 :            :           /* We should try to assign hard registers to scratches even
    2451                 :            :              if there were no RTL transformations in lra_constraints.
    2452                 :            :              Also we should check IRA assignments on the first
    2453                 :            :              iteration as they can be wrong because of early clobbers
    2454                 :            :              operands which are ignored in IRA.  */
    2455                 :    2012400 :           if (! reloads_p && lra_constraint_iter > 1)
    2456                 :            :             {
    2457                 :            :               /* Stack is not empty here only when there are changes
    2458                 :            :                  during the elimination sub-pass.  */
    2459                 :    1027530 :               if (bitmap_empty_p (lra_constraint_insn_stack_bitmap))
    2460                 :            :                 break;
    2461                 :            :               else
    2462                 :            :                 /* If there are no reloads but changing due
    2463                 :            :                    elimination, restart the constraint sub-pass
    2464                 :            :                    first.  */
    2465                 :          0 :                 continue;
    2466                 :            :             }
    2467                 :            :           /* Do inheritance only for regular algorithms.  */
    2468                 :     984868 :           if (! lra_simple_p)
    2469                 :     984861 :             lra_inheritance ();
    2470                 :     984868 :           if (live_p)
    2471                 :      40772 :             lra_clear_live_ranges ();
    2472                 :     984870 :           bool fails_p;
    2473                 :     984862 :           do
    2474                 :            :             {
    2475                 :            :               /* We need live ranges for lra_assign -- so build them.
    2476                 :            :                  But don't remove dead insns or change global live
    2477                 :            :                  info as we can undo inheritance transformations after
    2478                 :            :                  inheritance pseudo assigning.  */
    2479                 :     984870 :               lra_create_live_ranges (true, !lra_simple_p);
    2480                 :     984870 :               live_p = true;
    2481                 :            :               /* If we don't spill non-reload and non-inheritance
    2482                 :            :                  pseudos, there is no sense to run memory-memory move
    2483                 :            :                  coalescing.  If inheritance pseudos were spilled, the
    2484                 :            :                  memory-memory moves involving them will be removed by
    2485                 :            :                  pass undoing inheritance.  */
    2486                 :     984870 :               if (lra_simple_p)
    2487                 :          7 :                 lra_assign (fails_p);
    2488                 :            :               else
    2489                 :            :                 {
    2490                 :     984863 :                   bool spill_p = !lra_assign (fails_p);
    2491                 :            :                   
    2492                 :     984863 :                   if (lra_undo_inheritance ())
    2493                 :      71287 :                     live_p = false;
    2494                 :     984863 :                   if (spill_p && ! fails_p)
    2495                 :            :                     {
    2496                 :      17474 :                       if (! live_p)
    2497                 :            :                         {
    2498                 :       7493 :                           lra_create_live_ranges (true, true);
    2499                 :       7493 :                           live_p = true;
    2500                 :            :                         }
    2501                 :      17474 :                       if (lra_coalesce ())
    2502                 :            :                         live_p = false;
    2503                 :            :                     }
    2504                 :     984376 :                   if (! live_p)
    2505                 :      64281 :                     lra_clear_live_ranges ();
    2506                 :            :                 }
    2507                 :     984870 :               if (fails_p)
    2508                 :            :                 {
    2509                 :            :                   /* It is a very rare case.  It is the last hope to
    2510                 :            :                      split a hard regno live range for a reload
    2511                 :            :                      pseudo.  */
    2512                 :         10 :                   if (live_p)
    2513                 :          9 :                     lra_clear_live_ranges ();
    2514                 :         10 :                   live_p = false;
    2515                 :         10 :                   if (! lra_split_hard_reg_for ())
    2516                 :            :                     break;
    2517                 :            :                 }
    2518                 :            :             }
    2519                 :            :           while (fails_p);
    2520                 :     984868 :           if (! live_p) {
    2521                 :            :             /* We need the correct reg notes for work of constraint sub-pass.  */
    2522                 :      64288 :             lra_create_live_ranges (true, true);
    2523                 :      64288 :             live_p = true;
    2524                 :            :           }
    2525                 :            :         }
    2526                 :            :       /* Don't clear optional reloads bitmap until all constraints are
    2527                 :            :          satisfied as we need to differ them from regular reloads.  */
    2528                 :    1027530 :       bitmap_clear (&lra_optional_reload_pseudos);
    2529                 :    1027530 :       bitmap_clear (&lra_subreg_reload_pseudos);
    2530                 :    1027530 :       bitmap_clear (&lra_inheritance_pseudos);
    2531                 :    1027530 :       bitmap_clear (&lra_split_regs);
    2532                 :    1027530 :       if (! live_p)
    2533                 :            :         {
    2534                 :            :           /* We need full live info for spilling pseudos into
    2535                 :            :              registers instead of memory.  */
    2536                 :          0 :           lra_create_live_ranges (lra_reg_spill_p, true);
    2537                 :          0 :           live_p = true;
    2538                 :            :         }
    2539                 :            :       /* We should check necessity for spilling here as the above live
    2540                 :            :          range pass can remove spilled pseudos.  */
    2541                 :    1027530 :       if (! lra_need_for_spills_p ())
    2542                 :            :         break;
    2543                 :            :       /* Now we know what pseudos should be spilled.  Try to
    2544                 :            :          rematerialize them first.  */
    2545                 :      83724 :       if (lra_remat ())
    2546                 :            :         {
    2547                 :            :           /* We need full live info -- see the comment above.  */
    2548                 :       1588 :           lra_create_live_ranges (lra_reg_spill_p, true);
    2549                 :       1588 :           live_p = true;
    2550                 :       1588 :           if (! lra_need_for_spills_p ())
    2551                 :            :             {
    2552                 :        286 :               if (lra_need_for_scratch_reg_p ())
    2553                 :          0 :                 continue;
    2554                 :            :               break;
    2555                 :            :             }
    2556                 :            :         }
    2557                 :      83438 :       lra_spill ();
    2558                 :            :       /* Assignment of stack slots changes elimination offsets for
    2559                 :            :          some eliminations.  So update the offsets here.  */
    2560                 :      83438 :       lra_eliminate (false, false);
    2561                 :      83438 :       lra_constraint_new_regno_start = max_reg_num ();
    2562                 :      83438 :       if (lra_bad_spill_regno_start == INT_MAX
    2563                 :      83438 :           && lra_inheritance_iter > LRA_MAX_INHERITANCE_PASSES
    2564                 :        529 :           && lra_rematerialization_iter > LRA_MAX_REMATERIALIZATION_PASSES)
    2565                 :            :         /* After switching off inheritance and rematerialization
    2566                 :            :            passes, avoid spilling reload pseudos will be created to
    2567                 :            :            prevent LRA cycling in some complicated cases.  */
    2568                 :          0 :         lra_bad_spill_regno_start = lra_constraint_new_regno_start;
    2569                 :      83438 :       lra_assignment_iter_after_spill = 0;
    2570                 :            :     }
    2571                 :     944096 :   restore_scratches ();
    2572                 :     944096 :   lra_eliminate (true, false);
    2573                 :     944096 :   lra_final_code_change ();
    2574                 :     944096 :   lra_in_progress = 0;
    2575                 :     944096 :   if (live_p)
    2576                 :     944096 :     lra_clear_live_ranges ();
    2577                 :     944096 :   lra_live_ranges_finish ();
    2578                 :     944096 :   lra_constraints_finish ();
    2579                 :     944096 :   finish_reg_info ();
    2580                 :     944096 :   sbitmap_free (lra_constraint_insn_stack_bitmap);
    2581                 :     944096 :   lra_constraint_insn_stack.release ();
    2582                 :     944096 :   finish_insn_recog_data ();
    2583                 :     944096 :   regstat_free_n_sets_and_refs ();
    2584                 :     944096 :   regstat_free_ri ();
    2585                 :     944096 :   reload_completed = 1;
    2586                 :     944096 :   update_inc_notes ();
    2587                 :            : 
    2588                 :     944096 :   inserted_p = fixup_abnormal_edges ();
    2589                 :            : 
    2590                 :            :   /* We've possibly turned single trapping insn into multiple ones.  */
    2591                 :     944096 :   if (cfun->can_throw_non_call_exceptions)
    2592                 :            :     {
    2593                 :     363920 :       auto_sbitmap blocks (last_basic_block_for_fn (cfun));
    2594                 :     181960 :       bitmap_ones (blocks);
    2595                 :     181960 :       find_many_sub_basic_blocks (blocks);
    2596                 :            :     }
    2597                 :            : 
    2598                 :     944096 :   if (inserted_p)
    2599                 :       2177 :     commit_edge_insertions ();
    2600                 :            : 
    2601                 :            :   /* Replacing pseudos with their memory equivalents might have
    2602                 :            :      created shared rtx.  Subsequent passes would get confused
    2603                 :            :      by this, so unshare everything here.  */
    2604                 :     944096 :   unshare_all_rtl_again (get_insns ());
    2605                 :            : 
    2606                 :     944096 :   if (flag_checking)
    2607                 :     944084 :     check_rtl (true);
    2608                 :            : 
    2609                 :     944096 :   timevar_pop (TV_LRA);
    2610                 :     944096 : }
    2611                 :            : 
    2612                 :            : /* Called once per compiler to initialize LRA data once.  */
    2613                 :            : void
    2614                 :     149606 : lra_init_once (void)
    2615                 :            : {
    2616                 :     149606 :   init_insn_code_data_once ();
    2617                 :     149606 : }
    2618                 :            : 
    2619                 :            : /* Called once per compiler to finish LRA data which are initialize
    2620                 :            :    once.  */
    2621                 :            : void
    2622                 :     198377 : lra_finish_once (void)
    2623                 :            : {
    2624                 :     198377 :   finish_insn_code_data_once ();
    2625                 :     198377 : }

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.